Modeling and Solving the Multi-depot Vehicle Routing Problem with Time Window by Considering the Flexible end Depot in Each Route

Mirabi, Mohammad; Shokri, Nasibeh; Sadeghieh, Ahmad

doi:10.22034/2016.3.02

Modeling and Solving the Multi-depot Vehicle Routing Problem with Time Window by Considering the Flexible end Depot in Each Route

Document Type : Research Paper

Authors

¹ Department of industrial engineering, Ayatollah Haeri University of Meybod, Meybod, Yazd, Iran

² Group of industrial engineering, ElM-O-Honar University, Yazd Iran

³ Group of industrial engineering, Yazd University, Yazd, Iran

10.22034/2016.3.02

Abstract

This paper considers the multi-depot vehicle routing problem with time window in which each vehicle starts from a depot and there is no need to return to its primary depot after serving customers. The mathematical model which is developed by new approach aims to minimizing the transportation cost including the travelled distance, the latest and the earliest arrival time penalties. Furthermore, in order to reduce the problem searching space, a novel GA clustering method is developed. Finally, Experiments are run on number problems of varying depots and time window, and customer sizes. The method is compared to two other clustering techniques, fuzzy C means (FCM) and K-means algorithm. Experimental results show the robustness and effectiveness of the proposed algorithm.

Keywords

Main Subjects

modelling & simulation

References

Alvarenga. G.B., Mateus. G.R, de Tomi. G. (2007). “A Genetic and Set Partitioning Two-phase Approach for the Vehicle Routing Problem with Time Windows”.Computers & Operations Research, Vol. 34, pp. 1561– 1584.

Banos.R, Ortega, Consolacion. G, Fernandez.A, de Toro.F. (2013). “A Simulated Annealing-based Parallel Multi- Objective Approach to Vehicle Routing Problems with Time Windows”, Expert Systems with Applications, Vol. 40,pp. 1696–1707.

Cordeau J-F, Gendreau M, Laporte G. (1997). “A Tabu Search Heuristic for Periodic and Modeling and Solving the Multi-depot Vehicle Routing Problem with Multi-Depot Vehicl Routing Problems”. Networks Vol.30, pp. pp 105–19.

Cordeau J-F,Maischberger. M, (2010) “A parallel iterated tabu search heuristic for vehicle routing problems”. Computers & Operational Research Vol.39, pp. 2033-2050.

Crevier B, Cordeau J, Laporte G. (2007). “The Multi-Depot Vehicle Routing Problem With Inter-depot Routes”. European Journal of Operational Research, Vol.176, pp. 756–73.

Dondo R, Cerda J. (2007). “A Cluster-based Optimization Approach for the Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows”, European Journal of Operational Research, Vol.176, pp, 1478– 1507.

Dondo R, Cerda J. (2009). “A Hybrid Local Improvement Algorithm for Large Scale Multi-Depot Vehicle Routing Problems with Time Windows”, Computers and Chemical Engineering, Vol33, pp. 513–530.

Eidi, A.R. AbdulRahimi, H. (2012). “Proposition and Solution of the Multi-periodic and Multi-depot Routing Problem Model with Flexibility in Determining the finished depot of each route”, International Journal of production management and Industries Engineering Vol, 23. No.3. pp, 334-349.

Holland, J. (1975). “Adaptation in natural and artificial systems”, Ann Arbor: The University of Michigan Press.

Ho W, Ho TS, Ji P, Lau CW. (2008). “A Hybrid Genetic Algorithm for The Multi-Depot Vehicle Routing Problem”. Engineering Applications of Artificial Intelligence, Vol. 21, pp. 548–557.

Hosseininezhad.F, Salajegheh.A. (2012). “Study and Comparison of Partitioning Clustering Algorithms”, Iranian Journal of Medical Informatics, Vol 2, No. 1.

Kek, A.G.H., Cheu, R.L., Meng, Q. (2008). “Distance- Constrained Capacitated Vehicle Routing Problems with flexible Assignment of Start and End Depots”, Mathematical and Computer Modeling, Vol. 47, No 1-2, pp. 140- 152.

Kallehauge.B. (2008). “Formulations and Exact Algorithms For the Vehicle Routing Problem With Time Windows”, Computers & Operations Research, Vol. 35, pp. 2307 – 2330.

Kritikos, M.N., Ioannou, G. (2010). “The balanced cargo vehicle routing problem with time windows, International Journal of Production Economics, Vol. 123(1), pp. 42-51.

Maulik .U, Bandyopadhya. S. (2000). “Genetic algorithm-based clustering technique”, Pattern Recognition, Vol. 33, pp. 1455-1465.

Mirabi, Shokri and Sadeghieh Mirabi. M, Ghomi. S. M. T. F, and Jolai. F. (2010). “Efficient Stochastic Hybrid Heuristics for the Multi-Depot Vehicle Routing Problem,” Robotics and computer integrated manufacturing, Vol. 26, pp. 564-569.

Ombuki.B, Ross.B.J and Hanshar.F. (2006). “Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows”, Applied Intelligence, Vol. 24,pp. 17–30.

Renaud J, Laporte G, Boctor FF. (1996). “A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem”.Computers & Operations Research; Vol. 23, pp. 229–35.

Salhi, S., Sari, M. (1997). “A Multi-level Composite Heuristic for the Multi-depot Vehicle Fleet Mix Problem”. European Journal of Operational Research, Vol. 103, pp. 95–112.

Sivanandam.S.N.,.Deepa. S.N. (2008). “Introduction to Genetic Algorithms”, Springer-Verlag Berlin Heidelberg; Springer Berlin Heidelberg New York; chapter 2; ISBN 978-3-540- 73189-4; pp. 31-53.

Sumaiya Iqbal, Kaykobad.M, Sohel Rahman. M. 2015.”Solving the Multi-Object Vehicle Routing Problem with Soft Time Window with the help of bees”.Swarm and Evolutionary Computation, Vol. 24, pp. 50-64.

Thangiah. S.R. (1999). “A Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Heuristic for Vehicle Routing Problems With Time Windows”, in: L. Chambers (Ed.), Practical Handbook of Genetic Algorithms Complex Structures, Vol. 3, CRC Press, pp. 347–381.

Tan K.C, Lee. L.H, Zhu K.Q, Qu. K. (2001). “Heuristic Methods for Vehicle Routing Problem with Time Windows”, Artificial Intelligence in Engineering 15, 281– 295.

Toth, P., and Vigo, D. (2002). “The vehicle routing problem”, Society for Industrial and Applied Mathematics”, Philadelphia, PA.

Xu .Y, Wang.L, Yang.Y. (2012). “A New Variable Neighborhood Search Algorithm For the Multi-Depot Heterogeneous Vehicle Routing Problem With Time Windows”, Electronic Notes in Discrete Mathematics, Vol. 39, pp, 289-296.

Yu.B, Yang.Z.Z. (2011). “An Ant Colony Optimization Model: The Period Vehicle Routing Problem With Time Windows”, Transportation Research Part E, Vol.47,pp. 166–181. http://www.bernabe.dorronsoro.es/vrp/