Routing Optimization by Considering Multiple Uses of Vehicles and Demand Uncertainty: A Real-World Case Study

This paper studies a novel routing optimization problem motivated by a practical application of urban corrugated box transportation. The problem involves several features originating from the practical application, such as multi-trip, demand uncertainty, and demand-dependent loading time. The robust arc-flow formulation based on the budget uncertainty set is given. Then, we have recourse to the branch-and-price algorithm to solve the problem. Specifically, the pricing subproblem is to find the robust feasible routes with several unique features, including demand uncertainty, trip duration limitation, and demand-dependent loading time. A tailored labeling algorithm with recursive resource extension functions is involved to identify the robust feasible routes. Several numerical experiments are conducted on a real-world case study and generated instances based on the real road network. The computational results indicate that the proposed algorithm is more efficient than the commercial solver, and the proposed algorithm can fit various scenarios in practical applications to generate conservative routes efficiently.