Two-step Meta-heuristic Approach for a Vehicle Assignment Problem – Case from İstanbul/Turkey
Abstract
In this paper, a two-step meta-heuristic approach is proposed for vehicle assignment problem with geometric shape-based clustering and genetic algorithm. First, the geometric shape-based clustering method is used and then the solution of this method is given to the genetic algorithm as initial solution. The solution process is continued by genetic algorithm. There are 282 bus lines in İstanbul European side. Those buses should be assigned to six bus garages. The proposed method is used to determine the minimum distance between the bus lines and garages by assigning buses to garages. According to the computational results, the proposed algorithm has better clustering performance in terms of the distance from each bus-line start point to each bus garage in the cluster. The crossover rate changing method is also applied as a trial in order to improve the algorithm performance. Finally, the outputs that are generated by different crossover rates are compared with the results of the k-Nearest Neighbour algorithm to prove the effectiveness of the study.
References
Verbas Ö, Mahmassani HS, Hyland MF. Gap-based transit assignment algorithm with vehicle capacity constraints: Simulation-based implementation and large-scale application. Transportation Research Part B. 2016;93: 1-16. Available from: doi:10.1016/j.trb.2016.07.002
Vidal T, Crainic TG, Gendreau M, Prins C. Implicit depot assignments and rotations in vehicle routing heuristics. European Journal of Operational Research. 2014;237: 15-28. Available from: doi:10.1016/j.ejor.2013.12.044
Zhao Y, Leng L, Qian Z, Wang W. A Discrete hybrid invasive weed optimization algorithm for the capacitated vehicle routing problem. Procedia Computer Science. 2016;91: 978-987. Available from: doi:10.1016/j.procs.2016.07.127
Tlili T, Faiz S, Krichen S. A Hybrid metaheuristic for the distance-constrained capacitated vehicle routing problem. Procedia – Social and Behavioral Sciences. 2014;109: 779-783. Available from: doi:10.1016/j.sbspro.2013.12.543
Yassen ET, Ayob M, Nazri MZA, Sabar NR. An adaptive hybrid algorithm for vehicle routing problems with time windows. Computers & Industrial Engineering. 2017;113: 382-391. Available from: doi:10.1016/j.cie.2017.09.034
Damleijer K, Spliet R. A branch-and-cut algorithm for Computers & Operations Research. 2018;89: 140-152. Available from: doi:10.1016/j.cor.2017.08.015
Oliveira FB, Enayatifar R, Sadaei HJ, Guimaraes FG, Potvin JY. A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem. Expert Systems with Applications. 2016;43: 117-130. Available from: doi:10.1016/j.eswa.2015.08.030
Du J, Li X, Yu L, Dan R, Zhou J. Multi-depot vehicle routing problem for hazardous materials transportation: A fuzzy bilevel programming. Information Sciences. 2017;399: 201-218. Available from: doi:10.1016/j.ins.2017.02.011
Zachariadis EE, Tarantilis CD, Kiranoudis CT. The vehicle routing problem with simultaneous pick-ups and deliveries and two-dimensional loading constraints. European Journal of Operational Research. 2016;251(2): 369-386. Available from: doi:10.1016/j.ejor.2015.11.018
Kartal Z, Hasgul S, Ernst AT. Single allocation p-hub median location and routing problem with simultaneous pick-up and delivery. Transportation Research Part E: Logistics and Transportation Review. 2017;108: 141-159. Available from: doi:10.1016/j.tre.2017.10.004
Norouzi N, Amalnick MS, Alinaghiyan M. Evaluating of the particle swarm optimization in a periodic vehicle routing problem. Measurement. 2015;62: 162-169. Available from: doi:10.1016/j.measurement.2014.10.024
Shahparvari S, Abbasi B. Robust stochastic vehicle routing and scheduling for bushfire emergency evacuation: An Australian case study. Transportation Research Part A: Policy and Practice. 2017;104: 32-49. Available from: doi:10.1016/j.tra.2017.04.036
Huang Y, Zhao L, Woensel TV, Gross JP. Time-dependent vehicle routing problem with path flexibility. Transportation Research Part B: Methodological. 2017;95: 169-195. Available from: doi:10.1016/j.trb.2016.10.013
Aringhieri R, Bruglieri M, Malucelli F, Nonato M. An asymmetric vehicle routing problem arising in the collection and disposal of special waste. Electronic Notes in Discrete Mathematics. 2004;17: 41-47. Available from: doi:10.1016/j.endm.2004.03.011
Liu R, Jiang Z. The close–open mixed vehicle routing problem. European Journal of Operational Research. 2012;220(2): 349-360. Available from: doi:10.1016/j.ejor.2012.01.061
Yu VF, Jewpanya P, Redi AANP. Open vehicle routing problem with cross-docking. Computers & Industrial Engineering. 2016;94: 6-17. Available from: doi:10.1016/j.cie.2016.01.018
Atefi R, Salari M, Coelho LC, Renaud J. The open vehicle routing problem with decoupling points. European Journal of Operational Research. 2018;265(1): 316-327. Available from: doi:10.1016/j.ejor.2017.07.033
Okulewicz M, Mandziuk J. The impact of particular components of the PSO-based algorithm solving the dynamic vehicle routing problem. Applied Soft Computing. 2017;58: 586-604. Available from: doi:10.1016/j.asoc.2017.04.070
Abdallah AMFM, Essam DL, Sarker RA. On solving periodic re-optimization dynamic vehicle routing problems. Applied Soft Computing. 2017;55: 1-12. Available from: doi:10.1016/j.asoc.2017.01.047
Lin CKY. A vehicle routing problem with pickup and delivery time windows, and coordination of transportable resources. Computers & Operations Research. 2011;38(11): 1596-1609. Available from: doi:10.1016/j.cor.2011.01.021
Afshar-Nadjafi B, Afshar-Nadjafi A. A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet. Journal of King Saud University – Engineering Sciences. 2017;29(1): 29-34. Available from: doi:10.1016/j.jksues.2014.04.007
Zhou, L, Baldacci R, Vigo D, Wang X. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution. European Journal of Operational Research. 2018;265(2): 765-778. Available from: doi:10.1016/j.ejor.2017.08.011
Kulkami RV, Bhave PR. Integer programming formulations of vehicle routing problems. European Journal of Operational Research. 1985;20(1): 58-67. Available from: doi:10.1016/0377-2217(85)90284-X
Park YB, Koelling CP. A solution of vehicle routing problems in a multiple objective environment. Engineering Costs and Production Economics. 1986;10(2): 121-132. Available from: doi:10.1016/0167-188X(86)90006-6
Radharamanan R, Choi LI. A branch and bound algorithm for the travelling salesman and the transportation routing problems. Computers & Industrial Engineering. 1986;11(1-4): 236-240. Available from: doi:10.1016/0360-8352(86)90085-9
Laporte G, Nobert Y, Taillefer S. A branch-and-bound algorithm for the asymmetrical distance-constrained vehicle routing problem. Mathematical Modelling. 1987;9(12): 857-868. Available from: doi:10.1016/0270-0255(87)90004-2
Brodei GR, Waters CDJ. Integer linear programming formulation for vehicle routing problems. European Journal of Operational Research. 1988;34(3): 403-404. Available from: doi:10.1016/0377-2217(88)90162-2
Anbuudayasankar SP, Ganesh K, Koh SCL, Ducq Y. Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls. Expert Systems with Applications. 2012;39(3): 2296-2305. Available from: doi:10.1016/j.eswa.2011.08.009
Yusoff M, Ariffin J, Mohamed A. DPSO based on a min-max approach and clamping strategy for the evacuation vehicle assignment problem. Neurocomputing. 2015;148: 30-38. Available from: doi:10.1016/j.neucom.2012.12.083
Jabir E, Panicker VV, Sridharan R. Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem. Transportation Research Part D: Transport and Environment. 2017;57: 422-457. Available from: doi:10.1016/j.trd.2017.09.003
Wang J, Jagannathan AKR, Zuo X, Murray CC. Two-layer simulated annealing and tabu search heuristics for a vehicle routing problem with cross docks and split deliveries. Computers & Industrial Engineering. 2017;112: 84-98. Available from: doi:10.1016/j.cie.2017.07.031
Ng KKH, Lee CKM, Zhang SZ, Wu K, Ho W. A multiple colonies artificial bee colony algorithm for a capacitated vehicle routing problem and re-routing strategies under time-dependent traffic congestion. Computers & Industrial Engineering. 2017;109: 151-168. Available from: doi:10.1016/j.cie.2017.05.004
Kowalski RJ, Li C, Ganjyal GM. Optimizing twin-screw food extrusion processing through regression modeling and genetic algorithms. Journal of Food Engineering. 2018;234: 50-56. Available from: doi:10.1016/j.jfoodeng.2018.04.004
Arthur J, Bahran R, Hutchinson J, Pozzi SA. Genetic algorithm for nuclear data evaluation applied to subcritical neutron multiplication inference benchmark experiments. Annals of Nuclear Energy. 2019; 133: 853–862. Available from: doi:10.1016/j.anucene.2019.07.024
Abreu LR, Cunha JO, Prata BA, Framinan JM. A genetic algorithm for scheduling open shops with sequence-dependent setup times. Computers & Operations Research. 2020;113: 104793. Available from: doi:10.1016/j.cor.2019.104793
Meesrikamolkul W, Niennattrakul V, Ratanamahatana CA. Shape-Based Clustering for Time Series Data. Advances in Knowledge Discovery and Data Mining: Proceedings of the 16th Pacific-Asia Conference, PAKDD, Part I, Kuala Lumpur/Malaysia; 2012. p. 530-541. Available from: doi:10.1007/978-3-642-30217-6_44
Xu S, Zou S, Wang L. A Geometric Clustering Algorithm with Applications to Structural Data. Journal of Computational Biology. 2015;22(5): 436-450. Part I, 10.1089/cmb.2014.0162
Tharwat A, Hahdi H, Elhoseny M, Hassanien AE. Recognizing human activity in mobile crowdsensing environment using optimized k-NN algorithm. Expert Systems with Applications. 2018;107: 32-44. Available from: doi:10.1016/j.eswa.2018.04.017
Huan Y, Wei T, Wang Z, Lei C, Chen F, Wang X. Polarization switching and rotation in KNN-based lead-free piezoelectric ceramics near the polymorphic phase boundary. Journal of the European Ceramic Society. 2019;39(4): 1002-1010. Available from: doi:10.1016/j.jeurceramsoc.2018.11.001
Bania RK, Halder A. R-Ensembler: A greedy rough set based ensemble attribute selection algorithm with kNN imputation for classification of medical data. Computer Methods and Programs in Biomedicine. 2020;184: 105122. Available from: doi:10.1016/j.cmpb.2019.105122
Thangiah SR, Salhi S. Genetic clustering: An adaptive heuristic for the multi-depot vehicle routing problem. Applied Artificial Intelligence. 2001;15:361-383. Available from: doi:10.1080/08839510151087293
Copyright (c) 2020 G. Nilay Yücenur
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
