.png){kind=icon}
Return
Contested Route Planning
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-08067-7_6.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider the problem of routing for logistics purposes, in a contested environment where an adversary attempts to disrupt the vehicle along the chosen route. We construct a game-theoretic model that captures the problem of optimal routing in such an environment. While basic robust deterministic routing plans are already challenging to devise, they tend to be predictable, which can limit their effectiveness. By introducing calculated randomness via modeling the route planning process as a two-player zero-sum game, we compute immediately deployable plans that are diversified and harder to anticipate. Although solving the game exactly is intractable in theory, our use of the double-oracle framework enables us to achieve computation times on the order of seconds, making the approach operationally viable. In particular, the framework is modular enough to accommodate specialized routing algorithms as oracles. We evaluate our method on real-world scenarios, showing that it scales effectively to realistic problem sizes and significantly benefits from explicitly modeling the adversarys capabilities, as demonstrated through ablation studies and comparisons with baseline approaches.
Keywords:
Vehicle routing
Game theory
Equilibrium computation
Journal
G
IF:
0
Papers:
16
Citations:
0
Organization
Cited Papers
.png){kind=icon}
ShareSave
ShareSaveShareSaveShareSaveShareSave
A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty
PREAI
ShareSave
View more