Multi-type ant system algorithm for the time dependent vehicle routing problem with time windows

doi:10.21629/JSEE.2018.03.20

Abstract

Abstract:

The time dependent vehicle routing problem with time windows (TDVRPTW) is considered. A multi-type ant system (MTAS) algorithm hybridized with the ant colony system (ACS) and the max-min ant system (MMAS) algorithms is proposed. This combination absorbs the merits of the two algorithms in solutions construction and optimization separately. In order to improve the efficiency of the insertion procedure, a nearest neighbor selection (NNS) mechanism, an insertion local search procedure and a local optimization procedure are specified in detail. And in order to find a balance between good scouting performance and fast convergence rate, an adaptive pheromone updating strategy is proposed in the MTAS. Computational results confirm the MTAS algorithm's good performance with all these strategies on classic vehicle routing problem with time windows (VRPTW) benchmark instances and the TDVRPTW instances, and some better results especially for the number of vehicles and travel times of the best solutions are obtained in comparison with the previous research.

Key words: multi-type ant system (MTAS), time dependent, vehicle routing problem with time windows (VRPTW), nearest neighbor selection (NNS)

Ye DENG, Wanhong ZHU, Hongwei LI, Yonghui ZHENG. Multi-type ant system algorithm for the time dependent vehicle routing problem with time windows[J]. Journal of Systems Engineering and Electronics, 2018, 29(3): 625-638.

Figures/Tables 12

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Table 1

Table 2

Table 3

Table 4

Table 5

Table 6

References 58

1	DANTZIG G B, RAMSER J H. The truck dispatching problem. Management Science, 1959, 6 (1): 80- 91. doi: 10.1287/mnsc.6.1.80
2	CLARKE G, WRIGHT J W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964, 12 (4): 568- 581. doi: 10.1287/opre.12.4.568
3	AVCI M, TOPALOGLU S. An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries. Computers & Industrial Engineering, 2015, 83, 15- 29.
4	ZHANG T, CHAOVALITWONGSE W A, ZHANG Y. Integrated ant colony and tabu search approach for time dependent vehicle routing problems with simultaneous pickup and delivery. Journal of Combinatorial Optimization, 2014, 28 (1): 288- 309.
5	BELLOSO J, JUAN A A, MARTINEZ E, et al. A biasedrandomized metaheuristic for the vehicle routing problem with clustered and mixed backhauls. Networks, 2017, 69 (3): 241- 255. doi: 10.1002/net.21734
6	LUO Z, QIN H, CHE C H, et al. On service consistency in multi-period vehicle routing. European Journal of Operational Research, 2015, 243 (3): 731- 744.
7	CHENG C, QI M, WANG X, et al. Multi-period inventory routing problem under carbon emission regulations. International Journal of Production Economics, 2016, 182, 263- 275. doi: 10.1016/j.ijpe.2016.09.001
8	GENDREAU M, GHIANI G, GUERRIERO E. Timedependent routing problems: a review. Computers & Operations Research, 2015, 64 (1): 189- 197.
9	MALANDRAKI C, DASKIN M S. Time dependent vehicle routing problems: formulations, properties and heuristic algorithms. Transportation Science, 1992, 26 (3): 185- 200. doi: 10.1287/trsc.26.3.185
10	ICHOUA S, GENDREAU M, POTVIN J Y. Vehicle dispatching with time-dependent travel times. European Journal of Operational Research, 2003, 144 (2): 379- 396.
11	AHN B H, SHIN J Y. Vehicle-routeing with time windows and time-varying congestion. Journal of the Operational Research Society, 1991, 42 (5): 393- 400. doi: 10.1057/jors.1991.81
12	FLEISCHMANN B, GIETZ M, GNUTZMANN S. Timevarying travel times in vehicle routing. Transportation Science, 2004, 38 (2): 160- 173. doi: 10.1287/trsc.1030.0062
13	ALBIACH J, SANCHIS J, SOLER D. An asymmetric TSP with time windows and with time-dependent travel times and costs: an exact solution through a graph transformation. European Journal of Operational Research, 2008, 189 (3): 789- 802.
14	OSVALD A, STIRN L Z. A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food. Journal of Food Engineering, 2008, 85 (2): 285- 295. doi: 10.1016/j.jfoodeng.2007.07.008
15	KUO Y. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Computers & Industrial Engineering, 2010, 59 (1): 157- 165.
16	BALSEIRO S R, LOISEAU I, RAMONET J. An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows. Computers & Operations Research, 2011, 38 (6): 954- 966.
17	HASHIMOTO H, YAGIURA M, IBARAKI T. An iterated local search algorithm for the time-dependent vehicle routing problem with time windows. Discrete Optimization, 2008, 5 (2): 434- 456. doi: 10.1016/j.disopt.2007.05.004
18	FIGLIOZZI M A. The time dependent vehicle routing problem with time windows: benchmark problems, an efficient solution algorithm, and solution characteristics. Transportation Research Part E: Logistics and Transportation Review, 2012, 48 (3): 616- 636. doi: 10.1016/j.tre.2011.11.006
19	KOK A L, HANS E, SCHUTTEN J. Vehicle routing under time-dependent travel times: the impact of congestion avoidance. Computers & Operations Research, 2012, 39 (5): 910- 918.
20	MINOCHA B, TRIPATHI S. Two phase algorithm for solving VRPTW problem. International Journal of Artificial Intelligence and Expert Systems, 2013, 4 (1): 1- 16.
21	BEHROUZ A N, ALIREZA A N. A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet. Journal of King Saud University-Engineering Sciences, 2014, 29 (1): 29- 34.
22	SETAK M, HABIBI M, KARIMI H, et al. A time-dependent vehicle routing problem in multigraph with FIFO property. Journal of Manufacturing Systems, 2015, 35, 37- 45. doi: 10.1016/j.jmsy.2014.11.016
23	LECLUYSE C, VAN WOENSEL T, PEREMANS H. Vehicle routing with stochastic time-dependent travel times. 4OR, 2009, 7 (4): 363- 377. doi: 10.1007/s10288-009-0097-9
24	DUAN Z, SUN S, SUN S, et al. Stochastic time-dependent vehicle routing problem: mathematical models and ant colony algorithm. Advances in Mechanical Engineering, 2015, 7 (11): 1- 16.
25	WEN L, EGLESE R. Minimum cost VRP with timedependent speed data and congestion charge. Computers & Operations Research, 2015, 56, 41- 50.
26	DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agents. IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(1): 29-41.
27	GAMBARDELLA L M, DORIGO M. Ant-Q: a reinforcement learning approach to the traveling salesman problem. Proc. of the 12th International Conference on Machine Learning, 1995: 252-260.
28	DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. on Evolutionary Computation, 1997, 1(1): 53-66.
29	STÜTZLE T, HOOS H H. MAX-MIN ant system. Future Generation Computer Systems, 2000, 16 (8): 889- 914. doi: 10.1016/S0167-739X(00)00043-1
30	BULLNHEIMER B, HARTL R F, STRAUSS C. A new rank based version of the ant system-a computational study. Central European Journal of Operations Research, 1997, 7 (1): 25- 38.
31	BLUM C, DORIGO M. The hyper-cube framework for ant colony optimization. IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, 2004, 34(2): 1161-1172.
32	GAMBARDELLA L M, TAILLARD E, AGAZZI G, et al. MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows. Proc. of the New Ideas in Optimization, 1999: 63-76.
33	DONATI A V, GAMBARDELLA L M, CASAGRANDE N, et al. Time dependent vehicle routing problem with an ant colony system. IDSIA Report, 2003, 185 (3): 1174- 1191.
34	DONATI A V, MONTEMANNI R, CASAGRANDE N, et al. Time dependent vehicle routing problem with a multi ant colony system. European Journal of Operational Research, 2008, 185 (3): 1174- 1191.
35	DONATI A V, MONTEMANNI R, GAMBARDELLA L M, et al. Integration of a robust shortest path algorithm with a time dependent vehicle routing model and applications. Computational Intelligence for Measurement Systems & Applications, 2003, 48 (5): 26- 31.
36	KUMAR S N, PANNEERSELVAM R. A comparative study of proposed genetic algorithm-based solution with other algorithms for time-dependent vehicle routing problem with time windows for e-commerce supply chain. Journal of Service Science & Management, 2015, 8 (6): 844- 859.
37	HUART V, PERRON S, CAPOROSSI G, et al. A Heuristic for the time-dependent vehicle routing problem with time windows. Cham, Switzerland: Springer International Publishing, 2016.
38	SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 1987, 35 (2): 254- 265. doi: 10.1287/opre.35.2.254
39	POTVIN J Y, ROUSSEAU J M. A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. European Journal of Operational Research, 1993, 66 (3): 331- 340.
40	ATKINSON J B. A greedy look-ahead heuristic for combinatorial optimization: an application to vehicle scheduling with time windows. Journal of the Operational Research Society, 1994, 45 (6): 673- 684. doi: 10.1057/jors.1994.105
41	IOANNOU G, KRITIKOS M, PRASTACOS G. A greedy look-ahead heuristic for the vehicle routing problem with time windows. Journal of the Operational Research Society, 2001, 52 (5): 523- 537. doi: 10.1057/palgrave.jors.2601113
42	LAU H C, SIM M, TEO K M. Vehicle routing problem with time windows and a limited number of vehicles. European Journal of Operational Research, 2003, 148 (3): 559- 569.
43	LIM A, ZHANG X. A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows. Informs Journal on Computing, 2007, 19 (3): 443- 457. doi: 10.1287/ijoc.1060.0186
44	LIN S. Computer solutions of the traveling salesman problem. Bell System Technical Journal, 1965, 44 (10): 2245- 2269. doi: 10.1002/j.1538-7305.1965.tb04146.x
45	FOSIN J, CARIC T, IVANJKO E. Vehicle routing optimization using multiple local search improvements. Automatika, 2014, 55 (2): 124- 132. doi: 10.7305/automatika.2014.01.580
46	ILHAN O R. Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Evanston, United States: Northwestern University, 1976.
47	OSMAN I H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 1993, 41 (4): 421- 451. doi: 10.1007/BF02023004
48	TAILLARD E, BADEAU P, GENDREAU M, et al. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 1997, 31 (2): 170- 186. doi: 10.1287/trsc.31.2.170
49	DOHN A, RASMUSSEN M S, LARSEN J. The vehicle routing problem with time windows and temporal dependencies. Networks, 2011, 58 (4): 273- 289. doi: 10.1002/net.20472
50	GENDREAU M, HERTZ A, LAPORTE G. New insertion and postoptimization procedures for the traveling salesman problem. Operations Research, 1991, 40 (6): 1086- 1094.
51	DESROCHERS M, LENSTRA J K, SAVELSBERGH M W P, et al. Vehicle routing with time windows: optimization and approximation. Proc. of the Vehicle Routing: Methods & Studies, 1987: 65-84.
52	GAMBARDELLA L M, TAILLARD E, AGAZZI G. MACSVRPTW: a multiple ant colony system for vehicle routing problems with time windows, IDSIA-06-99. Lugano, Switzerland: Technical Report Idsia, 1999.
53	STÜTZLE T, HOOS H H. Improving the ant system: a detailed report on the MAX-MIN ant system. FG Intellektik, FB Informatik, TU Darmstadt, 1996, 12 (1): 1- 22.
54	HOMBERGER J, GEHRING H. Two evolutionary metaheuristics for the vehicle routing problem with time windows. Information, 1999, 37 (3): 297- 318.
55	STÜTZLE T. Local search algorithms for combinatorial problems: analysis, improvements and new applications. Donauworth: STM Publishing House, 1999.
56	STUTZLE T, HOOS H. Improvements on the ant-system: introducing the MAX-MIN ant system. Proc. of the Artificial Neural Nets and Genetic Algorithms, 1998: 245-249.
57	BENT R, VAN HENTENRYCK P. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, 2004, 38 (4): 515- 530. doi: 10.1287/trsc.1030.0049
58	LIM A, ZHANG X. A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows. INFORMS Journal on Computing, 2007, 19 (3): 443- 457. doi: 10.1287/ijoc.1060.0186

Instance	ACS-TIME		MMAS-TIME		MMAS-TIME + adaptive strategy
Instance	BTD/NV	Gap/%	BTD/NV	Gap/%	BTD/NV	Gap/%
R101	1 668.74/20	0.40	1 657.45/20	0.41	1 657.45/20	0.14
R108	978.64/11	0.32	974.90/11	0.40	972.04/11	0.08
C101	824.94/10	0.00	824.94/10	0.00	824.94/10	0.00
C104	905.36/10	0.21	903.99/10	0.08	899.48/10	0.13
RC104	1 190.13/11	0.52	1 171.46/11	0.11	1 151.80/11	0.50
RC106	1 420.24/13	0.25	1 420.71/13	0.30	1 386.99/13	1.29
Average	1 164.68/12.5	0.31	1 158.91/12.5	0.24	1 148.78/12.5	0.41

Class	MTAS				IRCI by Figliozzi (2012)
Class	ANV	ATT	ATD	AV	ANV	ATT	ATD	AV
R1	11.67	1 071^*	1 297^*	1.21	11.67	1 080	1 295	1.20
R2	2.73^*	1 022	1 275	1.25	2.82	990	1 216	1.23
C1	10.00	686^*	828^*	1.21	10.00	729	879	1.21
C2	3.00	502^*	590^*	1.18	3.00	563	657	1.17
RC1	11.25^*	1 185	1 468	1.24	11.38	1 164	1 405	1.21
RC2	3.25	1 166^*	1 455	1.25	3.25	1 177	1 444	1.23

Class	MTAS				IRCI by Figliozzi (2012)
Class	ANV	ATT	ATD	AV	ANV	ATT	ATD	AV
R1	10.67^*	918	1 352	1.47	10.75	897	1 258	1.40
R2	2.45^*	887	1 332	1.50	2.55	861	1 244	1.44
C1	10.00	616^*	828^*	1.34	10.00	644	864	1.34
C2	3.00	441^*	590^*	1.34	3.00	495	654	1.32
RC1	10.38^*	992	1 462	1.47	10.50	989	1 395	1.41
RC2	2.75^*	1 013	1 502	1.48	2.88	993	1 454	1.46

Class	MTAS				IRCI by Figliozzi (2012)
Class	ANV	ATT	ATD	AV	ANV	ATT	ATD	AV
R1	9.92	785^*	1 323	1.68	9.92	793	1 237	1.56
R2	2.27	768^*	1 324	1.72	2.27	774	1 269	1.64
C1	10.00	570^*	828^*	1.45	10.00	608	880	1.45
C2	3.00	405^*	590^*	1.46	3.00	485	697	1.44
RC1	10.00	858^*	1 448	1.69	10.00	860	1 362	1.58
RC2	2.75	865^*	1 464	1.69	2.75	867	1 434	1.65