Optimization Online


On the Slot Optimization Problem in On-Line Vehicle Routing

Philipp Hungerländer (philipp.hungerlaender***at***aau.at)
Andrea Rendl (andrea.rendl***at***aau.at)
Christian Truden (christian.truden***at***aau.at)

Abstract: 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.

Keywords: Vehicle routing problem; time windows; online optimization; time slot management; adaptive neighborhood search.

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Applications -- OR and Management Sciences (Production and Logistics )

Citation: EWGT 2017, accepted.

Download: [PDF]

Entry Submitted: 04/13/2017
Entry Accepted: 04/13/2017
Entry Last Modified: 06/11/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society