Heuristics for the vehicle routing problem with multiple deliverymen

Contents

1 Introduction
1.1 Problem description
1.2 Vehicle Routing with Time Windows
1.3 Vehicle Routing with Multiple Deliverymen
1.4 Literature Overview

2 Operators
2.1 Overview
2.2 2-opt
2.2.1 Description
2.2.2 Implementation
2.2.3 Further comments
2.3 Cross
2.3.1 Description
2.3.2 Implementation
2.3.3 Further comments
2.4 Relocate
2.4.1 Description
2.4.2 Implementation
2.5 Ejection Chains
2.5.1 Description
2.5.2 Implementation
2.5.3 Further comments

3 Testing and its environment
3.1 Construction Heuristic
3.2 Test environment
3.3 Tests
3.3.1 Tests on construction parameters
3.3.2 Tests on truck reduction
3.3.3 Tests on deliverymen reduction
3.3.4 Tests on distance reduction

4 Algorithm
4.1 Description
4.2 Test results and comparison

5 Conclusion

Bibliography

List of Tables

2.1 Operator Overview

2.2 All 2-opt exchanges

2.3 Possibilities of CROSS and ICROSS

2.4 All Cross exchanges

3.1 Best initial solutions for a-step = 0.01

3.2 Best initial solutions for a-step = 0.1

3.3 Best initial solutions for different a-step values

3.4 Relocate for truck reduction

3.5 Ejection Chains for truck reduction

3.6 Ejection Chains/ Relocate combination for truck reduction . .

3.7 Relocate for deliverymen reduction

3.8 Ejection chains for deliverymen reduction

3.9 EC/ Relocate combination for deliverymen reduction

3.10 2-opt for distance reduction

3.11 Cross for distance reduction

3.12 Cross sequence length comparision

3.13 Relocate sequence length comparision

3.14 Standard sequence lengths

3.15 2-opt/Cross combination for distance reduction

4.1 Relocate sequence length comparison

4.2 Results for R101 - R112 with 25 customers

4.3 Results for R101 - R112 with 50 customers

4.4 Results for R101 - R112 with 100 customers

List of Figures

1.1 A typical route for the VRPTWMD

2.1 Cross Operator

2.2 2-opt*

2.3 I-Cross

2.4 Relocate

2.5 Ejection Chains

2.6 GENI Operator

2.7 Cyclic Transfer

3.1 R104- trucks and distance for initial solutions a-step = 0.05 .

4.1 Python Pseudo Code

Chapter 1 Introduction

1.1 Problem description

Logistics and Transportation arc major growing segments in research as well as in real world applications. Daily activities arc not possible without well de­signed transportation policies. Today's world requires not only cheap trans­portation, but also flexibility. Transportation has become an integral part of customer satisfaction, as the environment gets more demanding. Nowadays more and more products can be ordered online, including books, electronics or even groceries. Most of these products arc delivered to households or small shops without big storage areas and therefore deliveries become smaller but more frequent. If a company only owns one truck, the problem solution can be found by solving the classical Traveling Salesman Problem (TSP), the root of all routing problems. As this is not the typical case more research has been done since then. What if the deliveries arc performed by more than one truck? The routing of these trucks is not a trivial issue. This routing problem with variable trucks is called Vehicle Routing Problem (VRP) and was first mentioned by Dantzig and Ramscr [7]. A more recent description can be found in Toth and Vigo [30]. Even though TSP and VRP arc just focusing on the geographical dimension, there is a wide area of applications. As the timing of the deliveries has become more and more important, a model adaption was needed. Time slots were included into the problem for­mulation. With this adaptation much more companies could use computer aided routing for their delivery systems. The distribution problem capable to deal with this setting became widely known as Vehicle Routing Problem with Time Windows (VRPTW).

1.2 Vehicle Routing with Time Windows

This problem can be defined by a graph G = (V, E) with n + 1 nodes, with n representing the number of customers. Node 0 in the vertex set V represents the depot and is both the start and end point of each route. Each edge in E, the set of edges, is associated with a nonnegative distance. To calculate the travel time, the speed of the vehicle is needed. Additionally to the truck traveling, the service time of each customer needs to be considered. To sim­plify the modeling, the service time s and the truck travel time t are both summed in the so called total time tt. This ttij stands for the service time of customer si plus the traveling time tij from customer i to customer j. Each customer i has a given time window with an earliest start ai and a latest start fy. The starting time of service at customer i plus the total time ttij may not exceed the end of the time window of customer bj. If a truck arrives before the beginning of the time window the solution is feasible, but the vehicle has to wait until service can start. Additional to the service time and the coordinates in the 2-dimensional space, each customer is associated with a service quantity qi, that can either represent delivery or pickup quantity. Furthermore each of the similar trucks has a load capacity Q, that must not be exceeded by customer's load on each route. The aim of the problem for­mulation is to minimize the total cost composed by the weighted sum of total truck number and total distance. The model description used above can be found similarly in many papers dealing with VRPTW, see e.g. Solomon [27]. Also the data sets used in most of the articles as benchmarks, were provided by Solomon [27] in this article. As this problem is widely studied VRPTW is not the only problem concerned with routing and time windows. There exist other adaptations of VRP dealing with multiple depots or pickup and delivery at the same time. Recently, a new adaptation has been developed by Pureza et al. [21]. This adaptation also assigns deliverymen to each route in such away that service time can be reduced.

1.3 Vehicle Routing with Multiple Deliverymen

This adaption was inspired by a real world application in the tobacco and beverage industry, as deliveries had to be made on one day without violating time constraints. The Brazilian company solved this problem occurring for deliveries in areas with high population density, by assigning delivery men to each truck. These additional workers reduced service time in a way that more customers could be visited within one day. As these customers arc geo­graphically quite close due to the high population density, several customers arc clustered into a so called supernode. This clustering can be seen in 1.1 taken from Purcza et al. [21]. The truck stops at the supernode and the deliverymen assigned to the truck distribute the demand to the several cus­tomers by foot and with the help of a sack barrow. The problem was defined as Vehicle Routing Problem with Time Windows and Multiple Deliverymen (VRPTWMD). The description in this work follows the one from Purcza et al. [21]. They also define a capacity limit for deliverymen, as the truck cabin only offers limited space. The maximum number of deliverymen L is not the only adaption necessary in the classical VRPTW model. In the ob­jective function, the costs for deliverymen need to be included. Depending on the environment, the factor prices of truck and deliverymen can vary a lot. In Central Europe one might focus on simultaneous reduction of trucks and deliverymen, while in Brazil the number of deliverymen do not add sig­nificant differences to the total costs, as wages arc relatively low. The author defined two possible objective functions; the first is a lexicographic ordering of the number of trucks x, number of deliverymen y and total distance z present in the solution S.

illustration not visible in this excerpt

If the differences in cost arc not significant to justify a lexicographic ordering, an alternative version of the objective function can be used. This objective function was also implemented for the algorithm proposed in chapter 4. The aim is to minimize the weighted sum of trucks, deliverymen and total distance present in solution S.

illustration not visible in this excerpt

In equation 1.2, ci5 c2 and c3 are cost parameters that can be changed according to factor price relation. In the implementation of Pureza et al. [211 as well as in this work, the parameters used were ci = 1, c2 = 0.1 and c3 = 0.0001. This formulation is for the data used in the tests al­most lexicographic, as the maximum crew size on each truck was defined by Lmax = 3 and therefore the maximal additional costs for a full crew will not exceed 0.3. The exact mathematical model used for the VRPTWMD can be seen in Pureza et al. [21]. As the focus of this work is to introduce operators and test them, the modeling will not be discussed in detail here. The aim of this thesis is to show possible operators for this new developed VRPTWMD and propose an alternative algorithm to the ones proposed by Pureza et ah. For this, the first step was to get an overview of the topic and the literature existing. These starting points for VRPTWMD will be described in the next section.

1.4 Literature Overview

If you want to work on the VRPTW, the best way to start is to read Bravsv and Gendreau [2], as they give a compact overview of the subject under consideration. This paper is the first of two giving a general overview of the topic. It focuses on construction heuristics and local search improvement methods. For those who prefer to get a general overview of VRP and its extensions, El-Shcrbcny [8] can be recommended. If the articles mentioned so far seem to be too elaborated, it might me more useful to start to read a PhD thesis, in this ease start with Larsen [15]. If your native language is Spanish or Portuguese, Piciucras [19] or Ribas [2could be considered. A big advantage of the first thesis is that it was only finished in April 2011, being the most recent work cited here. Having read the basics, the next step might be to select a method to tackle the VRP. If one is interested in metaheuristies for the VRPTW, the work of Golden et al. fill suits perfectly. This paper focuses on the general VRP, while the second part of the paper mentioned earlier by Braysv and Gendreau [3], concentrates explicitly on VRPTW. Both arc definitely worth reading, especially the second, since it also includes several results for the metaheuristies presented there. To design the algorithm, a guide developed by Cordcau et al. [6] can be very helpful. They present four attributes that might help in the developing process. Another interesting paper, written by Golden et al. [12] at a much earlier stage, proofs to be interesting, as it is concerned with the possibilities in the future of the VRP, seen in 1986.

To work on the new developed VRPTWMD, Pureza et al. [21] is the first paper available at the moment, but it seems to be a very reasonable extension and as such there might be much more on the subject in an early future. All operators used in VRPTW also can be applied to VRPTWMD. Depending on the aim, some might be more useful than others, but in general extensive testing needs to be done, so that the structure of the new problem is known better and the operators can be applied more precisely. The following part is taken from Golden et al. fp. 808] [12] and should give an idea of the success story written by the VRP.

In summary, our expectation is that, in the area of computer- assisted vehicle routing, the next seven years will be as exciting and productive as the last seven. Furthermore, the rich interplay between theory and practice will continue to serve as a model to the operations research community.

This quotation seems to be true for each point in time since it has been written back in 1986. There is no sign that the next seven years will be less fruitful than the past seven. It seems that vehicle routing is at the moment not endangered by the seven bad years known from the Old Testament.

Chapter 2 Operators

2.1 Overview

In this section the operators used in the algorithm arc described by their origin, functionality and implementation. After each section there is some additional information and comments concerning the operator. The opera­tors used in the algorithm can be defined as intra-route, meaning a change within one route or inter-route, involving at least two routes. 2-opt is the only inter-route operator used in the algorithm. Relocate and Cross al­ways need two routes, a source and a target route. While Relocate moves customers from the source to the target route, Cross exchanges customers between target and source route. Ejection Chains is the only operator that involves two or more routes, but the exact number cannot be defined due to its properties. In Table 2.1 an overview of the operators is given by name, author, reference in the bibliography and publishing year. Those marked in gray will not be used in the algorithm, but will be mentioned in this work for comparison or as an alternative possibility.

Except for Ejection Chains and Cyclical Transfer, all operators can be seen as special cases of a A-interchange introduced bv Osman [18] for the VRP. A stands for the maximal number of customers to be moved or inserted. Osman introduced this method and the writing style used in this paper. A relocation of one customer into another route can be written as A(1,0) mean­ing one customer will be moved from the source route to the target route. A(l,2) would then be an exchange where one customer moves from the source route to the target route and two customers move the other direction. The

illustration not visible in this excerpt

Table 2.1: Operator Overview

difference between Cross and A-interchange is that Cross only considers con­secutive customers to be moved, while A-interchange tries all possible com­binations of customers (see Taillard et al. [28]). Also 2-opt can be seen as a special case of A-interchange with the same route as target and source. Ad­ditional 2-opt may only do those A-interchanges that consider consecutive customers and insert them on the same position in reversed order. Gener­ally speaking, A-interchange is the most general operator known in VRPTW context and includes several smaller and more precisely defined operators, that will be described in the next sections.

2.2 2-opt

2.2.1 Description

This operator developed by Lin [17] for the TSP can also be used for the VRP. 2-opt is a special case of the intra-route operator, generally called k- opt. It performs an exchange of k edges. Only 2-opt was implemented in this work, as time windows reduce the probability of improvement moves exchanging more than 2 edges. Given a feasible route R [0, L 2, 3, 0] the operator would now try to perform the following exchanges shown in Table 2.2.

As shown in Table 2.2 the 2-opt cuts a sequence of nodes, reverses it and re-inserts it at the same position. There is no choice where to insert it, as there only exists one possibility to reconnect and it is given by the nature of the 2-opt. According to this exchange procedure, the maximal length of the sequence to be reversed will be the number of nodes on the route. This may lead to a high number of exchanges, that arc improbable to be feasible. In the VRTW setting, it docs make sense to introduce a maximum length of the sequence to be reversed. The reasoning is the following. If the last customer on the route becomes first and the first becomes last, the route is only feasible if time windows arc very wide or the route is very short in terms of customers. The longer the sequence, the less probable it is that the exchange is feasible. If one sets the maximal length to three, the third exchange mentioned in the Tabic 2.2 would not be examined. This will save computational effort, especially if routes become much longer, but it may also exclude some possible improvement. So this operator raises the question of the appropriate sequence length, as a trade-off between solution quality and computational time. Later this issue will be tested for the setting with and without deliverymen.

illustration not visible in this excerpt

Table 2.2: All 2-opt exchanges

2.2.2 Implementation

2-opt was implemented primarily to improve distance. The computational time dedicated to distance improvements is much less than truck and deliv­erymen improvements, as these improvements arc much higher weighted in the objective function. But as the 2-opt needs low computational effort com­pared to the other operators, it could also be used after each change in the solution structure. These constant small improvements might allow truck or deliverymen reduction, that would not be possible without it. 2-opt inputs arc the maximal sequence length to exchange and a feasible solution. The maximal length of 2-opt can be defined in a configuration file by the user. 2-opt tries, starting with the first route, to perform an exchange of maximal length sequence. The exchange is only accepted if the new solution is feasi­ble and the distance on the route was reduced. If no such improvement is found on the first route, the length of the sequence to be exchanged will be decreased by one and again all exchanges on the first route will be exam­ined. If no improvement is found with the 2-opt operator with a length of two nodes (last reasonable sequence length), then 2-opt continues by trying to improve the second route by exchanging sequences with maximal length. Again, sequence length will be reduced if no improvement is found. If once a feasible distance improvement was found, the 2-opt operator starts over again with the first route and the maximal sequence length. This proce­dure could be improved as one route could be checked several times, even knowing before that there will be no improvement. This approach has been followed due to implementational reasons and it should not effect overall computational time too much, as 2-opt is very fast. It stops after examining all exchanges with a sequence length less than the maximal length on all routes, without finding any improvement. Generally after applying 2-opt, we can be sure that our route is 2-optimal, meaning that no improvement with a two edge exchange can be achieved. With this implementation we can only guarantee this by setting the maximal length of the sequence equal to the number of nodes on the route.

2.2.3 Further comments

Clearly no load feasibility cheeks need to be performed for an intra-route operator, such as 2-opt. So the only concern is time window feasibility. The operator is very popular as a fast exchange heuristic focusing on distance improvements. A very interesting input was given by Bravsv et al. [4, p. 591], as they suggest to cheek first if an exchange improves distance or not and only afterwards cheek time window feasibility. This improves the computational effort without a loss in quality, as distance cheeks arc much faster than time window cheeks. This operator may also be used to try to reduce deliverymen by rearranging customers in such a way that the number of deliverymen can be decreased by one without getting an infeasible route.

illustration not visible in this excerpt

Figure 2.1 : Cross Operator

2.3 Cross

2.3.1 Description

This inter-route operator was first mentioned by Taillard ct al.[28, p. 591]. The basic idea is to exchange two segments of different routes. As this operator is more complex than 2-opt, it also requires more decisions on how to implement it. To get an idea of the operator, consider Figure 2.1 taken from Braysy and Gcndrcau[2, p. 112]. The depot is duplicated for simplicity and represented with a square. Two routes displayed (upper and lower route). Cross is performing an exchange of the two segments fi, k] and [j, 1]. This quite obvious procedure gets more complicated if one looks more to the details. The following questions need to be answered for implementation:

(i) Do the two segments need to be of the same length?
(ii) What is the maximal length of the sequences?
(iii) Should the orientation of the segments stay the same?

Question (i) can be definitely answered with No. Cross loses its power, if it is reduced to equal length sequences. Even though, it might not be useful to exchange only one customer with an entire route. Clearly the issue under consideration depends hardly on time windows. In ease there arc time win­dows, a restriction to a maximal difference of nodes might be useful, but a detailed analysis of this issue would lead too into a different direction. The nature of the second question is not very different. Once again, it depends on the question, if time windows arc restricting the feasibility of exchanges or not. For sure there is no right or wrong number, the question can only be

illustration not visible in this excerpt

Figure 2.2:2-opt*

illustration not visible in this excerpt

Figure 2.3:I-Cross

answered by an individual trade-off between computational time and solu­tion quality. An exchange like Cross (m, n), where rn represents the number of nodes on the first route and n the number of nodes on the second, is superfluous as this leads only to a "'pseudo"’ exchange of the nodes, as the solution is not changed at all. So the longest reasonable exchanges arc Cross (n, m-1) and Cross(n-l, m). Some tests concerning maximal length of Cross will be discussed in section 3.3. One interesting fact is that, if the maximal segment length is n-1, where n is the number of nodes on each route, then the 2-opt* operator introduced by Potvin and Rousseau 1201 is already included in the Cross. This 2-opt* can be generally described as a tail exchange of two routes. Here is an example to get a firm picture. Finally question (iii) needs to be answered. Depending on the length of the segments and the width of the time windows, a reversion of one or both segments may be useful. This issue was first tackled by Braysy |1| in an environment with loose time windows. Braysy called the operator I-Cross and in combination with Cross, we can generate four different solutions out of one starting solution. These four possibilities arc evidenced Table 2.3. If intelligently implemented, the inversion of the orientation can lead to improvements without much more

illustration not visible in this excerpt

Table 2.3: Possibilities of CROSS and ICROSS

computational effort. A possibility would be starting with Cross and only if one segment violates the time windows, changing the direction of this seg­ment. If both segments lead to infeasibilities, I-Cross 4 could be tried, even though the probability of success will be lower than for the first 3 possibili­ties mentioned above.

Table 2.4 indicates the necessary edge exchanges needed for CROSS. Those needed for I-Cross can be easily found out by the reader. The routes used in the following table are Rl [0, 1, 2, 0] and R2 f0, 3, 4, 0],

illustration not visible in this excerpt

Table 2.4: All Cross exchanges

2.3.2 Implementation

The three questions need to be answered for the implementation of the op­erator. First, all possible combinations of non-empty exchanges of sequence shorter than the maximal sequence length were considered in the following order. Starting with the longest exchanges possible, the length of the second sequence is always reduced by one until it reaches the exchange with only one node of the second route.

[...]