Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T22:04:09.420Z Has data issue: false hasContentIssue false
  • English
  • Français

A novel hybrid genetic algorithm for the multidepot periodic vehicle routing problem

Published online by Cambridge University Press:  14 July 2014

Mohammad Mirabi
Mohammad Mirabi*
Affiliation:
Department of Industrial Engineering, Ayatollah Haeri University of Meybod, Meybod, Iran
*
Reprint requests to: Mohammad Mirabi, Department of Industrial Engineering, Ayatollah Haeri University of Meybod, Meybod, P.O. Box 89619-55133, Iran. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A genetic algorithm is a metaheuristic proposed to derive approximate solutions for computationally hard problems. In the literature, several successful applications have been reported for graph-based optimization problems, such as scheduling problems. This paper provides one definition of periodic vehicle routing problem for single and multidepots conforming to a wide range of real-world problems and also develops a novel hybrid genetic algorithm to solve it. The proposed hybrid genetic algorithm applies a modified approach to generate a population of initial chromosomes and also uses an improved heuristic called the iterated swap procedure to improve the initial solutions. Moreover, during the implementation a hybrid algorithm, cyclic transfers, an effective class of neighborhood search is applied. The author uses three genetic operators to produce good new offspring. The objective function consists of two terms: total traveled distance at each depot and total waiting time of all customers to take service. Distances are assumed Euclidean or straight line. These conditions are exactly consistent with the real-world situations and have received little attention in the literature. Finally, the experimental results have revealed that the proposed hybrid method can be competitive with the best existing methods as asynchronous parallel heuristic and variable neighborhood search in terms of solution quality to solve the vehicle routing problem.

Keywords

Genetic AlgorithmIterated Swap ProcedureMultidepotPeriodic Vehicle Routing Problem
Type
Regular Articles
Information
AI EDAM , Volume 29 , Issue 1 , February 2015 , pp. 45 - 54
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Alegre, J., Laguna, M., & Pacheco, J. (2007). Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts. European Journal of Operation Research 179(3), 736–746.Google Scholar
Baldacci, R., Bartolini, E., & Mingozzi, A. (2011). An exact algorithm for the periodic routing problem. Operations Research 59, 228–241.CrossRefGoogle Scholar
Baldacci, R., & Mingozzi, A. (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming A 120(2), 347–380.Google Scholar
Chao, I., Golden, B.L., & Wasil, E. (2007). A new heuristic for the multi-depot vehicle routing problem that improves upon best known solutions. American Journal of Mathematical and Management Sciences 13(3–4), 371–406.CrossRefGoogle Scholar
Clarke, G., & Wright, J.W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research 12, 568–581.Google Scholar
Cordeau, J.F., Gendreau, M., & Laporte, G. (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30(2), 105–119.Google Scholar
Cordeao, J.F., Laporte, G., & Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society 52(8), 928–936.CrossRefGoogle Scholar
Crainic, T.G., Crisan, G.C., Gendreau, M., Lahrichi, N., & Rei, W. (2009). Multi thread cooperative optimization for rich combinatorial problems. Proc. 23rd IEEE Int. Parallel and Distributed Processing Symposium, IDPPS, Rome, May 23–29.CrossRefGoogle Scholar
Crevier, B., Cordeau, J., & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operation Research 176(2), 756–773.Google Scholar
Dantzig, G.B., & Ramser, J.H. (1959). The truck dispatching problem. Management Science 6(1), 80–91. doi:10.1287/mnsc.6.1.80Google Scholar
Drummond, L.M.A., Ochi, L.S., & Vianna, D.S. (2001). An asynchronous parallel metaheuristics for the period routing problem. Future Generation Computer Systems 17(4), 379–386.CrossRefGoogle Scholar
Gen, M., & Cheng, R. (1997). Genetic Algorithms and Engineering Design. New York: Wiley.Google Scholar
Giosa, I.D., Tansini, I.L., & Viera, I.O. (2002). New assignment algorithms for the multi-depot vehicle routing problem. Journal of the Operational Research Society 53(9), 977–984.Google Scholar
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. New York: Addison–Wesley.Google Scholar
Hemmelmayr, V.C., Doerner, K.F., & Hartl, R.F. (2009). A variable neighborhood search heuristic for periodic routing problems. European Journal of Operation Research 195(3), 791–802.Google Scholar
Ho, W., Ho, T.S., Ji, P., & Lau, C.W. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence 21(4), 548–557.Google Scholar
Ho, W., & Ji, P. (2003). Component scheduling for chip shooter machines: a hybrid genetic algorithm approach. Computers & Operations Research 30(14), 2175–2189.Google Scholar
Ho, W., & Ji, P. (2004). A hybrid genetic algorithm for component sequencing and feeder arrangement. Journal of Intelligent Manufacturing 15(3), 307–315.Google Scholar
Lim, A., & Zhu, W. (2006). A fast and effective insertion algorithm for MDVRP with fixed distribution of vehicles and a new simulated annealing approach. Proc. 19th Int. Conf. Industrial, Engineering & Other Applications of Applied Intelligent Systems (IEA/AIE'06), LNAI, Vol. 4031, pp. 282–291. Berlin: Springer–Verlag.Google Scholar
Matos, C., & Oliveira, R.C. (2004). An experimental study of the ant colony system for the period vehicle routing problem. In Ant Colony, Optimization and Swarm Intelligence, LNCS, Vol. 3172, pp. 1–29. Heidelberg: Springer.Google Scholar
Mirabi, M., Fatemi, S.M.T., & Jolai, F. (2014). A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problem. Journal of Industrial Engineering International 10(57), 1–9. doi:10.1007/s40092-014-0057-7Google Scholar
Parthanadee, P., & Logendran, R. (2006). Periodic product distribution from multi depot under limited supplies. IIE Transactions 38(11), 1009–1026.Google Scholar
Pirkwieser, S., & Raidl, G.R. (2010). Multilevel variable neighborhood search for periodic routing problems. Proc. Evolutionary Computation in Combinatorial Optimization: 10th European Conf., COP 2010 (Cowling, P., & Merz, P., Eds.), pp. 226–238. Berlin: Springer–Verlag.Google Scholar
Pisinger, D., & Ropke, S. (2007). A general heuristic for the vehicle routing problems. Computers & Operations Research 34(8), 2403–2435.Google Scholar
Renaud, J., Laporte, G., & Boctor, F.F. (1996). A tabu search heuristic for the multi-depot vehicle routing problem. Computers & Operations Research 23(3), 229–235.Google Scholar
Thangiah, S., & Salhi, S. (2001). Genetic clustering: an adaptive heuristic for the multi depot vehicle routing problem. Applied Artificial Intelligence 15(4), 361–383.CrossRefGoogle Scholar
Vidal, T., Crainic, T.G., Gendreau, M., Lahrichi, N., & Rei, W. (2012). A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems. Operations Research 60(3), 611–624.Google Scholar