IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v301y2022i2p486-501.html
   My bibliography  Save this article

Online crowdsourced truck delivery using historical information

Author

Listed:
  • Zhang, Huili
  • Luo, Kelin
  • Xu, Yao
  • Xu, Yinfeng
  • Tong, Weitian

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-Matchingeither 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.

Suggested Citation

  • Zhang, Huili & Luo, Kelin & Xu, Yao & Xu, Yinfeng & Tong, Weitian, 2022. "Online crowdsourced truck delivery using historical information," European Journal of Operational Research, Elsevier, vol. 301(2), pages 486-501.
    • Handle: RePEc:eee:ejores:v:301:y:2022:i:2:p:486-501
    DOI: 10.1016/j.ejor.2021.10.036
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721008869
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.10.036?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Behrend, Moritz & Meisel, Frank & Fagerholt, Kjetil & Andersson, Henrik, 2021. "A multi-period analysis of the integrated item-sharing and crowdshipping problem," European Journal of Operational Research, Elsevier, vol. 292(2), pages 483-499.
    2. Lafkihi, Mariam & Pan, Shenle & Ballot, Eric, 2019. "Freight transportation service procurement: A literature review and future research opportunities in omnichannel E-commerce," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 125(C), pages 348-365.
    3. Intissar Ben Othmane & Monia Rekik & Sehl Mellouli, 2019. "A profit-maximization heuristic for combinatorial bid construction with pre-existing network restrictions," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 70(12), pages 2097-2111, December.
    4. Hammami, Farouk & Rekik, Monia & Coelho, Leandro C., 2019. "Exact and heuristic solution approaches for the bid construction problem in transportation procurement auctions with a heterogeneous fleet," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 150-177.
    5. Triki, Chefi & Oprea, Simona & Beraldi, Patriza & Crainic, Teodor Gabriel, 2014. "The stochastic bid generation problem in combinatorial transportation auctions," European Journal of Operational Research, Elsevier, vol. 236(3), pages 991-999.
    6. Song, Jiongjiong & Regan, Amelia, 2005. "Approximation algorithms for the bid construction problem in combinatorial auctions for the procurement of freight transportation contracts," Transportation Research Part B: Methodological, Elsevier, vol. 39(10), pages 914-933, December.
    7. Minghui Lai & Weili Xue & Qian Hu, 2019. "An Ascending Auction for Freight Forwarder Collaboration in Capacity Sharing," Transportation Science, INFORMS, vol. 53(4), pages 1175-1195, July.
    8. Lee, Chi-Guhn & Kwon, Roy H. & Ma, Zhong, 2007. "A carrier's optimal bid generation problem in combinatorial auctions for transportation procurement," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 43(2), pages 173-191, March.
    9. Hou, Liwen & Li, Dong & Zhang, Dali, 2018. "Ride-matching and routing optimisation: Models and a large neighbourhood search heuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 143-162.
    10. Alnaggar, Aliaa & Gzara, Fatma & Bookbinder, James H., 2021. "Crowdsourced delivery: A review of platforms and academic literature," Omega, Elsevier, vol. 98(C).
    11. Amy Cohn & Sarah Root & Alex Wang & Douglas Mohr, 2007. "Integration of the Load-Matching and Routing Problem with Equipment Balancing for Small Package Carriers," Transportation Science, INFORMS, vol. 41(2), pages 238-252, May.
    12. Ozlem Ergun & Gultekin Kuyzu & Martin Savelsbergh, 2007. "Reducing Truckload Transportation Costs Through Collaboration," Transportation Science, INFORMS, vol. 41(2), pages 206-221, May.
    13. Mariam Lafkihi & Shenle Pan & Eric Ballot, 2019. "Freight transportation service procurement: A literature review and future research opportunities in omnichannel E-commerce," Post-Print hal-02086154, HAL.
    14. Will Ma & David Simchi-Levi, 2020. "Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios," Operations Research, INFORMS, vol. 68(6), pages 1787-1803, November.
    15. Chiwei Yan & Helin Zhu & Nikita Korolko & Dawn Woodard, 2020. "Dynamic pricing and matching in ride‐hailing platforms," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(8), pages 705-724, December.
    16. Le, Tho V. & Ukkusuri, Satish V. & Xue, Jiawei & Van Woensel, Tom, 2021. "Designing pricing and compensation schemes by integrating matching and routing models for crowd-shipping systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    17. Okan Örsan Özener & Özlem Ergun & Martin Savelsbergh, 2011. "Lane-Exchange Mechanisms for Truckload Carrier Collaboration," Transportation Science, INFORMS, vol. 45(1), pages 1-17, February.
    18. Boysen, Nils & Emde, Simon & Schwerdfeger, Stefan, 2022. "Crowdshipping by employees of distribution centers: Optimization approaches for matching supply and demand," European Journal of Operational Research, Elsevier, vol. 296(2), pages 539-556.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hammami, Farouk & Rekik, Monia & Coelho, Leandro C., 2021. "Exact and hybrid heuristic methods to solve the combinatorial bid construction problem with stochastic prices in truckload transportation services procurement auctions," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 204-229.
    2. Hammami, Farouk & Rekik, Monia & Coelho, Leandro C., 2019. "Exact and heuristic solution approaches for the bid construction problem in transportation procurement auctions with a heterogeneous fleet," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 150-177.
    3. Martin W.P Savelsbergh & Marlin W. Ulmer, 2022. "Challenges and opportunities in crowdsourced delivery planning and operations," 4OR, Springer, vol. 20(1), pages 1-21, March.
    4. Kuyzu, Gültekin & Akyol, Çağla Gül & Ergun, Özlem & Savelsbergh, Martin, 2015. "Bid price optimization for truckload carriers in simultaneous transportation procurement auctions," Transportation Research Part B: Methodological, Elsevier, vol. 73(C), pages 34-58.
    5. Wang, Haibo & Alidaee, Bahram, 2023. "White-glove service delivery: A quantitative analysis," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    6. Yu, Hao & Huang, Min & Chao, Xiuli & Yue, Xiaohang, 2022. "Truthful multi-attribute multi-unit double auctions for B2B e-commerce logistics service transactions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    7. Lafkihi, Mariam & Pan, Shenle & Ballot, Eric, 2019. "Freight transportation service procurement: A literature review and future research opportunities in omnichannel E-commerce," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 125(C), pages 348-365.
    8. He, Shan & Dai, Ying & Ma, Zu-Jun, 2023. "To offer or not to offer? The optimal value-insured strategy for crowdsourced delivery platforms," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 173(C).
    9. Gansterer, Margaretha & Hartl, Richard F. & Sörensen, Kenneth, 2020. "Pushing frontiers in auction-based transport collaborations," Omega, Elsevier, vol. 94(C).
    10. Richard Li-Yang Chen & Shervin AhmadBeygi & Amy Cohn & Damian R. Beil & Amitabh Sinha, 2009. "Solving Truckload Procurement Auctions Over an Exponential Number of Bundles," Transportation Science, INFORMS, vol. 43(4), pages 493-510, November.
    11. Wang, Junjin & Liu, Jiaguo & Wang, Fan & Yue, Xiaohang, 2021. "Blockchain technology for port logistics capability: Exclusive or sharing," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 347-392.
    12. Mesa-Arango, Rodrigo & Ukkusuri, Satish V., 2015. "Demand clustering in freight logistics networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 81(C), pages 36-51.
    13. Mancini, Simona & Gansterer, Margaretha, 2022. "Bundle generation for last-mile delivery with occasional drivers," Omega, Elsevier, vol. 108(C).
    14. Zolfagharinia, Hossein & Haughton, Michael, 2018. "The importance of considering non-linear layover and delay costs for local truckers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 331-355.
    15. R. Jothi Basu & Nachiappan Subramanian & Angappa Gunasekaran & P. L. K. Palaniappan, 2017. "Influence of non-price and environmental sustainability factors on truckload procurement process," Annals of Operations Research, Springer, vol. 250(2), pages 363-388, March.
    16. Zhang, Bo & Yao, Tao & Friesz, Terry L. & Sun, Yuqi, 2015. "A tractable two-stage robust winner determination model for truckload service procurement via combinatorial auctions," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 16-31.
    17. Xu, Su Xiu & Huang, George Q., 2014. "Efficient auctions for distributed transportation procurement," Transportation Research Part B: Methodological, Elsevier, vol. 65(C), pages 47-64.
    18. Li, Yuan & Chen, Haoxun & Prins, Christian, 2016. "Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests," European Journal of Operational Research, Elsevier, vol. 252(1), pages 27-38.
    19. Kong, Xiang T.R. & Kang, Kai & Zhong, Ray Y. & Luo, Hao & Xu, Su Xiu, 2021. "Cyber physical system-enabled on-demand logistics trading," International Journal of Production Economics, Elsevier, vol. 233(C).
    20. Nathalie Touratier-Muller & Jacques Jaussaud, 2021. "Development of Road Freight Transport Indicators Focused on Sustainability to Assist Shippers: An Analysis Conducted in France through the FRET 21 Programme," Sustainability, MDPI, vol. 13(17), pages 1-17, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:301:y:2022:i:2:p:486-501. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.