Let's Connect
Follow Us
Watch Us
(+385) 1 2380 262
journal.prometfpz.unizg.hr
Promet - Traffic&Transportation journal

Accelerating Discoveries in Traffic Science

Accelerating Discoveries in Traffic Science

PUBLISHED
06.02.2020
LICENSE
Copyright (c) 2024 G. Nilay Yücenur

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

Authors:G. Nilay Yücenur

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.

Keywords:vehicle assignment problem, geometric shape-based clustering, genetic algorithm, crossover rate, the k-Nearest Neighbour algorithm

References

  1. 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

Show more


Accelerating Discoveries in Traffic Science |
2024 © Promet - Traffic&Transportation journal