Optimization For Vehicle Routing Problem With Time Windows And Precedence Constraints By Ant Colony

Vehicle Routing Problem (VRP) is an important problem in physical distribution while Ant Colony System (ACS) is a new mate-heuristic algorithm. This paper uses an improved ACS to solve the VRP with time windows and precedence constraints (VRPTWPC), a special VRP.ACS is improved in this paper. After deeply analyzing ACS, the visibility based on unit saving and time urgency and trail update rule based on .K-optimal solutions for VRPTW are put forward. 2-opt crossover is also used to finish the local search. Experiment on the standard VRP problem shows that a satisfied solution can be found in three cycles.Precedence constraint is also defined in this paper and the worthiness about research on the VRP with precedence constraints is investigated. Precedence constraint is classified after the mathematical notation is given.The algorithm to solve the VRP with precedence constraints is proposed, which includes precedence analysis, undivided set finding and transformation problem from special to normal. Tabu table is used to deal with precedence and trail mutation rule is introduced to ensure that it is possible to reach the tabu point after tabu broken. VRPTWPC is constructed through adding some precedence constraints to Solomon's VRPTW C101.25, a standard VRP problem. Experiments show that the way to solve VRPTWPC is feasible.A special local search is discussed in this paper. The idea of path-preserve-edge-exchange for precedence constraints is given and lexicographic-path-preserving-3-exchange is depicted. Experiment shows that adding the exchange to ACS is effective. Comparison test indicates that satisfied solutions always occur during fewer cycles.