The delivery dispatching problem with time windows for urban consolidation centers

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
1 Downloads (Pure)

Abstract

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. We 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. We 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, we 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, we formulate an integer linear program to be used within our ADP algorithm. We evaluate the performance of ADP policies against four benchmark policies: two heuristic policies, a direct cost minimization policy, and a post-decision rollout policy. We 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.
Original languageEnglish
Pages (from-to)203-221
Number of pages19
JournalTransportation science
Volume53
Issue number1
Early online date28 Aug 2017
DOIs
Publication statusPublished - 1 Jan 2019

Fingerprint

Dynamic programming
Consolidation
consolidation
programming
cost minimizing
Costs
decision model
toy
costs
performance
heuristics
flexibility
time
experiment
Experiments

Cite this

@article{5378b76ecac34ee08adb89f0b23e1959,
title = "The delivery dispatching problem with time windows for urban consolidation centers",
abstract = "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. We 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. We 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, we 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, we formulate an integer linear program to be used within our ADP algorithm. We evaluate the performance of ADP policies against four benchmark policies: two heuristic policies, a direct cost minimization policy, and a post-decision rollout policy. We 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.",
author = "{van Heeswijk}, W.J.A. and Mes, {Martijn R.K.} and Schutten, {Johannes M.J.}",
year = "2019",
month = "1",
day = "1",
doi = "10.1287/trsc.2017.0773",
language = "English",
volume = "53",
pages = "203--221",
journal = "Transportation science",
issn = "0041-1655",
publisher = "INFORMS Institute for Operations Research and the Management Sciences",
number = "1",

}

The delivery dispatching problem with time windows for urban consolidation centers. / van Heeswijk, W.J.A.; Mes, Martijn R.K.; Schutten, Johannes M.J.

In: Transportation science, Vol. 53, No. 1, 01.01.2019, p. 203-221.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - The delivery dispatching problem with time windows for urban consolidation centers

AU - van Heeswijk, W.J.A.

AU - Mes, Martijn R.K.

AU - Schutten, Johannes M.J.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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. We 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. We 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, we 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, we formulate an integer linear program to be used within our ADP algorithm. We evaluate the performance of ADP policies against four benchmark policies: two heuristic policies, a direct cost minimization policy, and a post-decision rollout policy. We 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.

AB - 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. We 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. We 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, we 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, we formulate an integer linear program to be used within our ADP algorithm. We evaluate the performance of ADP policies against four benchmark policies: two heuristic policies, a direct cost minimization policy, and a post-decision rollout policy. We 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.

U2 - 10.1287/trsc.2017.0773

DO - 10.1287/trsc.2017.0773

M3 - Article

VL - 53

SP - 203

EP - 221

JO - Transportation science

JF - Transportation science

SN - 0041-1655

IS - 1

ER -