Reinforcement learning-based algorithm for the dynamic multi-depot crowdsourced delivery problem

doi:10.1016/j.eswa.2025.127818

Reinforcement learning-based algorithm for the dynamic multi-depot crowdsourced delivery problem

2025-07-01

0

PRE

AI

Mohamed Wahab Mohamed Ismail

Z

Zhang Zong-cheng

DOI：10.1016/j.eswa.2025.127818

Original

Original request for help

Save

Abstract

En 中文

The industry is increasingly interested in crowdsourced solutions, where ad hoc drivers offer services through an online crowdsourcing platform (OCP). This study examines a dynamic environment where the OCP receives realtime delivery tasks and assigns them to these ad hoc drivers. The drivers collect items from multiple depots and deliver them to customers. The arrival of crowdsourced vehicles is also dynamic. This scenario introduces a new variation of the vehicle routing problem, the dynamic multi-depot crowdsourced delivery problem (DMDCDP). It involves grouping multiple orders into batches, assigning each order batch to a crowdsourced vehicle, determining the appropriate depot for each vehicle to collect the required order batch from, and finding the optimal routes for the crowdsourced vehicles. To maximize the total gain of the OCP over the entire planning horizon, this study incorporates anticipated spatiotemporal characteristics of future orders and vehicles into the current decision-making process for the DMDCDP. That is achieved by developing a Markov decision process (MDP) model and proposing a reinforcement learning framework-based hybrid algorithm, NSTDKM. It incorporates an improved adaptive large neighborhood search (IALNS) technique for batching orders and allocating them to depots and the temporal-difference-based Kuhn-Munkres technique for assigning order batches to vehicles and planning routes. A total of 7740 sets of experiments are conducted to examine the performance of the NSTDKM algorithm. For all instances, the NSTDKM consistently outperforms the two existing algorithms and improves the overall gain of the OCP. On average, the NSTDKM exhibits an improvement of 35.7% and 21.7% compared to those two algorithms. Ablation experiments further validate the effectiveness of the NSTDKM, as it achieved the best overall gain of the OCP for 93% of instances, with an average improvement of 13.17%, 9.2%, and 2.7% compared to the three comparative algorithms. The value tables, trained offline by the NSTDKM, also demonstrate strong generalization for new instances with varying temporal and spatial distributions and demand distributions. Furthermore, the NSTDKM performs well under different decision-making frequencies.

Keywords:

Dynamic crowdsourced delivery

Multiple depots

Order batching

Anticipated future gain

Reinforcement learning

Reinforcement learning-based algorithm for the dynamic multi-depot crowdsourced delivery problem

Abstract

Journal

Organization

Cited Papers