ACO-VRPTWRV: A New Algorithm for the Vehicle Routing Problems with Time Windows and Re-used Vehicles based on Ant Colony Optimization

摘要

A model with multiple objectives to minimize the number and the total delivery time of vehicles for vehicle routing problems with time windows and reused vehicles is proposed. ACO-VRPTWRV algorithm based on ant colony optimization is presented. Heuristic function and state transition rule of ants are designed according to the rule to serve customers with earlier service beginning time, shorter service time and earlier ending time of time windows firstly based on ant colony system. Pheromone trail updating strategy is designed through the combination of max-min and rank-based ant system, making better use of the best solutions while avoiding stagnating in local optimization. A good initial solution is generated in the light of giving customers with earlier service ending time priority. Numerical results show ACO-VRPTWRV is able to produce good solutions quickly, decreasing the number and total delivery time of vehicles. So the model and algorithm is efficient