A GRASP/VND Heuristic for the Heterogeneous Fleet Vehicle Routing Problem with Time Windows

摘要

The Heterogeneous Fleet Vehicle Routing Problem with Time Windows (HFVRPTW) is here introduced. This combinatorial optimization problem is an extension of the well-known Vehicle Routing Problem (VRP), which belongs to the NP-Hard class. As a corollary, our problem belongs to this class, a fact that promotes the development of approximative methods. A mathematical programming formulation for the HFVRPTW is presented, and an exact solution method using CPLEX is implemented. A GRASP/VND methodology is also developed, combining five different local searches. The effectiveness of our proposal is studied in relation with the exact solver. Our proposal outperforms the exact CPLEX in terms of CPU times, and finds even better solutions under large-sized instances, where the exact solver halts after ten hours of continuous execution.