The Flexible Delivery Problem with Time Windows

n this thesis, we propose the Flexible Delivery Problem with Time Windows (FDPTW) as a new member to the family of vehicle routing problems. In this problem, there is a set of parcels with multiple potential delivery locations and corresponding time windows that have to be delivered by a set of vehicles originating from a single depot. Since this is a new problem, we create various sets of benchmark instances for this problem to allow for empirical analysis of solution methods. We develop three exact formulations for this problem, but using these formulations and the general purpose mixed integer programming solver CPLEX we are unable to solve moderately-sized problem instances. Therefore, the focus of this thesis lies on developing a route construction and route improvement local search heuristic for the FDPTW.