The vehicle routing problem (VRP) is a central problem for many transportation applications. Although it is well known that it is difficult to solve, how much of this difficulty is caused by the formulation of the problem is less understood. This paper experimentally investigates how the solution times to solve a VRP with a general integer programming (IP) solver are affected by the formulation of the VRP used. The different formulations are evaluated by examining solution efficiency as a function of several a priori performance measures based on the data parameters. The experimental results show how the solution run times are sensitive to problem parameters; in particular, the sensitivity of formulations to the coefficient of variation of the cost matrix of travel times is explained by two interacting factors.
Get full access to this article
View all access options for this article.
References
1.
PalmerK., DessoukyM. M., and AbdelmaguidT.Impacts of Management Practices and Advanced Technologies on Demand-Responsive Transit Systems. Transportation Research, Part A: Policy and Practice, Vol. 38, 2004, pp. 495–509.
2.
LaporteG.The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research, Vol. 59, 1992, pp. 345–358.
3.
TothP., and VigoD.Models, Relaxations, and Exact Approaches for the Capacitated Vehicle Routing Problem. Discrete Applied Mathematics, Vol. 123, 2002, pp. 487–512.
4.
TothP., and VigoD. (eds.). The Vehicle Routing Problem: Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, Pa., 2002.
5.
LenstraJ. K., and Rinnooy KanA. H. G.Complexity of Vehicle Routing and Scheduling Problems. Networks, Vol. 11, 1981, pp. 221–227.
6.
LuQ., and DessoukyM.An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem. Transportation Science, Vol. 38, No. 4, 2004, pp. 503–514.
7.
JonesK. L., LustigI. J., FarwoldenJ. M., and PowellW. B.Multicommodity Network Flows: The Impact of Formulation on Decomposition. Mathematical Programming, Vol. 62, 1993, pp. 95–117.
8.
BaldacciR., HadjiconstantinouE., and MingozziA.An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation. Operations Research, Vol. 52, No. 5, 2004, pp. 723–738.
9.
RalphsT. K., KopmanL., PulleyblankW. R., and TrotterL. E.On the Capacitated Vehicle Routing Problem. Mathematical Programming, Vol. 94, No. 2-3, 2003, pp. 343–359.
10.
RalphsT. K.Parallel Branch and Cut for Vehicle Routing. Parallel Computing, Vol. 29, No. 5, 2003, pp. 607–629.
11.
ChristofidesN., MingozziA., and TothP.Exact Algorithms for the Vehicle Routing Problem, Based on Spanning Tree and Shortest Path Relaxations. Mathematical Programming, Vol. 20, No. 3, 1981, pp. 255–282.
12.
LaporteG., and NorbertY.Exact Algorithms for the Vehicle Routing Problem. Annals of Discrete Mathematics, Vol. 31, 1987, pp. 147–184.
13.
AgarwalY., MathurK., and SalkinH. M.A Set-Partitioning–Based Exact Algorithm for the Vehicle Routing Problem. Networks, Vol. 19, 1989, pp. 731–749.
14.
HadjiconstantinouE., ChristofidesN., and MingozziA.A New Exact Algorithm for the Vehicle Routing Problem Based on Q-Paths and K-Shortest Paths Relaxations. Annals of Operations Research, Vol. 61, 1995, pp. 21–43.
15.
MartinhonC., LucenaA., and MaculanN.Stronger K-Tree Relaxations for the Vehicle Routing Problem. European Journal of Operational Research, Vol. 158, 2004, pp. 56–71.
16.
DesrochersM., DesrosiersJ., and SolomonM. M.A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows. Operations Research, Vol. 40, 1992, pp. 342–354.
17.
CordeauJ. F., GendreauM., LaporteG., PotvinJ. Y., and SemetF.A Guide to Vehicle Routing Heuristics. Journal of the Operational Research Society, Vol. 53, No. 5, 2002, pp. 512–522.
18.
ClarkeG., and WrightJ.Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, Vol. 12, No. 4, 1964, pp. 568–581.
19.
GillettG., and MillerL.A Heuristic Algorithm for the Vehicle Dispatch Problem. Operations Research, Vol. 22, 1974, pp. 340–349.
20.
GendreauM., HertzA., and LaporteG.A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science, Vol. 40, 1994, pp. 1276–1290.
21.
PotvinJ. Y., and BengioS.The Vehicle Routing Problem with Time Windows. Part II: Genetic Search. INFORMS Journal on Computing, Vol. 8, No. 2, 1996, pp. 165–172.
22.
OsmanI. H.Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem. Annals of Operations Research, Vol. 41, 1993, pp. 421–451.
23.
HombergerJ., and GehringH.Two Evolutionary Metaheuristics for the Vehicle Routing Problem with Time Windows. INFOR, Vol. 37, No. 3, 1999, pp. 297–318.
24.
DiazB. D.The VRP Web. neo.lcc.uma.es/radi-aeb/WebVRP. Accessed March 7, 2007.
25.
FisherM. L.Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees. Operations Research, Vol. 42, 1994, pp. 626–642.
26.
ChristofidesN., and EilonS.An Algorithm for the Vehicle Dispatching Problem. Operational Research Quarterly, Vol. 20, 1969, pp. 309–318.
27.
GentI. P., and WalshT.The TSP Phase Transition. Artificial Intelligence, Vol. 88, 1996, pp. 349–358.
28.
CheesemanF., KanefskyB., and TaylorW. M.Where the Really Hard Problems Are. Proc., NCAI-91, Sydney, Australia, 1991, pp. 331–337.
29.
ZhangW.Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem. Journal of Artificial Intelligence Research, Vol. 21, 2004, pp. 471–497.
30.
ZhangW., and KorfR. E.A Study of Complexity Transitions on the Asymmetric Traveling Salesman Problem. Artificial Intelligence, Vol. 81, No. 1-2, 1996, pp. 223–239.
31.
DesrochersM., and LaporteG.Improvements and Extensions to the Miller-Tucker-Zemlin Subtour Elimination Constraints. Operations Research Letters, Vol. 10, 1991, pp. 27–36.
32.
DessoukyM. M., HallR., NowrooziA., and MourikasK.Bus Dispatching at Timed Transfer Transit Stations Using Bus Tracking Technology. Transportation Research Part C, Vol. 7, 1999, pp. 187–208.
33.
ChristofidesN.Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem. Technical Report 388. Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, Pa., 1976.
34.
OrponenP., and MannilaH.On Approximation Preserving Reductions: Complete Problems and Robust Measures. Technical Report C-1987-28. Department of Computer Science, University of Helsinki, Finland, 1987.
