Ant Colony Optimization on Multiple Pickup and Delivery Problem in Crowdsourced Delivery Services

VICTOR PASKALATHIS, Dr. Azhari S.N., M.T.

2017 | Tesis | S2 Ilmu Komputer

Pengiriman barang berbasis urun daya (crowdsourcing) umumnya dilakukan melalui pengiriman langsung, yakni dengan mengambil barang di lokasi asal dan mengirimnya langsung ke lokasi tujuan. Hal ini dilakukan dengan mengutus kurir terdekat dari lokasi asal. Efisiensi dapat diperoleh dengan menerapkan pengambilan dan pengiriman jamak, yakni dengan cara memperbanyak jumlah permintaan yang dapat dipenuhi dalam satu perjalanan. Hal ini merupakan kesempatan yang perlu dikaji lebih dalam, mengingat layanan pengiriman barang konvensional saat ini masih mengandalkan pengiriman esok hari, sedangkan layanan pengiriman barang hari yang sama lebih mahal dibanding pengiriman barang berbasis urun daya. Penelitian ini mengimplementasikan algoritma eksak untuk menyelesaikan masalah konsolidasi hingga tiga permintaan dalam satu perjalanan. Algoritma heuristik digunakan untuk menyusun rute awal berdasarkan penghematan jarak tertinggi. Hasilnya kemudian dioptimasi menggunakan algoritma semut. Lima model pengiriman akan diperbandingkan dalam penelitian ini, yaitu perhitungan berdasarkan: (1) data aktual; (2) matriks jarak dan waktu; (3) konsolidasi dari dua permintaan; (4) konsolidasi dari tiga permintaan; dan (5) algoritma semut. Studi kasus yang digunakan adalah wilayah operasional Yogyakarta selama satu hari penuh. Hasil optimasi menggunakan algoritma semut menunjukkan bahwa 178 permintaan dapat dipenuhi dalam 93 perjalanan. Model ini juga memberikan penghematan jarak tempuh sebesar 20%, waktu tempuh sebesar 14% serta peningkatan keuntungan dua kali lipat dibandingkan dengan pengiriman langsung.

Common practice in crowdsourced delivery services is through direct delivery. This is done by dispatching direct trip to driver nearby the origin location. Efficiency can be gained through multiple pickup and delivery. This can be done by increasing the number of requests in a trip. This is quite an opportunity since current conventional courier services are using next-day delivery and same-day courier costs much more expensive than crowdsourced delivery services. The research implemented exact algorithm to solve the consolidation problem with up to 3 requests in a trip. The consolidated trip is reflected with how much distance savings compared with direct delivery. Heuristic algorithm is performed to construct initial route based on highest savings. The result then optimized using Ant Colony Optimization (ACO). Five delivery models are compared, (1) actual delivery, (2) direct delivery based on distance and duration matrices, (3) 2-consolidated delivery, (4) 3-consolidated delivery, and (5) ACO. The case study is based on Yogyakarta area for a whole day. The ACO model show that 178 requests can be completed in 93 trips. Compared to direct delivery, the model also provides 20% distance savings, 14% duration savings, and doubles the profit.

Kata Kunci : Ant Colony Optimization, crowdsourcing, Pickup and Delivery Problem, delivery route, transportation