Coordinated vehicle scheduling and rescheduling: ADMM decomposition and consistent branch-and-bound

In practice, customer demand often fluctuates substantially, creating additional challenges for route optimisation. Advances in forecasting and data mining allow probabilistic demand patterns to be inferred from historical orders and operational data, facilitating the development of routing strategies that better accommodate demand variability. To further enhance operational stability, we propose a novel integrated framework – formulated as an arc-based model – that jointly optimises master routing schedule (MRS) and scenario-based rescheduling (S-RS), while explicitly accounting for service consistency between them. Service consistency is defined as the degree to which customer-vehicle assignments are preserved between the MRS and the S-RS. To address the problem, we reformulated the arc-based optimisation model into a path-based framework. Leveraging the Alternating Direction Method of Multipliers (ADMM), we decomposed the problem into three interrelated subproblems and designed a nested, two-layer, ADMM-based iterative solution framework to solve the proposed optimisation model. Exploiting problem-specific characteristics, a service consistency-based branch-and-bound algorithm was designed to solve the S-RS. The developed algorithm was tested in a real-world dataset provided by JD Logistics. The results show that appropriate tuning of the heuristic-pruning thresholds balances solution quality and runtime, which constitutes the primary advantage of our approach.