A Variable Neighborhood Search-Based Heuristic for the Multi-Depot Vehicle Routing Problem

Authors

  • Arif Imran Department of Industrial Engineering, National Institute of Technology, Jl. P.H.H Mustafa 23 Bandung 40124

:

https://doi.org/10.9744/jti.15.2.95-102

Keywords:

Meta-heuristic, routing, multi-depot, variable neighborhood.

Abstract

The multi-depot vehicle routing problem (MDVRP) is addressed using an adaptation of the variable neighborhood search (VNS). The proposed VNS algorithm besides using several neighborhoods and a number of local searches has a number of additional features. These include a scheme for identifying borderline customers, a diversivication procedure and a mechanism that aggregates and disaggregates routes between depots. The proposed algorithm is tested on the data instances from the literature and produces competitive results.

References

Ball, M., Golden, B., Assad, A., and Bodin, L., Planning for Truck Fleet Size in the Presence of a Common Carrier Option, Decision Science 14,1983, pp. 103-120.

Benton, W.C., Evaluating a Modified Heuristic for the Multiple Vehicles Scheduling Problem, Working Paper RS86-14, College Administration Science, the Ohio State University, Columbus, OH, 1986.

Cassidy, P.J., and Bennet, H.S., TRAMP-A Multi-Depot Vehicle Scheduling System, Operational Research Quarterly 23, 1972, pp. 151-162.

Chao, I.M., Golden, B., and Wasil, E., A New Heuristic for the Multi-Depot Vehicle Routing Problem that Improves upon Best-Known Solutions, American Journal Mathematics Ma-nagement Science 13, 1993, pp. 371-406.

Christofides, N., and Eilon, S. An Algorithm for the Vehicle Dispatching Problem, Operational Research Quarterly 20, 1969, pp. 309-318.

Clarke, G., and Wright, J.W., Scheduling of Vehicle from Central Depot to a Number Number of Delivery Points, Operations Research 12, 1964, pp. 568-581.

Cordeau, J.F., Gendreau, M., and Laporte, G., A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problem, Networks 30, 1997, pp. 105-119.

Dijkstra, E.W., A Note on Two Problems in Connection with Graphs, Numerische Mathematik 1, 1959, pp. 269-271.

Dorigo, M., Maniezzo,V., and Colorni, A., Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on System Man and Cybernetics 26(1), 1996, pp. 29-41.

Dueck. G., New Optimization Heuristics: The Great Deluge Algorithm and Record to Record Travel, Journal of Computation Physics 104, 1993, pp. 86-92.

Gillett, B.E., and Johnson, J.W., Multi-Terminal Vehicle Dispatching Algorithm, Omega 4, 1976, pp. 711-718.

Gillett, B.E., and Miller, L.R., A Heuristic Algorithm for the Vehicle Dispatch Problem, Operations Research 22, 1974, pp. 340-344.

Golden, B., Magnanti, T., and Nguyen, H., Implementing Vehicle Routing Algorithms, Networks 7, 1977, pp. 113-148.

Ho, W., Ho, G.T.S., Ji, P., and Lau, H.C.W., A Hybrid Genetic Algorithm for the Multi-Depot Vehicle Routing Problem, Engineering Applications of Artificial Intelligence 21, 2008, pp. 548-557.

Klots B., Gal, S., and Harpaz, A., Multi-Depot and Multi Product Delivery Optimization Problem with Time and Service Constraints. Technical Report, IBM Israel, Haifa, 1992.

Imran, A., An Adaptation of Metaheuristics for the Single and Multiple Depots Heterogeneous Fleet Vehicle Routing Problems, PhD thesis, University of Kent, United Kingdom, 2008.

Imran, A., and Okdinawati, L., An Adaptation of the Variable Neighborhood Search Heuris-tic to Solve the Vehicle Routing Problem, Jurnal Teknik Industri, Jurusan Teknik dan Manajemen Industri, Universitas Muham-madiyah Malang, 1, 2011, pp. 11-17.

Imran A, Salhi, S., and Wassan N.A., A Variable Neighborhood-Based Heuristic for the Heterogeneous Fleet Vehicle Routing Problem, European Journal of Operational Research 197, 2009, pp. 509-518.

Laporte, G., Norbert, Y., and Arpin, D., Optimal Solutions to Capacitated Multi-Depot Vehicle Routing Problem, Congressus Numerantium 44, 1984, pp. 283-292.

Laporte, G., Norbert, Y., and Taillefer, S., Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems. Transportation Science 22, 1988, pp. 161-172.

Lin, S., Computers Solutions of the Travelling Salesman Problem, Bell System Technical Journal 44, 1965, pp. 2245-2269.

Min, H., Current, J., and Schilling D., The Delivery Depot Vehicle Routing Problem with Backhauling, Journal of Business Logistics 13, 1992, pp. 259-288.

Mladenovic, N., and Hansen, P. Variable Neigh-borhood Search. Computers & Operations Research 24, 1997, pp. 1097-1100.

Perl, J., and Daskin, M.S., A Warehouse Location-Routing, Transportation Research 19B, 1985, pp. 381-396.

Renaud, J., Laporte, G., and Boctor, F.F., A Tabu Search Heuristic for the Multi-Depot Vehicle Routeing Problem, Computers & Operations Research 23, 1996, pp. 229-235.

Salhi, S., Imran, A., and Wassan, N.A., The Multi-Depot Vehicle Routing Problem with Heterogeneous Vehicle Fleet: Formulation and a Variable Neighborhood Search Implementation, Computers & Operations Research. doi/10.1016/ j.cor.2013.05.011, 2013.

Salhi, S., and Sari, M., A Multi-level Composite Heuristic for the Multi-Depot Vehicle Fleet Mix Problem, European Journal of Operational Research 103, 1997, pp. 95-112.

Tarantilis, C.D., and Kiranoudis, C.T., Distribution of Fresh Meat, Journal of Food Engineering 51, 2002, pp. 85–91.

Tillman, F., The Multiple Terminal Delivery Problem with Probabilistic Demands, Transportation Science 3, 1969, 192-204.

Tillman, F.A., and Cain, T.M., An Upper bound Algorithm for the Single and Multiple Terminal Delivery Problem, Management Science 18, 1972, pp. 664-682.

Wren, A., and Holiday, A., Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points, Operational Research Quarterly 23, 1972, pp.333-344.

Yellow, P., A Computational Modification to the Savings Method of Vehicle Scheduling, Operatio-nal Research Quarterly 21, 1970, pp. 281-283.

Yu, B., Yang, Z.Z., and Xie, J.X., A Parallel Improved Ant Colony Optimization for Multi Depot Vehicle Routing Problem, Journal of the Operational Research Society 62, 2011, pp. 183–188.

Downloads

Published

2013-12-04

How to Cite

[1]
A. Imran, “A Variable Neighborhood Search-Based Heuristic for the Multi-Depot Vehicle Routing Problem”, Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri, vol. 15, no. 2, pp. 95-102, Dec. 2013.

Issue

Vol. 15 No. 2 (2013): DECEMBER 2013

Section

Articles

License

Articles published in the Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri will be Open-Access articles distributed under the terms and conditions of the Creative Commons Attribution License (CC BY).


This work is licensed under a  Creative Commons Attribution License (CC BY).