1. Home
  2. Vol 3, No 2 (2021)
  3. Wasilah

Modified Migrating Birds Optimization Algorithm: Multi-Depot Capacitated Vehicle Routing Problem

Dini Nur Wasilah, Agustina Pradjaningsih

Abstract


The multi-depot capacitated vehicle routing problem (MDCVRP) is a variation of the vehicle routing problem (VRP) modeled from distribution problems in the industrial world. This problem is a complex optimization problem in the field of operations research in applied mathematics. The MDCVRP is very interesting to discuss and find the best solution method. In this study, the authors apply the modified migrating birds' optimization (MMBO) algorithm, which is a hybrid of the migrating birds' optimization (MMBO) and iterated local search (ILS) algorithms. The purpose of this study is to analyze the results of applying the algorithm in solving MDCVRP. We used 20 MDCVRP data in simulation, grouped into four sizes (25, 50, 75, and 100 points). Based on the results of this research, it is known that the MMBO algorithm can produce the following solutions. First, on the data of 25 points, the experiment reaches the optimal value with small convergent iterations. Second, the best results on the data of 50 points have reached optimal value, but some other results have not been optimal. And, third, for data of 75 and 100 points, there is no optimal solution obtained by the MMBO algorithm. These results conclude that the MMBO algorithm effectively solves the MDCVRP problem with small data, but the bigger data, the more ineffective.

Keywords: MDCVRP; VRP; optimization; operation research; applied Mathematics; MMBO.

 

Abstrak

Multi-depot capacitated vehicle routing problem (MDCVRP) adalah salah satu variasi dari vehicle routing problem (VRP) yang dimodelkan dari permasalahan distribusi di dunia industri. Permasalahan ini merupakan permasalahan optimasi kompleks dalam bidang riset operasi ilmu matematika terapan. MDCVRP sangat menarik untuk dibahas dan dicari metode penyelesaian terbaik. Dalam penelitian ini, penulis menerapkan algoritma modified migrating birds optimization (MMBO) yang merupakan hybrid algoritma migrating birds optimization (MBO) dan iterated local search (ILS). Tujuan penelitian ini adalah menganalisis hasil penerapan algoritma dalam menyelesaikan MDCVRP. Untuk simulasi, penulis menggunakan 20 data MDCVRP yang dikelompokkan menjadi empat ukuran (25, 50, 75, dan 100 titik). Berdasarkan hasil penelitian yang telah dilakukan, diketahui bahwa algoritma MMBO mampu menghasilkan solusi sebagai berikut. Pertama, Pada data 25 titik, percobaan mencapai nilai optimal dengan iterasi konvergen yang kecil. Kedua, Hasil terbaik pada data 50 titik telah mencapai nilai optimal namun sebagain hasil lainnya belum optimal. Dan ketiga, untuk data 75 dan 100 titik, tidak terdapat solusi optimal yang dihasilkan algoritma MMBO. Dari hasil tersebut dapat disimpulkan bahwa algoritma MMBO efektif untuk menyelesaikan MDCVRP data kecil, namun semakin besar datanya menjadi kurang efektif.

Kata kunci: MDCVRP; VRP; optimasi; riset operasi; matematika terapan; MMBO. 


Keywords


MDCVRP;VRP;Optimization; Operation Research; Applied Mathematics;MMBO

References


B. L. Golden, S. Raghavan, and E. A. Wasil, The Vehicle Routing Problem: Latest Advances and New Challenges (Vol 43), Berlin: Springer Science & Business Media, 2008.

T. Murata and R. Itai, "Multi-Objective Vehicle Routing Problems Using Two-Fold EMO Algorithms to Enhance Solution Similarity on Non-Dominated Solutions," International Conference on Evolutionary Multi-Criterion Optimization, pp. 885-896, 2005.

P. Toth and D. Vigo, The Vehicle Routing Problem, Philadelphia: Society for Industrial and Applied Mathematics, 2002.

W. G. T. H. Ho, P. Ji, and H. C. Lau, "A Hybrid Genetic Algorithm for the Multi-Depot Vehicle Routing Problem," Engineering Applications of Artificial Intelligence, vol. 21, no. 4, pp. 548-557, 2008.

M. Mirabi, S. M. T. F. Ghomi and F. Jolai, "Efficient Stochastic Hybrid Heuristics for the Multi-Depot Vehicle Routing Problem," Robotics and Computer-Integrated Manufacturing, vol. 26, pp. 564-569, 2010.

B. Yu, Z. Z. Yang, and J. X. Xie, "A Parallel Improved Ant Colony Optimization for Multi-Depot Vehicle Routing Problem," Journal of the Operational Research Society, vol. 62, pp. 183-188, 2011.

S. Geetha and G. Poonthalir, "Nested Particle Swarm Optimization for Multi-Depot Vehicle Routing Problem," Int. J. Operational Research, vol. 16, no. 3, pp. 329-348, 2013.

A. A. Juan, I. Pascual, D. Guimarans and B. Barriors, "Combining Biased Randomized with Iterated Local Search for Solving the Multidepot Vehicle Routing Problem," International Transactions in Operational Research, vol. 22, no. 4, pp. 647-667, 2015.

F. B. d. Oliviera, R. Enayatifar, H. J. Sadaei, F. G. Guimaraes, and J. Y. Potvin, "A Cooperative Coevolutionary Algorithm for the Multi-Depot Vehicle Routing Problem," Expert Systems with Applications, vol. 43, pp. 117-130, 2016.

L. W. Shen, H. Asmuni and F. C. Weng, "A Modified Migrating Birds Optimization for University Course Timetabling Problem," Jurnal Teknologi, vol. 72, no. 1, pp. 89-96, 2015.

E. Duman, M. Uysal and A. F. Alkaya, "Migrating Birds Optimization: A New Metaheuristic Approach and Its Performance on Quadratic Assignment Problem," Information Sciences, vol. 217, pp. 65-77, 2012.

H. R. Lourenco, O. C. Martin, and T. Stutzle, "Iterated Local Search: Framework and Applications," International Series in Operations Research & Management Science, vol. 146, pp. 363-397, 2010.

J. A. Filar and D. Krass, "Hamiltonian Cycles and Markov Chains," Mathematics of Operations Research, vol. 19, no. 1, pp. 223-237, 2012.


Full Text: PDF

DOI: 10.15408/inprime.v3i2.21257

Refbacks

  • There are currently no refbacks.