A scenario-based approach for the vehicle routing problem with roaming delivery locations under stochastic travel times

Research output: Working paperAcademic

Abstract

We address a stochastic variant of the Vehicle Routing Problem with Roaming Delivery Locations. In this model, direct-to-consumer deliveries can be made in the trunk of the customer’s car, while the vehicle is parked at a location along the customer’s itinerary. The stochasticity arises from the uncertainty in travel times and the problem is formulated as a two-stage stochastic model. We propose a scenario-based sample average approximation to obtain a heuristic solution. Several experiments to assess the effect of our solution approach compared to a pure deterministic solution approach using expected travel times,show that a cost savings of on average more than 30% can be obtained. Furthermore, it is shown that the flexibility provided by using alternative roaming delivery locations as a recourse to avoid missed deliveries can provide, on average, costs savings of 25% compared to a recourse staying with the locations chosen in the a priori first stage plan.

LanguageEnglish
PublisherOptimization Online
Number of pages29
StatePublished - 7 May 2019

Fingerprint

Vehicle routing
Travel time
Stochastic models
Costs
Railroad cars
Experiments

Keywords

  • trunk-delivery
  • stochastic travel times
  • sample average approximation

Cite this

@techreport{8bf171032fde4c9197cd303ec62cb07d,
title = "A scenario-based approach for the vehicle routing problem with roaming delivery locations under stochastic travel times",
abstract = "We address a stochastic variant of the Vehicle Routing Problem with Roaming Delivery Locations. In this model, direct-to-consumer deliveries can be made in the trunk of the customer’s car, while the vehicle is parked at a location along the customer’s itinerary. The stochasticity arises from the uncertainty in travel times and the problem is formulated as a two-stage stochastic model. We propose a scenario-based sample average approximation to obtain a heuristic solution. Several experiments to assess the effect of our solution approach compared to a pure deterministic solution approach using expected travel times,show that a cost savings of on average more than 30{\%} can be obtained. Furthermore, it is shown that the flexibility provided by using alternative roaming delivery locations as a recourse to avoid missed deliveries can provide, on average, costs savings of 25{\%} compared to a recourse staying with the locations chosen in the a priori first stage plan.",
keywords = "trunk-delivery, stochastic travel times, sample average approximation",
author = "{Sampaio Oliveira}, Afonso and Joris Kinable and Luuk Veelenturf and {van Woensel}, Tom",
year = "2019",
month = "5",
day = "7",
language = "English",
publisher = "Optimization Online",
type = "WorkingPaper",
institution = "Optimization Online",

}

TY - UNPB

T1 - A scenario-based approach for the vehicle routing problem with roaming delivery locations under stochastic travel times

AU - Sampaio Oliveira,Afonso

AU - Kinable,Joris

AU - Veelenturf,Luuk

AU - van Woensel,Tom

PY - 2019/5/7

Y1 - 2019/5/7

N2 - We address a stochastic variant of the Vehicle Routing Problem with Roaming Delivery Locations. In this model, direct-to-consumer deliveries can be made in the trunk of the customer’s car, while the vehicle is parked at a location along the customer’s itinerary. The stochasticity arises from the uncertainty in travel times and the problem is formulated as a two-stage stochastic model. We propose a scenario-based sample average approximation to obtain a heuristic solution. Several experiments to assess the effect of our solution approach compared to a pure deterministic solution approach using expected travel times,show that a cost savings of on average more than 30% can be obtained. Furthermore, it is shown that the flexibility provided by using alternative roaming delivery locations as a recourse to avoid missed deliveries can provide, on average, costs savings of 25% compared to a recourse staying with the locations chosen in the a priori first stage plan.

AB - We address a stochastic variant of the Vehicle Routing Problem with Roaming Delivery Locations. In this model, direct-to-consumer deliveries can be made in the trunk of the customer’s car, while the vehicle is parked at a location along the customer’s itinerary. The stochasticity arises from the uncertainty in travel times and the problem is formulated as a two-stage stochastic model. We propose a scenario-based sample average approximation to obtain a heuristic solution. Several experiments to assess the effect of our solution approach compared to a pure deterministic solution approach using expected travel times,show that a cost savings of on average more than 30% can be obtained. Furthermore, it is shown that the flexibility provided by using alternative roaming delivery locations as a recourse to avoid missed deliveries can provide, on average, costs savings of 25% compared to a recourse staying with the locations chosen in the a priori first stage plan.

KW - trunk-delivery

KW - stochastic travel times

KW - sample average approximation

UR - http://www.optimization-online.org/DB_HTML/2019/05/7197.html

M3 - Working paper

BT - A scenario-based approach for the vehicle routing problem with roaming delivery locations under stochastic travel times

PB - Optimization Online

ER -