APPLYNING THE ANT COLONY OPTIMIZATION TO THE DAYNAMIC VEHICLE ROUTING PROBLEM

摘要

The vehicle routing problem is the combinatorial optimization problem which determines a set of optimal routes for fleet of vehicles with minimum total travel cost in order to satisfy a given set of customers. Ant Colony Optimization (ACO) is a new swarm intelligence meta-heuristic which is found to be efficient to solve combinatorial optimization problems. Recently, Solution methods using ACO for various static vehicle routing problems, such as with vehicle capacities and with time windows, are proposed. In the real world, however, we must consider various cases such as one vehicle or some vehicles fell into delivery impossibility status by traffic accident or engine trouble in the middle of deliver. In such a situation, immediately, the depot has to reschedule of an effective vehicle route. In this paper, we propose a solution method based on ACO for the dynamic Vehicle Routing Problem in consideration of traffic accident and engine trouble of vehicles.