Optimization Online


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

Philipp Hungerländer (philipp.hungerlaender***at***aau.at)
Kerstin Maier (kerstin.maier***at***aau.at)
Jörg Pöcher (joerg.poecher***at***aau.at)
Andrea Rendl (andrea.rendl***at***aau.at)
Christian Truden (christian.truden***at***aau.at)

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 have a special structure: they are non-overlapping and can hold several customers. These special features stem from a real-world application, and we show how they can be exploited during the solving process. In this work, we consider an on-line variant of the cVRPsTW, similar to the Home Delivery Problem that arises in the online shopping services of supermarket chains: customers choose a delivery time window for their order online, and the vehicle 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 available tours. Secondly, the new customers have to be inserted in real time due to very high customer request frequency. 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 heuristics and two mixed-integer linear programs that are employed by the heuristics. In an experimental evaluation, we demonstrate the efficiency of our approaches on a variety of benchmark sets based on different scenarios that are motivated by our application.

Keywords: Vehicle routing problem; time windows; online optimization; exploiting special structure; local search heuristics; mixed-integer linear programming

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

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Applications -- OR and Management Sciences (Supply Chain Management )

Citation: Technical report, Alpen-Adria Universität Klagenfurt, Mathematics, Optimization Group, TR-AAUK-M-O-17-02-13, 2017

Download: [PDF]

Entry Submitted: 02/14/2017
Entry Accepted: 02/14/2017
Entry Last Modified: 02/24/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