Kitle destekli dağıtım servis ağı tasarımı problemi

Öz

Şehir içi dağıtım faaliyetlerinin artan maliyetleri ve neden olduğu sorunlar (trafik, çevre kirliliği, gürültü, araç kazaları, vb.) hakkında artan kaygılar, bu alanda yenilikçi yaklaşımlara olan ihtiyacı giderek artırmaktadır. Ön plana çıkan söz konusu yaklaşımlardan birisi de Kitle destekli dağıtım (KDD) modelidir. Yolcu ve paket taşımacılığını bütünleştirerek atıl araç kapasitelerinin faydalı bir şekilde kullanılmasını amaçlayan bu modelde, kişilerin küçük ekonomik kazançlar sağlamak ve/veya dağıtım faaliyetlerinin çevreye verdiği zararları azaltılmasına katkı sunmak amacıyla kendi seyahatleri sırasında yolları üzerindeki servis noktaları arasında paket taşımacılığı yapması öngörülmektedir. Bu çalışmada, KDD faaliyetlerinin etkin bir şekilde yürütebilmesi için gerekli olan servis noktalarının/paket otomatlarının şehrin hangi noktalarına hangi kapasiteler ile kurulması gerektiğini belirlemek için çözülmesi gereken stratejik seviye “KDD servis ağı tasarımı” problemini literatüre tanıtıyoruz. İki seviyeli, senaryo tabanlı belirsiz bir tamsayılı program olarak modellediğimiz problemin çözümü için etkin bir Benders Ayrıştırma algoritması önermekteyiz. Gerçekleştirdiğimiz geniş kapsamlı hesapsal çalışmalar geliştirdiğimiz çözüm yönteminin etkinliğini ortaya koymakta, önemli yönetimsel çıkarımlar sunmaktadır. Elde ettiğimiz sonuçlar, hızlı paket taşımacılığı gibi oldukça zorlu ve maliyetli (ekonomik ve çevresel) bir dağıtım faaliyeti için iyi tasarlanmış bir KDD modelinin önemli kazanımlar sağlayabileceğini göstermektedir. Nispeten küçük sayıda (çalıştığımız problem örneklerinde en fazla 60 adet) servis noktaları ile dağıtımların önemli bir kısmının (çalıştığımız problem örneklerinde %56’ya kadar) “kitle” tarafından yapıldığı etkin bir KDD sisteminin teşkil edilebileceğini gösteren bu sonuçlar, önerilen yenilikçi yaklaşımın uygulanabilirliği konusunda önemli ipuçları vermektedir.

Anahtar Kelimeler

• Şehir içi lojistiği
• Kitle destekli dağıtım
• Belirsizlikte eniyileme
• Benders ayrıştırma

Crowd-shipping service network design problem

Abstract

With the rising concerns over the increasing costs and negative externalities of city logistics, the need for innovative approaches to come up with low-cost and environmentally friendly distribution systems is on the rise. One such innovative approach is crowd-shipping (CS). In this model, which aims to combine packet and passenger transfers to utilize redundant transportation capacity, the individuals who want to earn small compensations and/or help the environment are employed to carry out package transfers between service points on the paths of their already planned trips. In this study, we introduce the strategic level CS network design problem, which needs to be solved to determine the locations and the capacities of the service points in the urban area to establish an efficient CS delivery system. We propose a novel Benders Decomposition algorithm to solve this challenging problem that we model as a scenario-based two-stage stochastic integer program. The results of our comprehensive numerical experiments attest to the efficacy of the approach to solve practical size problem instances and provide significant managerial insights, showing that such a well-designed CS network can provide savings (in terms of both economic and environmental costs), even in the case of express package transfers with very stringent delivery lead time restrictions. In particular, our results show that by carefully choosing the locations and the capacities of the service points, it is possible to carry out a significant portion of express deliveries with the crowd provided delivery capacity (up to 56% in our experiments) without deploying a very large number of them (less than 60 in all our experiment) in the region, indicating the strong potential and applicability of the CS delivery systems in real world delivery operations.

Keywords

• City logistics
• Crowd-Shipping
• Stochastic programming
• Benders decomposition

References

1. [1] Dolan S. “The challenges of Last Mile Delivery Logistics & the Technology Solutions Cutting Costs”. https://www.businessinsider.com/last-mile-deliveryshipping-explained?r=US&IR=T (08.24.2020).
2. [2] Marcucci E, Michela LP, Carrocci CH, Gatta V, Pieralice E. “Connected shared mobility for passengers and freight: Investigating the potential of crowdshipping in urban areas”. IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), Napoli, Italy, 16-28 June 2017.
3. [3] Yıldız B. “Express package routing problem with occasional couriers and transshipment locations”. Transportation Research Part C: Emerging Technologies, 2021. https://doi.org/10.1016/j.trc.2021.102994
4. [4] Savelsbergh M, Van Woensel T. “50th anniversary invited article-city logistics: Challenges and opportunities”. Transportation Science, 50(2), 579-590, 2016.
5. [5] Yıldız B, Savelsbergh M. “Service and capacity planning in crowd-sourced delivery”. Transportation Research Part C: Emerging Technologies, 100, 177-199, 2019.
6. [6] Raviv T, Tenzer EZ. “Crowd-Shipping of small parcels in a physical internet”. https://www.researchgate.net/ publication/326319843_Crowdshipping_of_small_parcels _in_a_physical_internet (01.06.2018).
7. [7] Le TV, Ukkusuri SV. “Crowd-Shipping services for last mile delivery: Analysis from American survey data”. Transportation Research Interdisciplinary Perspectives, 2019, https://doi.org/10.1016/j.trip.2019.100008
8. [8] Rai HB, Verlinde S, Merckx J, Macharis C. “Crowd logistics: an opportunity for more sustainable urban freight transport”. European Transport Research Review, 2017. https://doi.org/10.1007/s12544-017-0256-6

9. [9] Punel A, Stathopoulos A. “Modeling the acceptability of crowdsourced goods deliveries: Role of context and experience effects”. Transportation Research Part E: Logistics and Transportation Review, 105, 18-38, 2017.
10. [10] Archetti C, Savelsbergh M, Speranza MG. “The vehicle routing problem with occasional drivers”. European Journal of Operational Research, 254(2), 472-480, 2016.
11. [11] Macrina G, Pugliese LDP, Guerriero F, Laganà D. “The vehicle routing problem with occasional drivers and time windows”. International Conference on Optimization and Decision Science, Serento, Italy, 4-7 September 2017.
12. [12] Arslan AM, Agatz N, Kroon L, Zuidwijk R. “Crowdsourced delivery-A dynamic pickup and delivery problem with ad hoc drivers”. Transportation Science, 53(1), 222-235, 2019.
13. [13] Macrina G, Pugliese LDP, Guerriero F, Laporte G. “Crowdshipping with time windows and transshipment nodes”. Computers & Operations Research, 2020. https://doi.org/10.1016/j.cor.2019.104806
14. [14] Chen C, Zhang D, Ma X, Guo B, Wang L, Wang Y, Sha E. “Crowddeliver: Planning city-wide package delivery paths leveraging the crowd of taxis”. IEEE Transactions on Intelligent Transportation Systems, 18(6), 1478-1496, 2016.
15. [15] Chen C, Pan S, Wang Z, Zhong RY. “Using taxis to collect citywide E-commerce reverse flows: a crowdsourcing solution”. International Journal of Production Research, 55(7), 1833-1844, 2017.
16. [16] Chen W, Mes M, Schutten M. “Multi-hop driver-parcel matching problem with time windows”. Flexible services and manufacturing journal, 30(3), 517-553, 2018.
17. [17] Farahani RZ, Miandoabchi E, Szeto WY, Rashidi H. “A review of urban transportation network design problems”. European Journal of Operational Research, 229(2), 281-302, 2013.
18. [18] Başkan Ö, Ceylan H. “Ulaşım ağ tasarımı problemlerinin çözümünde diferansiyel gelişim algoritması tabanlı çözüm yaklaşımları”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 20(9), 324-331, 2014.
19. [19] Tekin G, Turgut Y, Yılmaz A, Arslan Ş, Çamcı A. “Deprem sonrası planlamaya yönelik lojistik ağ tasarımı: Ümraniye bölgesinde farklı deprem senaryoları için bir uygulama”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 25(1), 98-105, 2019.
20. [20] Yılmaz D, Gerçek H. “Analitik hiyerarşi yöntemi ile İstanbul’da bütünleşik bisiklet ağı kümelerinin önceliklendirilmesi”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 20(6), 215-224, 2014.
21. [21] Koç Ç, Özceylan E, Kesen SE, Çil ZA, Mete S. “İleri tedarik zinciri ağ tasarımı problemi: sezgisel yaklaşımlar”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 24(4), 749-763, 2018.
22. [22] Bayram V, Yaman H. “Shelter location and evacuation route assignment under uncertainty: A benders decomposition approach”. Transportation Science, 52(2), 416-436, 2018.
23. [23] Yıldız B, Olcaytu E, Şen A. “The urban recharging infrastructure design problem with stochastic demands and capacitated charging stations”. Transportation Research Part B: Methodological, 119, 22-44, 2019.
24. [24] Geoffrion AM. “Generalized Benders decomposition”. Journal of Optimization Theory and Applications, 10(4), 237-260, 1972.
25. [25] Van Slyke RM, Wets R. “L-shaped linear programs with applications to optimal control and stochastic programming”. SIAM Journal on Applied Mathematics, 17(4), 638-663, 1969.
26. [26] Bayram V, Yaman H. “Shelter location and evacuation route assignment under uncertainty: A benders decomposition approach”. Transportation Science, 52(2), 416-436, 2018.
27. [27] Orhan İ, Kapanoğlu M, Karakoç TH. “Havayolu operasyonlarında planlama ve çizelgeleme”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 16(2), 181-191, 2010
28. [28] Chu Y, Xia Q. “Generating benders cuts for a general class of integer programming problems”. International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, Berlin, Germany, 10-14 April 2004.
29. [29] Subulan K. “An interval programming based approach for fully uncertain resource constrained project scheduling problem considering project manager's attitude toward risk”. Pamukkale University Journal of Engineering Sciences, 25(4), 481-497, 2019.
30. [30] Dietmann K. Crowdshipping the Last-Mile Delivery-An Empirical Investigation Into the Crowd's Willingness to Participate as Crowdshipping Drivers. MSc Université de Liège, Liège, Belgium, 2020.
31. [31] Yıldız B, Arslan O, Karaşan O. “A branch and price approach for routing and refueling station location model”. European Journal of Operational Research, 248(3), 815-826, 2016.