Systematic Literature Review Of Particle Swarm Optimization Implementation For Time-Dependent Vehicle Routing Problem

Authors

  • M. Diah Magister Teknik Informatika Universitas AMIKOM, Yogyakarta, Indonesia
  • Arief Setyanto Magister Teknik Informatika Universitas AMIKOM, Yogyakarta, Indonesia
  • Emha Taufiq Luthfi Magister Teknik Informatika Universitas AMIKOM, Yogyakarta, Indonesia

DOI:

https://doi.org/10.15575/join.v7i1.804

Keywords:

Time-Dependent VRP, Particle Swarm Optimization, Optimum Route Criteria, Dynamic VRP, Systematic Literature Review

Abstract

Time-dependent VRP (TDVRP) is one of the three VRP variants that have not been widely explored in research in the field of operational research, while Particle Swarm Optimization (PSO) is an optimization algorithm in the field of operational research that uses many variables in its application. There is much research conducted about TDVRP, but few of them discuss PSO's implementation. This article presented as a literature review which aimed to find a research gap about implementation of PSO to resolve TDVRP cases. The research was conducted in five stages. The first stage, a review protocol defined in the form of research questions and methods to perform the review. The second stage is references searching. The third stage is screening the search result. The fourth stage is extracting data from references based on research questions. The fifth stage is reporting the study literature results. The results obtained from the screening process were 37 eligible reference articles, from 172 search results articles. The results of extraction and analysis of 37 reference articles show that research on TDVRP discusses the duration of travel time between 2 locations. The route optimization parameter is determined from the cost of the trip, including the total distance traveled, the total travel time, the number of routes, and the number used vehicles. The datasets that are used in research consist of 2 types, real-world datasets and simulation datasets. Solomon Benchmark is a simulation dataset that is widely used in the case of TDVRP. Research on PSO in the TDVRP case is dominated by the discussion of modifications to determine random values of PSO variables.

References

K. Braekers, K. Ramaekers, and I. Van Nieuwenhuyse, “The vehicle routing problem: State of the art classification and review,†Comput. Ind. Eng., vol. 99, no. September 2018, pp. 300–313, 2016, doi: 10.1016/j.cie.2015.12.007.

S. N. Kumar and R. Panneerselvam, “A Survey on the Vehicle Routing Problem and Its Variants,†Intell. Inf. Manag., vol. 04, no. 03, pp. 66–74, 2012, doi: 10.4236/iim.2012.43010.

Y. Marinakis, M. Marinaki, and A. Migdalas, “A Multi-Adaptive Particle Swarm Optimization for the Vehicle Routing Problem with Time Windows,†Inf. Sci. (Ny)., vol. 481, pp. 311–329, 2019, doi: 10.1016/j.ins.2018.12.086.

S. N. Kumar and R. Panneerselvam, “A Time-Dependent Vehicle Routing Problem with Time Windows for E-Commerce Supplier Site Pickups Using Genetic Algorithm,†Intell. Inf. Manag., vol. 07, no. 04, pp. 181–194, 2015, doi: 10.4236/iim.2015.7474015.

M. Gmira, M. Gendreau, A. Lodi, and J. Y. Potvin, “Tabu search for the time-dependent vehicle routing problem with time windows on a road network,†Eur. J. Oper. Res., vol. 288, no. 1, pp. 129–140, 2021, doi: 10.1016/j.ejor.2020.05.041.

F. Marini and B. Walczak, “Particle swarm optimization (PSO). A tutorial,†Chemom. Intell. Lab. Syst., vol. 149, pp. 153–165, 2015, doi: 10.1016/j.chemolab.2015.08.020.

H. Shen, Y. Zhu, T. Liu, and L. Jin, “Particle swarm optimization in solving Vehicle Routing Problem,†2009 2nd Int. Conf. Intell. Comput. Technol. Autom. ICICTA 2009, vol. 1, no. 4, pp. 287–291, 2009, doi: 10.1109/ICICTA.2009.77.

A. N. Atiqoh, “Analisis Inertia Weight pada Algoritma Particle Swarm Optimization (PSO) Untuk Optimalisasi dan Pemodelan Sistem Terhadap Persoalan Vehicle Routing Problem With Time Window (VRPTW),†Universitas Islam Negeri Sunan Ampel, 2020.

S. R. Balseiro, I. Loiseau, and J. Ramonet, “An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows,†Comput. Oper. Res., vol. 38, no. 6, pp. 954–966, 2011, doi: 10.1016/j.cor.2010.10.011.

E. Chukwu and L. Garg, “A systematic review of blockchain in healthcare: Frameworks, prototypes, and implementations,†IEEE Access, vol. 8, pp. 21196–21214, 2020, doi: 10.1109/ACCESS.2020.2969881.

B. Kitchenham, “Procedures for Performing Systematic Reviews,†Keele, 2004. doi: 10.1145/3328905.3332505.

B. Kitchenham, O. Pearl Brereton, D. Budgen, M. Turner, J. Bailey, and S. Linkman, “Systematic literature reviews in software engineering - A systematic literature review,†Inf. Softw. Technol., vol. 51, no. 1, pp. 7–15, 2009, doi: 10.1016/j.infsof.2008.09.009.

M. A. Lawal, A. B. M. Sultan, and A. O. Shakiru, “Systematic literature review on SQL injection attack,†Int. J. Soft Comput., vol. 11, no. 1, pp. 26–35, 2016.

W. Mengist, T. Soromessa, and G. Legese, “Method for conducting systematic literature review and meta-analysis for environmental science research,†MethodsX, vol. 7, p. 100777, 2020, doi: 10.1016/j.mex.2019.100777.

U. Yudatama, B. A. A. Nazief, and A. N. Hidayanto, “Benefits and barriers as a critical success factor in the implementation of IT governance: Literature review,†2017 Int. Conf. ICT Smart Soc. ICISS 2017, vol. 2018-Janua, pp. 1–6, 2018, doi: 10.1109/ICTSS.2017.8288869.

C. Liu et al., “A combined order selection and time-dependent vehicle routing problem with time widows for perishable product delivery,†Eur. J. Oper. Res., vol. 48, no. 3, pp. 297–305, 2020, doi: 10.1016/j.measurement.2016.04.043.

Y. Huang, L. Zhao, T. Van Woensel, and J. P. Gross, “Time-dependent vehicle routing problem with path flexibility,†Transp. Res. Part B Methodol., vol. 95, pp. 169–195, 2017, doi: 10.1016/j.trb.2016.10.013.

A. L. Kok, E. W. Hans, J. M. J. Schutten, and W. H. M. Zijm, “A dynamic programming heuristic for vehicle routing with time-dependent travel times and required breaks,†Flex. Serv. Manuf. J., vol. 22, no. 1–2, pp. 83–108, 2010, doi: 10.1007/s10696-011-9077-4.

C. Malandraki and M. S. Daskin, “Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms,†Transp. Sci., vol. 26, no. 3, pp. 185–200, 1992, doi: 10.1287/trsc.26.3.185.

T. Zhang, W. A. Chaovalitwongse, and Y. Zhang, “Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery,†J. Comb. Optim., vol. 28, no. 1, pp. 288–309, 2014, doi: 10.1007/s10878-014-9741-1.

N. Rincon-Garcia, B. Waterson, T. J. Cherrett, and F. Salazar-Arrieta, “A metaheuristic for the time-dependent vehicle routing problem considering driving hours regulations – An application in city logistics,†Transp. Res. Part A Policy Pract., vol. 137, no. xxxx, pp. 429–446, 2020, doi: 10.1016/j.tra.2018.10.033.

M. Soysal and M. Çimen, “A Simulation Based Restricted Dynamic Programming approach for the Green Time Dependent Vehicle Routing Problem,†Comput. Oper. Res., vol. 88, pp. 297–305, 2017, doi: 10.1016/j.cor.2017.06.023.

D. Taş, N. Dellaert, T. van Woensel, and T. de Kok, “The time-dependent vehicle routing problem with soft time windows and stochastic travel times,†Transp. Res. Part C Emerg. Technol., vol. 48, pp. 66–83, 2014, doi: 10.1016/j.trc.2014.08.007.

M. Setak, M. Habibi, H. Karimi, and M. Abedzadeh, “A time-dependent vehicle routing problem in multigraph with FIFO property,†J. Manuf. Syst., vol. 35, pp. 37–45, 2015, doi: 10.1016/j.jmsy.2014.11.016.

M. Andres Figliozzi, “The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics,†Transp. Res. Part E Logist. Transp. Rev., vol. 48, no. 3, pp. 616–636, 2012, doi: 10.1016/j.tre.2011.11.006.

B. Pan, Z. Zhang, and A. Lim, “Multi-trip time-dependent vehicle routing problem with time windows,†Eur. J. Oper. Res., vol. 291, no. 1, pp. 218–231, 2021, doi: 10.1016/j.ejor.2020.09.022.

N. Norouzi, M. Sadegh-Amalnick, and R. Tavakkoli-Moghaddam, “Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption,†Optim. Lett., vol. 11, no. 1, pp. 121–134, 2017, doi: 10.1007/s11590-015-0996-y.

M. Flamini, M. Nigro, and D. Pacciarelli, “Assessing the value of information for retail distribution of perishable goods,†Eur. Transp. Res. Rev., vol. 3, no. 2, pp. 103–112, 2011, doi: 10.1007/s12544-011-0051-8.

D. Escuín, C. Millán, and E. Larrodé, “Modelization of Time-Dependent Urban Freight Problems by Using a Multiple Number of Distribution Centers,†Networks Spat. Econ., vol. 12, no. 3, pp. 321–336, 2012, doi: 10.1007/s11067-009-9099-6.

D. W. Cho, Y. H. Lee, T. Y. Lee, and M. Gen, “An adaptive genetic algorithm for the time dependent inventory routing problem,†J. Intell. Manuf., vol. 25, no. 5, pp. 1025–1042, 2014, doi: 10.1007/s10845-012-0727-5.

Z. J. Ma, Y. Wu, and Y. Dai, “A combined order selection and time-dependent vehicle routing problem with time widows for perishable product delivery,†Comput. Ind. Eng., vol. 114, pp. 101–113, 2017, doi: 10.1016/j.cie.2017.10.010.

Y. Marinakis and M. Marinaki, “A hybrid genetic - Particle Swarm Optimization Algorithm for the vehicle routing problem,†Expert Syst. Appl., vol. 37, no. 2, pp. 1446–1455, 2010, doi: 10.1016/j.eswa.2009.06.085.

F. P. Goksal, I. Karaoglan, and F. Altiparmak, “A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery,†Comput. Ind. Eng., vol. 65, no. 1, pp. 39–53, 2013, doi: 10.1016/j.cie.2012.01.005.

J. Kennedy and R. Eberhart, “Particle swarm optimization,†IEEE Int. Conf. Neural Networks, vol. 4, pp. 1942–1948, 1995.

Y. Marinakis, M. Marinaki, and G. Dounias, “A hybrid particle swarm optimization algorithm for the vehicle routing problem,†Eng. Appl. Artif. Intell., vol. 23, no. 4, pp. 463–472, 2010, doi: 10.1016/j.engappai.2010.02.002.

T. J. Ai and V. Kachitvichyanukul, “Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem,†Comput. Ind. Eng., vol. 56, no. 1, pp. 380–387, 2009, doi: 10.1016/j.cie.2008.06.012.

N. Norouzi, M. Sadegh-Amalnick, and M. Alinaghiyan, “Evaluating of the particle swarm optimization in a periodic vehicle routing problem,†Meas. J. Int. Meas. Confed., vol. 62, pp. 162–169, 2015, doi: 10.1016/j.measurement.2014.10.024.

R. J. Kuo, F. E. Zulvia, and K. Suryadi, “Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand - A case study on garbage collection system,†Appl. Math. Comput., vol. 219, no. 5, pp. 2574–2588, 2012, doi: 10.1016/j.amc.2012.08.092.

K. D. Rest and P. Hirsch, “Daily scheduling of home health care services using time-dependent public transport,†Flex. Serv. Manuf. J., vol. 28, no. 3, pp. 495–525, 2016, doi: 10.1007/s10696-015-9227-1.

Y. Marinakis, G. R. Iordanidou, and M. Marinaki, “Particle Swarm Optimization for the vehicle routing problem with stochastic demands,†Appl. Soft Comput. J., vol. 13, no. 4, pp. 1693–1704, 2013, doi: 10.1016/j.asoc.2013.01.007.

Z. Yanwei, W. Bin, W. Wanliang, and Z. Jingling, “Particle Swarm Optimization for Open Vehicle Routing Problem with Time Dependent Travel Time,†IFAC Proc. Vol., vol. 41, no. 2, pp. 12843–12848, 2008, doi: 10.3182/20080706-5-kr-1001.02172.

S. A. Mirhassani and N. Abolghasemi, “A particle swarm optimization algorithm for open vehicle routing problem,†Expert Syst. Appl., vol. 38, no. 9, pp. 11547–11551, 2011, doi: 10.1016/j.eswa.2011.03.032.

D. Sedighizadeh and H. Mazaheripour, “Optimization of multi objective vehicle routing problem using a new hybrid algorithm based on particle swarm optimization and artificial bee colony algorithm considering Precedence constraints,†Alexandria Eng. J., vol. 57, no. 4, pp. 2225–2239, 2018, doi: 10.1016/j.aej.2017.09.006.

J. Chen and J. Shi, “A multi-compartment vehicle routing problem with time windows for urban distribution – A comparison study on particle swarm optimization algorithms,†Comput. Ind. Eng., vol. 133, no. May, pp. 95–106, 2019, doi: 10.1016/j.cie.2019.05.008.

R. M. Chen, Y. M. Shen, and W. Z. Hong, “Neural-like encoding particle swarm optimization for periodic vehicle routing problems,†Expert Syst. Appl., vol. 138, p. 112833, 2019, doi: 10.1016/j.eswa.2019.112833.

M. Alinaghian, M. Ghazanfari, N. Norouzi, and H. Nouralizadeh, “A Novel Model for the Time Dependent Competitive Vehicle Routing Problem: Modified Random Topology Particle Swarm Optimization,†Networks Spat. Econ., vol. 17, no. 4, pp. 1185–1211, 2017, doi: 10.1007/s11067-017-9364-z.

Downloads

Published

2022-06-30

Issue

Vol. 7 No. 1 (2022)

Section

Article

Citation Check

License

You are free to:

 

Under the following terms:

  • Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.

  • NoDerivatives — If you remix, transform, or build upon the material, you may not distribute the modified material.

  • No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

 

Notices:

  • You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation.
  • No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License