Solving an On-Line Capacitated Vehicle Routing Problem with Structured Time Windows

Philipp Hungerländer, Kerstin Maier, Jörg Pöcher, Andrea Rendl and Christian Truden ()
Additional contact information
Philipp Hungerländer: Alpen-Adria Universität Klagenfurt
Kerstin Maier: Alpen-Adria Universität Klagenfurt
Jörg Pöcher: Alpen-Adria Universität Klagenfurt
Andrea Rendl: Alpen-Adria Universität Klagenfurt
Christian Truden: Alpen-Adria Universität Klagenfurt

A chapter in Operations Research Proceedings 2016, 2018, pp 127-132 from Springer

Abstract: Abstract The capacitated Vehicle Routing Problem with structured Time Windows (cVRPsTW) is concerned with finding optimal tours for vehicles with given capacity constraints to deliver goods to customers within assigned time windows that can hold several customers and have a special structure (in our case equidistant and non-overlapping). In this work, we consider an on-line variant of the cVRPsTW that arises in the online shopping service of an international supermarket chain: customers choose a delivery time window for their order online, and the fleet’s tours are updated accordingly in real time. This leads to two challenges. First, the new customers need to be inserted at a suitable place in one of the existing tours. Second, the new customers have to be inserted in real time due to very high request rates. This is why we apply a computationally cheap, two-step approach consisting of an insertion step and an improvement step. In this context, we present a Mixed-Integer Linear Program (MILP) and a heuristic that employs the MILP. In an experimental evaluation, we demonstrate the efficiency of our approaches on a variety of benchmark sets.

Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-55702-1_18

Ordering information: This item can be ordered from
http://www.springer.com/9783319557021

DOI: 10.1007/978-3-319-55702-1_18

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().