Program Dinamis Pada Penentuan Rute Kendaraan Dengan Time Windows
DOI:
https://doi.org/10.31629/jg.v3i2.511Keywords:
penentuan rute kendaraan, program dinamis, algoritma eksakAbstract
Penentuan rute armada merupakan salah satu permasalahan optimisasi kombinatorik yang memiliki pengaruh pada distribusi barang. Pengiriman barang cepat busuk (perishable good) seperti produk darah, dengan karakteristik jarak tempuh yang pendek memungkinkan untuk dilakukan dengan satu kendaraan. Terdapat kendala time windows pada pelanggan dan depot yang membatasi pengiriman. Masalah penentuan rute dalam penelitian ini dipandang sebagai single vehicle routing problem dengan time windows. Penelitian ini bertujuan untuk mendeskripsikan algoritma yang ditulis berdasarkan program dinamis untuk masalah penentuan rute kendaraan dengan time windows. Pada algoritma diterapkan tes yang bertujuan meningkatkan performa algoritma. Pada bagian akhir diberikan contoh penyelesaian masalah penentuan rute kendaraan dengan time windows menggunakan algoritma.
Kata kunci: penentuan rute kendaraan; program dinamis; algoritma eksak
Routing problem is kind of combinatoric optimization problem that has an influence on the distribution of goods. Delivery of perishable good such as blood products with short travel characteristics makes it possible to do with one vehicle. There are time-windows constraints on customer and depots that limit delivery. This research aims to describe algorithms written based on dynamic programs for the problem of determining vehicle routes with time windows. In the algorithm applied a test that aims to improve the performance of the algorithm. In the end, given an example of solving the problem of determining a vehicle route with time windows using an algorithm.
Keywords: vehicle routing problem; dynamic programming; exact algorithm
Downloads
References
Azi, N., Gendreau, M., & Potvin, J. (2007). An exact algorithm for a single-vehicle routing problem with time windows and multiple routes, 178, 755–766. https://doi.org/10.1016/j.ejor.2006.02.019
Belman, R. (1954). The theory of dynamic programming, P-550.
Cormen, Thomas H;Leiserson, Charles E;Rivest, R. L. (2001). Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein Introduction to algorithms 2001.
Desrochers, M;Lenstra, J.K;Savelsber, M.W.P; Soumis, F. (n.d.). 5-Apr-desrochers.pdf.
Dumas, Y., Desrosiers, J., Gelinas, E., & Solomon, M. M. (1995). An optimal algorithm for the traveling salesman problem with time windows, (September 2015).
Horowitz, Elis;Sahni, Sartaj;Rasekaran, S. (n.d.). horowitz-and-sahani-fundamentals-of computer-algorithms-2nd-edition.pdf.
Lee, L. H., Tan, K. C., Ou, K., & Chew, Y. H. (2003). Vehicle capacity planning system: a case study on vehicle routing problem with time windows, 33(2), 169–178.
Melián-batista, B., Santiago, A. De, Angelbello, F., & Alvarez, A. (2014). A bi-objective vehicle routing problem with time windows : A real case in Tenerife à¬ÂÂ. Applied Soft Computing Journal, 17, 140–152. https://doi.org/10.1016/j.asoc.2013.12.012
Rich, J. L. (1999). A Computational Study of Vehicle Routing Application.
Toth, P. D. (2002). [Paolo_Toth;_Daniele_Vigo]_The_Vehicle_Routing_Pro(BookZZ.
