基于离散灰狼算法的带软时间窗车辆路径规划问题  

Vehicle Routing Problem with Soft Time Windows Based on Discrete Grey Wolf Algorithm

作　　者：康熙沛 杨家其[1] 丛喆 余昊[1] 向子权 KANG Xipei;YANG Jiaqi;CONG Zhe;YU Hao;XIANG Ziquan(School of Transportation and Logistics Engineering,Wuhan University of Technology,Wuhan 430063,China)

机构地区：[1]武汉理工大学交通与物流工程学院,武汉430063

出　　处：《武汉理工大学学报（交通科学与工程版）》2022年第4期598-603,共6页Journal of Wuhan University of Technology（Transportation Science & Engineering）

基　　金：吉林省交通运输厅交通运输科技计划项目(103-46160101)。

摘　　要：针对物流配送中对配送时效的要求,引入单位时间费用随时间变化的软时间窗,建立以车辆配送成本最小为目标的优化模型.应用离散灰狼算法求解该问题.由于标准灰狼算法只能求解连续型数值优化问题,引入交换算子(swap operator,SO)和交换序列(swap sequence,SS),并重新定义灰狼位置更新公式,使得灰狼算法可以求解带软时间窗的车辆路径规划离散问题.为了解决求解效率低和易陷入局部最优的问题,应用局部搜索(partial search,PS)技术优化离散灰狼算法.最后分别使用遗传算法和离散灰狼算法对同一算例求解,做对比实验.结果表明:离散灰狼算法可以有效求解带软时间窗的车辆路径规划问题,且离散灰狼算法在寻优能力和求解稳定性上均强于遗传算法.According to the requirement of distribution timeliness in logistics distribution,a soft time window with the change of unit time cost with time was introduced,and an optimization model aiming at the minimum vehicle delivery cost was established.The discrete grey wolf algorithm is applied to solve this problem.As the standard grey wolf algorithm can only solve the continuous numerical optimization problem,the Swap Operator(SO)and Swap Sequence(SS)were introduced,and the grey wolf position updating formula was redefined,so that the grey wolf algorithm can solve the discrete problem of vehicle route planning with soft time windows.In order to solve the problems of low solution efficiency and easy to fall into local optimum,Partial Search(PS)technology was applied to optimize discrete grey wolf algorithm.Finally,genetic algorithm and discrete grey wolf algorithm were used to solve the same example,and a comparative experiment was made.The results show that the discrete grey wolf algorithm can effectively solve the vehicle routing problem with soft time windows,and the discrete grey wolf algorithm is superior to the genetic algorithm in optimization ability and solution stability.

关 键 词：车辆路径问题 软时间窗 离散灰狼算法 

分 类 号：U491[交通运输工程—交通运输规划与管理]