Algoritma Genetika untuk Pemecahan Masalah Rute Kendaraan dengan Ukuran dan Campuran Armada, Trip Majemuk, Pengiriman Terbagi, Produk Majemuk, dan Kendaraan dengan Kompartemen Majemuk
Abstract
This paper discusses a variant of the basic vehicle routing problem (VRP) by including the following characteristics: fleet size and mix, multiple trips, split delivery, and multiple compartments. One of real cases of this problem is related to determining tanker’s routes in delivering fuel products from a supply port to a number of destination ports. Each tanker has several compartments where each compartment is dedicated to a certain fuel product. In this paper, a solution approach based on genetic algorithm (GA) is proposed and tested using nine hypothetical instances. Experiment results show that the proposed GA gives consistent results measured by coefficient variationsMetrics
References
Dantzig, G. B. and Ramser, J., The Truck Dispatching Problem, Management Science, 6 (1), 1959, pp. 80-91.
Wassan, N. A. and Osman, I. H., Tabu Search Variant for the Mix Fleet Vehicle Routing Problem, Journal of the Operational Research Society, 53 (7), 2002, pp. 768-782.
Lee, Y. H., Kim, J. I., Kang, K. H. and Kim, K. H., A Heuristic for Vehicle Fleet Mix Problem using Tabu Search and Set Partitioning, Journal of the Operational Research Society, 59 (6), 2008, pp. 833-841.
Gheysens, F., Golden, B., and Assad, A., A Comparison of Techniques for Solving the Fleet Size and Mix Vehicle Routing Problem, OR Spektrum, 6, 1984, pp. 207-216.
Brandão, J. and Mercer, A., A Tabu Search Algorithm for the Multi-Trip Vehicle Routing and Scheduling Problem, European Journal of Operational Research, 100, 1997, pp. 180-191.
Taillard, É. D., Laporte, G. and Gendreau, M., Vehicle Routeing with Multiple Use of Vehicles, Journal of the Operational Research Society, 47 (8), 1996, pp. 1065-1070.
Brandão, J. C. S and Mercer, A., The Multi-Trip Vehicle Routing Problem, Journal of the Operational Research Society, 49 (8), 1998, pp. 799-805.
Zhao, Q. -H, Wang, S. -Y., Lai, K. K. and Xia, G. -P., A Vehicle Routing Problem with Multiple Use of Vehicles, Advanced Modeling and Optimization, 4 (3), 2002, pp. 31-40.
Petch, R. J. and Salhi, S., A Multi-Phase Constructive Heuristic for the Vehicle Routing Problem with Multiple Trips, Discrete Applied Mathematics, 133, 2004, pp. 69-92.
Salhi, S. and R. J. Petch, R. J., A GA based heuristic for the vehicle routing problem with multiple trips, Journal of Mathematical Modelling and Algorithms, 6 (4), 2007, pp. 591-613.
Dror, M, Laporte, G. and Trudeau, P., Vehicle Routing with Split Deliveries, Discrete Applied Mathematics, 50, 1994, pp. 239-254.
Archetti, C., Speranza, M. G. and Hertz, A., A Tabu Search Algorithm for The Split Delivey Vehicle Routing Problem, Transportation Science, 40 (1), 2006, pp. 64-73.
Boudia, M., Prins, C. and Reghioui, M., An Effective Memetic Algorithm with Population Management for the Split Delivery Vehicle Routing Problem, Proceedings of the 4th international conference on Hybrid metaheuristics, Dortmund, Germany, 2007.
Tavakkoli-Moghaddam, R., Safaei,N., Kah, M. M. O. and Rabbani, M., A New Capacitated Vehicle Routing Problem with Split Service for Minimizing Fleet Cost by Simulated Annealing, Journal of the Franklin Institute, 344, 2007, pp. 406–425.
Derigs, U, Li, B. and Vogel, U., Local Search-Based Metaheuristics for the Split Delivery Vehicle Routing Problem, Journal of the Operational Research Society, 61 (9), 2010, pp. 1356-1364.
Wilck IV, J. H. and Cavalier, T. M., A Construction Heuristic for the Split Delivery Vehicle Routing Problem, American Journal of Operations Research, 2, 2012, pp. 153-162.
Christofides, N., Mingozzi, A. and Toth, P., The Vehicle Routing Problem, in Combinatorial Optimization, Chichester, UK, Wiley, 1979, pp. 315-338.
Chajakis, E. D. and Guignard, M., Scheduling Deliveries in Vehicles with Multiple Compartments, Journal of Global Optimization, 26, 2003, pp. 43-78.
El Fallahi, A., Prins, C., and Calvo, R. W., A Memetic Algorithm and a Tabu Search for the Multi-Compartment Vehicle Routing Problem, Computers & Operations Research, 35 (5), 2008, pp. 1725-1741.
Avella, P., Boccia, M. and A. Sforza, Solving a fuel delivery problem by heuristics and exact approaches, European Journal of Operational Research, 152 (1), 2004, pp. 170-179.
Derigs, U, Gottlieb, J., Kalkof, J., Piesche, M., Rothlauf, F. and Vogel, U. Vehicle Routing with Compartments: Applications, Modelling and Heuristics, OR Spectrum, 33 (4), 2011, pp. 885-914.
Reed, M, Yiannakou, A. and Evering, R., An Ant Colony Algorithm for the Multi-Compartment Vehicle Routing Problem, Applied Soft Computing, 15, 2014, pp. 169-176.
Suprayogi and Komara, S., A Sequential Insertion Algorithm for Solving a Distribution Problem of Fuel Products, JSPS Seminar on Marine Transportation Engineering, Hiroshima, Japan, 2006.
Suprayogi, Komara, S. and Yamato, H., Local Search Technique for Solving a Delivery Problem of Fuel Products, Proceedings of the 2nd International Conference on Operations and Supply Chain Management, Bangkok, Thailand, 2007.
Suprayogi dan Arvianto, A., Masalah Rute Kendaraan dengan Rute Majemuk, Jendela Waktu Majemuk, Pengiriman Terbagi, Produk Majemuk dan Kompartemen Majemuk, Prosiding Seminar Nasional Teknik Industri BKSTI 2014, Bukittinggi, Indonesia, 2014.
Arvianto, A., Setiawan, A. H. dan Saptadi, S., Model Vehicle Routing Problem dengan Karakteristik Rute Majemuk, Multiple Time Windows, Multiple Products dan Heterogeneous Fleet untuk Depot Tunggal, Jurnal Teknik Industri, 16 (2), 2014, pp. 85-96.
Paillin, D. B. dan Wattimena, E., Penerapan algoritma sequential insertion dalam pendistribusian BBM di kawasan timur Indonesia (Studi kasus pada PT Pertamina UPMS VIII Terminal Transit Wayame-Ambon), ARIKA, 9 (1), 2015, pp. 53-62.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Â