Journal of Systems Engineering and Electronics ›› 2018, Vol. 29 ›› Issue (3): 625-638.doi: 10.21629/JSEE.2018.03.20

• Software Algorithm and Simulation • Previous Articles     Next Articles

Multi-type ant system algorithm for the time dependent vehicle routing problem with time windows

Ye DENG1(), Wanhong ZHU1,*(), Hongwei LI1(), Yonghui ZHENG2()   

  1. 1 College of Field Engineering, Army Engineering University of PLA, Nanjing 210001, China
    2 Department of Fire Control, Armored Force Institute of PLA, Bengbu 214500, China
  • Received:2017-01-03 Online:2018-06-28 Published:2018-07-02
  • Contact: Wanhong ZHU E-mail:dengye32@163.com;zhuwh_njgy@sina.com;13913828080@139.com;zyh_sr71@163.com
  • About author:DENG Ye was born in 1989. He is a Ph.D. candidate in College of Field Engineering, Army Engineering University of PLA. His research interests include logistics modeling, optimization and algorithm. E-mail: dengye32@163.com|ZHU Wanhong was born in 1964. He is a professor in College of Field Engineering, Army Engineering University of PLA. His research interests are systems engineering and analysis and comprehensive protection effectiveness evaluation. E-mail: zhuwh_njgy@sina.com|LI Hongwei was born in 1978. He is an associate professor in College of Field Engineering, Army Engineering University of PLA. His research interests are military operation research and system simulation. E-mail: 13913828080@139.com|ZHENG Yonghui was born in 1985. He is a lecturer in Armored Force Institute of PLA. His research interests are military operation research and system engineering. E-mail:zyh_sr71@163.com

Abstract:

The time dependent vehicle routing problem with time windows (TDVRPTW) is considered. A multi-type ant system (MTAS) algorithm hybridized with the ant colony system (ACS) and the max-min ant system (MMAS) algorithms is proposed. This combination absorbs the merits of the two algorithms in solutions construction and optimization separately. In order to improve the efficiency of the insertion procedure, a nearest neighbor selection (NNS) mechanism, an insertion local search procedure and a local optimization procedure are specified in detail. And in order to find a balance between good scouting performance and fast convergence rate, an adaptive pheromone updating strategy is proposed in the MTAS. Computational results confirm the MTAS algorithm's good performance with all these strategies on classic vehicle routing problem with time windows (VRPTW) benchmark instances and the TDVRPTW instances, and some better results especially for the number of vehicles and travel times of the best solutions are obtained in comparison with the previous research.

Key words: multi-type ant system (MTAS), time dependent, vehicle routing problem with time windows (VRPTW), nearest neighbor selection (NNS)