Email this article 
Open Access
Subscription or Fee Access
Variant Constraint Multi Depot Vehicle Routing Problem
Abstract
This paper address variant constraint vehicle routing problem in which vehicles may be replenished at intermediate depots along their route. To solve the problem we planned to develop an exact algorithm called Lexi-Search. Tests are conducted on randomly generated instances.
Keywords
References
. E. Angelelli and M. G. Speranza. The application of a vehicle routing model to a waste-Collection problem: two case studies. Journal of the Operational Research Society, 53:944–952, 2002.
. E. Angelelli and M. G. Speranza. The periodic vehicle routing problem with intermediate facilities.European Journal of Operational Research, 137:233–247, 2002.
. J. C. S. Brand˜ao and A.Mercer. A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European Journal of Operational Research, 100:180–191, 1997.
. J. C. S. Brand˜ao and A. Mercer. The multi-trip vehicle routing problem. Journal of the Operational Research Society, 49:799–805, 1998.
. F. Cano Sevilla and C. Sim´on de Blas. Vehicle routing problem with time windows and Intermediate facilities. S.E.I.O.’03 Edicions de la Universitat de Lleida, pages 3088–3096, 2003.
. I-M. Chao, B. L. Golden, and E. A. Wasil. A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. American Journal of Mathematical and Management Sciences, 13:371–406, 1993.
. J.-F. Cordeau, M. Gendreau, and G. Laporte. A tabu search heuristic for periodic and multi-Depot vehicle routing problems. Networks, 30:105–119, 1997.
. J.-F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin, and F. Semet. A guide to vehicle Routing heuristics. Journal of the Operational Research Society, 53:512–522, 2002.
. J.-F. Cordeau, G. Laporte, and A. Mercier. A unified tabu search heuristic for vehicle routing Problems with time windows. Journal of the Operational Research Society, 52:928–936, 2001.
. G. Dueck. New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104:86–92, 1993.
. K. Fagerholt. Designing optimal routes in a liner shipping problem. Maritime Policy & Management, 31:259–268, 2004.
. B. Fleischmann. The vehicle routing problem with multiple use of vehicles. Working paper, Fachbereich Wirtschaftswissenschaften, Universit¨at Hamburg, 1990.
. M. Gendreau, A. Hertz, and G. Laporte. New insertion and postoptimization procedures for the traveling salesman problem. Operations Research, 40:1086–1094, 1992. 23
. M. Gendreau, A. Hertz, and G. Laporte. A tabu search heuristic for the vehicle routing problem. Management Science, 40:1276–1290, 1994.
. M. Gendreau, G. Laporte, and J.-Y. Potvin. Metaheuristics for the capacitated vehicle routing problem. In P. Toth and D. Vigo, editors, The Vehicle Routing Problem, pages 129–154. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002.
. B. E. Gillett and J. G. Johnson. Multi-terminal vehicle-dispatch algorithm. Omega, 4:711–718, 1976.
. B. L. Golden, T. L. Magnanti, and H. Q. Nguyen. Implementing vehicle routing algorithms. Networks, 7:113–148, 1977.
. W. C. Jordan. Truck backhauling on networks with many terminals. Transportation Research, 21B:183–193, 1987.
. W. C. Jordan and L. D. Burns. Truck backhauling on two terminal networks. Transportation Research, 18B:487–503, 1984.
. G. Laporte, Y. Nobert, and D. Arpin. Optimal solutions to capacitated multidepot vehicle Routing problems. Congressus Numerantium, 44:283–292, 1984.
. G. Laporte, Y. Nobert, and S. Taillefer. Solving a family of multi-depot vehicle routing and Locationrouting problems. Transportation Science, 22:161–172, 1988.
. G. Laporte and F. Semet. Classical heuristics for the capacitated vehicle routing problem. In P. Toth and D. Vigo, editors, The Vehicle Routing Problem, pages 109–128. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002.
. S. Lin. Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44:2245–2269, 1965.
. O. M. Raft. A modular algorithm for an extended vehicle scheduling problem. European Journal of Operational Research, 11:67–76, 1982.
. J. Renaud, G. Laporte, and F. F. Boctor. An improved petal heuristic for the vehicle routing problem. Journal of the Operational Research Society, 47:329–336, 1996.
. J. Renaud, G. Laporte, and F. F. Boctor. A tabu search heuristic for the multi-depot vehicle Routing problem. Computers & Operations Research, 23:229–235, 1996.
. Y. Rochat and ´E. D. Taillard. Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1:147–167, 1995. 24
. Suprayogi, H. Yamato, and Iskendar. Ship routing design for the oily liquid waste collection. Journal of the Society of Naval Architects of Japan, 190:325–335, 2001.
. ´E. D. Taillard, G. Laporte, and M. Gendreau. Vehicle routing with multiple use of vehicles. Journal of the Operational Research Society, 47:1065–1070, 1996.
. F. A. Tillman. The multiple terminal delivery problem with probabilistic demands. Transportation Science, 3:192–204, 1969.
. F. A. Tillman and T. M. Cain. An upperbound algorithm for the single and multiple terminal Delivery problem. Management Science, 18:664–682, 1972.
. F. A. Tillman and R. W. Hering. A study of look-ahead procedure for solving the multiterminal delivery problem. Transportation Research, 5:225–229, 1971.
. A. Wren and A. Holliday. Computer scheduling of vehicles from one or more depots to a number of delivery points. Operational Research Quarterly, 23:333–344, 1972.
. Q.-H. Zhao, S.-Y. Wang, K-K Lai, and G.-P. Xia. A vehicle routing problem with multiple use of vehicles. Advanced Modeling and Optimization, 4:21–40, 2002.
. Benoit Crevier et. al. The Multi-Depot Vehicle routing problem with Inter –Depot routes Canada Research Chair in Distribution Management, May, 2005.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.