1. College of Computer Science, Chongqing University, Chongqing 400044, China 2. Centre de Gestion Scientifigue-I3-UMR CNRS 9217, Mines ParisTech, PSL Research University, Paris 75272, France 3. Key Laboratory of Intelligent Information Processing and Control of Chongqing Municipal Institutions of Higher Education, Chongqing Three Gorges University, Chongqing 404100, China
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.
The generation time, origin and destination of a taxi ordering request
A package delivery request
The generation time, deadline, origin and destination of a package
A sub-request of package delivery request
The generation time, deadline, origin and destination of a sub-request
The extra travel distance, i.e., the detour distance
The optimized reference path
The common reference path
A package time window
A taxi time window
The origin and the destination of a trip
The distance threshold for interchange stations
The travel distance
The latest departure time of a package
The latest arriving time of a package
The average waiting time in interchange stations
The number of interchange stations in the common reference path
The remaining time of a package
The arriving time of a package at station
The average speed of the taxis in Manhattan
A binary variable indicating whether sub-request of package delivery request is delivered by taxi ordering request
The sub-request set of package delivery request with the same destination to package delivery request
The sub-request set of package delivery request with the same origin to package delivery request
The sub-request set of package delivery request with the same destination to package delivery request
The sub-request set of package delivery request with the same origin to package delivery request
The set of interchange stations package delivery request will pass by
The time when package delivery request taken by taxi ordering request arrives at the destination of its sub-request
The start time of taxi ordering request , its origin is the destination of sub-request of package delivery request
Fig.2
Dataset
Properties
Statistics
Trajectory data
# of taxis
# of trips
Road network data
# of road intersections
11,999
# of road segments
15,202
Tab.1
Dataset
# of trajectories
Training set
9,152,370
Test set
3,874,860
Tab.2
Fig.3
Fig.4
Fig.5
Fig.6
Fig.7
Fig.8
Fig.9
Fig.10
Fig.11
1
N Agatz , M Fleischmann , J Van Nunen . E-fulfillment and multichannel distribution—a review. European Journal of Operational Research, 2008, 187( 2): 339– 356
2
S Ogawara , J Chen , Q Zhang . Internet grocery business in Japan: current business models and future trends. Industrial Management & Data Systems, 2003, 103( 9): 727– 735
3
C Chen , D Zhang , X Ma , B Guo , L Wang , Y Wang , E Sha . Crowddeliver: planning city-wide package delivery paths leveraging the crowd of taxis. IEEE Transactions on Intelligent Transportation Systems, 2016, 18( 6): 1478– 1496
4
E Fatnassi , J Chaouachi , W Klibi . 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
Y Chen , D Guo , M Xu , G Tang , T Zhou , B Ren . 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
M Lindholm , S Behrends . Challenges in urban freight transport planning-a review in the Baltic Sea Region. Journal of Transport Geography, 2012, 22 : 129– 136
8
W Lerner , V Audenhove . The future of urban mobility: towards networked, multimodal cities in 2050. Public Transport International, 2012,
9
W Chen , M Mes , M Schutten . Multi-hop driver-parcel matching problem with time windows. Flexible Services and Manufacturing Journal, 2018, 30( 3): 517– 553
10
B Cohen , P Munoz . Sharing cities and sustainable consumption and production: towards an integrated framework. Journal of Cleaner Production, 2016, 134 : 87– 97
11
A Punel , A Ermagun , A Stathopoulos . Studying determinants of crowd-shipping use. Travel Behaviour and Society, 2018, 12 : 30– 40
12
H Paloheimo , M Lettenmeier , H Waris . Transport reduction by crowdsourced deliveries—a library case in Finland. Journal of Cleaner Production, 2016, 132 : 240– 251
13
N Kafle , B Zou , J Lin . Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery. Transportation Research Part B: Methodological, 2017, 99 : 62– 82
14
C Archetti , M Savelsbergh , M Speranza . The vehicle routing problem with occasional drivers. European Journal of Operational Research, 2016, 254( 2): 472– 480
15
A Arslan , N Agatz , L Kroon , R Zuidwijk . Crowdsourced delivery—a dynamic pickup and delivery problem with ad hoc drivers. Transportation Science, 2019, 53( 1): 222– 235
16
W Deng , X Guan , S Ma , S Liu . Selection of crowdsourcing formats: simultaneous contest vs sequential contest. Industrial Management & Data Systems, 2019, 119( 1): 35– 53
17
T Le , A Stathopoulos , T Van Woensel , S Ukkusuri . 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
A Ermagun , A Shamshiripour , A Stathopoulos . Performance analysis of crowd-shipping in urban and suburban areas. Transportation, 2019, 47 : 1955– 1985
19
I Pavlidou , S Papagiannidis , E Tsui . Crowdsourcing: a systematic review of the literature using text mining. Industrial Management & Data Systems, 2020, 120( 11): 2041– 2065
20
Y Chen , D Guo , M Xu , G Tang , G Cheng . Measuring maximum urban capacity of taxi-based logistics. IEEE Transactions on Intelligent Transportation Systems, 2021, 22( 10): 6449– 6459
21
A Barr , J Wohl . Exclusive: walmart may get customers to deliver packages to online buyers. Reuters-business Week, 2013,
22
G Bensinger . Amazon’s next delivery drone: you. Wall Street Journal, 2015, 265( 140): B1– B2
23
B Li , D Krushinsky , H Reijers , T Van Woensel . The share-a-ride problem: people and parcels sharing taxis. European Journal of Operational Research, 2014, 238( 1): 31– 40
24
B Li , D Krushinsky , T Van Woensel , H Reijers . The share-a-ride problem with stochastic travel times and stochastic delivery locations. Transportation Research Part C: Emerging Technologies, 2016, 67 : 95– 108
25
M Lim , J Wang , C Wang , M Tseng . A novel method for green delivery mode considering shared vehicles in the IoT environment. Industrial Management & Data Systems, 2020, 120( 9): 1733– 1757
26
G Macrina , L Pugliese , F Guerriero , G Laporte . 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
R Masson , A Trentini , F Lehuédé , N Malhéné , O Péton , H Tlahig . Optimization of a city logistics transportation system with mixed passengers and goods. EURO Journal on Transportation and Logistics, 2017, 6( 1): 81– 109
29
C Chen , S Pan , Z Wang , R Zhong . Using taxis to collect citywide E-commerce reverse flows: a crowdsourcing solution. International Journal of Production Research, 2017, 55( 7): 1833– 1844
30
C Cleophas , C Cottrill , J Ehmke , K Tierney . Collaborative urban transportation: recent advances in theory and practice. European Journal of Operational Research, 2019, 273( 3): 801– 816
31
C Chen , X Chen , Z Wang , Y Wang , D Zhang . ScenicPlanner: planning scenic travel routes leveraging heterogeneous user-generated digital footprints. Frontiers of Computer Science, 2017, 11( 1): 61– 74
32
S Guo , C Chen , J Wang , Y Liu , X Ke , Z Yu , D Zhang , D Chiu . 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
C Chen , Y Ding , Z Wang , J Zhao , B Guo , D Zhang . VTracer: when online vehicle trajectory compression meets mobile edge computing. IEEE Systems Journal, 2019, 14( 2): 1635– 1646
34
S Pan , V Giannikas , Y Han , E Grover-Silva , B Qiao . Using customerrelated data to enhance e-grocery home delivery. Industrial Management & Data Systems, 2017, 117( 9): 1917– 1933
35
J Wang , X Wang , C Li , J Wu . Deep fuzzy cognitive maps for Interpretable multivariate time series prediction. IEEE Transactions on Fuzzy Systems, 2020, 29( 9): 2647– 2660
36
J Wang , J Wu , Z Wang , F Gao , Z Xiong . Understanding urban dynamics via context-aware tensor factorization with neighboring regularization. IEEE Transactions on Knowledge and Data Engineering, 2019, 32( 11): 2269– 2283
37
J Wang , N Wu , X Lu , X Zhao , K Feng . Deep trajectory recovery with fine-grained calibration using kalman filter. IEEE Transactions on Knowledge and Data Engineering, 2019, 33( 3): 921– 934
38
D Chai , L Wang , K Chen , Q Yang . Secure federated matrix factorization. IEEE Intelligent Systems, 2020, 36( 5): 11– 20
39
S Skiena. Combinatorics and graph theory with mathematica. 2003
40
R Tarjan . Depth-first search and linear graph algorithms. Siam Journal on Computing, 1972, 1( 2): 146– 160
41
J Dötterl, R Bruns, J Dunkel, S Ossowski. 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
A Balasubramanian , B Levine , A Venkataramani . DTN routing as a resource allocation problem. ACM Sigcomm Computer Communication Review, 2007, 37( 4): 373– 384
43
Y Ko , N Vaidya . Flooding-based geocasting protocols for mobile ad hoc networks. Mobile Networks and Applications, 2002, 7( 6): 471– 480
44
L Zhang, B Yu, J Pan. 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
M Zorzi , R Rao . Geographic random forwarding (GeRaF) for ad hoc and sensor networks: energy and latency performance. IEEE Transactions on Mobile Computing, 2003, 2( 4): 349– 365
