An exact single-agent task selection algorithm for the crowdsourced logistics

• Main Authors: HAN, Chung-kyun, CHENG, Shih-Fen
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2020
• Subjects: Human Computation and Crowdsourcing; Planning Algorithms; transportation; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/5175; https://ink.library.smu.edu.sg/context/sis_research/article/6178/viewcontent/Exact_Single_Agent_Task_Sel_2020_pvoa.pdf
• Institution: Singapore Management University

The trend of moving online in the retail industry has created great pressure for the logistics industry to catch up both in terms of volume and response time. On one hand, volume is fluctuating at greater magnitude, making peaks higher; on the other hand, customers are also expecting shorter response time. As a result, logistics service providers are pressured to expand and keep up with the demands. Expanding fleet capacity, however, is not sustainable as capacity built for the peak seasons would be mostly vacant during ordinary days. One promising solution is to engage crowdsourced workers, who are not employed full-time but would be willing to help with the deliveries if their schedules permit. The challenge, however, is to choose appropriate sets of tasks that would not cause too much disruption from their intended routes, while satisfying each delivery task's delivery time window requirement. In this paper, we propose a decision-support algorithm to select delivery tasks for a single crowdsourced worker that best fit his/her upcoming route both in terms of additional travel time and the time window requirements at all stops along his/her route, while at the same time satisfies tasks' delivery time windows. Our major contributions are in the formulation of the problem and the design of an efficient exact algorithm based on the branch-and-cut approach. The major innovation we introduce is the efficient generation of promising valid inequalities via our separation heuristics. In all numerical instances we study, our approach manages to reach optimality yet with much fewer computational resource requirement than the plain integer linear programming formulation. The greedy heuristic, while efficient in time, only achieves around 40-60% of the optimum in all cases. To illustrate how our solver could help in advancing the sustainability objective, we also quantify the reduction in the carbon footprint.