Abstract:
Emerging urban logistics applications need to address a wide range of challenges, including complex traffic conditions and time-sensitive requirements. In this paper, in the context of urban logistics we consider a vehicle routing problem with time-dependent travel times and time windows (VRPTW), and the goal is to minimize the total generalized costs including the transportation cost, vehicular waiting cost and the fixed cost associated with each vehicle, as well as capturing the endogenous traffic patterns. We adopt a high-dimensional space-time network flow model to formulate the underlying vehicle routing problem with a rich set of criteria and constraints. A thorny issue, when solving VRP with side constraints, is how to iteratively improve both primal and dual solution quality in general and how to break symmetry due to many identical solutions, especially with homogeneous vehicles. Along this line, many coupling constraints, such as the consensus constraints across different agents or decision makers, need to be carefully addressed to find high-quality optimal or close-to-optimal solutions under medium-scale or large-scale instances. Currently, Alternating Direction Method of Multipliers (ADMM) is widely used in the field of convex optimization, as an integration of Augmented Lagrangian relaxation and block coordinate descent methods for a large number of machine learning and large-scale continuous system optimization and control. In this paper, we first introduce the ADMM to the multi-vehicle routing problem, which is a special case of integer linear programming, and demonstrate the way to reduce the quadratic penalty terms used in ADMM into simple linear functions. In a broader context, a computationally reliable dual decomposition framework is developed to iteratively improve both primal and dual solution quality. We examine the performance of the proposed approach using classical a number of VRP benchmark instances. A real-world instance is specifically tested, based on a problem solving competition offered by Jingdong Logistics, a major E-commerce company.
Bio:
Xuesong Zhou is an Associate Professor of Transportation Systems in the School of Sustainable Engineering and the Built Environment at Arizona State University (ASU) in Tempe, Arizona. Dr. Zhou’s research work focuses on dynamic traffic assignment, traffic estimation and prediction, large-scale routing and rail scheduling. Dr. Zhou is currently an Associate Editor of Transportation Research Part C, an Associate Executive Editor-in-Chief of Urban Rail Transit, an Associate Editor of Networks and Spatial Economics, an Editorial Board Member of Transportation Research Part B. He was the formal Chair of INFORMS Rail Application Section (2016), and the Co-Chair of the IEEE ITS Society Technical Committee on Traffic and Travel Management, as well as a subcommittee chair of the TRB Committee on Transportation Network Modeling (ADB30). He has published more than 50 papers related to dynamic traffic assignment and rail operations research in many journals with an H-index of 33.