A study on the effect of the asymmetry on real capacitated vehicle routing problems

Research Area: Articulos Year: 2012
Type of Publication: Article Keywords: Asymmetry, Capacitated Vehicle Routing Problem, Algorithms, Road Transportation Networks
Authors: Rodríguez, Alejandro; Ruiz, Rubén
Journal: Computers & Operations Research Volume: 39
Number: 9 Pages: 2142–2151
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.
Digital version
[ Back ]