车辆可重复利用VRPTW问题的模型和改进蚁群算法

提出车辆可重复利用的VRPTW问题,建立多目标整数规划模型;基于蚁群系统（ACS）,按优先访问服务开始时间较早、服务时间较短和关窗时间较早的原则,设计启发式因子和蚂蚁状态转移规则;借鉴MMAS和ASrank的优点设计信息素更新策略,既加强对每次迭代最好解的利用,又避免陷入局优;根据客户服务结束时间较早优先原则构造初始解.实验结果表明,可以大幅度减少所需车辆数并节省车辆的总运行时间,具有较快的收敛速度,本文的模型和算法是有效的.

A Model for the VRPTW with Re-used Vehicles and Improved Ant Colony Optimization

A multiple objective integer programming model with minimizing of the number of vehicles and minimizing of the total time of all vehicles for the vehicle routing problems with time windows and re-used vehicles(VRPTWRV)is presented.Then an Ant Colony Optimization based approach to solve this problem is designed.The heuristic function and probabilistic formula are constructed according to the rules to give customs with earlier service beginning time,shorter service time and earlier closed time of time window priority on the basis of Ant Colony System.Pheromone trail updating strategy is designed based on the combination of the advantages of MAX-MIN Ant System and Rank-based Ant System,making better use of the best solution of every iteration as well as avoiding stopping in local optimization.A good initial solution is produced in term of serving customs with earlier service closed time firstly.Experimental results demonstrate that the algorithm is capable of generating good solutions to VRPTWRV quickly,decreasing the number of vehicles and total time of all vehicles considerably.So,the model and algorithm is valid.