Reliable Dual Decomposition Framework for Vehicle Routing Problems in City Logistics: Alternating Direction Method of Multipliers

The challenge of city logistics is faced by many logistics companies due to the complex traffic conditions and diversified demands. In this paper, the authors consider a time-dependent vehicle routing problem with time windows (TD-VRPTW) model to formulate freight distribution problems in city logistics in order to minimize the total cost of logistics companies, including the transportation cost, the waiting cost and the fixed vehicle cost. By employing a hyper graph, namely a state-space-time network representation, this TD-VRPTW is formulated as an integer linear programming or a hyper network flow model. In order to iteratively generate high-quality feasible solutions for large-scale real-world instances, the authors introduce the use of an alternating direction method of multipliers (ADMM) in solving this class of high-dimensional transportation network optimization problems, within a reliable dual decomposition framework. Specifically, the primal problem is decomposed into a set of state-space-time shortest path sub-problems, which can be solved by a dynamic programming algorithm in sequence to improve the solution quality iteratively. Finally, two sets of numerical experiments, involving relatively small-scale cases and a real-world instance based on the Jingdong Logistics, a China E-commerce company, are implemented to examine the performance of the proposed approach.

  • Supplemental Notes:
    • This paper was sponsored by TRB committee ADB30 Standing Committee on Transportation Network Modeling.
  • Corporate Authors:

    Transportation Research Board

  • Authors:
    • Yao, Yu
    • Zhu, Xiaoning
    • Mo, Pengli
    • Dong, Hongyu
    • Wu, Shengnan
    • Wu, Hailong
    • Zhou, Xuesong
  • Conference:
  • Date: 2019


  • English

Media Info

  • Media Type: Digital/other
  • Features: Figures; References; Tables;
  • Pagination: 6p

Subject/Index Terms

Filing Info

  • Accession Number: 01698255
  • Record Type: Publication
  • Report/Paper Numbers: 19-03720
  • Files: TRIS, TRB, ATRI
  • Created Date: Dec 7 2018 9:50AM