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

Keywords: vehicle routing problem; time windows; online optimization; exploiting special structure; mixed-integer linear programming

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

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

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

Citation: Operations Research Proceedings 2016, accepted.

Download: [PDF]

Entry Submitted: 12/12/2016
Entry Accepted: 12/12/2016
Entry Last Modified: 12/12/2016

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