A Hybrid Metaheuristic Algorithm for the Multi-depot Vehicle Routing Problem with Time Windows

摘要

The multi-depot vehicle routing problem with time windows (MDVRPTW) is an extension to the classical Vehicle Routing Problem (VRP); it is the major research topics in the supply chain management field. It aims to designing a set of minimum-cost routes for a vehicle fleet servicing many customers with known demands and predefined time windows.In this paper a hybrid metaheuristic algorithm is proposed to solve MDVSPTW successfully by ants transfer policy and algorithm to construct solution designed in this dissertation. To improve hybrid ant colony algorithm performance, a local search improvement algorithm that explores a large neighborhood of the current solution to discover a cheaper set of feasible routes. The neighborhood structure comprises all solutions that can be generated by iteratively performing node exchanges among nearby trips followed by a node reordering on every route. The experiment indicates the validity of the technique to MDVSPTW with the above-mentioned conditions.