摘要
提出车辆可重复利用的VRPTW问题,建立多目标整数规划模型;基于蚁群系统(ACS),按优先访问服务开始时间较早、服务时间较短和关窗时间较早的原则,设计启发式因子和蚂蚁状态转移规则;借鉴MMAS和ASrank的优点设计信息素更新策略,既加强对每次迭代最好解的利用,又避免陷入局优;根据客户服务结束时间较早优先原则构造初始解。实验结果表明,可以大幅度减少所需车辆数并节省车辆的总运行时间,具有较快的收敛速度,本文的模型和算法是有效的。
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 vehieles（VRPTWRV）is presented. Then an Ant Colony Optimization based approach to solve this problem is designed. The heuristic function and probabilistie 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.
出处
《系统工程》
CSCD
北大核心
2007年第4期20-26,共7页
Systems Engineering
基金
国家自然科学基金资助项目(70501018
60533100
70301007)
关键词
系统工程
车辆路径问题
蚁群算法(ACO)
整数规划
System Engineering
Vehicle Routing Problems
Ant Colony Optimization（ACO）
Integer Programming
