Solution of emergency logistics open-loop vehicle routing problem with time window based on improved ant colony algorithm(PDF)
长安大学学报（自然科学版）[ISSN:1006-6977/CN:61-1281/TN]
- Issue:
- 2017年06期
- Page:
- 105-112
- Research Field:
- 交通工程
- Publishing date:
Info
- Title:
- Solution of emergency logistics open-loop vehicle routing problem with time window based on improved ant colony algorithm
- Author(s):
- GUO Yong-mei; HU Da-wei; CHEN Xiang
- School of Automobile, Chang’an University, Xi’an 710064, Shaanxi, China
- Keywords:
- traffic engineering; emergency logistics; open-loop vehicle routing problem; reliability; ant colony algorithm; fish swarm algorithm
- PACS:
- U491
- DOI:
- -
- Abstract:
- In order to solve the problem of material transportation in the affected area, an emergency logistics open-loop vehicle routing problem with time window (EL-OLVRPTW) was studied. Taking into account the difference of road traffic performance and the priority of material transportation after disaster, a vehicle routing model based on the maximization of logistics response ability was proposed on the basis of ensuring the reliability of emergency material transportation. Meanwhile, an improved ant colony algorithm (IAC) was proposed to break through the bottleneck of traditional optimization algorithm. The new algorithm improved its convergence and had a great ability to keep from falling into local optimum. This algorithm combined the artificial fish swarm algorithm and the ant colony algorithm. Crowding factor was used for guiding the ant colony for its process of aggregation and finally improved the quality of its solution. The proposed model and algorithm were verified by a basic numerical case. The optimized solution curve was obtained and the optimal solution was solved. The evaluation calculation experiment was conducted on the performance of improved ant colony algorithm by adopting one CMT and GWKC standard example. Numerical calculation adopted simulated annealing algorithm, variable neighborhood search algorithm and neighborhood search algorithm on the standard examples. The results show that the IAC proposed in this paper has a significant advantage in its solving convergence and accuracy. Among these numerical results, the optimal solution solved by IAC is obtained after 60 iterations, which advances 68 iterative cycles compared with the ant colony algorithm. And optimization of the solution is close to 7.8%. Under the same experimental conditions, the scale of the instance data is independent of the difference of the optimal solution, which means the scale of the example does not affect the accuracy of the algorithms. The proposed IAC can significantly improve the accuracy of the solution by properly extending the search time for neighborhood within an acceptable time limit. Compared with other algorithms, the optimal result is obtained by the proposed IAC in each group. The optimal solution obtained by IAC is optimized more than 40% than the known upper bound in the case of CMT2.
Last Update: 2017-12-18