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

针对物流配送中动态车辆路径优化问题,综合考虑动态需求、路网影响、车辆共享、时间窗以及客户满意度,建立了多目标动态数学规划模型,该模型能更好地描述现代物流配送问题.同时,提出一种两阶段求解策略,第一阶段采用多目标混合粒子群优化算法获取预优化阶段Pareto最优解,采用改进的粒子状态更新策略并融合模拟退火操作提升粒子群搜索性能,采用自适应网格技术保持解的分布性;第二阶段对客户的需求变化采用贪婪插入和变邻域搜索进行实时路径调整.实验表明,该算法在解空间中有更好的探寻能力,并能快速收敛到全局最优,满足动态路径优化实时性要求.

Modeling and Optimization for Multi-objective Dynamic Vehicle Routing Problem

For the dynamic vehicle routing problem in logistics distribution,this paper built a multi-objective and dynamic mathematical programming model synthesizing dynamic demands,the effects on the road network,vehicle sharing,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 optimization 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 technique 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 algorithm has better exploring ability in solution space, and it can also converge to the global optimum rapidly,and satisfy the real-time requirement.