The Delivery Dispatching Problem with Time Windows for Urban Consolidation Centers

This paper addresses the dispatching problem faced by an urban consolidation center. The center receives orders according to a stochastic arrival process and dispatches them in batches for the last-mile distribution. The operator of the center aims to find the cost-minimizing consolidation policy, depending on the orders at hand, preannounced orders, and stochastic arrivals. The authors present this problem as a variant of the delivery dispatching problem that includes dispatch windows and define a corresponding Markov decision model. Larger instances of the problem suffer from intractably large state-, outcome-, and action spaces. The authors propose an approximate dynamic programming (ADP) algorithm that can handle such instances, using a linear value function approximation to estimate the downstream costs. To design the value function approximation, the authors construct various sets of basis functions, numerically evaluate their suitability, and discuss the properties of good basis functions for the dispatching problem. Numerical experiments on toy-sized instances show that the best set of basis functions approximates the optimal values with an error of less than 3%. To cope with large action spaces, the authors formulate an integer linear program to be used within their ADP algorithm. The authors evaluate the performance of ADP policies against four benchmark policies: two heuristic policies, a direct cost minimization policy, and a post-decision rollout policy. The authors test the performance of ADP on a variety of networks. ADP consistently outperforms the benchmark policies, performing particularly well when there is sufficient flexibility in dispatch times. The online appendix is available at https://doi.org/10.1287/trsc.2017.0773.

• Record URL:
  https://doi.org/10.1287/trsc.2017.0773
• Record URL:
  https://pubsonline.informs.org/doi/abs/10.1287/trsc.2017.0773
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Supplemental Notes:
  • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
• Authors:
  • van Heeswijk, W J A
  • Mes, M R K
  • Schutten, J M J
• Publication Date: 2019-1

Language

• English

Media Info

• Media Type: Web
• Features: References;
• Pagination: pp 203-221
• Serial:
  • Transportation Science
  • Volume: 53
  • Issue Number: 1
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Delivery service; Dispatching; Dynamic programming; Integer programming; Markov processes; Physical distribution; Time windows; Urban areas
• Uncontrolled Terms: Urban freight consolidation centers
• Subject Areas: Freight Transportation; Highways; Operations and Traffic Management; Planning and Forecasting; Terminals and Facilities;

Filing Info

• Accession Number: 01695258
• Record Type: Publication
• Files: TRIS
• Created Date: Feb 21 2019 9:49AM