A way to optimally solve a time-dependent vehicle routing problem with time windows. (English) Zbl 1154.90608

Summary: We deal with a generalization of the Vehicle Routing Problem with Time Windows that considers time-dependent travel times and costs. Through several steps we transform this extension into an Asymmetric Capacitated Vehicle Routing Problem, so it can be solved both optimally and heuristically with known codes.


90C35 Programming involving graphs or networks
90B15 Stochastic network models in operations research
90B06 Transportation, logistics and supply chain management


Full Text: DOI Link


[1] Albiach, J.; Sanchis, J. M.; Soler, D., An Asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation, European J. Oper. Res., 189, 789-802 (2008) · Zbl 1146.90363
[2] Avarenga, G. B.; Mateus, G. R.; de Tomi, G., A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows, Comput. Oper. Res., 34, 1561-1584 (2007) · Zbl 1163.90357
[3] Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, Part I: Route construction and local search algorithms, Transp. Sci., 39, 104-118 (2005)
[4] Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, Part II: Metaheuristics, Transp. Sci., 39, 119-139 (2005)
[5] Chen, H. K.; Hsueh, C. F.; Chang, M. S., The real-time time-dependent vehicle routing problem, Transp. Res. Part E, 42, 383-408 (2006)
[6] Cordeau, J. F.; Desaulniers, G.; Desrosiers, J.; Solomon, M. M.; Soumis, F., The VRP with time windows, (Toth, P.; Vigo, D., The Vehicle Routing Problem. Siam Monographs on Discrete Mathematics and Applications (2002), SIAM), 157-194 · Zbl 1076.90543
[7] De Franceschi, R.; Fischetti, M.; Toth, P., A new ILP-based refinement heuristic for vehicle routing problems, Math. Program. Ser. B, 105, 471-499 (2006) · Zbl 1085.90011
[8] Donati, A. V.; Montemani, R.; Casagrande, N.; Rizzoli, A. E.; Gambardella, L. M., Time dependent vehicle routing problem with a multi ant colony system, European J. Oper. Res., 185, 1174-1191 (2008) · Zbl 1146.90328
[9] Fischetti, M.; Toth, P.; Vigo, D., A branch-and bound algorithm for the capacitated vehicle routing problem on directed graphs, Oper. Res., 42, 626-642 (1994)
[10] Fleischmann, B.; Gietz, M.; Gnutzmann, S., Time-varying travel times in vehicle routing, Transp. Sci., 38, 160-173 (2004)
[11] Ghiani, G.; Improta, G., An efficient transformation of the generalized vehicle routing problem, European J. Oper. Res., 122, 11-17 (2000) · Zbl 0968.90010
[12] Ichoua, S.; Gendreau, M.; Potvin, J. Y., Vehicle dispatching with time-dependent travel times, European J. Oper. Res., 144, 379-396 (2003) · Zbl 1012.90003
[13] Haghani, A.; Jung, S., A dynamic vehicle routing problem with time-dependent travel times, Comput. Oper. Res., 32, 2959-2986 (2005) · Zbl 1071.90011
[14] Laporte, G.; Mercure, H.; Nobert, Y., An exact algorithm for the asymmetrical capacitated vehicle-routing problem, Networks, 16, 33-46 (1986) · Zbl 0643.90034
[15] Noon, C. E.; Bean, J. C., An efficient transformation of the generalized traveling salesman problem, INFOR, 31, 39-44 (1993) · Zbl 0774.90085
[16] Pisinger, D.; Ropke, S., A general heuristic for vehicle routing problems, Comput. Oper. Res., 34, 2403-2435 (2007) · Zbl 1144.90318
[17] Potvin, J. Y.; Xu, Y.; Benyahia, I., Vehicle routing and scheduling with dynamic travel times, Comput. Oper. Res., 33, 1129-1137 (2006) · Zbl 1079.90021
[18] Vigo, D., A heuristic algorithm for the asymmetric capacitated vehicle routing problem, European J. Oper. Res., 89, 108-126 (1996) · Zbl 0908.90115
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.