Two-step Meta-heuristic Approach for a Vehicle Assignment Problem – Case from İstanbul/Turkey

  • G. Nilay Yücenur Beykent University
Keywords: vehicle assignment problem, geometric shape-based clustering, genetic algorithm, crossover rate, the k-Nearest Neighbour algorithm

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.

Author Biography

G. Nilay Yücenur, Beykent University

Industrial Engineering Department

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

Published
2020-02-06
How to Cite
1.
Yücenur GN. Two-step Meta-heuristic Approach for a Vehicle Assignment Problem – Case from İstanbul/Turkey. PROMET [Internet]. 2020Feb.6 [cited 2020Sep.19];32(1):79-0. Available from: https://traffic.fpz.hr/index.php/PROMTT/article/view/3156
Section
Articles