Citywide package deliveries via crowdshipping: minimizing the efforts from crowdsourcers

Abstract

Most current crowdsourced logistics aim to minimize systems cost and maximize delivery capacity, but the efforts of crowdsourcers such as drivers are almost ignored. In the delivery process, drivers usually need to take long-distance detours in hitchhiking rides based package deliveries. In this paper, we propose an approach that integrates offline trajectory data mining and online route-and-schedule optimization in the hitchhiking ride scenario to find optimal delivery routes for packages and drivers. Specifically, we propose a two-phase framework for the delivery route planning and scheduling. In the first phase, the historical trajectory data are mined offline to build the package transport network. In the second phase, we model the delivery route planning and package-taxi matching as an integer linear programming problem and solve it with the Gurobi optimizer. After that, taxis are scheduled to deliver packages with optimal delivery paths via a newly designed scheduling strategy. We evaluate our approach with the real-world datasets; the results show that our proposed approach can complete citywide package deliveries with a high success rate and low extra efforts of taxi drivers.

Graphical abstract

Keywords

crowdshipping / hitchhiking rides / dynamic delivery optimization / package delivery / taxi scheduling

References

[1] Agatz N , Fleischmann M , Van Nunen J . E-fulfillment and multichannel distribution—a review. European Journal of Operational Research, 2008, 187( 2): 339– 356

[2] Ogawara S , Chen J , Zhang Q . Internet grocery business in Japan: current business models and future trends. Industrial Management & Data Systems, 2003, 103( 9): 727– 735

[3] 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, 2016, 18( 6): 1478– 1496

[4] Fatnassi E , Chaouachi J , Klibi W . Planning and operating a shared goods and passengers on-demand rapid transit system for sustainable city-logistics. Transportation Research Part B: Methodological, 2015, 81 : 440– 460

[5] Chen Y , Guo D , Xu M , Tang G , Zhou T , Ren B . PPtaxi: non-stop package delivery via multi-hop ridesharing. IEEE Transactions on Mobile Computing, 2019, 19( 11): 2684– 2698

[6] Chen C, Yang S, Wang Y, Guo B, Zhang D. CrowdExpress: a probabilistic framework for on-time crowdsourced package deliveries. IEEE Transactions on Big Data, 2020, DOI: 10.1109/TBDATA.2020.2991152

[7] Lindholm M , Behrends S . Challenges in urban freight transport planning-a review in the Baltic Sea Region. Journal of Transport Geography, 2012, 22 : 129– 136

[8] Lerner W , Audenhove V . The future of urban mobility: towards networked, multimodal cities in 2050. Public Transport International, 2012,

[9] Chen W , Mes M , Schutten M . Multi-hop driver-parcel matching problem with time windows. Flexible Services and Manufacturing Journal, 2018, 30( 3): 517– 553

[10] Cohen B , Munoz P . Sharing cities and sustainable consumption and production: towards an integrated framework. Journal of Cleaner Production, 2016, 134 : 87– 97

[11] Punel A , Ermagun A , Stathopoulos A . Studying determinants of crowd-shipping use. Travel Behaviour and Society, 2018, 12 : 30– 40

[12] Paloheimo H , Lettenmeier M , Waris H . Transport reduction by crowdsourced deliveries—a library case in Finland. Journal of Cleaner Production, 2016, 132 : 240– 251

[13] Kafle N , Zou B , Lin J . Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery. Transportation Research Part B: Methodological, 2017, 99 : 62– 82

[14] Archetti C , Savelsbergh M , Speranza M . The vehicle routing problem with occasional drivers. European Journal of Operational Research, 2016, 254( 2): 472– 480

[15] Arslan A , Agatz N , Kroon L , Zuidwijk R . Crowdsourced delivery—a dynamic pickup and delivery problem with ad hoc drivers. Transportation Science, 2019, 53( 1): 222– 235

[16] Deng W , Guan X , Ma S , Liu S . Selection of crowdsourcing formats: simultaneous contest vs sequential contest. Industrial Management & Data Systems, 2019, 119( 1): 35– 53

[17] Le T , Stathopoulos A , Van Woensel T , Ukkusuri S . Supply, demand, operations, and management of crowd-shipping services: a review and empirical evidence. Transportation Research Part C: Emerging Technologies, 2019, 103 : 83– 103

[18] Ermagun A , Shamshiripour A , Stathopoulos A . Performance analysis of crowd-shipping in urban and suburban areas. Transportation, 2019, 47 : 1955– 1985

[19] Pavlidou I , Papagiannidis S , Tsui E . Crowdsourcing: a systematic review of the literature using text mining. Industrial Management & Data Systems, 2020, 120( 11): 2041– 2065

[20] Chen Y , Guo D , Xu M , Tang G , Cheng G . Measuring maximum urban capacity of taxi-based logistics. IEEE Transactions on Intelligent Transportation Systems, 2021, 22( 10): 6449– 6459

[21] Barr A , Wohl J . Exclusive: walmart may get customers to deliver packages to online buyers. Reuters-business Week, 2013,

[22] Bensinger G . Amazon’s next delivery drone: you. Wall Street Journal, 2015, 265( 140): B1– B2

[23] Li B , Krushinsky D , Reijers H , Van Woensel T . The share-a-ride problem: people and parcels sharing taxis. European Journal of Operational Research, 2014, 238( 1): 31– 40

[24] Li B , Krushinsky D , Van Woensel T , Reijers H . The share-a-ride problem with stochastic travel times and stochastic delivery locations. Transportation Research Part C: Emerging Technologies, 2016, 67 : 95– 108

[25] Lim M , Wang J , Wang C , Tseng M . A novel method for green delivery mode considering shared vehicles in the IoT environment. Industrial Management & Data Systems, 2020, 120( 9): 1733– 1757

[26] Macrina G , Pugliese L , Guerriero F , Laporte G . Crowd-shipping with time windows and transshipment nodes. Computers & Operations Research, 2020, 113 : 104806–

[27] Ghilas V, Demir E, Van Woensel T. Integrating passenger and freight transportation: model formulation and insights. In: Proceedings of the 2013 Beta Working Papers; Technische Universiteit Eindhoven: Eindhoven, The Netherlands. 2013, 1–23

[28] Masson R , Trentini A , Lehuédé F , Malhéné N , Péton O , Tlahig H . Optimization of a city logistics transportation system with mixed passengers and goods. EURO Journal on Transportation and Logistics, 2017, 6( 1): 81– 109

[29] Chen C , Pan S , Wang Z , Zhong R . Using taxis to collect citywide E-commerce reverse flows: a crowdsourcing solution. International Journal of Production Research, 2017, 55( 7): 1833– 1844

[30] Cleophas C , Cottrill C , Ehmke J , Tierney K . Collaborative urban transportation: recent advances in theory and practice. European Journal of Operational Research, 2019, 273( 3): 801– 816

[31] Chen C , Chen X , Wang Z , Wang Y , Zhang D . ScenicPlanner: planning scenic travel routes leveraging heterogeneous user-generated digital footprints. Frontiers of Computer Science, 2017, 11( 1): 61– 74

[32] Guo S , Chen C , Wang J , Liu Y , Ke X , Yu Z , Zhang D , Chiu D . Rodrevenue: seeking strategies analysis and revenue prediction in ride-ondemand service using multi-source urban data. IEEE Transactions on Mobile Computing, 2019, 19( 9): 2202– 2220

[33] Chen C , Ding Y , Wang Z , Zhao J , Guo B , Zhang D . VTracer: when online vehicle trajectory compression meets mobile edge computing. IEEE Systems Journal, 2019, 14( 2): 1635– 1646

[34] Pan S , Giannikas V , Han Y , Grover-Silva E , Qiao B . Using customerrelated data to enhance e-grocery home delivery. Industrial Management & Data Systems, 2017, 117( 9): 1917– 1933

[35] Wang J , Wang X , Li C , Wu J . Deep fuzzy cognitive maps for Interpretable multivariate time series prediction. IEEE Transactions on Fuzzy Systems, 2020, 29( 9): 2647– 2660

[36] Wang J , Wu J , Wang Z , Gao F , Xiong Z . Understanding urban dynamics via context-aware tensor factorization with neighboring regularization. IEEE Transactions on Knowledge and Data Engineering, 2019, 32( 11): 2269– 2283

[37] Wang J , Wu N , Lu X , Zhao X , Feng K . Deep trajectory recovery with fine-grained calibration using kalman filter. IEEE Transactions on Knowledge and Data Engineering, 2019, 33( 3): 921– 934

[38] Chai D , Wang L , Chen K , Yang Q . Secure federated matrix factorization. IEEE Intelligent Systems, 2020, 36( 5): 11– 20

[39] Skiena S. Combinatorics and graph theory with mathematica. 2003

[40] Tarjan R . Depth-first search and linear graph algorithms. Siam Journal on Computing, 1972, 1( 2): 146– 160

[41] Dötterl J, Bruns R, Dunkel J, Ossowski S. On-time delivery in crowdshipping systems: an agent-based approach using streaming data. In: Frontiers in Artificial Intelligence and Applications. IOS Press, 2020, 51– 58

[42] Balasubramanian A , Levine B , Venkataramani A . DTN routing as a resource allocation problem. ACM Sigcomm Computer Communication Review, 2007, 37( 4): 373– 384

[43] Ko Y , Vaidya N . Flooding-based geocasting protocols for mobile ad hoc networks. Mobile Networks and Applications, 2002, 7( 6): 471– 480

[44] Zhang L, Yu B, Pan J. GeoMob: a mobility-aware geocast scheme in metropolitans via taxicabs and buses. In: Proceedings of IEEE INFOCOM 2014-IEEE Conference on Computer Communications. 2014, 2014−1787

[45] Zorzi M , Rao R . Geographic random forwarding (GeRaF) for ad hoc and sensor networks: energy and latency performance. IEEE Transactions on Mobile Computing, 2003, 2( 4): 349– 365

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Grant No. 61872050), in part by the Chongqing Basic and Frontier Research Program (cstc2018jcyjAX0551), Foundation of Chongqing Municipal Key Laboratory of Institutions of Higher Education ([2017]3), Foundation of Chongqing Development and Reform Commission (2017[1007]), and Foundation of Chongqing Three Gorges University. Sijing Cheng and Chao Chen contributed equally to this work. Wei Zhang is the corresponding authors for this paper.

RIGHTS & PERMISSIONS

2022 Higher Education Press