Simulated annealing algorithm for solving the capacitated vehicle routing problem: a case study of pharmaceutical distribution

Authors

  • Anak Agung Ngurah Perwira Redi Pertamina University
  • Fiki Rohmatul Maula Pertamina University
  • Fairuz Kumari Pertamina University
  • Natasha Utami Syaveyenda Pertamina University
  • Nanda Ruswandi Pertamina University
  • Annisa Uswatun Khasanah Universitas Islam Indonesia
  • Adji Chandra Kurniawan Pertamina University

DOI:

https://doi.org/10.30656/jsmi.v4i1.2215

Keywords:

VRP, Nearest neighbour, Simulated annealing, Heuristic method

Abstract

This study aims to find a set of vehicles routes with the minimum total transportation time for pharmaceutical distribution at PT. XYZ in West Jakarta. The problem is modeled as the capacitated vehicle routing problem (CVRP). The CVRP is known as an NP-Hard problem. Therefore, a simulated annealing (SA) heuristic is proposed. First, the proposed SA performance is compared with the performance of the algorithm form previous studies to solve CVRP. It is shown that the proposed SA is useful in solving CVRP benchmark instances. Then, the SA algorithm is compared to a commonly used heuristic known as the nearest neighborhood heuristics for the case study dataset. The results show that the simulated Annealing and the nearest neighbor algorithm is performing well based on the percentage differences between each algorithm with the optimal solution are 0.03% and 5.50%, respectively. Thus, the simulated annealing algorithm provides a better result compared to the nearest neighbour algorithm. Furthermore, the proposed simulated annealing algorithm can find the solution as same as the exact method quite consistently. This study has shown that the simulated annealing algorithm provides an excellent solution quality for the problem.

References

J. T. Mentzer, R. Gomes, and R. E. Krapfel, “Physical distribution service: A fundamental marketing concept?,†J. Acad. Mark. Sci., vol. 17, no. 1, pp. 53–62, Dec. 1989.

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

P. Toth and D. Vigo, Vehicle routing: problems, methods, and applications. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2014.

P. Campelo, F. Neves-Moreira, P. Amorim, and B. Almada-Lobo, “Consistent vehicle routing problem with service level agreements: A case study in the pharmaceutical distribution sector,†Eur. J. Oper. Res., vol. 273, no. 1, pp. 131–145, Feb. 2019.

N. Shah, “Pharmaceutical supply chains: key issues and strategies for optimisation,†Comput. Chem. Eng., vol. 28, no. 6–7, pp. 929–941, Jun. 2004.

M. A. Figliozzi, “Planning approximations to the average length of vehicle routing problems with time window constraints,†Transp. Res. Part B Methodol., vol. 43, no. 4, pp. 438–447, May 2009.

J. M. de Magalhães and J. P. de Sousa, “Dynamic VRP in pharmaceutical distribution—a case study,†Cent. Eur. J. Oper. Res., vol. 14, no. 2, pp. 177–192, Jun. 2006.

G. Nakiboglu and P. E. Gunes, “Vehicle Routing Problem in Pharmaceuticals Distribution and Genetic Algorithm Application,†in 2018 International Conference on Artificial Intelligence and Data Processing (IDAP), Sep. 2018, pp. 1–6.

R. A. Fadhil, E. G. Prabowo, and A. A. N. P. Redi, “Penentuan Lokasi Distribution Center dengan Metode P-Median di PT Pertamina EP,†J. Manaj. Ind. dan Logistik, vol. 4, no. 1, pp. 1–9, 2020.

W. Winarno and A. A. N. P. Redi, “Analisa Perbandingan Metode Simulated Annealing dan Large Neighborhood Search untuk Memecahkan Masalah Lokasi dan Rute Kendaraan Dua Eselon,†J. Manaj. Ind. dan Logistik, vol. 4, no. 1, pp. 35–46, 2020.

H. M. Repolho, J. F. Marchesi, O. S. S. Júnior, and R. R. R. Bezerra, “Cargo theft weighted vehicle routing problem: modeling and application to the pharmaceutical distribution sector,†Soft Comput., vol. 23, no. 14, pp. 5865–5882, Jul. 2019.

B. Bouziyane, B. Dkhissi, and M. Cherkaoui, “Multiobjective optimization in delivering pharmaceutical products with disrupted vehicle routing problem,†Int. J. Ind. Eng. Comput., vol. 11, no. 2, pp. 299–316, 2020.

A. A. N. P. Redi and A. A. N. A. Redioka, “Algoritma Simulated Annealing untuk Optimasi Rute Kendaraan dan Pemindahan Lokasi Sepeda pada Sistem Public Bike Sharing,†J. Sist. dan Manaj. Ind., vol. 3, no. 1, pp. 50–58, Jul. 2019.

P. J. M. van Laarhoven and E. H. L. Aarts, Simulated annealing. Dordrecht: Springer Netherlands, 1987.

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,†Science (80-. )., vol. 220, no. 4598, pp. 671–680, May 1983.

M. A. Mohammed et al., “Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution,†J. Comput. Sci., vol. 21, pp. 232–240, Jul. 2017.

L. Du and R. He, “Combining Nearest Neighbor Search with Tabu Search for Large-Scale Vehicle Routing Problem,†Phys. Procedia, vol. 25, pp. 1536–1546, 2012.

J. Rudianto, “ersepsi Apoteker Terhadap Konseling Pasien dan Pelaksanaannya di Apotek-Apotek Kabupaten Kudus,†Universitas Muhammadiyah Surakarta, 2011.

V. F. Yu, A. A. N. P. Redi, C. Halim, and P. Jewpanya, “The path cover problem: Formulation and a hybrid metaheuristic,†Expert Syst. Appl., vol. 146, p. 113107,. May 2020.

P. Augerat, D. Naddef, J. M. Belenguer, E. Benavent, A. Corberan, and G. Rinaldi, Computational results with a branch and cut code for the capacitated vehicle routing problem. France: Institut IMAG, 1995.

V. F. Yu, A. A. N. P. Redi, C.-L. Yang, E. Ruskartina, and B. Santosa, “Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem,†Appl. Soft Comput., vol. 52, pp. 657–672, Mar. 2017.

Downloads

Published

2020-07-28

Issue

Vol. 4 No. 1 (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]
“Simulated annealing algorithm for solving the capacitated vehicle routing problem: a case study of pharmaceutical distribution”, j. sist. manaj. ind., vol. 4, no. 1, pp. 41–49, Jul. 2020, doi: 10.30656/jsmi.v4i1.2215.
Crossref
Scopus
Google Scholar
Europe PMC

Similar Articles

1-10 of 59

You may also start an advanced similarity search for this article.

Most read articles by the same author(s)