×

A library of local search heuristics for the vehicle routing problem. (English) Zbl 1230.90033

Summary: The vehicle routing problem (VRP) is a difficult and well-studied combinatorial optimization problem. Real-world instances of the VRP can contain hundreds and even thousands of customer locations and can involve many complicating constraints, necessitating the use of heuristic methods. We present a software library of local search heuristics that allows one to quickly generate solutions to VRP instances. The code has a logical, object-oriented design and uses efficient data structures to store and modify solutions. The core of the library is the implementation of seven local search operators that share a similar interface and are designed to be extended to handle additional options with minimal code change. The code is well-documented, straightforward to compile, and is freely available online. The code contains several applications that can be used to generate solutions to the capacitated VRP. Computational results indicate that these applications are able to generate solutions that are within about one percent of the best-known solution on benchmark problems.

MSC:

90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Applegate, D., Bixby, R., Chvátal, V., Cook, W., Espinoza, D., Goycoolea, M., Helsgaun K.: The Concorde source code. http://www.tsp.gatech.edu/concorde.html (2010)
[2] Applegate D., Bixby R., Chvdftal V., Cook W.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton, NJ (2006) · Zbl 1130.90036
[3] Bräysy O., Gendreau M.: VRPTW, part I: Route construction and local search algorithms. Transp. Sci. 39, 104–118 (2005)
[4] Bräysy O., Gendreau M.: VRPTW, part II: Metaheuristics. Transp. Sci. 39, 119–139 (2005)
[5] Christofides N., Eilon S.: An algorithm for the vehicle dispatching problem. Oper. Res. Q. 20, 309–318 (1969)
[6] Christofides N., Mingozzi A., Toth P.: The vehicle routing problem. In: Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (eds) Combinatorial Optimization, pp. 315–338. Wiley, Chichester, UK (1979) · Zbl 0413.90075
[7] COIN-OR. Open Solver Interface (OSI). https://projects.coin-or.org/Osi/ (2010)
[8] Dueck G.: New optimization heuristics: the great-deluge algorithm and the record-to-record travel. J. Comput. Phys. 104, 86–92 (1993) · Zbl 0773.65042
[9] Fukasawa R., Longo H., Lysgaard J., Poggi D., Reis M., Uchoa E., Werneck R.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. 106(3), 491–511 (2006) · Zbl 1094.90050
[10] Gendreau M., Potvin J-Y., Bräysy O., Hasle G., Løkketangen A.: Metaheuristics for the vehicle routing problem and its extensions: a categorized bibliography. In: Golden, B., Raghavan, S., Wasil, E. (eds) The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 143–169. Springer, New York (2008) · Zbl 1187.90001
[11] Glover F., Taillard E.: A user’s guide to tabu search. Ann. Oper. Res. 41(1), 1–28 (1993) · Zbl 0772.90063
[12] GLPK, The GNU Linear Programming Kit. http://www.gnu.org/software/glpk/ (2010)
[13] Golden B., Wasil E., Kelly J., Chao I.-M.: The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results. In: Crainic, T., Laporte, G. (eds) Fleet Management and Logistics, pp. 33–56. Kluwer, Boston (1998) · Zbl 0997.90021
[14] Groër, C.: Parallel and serial algorithms for vehicle routing problems. Ph.D thesis, University of Maryland, College Park, MD (2008)
[15] Groër, C.: The VRPH software. http://sites.google.com/site/vrphlibrary/ (2010)
[16] Hassin R., Keinan A.: Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP. Oper. Res. Lett. 36(2), 243–246 (2008) · Zbl 1144.90467
[17] Helsgaun K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Euro. J. Oper. Res. 126(1), 106–130 (2000) · Zbl 0969.90073
[18] Helsgaun, K.: The LKH source code. http://www.akira.ruc.dk/\(\sim\)keld/research/LKH/ (2010)
[19] Kindervater G., Savelsbergh M.: Vehicle routing: handling edge exchanges. In: Aarts, E., Lenstra, J.K. (eds) Local Search in Combinatorial Optimization, pp. 337–360. Princeton University Press, Princeton, NJ (2003) · Zbl 0887.90060
[20] Kirkpatrick S., Gelatt C., Vecchi M.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983) · Zbl 1225.90162
[21] Kytöjoki J., Nuortio T., Bräysy O., Gendreau M.: An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Comput. Oper. Res. 47(2), 329–336 (2005) · Zbl 1141.90429
[22] Le Bouthillier A., Crainic T.: A cooperative parallel meta-heuristic for the vehicle routing problem with time windows. Comput. Oper. Res. 32, 1685–1708 (2005) · Zbl 1074.90006
[23] Li F., Golden B., Wasil E.: Very large-scale vehicle routing: new test problems, algorithms, and results. Comput. Oper. Res. 32, 1165–1179 (2005) · Zbl 1075.90013
[24] Lin S., Kernighan B.: An effective heuristic algorithm for the traveling salesman problem. Oper. Res. 21, 2245–2269 (1973) · Zbl 0256.90038
[25] Lodi A., Punnen A.: TSP software. In: Gutin, G., Punnen, A. (eds) The Traveling Salesman Problem and its Variations, pp. 737–749. Kluwer, Dordrecht (2002) · Zbl 1113.90359
[26] Lysgaard, J.: CVRPSP: A package of separation routines for the capacitated vehicle routing problem. Working Paper 03–04 (2004)
[27] Mester D., Bräysy O.: Active guided evolution strategies for the large scale vehicle routing problem with time windows. Comput. Oper. Res. 32, 1593–1614 (2005) · Zbl 1122.90403
[28] Mester D., Bräysy O.: Active-guided evolution strategies for large-scale vehicle routing problems. Comput. Oper. Res. 34, 2964–2975 (2007) · Zbl 1185.90176
[29] Nagata Y., Bräysy O.: Efficient local search limitation strategies for vehicle routing problems. In: Hemert, J., Cotta, C. (eds) EvoCOP, Volume 4972 of Lecture Notes in Computer Science, pp. 48–60. Springer, Berlin (2008)
[30] Nagata Y., Bräysy O.: Edge assembly-based memetic algorithm for the capacitated vehicle routing problem. Networks 54, 205–215 (2009) · Zbl 1206.90025
[31] PLPlot: The PLPlot software package. http://plplot.sourceforge.net/ (2010)
[32] Prins C.: A GRASP evolutionary local search hybrid for the vehicle routing problem. In: Pereira, F., Tavares, J. (eds) Bio-Inspired Algorithms for the Vehicle Routing Problem, pp. 35–53. Springer, Berlin (2009)
[33] Ralphs T.: Parallel branch and cut for capacitated vehicle routing. Parallel Comput. 29, 607–620 (2003)
[34] Ralphs, T., Guzelsoy, M., Mahajan, A.: The SYMPHONY source code. https://projects.coin-or.org/SYMPHONY (2010)
[35] Ralphs T., Kopman L., Pulleyblank W., Trotter L.: On the capacitated vehicle routing problem. Math. Program. 94, 343–359 (2003) · Zbl 1030.90131
[36] Reinelt G.: TSPLIB–a traveling salesman problem library. ORSA J. Comput. 3, 376–384 (1991) · Zbl 0775.90293
[37] Rochat Y., Taillard E.: Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1, 147–167 (1995) · Zbl 0857.90032
[38] Taillard E.: Parallel iterative search methods for vehicle routing problems. Networks 23, 661–676 (1993) · Zbl 0804.90045
[39] Taillard, E.: VRP benchmarks. http://mistic.heig-vd.ch/taillard/problemes.dir/vrp.dir/vrp.html (1993) · Zbl 0769.90052
[40] Yellow P.C.: A computational modification to the savings method of vehicle scheduling. Oper. Res. Q. 21, 281–293 (1970)
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.