×

zbMATH — the first resource for mathematics

A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. (English) Zbl 1304.90038
Summary: We consider the Cumulative Capacitated Vehicle Routing Problem (CCVRP), which is a variation of the well-known Capacitated Vehicle Routing Problem (CVRP). In this problem, the traditional objective of minimizing total distance or time traveled by the vehicles is replaced by minimizing the sum of arrival times at the customers. We propose a branch-and-cut-and-price algorithm for obtaining optimal solutions to the problem. To the best of our knowledge, this is the first published exact algorithm for the CCVRP. We present computational results based on a set of standard CVRP benchmarks and investigate the effect of modifying the number of vehicles available.

MSC:
90B06 Transportation, logistics and supply chain management
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
CVRPSP; CVRPSEP; VRP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Applegate, D.; Cook, W.; Dash, S.; Rohe, A., Solution of a MIN-MAX vehicle routing problem, INFORMS Journal of Computing, 14, 2, 132-143, (2002) · Zbl 1238.90110
[2] Augerat, P. (1995). Approche polyédrale du Problème de Tournées de Véhicules. PhD thesis, Laboratoire ARTEMIS-IMAG, Institut National Polytechnique de Grenoble, France.
[3] Bowerman, R.; Hall, B.; Calamai, P., A multi-objective optimization approach to urban school bus routing: formulation and solution method, Transportation Research Part A, 29A, 2, 107-123, (1995)
[4] Campbell, A. M.; Vandenbussche, D.; Hermann, W., Routing for relief efforts, Transportation Science, 42, 2, 127-145, (2008)
[5] Chakrabarty, D.; Swamy, C., Facility location with client latencies: linear programming based techniques for minimum latency problems, Lecture Nodes in Computer Science, 6655, 92-103, (2011) · Zbl 1339.90193
[6] Chaudhuri, K., Godfrey, B., Rao, S., & Talwar, K. (2003). Paths, trees, and minimum latency tours. In Proceedings of the 44th annual IEEE symposium on the foundations of computer science (pp. 36-45).
[7] Chen, P.; Dong, X.; Niu, Y., An iterated local search algorithm for the cumulative capacitated vehicle routing problem, (Tan, Honghua, Technology for education and learning, Advances in intelligent and soft computing, Vol. 136, (2012), Springer Berlin/Heidelberg), 575-581
[8] Christofides, N.; Eilon, S., An algorithm for the vehicle-dispatching problem, Operations Research Quarterly, 20, 3, 309-318, (1969)
[9] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (Christofides, N.; Mingozzi, A.; Toth, P.; Sandi, C., Combinatorial optimization, (1979), Wiley & Sons) · Zbl 0413.90075
[10] Christofides, N.; Mingozzi, A.; Toth, P., Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, Mathematical Programming, 20, 1, 255-282, (1981) · Zbl 0461.90067
[11] Corberán, Á.; Fernández, E.; Laguna, M.; Martí, R., Heuristic solutions to the problem of routing school buses with multiple objectives, Journal of the Operational Research Society, 53, 4, 427-435, (2002) · Zbl 1130.90305
[12] (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column generation, (2005), Springer New York, NY, USA) · Zbl 1084.90002
[13] Desrosiers, J.; Dumas, Y.; Solomon, M. M.; Soumis, F., Time constrained routing and scheduling, (Ball, M. O.; Magnanti, T. L.; Monma, C. L.; Nemhauser, G. L., Network routing, (1995), Elsevier) · Zbl 0861.90052
[14] Dewilde, T.; Cattrysse, D.; Coene, S.; Spieksma, F. C.R.; Vansteenwegen, P., Heuristics for the traveling repairman problem with profits, Computers & Operations Research, 40, 7, 1700-1707, (2013) · Zbl 1348.90634
[15] Fakcharoenphol, J.; Harrelson, C.; Rao, S., The k-traveling repairman problem, ACM Transactions on Algorithms, 3, 4, (2007)
[16] Fukasawa, R.; Longo, H.; Lysgaard, J.; Poggi de Aragão, M.; Reis, M.; Uchoa, E., Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Mathematical Programming, 106, 3, 491-511, (2006) · Zbl 1094.90050
[17] Golden, B. L.; Laporte, G.; Taillard, E. D., An adaptive memory heuristic for a class of vehicle routing problems with minmax objective, Computers & Operations Research, 24, 5, 445-452, (1997) · Zbl 0882.90031
[18] Hartl, R. F.; Hasle, G.; Janssens, G. K., Special issue on rich vehicle routing problems, editorial, Central European Journal of Operations Research, 14, 2, 103-104, (2006) · Zbl 1203.90007
[19] Irnich, S., & Desaulniers, G. (2005). Shortest path problems with resource constraints. In Desaulniers et al. (2005). · Zbl 1130.90315
[20] Jothi, R.; Raghavachari, B., Approximating the k-traveling repairman problem with repairtimes, Journal of Discrete Algorithms, 5, 2, 293-303, (2007) · Zbl 1122.90086
[21] Kara, İ., Kara, B. Y., & Yetiş, M. K. (2008). Cumulative vehicle routing problems. In T. Caric, & H. Gold (Eds.), Vehicle routing problem. InTech.
[22] Kara, İ., Kara, B. Y., & Yetiş, M. K. (2007). Energy minimizing vehicle routing problem. In A. Dress, Y. Xu, & B. Zhu (Eds.), Combinatorial optimization and applications. LNCS (Vol. 4616, pp. 62-71). · Zbl 1175.90333
[23] Ke, L.; Feng, Z., A two-phase metaheuristic for the cumulative capacitated vehicle routing problem, Computers & Operations Research, 40, 2, 633-638, (2013) · Zbl 1349.90859
[24] Laporte, G., Fifty years of vehicle routing, Transportation Science, 43, 4, 408-416, (2009)
[25] Letchford, A. N.; Lysgaard, J.; Eglese, R. W., A branch-and-cut algorithm for the capacitated open vehicle routing problem, Journal of the Operational Research Society, 58, 12, 1642-1651, (2007)
[26] Levin, A.; Penn, M., Approximation algorithm for minimizing total latency in machine scheduling with deliveries, Discrete Optimization, 5, 1, 97-107, (2008) · Zbl 1134.90018
[27] Li, C.-L.; Vairaktarakis, G.; Lee, C.-Y., Machine scheduling with deliveries to multiple customer locations, European Journal of Operational Research, 164, 1, 39-51, (2005) · Zbl 1132.90329
[28] Lysgaard, J. (2003). CVRPSEP: A package of separation routines for the capacitated vehicle routing problem. Working Paper 03-04, Department of Management Science and Logistics, Aarhus School of Business. <www.hha.dk/∼lys>.
[29] Lysgaard, J.; Letchford, A. N.; Eglese, R. W., A new branch-and-cut algorithm for the capacitated vehicle routing problem, Mathematical Programming, 100, 2, 423-445, (2004) · Zbl 1073.90068
[30] Ngueveu, S. U.; Prins, C.; Wolfler Calvo, R., An effective memetic algorithm for the cumulative capacitated vehicle routing problem, Computers & Operations Research, 37, 11, 1877-1885, (2010) · Zbl 1188.90037
[31] Ribeiro, G. M.; Laporte, G., An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem, Computers & Operations Research, 39, 3, 728-735, (2012) · Zbl 1251.90057
[32] Sbihi, A., & Eglese, R. W. (2006). The relationship between vehicle routing and scheduling and green logistics - A literature survey. Management science working paper series, Lancaster University.
[33] Silva, M. M.; Subramanian, A.; Vidal, T.; Ochi, L. S., A simple and effective metaheuristic for the minimum latency problem, European Journal of Operational Research, 221, 3, 513-520, (2012) · Zbl 1253.90012
[34] Wu, B. Y.; Huang, Z.-N.; Zhan, F.-J., Exact algorithm for the minimum latency problem, Information Processing Letters, 92, 6, 303-309, (2004) · Zbl 1173.68832
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.