MULTI-OBJECTIVE OPTIMIZATION OF VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

Abstract

This paper focuses on the importance of multi-objective optimization in vehicle routing problem. The main objective of this paper is to do multi-objective optimization of Solomon 100 customers 56 vehicle routing problems independently of problem type and parameters. To perform this work, firstly our mathematical model is remembered; secondly for each problem our Savings-insertion builds a good initial solution and thirdly our Reactive Tabu with a Variable Threshold improves the initial solution. The three objectives are the minimization of a number of routes, the minimization of total distance and the minimization of total time by respecting the time window and the demand of all customers. Finally, the experimental results obtained with our methodology for Solomon 100 customers 56 vehicle routing problems are showed and discussed. Our results show that the multi-objective optimization is more beneficial than the total distance minimization.

Headnote

Abstract:

This paper focuses on the importance of multi-objective optimization in vehicle routing problem. The main objective of this paper is to do multi-objective optimization of Solomon 100 customers 56 vehicle routing problems independently of problem type and parameters. To perform this work, firstly our mathematical model is remembered; secondly for each problem our Savings-insertion builds a good initial solution and thirdly our Reactive Tabu with a Variable Threshold improves the initial solution. The three objectives are the minimization of a number of routes, the minimization of total distance and the minimization of total time by respecting the time window and the demand of all customers. Finally, the experimental results obtained with our methodology for Solomon 100 customers 56 vehicle routing problems are showed and discussed. Our results show that the multi-objective optimization is more beneficial than the total distance minimization.

Key words:

Insertion, Multi-objective, Reactive Tabu, Savings, Time Windows, Vehicle Routing.

INTRODUCTION

Products distribution is a process on which products are moved from sources to customers. According to Toth and Vigo [1], transportation costs typically represent 10-20% of the final price of goods on the market. Over the past 20 years, Vehicle Routing Problem (VRP) was especially solved through the use of meta-heuristics, see Jozefowiez et al. [2], Vidal et al. [3]. Eksioglu et al. [4] made a taxonomic review of VRP defining this research field and making a fully detailed classification of variants with many examples. After the review of previous classifications and taxonomies, major journals that publish articles on this issue are listed and taxonomy is proposed. It made a classification by type of study, characteristics of scenario, physical characteristics of the problem, characteristics of information and data used. Potvin [5] made a review of biologically inspired algorithms used in the VRP. He highlighted the different variants of the problem and the different methodologies used to solve them. This review focuses on the use of biologically-inspired algorithms in solving the VRP. These include evolutionary algorithms, ant colonies, particle swarm optimization, neural networks, artificial immune systems and hybrid algorithms. Gendreau and Tarantilis [6] conducted a review of the state of art of large scale VRP, indicating the difficulty of solving the problems of more than 100 customers with exact methods. They criticized the major works in this field by highlighting the techniques used. This review made a comparison of the performance of different algorithms and an analysis based on key attributes such as effectiveness, efficiency, simplicity and flexibility. Karakatič and Podgorelec [7] made a survey of genetic algorithms for solving multi-depot VRP. They highlighted the different variants of the problem and the different genetic algorithms approaches used to solve them. This review focuses on the comparison of different selection, crossover and mutation operators used by the researchers.

Flisberg et al. [8] have proposed a multi-depot forest transportation model. The resolution method used is the generation of transport nodes by solving the linear programming problem of flow distribution and routing of these nodes with tabu search. Rancourt et al. [9] proposed a model of long-haul vehicle routing and scheduling with working hours. The resolution method used is a bi-objective tabu search algorithm. The first objective is to minimize the number of vehicles used and the second objective is the minimization of the total cost, which is the weighted sum of the total distance traveled and the corresponding total time. Rancourt and Paquette [10], based on the work of Rancourt et al. [9], established a multi-criteria optimization model of long-haul vehicle routing and scheduling with working hours. The solving method used is a multi-criteria tabu search algorithm determining a set of heuristic non-dominated solutions. The mechanism consists of a single thread in which the weights assigned to the two objectives, namely operating costs and driver inconvenience are dynamically modified and in which dominated solutions are eliminated throughout the search. Li et al. [11] have proposed a multi-depot VRP with simultaneous deliveries and pickups model. The resolution method used is iterated local search embedded adaptive neighborhood selection approach. McNabb et al. [12] tested local search move operators on the VRP with split deliveries and time windows. For this, they used eight local search operators, in combinations of up to three, paired with max-min ant system.

The problem to solve is NP-complete, assimilating according to Dhaenens et al. [13] for an extension of the traveling salesman problem. This problem is known as an NP-complete problem according to Ben Ismail et al. [14].

Unlike most other VRP authors making an arbitrary hierarchy of optimality criteria, we evaluate them all simultaneously. This simultaneous evaluation provides good solutions least questionable. It is done by minimizing the total cost which is an aggregation of costs due to different optimality criteria: the number of vehicles, the total distance and total travel time. This methodology clearly releases a good compromise solution of Multi-Objective Optimization of Vehicle Routing Problem with Time Windows (MOOVRPTW), according to the cost parameters used.

In the next section, we explain our methodology. In the third section, we present our results followed by discussion and finally we finish with a conclusion in the fourth section. 1METHODOLOGY

To perform MOOVRPTW, we remember our optimization based on Savings-insertion, followed by the Reactive tabu with a variable threshold. This allows the minimization of the total cost of transport, including hard capacity and hard time windows. Below, we remember our mathematical model (see Bagayoko et al. [15], Bagayoko et al. [16], Bagayoko et al. [17]).

Let us assume that m vehicles, with a load capacity of Q, are needed. There are L customers and one depot, which takes the index 1 at the start of the route and the index L+2 at the route end. The fleet is homogeneous, and every customer demand must be satisfied within his time window. We split every customer having a demand upper than the vehicles' load capacity to get each customer demand lower than or equal to the vehicles' load capacity. The following assumptions are made in modeling the problem:

Assumptions

a. Each customer location (xj, y), demand q, and time window (tsj = start time, fj = end time) are known;

b. Each customer is served only by one vehicle at a time;

c. Each vehicle leaves the depot (index 1) and returns to the depot (index L+2);

d. All vehicles needed are immediately available;

e. The average vehicle moving speed VS is known;

f. Each customer demand q is lower than or equal to vehicles' load capacity Q.

Notation

xj, у custom er j location

tsj customer j start time

fj customer j end time

q customer j demand

Ct total transport cost

m number of vehicles used

VS average moving speed of vehicles

Q vehicles' load capacity

L number of customers

cf unit vehicle fixed cost, covering loading and unloading

cijk unit transport cost per kilometer of vehicle k from i to j

dj distance between two locations i and j

Xjk indicates if vehicle k goes from i to j

cvt unit route time cost of vehicle

cdt unit work time cost of driver

tjk arrival time of vehicle k to customer j

wjk waiting time for vehicle k at customer j

sj customer j service time

tij time spent from i to j

yjk indicates if customer j is served by vehicle k

Tk end of vehicle k time

The studied problem is modeled and the mathematical model objective is given in (1):

...

There are eleven constraints restrictions:

...

These eleven constraints restrictions allow the realization of the objective of minimizing the total transport cost by obtaining a feasible solution directly. For details of our mathematical model, see Bagayoko et al. [15], Bagayoko et al. [16], Bagayoko et al. [17].

We applied our Savings-insertion, followed by our Reactive tabu with a variable threshold two-steps approach to solve the MOOVRPTW. The initial solution is generated using our Savings-insertion technique and serves as the starting point of the improvement technique. Our Reactive tabu with a variable threshold is used to improve this initial solution. Our methodology application allows us to find a good compromise solution of the problem. For details of different steps of our methodology, see Bagayoko et al. [16] and Bagayoko et al. [17].

In the next section, our MOOVRPTW results are presented and discussed.

2RESULTS AND DISCUSION

Our data are Solomon 100 customers 56 problems, see Solomon [18]. The central depot index is 1 and all customers are served from this depot. For cost calculation, suppose that the unit vehicle fixed cost Cf = 400$, the unit cost of transport per kilometer cijk = 2.8$, the unit vehicle route time cost per minute cvt = 1.85$, the unit driver work time cost per minute cdt = 0.45$. We used 50 as the maximum percentage of smallest customers and 49 as the maximum percentage of biggest customers. The distance between two locations i and j is calculated using symmetric problem formula:

...

Each route duration is calculated according to Kay [31] as follow: departure at depot start time and forward scan to determine earliest finish time; reverse scan from earliest finish time to determine latest start time for this earliest finish time; departure at the determined latest start time and second forward scan to delay waits as much as possible to the end of the route.

Table 1 above shows the results of applying our total cost minimization methodology. Firstly, our Savings-insertion results show that we reached 2 best-known results. Secondly, our Reactive Tabu with a Variable Threshold results shows that we reached 5 best-known results.

On table 2 is showed the comparison between Solomon [18] heuristic results and our Savings-insertion heuristic results. The average total costs of each type of problems are compared. The comparison shows that our methodology provides the best solutions for all problems types (see Fig. 1).

Below, on table 3 is showed the comparison between Chiang and Russell [26], Potvin and Bengio [21] meta-heuristics results versus our Savings-insertion followed by Reactive Tabu with Variable Threshold results. The average total costs of each type of problems are compared. The comparison shows that our methodology provides the best solutions for all problems types except problems type C2 (see Fig. 2).

Table 4, Table 5, and Table 6 show our sensitivity analysis done by increasing our cost parameters: unit vehicle fixed cost (cf), unit cost of transport per kilometer (cijk), unit route time cost (cvt) & unit work time cost (cdt) one by one. Our results indicated that our methodology reacts logically to different parameter changes.

3 CONCLUSION

In our paper we resolved the multi-objective optimization of Solomon 100 customers 56 VRP using our Savings-insertion followed by our Reactive tabu with a variable threshold. For this purpose, we remembered our mathematical model to minimize the total cost of transport and including hard capacity and hard time windows constraints. The sensitivity analysis indicated that our methodology reacts logically to different cost parameters changes. Our results show that our methodology clearly provides good solutions of the concerned problems, according to the cost parameters used. The multi-objective optimization is more beneficial than minimizing the total distance; because, multi-objective optimization offers a multitude of possibilities in the choice of cost parameters in order to make the optimization corresponding to the desired objective. We then conclude that it would be interesting to test our methodology on other problems of multi-objective optimization.

References

References

[1] Toth, P., and D. Vigo, 2001, "The vehicle routing problem", monographs on discrete mathematics and applications. Philadelphia: SIAM.

[2] Jozefowiez, N., F. Semet and E.G. Talbi, 2008, "Multi-objective vehicle routing problems". European Journal of Operational Research, vol. 189, no 2, pp. 293-309.

[3] Vidal, T., T.G., Crainic, M. Gendreau and C. Prins, 2011, "Heuristiques pour les problemes de tournées de véhicules multi-attributs ".

[4] Eksioglu, B., A.V. Vural and A. Reisman, 2009,"The vehicle routing problem: A taxonomic review ". Computers & Industrial Engineering, vol. 57, no 4, pp. 14721483.

[5] Potvin, J.Y., 2009, "A review of bio-inspired algorithms for vehicle routing". Bioinspired Algorithms for the Vehicle Routing Problem, pp. 1-34.

[6] Gendreau, M., and C.D. Tarantilis, 2010, "Solving large-scale vehicle routing problems with time windows: The state-of-the-art." CIRRELT.

[7] Karakatič, Sašo, and Vili Podgorelec, 2015, "A survey of genetic algorithms for solving multi depot vehicle routing problem". Applied Soft Computing, vol. 27, pp. 519-532.

[8] Flisberg, P., B. Lidén and M. Rönnqvist, 2009, "A hybrid method based on linear programming and tabu search for routing of logging trucks". Computers & Operations Research, vol. 36, no 4, pp. 1122-1144.

[9] Rancourt, M.E., J.F. Cordeau and G. Laporte, 2012, "Long-haul vehicle routing and scheduling with working hour rules". Transportation Science.

[10]Rancourt, Marie-Eve, and Julie Paquette, 2014, "Multicriteria Optimization of A Long-Haul Routing and Scheduling Problem". Journal of Multi-Criteria Decision Analysis, vol. 21, no 5-6, pp. 239-255.

[11] Li, Jian, Panos M Pardalos, Hao Sun, Jun Pei and Yong Zhang, 2015, "Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickup". Expert Systems with Applications, vol. 42, no 7, pp. 3551-3561.

[12] McNabb, Marcus E, Jeffery D Weir, Raymond R Hill and Shane N Hall, 2015, "Testing local search move operators on the vehicle routing problem with split deliveries and time windows". Computers & Operations Research, vol. 56, pp. 93-109.

[13] Dhaenens, C., M.L. Espinouse and B. Penz, 2008, "Classical combinatorial problems and solution techniques". Operations Research and networks, pp. 71-103.

[14] Ismail, S.B., F. Legras and G. Coppin, 2011, "Synthese du probleme de routage de véhicules?.

[15] Bagayoko, M., Dao, T. M., & Ateme-Nguema, B. H., (2015, March), "Forest vehicle routing problem solved by New Insertion and meta-heuristics". In Industrial Engineering and Operations Management (IEOM), 2015 International Conference on (ppp. 1-8). IEEE.

[16] Bagayoko, M. S., Dao, T. M., & Ateme-Nguema, B., "Multi-Objective Forest Vehicle Routing Using Savings-Insertion and Reactive Tabu with a Variable Threshold" Vol. 6 - Issue 12 (December - 2016), International Journal of Engineering Research and Applications (IJERA), ISSN: 2248-9622, www.ijera.com.

[17] Bagayoko, M. S., Ateme-Nguema, B., & Dao, T. M., "Vehicle Routing Problem Using Savings-Insertion and Reactive Tabu with a Variable Threshold" Vol. 5 - Issue 12, American Journal of Engineering Research (AJER), e-ISSN: 2320-0847 p-ISSN : 2320-0936, www.ajer.org.

[18]Solomon, Marius M., 1987, "Algorithms for the vehicle routing and scheduling problems with time window constraints". Operations research, vol. 35, no 2, pp. 254265.

[19] Desrochers, Martin, Jacques Desrosiers and Marius Solomon, 1992, "A new optimization algorithm for the vehicle routing problem with time windows". Operations research, vol. 40, no 2, pp. 342-354.

[20]Rochat, Yves, and Éric D Taillard, 1995, "Probabilistic diversification and intensification in local search for vehicle routing". Journal of heuristics, vol. 1, no 1, pp. 147-167.

[21]Potvin, Jean-Yves, and Samy Bengio. 1996. "The vehicle routing problem with time windows part II: genetic search ?. INFORMS Journal on Computing, vol. 8, no 2, pp. 165-172.

[22]Tan, Kay Chen, YH Chew and Loo Hay Lee, 2006, "A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems". European Journal of Operational Research, vol. 172, no 3, pp. 855-885.

[23] Lau, H. C., Y. F. Lim, Q. Liu, 2001, "Diversification of neighborhood via constraint-based local search and its application to VRPTW". Proc. CP-AI-OR 2001 Workshop, Kent, UK.

[24] Kallehauge, Brian, Jesper Larsen and Oli BG Madsen, 2006, "Lagrangian duality applied to the vehicle routing problem with time windows". Computers & Operations Research, vol. 33, no 5, pp. 1464-1487.

[25] Mester, David, Olli Bräysy and Wout Dullaert, 2007, "A multi-parametric evolution strategies algorithm for vehicle routing problems". Expert Systems with Applications, vol. 32, no 2, pp. 508-517.

[26] C Chiang, Wen-Chyuan, and Robert A Russell, 1997, "A reactive tabu search metaheuristic for the vehicle routing problem with time windows". INFORMS Journal on Computing, vol. 9, no 4, pp. 417-430.

[27]Thangiah, S.R., J.Y. Potvin and T. Sun, 1996, "Heuristic approaches to vehicle routing with backhauls and time windows". Computers & Operations Research, vol. 23, no 11, pp. 1043-1057.

[28] Kohl, Niklas, Jacques Desrosiers, Oli BG Madsen, Marius M Solomon and Francois Soumis, 1999, "2-path cuts for the vehicle routing problem with time windows". Transportation Science, vol. 33, no 1, pp. 101-116.

[29] Cordeau, Jean-François, Gilbert Laporte and Anne Mercier, 2001, "A unified tabu search heuristic for vehicle routing problems with time windows". Journal of the Operational Research Society, vol. 52, no 8, pp. 928-936.

[30] Jawarneh, Sana, and Salwani Abdullah, 2015, "Sequential insertion heuristic with adaptive bee colony optimisation algorithm for vehicle routing problem with time windows". PloS one, vol. 10, no 7, pp. e0130224.

[31] Kay, M., 2016, "Matlog: Logistics Engineering Matlab Toolbox", http://www.ise.ncsu.edu/kay/matlog (last accessed on July 29, 2016).