An augmented Lagrangian relaxation method for the mean-standard deviation based vehicle routing problem

With the ever-increasing trip demand and limited transportation resource, traffic congestions remain a tricky problem. Under traffic congestions, travel times are unstable and variable in a real-world network. When we conduct many time-sensitive vehicle routing optimizations such as vaccine transportation, it is essential to consider the travel time variability in these optimizations. However, most previous vehicle routing studies neglected the travel time variability and adopted the expected travel times or lengths of links. The historical travel times of multiple days allow us to access and describe the travel time variability. We can easily obtain the travel time means and standard deviations of links from these data. This study applies these two statistical indicators to vehicle routing optimization and concentrates on a mean-standard deviation based vehicle routing model. This model has a nonlinear and concave objective function that dramatically increases the problem complexity. We develop a novel augmented Lagrangian relaxation approach for this problem. A lower bound is constructed for this problem by applying the Lagrangian relaxation and decomposition technique twice. To break the inherent symmetry of this problem, we use the augmented Lagrangian relaxation method with block coordinate descent, linearization, and Lagrangian substitution techniques to achieve high-quality feasible solutions. Thus, the relative gap between the lower and upper bounds can be evaluated and reduced in the solving procedure. We implement the proposed method on the datasets modified from the standard benchmark instances. The average relative gaps of instances in sets A and P are 8.8% and 7.6%, respectively. (c) 2022 Elsevier B.V. All rights reserved.

Automated summary

With the increasing demand for travel and limited transportation resources, traffic congestion remains a challenging problem. This study considers the variability of travel times in vehicle routing optimization by utilizing historical travel time data. A mean-standard deviation based vehicle routing model is developed and solved using an augmented Lagrangian relaxation approach. The proposed method effectively reduces the relative gap between the lower and upper bounds in the solving procedure.