* Corresponding Author
Hide
Show all
Ant Colony Optimization on Crowdsourced Delivery Trip Consolidation
https://doi.org/10.22146/ijccs.16631 Victor Paskalathis(1*), Azhari SN(2)
(1)
(2) Jurusan Ilmu Komputer dan Elektronika, FMIPA UGM, Yogyakarta
(*) Corresponding Author
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
Full Text:
PDFReferences
USPS OIG, 2014, Using the 'Crowd' to Deliver Packages, USPS OIG, Arlington.
Berling, P., & Eng-Larson, F., 2016, Pricing and Timing of Consolidated Deliveries in Presence of an Express Alternative - Financial and Environmental Analysis, European Journal of Operational Research, 250(2), pp. 590-601.
Savelsbergh, M.W.P, Sol, M., 1995, The General Pickup and Delivery Problem, Transport Sci, 29, pp. 17-29
Toth, P., & Vigo, D., 2002, The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, Philadelphia.
Blum, C. and Roli, A., 2008, Hybrid Metaheuristics: An Introduction, Blum, C., Aguilera, M.J.B., Roli, A., Sampels, M. (eds.): Hybrid Metaheuristics: An Emerging Approach to Optimization, Springer-Verlag, Berlin.
Armstrong, G.R., 1981, The Single and Multiple Vehicle Pickup and Delivery Problem: Exact and Heuristic Algorithms, University of Tennessee, Knoxville.
Rani, F. K., 2008, Pengembangan Algoritma Heuristik untuk Penyelesaian Dynamic Pick Up and Delivery Problem with Time Windows (DPDTW) Pada Penyedia Jasa City – Courier, Skripsi, Fakultas Teknik Industri ITS, Surabaya.
Doerner, K., Hartl, R., Reimann, M., 2000, Ant colony optimization applied to the pickup and delivery problem, SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, Vienna.
Firmansyah, A., 2011, Algoritma Improved Ant Colony System untuk Menyelesaikan Dynamic Pick-Up and Delivery Problem with Time Windows Pada Penyedia Layanan Kurir Dalam Kota, Skripsi, Fakultas Teknik Industri ITS, Surabaya.
Gamayanti, N., 2009, Pengembangan Algoritma Heuristik Ant Colony System untuk Permasalahan Dynamic Vehicle Routing Problem dengan Time Window (DVRPTW) pada Proses Konsolidasi Penyedia Jasa Inter-City Courier, Thesis, Fakultas Teknik Industri ITS, Surabaya.
Saaty, T.L., & Vargas, L.G., 2012, Models, Methods, Concepts & Applications of the Analytic Hierarchy Process, 2nd ed. Springer, New York.
Cavar, I., Gold, H., & Caric, T., 2005, Assessment of Heuristic Algorithms for Solving Real Capacitated Vehicle Routing Problems by Analytic Hierarchy Process, Transportation Research Board, San Francisco.
Dorigo, M., & Stützle, T., 2004, Ant Colony Optimization, MIT Press, Cambridge.
Clarke, G. & Wright, J., 1964, Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operation Research, Vol. 12, pp. 568-581.
Dorigo, M., & Gambardella, L., 1997, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, 1(1), pp. 53-66.
DOI: https://doi.org/10.22146/ijccs.16631
Article Metrics
Abstract views : 3708
| 
views : 3168
Refbacks
- There are currently no refbacks.
Copyright (c) 2017 IJCCS - Indonesian Journal of Computing and Cybernetics Systems
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
View My Stats1