Paper Info
Title
Online crowdsourced truck delivery using historical information
Abstract
Various crowdsourced logistics platforms are forming rapidly along with the booming mobile Internet. Motivated by modern crowdsourced truck logistics platforms, we introduce the online crowdsourced truck delivery (OCTD) problem and reformulate it as the online bipartite hyper-matching problem. We then explore the possibility of accommodating historical information to design efficient online algorithms to serve online orders. To the best of our knowledge, it is the first work on incorporating historical information to solve the online bipartite hyper-matching problem. Depending on whether orders can be partially served, we investigate two practical situations, i.e. separable and inseparable cases. For the inseparable case, we propose a randomized online algorithm, named HYPER-MATCHING , whose competitive ratio is a non-decreasing function of the amount of historical information. For the separable case, we modify HYPER-MATCHING to present another randomized online algorithm, named SEPARABLE-HYPER-MATCHING . It is worth noting that the competitive ratios of HYPER-MATCHING and SEPARABLE-HYPER-MATCHING either beat or match the current best online algorithms when no historical information is considered. We then present four computationally efficient heuristic algorithms, including a greedy variant and a batch processing variant for each of the inseparable and separable cases. We perform a sequence of experiments using synthetic and real-world datasets, with an emphasis on the influence that historical information has on algorithm performance. The experiment results demonstrate the effectiveness of our algorithms and particularly the positive influence of historical information on our algorithms.(c) 2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2022
10.1016/j.ejor.2021.10.036
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Keywords
DocType
Volume
Transportation, Online crowdsourced truck delivery, Online bipartite hyper-matching, Random order model, Historical information
Journal
301
Issue
ISSN
Citations 
2
0377-2217
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Huili Zhang1437.02
Kelin Luo201.35
Yao Xu303.72
Yinfeng Xu41636108.18
Weitian Tong57314.59