×

Heuristic solutions for the vehicle routing problem with time windows and synchronized visits. (English) Zbl 1343.90018

Summary: We present a simulated annealing based algorithm for a variant of the vehicle routing problem (VRP), in which a time window is associated with each client service and some services require simultaneous visits from different vehicles to be accomplished. The problem is called the VRP with time windows and synchronized visits. The algorithm features a set of local improvement methods to deal with various objectives of the problem. Experiments conducted on the benchmark instances from the literature clearly show that our method is fast and outperforms the existing approaches. It produces all known optimal solutions of the benchmark in very short computational times, and improves the best results for the rest of the instances.

MSC:

90B18 Communication networks in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Afifi, S., Dang, D.C., Moukrim, A.: A simulated annealing algorithm for the vehicle routing problem with time windows and synchronization constraints. In: Proceedings of LION-7, Lecture Notes in Computer Science, vol. 7997, pp. 259-265 (2013) · Zbl 1076.90553
[2] Aho, A.V., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput. 1(2), 131-137 (1972) · Zbl 0247.05128 · doi:10.1137/0201008
[3] Baños, R., Ortega, J., Gil, C., Márquez, A.L., De Toro, F.: A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows. Comput. Ind. Eng. 65(2), 286-296 (2013) · doi:10.1016/j.cie.2013.01.007
[4] Baños, R., Ortega, J., Gil, C., Fernandez, A., De Toro, F.: A simulated annealing-based parallel multi-objective approach to vehicle routing problems with time windows. Expert Syst. Appl. 40(5), 1696-1707 (2013) · doi:10.1016/j.eswa.2012.09.012
[5] Bouly, H., Dang, D.C., Moukrim, A.: A memetic algorithm for the team orienteering problem. 4OR 8(1), 49-70 (2009) · Zbl 1186.90012 · doi:10.1007/s10288-008-0094-4
[6] Bredström, D., Rönnqvist, M.: A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints. NHH Dept of Finance and Management Science Discussion Paper (2007)
[7] Bredström, D., Rönnqvist, M.: Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. Eur. J. Oper. Res. 191(1), 19-31 (2008) · Zbl 1146.90364 · doi:10.1016/j.ejor.2007.07.033
[8] Chiang, W.C., Russell, R.A.: Simulated annealing metaheuristics for the vehicle routing problem with time windows. Ann. Oper. Res. 63(1), 3-27 (1996) · Zbl 0849.90054 · doi:10.1007/BF02601637
[9] Czech, Z., Czarnas, P.: Parallel simulated annealing for the vehicle routing problem with time windows. In: Proceedings of 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing (2002) · Zbl 0934.90008
[10] Dang, D.C., Guibadj, R.N., Moukrim, A.: An effective PSO-inspired algorithm for the team orienteering problem. Eur. J. Oper. Res. 229(2), 332-344 (2013) · Zbl 1317.90114 · doi:10.1016/j.ejor.2013.02.049
[11] Dohn, A., Rasmussen, M.S., Larsen, J.: The Vehicle Routing Problem with Time Windows and Temporal Dependencies. Networks 58(4), 273-289 (2011) · Zbl 1231.90085 · doi:10.1002/net.20472
[12] Drexl, M.: Synchronization in vehicle routing a survey of VRPs with multiple synchronization constraints. Transp. Sci. 46(3), 297-316 (2012) · doi:10.1287/trsc.1110.0400
[13] El Hachemi, N., Gendreau, M., Rousseau, L.M.: A heuristic to solve the synchronized log-truck scheduling problem. Comput. Oper. Res. 40(3), 666-673 (2013) · Zbl 1349.90854 · doi:10.1016/j.cor.2011.02.002
[14] Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1-3), 23-47 (2003) · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5
[15] Ioachim, I., Desrosiers, J., Soumis, F., Bélanger, N.: Fleet assignment and routing with schedule synchronization constraints. Eur. J. Oper. Res. 119(1), 75-90 (1999) · Zbl 0934.90008 · doi:10.1016/S0377-2217(98)00343-9
[16] Kirkpatrick, S., Vecchi, M., et al.: Optimization by simmulated annealing. Science 220(4598), 671-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[17] Lenstra, J.K., Kan, A.: Complexity of vehicle routing and scheduling problems. Networks 11(2), 221-227 (1981) · doi:10.1002/net.3230110211
[18] Li, Y., Lim, A., Rodrigues, B.: Manpower allocation with time windows and job-teaming constraints. Nav. Res. Logist. (NRL) 52(4), 302-311 (2005) · Zbl 1140.90404 · doi:10.1002/nav.20075
[19] Potvin, J.Y., Kervahut, T., Garcia, B.L., Rousseau, J.M.: The vehicle routing problem with time windows part I: tabu search. INFORMS J. Comput. 8(2), 158-164 (1996) · Zbl 0866.90057 · doi:10.1287/ijoc.8.2.158
[20] Rasmussen, M.S., Justesen, T., Dohn, A., Larsen, J.: The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies. Eur. J. Oper. Res. 219(3), 598-610 (2012) · Zbl 1253.90154 · doi:10.1016/j.ejor.2011.10.048
[21] Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254-265 (1987) · Zbl 0625.90047 · doi:10.1287/opre.35.2.254
[22] Solomon, M.M., Desrosiers, J.: Time window constrained routing and scheduling problems. Transp. Sci. 22, 1-13 (1988) · Zbl 0638.90052 · doi:10.1287/trsc.22.1.1
[23] Tavakkoli-Moghaddam, R., Gazanfari, M., Alinaghian, M., Salamatbakhsh, A., Norouzi, N.: A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing. J. Manuf. Syst. 30(2), 83-92 (2011) · doi:10.1016/j.jmsy.2011.04.005
[24] Toth, P., Vigo, D.: An overview of vehicle routing problems. Veh. Routing Probl. 9, 1-26 (2002) · Zbl 1076.90553 · doi:10.1137/1.9780898718515.ch1
[25] Van Breedam, A.: Improvement heuristics for the vehicle routing problem based on simulated annealing. Eur. J. Oper. Res. 86(3), 480-490 (1995) · Zbl 0914.90107 · doi:10.1016/0377-2217(94)00064-J
[26] Wen, M., Larsen, J., Clausen, J., Cordeau, J.F., Laporte, G.: Vehicle routing with cross-docking. J. Oper. Res. Soc. 60(12), 1708-1718 (2009) · Zbl 1196.90027 · doi:10.1057/jors.2008.108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.