Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

1-2020

Abstract

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.

Keywords

Human Computation and Crowdsourcing, Planning Algorithms, transportation

Discipline

Operations Research, Systems Engineering and Industrial Engineering | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 29th International Joint Conference on Artificial Intelligence IJCAI 2020: Virtual, Yokohama, Japan, January 7-15

First Page

4352

Last Page

4358

ISBN

9780999241165

Identifier

10.24963/ijcai.2020/600

Publisher

IJCAI

City or Country

Menlo Park, CA

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.24963/ijcai.2020/600

Download

Share

COinS