Titel: On the Slot Optimization Problem in On-Line Vehicle Routing

The capacitated vehicle routing problem with time windows (cVRPTW) is concerned with finding optimal tours for vehicles that deliver goods to customers within a specific time slot (or time window), respecting the maximal capacity of each vehicle. The on-line variant of the cVRPTW arises for instance in online shopping services of supermarket chains: customers choose a delivery time slot for their order online, and the fleet’s tours are updated accordingly in real time, where the vehicles’ tours are incrementally filled with orders.

In this paper, we consider a challenge arising in the on-line cVRPTW that has not been considered in detail in the literature so far. When placing a new order, the customer receives a selection of available time slots that depends on the customer’s address and the current (optimized) schedule. The customer chooses a preferred time slot, and the order is scheduled. The larger the selection, the more likely the customer finds a suitable time slot, leading to higher customer satisfaction and a higher overall number of orders placed. We denote the problem of determining the maximal number of feasible time slots for a new customer order as the Slot Optimization Problem (SOP).

We formally define the SOP and propose an adaptive neighbourhood search heuristic for determining feasible slots for inserting a new customer orders based on a given delivery schedule in real time. Our approach is tailored to the SOP and combines local search techniques with strategies to overcome local minima. In an experimental evaluation, we demonstrate the efficiency of our approach on a variety of benchmark sets.

Publikationstyp: Beitrag in Sammelwerk (Autorenschaft)
Art der Veröffentlichung Online Publikation
Erschienen in: Transportation Research Procedia
Transportation Research Procedia
zur Publikation
 ( Elsevier Ltd.; )
Erscheinungsdatum: 04.01.2018
Titel der Serie: -
Bandnummer: 27
Erstveröffentlichung: Ja
Version: -
Seite: S. 492 - 499


ISSN: 2352-1465
AC-Nummer: -
Open Access
  • In einem Open-Access-Journal erschienen


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
  • Ja
  • 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