开放期刊系统

有容量限制的车辆路径问题启发式模型的比较研究

Agung Chandra, Aulia Naro

摘要

CVRP 是 VRP 的变体,可用于查找最小距离和车辆数量。本文对三种初始解算法进行了比较,以找出货物从配送 中心到西雅加达所有常规门店的最短距离—改进的 Clarke 和 Wright (ICW)算法,Karagul Tokat Aydemir (KTA)算法,以及扫描-聚 类优先路线第二算法。结果表明,与其他两种算法相比,扫描算法的总距离最短,比 KTA 算法短 48.57%,比 ICW 算法短 33.33%。 需要评估更大的样本量来加强这一发现。

关键词

CVRP;ICW;KTA;扫描算法

全文:

PDF

参考

[1] K. Jerabek, P. Majercak, T. Kliestik, K. Valaskova. Application of Clark and Wright’s Savings Algorithm Model to Solve Routing Problem in Supply Logistics. Preliminary communication, 2016. doi: 10.17818/NM/2016/SI7. [2] A. Chandra, B. Setiawan. Optimizing the Distribution Routes Using Vehicle Routing Problem (VRP) Method. Jurnal Manajemen Transportasi & Logistik, 2018,5(2):105–116. [3] A. Chandra, A. Naro. Studi Komparatif Metaheuristics untuk Mengoptimalkan Jalur Distribusi. Laporan Riset Internal (unpublished report). Universitas Mercu Buana; 2019. [4] G.D. Konstantakopoulos, S.P. Gayialis, I.P. Tatsiopoulos. Vehicle Routing Problem for Urban Freight Transportation: A Review. Conference Paper, June 2017. [5] T. Caric, S. Pasagic, Z. Lanovic. Vehicle Routing Problem Models. Science in Traffic Review, 2004,16(1):59–62. [6] F.W. Takes, W.A. Kosters. Applying Monte Carlo Techniques in the Capacitated Vehicle Routing Problem. White Paper, Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands, 2010. [7] T. Pichpibul, R. Kawtummachai. An Improved Clarkee and Wrigth Savings Algorithm for the Capacitated Vehicle Routing Problem. Science Asia 2012,38:307–318. [8] Y. Marinakis, A. Migdalas. Annotated Bibliography in Vehicle Routing. Operations Research, An International Journal, 2007,7(1):27–46. [9] F.W. Takes, W.A. Kosters. Applying Monte Carlo Techniques to the Capacitated Vehicle Routing Problem. Leiden Institute ofAdvanced Computer Science, Leiden University, The Netherlands; 2010. [10] R.B.S. Shankar, K.D. Reddy, P. Venkataramaiah. Solution to a Capacitated Vehicle Routing Problem Using Heuristics and Firefly Algorithm. International Journal of Applied Engineering Research, 2018,13(21):15247–15254. [11] T. Pichpibul, R. Kawtummachai. A Heuristic Approach Based on Clarkee – Wright Algorithm for Open Vehicle Routing Problem. The Scientific World Journal, 2013. http://dx.doi.org/10.1155/2013/874349. [12] K. Karagul, S. Tokat, F. Aydemir. Physics-inspired Optimization Algorithm for Obtaining Initial Routes of Capacitated Vehicle Routing Problem. EURO Working Group on Vehicle Routing and Logistic Optimization (VeRoLog), Oslo, Norway; 2014. [13] K. Karagul, S. Tokat, F. Aydemir. A New Algorithm to The Construction of The Initial Routes for the Capacitated Vehicle Routing Problem. Journal of Engineering Sciences and Design, 2016,4(3):215–216. [14] N. Suthikarnnarunai. A Sweeping Algorithm for the Mix Fleet Vehicle Routing Problem. Proceedings of International Multiconference of Engineers and Computer Scientists Volume II, Hong Kong; 2008. [15] R.C. Larson, A.R. Odoni. Urban Operations Research. Chapter 6: Applications of Network Models. Prentice Hall, New Jersey; 1981. http://mit.edu/urban_or_book/www/book/chapter6/6.4.12.html [16] E. Baran.Route Determination for Capacitated Vehicle Routing Problem with Two Different Hybrid Heuristic Algorithm. International Journal of Engineering Science and Application 2018,2(2):55–64. [17] K. Karagul, S. Tokat, E. Aydemir. A New Algorithm for the Establishment of Initial Route for Capacity Constaints Vehicle Routing Problem. Journal of Engineering Sciences and Design, 2016,4(3):215–226. doi: 10.21923/jesd.60313. [18] K. Karagul, M.G. Kay, S. Tokat. A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problem. Journal of Science 2018,31(2):489–513. [19] R.F. Hartl, S.N. Parragh. Transportation Logistics: An Introduction to Vehicle Route Problem: Cluster First Route Second Heuristics. 2012. https://prolog.univie.ac.at/teaching/LVAs/KFKTL/WS%2012/TL-Part5-VRP-Intro-Handout.pdf [20] R.B.S. Shankar, K.D. Reddy. A Comparative Study on Heuristic and Metaheuristic Approach in Solving a Capacitated Vehicle Routing Problem. International Journal of Innovative Science and Research Technology 2018,3(9):94–98. [21] B. Wibowo. Budhi’s Notes. Part II – Solving Vehicle Routing Problem with Excel. 2016. https://budhiwibowo.files.wordpress.com/2016/03/dss-case-2-vehicle-routing-problem.xlsx.


(55 摘要 Views, 50 PDF Downloads)

Refbacks

  • 当前没有refback。