求解带有同时取送货和时间窗的改进遗传算法

摘要：针对带有同时取送货需求和时间窗约束的车辆路径问题，运用改进遗传算法进行求解，引入新的交叉算子，增加了种群多样性；对变异概率进行自适应调整，保留适应度较优的染色体。以某企业在天津市的多家社区连锁超市为研究对象，求解出适合该企业的最优路径。结果表明：为满足各超市的时间窗需求，企业需改进现有配送方案。

关键词：车辆路径问题 同时取送货 时间窗 改进遗传算法 自适应调整

中图分类号 TP301.6 文献标识码 A

引 言

有时间窗的同时取送货的车辆路径问题（Vehicle Routing Problem of Delivery and Pick-up with Time Windows， VRPDPTW） 是VRP的一个重要扩展，对每一个客户点的服务（取货和送货）时间进行了约束[1]。VRPDPTW在现实中有着广泛的应用。送奶工人送去鲜奶的同时要取走原先的奶瓶；配送车辆为超市补充货源，并取走需要退回的产品或包装箱等。

有时间窗的同时取送货的车辆路径问题的描述

本文VRPDPTW问题，涉及一个配送中心和N个客户点，一个有K辆车型相同的车队且每个客户仅由一辆车服务，配送中心是车辆的始点与终点；配送工作在规定的时间窗内开始；货物只考虑重量约束，每个子路径上所有客户点的送货量和取货量不超过配送车辆的最大容量C；优先使距离之和最短，同时保证配送时间较短。

取货与送货时间均为；为点i到点j的运输时间，分别为开始时间与完成时间，其中，且。

2 改进遗传算法的步骤

本文采用改进的遗传算法求解VRPDPTW问题。

（一）染色体的编码

本文采用整数编码，将不相同的整数（1，2， …N）全排列，组成一个长度为N-1的染色体，种群规模为。

（二）遗传操作

图 1两点异位交叉

为防止适应度值较高的染色体变异，采用倒位变异。在服从的正态分布情况下，对变异概率进行自适应调整[2，3]：

。

求解过程如下：

因为在正态分布中，所以：

通过方程（2）（3）求得的代入到（1），所以变异概率自适应机制可表示为：

这就使变异概率只于适应度值与期望有关，而不再是人为地对变异概率进行赋值，减少人为主观因素对变异操作的影响。

划分路径

随机给每个客户点的送货量赋值，取货量Pi=送货量Di×一定比例。基于送货量划分出子路径，优先配送时间窗下限。

（四）算法终止

本文采用时间标准，即当进化次数达到预先设定的最大进化迭代次数MAX时，算法终止。

3 计算实例与结果分析

（一）算法参数

本文对某公司在天津市内6区的246家社区连锁超市进行分析。配送中心和超市的坐标通过百度拾取坐标系统获得，测量比例尺为1：1000000。配送中心与超市之间的距离通过公式作近似计算得出。其中N= 246，Num=100，MAX=1000，C=30，p=0.6。

（二）结果分析

从图2看出，加入取送货和时间窗后，相邻超市并不是由同一车辆进行配送服务，这说明最佳配送路径并不是按“服务临近区域”的原则服务市内6区的超市，所以该公司需要适当地改进现有配送原则，既可以满足各超市的时间需求又可以节省配送成本。

图2 部分超市的配送路径图

4结 语

求解有时间窗的同时取送货的车辆路径问题，本文采用了改进的遗传算法，引入两点异位变异并对变异概率进行自适应调整，使求解结果更准确、有效。社区连锁超市的最优配送路径图显示出，传统“服务临近区域”的原则并不可行的，需要改进，体现了论文较好的实用价值。

参考文献

李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京： 中国物资出版社，2001：132-133.

龙磊，陈秋双，华彦宁，等.具有同时集送货需求的车辆路径问题的自适应混合遗传算法[J].计算机集成制造系统，2008，14（3）：548-556.

侯玲娟，周泓，梁春华.不确定需求和旅行时间下车辆调度问题研究[J].计算机集成制造系统，2011，17（1）：101-108.

作者简介：

刘俐 （1989―），女，硕士研究生，主研领域：物流与供应链管理；

侯玲娟（1984―），女，讲师，博士研究生，主研领域：生产与物流系统管理中的优化理论与算法研究；