带时间窗约束的多目标车辆路径优化研究与应用.pdf

摘要

摘要

随着经济的快速发展和城市化程度的提高，在人们生活和生产过程中物流活动急剧

增加。人们对高效合理的物流配送方案的需求越来越迫切，同时，物流活动带来的环境

问题也随着国家对绿色经济的提倡得到越来越多学者的关注。车辆路径优化问题作为物

流活动的根本问题，是通过对车辆行驶路线进行高效合理的规划，以达到运输成本最小

化的一类优化问题，其相关理论和算法对于现实生活有着不可缺少的价值。在物流配送

过程中，交通拥堵时常发生，如何在复杂情况下及时满足客户需求，最小化运输成本并

降低对环境的污染成为广泛关注且具有现实意义的课题。

本文的主要研究内容和创新点如下：

(1)时变环境下的带时间窗绿色多目标车辆路径优化问题模型的构建。现有的带时间

窗约束的车辆路径优化问题模型中对现实条件的考虑较少，往往只考虑了时间窗约束，

且现有模型考虑的求解目标单一，不能很好的反映实际配送过程对路径规划的要求。对

于以上不足，本文提出一种时变环境下的带时间窗绿色多目标车辆路径优化问题(Time

DependentGreenVechileRouteProblemwithTimeWindow,TDGVRPTW)模型，该模型同

时考虑三个目标，包括总运输成本、总行驶时间以及车辆数。并对容量、时间窗和道路

拥堵情况等约束以及碳排放量等成本进行考虑，相比以往模型更加符合实际情况。

(2)提出了一种改进多目标差分进化算法求解TDGVRPTW。随着车辆路径优化问题

求解目标数量的增加，算法求得优质解的困难明显增加，为了求得更好的解集，提出一

种改进差分进化算法用于求解TDGVRPTW。算法的改进主要体现在初始化阶段和变异

算子以及选择策略：在初始化阶段，提出反向Tent混沌初始化生成分布更加均匀的初始

化种群，提高算法的有哪些信誉好的足球投注网站范围；在进化过程中，设计了一种混合变异策略以及修补算子，

混合变异策略融合两种流行DE算子，修补算子对越界个体进行修补，防止后代种群越

界后聚集在解空间边界上；在选择阶段，设计一种自适应选择策略保留潜在解。提出的

改进策略较好的平衡了种群的多样性和收敛性。通过理论分析以及在Solomon基准数据

集以及真实MOVRPTW实例进行对比实验验证提出的改进算法的有效性。

(3)提出了一种基于协同进化框架的动态约束多目标优化算法求解TDGVRPTW。

VRP问题具有复杂的约束条件，而现有的VRP求解算法中，往往根据约束条件做出严

格限制以满足问题要求，未能充分利用约束条件信息对问题求解的作用。因此基于多任

务优化中简单任务辅助复杂任务求解的思想，设计了一种合作协同约束多目标进化算法

用于求解TDGVRPTW。该算法将完整的TDGVRPTW作为复杂任务，在求解复杂任务

时，选择过程引入同时考虑个体的分布和收敛信息的移位拥挤距离计算，较好的平衡种

群的收敛性和多样性。同时设计了一种动态约束选择策略用于简单任务的实现，简单任

务考虑部分约束条件对种群的影响。任务之间通过子代种群进行信息交互。在约束多目

标测试函数集、Solomon基准数据集以及真实MOVRPTW实例进行对比实验，实验结

果表明基于协同进化框架的约束多目标优化算法具有较好的综合性能。

关键词：车辆路径优化；碳排放；时间窗；多目标优化；协同进化；差分进化

Abstract

Abstract

Withtherapiddevelopmentoftheeconomyandurbanization,logisticsactivities

dramaticallyincreasedinpeoplesdailylifeandproductionprocesses.Theneedforefficient

andreasonablelogisticsdeliverysolutionswasbecomingincreasinglyurgent,while

environmentalproblemscausedbylogisticsact