An Ant Colony Algorithm with Memory Grouping List for Multi-Depot Vehicle Routing Problem

Multi-depot vehicle routing problem (MDVRP for short) is complex and a typical NP-Hard problem in manufactories, especially in assembly plant. We herein present an ant colony algorithm with memory grouping list (ACMGL for short) to solve this problem. To handle affiliation between clients and depots, we present certain point grouping (CP Grouping) and uncertain point grouping (UP Grouping) and obtain variable grouping purposes, make a grouping memory list for each depot store the optimal value and path of uncertain grouping after UP grouping, and thus improve the efficiency of the operation. Experimental results verified our algorithm in the computational efficiency.