Metode Heuristik untuk Menentukan Jadwal Periodik Rute Kendaraan Distribusi Produk dengan Permintaan Stokastik

Mohamad Sofitra, Dedi Wijayanto, Noveicalistus H. Djanggu

Abstract


Pada penelitian ini dirancang suatu metode solusi heuristik untuk menyelesaikan permasalahan Periodic Vehicle Routing Problem with Stochastic Demand pada kasus rural logistics. Tujuannya adalah memperoleh suatu set jadwal distribusi berupa tour apriori harian kendaraan ke sejumlah pengecer selama periode waktu  yang memberikan ekspektasi total waktu distribusi paling minimum. Algoritma solusi yang dirancang terdiri atas dua tahapan proses yaitu tahap konstruksi solusi dan tahap perbaikan solusi. Tahap konstruksi solusi dilakukan dengan menggunakan prinsip cluster-first-route-second. Sedangkan tahap perbaikan solusi digunakan strategi eksploratif dan strategi eksploitatif yang berfungsi mencari tetangga-tetangga solusi yang mungkin lebih baik dari solusi-solusi sementara yang telah berhasil ditemukan pada tahap konstruksi atau tahap perbaikan solusi pada iterasi sebelumnya. Strategi eksploratif terdiri atas dua metode yaitu metode inter-tour circular exchange dan overtime cut-off, sedangkan strategi eksploitatif menggunakan metode intra-tour swap. Pengujian kinerja algoritma solusi hasil rancangan dilakukan menggunakan 27 blok eksperimen hasil kombinasi tiga faktor yang diduga merupakan parameter-parameter yang berpengaruh pada kinerja algoritma solusi. Dengan menggunakan pengaturan parameter pencarian yang tepat, algoritma yang dirancang mampu menunjukkan kinerja yang memuaskan yaitu menghasilkan solusi yang berkualitas baik dengan waktu komputasi yang wajar.


Keywords


vehicle routing problem; stochastic demand; jadwal periodik; rural logistics; solusi heuristik

Full Text:

PDF

References


G. D. Konstantakopoulos, S. P. Gayialis, and E. P. Kechagias, “Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification,” Oper. Res., vol. 22, no. 3, pp. 2033–2062, Jul. 2022, doi: 10.1007/s12351-020-00600-7.

H. Zhang, H. Ge, J. Yang, and Y. Tong, “Review of Vehicle Routing Problems: Models, Classification and Solving Algorithms,” Arch. Comput. Methods Eng., vol. 29, no. 1, pp. 195–221, Jan. 2022, doi: 10.1007/s11831-021-09574-x.

A. Mor and M. G. Speranza, “Vehicle routing problems over time : a survey,” 4OR, vol. 18, no. 2, pp. 129–149, 2020, doi: 10.1007/s10288-020-00433-2.

R. Elshaer and H. Awad, “A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants,” Comput. Ind. Eng., vol. 140, p. 106242, Feb. 2020, doi: 10.1016/j.cie.2019.106242.

J. Oyola, H. Arntzen, and D. L. Woodruff, “The stochastic vehicle routing problem, a literature review, part I: models,” EURO J. Transp. Logist., vol. 7, no. 3, pp. 193–221, 2018, doi: 10.1007/s13676-016-0100-5.

M. Gendreau, O. Jabali, and W. Rei, “Future research directions in stochastic vehicle routing,” Transp. Sci., vol. 50, no. 4, pp. 1163–1173, 2016, doi: 10.1287/trsc.2016.0709.

F. Torres, M. Gendreau, and W. Rei, “Crowdshipping: An open VRP variant with stochastic destinations,” Transp. Res. Part C Emerg. Technol., vol. 140, p. 103677, Jul. 2022, doi: 10.1016/j.trc.2022.103677.

A. A. Juan et al., “A review of the role of heuristics in stochastic optimisation: from metaheuristics to learnheuristics,” Ann. Oper. Res., vol. 320, no. 2, pp. 831–861, Jan. 2023, doi: 10.1007/s10479-021-04142-9.

J. Oyola, H. Arntzen, and D. L. Woodruff, “The stochastic vehicle routing problem, a literature review, Part II: solution methods,” EURO J. Transp. Logist., vol. 6, no. 4, pp. 349–388, Dec. 2017, doi: 10.1007/s13676-016-0099-7.

Kellen D. Endler, Cassius T. Scarpin, Maria T. A. Steiner, and Alexandre C. Choueiri, “Systematic Review of the Latest Scientific Publications on the Vehicle Routing Problem,” Asia-Pac. J. Oper. Res., vol. 40, no. 6, p. 2250046.

M. A. Ebrahimi, H. Dehghan Dehnavi, M. Mirabi, M. T. Honari, and A. Sadeghian, “Solving NP hard problems using a new genetic algorithm,” Int. J. Nonlinear Anal. Appl., no. Online First, Apr. 2022, doi: 10.22075/ijnaa.2022.26610.3364.

D. J. Bertsimas, “A Vehicle Routing Problem with Stochastic Demand,” Oper. Res., vol. 40, no. 3, pp. 574–585, Jun. 1992, doi: 10.1287/opre.40.3.574.

L. Calvet, D. Wang, A. Juan, and L. Bové, “Solving the multidepot vehicle routing problem with limited depot capacity and stochastic demands,” Int. Trans. Oper. Res., vol. 26, no. 2, pp. 458–484, Mar. 2019, doi: 10.1111/itor.12560.

C. L. Quintero-Araujo, D. Guimarans, and A. A. Juan, “A simheuristic algorithm for the capacitated location routing problem with stochastic demands,” J. Simul., vol. 15, no. 3, pp. 217–234, Jul. 2021, doi: 10.1080/17477778.2019.1680262.

D. R. Gaur, A. Mudgal, and R. R. Singh, “Improved approximation algorithms for cumulative VRP with stochastic demands,” Discrete Appl. Math., vol. 280, pp. 133–143, Jun. 2020, doi: 10.1016/j.dam.2018.01.012.

F. Liu, C. Lu, L. Gui, Q. Zhang, X. Tong, and M. Yuan, “Heuristics for Vehicle Routing Problem: A Survey and Recent Advances.” arXiv, Mar. 01, 2023. Accessed: Nov. 01, 2023. [Online]. Available: http://arxiv.org/abs/2303.04147

B. Singh, L. Oberfichtner, and S. Ivliev, “Heuristics for a cash-collection routing problem with a cluster-first route-second approach,” Ann. Oper. Res., vol. 322, no. 1, pp. 413–440, Mar. 2023, doi: 10.1007/s10479-022-04883-1.

F. Kocatürk, G. Y. Tütüncü, and S. Salhi, “The multi-depot heterogeneous VRP with backhauls: formulation and a hybrid VNS with GRAMPS meta-heuristic approach,” Ann. Oper. Res., vol. 307, no. 1–2, pp. 277–302, Dec. 2021, doi: 10.1007/s10479-021-04137-6.

Pisinger , David and Ropke, Stefan, “Large neighborhood search,” in Handbook of Metaheuristics, 3th ed., vol. 146, M. Gendreau and J.-Y. Potvin, Eds., in International Series in Operations Research & Management Science, vol. 146. , Boston, MA: Springer US, 2019.




DOI: http://dx.doi.org/10.26418/jp.v10i1.72376

Refbacks

  • There are currently no refbacks.