关键词: 蚁群算法, 变邻域搜索, 软时间窗, 车辆路径问题

Abstract: To solve the Vehicle Routing Problem with Soft Time Window (VRPSTW) problem,a mixed integer programming model with distribution cost as the optimization objective was established,and an Improved Ant Colony Optimization (IACO) algorithm was proposed.Based on the traditional Ant Colony Optimization (ACO) algorithm,the formula of ant state transition probability was improved,and the pheromone update strategy was develped by adaptively adjusting the pheromone volatilization coefficient.The insertion operator and the exchange operator were designed to embed the variable neighborhood local search.The conditions for starting and exiting the local search were set to update the current local optimal solution.Three different scale examples in the Solomon benchmark set were selected to test the performance of the algorithm.The type-C instances with 100 customers in Solomon benchmark set were selected to verify the feasibility of this algorithm to solve large-scale problems.The results of IACO were compared with those of traditional ACO and other literatures.The experimental results showed that the optimization ability of IACO was better than other algorithms,and the optimal distribution scheme obtained by IACO achieved lower vehicle distribution cost.Therefore,the effectiveness of IACO was verified.

Key words: ant colony optimization algorithm, variable neighborhood search, soft time windows, vehicle routing problem