Study Of A Multi-Depot Vehicle Routing Problem With Time Windows (MDVRPTW)

The present study considers a Multi-Depot Vehicle Routing Problem with time windows (MDVRPTW) which is an extension of the VRPTW, and a NP-hard problem see [7],for simultaneously determining the routes for several vehicles from multiple depots to a set of customers and then return to the same depot, within a time windows. To solve this problem, there are two step approaches "cluster first, route second" not independents. A bad assignment solution result a higher total cost (distance) in routing so that a bad solution for MDVRPTW [1].In order to obtain a good solution we will focus in this paper on both of the two steps, for (the cluster step (phase)) we will describe most famous assignment algorithms designed especially for assignment of customers to the depots, but we will give an example shown that these methods are not really useful in our case, which makes us to use another technique.We gave a convenient structure of the original problem which allows us to decompose it to a clustering problem (main problem) and a set of vehicle routing problems (sub-problems) with time window constraints by using a decomposition technique [4]. This method makes the problem’s resolution easier by using a simpler procedures to resolve it, it has also an advantage to reduce the problem size. After transforming the form of the original problem to a clustering problem (main problem) a genetic algorithm is used to solve it, while a heuristic algorithm (ACO) is used to solve the set vehicle routing problems.