Titel: Solving an On-line Capacitated Vehicle Routing Problem with Structured Time Windows

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.

Publikationstyp: Beitrag in Proceedings (Autorenschaft)
Art der Veröffentlichung Printversion
Erschienen in: Operations Research Proceeding 2016
Operations Research Proceeding 2016
zur Publikation
 ( Springer International Publishing AG; A. Fink, A. Fügenschuh, M. Geiger )
Erscheinungsdatum: 21.07.2017
Titel der Serie: Operations Research Proceedings book series (ORP)
Bandnummer: -
Erstveröffentlichung: Ja
Seite: S. 127 - 132


  • 978-3-319-55702-1
  • 978-3-319-55701-4
AC-Nummer: -
Open Access
  • Online verfügbar (nicht Open Access)


Organisation Adresse
Fakultät für Technische Wissenschaften
Institut für Mathematik
Universitätsstraße 65-67
9020 Klagenfurt am Wörthersee
zur Organisation
Universitätsstraße 65-67
AT - 9020  Klagenfurt am Wörthersee


  • 101015 - Operations Research
  • 101016 - Optimierung
Forschungscluster Kein Forschungscluster ausgewählt
Peer Reviewed
  • Nein
  • Science to Science (Qualitätsindikator: II)
Klassifikationsraster der zugeordneten Organisationseinheiten:
  • Diskrete Mathematik und Optimierung


Keine Partnerorganisation ausgewählt

Beiträge der Publikation

Keine verknüpften Publikationen vorhanden