Abstract
Traditional Vehicle Routing Problem (VRP) solvers prioritize mathematical optimality, often neglecting the implicit preferences of human drivers. This paper presents a preference-based Deep Reinforcement Learning (DRL) framework, POMO+PO, which leverages historical route data to learn driver behavior. By introducing an "Arc Difference" metric and a preference-optimized objective, the model generates routes that align with past driver choices. Experimental results on CVRPLIB benchmarks demonstrate that POMO+PO significantly outperforms standard neural and Markov-based approaches in route alignment and generalization to unseen instances.
Introduction
The Vehicle Routing Problem (VRP) is a fundamental optimization task in logistics. While modern DRL solvers excel at minimizing distance or time, they frequently produce routes that drivers reject. This discrepancy arises because drivers often have implicit preferences—such as avoiding specific intersections or hilly terrain—that are not captured in standard cost functions.
This research treats driver "irrationality" as a valuable signal. By framing route estimation as a Preference-based Reinforcement Learning (PbRL) problem, the authors aim to bridge the gap between theoretical optimality and practical driver acceptance. The core idea is that preference labels are affine invariant, making the model robust to reward scaling and focused on the relative superiority of routes.
Methods
The proposed framework, POMO+PO (Policy Optimization with Multiple Optima + Preference Optimization), integrates historical data into the learning loop to capture these subjective nuances.
Key components include:
- Arc Difference (AD): A structural similarity metric that counts differing edges (arcs) between generated and historical routes. This serves as a proxy for how well the model mimics driver behavior.
- Preference-Based Reward: A composite reward function balancing efficiency (distance) and human-like pathing (AD), controlled by a hyperparameter ($\beta$).
- Reparameterized Optimization Objective: Instead of calculating complex partition functions, the authors reparameterize the reward as a function of policy probability, ensuring stable and computationally tractable optimization.
- Base Architecture: The system utilizes POMO, a state-of-the-art constructive solver that builds solutions node-by-node.
Results and Discussion
The model was evaluated using sub-instances derived from the CVRPLIB dataset. To simulate historical data, optimal routes were perturbed to create a diverse set of 30 preferred routes per instance.
As shown in the visual comparison, POMO+PO produces routes that closely mirror historical preferences. Quantitatively, the model achieved an average AD of 3.15, significantly lower than standard Neural Network approaches (8.81) and Markov-based models (13.21).
Furthermore, POMO+PO demonstrated superior generalization. When tested on unseen instances, it maintained a low AD of 6.68, whereas competing models saw their error rates skyrocket to 15-17+. This suggests the model learns general preference patterns rather than simply memorizing specific maps.
Conclusion
The POMO+PO framework successfully incorporates implicit driver preferences into VRP solving, treating subjectivity as a feature rather than a bug. While currently tested on simulated static data, future work will address real-world GPS noise and dynamic factors like real-time traffic. This approach marks a significant step toward logistics AI that works in harmony with human expertise.
Summary updated