Implementation of discrete particle swarm optimization algorithm in the capacitated vehicle routing problem

Authors

  • Aisyahna Nurul Mauliddina Department of Logistics Engineering, Pertamina University
  • Faris Ahmad Saifuddin Department of Logistics Engineering, Pertamina University
  • Adesatya Lentera Nagari Department of Logistics Engineering, Pertamina University
  • Anak Agung Ngurah Perwira Redi Department of Industrial Engineering-Binus Graduate Program, Binus University
  • Adji Candra Kurniawan Department of Logistics Engineering, Pertamina University
  • Nanda Ruswandi Department of Logistics Engineering, Pertamina University

DOI:

https://doi.org/10.30656/jsmi.v4i2.2607

Keywords:

Discrete particle swarm optimization, Capacitated vehicle routing problem, Repeated measure ANOVA, Metaheuristic

Abstract

Capacitated Vehicle Routing Problem (CVRP) is known as an NP-hard problem. It is because CVRP problems are very hard for finding optimal solutions, especially in large instances. In general, the NP-hard problem is difficult to solve in the exact method, so the metaheuristic approach is implemented in the CVRP problem to find a near-optimal solution in reasonable computational time. This research uses the DPSO algorithm for solving CVRP with ten instances of benchmark datasets. DPSO implementation uses tuning parameters with the One Factor at Time (OFAT) method to select the best DPSO parameters. The outcome objective function will be compared with several PSO models proposed in previous studies. Statistical test using One Way Reputed Measure ANOVA is needed to compare algorithm performance. First, ANOVA uses for comparing’s results. Then, ANOVA is also used to test DPSO’s performance compared with DPSO-SA, SR-1, and SR-2 algorithm. The computational result shows that the basic DPSO algorithm not competitive enough with other methods for solving CVRP.

Downloads

Download data is not yet available.

References

P. Augerat, J. M. Belenguer, E. Benavent, A. Corberán, and D. Naddef, “Separating capacity constraints in the CVRP using tabu search,†Eur. J. Oper. Res., vol. 106, no. 2, pp. 546–557, 1998, doi: 10.1016/S0377-2217(97)00290-7.

G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,†Manage. Sci., vol. 6, no. 1, pp. 80–91, Oct. 1959, doi: 10.1287/mnsc.6.1.80.

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.

Y. Marinakis, G.-R. Iordanidou, and M. Marinaki, “Particle Swarm Optimization for the Vehicle Routing Problem with Stochastic Demands,†Appl. Soft Comput., vol. 13, no. 4, pp. 1693–1704, 2013, doi: 10.1016/j.asoc.2013.01.007.

M. A. Hannan, M. Akhtar, R. A. Begum, H. Basri, A. Hussain, and E. Scavino, “Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm,†Waste Manag., vol. 71, pp. 31–41, 2018, doi: 10.1016/j.wasman.2017.10.019.

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.

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.

T. Xiao and Z. Fu, “A genetic algorithm for the open vehicle routing problem with soft time windows,†J. Railw. Sci. Eng., vol. 5, no. 2, pp. 79–83, 2008. Available: http://en.cnki.com.cn/Article_en/CJFDTotal-CSTD200802017.htm.

A. L. Chen, G. K. Yang, and Z. M. Wu, “Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem,†J. Zhejiang Univ. Sci., vol. 7, no. 4, pp. 607–614, 2006, doi: 10.1631/jzus.2006.A0607.

R. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,†in MHS’95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 1995, pp. 39–43, doi: 10.1109/MHS.1995.494215.

A. R. Guner and M. Sevkli, “A Discrete Particle Swarm Optimization Algorithm for Uncapacitated Facility Location Problem,†J. Artif. Evol. Appl., vol. 2008, pp. 1–9, Apr. 2008, doi: 10.1155/2008/861512.

J. Zou, Q. Deng, J. Zheng, and S. Yang, “A close neighbor mobility method using particle swarm optimizer for solving multimodal optimization problems,†Inf. Sci. (Ny)., vol. 519, pp. 332–347, 2020, doi: 10.1016/j.ins.2020.01.049.

G. Singh and A. Singh, “A hybrid algorithm using particle swarm optimization for solving transportation problem,†Neural Comput. Appl., vol. 32, no. 15, pp. 11699–11716, 2020, doi: 10.1007/s00521-019-04656-1.

S. Irnich, P. Toth, and D. Vigo, “Chapter 1: The Family of Vehicle Routing Problems,†in Vehicle Routing, Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 1–33, 2014, doi: 10.1137/1.9781611973594.ch1.

S. Raff, “Routing and scheduling of vehicles and crews: The state of the art,†Comput. Oper. Res., vol. 10, no. 2, pp. 63–211, 1983, doi: 10.1016/0305-0548(83)90030-8.

X.-S. Yang, “7 Particle Swarm Optimization,†2014, doi: 10.1016/B978-0-12-416743-8.00007-5.

G. Lindfield and J. Penny, “Particle Swarm Optimization Algorithms,†Introd. to Nature-Inspired Optim., pp. 49–68, 2017, doi: 10.1016/b978-0-12-803636-5.00003-7.

R. C. Eberhart and Y. Shi, “Particle swarm optimization: Developments, applications and resources,†Proc. IEEE Conf. Evol. Comput. ICEC, vol. 1, no. February, pp. 81–86, 2001, doi: 10.1109/cec.2001.934374.

M. Isiet and M. Gadala, “Sensitivity analysis of control parameters in particle swarm optimization,†J. Comput. Sci., vol. 41, p. 101086, 2020, doi: 10.1016/j.jocs.2020.101086.

M. Pant, R. Thangaraj, and A. Abraham, “Particle swarm optimization: Performance tuning and empirical analysis,†Stud. Comput. Intell., vol. 203, pp. 101–128, 2009, doi: 10.1007/978-3-642-01085-9_5.

H. Wang, Q. Geng, and Z. Qiao, “Parameter tuning of particle swarm optimization by using Taguchi method and its application to motor design,†ICIST 2014 - Proc. 2014 4th IEEE Int. Conf. Inf. Sci. Technol., no. 20130415, pp. 722–726, 2014, doi: 10.1109/ICIST.2014.6920579.

J. S. Arora, Introduction to Optimum Design. Elsevier Science, 2004. Available: https://books.google.co.id/books?id=9FbwVe577xwC.

I. C. Trelea, “The particle swarm optimization algorithm: Convergence analysis and parameter selection,†Inf. Process. Lett., vol. 85, no. 6, pp. 317–325, 2003, doi: 10.1016/S0020-0190(02)00447-7.

Downloads

Published

2020-12-29

Issue

Vol. 4 No. 2 (2020)

Section

Research Article

License

All articles in Jurnal Sistem dan Manajemen Industri can be disseminated provided they include the identity of the article and the source of the article Jurnal Sistem dan Manajemen Industri. The publisher is not responsible for the contents of the article. The content of the article is the sole responsibility of the author

Creative Commons License

Jurnal Sistem dan Manajemen Industri is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

How to Cite

[1]
Aisyahna Nurul Mauliddina, Faris Ahmad Saifuddin, A. L. . Nagari, A. A. N. P. . Redi, A. C. . Kurniawan, and N. . Ruswandi, “Implementation of discrete particle swarm optimization algorithm in the capacitated vehicle routing problem”, j. sist. manaj. ind., vol. 4, no. 2, pp. 117–128, Dec. 2020, doi: 10.30656/jsmi.v4i2.2607.
Crossref
Scopus
Google Scholar
Europe PMC