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

摘要： 针对带软时间窗的车辆路径问题(VRPSTW),建立以配送成本为优化目标的混合整数规划模型,提出一种改进蚁群算法(IACO)求解该问题。在传统蚁群算法(ACO)的基础上,改进蚂蚁状态转移概率公式,通过自适应调整信息素挥发系数改进信息素更新策略,设计插入算子和交换算子嵌入变邻域局部搜索,并设置开始和退出局部搜索的条件,更新当前局部最优解。选取Solomon标准测试集里3类不同规模的算例,测试算法改进效果,以客户规模为100的C类算例验证所提算法求解较大规模算例的可行性,并与传统蚁群算法以及其他文献中的算例结果进行对比。实验结果表明,改进蚁群算法的寻优能力高于其他算法,求解得到的最优配送方案能够实现更低的车辆配送成本,从而验证了改进蚁群算法的有效性。

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