带时间窗VRP问题的多智能体进化算法

基于实用性和合理性的角度, 研究了单个配送中心带时间窗的车辆路径问题。以行驶时间最短和客户等待时间最小为目标函数, 以服务时间窗与车辆载质量为约束条件, 建立了双目标优化模型, 采用基于整数编码的多智能体进化算法求解模型, 并将计算结果与利用遗传算法求得的结果进行对比。
计算结果表明: 当客户需求点的数量为13, 需求点的服务时间为5min, 车辆最大载质量为3t, 初始智能体个数为49, 最大进化代数为200次时, 经过30次计算后, 采用遗传算法的最差值为121.8min, 最优值为110.3min, 采用提出多智能体进化算法的最差值为113.6min, 最优目标值为103.6min。可见, 采用多智能体进化算法能够获得更高质量的最优解, 而且经过多次反复试验, 最终解的变化不大。

Multi-agent evolutionary algorithm of VRP problem with time window

Based on the angle of practicality and rationality, the vehicle routing problem with time window for single distribution center was studied.The shortest driving time and the minimum customer waiting time were taken as objective functions, the service time window and vehicle load were taken as constraint conditions, and the bi-objective optimization model was constructed. The Multi-agent evolutionary algorithm based on number coding (NC-MAEA) was used to solve the model, and the calculation result was compared with the calculation result solved by genetic algorithm.Calculation result shows that when the number of customer demand point is 13, the service time of demand point is 5 min, the maximum vehicle load is 3 t, the number of initial agent is 49 and the maximum evolution iterations is 200, the worst value is 121.8 min and the optimal value is 110.
3 min calculated by using genetic algorithm after 30 calculation times.The worst value is 113.6 min and the optimal value is 103.6 min calcuated by using the propsed algorithm.It is clear that the higher quality optimal result can be gotten by using the multi-agent evolutionary algorithm, the results change little after repeated tests.