Ant Colony Optimization on Crowdsourced Delivery Trip Consolidation
Abstract: Common practice in
crowdsourced delivery services is through direct delivery. That is by dispatching direct trip to a driver
nearby the origin location. The total distance can be reduced through multiple
pickup and delivery by increasing the number of requests in a trip.
The research implements exact algorithm to solve the consolidation
problem with up to 3 requests in a trip. Greedy heuristic is performed to
construct initial route based on highest savings. The result is then optimized
using Ant Colony Optimization (ACO). Four scenarios are compared. A direct
delivery scenarios and three multiple pickup and delivery scenarios. These
include 2-consolidated delivery, 3-consolidated delivery, and 3-consolidated
delivery optimized with ACO. Four parameters are used to evaluate using
Analytical Hierarchical Process (AHP). These include the number of trips, total
distance, total duration, and security concerns.
The case study is based on Yogyakarta area for a whole day. The final
route optimized with ACO shows 178 requests can be completed in 94 trips.
Compared to direct delivery, consolidation can provides savings up to 20% in
distance and 14% in duration. The evaluation result using AHP shows that ACO
scenario is the best scenario.
Keywords: Ant Colony
Optimization; Pickup and Delivery Problem; highest savings; crowdsourced; trip
consolidation
Penulis: Victor Paskalathis
Kode Jurnal: jptinformatikadd170093
