The Design And Implementation Of An ACO Approach To MDVRP

Multi-Depot vehicle Routing Problem ( MDVRP ) is one of the complicated combi-natorial optimization problems. MDVRP can be found in reality, and closely associatedwith people's daily life. As a popular meta-heuristic, Ant Colony Optimization ( ACO) has been successfully applied to many routine problems, but few discussion aboutthe application of ACO for MDVRP. By analyzing the characteristics of MDVRP, thisthesis proposes two ACO approaches for MDVRP: the Multi-Colony approach and theSingle-Colony approach. The Multi-Colony approach follows the divide and conquerpolicy, divides a MDVRP instance into several VRP instances by the pre-allocatingalgorithm, then solves VRP by ACO, and finally combines the results of VRP intoMDVRP solution. The Single-Colony approach starts solving MDVRP as a whole,follows the usually framework of ACO solving other NP-hard problems. Both ap-proaches have their own pros and cons. We test these two approaches on the MDVRPbenchmark, the Multi-Colony approach got optimum on 4 problem instances, and theSingle-Colony approach got optimum on 6 problem instances. For the other probleminstances, the Multi-Colony approach got better results than the Single-Colony ap-proach on small size(number of customers n≤100)test instances, but worse resultson big size(number of customers n > 100)test instances.