Multiple Depot Vehicle Routing Problems on Clustering Algorithms

Kanokon Leungsubthawee, Supalin Saranwong, Chulin Likasiri

Abstract

This work addresses the clustering problem with two types of clients via the multiple depot vehicle routing problem (MDVRP). The objective function is to minimize the total distance traveled in the system. Two algorithms are proposed to tackle the difficulty of this problem. In the first algorithm, clients are randomly assigned to their closet depots while in the second algorithm each depot in the unassigned depot list is assigned sequentially to its nearest unassigned client. Comparisons of solutions obtained from the proposed algorithms and the optimal solutions show that in small size problems, the objective functions from the first algorithm are closer to the optimal solutions than those from the second algorithm. In larger problems, however, the second algorithm works better than the first because the difference between the number of clients and number of depots is increased. More feasible solutions can also be obtained from the second algorithm in all problems sizes. It can thus be seen that the ratio between number of clients and number of depots affects to the performance of the proposed algorithms.