An exact algorithm for the pickup and delivery problem with crowdsourced bids and transshipment

E. Su, Hu Qin, Jiliu Li, Kai Pan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

This paper addresses a pickup and delivery problem with crowdsourced bids and transshipment (PDPCBT) in last-mile delivery, where all requests can be satisfied by either using the own vehicle fleet or outsourcing with a small compensation to crowdshippers through transshipment facilities. The crowdshippers show their willingness to deliver by submitting bids to the e-commerce company. To minimize both the travel cost of vehicles and the compensation of crowdshippers, the routes of vehicles and the selection of bids need to be optimized simultaneously. We formulate the PDPCBT into an arc-based formulation and a route-based formulation, where the latter is strengthened by the subset row inequalities. Based on the route-based formulation, we present a branch-and-price-and-cut algorithm to solve it exactly. To deal with two possible ways of serving requests, we first decompose the corresponding pricing problem into a shortest path problem and a knapsack problem, and then tackle them in the same bi-directional labeling algorithm framework. We also discuss acceleration techniques and implementation details to speed up the performance of the overall procedure. Computational experiments are conducted on a set of classic request instances, together with a set of randomly generated bid instances. With a time limit of two hours, numerical results validate the efficiency and effectiveness of the proposed algorithm. Finally, sensitivity analysis and managerial findings are also provided on the PDPCBT.

Original languageEnglish
Article number102831
JournalTransportation Research Part B: Methodological
Volume177
DOIs
Publication statusPublished - Nov 2023

Keywords

  • Branch-and-price-and-cut
  • Crowdsourced delivery
  • Pickup and delivery
  • Transshipment facilities
  • Vehicle routing

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint

Dive into the research topics of 'An exact algorithm for the pickup and delivery problem with crowdsourced bids and transshipment'. Together they form a unique fingerprint.

Cite this