On a capacitated multivehicle routing problem

ABSTRACT

The Vehicle Routing Problem (VRP) is a discrete optimization problem with high industrial relevance and high computational complexity. The problem has been extensively studied since it was introduced by Dantzig and Ramser. In this paper, we present a version of the VRP motivated by mobile sensor networks which we call the Capacitated Multivehicle Routing Problem (CMVRP). Our objective is to determine the minimum amount of energy required to serve all jobs, which takes into account both the service requirement and the travel overhead. We present a constant factor approximation algorithm for the off-line case and a distributed algorithm for the on-line problem that uses only a constant factor more energy than the off-line solution.

REFERENCES

• 1: L. Bodin and B. Golden. Classification in vehicle routing and scheduling. Networks, 11(2):97--108, 1981.
• 2: J. Bramel and D. Simchi--Levi. Probabilistic analyses and practical algorithms for the vehicle routing problem with time windows. Operations Research, 44(3):501--509, 1996.
• 3: Olli Bräysy , Michel Gendreau, Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms, Transportation Science, v.39 n.1, p.104-118, February 2005 [doi>10.1287/trsc.1030.0056]
• 4: G. B. Dantzig and J. H. Ramser. The truck dispatching problem. Management Science, 6(1):80--91, 1959.
• 5: E. W. Dijkstra and C. S. Scholten. Termination detection for diffusing computations. Inf. Proc. Letters, 11(1):1--4, 1980.
• 6: M. L. Fisher. Optimal solution of vehicle routing problems using minimum k--trees. Operations Research, 42(4):626--642, 1994.
• 7: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 8: Naoki Katoh , Taihei Yano, An approximation algorithm for the pickup and delivery vehicle routing problem on trees, Discrete Applied Mathematics, v.154 n.16, p.2335-2349, 1 November 2006 [doi>10.1016/j.dam.2006.04.028]
• 9: G. Laporte. The vehicle routing problem: An overview of exact and approximate algorithms. European J. Oper. Res., 59:345--358, 1992.
• 10: T. Ralphs, J. Hartman, and M. Galati. Capacitated vehicle routing and some related problems. Some CVRP Slides, Rutgers University, 2001.
• 11: T. Ralphs, L. Kopman, W. Pulleyblank, and L. Trotter. On the capacitated vehicle routing problem. Accepted to Mathematical Programming, 2001.
• 12: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, The Earth Mover's Distance as a Metric for Image Retrieval, International Journal of Computer Vision, v.40 n.2, p.99-121, Nov. 2000 [doi>10.1023/A:1026543900054]
• 13: M. M. Solomon. Algorithms for the vehicle routing problem with time windows. Transportation Science, 29(2):156--166, 1995.
• 14: P. Toth , D. Vigo, An overview of vehicle routing problems, The vehicle routing problem, Society for Industrial and Applied Mathematics, Philadelphia, PA, 01
• 15: Brett Warneke , Matt Last , Brian Liebowitz , Kristofer S. J. Pister, Smart Dust: Communicating with a Cubic-Millimeter Computer, Computer, v.34 n.1, p.44-51, January 2001 [doi>10.1109/2.963443]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
capacitated multivehicle routing problem, linear programming, resource allocation, transportation problem