Algoritma Genetika untuk Pemecahan Masalah Rute Kendaraan dengan Ukuran dan Campuran Armada, Trip Majemuk, Pengiriman Terbagi, Produk Majemuk, dan Kendaraan dengan Kompartemen Majemuk

Authors

  • Suprayogi Suprayogi Institut Teknologi Bandung, Bandung
  • Daniel Bunga Paillin Universitas Pattimura, Ambon

:

https://doi.org/10.9744/jti.19.2.115-124

Keywords:

vehicle routing problem, fleet size and mix, multiple trips, split delivery, multiple compartments, genetic algorithm

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 variations

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.

Downloads

Published

2018-01-08

How to Cite

[1]
S. Suprayogi and D. B. Paillin, “Algoritma Genetika untuk Pemecahan Masalah Rute Kendaraan dengan Ukuran dan Campuran Armada, Trip Majemuk, Pengiriman Terbagi, Produk Majemuk, dan Kendaraan dengan Kompartemen Majemuk”, Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri, vol. 19, no. 2, pp. 115-124, Jan. 2018.

Most read articles by the same author(s)