×

A study on the effect of the asymmetry on real capacitated vehicle routing problems. (English) Zbl 1251.90335

Summary: Matrices with distances between pairs of locations are essential for solving vehicle routing problems like the Capacitated Vehicle Routing Problem (CVRP), Traveling Salesman Problem (TSP) and others. This work deals with the complex reality of transportation networks and asymmetry. Through a series of comprehensive and thorough computational and statistical experiments we study the effect that many factors like asymmetry, geographical location of the depot and clients, demand, territory and maximum vehicle capacity have in the solution of CVRP instances. We examine both classical heuristics as well as current state-of-the-art metaheuristics and show that these methods are seriously affected by the studied factors from a solution time and quality of solutions perspective. We systematically compare the solutions obtained in the symmetric scenario with those obtained in the real asymmetric case at a quantitative as well as a qualitative level, with the objective of carefully measuring and understanding the differences between both cases.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90B10 Deterministic network models in operations research

Software:

LKH; VRP
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alba, E., Parallel metaheuristics. A new class of Algorithms (2006), Wiley: Wiley New York
[2] Christofides, N.; Eilon, S., Expected distances in distribution problems, Operations Research, 20, 4, 437-443 (1969)
[3] Clarke, G.; Wright, J., Scheduling of vehicles from central depot to number of delivery points, Operations Research, 12, 4, 568-581 (1964)
[4] Daganzo, C., The length of tours in zones of different shapes, Transportation Research Part B, 18, 2, 135-145 (1984)
[5] Dubois, N.; Semet, F., Estimation and determination of shortest-path length in a road network with obstacles, European Journal of Operational Research, 83, 1, 105-116 (1995) · Zbl 0903.90060
[6] Fisher, M., Optimal solution of vehicle-routing problems using minimum k-trees, Operations Research, 42, 4, 626-642 (1994) · Zbl 0815.90066
[7] Flood, M., The TSP, Operations Research, 4, 1, 61-75 (1956) · Zbl 1414.90304
[8] Gillett, B.; Miller, L., Heuristic algorithm for vehicle-dispatch problem, Operations Research, 22, 2, 340-349 (1974) · Zbl 0274.90013
[9] Golden, B.; Magnanti, T.; Nguyen, H., Implementing vehicle routing algorithms, Networks, 7, 2, 113-148 (1977) · Zbl 0359.90054
[10] Goodchild, M.; Kemp, K., NCGIA Core Curriculum in GIS. National center for geographic information and analysis (1990), University of California: University of California Santa Barbara CA
[11] Helsgaun, K., An effective implementation of the Lin-Kernighan Traveling Salesman Heuristic, European Journal of Operational Research, 126, 1, 106-130 (2000) · Zbl 0969.90073
[12] Laporte, G., What you should know about the vehicle routing problem, Naval Research Logistics, 54, 8, 811-819 (2007) · Zbl 1135.90308
[13] Laporte, G., Fifty years of vehicle routing, Transportation Science, 43, 4, 408-416 (2009)
[14] Laporte, G.; Mercure, H.; Nobert, Y., An exact algorithm for the asymmetrical capacitated vehicle-routing problem, Networks, 16, 1, 33-46 (1986) · Zbl 0643.90034
[15] Love, R.; Morris, J., Modeling inter-city road distances by mathematical functions, Operational Research Quarterly, 23, 1, 61-71 (1972) · Zbl 0231.90059
[16] Love, R.; Morris, J., On estimating road distances by mathematical functions, European Journal of Operational Research, 36, 2, 251-253 (1988)
[17] Nagata, Y., Edge assembly crossover for the capacitated vehicle routing problem, (Cotta, C.; van Hemert, J. I., Evolutionary computation in combinatorial optimization. Seventh European conference, EvoCOP. Lecture notes in computer science (2007), Springer: Springer Valencia), 142-153
[18] Pisinger, D.; Røpke, S., A general heuristic for vehicle routing problems, Computers & Operations Research, 34, 8, 2403-2435 (2007) · Zbl 1144.90318
[19] Rodríguez A, Ruiz R. The effect of the asymmetry of road transportation networks on the traveling salesman problem. Computers & Operations Research, in press. doi:10.1016/j.cor.2011.09.005; Rodríguez A, Ruiz R. The effect of the asymmetry of road transportation networks on the traveling salesman problem. Computers & Operations Research, in press. doi:10.1016/j.cor.2011.09.005
[20] Taillard, É. D., Parallel iterative search methods for vehicle routing problem, Networks, 23, 8, 661-693 (1993) · Zbl 0804.90045
[21] Toth, P.; Vigo, D., An overview of vehicle routing problems (2001), SIAM—Society for Industrial and Applied Mathematics: SIAM—Society for Industrial and Applied Mathematics Philadelphia
[22] Vincenty, T., Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations, Survey Review, 23, 176, 88-93 (1975)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.