Augmented Lagrangian relaxation approach for logistics vehicle routing problem with mixed backhauls and time windows

• Published in: Transportation research. Part E, Logistics and transportation review Logistics and transportation review, 2020-03, Vol.135, p.101891, Article 101891
• Main Authors: Yang, Senyan, Ning, Lianju, Shang, Pan, (Carol) Tong, Lu
• Format: Article
• Language: English
• Subjects: Augmented Lagrangian relaxation; Mixed backhauls; Nonlinear Gauss–Seidel method; Pickups and deliveries; Vehicle routing problem
• ISSN: 1366-5545; 1878-5794
• DOI: 10.1016/j.tre.2020.101891

•Study the vehicle routing problem with mixed backhauls and time windows for the city logistics.•Formulate a network flow optimization model in an extended state-space-time network.•Implement an augmented Lagrangian relaxation technique to construct the quadratic 0–1 programming model.•Decompose the model into a series of sub-problems, solved in a block Gauss–Seidel framework. This paper studies the vehicle routing problem with mixed backhauls and time windows (VRPMBTW) for city logistics. A time-discretized multi-commodity network flow optimization model is proposed in an extended state-space-time network representation, where the time-dependent pickups and deliveries can be depicted by extending the state dimensions. By implementing an augmented Lagrangian relaxation technique, the VRPMBTW is reformulated as a quadratic 0–1 programming model, which is further decomposed into the standard least-cost-path sub-problems, and iteratively solved by dynamic programming in a block nonlinear Gauss-Seidel framework. The proposed approach is tested on the simple 9-node network and the real-world Chicago sketch network.