Delay-resistant robust vehicle routing with heterogeneous time windows
研究了考虑不同车辆对不同客户有不同时间窗的鲁棒车辆路径问题，提出一种新目标函数惩罚延迟，通过列生成和标签算法找到耐延迟的鲁棒解，并在真实数据上验证了效果。
We consider a robust variant of the vehicle routing problem with heterogeneous time windows (RVRP-HTW) with a focus on delay-resistant solutions. Here, customers have different availability time windows for every vehicle and must be provided with a preferably tight appointment window for the planned service. Different vehicles are a possibility to model different days on which one physical vehicle can serve a customer. This is the main reason why different time windows for different vehicles are of high practical relevance. To ensure that the appointment windows are adhered to as much as possible, we introduce a new objective function that penalizes delays. Our novel approach allows us to find solutions that are robust with respect to uncertainties in travel and service times limited by a budget polytope. We present a set-partitioning model, the solution of which is based on column generation and employs a labeling algorithm that integrates robustness into the calculations and is adapted to our problem-specific constraints. In a Monte-Carlo simulation on real-life data, we evaluate this method in terms of runtime and solution quality. Our solutions show very good performance, even if the data is more uncertain than assumed for the optimization, incurring only marginal extra travel time compared to a naive deterministic planning scheme.