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


Ant Colony Optimization; Pickup and Delivery Problem; highest savings; crowdsourced; trip consolidation

Full Text:

PDF


References

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 : 4494 | views : 3439

Refbacks

  • There are currently no refbacks.




Copyright (c) 2017 IJCCS - Indonesian Journal of Computing and Cybernetics Systems

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.



Copyright of :
IJCCS (Indonesian Journal of Computing and Cybernetics Systems)
ISSN 1978-1520 (print); ISSN 2460-7258 (online)
is a scientific journal the results of Computing
and Cybernetics Systems
A publication of IndoCEISS.
Gedung S1 Ruang 416 FMIPA UGM, Sekip Utara, Yogyakarta 55281
Fax: +62274 555133
email:ijccs.mipa@ugm.ac.id | http://jurnal.ugm.ac.id/ijccs



View My Stats1
View My Stats2