Adapted Clustering Algorithms for the Assignment Problem in the MDVRPTW

Abstract

This paper proposes new applications of statistical and data mining techniques for the assignment problem in the Multi-Depot Vehicle Routing Problem with Time Windows (MDVRPTW). Given the intrinsic difficulty of this problem class, approximation methods of the type "cluster first, route second" (two step approaches) seem to be the most promising for practical size problems. After describing five assignment algorithms designed specially for assignment of customers to depots (the cluster phase), the adapted clustering algorithms for the assignment problem are introduced and a preliminary computational study of their performance is presented. Concluding as expected, that the they can be adapted to solve this type problem and many times give very good results (in terms of the routing results), but are still far from some of the other algorithms when it comes to execution times.