.png){kind=icon}
返回
Reinforcement Learning for Solving Multiple Vehicle Routing Problem with Time Window
.png){kind=icon}
OA
AI
DOI：10.1145/3625232.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Vehicle routing problem with time window (VRPTW) is of great importance for a wide spectrum of services and real-life applications, such as online take-out and car-hailing platforms. A promising method should generate high-qualified solutions within limited inference time, and there are three major challenges: (a) directly optimizing the goal with several practical constraints; (b) efficiently handling individual time-window limits; and (c) modeling the cooperation among the vehicle fleet. In this article, we present an end-to-end reinforcement learning framework to solve VRPTW. First, we propose an agent model that encodes constraints into features as the input and conducts harsh policy on the output when generating deterministic results. Second, we design a time penalty augmented reward to model the time-window limits during gradient propagation. Third, we design a task handler to enable the cooperation among different vehicles. We perform extensive experiments on two real-world datasets and one public benchmark dataset. Results demonstrate that our solution improves the performance by up to 11.7% compared to other RL baselines and could generate solutions for instances within seconds, while existing heuristic baselines take for minutes as well as maintain the quality of solutions. Moreover, our solution is thoroughly analyzed with meaningful implications due to the real-time response ability.
Keyword:
Vehicle routing problem with time window
reinforcement learning
期刊
IF:
6.6
论文数:
1.5K
被引数:
6.2K
机构
引用论文
.png){kind=icon}
Blacks’ Death Rate Due to Circulatory Diseases Is Positively Related to Whites’ Explicit Racial Bias黑人因循环系统疾病导致的死亡率与白人明显的种族偏见呈正相关
OAAI
OAAI分享收藏Dynamic Graph Mining for Multi-weight Multi-destination Route Planning with Deadlines Constraints
PREAI
分享收藏
查看更多内容