×

zbMATH — the first resource for mathematics

A combined multistart random constructive heuristic and set partitioning based formulation for the vehicle routing problem with time dependent travel times. (English) Zbl 1391.90074
Summary: Although the vehicle routing problem (VRP) has been broadly addressed in the literature, most of the works consider constant travel times. This is a strong simplification that does not allow to correctly model real world applications. In fact, nowadays, travel times sensibly change, across the day, due to congestion phenomena. Therefore, to actually represent the reality, it is necessary to consider time dependent travel times. In this paper, the VRP with time dependent travel times, service times at nodes, and limit on the maximum route duration, is addressed. The objective function consists into minimizing the total travel time. A multistart random constructive heuristic (MRCH), in which congestion level is considered, is proposed. The routes obtained by the MRCH are then used as columns in a set partitioning formulation. Computational results, carried out on instances derived by VRP instances taken from the literature, show the efficiency and effectiveness of the proposed approach.

MSC:
90B06 Transportation, logistics and supply chain management
90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
90B20 Traffic problems in operations research
90C59 Approximation methods and heuristics in mathematical programming
Software:
GRASP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bassi de Araujo, O.; Armentano, V., A multi-start random constructive heuristic for the container loading problem, Pesquisa Operacional, 27, 2, 311-331, (2007) · Zbl 1156.90313
[2] Balseiro, S.; Loiseau, I.; Ramonet, J., An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows, Comput. Oper. Res., 38, 6, 954-966, (2011) · Zbl 1205.90042
[3] Beasley, J., Adapting the savings algorithm for varying inter-customer travel times, Omega, 9, 658-659, (1981)
[4] Cordeau, J.; G., G.; E., G., Analysis and branch-and-cut algorithm for the time-dependent travelling salesman problem, Transp. Sci., 48, 46-58, (2014)
[5] Crainic, T.; Perboli, G.; Mancini, S.; Tadei, R., Impact of generalized travel costs on satellite location in two-echelon vehicle routing problem, PROCEDIA, 39, 195-204, (2012)
[6] Dabia, S.; Ropke, S.; Van Woensel, T.; de Kok, T., Branch and price for the time-dependent vehicle routing problem with time windows, Transp. Sci., 47, 380-396, (2012)
[7] Feo, T.; M., R., Greedy randomized adaptive search procedures, J. Global Optim., 6, 109-133, (1995) · Zbl 0822.90110
[8] Festa, P.; M., R., An annotated bibliography of grasp - part i: algorithms, Int. Trans. Oper. Res., 16, 1-24, (2009) · Zbl 1153.90553
[9] Figliozzi, M., The time dependent vehicle routing problem with time windows: benchmark problems, an efficient solution algorithm, and solution characteristics, Transp. Res. Part E, 48, 3, 616-636, (2012)
[10] Fleischmann, B.; Gnutzmann, S.; Sandvoß, E., Time-varying travel times in vehicle routing., Transp. Sci., 38, 160-173, (2004)
[11] Fleurent, C.; Glover, F., Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory, INFORMS J. Comput., 11, 2, 198-204, (1999) · Zbl 1040.90541
[12] Franceschetti, A.; Honhon, D.; Van Woensel, T.; Bektaş, T.; Laporte, G., The time-dependent pollution-routing problem, Transp. Res. Part B, 56, 265-293, (2013)
[13] Gendreau, M.; Ghiani, G.; Guerriero, E., Time-dependent routing problems: a review, Comput. Oper. Res., 64, 189-197, (2015) · Zbl 1349.90164
[14] Gendreau, M.; Potvin, J., Handbook of metaheuristics, (2010), Springer, Berlin · Zbl 1198.90002
[15] Harwood, K., Investigation into heuristic methods of solving time variant Vehicle Routing Problems, (2003), Cardiff University, Ph.D. thesis
[16] Hashimoto, H.; Yagiura, M.; Ibaraki, T., An iterated local search algorithm for the time-dependent vehicle routing problem with time windows, Discrete Optim., 5, 2, 434-456, (2008) · Zbl 1169.90326
[17] Hill, A.; Benton, W., Modeling intra-city time dependent travel speeds for vehicle scheduling problems, J. Oper. Res. Soc., 43, 4, 343-351, (1992) · Zbl 0825.90358
[18] Horn, M., Efficient modeling of travel in networks with time-varying link speeds., Networks, 36, 80-90, (2000) · Zbl 0971.90009
[19] Ichoua, S.; Gendreau, M.; Potvin, J., Vehicle dispatching with time-dependent travel times, Eur. J. Oper. Res., 144, 379-396, (2003) · Zbl 1012.90003
[20] Jabali, O.; van Woensel, T.; de Kok, A. G., Analysis of travel times and CO_2 emissions in time-dependent vehicle routing, Prod. Oper. Manage., 21, 1060-1074, (2012)
[21] Jung, S.; Haghani, A., A.genetic algorithm fort he time-dependent vehicle routing problem, Transp. Res. Rec., 1771, 164-171, (2001)
[22] Kelly, J.; Xu, J., A set-partitioning-based heuristic for the vehicle routing problem, INFORMS J. Comput., 11, 2, 161-172, (1999) · Zbl 1092.90503
[23] Kok, A.; Hans, E.; Schutten, J., Vehicle routing under time-dependent travel times: the impact of congestion avoidance, Comput. Oper. Res., 39, 5, 910-918, (2012) · Zbl 1251.90021
[24] Kuo, Y.; Wang, C.-C.; Chuang, P.-Y., Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds, Comput. Ind. Eng., 57, 4, 1385-1392, (2009)
[25] Lin, S.; Kernighan, B., An effective heuristic algorithm for the travelling-salesman problem, Oper. Res., 21, (1973) · Zbl 0256.90038
[26] Maden, W.; Eglese, R.; Black, D., Vehicle routing and scheduling with time-varying data: a case study, J. Oper. Res. Soc., 61, (2009) · Zbl 1196.90070
[27] Malandraki, C.; Daskin, M., Time dependent vehicle routing problems: formulations, properties and heuristic algorithms, Transp. Sci., 26, 3, 185-200, (1992) · Zbl 0758.90029
[28] Malandraki, C.; Dial, R., A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem, Eur. J. Oper. Res., 90, 1, 45-55, (1996) · Zbl 0916.90262
[29] Mancini, S., Time dependent travel speed vehicle routing and scheduling on a real road network: the case of Torino, Transp. Res. Procedia, 3, 433-441, (2014)
[30] Marti, R., Multi-start methods, 335-368, (2003), Kluwer · Zbl 1102.90383
[31] Osvald, A.; Stirn, L., A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food, J. Food Eng., 85, 285-295, (2008)
[32] Resende, M.; Ribeiro, C., GRASP with path-relinking: recent advances and applications, 29-63, (2005), Springer
[33] Skabardonis, A.; Varaiya, P.; Petty, K., Measuring recurrent and non recurrent traffic congestion, Transp. Res. Rec., 1856, 118-124, (2003)
[34] Soler, D.; Albiach, J.; Martinez, E., A way to optimally solve a time-dependent vehicle routing problem with time windows, Oper. Res. Lett., 37, 1, 37-42, (2009) · Zbl 1154.90608
[35] Solomon, M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper. Res., 35, 2, 254-265, (1987) · Zbl 0625.90047
[36] Zhang, T.; Chaovalitwongse, W.; Zhang, Y., Scatter search for the stochastic travel-time vehicle routing problem with simultaneous Pick-ups and deliveries, Comput. Oper. Res., 39, 10, 2277-2290, (2012) · Zbl 1251.90065
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.