| Allied Vehicle Routing Problem(AVRP) deals with optimization of vehicle routing and scheduling based on logistic alliance. In this paper, mathematical models are builded, Ant Colony Algorithm(ACA) is designed and experiments are computed in allusion to some different kind of AVRP. The main work is as follows:Firstly, an improved ACA is put forward to solve single fleet AVRP with time windows. A strategy of feasible approximate solution is put forward. In the strategy, three types of branch circuits are established and the ownership of skipped clients is processed to make sure a feasible solution is created in each time of iteration. In this way, feasible solution is created in each time of iteration.Secondly, an improved ACA is put forward to solve mixed fleet AVRP with time windows. On one hand, selection strategy is divided into three phases and appropriate transfer probability is chosen in each phase. On the other hand, pheromone volatilization gene is self-adaptively adjusted according to the relationship between strength and volatilization velocity of pheromone. In this way, it can make the solution jump out of local optimal point, and can get to a faster convergence speed.Thirdly, a method of uniting sweep algorithm and saving algorithm is put forward to solve multiple-depot AVRP with time windows. Ratios of nearest and second nearest distances between each client and fleet are computed, and final dispatch is confirmed according to the saving value.Fourthly, a parallel ACA is put forward to solve AVRP. Via analyzing the thinking of ACA, a master-slave scheme parallel ant colony algorithm based on coarse granularity is conformed. Tasks are respectively arranged to server and processors and their algorithm flows are designed. In this way, larger models of AVRP converge easily.Finally, content of the paper is summed up and a tentative plan for next work is put forward. |
PDF Full Text Request