Abstract: In this paper the ant colony algorithm of MDVRP is studied.First the method of making use of improved split algorithm to divide customerto vehicles for given customer sequence is introduced, then this problem isconverted into the problem of finding the optimal customer sequence by usingthe min cost flows to allocate vehicles to each depot, next ant colonyalgorithm for MDVRP is given. At last computational instances are given.

Key words:Multiple-Depot vehicle routing problems, splitalgorithm, min cost flows problem, ant colony algorithm

1. INTRODUCTION

During the late 1950s, the term of VRP (Vehicle Routing Problem) was proposed first byDantzig and Ramse^[1]. Then it was summarized and deepened byN.Christofides^[2]. Vehicle Routing Problem means that distributioncenter provides goods and arranges for vehicle routing to satisfy a certainamountofcustomers who have requirement of different quantity for goods, and toachieve a certain goal (e.g. the shortest distance, the least cost and shortestexpenditure time) under some constraint conditions. From this definition, wecan see that TSP (Traveling Salesman Problem) is a specific case of VRP. Gaeryhas proved that TSP is a difficult NP problem[3], so VRP also belongs to thedifficult NP problem^[4].

VRP has broad application, so it causesgreat interest among researchers. Many achievements were made in the research on VRP. Forcurrent achievements about VRP, it is based on having one distribution center. But in fact, many large commercialenterprises have severaldistribution centers. The problem is different from traditional VRP, and it iscalled MDVRP (Multiple-Depot vehicle routing problem)^[5].