Two-Stage Optimization for Multi-Objective Dynamic Vehicle Routing Problem with Time Windows under Uncertainty
针对物流中带时间窗的车辆路径问题，提出两阶段优化模型和算法，在鲁棒性和适应性之间取得平衡，实验表明优于现有方法。
As a fundamental optimization problem in real-world logistics and transportation, the Vehicle Routing Problem with Time Windows (VRPTW) typically faces uncertainty in the operational process (e.g., travel times and demands), as well as dynamically arriving customer requests. Pursuing robustness requires preserving sufficient buffers to absorb uncertainties, but inserting new customer requests inevitably consumes these buffers, which means the adaptability is achieved at the cost of robustness. Conversely, strictly maintaining robustness will reduce possible insertion positions that satisfy this requirement, thereby restricting adaptability to dynamic customer requests. Unfortunately, existing methods typically deal with both challenges separately, ignoring their inherent conflict and thus failing to achieve a balance between robustness and adaptability. To address this issue, this paper formulates a two-stage mathematical model for the Multi-Objective Dynamic VRPTW under Uncertainty, including a robust stage and a dynamic stage. To solve the model, a Two-Stage Optimization algorithm is developed. The robust stage employs a dual-population mechanism with a novel local search strategy to generate a high-quality and proactively flexible initial plan. During the dynamic stage, a rapid response procedure is proposed to efficiently accommodate new requests. Extensive experiments on benchmark and real-world problems demonstrate that the proposed algorithm outperforms competitive state-of-the-art algorithms in terms of robustness and solution optimality.