多目标动态车辆路径问题建模及优化  

Modeling and Optimization for Multi-objective Dynamic Vehicle Routing Problem

作　　者：周慧[1] 周良[1] 丁秋林[1] 

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京210016

出　　处：《计算机科学》2015年第6期204-209,共6页Computer Science

基　　金：江苏省产学研联合创新资金项目(SBY201320423)资助

摘　　要：针对物流配送中动态车辆路径优化问题,综合考虑动态需求、路网影响、车辆共享、时间窗以及客户满意度,建立了多目标动态数学规划模型,该模型能更好地描述现代物流配送问题。同时,提出一种两阶段求解策略,第一阶段采用多目标混合粒子群优化算法获取预优化阶段Pareto最优解,采用改进的粒子状态更新策略并融合模拟退火操作提升粒子群搜索性能,采用自适应网格技术保持解的分布性;第二阶段对客户的需求变化采用贪婪插入和变邻域搜索进行实时路径调整。实验表明,该算法在解空间中有更好的探寻能力,并能快速收敛到全局最优,满足动态路径优化实时性要求。For the dynamic vehicle routing problem in logistics distribution, this paper built a multi-obiective and dy- namic mathematical programming model synthesizing dynamic demands, the effects on the road network, vehicle sha- ring, time window and customer satisfaction. This model can describe modern logistics distribution better. Meanwhile, the paper put forward a two-phase solving strategy for it. In the first phase,multi-objective hybrid particle swarm opti- mization is adopted to get preliminary Pareto solutions. The algorithm uses the modified updating strategy of particle states and simulated annealing operation to improve the searching performance of particles, and uses adaptive grid tech- nique to maintain the dispersion of solutions. In the next phase, greedy insertion and variable neighborhood search are applied to adjust routes according to the changes in demand. The experimental results show that the two-phase algo- rithm has better exploring ability in solution space,and it can also converge to the global optimum rapidly, and satisfy the real-time requirement.

关 键 词：物流配送 车辆路径问题 混合粒子群优化算法 模拟退火 PARETO最优解 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]