The vehicle routing problem with time windows and flexible delivery locations

Abstract

We introduce a new variant of the well-known vehicle routing problem (VRP): the VRP with time windows and flexible delivery locations (VRPTW-FL). Generally, in the VRP each customer is served in one fixed service location. However, in the VRPTW-FL each customer is served in one of a set of potential service locations, each of which has a certain capacity. From a practical point of view, the VRPTW-FL is highly relevant due to its numerous applications, e.g. parcel delivery, routing with limited parking space, and hospital-wide scheduling of physical therapists. Theoretically, the VRPTW-FL is challenging to solve due to the limited location capacities. When serving a customer, location availability must be ensured at every time. To solve this problem, we present a mathematical model and a tailored hybrid adaptive large neighborhood search. Our heuristic makes use of an innovative backtracking approach during the construction phase to alter unsatisfactory decisions at an early stage. In the meta-heuristic phase, we employ novel neighborhoods and dynamic updates of the objective violation weights. For our computational analysis, we use hospital data to evaluate the utility of flexible delivery locations and various cost functions. Our algorithmic features improve the solution quality considerably.