The delivery dispatching problem with time windows for urban consolidation centers

Research output: Book/ReportReportProfessional

192 Downloads (Pure)

Abstract

This paper addresses the dispatch decision problem faced by an urban consolidation center. The center receives orders according to a stochastic arrival process, and dispatches them for the last-mile distribution in batches. The operator of the center aims to fi nd the cost-minimizing consolidation policy, depending on the orders at hand, pre-announced orders, and stochastic arrivals. We present this problem as a variant of the Delivery Dispatching Problem that includes dispatch windows, and model it as a Markov decision problem. For toy-sized instances, we solve this model to optimality. Through numerical experiments on these instances, we show that we approximate the optimal values with an error of less than 2%. Larger instances suff er from intractably large state-, outcome-, and action spaces. We propose an Approximate Dynamic Programming (ADP) algorithm that can handle such instances, using value function approximation to estimate the downstream costs. To cope with large action spaces - with sizes up to 2120 in our experiments - we formulate an integer linear program to be used within our ADP algorithm. To evaluate the performance of our ADP policies, we test against various benchmark policies, including a lookahead policy based on scenario sampling. We test the performance of ADP on a variety of networks. When the dispatching problem provides su fficient fl+6exibility in dispatch times, ADP outperforms our myopic benchmark policies by more than 15%, and lookahead policies by over 10%.
Original languageEnglish
Place of PublicationEindhoven
PublisherBETA Research School for Operations Management and Logistics
Publication statusPublished - 2015

Publication series

NameBETA working papers
PublisherBETA Research School for Operations Management and Logistics
No.493

Fingerprint

Dynamic programming
Consolidation
Costs
Experiments
Sampling

Keywords

  • METIS-316452
  • IR-104010

Cite this

van Heeswijk, W. J. A., Mes, M. R. K., & Schutten, J. M. J. (2015). The delivery dispatching problem with time windows for urban consolidation centers. (BETA working papers; No. 493). Eindhoven: BETA Research School for Operations Management and Logistics.
van Heeswijk, W.J.A. ; Mes, Martijn R.K. ; Schutten, Johannes M.J. / The delivery dispatching problem with time windows for urban consolidation centers. Eindhoven : BETA Research School for Operations Management and Logistics, 2015. (BETA working papers; 493).
@book{7c38d7d9a53241268f359f922f9d9caa,
title = "The delivery dispatching problem with time windows for urban consolidation centers",
abstract = "This paper addresses the dispatch decision problem faced by an urban consolidation center. The center receives orders according to a stochastic arrival process, and dispatches them for the last-mile distribution in batches. The operator of the center aims to fi nd the cost-minimizing consolidation policy, depending on the orders at hand, pre-announced orders, and stochastic arrivals. We present this problem as a variant of the Delivery Dispatching Problem that includes dispatch windows, and model it as a Markov decision problem. For toy-sized instances, we solve this model to optimality. Through numerical experiments on these instances, we show that we approximate the optimal values with an error of less than 2{\%}. Larger instances suff er from intractably large state-, outcome-, and action spaces. We propose an Approximate Dynamic Programming (ADP) algorithm that can handle such instances, using value function approximation to estimate the downstream costs. To cope with large action spaces - with sizes up to 2120 in our experiments - we formulate an integer linear program to be used within our ADP algorithm. To evaluate the performance of our ADP policies, we test against various benchmark policies, including a lookahead policy based on scenario sampling. We test the performance of ADP on a variety of networks. When the dispatching problem provides su fficient fl+6exibility in dispatch times, ADP outperforms our myopic benchmark policies by more than 15{\%}, and lookahead policies by over 10{\%}.",
keywords = "METIS-316452, IR-104010",
author = "{van Heeswijk}, W.J.A. and Mes, {Martijn R.K.} and Schutten, {Johannes M.J.}",
year = "2015",
language = "English",
series = "BETA working papers",
publisher = "BETA Research School for Operations Management and Logistics",
number = "493",

}

van Heeswijk, WJA, Mes, MRK & Schutten, JMJ 2015, The delivery dispatching problem with time windows for urban consolidation centers. BETA working papers, no. 493, BETA Research School for Operations Management and Logistics, Eindhoven.

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

Eindhoven : BETA Research School for Operations Management and Logistics, 2015. (BETA working papers; No. 493).

Research output: Book/ReportReportProfessional

TY - BOOK

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 - 2015

Y1 - 2015

N2 - This paper addresses the dispatch decision problem faced by an urban consolidation center. The center receives orders according to a stochastic arrival process, and dispatches them for the last-mile distribution in batches. The operator of the center aims to fi nd the cost-minimizing consolidation policy, depending on the orders at hand, pre-announced orders, and stochastic arrivals. We present this problem as a variant of the Delivery Dispatching Problem that includes dispatch windows, and model it as a Markov decision problem. For toy-sized instances, we solve this model to optimality. Through numerical experiments on these instances, we show that we approximate the optimal values with an error of less than 2%. Larger instances suff er from intractably large state-, outcome-, and action spaces. We propose an Approximate Dynamic Programming (ADP) algorithm that can handle such instances, using value function approximation to estimate the downstream costs. To cope with large action spaces - with sizes up to 2120 in our experiments - we formulate an integer linear program to be used within our ADP algorithm. To evaluate the performance of our ADP policies, we test against various benchmark policies, including a lookahead policy based on scenario sampling. We test the performance of ADP on a variety of networks. When the dispatching problem provides su fficient fl+6exibility in dispatch times, ADP outperforms our myopic benchmark policies by more than 15%, and lookahead policies by over 10%.

AB - This paper addresses the dispatch decision problem faced by an urban consolidation center. The center receives orders according to a stochastic arrival process, and dispatches them for the last-mile distribution in batches. The operator of the center aims to fi nd the cost-minimizing consolidation policy, depending on the orders at hand, pre-announced orders, and stochastic arrivals. We present this problem as a variant of the Delivery Dispatching Problem that includes dispatch windows, and model it as a Markov decision problem. For toy-sized instances, we solve this model to optimality. Through numerical experiments on these instances, we show that we approximate the optimal values with an error of less than 2%. Larger instances suff er from intractably large state-, outcome-, and action spaces. We propose an Approximate Dynamic Programming (ADP) algorithm that can handle such instances, using value function approximation to estimate the downstream costs. To cope with large action spaces - with sizes up to 2120 in our experiments - we formulate an integer linear program to be used within our ADP algorithm. To evaluate the performance of our ADP policies, we test against various benchmark policies, including a lookahead policy based on scenario sampling. We test the performance of ADP on a variety of networks. When the dispatching problem provides su fficient fl+6exibility in dispatch times, ADP outperforms our myopic benchmark policies by more than 15%, and lookahead policies by over 10%.

KW - METIS-316452

KW - IR-104010

M3 - Report

T3 - BETA working papers

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

PB - BETA Research School for Operations Management and Logistics

CY - Eindhoven

ER -

van Heeswijk WJA, Mes MRK, Schutten JMJ. The delivery dispatching problem with time windows for urban consolidation centers. Eindhoven: BETA Research School for Operations Management and Logistics, 2015. (BETA working papers; 493).