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

  • 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
Abstract views: 446 , PDF downloads: 9744
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.

PlumX Metrics

Published
2020-12-29
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.
Section
Research Article