Solving an On-line Capacitated Vehicle Routing Problem with Structured Time Windows
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.
Entry Submitted: 12/12/2016
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|