A clustering approach for vehicle routing problems with hard time windows

Dissertação para obtenção do Grau de Mestre em Logica Computicional

The Vehicle Routing Problem (VRP) is a well known combinatorial optimization problem and many studies have been dedicated to it over the years since solving the VRP optimally or near-optimally for very large size problems has many practical applications (e.g. in various logistics systems). Vehicle Routing Problem with hard TimeWindows (VRPTW) is probably the most studied variant of the VRP problem and the presence of time windows requires complex techniques to handle it. In fact, finding a feasible solution to the VRPTWwhen the number of vehicles is fixed is an NP-complete problem. However, VRPTW is well studied and many different approaches to solve it have been developed over the years. Due to the inherent complexity of the underlying problem VRPTW is NP-Hard. Therefore, optimally solving problems with no more than one hundred requests is considered intractably hard. For this reason the literature is full with inexact methods that use metaheuristics, local search and hybrid approaches which are capable of producing high quality solutions within practical time limits. In this work we are interested in applying clustering techniques to VRPTWproblem. The idea of clustering has been successfully applied to the basic VRP problem. However very little work has yet been done in using clustering in the VRPTW variant. We present a novel approach based on clustering, that any VRPTW solver can adapt, by running a preprocessing stage before attempting to solve the problem. Our proposed method, tested with a state of the art solver (Indigo), enables the solver to find solutions much faster (up to an order of magnitude speed-up). In general this comes with at slightly reduced solution quality, but in somes types of problems, Indigo is able to obtain better solutions than those obtained with no clustering.