Abstract
In this paper, we argue that vehicle routing solutions are often tactical decisions, that should not be changed too often or too much. For marketing or other reasons, vehicle routing solutions should be stable, i.e. a new solution (when e.g. new customers require service) should be as similar as possible to a solution already in use. Simultaneously however, this new solution should still have a good quality in the traditional sense (e.g. small total travel cost). In this paper, we develop a way to measure the difference between two vehicle routing solutions. We use this distance measure to create a metaheuristic approach that will find solutions that are “close” (in the solution space) to a given baseline solution and at the same time have a high quality in the sense that their total distance traveled is small. By using this approach, the dispatcher is offered a choice of Pareto-optimal solutions, allowing him to make a trade-off between changing his existing solution and allowing a longer travel distance. Some experiments are performed to show the effectiveness of the approach.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Berger and M. Barkaoui. A new hybrid genetic algorithm for the capacitated vehicle routing problem. Journal of the Operational Research Society, 54:1254-â1262, 2004.
D. J. Bertsimas and D. Simchi-Levi. A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Operations Research, 44:286–304, 1996.
D. J. Bertsimas. A vehicle routing problem with stochastic demand. Operations Research, 40:574–585, 1992.
D.J. Bertsimas, P. Jaillet, and A. R. Odoni. A priori optimization. Operations Research, 38:1019–1033, 1990.
N. Christofides, A. Mingozzi, and P. Toth. The vehicle routing problem. In N. Christofides, A. Mingozzi, P. Toth, and C. Sandi, editors, Combinatorial optimization, pages 315–338, Chichester, 1979. John Wiley.
G. Clark and J.W. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12:568–581, 1964.
J.-F. Cordeau, M. Gendreau, A. Hertz, G. Laporte, and J.-S. Sormany. New heuristics for the vehicle routing problem. In A. Langevin and D. Riopel, editors, Logistics Systems: Design and Optimization, pages 270–297. Springer, 2005.
M. Dell'Amico and P. Toth. Algorithms and codes for dense assignment problems: the state of the art. Discrete Applied Mathematics, 100:17–48, 2000.
M.L. Fisher. Optimal solution of vehicle routing problems using minimum k-trees. Operations Research, 42:626–642, 1994.
M. Gendreau, A. Hertz, and G. Laporte. A tabu search heuristic for the vehicle routing problem. Management Science, 40:1276–1290, 1994.
P. Jaillet. A priori solution of a traveling salesman problem in which a random subset of customers is visited. Operations Research, 36:929–936, 1988.
R. Jonker and A. Volgenant. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38:325–340, 1987.
J.K. Lenstra and A.H. Rinnooy Kan. Complexity of vehicle routing and scheduling problems. Networks, 11:221–228, 1981.
V.I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics-Doklady, 10:707–710, 1966.
J. Lysgaard, A.N. Letchford, and R.W. Eglese. A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 100(2):423–445, 2004.
C. Prins. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers and Operations Research, 31(12):1885–2002, 2004.
T.K. Ralphs. Parallel branch and cut for capacitated vehicle routing. Parallel Computing, 29:607–629, 2003.
C. Rego and C. Roucairol. A parallel tabu search algorithm using ejection chains for the vehicle routing problem. In I.H. Osman and J.P. Kelly, editors, Meta-Heuristics: Theory and Applications, pages 661–675, Kluwer, Boston, 1996.
M. Reimann, K. Doerner, and R.F. Hartl. D-ants: Savings based ants divide and conquer the vehicle routing problem. Computers & Operations Research, 31:563–591, 2004.
R. Ribeiro and H.R. Lorenço. A multi-objective model for a multiperiod distribution management problem. In J. Pinho de Sausa, editor, Book of Extended Abstracs of the Fifth Metaheuristics International Conference (MIC'2001), pages 97–102, Porto, 2001.
K. Sörensen. A framework for robust and flexible optimisation using metaheuristics with applications in supply chain design. PhD thesis, University of Antwerp, 2003.
K. Sörensen and M. Sevaux. GA/PM: Genetic algorithms with population management for permutation problems. In Proceedings of MIC 2003, pages 38(1)–38(6), Kyoto, Japan, 2003.
K. Sörensen and M. Sevaux. MA/PM: Memetic algorithms with population management. Computers and Operations Research, 33:1214–1225, 2006.
É.D. Taillard. Parallel iterative search methods for vehicle routing problems. Networks, 23:661–673, 1993.
S.R. Thangiah, B. Wilson, A. Pitluga, and W. Mennell. School bus routing in rural school districts. In 9th International Conference on Computer-Aided Scheduling of Public Transport (CASPT), San Diego, California, 2004.
P. Toth and D. Vigo. The granular tabu search and its application to the vehicle routing problem. INFORMS Journal on Computing, 15: 333-â346, 2003.
P. Toth and D. Vigo. Exact algorithms for vehicle routing. In T.G. Crainic and G. Laporte, editors, Fleet Management and Logistics, pages 1–31. Kluwer Academic Publishers, Boston, 1998.
E. Ukkonen. Finding approximate patterns in strings. Journal of Algorithms, 6:132–137, 1985.
R.A. Wagner and M.J. Fischer. The string-to-string correction problem. Journal of the Association for Computing Machinery, 21:168–173, 1974.
J. Xu and J.P. Kelly. A network flow-based tabu search heuristic for the vehicle routing problem. Transportation Science, 30:379–393, 1996.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sörensen, K. Route stability in vehicle routing decisions: a bi-objective approach using metaheuristics. cent.eur.j.oper.res. 14, 193–207 (2006). https://doi.org/10.1007/s10100-006-0168-3
Issue Date:
DOI: https://doi.org/10.1007/s10100-006-0168-3