×

zbMATH — the first resource for mathematics

An effective memetic algorithm for the cumulative capacitated vehicle routing problem. (English) Zbl 1188.90037
Summary: The cumulative capacitated vehicle routing problem (CCVRP) is a transportation problem which occurs when the objective is to minimize the sum of arrival times at customers, instead of the classical route length, subject to vehicle capacity constraints. This type of challenges arises whenever priority is given to the satisfaction of the customer need, e.g. vital goods supply or rescue after a natural disaster. The CCVRP generalizes the NP-hard traveling repairman problem (TRP), by adding capacity constraints and a homogeneous vehicle fleet. This paper presents the first upper and lower bounding procedures for this new problem. The lower bounds are derived from CCVRP properties. Upper bounds are given by a memetic algorithm using non-trivial evaluations of cost variations in the local search. Good results are obtained not only on the CCVRP, but also on the special case of the TRP, outperforming the only TRP metaheuristic published.

MSC:
90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
Software:
VRP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Archer, A.; Levin, A.; Williamson, D.P., A faster, better approximation algorithm for the minimum latency problem, SIAM journal on computing, 5, 37, 1473-1498, (2008) · Zbl 1181.68326
[2] Arkin, E.M.; Hassin, R.; Levin, A., Approximations for minimum and min – max vehicle routing problems, Journal of algorithms, 59, 1, 1-18, (2006) · Zbl 1112.68135
[3] Bertacco, L.; Brunetta, L.; Fischetti, M., The linear ordering problem with cumulative costs, European journal of operational research, 189, 3, 1345-1357, (2008) · Zbl 1146.90497
[4] Bianco, L.; Mingozzi, A.; Ricciardelli, S., The traveling salesman problem with cumulative costs, Networks, 23, 2, 81-91, (1993) · Zbl 0821.90121
[5] Blum A, Chalasani P, Coppersmith D, Pulleyblank B, Raghavan P, Sudan M. The minimum latency problem. In: Proceedings of the twenty-sixth annual ACM symposium on theory of computing (STOC ’94); 1994. p. 163-71. · Zbl 1345.90073
[6] Campbell, A.M.; Vandenbussche, D.; Hermann, W., Routing for relief efforts, Transportation science, 42, 2, 127-145, (2008)
[7] Chaudhuri K, Godfrey B, Rao S, Talwar K. Paths, trees, and minimum latency tours. In: FOCS ’03: proceedings of the 44th annual IEEE symposium on foundations of computer science, Washington, DC, USA. Spring, MD: IEEE Computer Society Press Silver; 2003. p. 36.
[8] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (), 315-338
[9] Cordone R, Wolfler Calvo R. Note on time window constraints in routing problems. Internal Report 96.005, Dipartimento di Electronica e Informazione, Politechnico di Milano, Milan, Italy; 1996. · Zbl 0994.90036
[10] Fischetti, M.; Laporte, G.; Martello, S., The delivery man problem and cumulative matroids, Operations research, 6, 1055-1064, (1993) · Zbl 0791.90062
[11] Kallehauge, B.; Larsen, J.; Madsen, O.B.G., Lagrangian duality applied to the vehicle routing problem with time windows, Computers and operations research, 33, 1464-1487, (2006) · Zbl 1126.90038
[12] Kara, I.; Yetis, B.K.; Yetis, K., Energy minimizing vehicle routing problem, (), 62-71 · Zbl 1175.90333
[13] Kindervater, G.; Savelsbergh, M., Vehicle routing: handling edge exchanges, (), 337-360 · Zbl 0887.90060
[14] 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, 1642-1651, (2007)
[15] Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers and operations research, 31, 1985-2002, (2004) · Zbl 1100.90504
[16] Reinelt G. \(\langle\)http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/⟩; 1995.
[17] Sahni S, Gonzalez T. P-complete problems and approximate solutions. In: 15th annual symposium on switching and automata theory. London: IEEE, October 1974. p. 28-32.
[18] Salehipour A, Sörensen K, Goos P, Bräysy O. An efficient \(\operatorname{GRASP} + \operatorname{VND}\) metaheuristic for the traveling repairman problem. Working paper, University of Antwerp, Faculty of Applied Economics, May 2008.
[19] Sarubbi J, Luna H, Miranda G. Minimum latency problem as a shortest path problem with side constraints. In: XIV latin Ibero-American congress on operations research (CLAIO); 2008.
[20] Savelsbergh, M.W.P., The vehicle routing problem with time windows: minimizing route duration, INFORMS journal on computing, 4, 146-154, (1992) · Zbl 0780.90105
[21] Wu, B.Y.; Huang, Z.-N.; Zhan, F.-J., Exact algorithms 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.