带时间窗装卸货问题的改进多策略分组编码遗传算法

郭东威，丁根宏，刘 伟

(1．周口师范学院数学与统计学院，河南 周口 466000；2．河海大学理学院，江苏 南京 211100)

1 引言

带时间窗装卸货问题(Pickup and Delivery Problem with Time Windows，PDPTW)是指为一个位于车场的车队安排服务路径来满足客户的装卸货及运输需求。每个需求任务包括两个需求点(客户点)：一个装货点和一个卸货点。每个需求点都有一个时间窗口，即在该点装货或卸货的最早开始时间和最迟开始时间。车辆不能迟于最迟开始时间到达需求点，可以早于最早开始时间到达，早到的车辆需要等到最早开始时间才能进行服务。同一个需求任务必须由同一辆车进行服务，即完成一个需求任务是指同一车辆在规定的时间窗内先到该需求任务的装货点装货，再到其卸货点卸货。组成车队的每辆车具有相同的最大负载量，且车辆数目足够多，每辆车从车场出发，完成配送任务后返回车场。如何安排配送路径，在满足约束条件下完成所有需求任务，并且使得所需车辆数最少，行驶总路程最短，等待总时间最少。PDPTW在现实中已有广泛的应用，如物流配送、公交路线安排等。

根据车辆数可以将PDPTW分为两类：一类是单车带时间窗装卸货问题(Single-vehicle Pickup and Delivery Problem with Time Windows，1-PDPTW)，指只有一辆车完成所有配送任务；一类是多车辆带时间窗装卸货问题(Multi-vehicle Pickup and Delivery Problem with Time Windows，m-PDPTW)，指有多辆车共同完成所有配送任务。本文研究的PDPTW指的是m-PDPTW。PDPTW属于组合优化中的NP-hard问题，求其最优解十分困难。已有文献的求解方法大致可分为两类：精确算法和启发式算法。Psaraftis[1]和Desrosiers等[2]分别应用动态规划算法求解了1-PDPTW。Dumas等[3]1991年应用分枝定界法成功解决了30个需求点以内的m-PDPTW。动态规划算法及分枝定界算法只能求解小规模的PDPTW，求解大规模问题主要采用启发式算法。2000年Nanry和Barnes[4]提出了求解PDPTW的禁忌搜索算法；Li和Lim[5]提出了禁忌模拟退火混合算法，在Solomon[6]的VRPTW算例基础上构造了PDPTW算例，并求出了近似最优解；Jung和Haghani[7]2000年用遗传算法快速有效的求解了小规模(30个需求点)的PDPTW，但是基本遗传算法求解大规模的PDPTW效果较差。2002年Jih等[8]提出了家族竞争遗传算法(FCGA)来求解1-PDPTW，2005年Pankratz[9]提出了求解PDPTW的分组编码遗传算法(Grouping Genetic Algorithm)，对规模为100个客户点的标准算例进行求解取得了较好的结果。国内对PDPTW的研究相对较少，能够查阅到的文献非常有限。早期的研究成果主要有：蓝伯雄和张跃[10]提出了求解PDPTW的概率式禁忌搜索算法，与非概率式禁忌搜索算法比较，提高了求解效率和精度；贾永基等[11]提出了一种快速禁忌搜索算法，该算法易于改进，可通过简单的变化来求解多约束的PDPTW 问题。近年来的研究成果主要有：潘立军和符卓[12-13]提出了一类时差插入检测法，比已有的插入检测法具有更快的检测速度；2014年Ding Genhong等[14]为了对分组编码遗传算法中得到的近似最优解进一步优化，在分组编码遗传算法中增加了路径调整策略，提出了多策略分组编码遗传算法(Multi-Strategy Grouping Genetic Algorithm，MSGGA)。此外，不少专家学者最近对一些变式问题进行了研究，2017年符卓等[15]用禁忌搜索算法求解了带软时间窗的需求依订单拆分车辆路径问题，颜瑞等[16]研究了二维装箱约束的多车场带时间窗的车辆路径问题。纵观国内的研究，不难发现所有文献中求解的算例均为100或200个客户点[12,14]或者是作者本人根据VRP算例构造的小规模算例[10-11]，像400个客户点或更多客户点的算例在已有文献中尚未求解。因此，对于PDPTW还需要进一步进行深入的研究。

经研究发现文献[9]中的组合交叉算子不宜减少车辆数，文献[10]中提出的路径调整策略均具有随机性，针对这两个问题本文提出了易位组合交叉算子、单车路径重排策略及需求对换策略，并求解了400个客户点的PDPTW标准算例。

2 PDPTW的数学模型

假设车辆的数目足够多，每辆车的最大载货量为Q。需求任务的个数为L，设需求任务i的装货地点为i，卸货地点为L+i，配送中心用0和2L+1表示。这里不同的点可能代表相同的物理位置，比如某个需求任务的装货点和卸货点可能在同一个物理位置(坐标相同)。设N={1,2,…,L,L+1,…,2L}为客户点集，即所有装货点与卸货点的集合。P+={1,2,…,L}为装货点集合，P-={L+1,L+2,…,2L}为卸货点集合，M={1,2,…,m}为可调用车辆集，V={0,2L+1}为配送中心集，N*=N∪V表示客户点与配送中心集。客户点i的货物需求量为qi,i∈N，qi的正负分别表示车辆在此装货和卸货，如果是装货，则需要车辆把货物从点i运送到点L+i。[ei,li]和[eL+i,lL+i]分别表示需求任务i的装货时间窗口和卸货时间窗口，每辆车必须在时间窗[e0,l0]内从配送中心出发，在时间窗[e2L+1,l2L+1]内返回配送中心。对∀i,j∈N*，tij代表从点i到点j的运输时间，cij表示从点i到点j的距离。设zik表示车辆k行驶到客户点i时的负载量，Aik表示车辆k到达客户点i的时间，si表示车辆在客户点i的服务时间，则Wik=max{ei-Aik,0}表示车辆k在客户点i的等待时间，si+Wik表示车辆k在客户点i的停留时间，ti+si+Wik表示车辆k离开客户点i的时间。

定义变量：

PDPTW的数学模型

多目标函数：

minm

三个目标函数分别表示使用车辆数最少、总行驶路程最短、总等待时间最少。

约束条件1：每个客户点只能由一辆车服务

约束条件2：每个客户点只能被服务一次

约束条件3：变量xijk与yik之间满足的关系

约束条件4：同一个需求任务必须被同一辆车服务，且装货在前卸货在后

Aik≤AL+i,k，∀i∈P+,∀k∈M。

约束条件5：车辆必须从配送中心出发到某一装货点，最后从某一卸货点返回至配送中心

约束条件6：时间窗限制

e0≤A0k≤l0，∀k∈M；

Aik≤li，∀i=1,2,…,2L+1,∀k∈M；

约束条件7：车载容量限制

0≤zik≤Q，∀i∈N,∀k∈M；

zjk=xijk(zik+qi)≤Q，∀i,j∈N,∀k∈M。

3 求解PDPTW的改进多策略分组编码遗传算法

3.1 分组编码方案

编码方式是遗传算法实现的关键，Falkenauer[17-18]提出了一种分组编码方案，2005年Pankratz G[9]首次将这种分组编码方案用于求解PDPTW，编码方式描述如下。

分组编码的每个个体(染色体)包含若干个基因，基因的个数就是所需的车辆数，每个基因代表安排给某一辆车的所有客户点及满足前序、负载、时间窗等约束的行驶路径。因此，每个个体(染色体)都是问题的一个可行解。例如，在某个PDPTW问题中需要3辆车对7个需求任务服务，假设车辆1负责需求任务1、3、5，车辆2负责需求任务2、7，车辆3负责需求任务4、6。图3.1就是分组编码的示意图，它表示包含3个基因的一个染色体(问题的一个可行解)。

图3.1 分组编码示意图注：0表示车场，+i表示装载点，-i表示卸货点。

3.2 初始种群的生成及启发式插入算法

初始种群的生成及交叉、变异算子中都要使用这种启发式插入算法[9]，它保证了在产生解的过程中路径的可行性。算法描述：1)选取未安排需求i；2)对个体中的所有单车路径插入需求i，并检验插入的可行性(包括前序、负载、时间窗的限制)；3)计算所有可行插入方案各自增加的代价(行驶路程、等待时间)，选取代价最小的插入方案；4)如果当前没有路径可以插入需求i，则新增一辆车安排需求i；5)重复1)到4)，直到所有未安排的需求被插入。

3.3 排序保优操作

在求解最优路径的迭代过程中，总希望获得更多的适应度值较好的个体，为此本文在算法中对种群进行排序保优操作，即计算个体的适应度值，将一定个数的最优个体进行复制保留，直接作为下一代的个体，然后再进行下一步遗传操作。本文中，每次经过遗传算子(交叉和变异)得到的种群都要进行排序保优操作，使得适应度值好的个体被保留下来，进行繁殖遗传到下一代。

3.4 交叉算子

交叉算子影响着遗传算法的收敛速度和最优解的产生，好的交叉算子能够加快算法的收敛速度和最优解的产生。交叉算子的设计一般依赖于编码方式，本文改进了文献[9]中的组合交叉算子，提出了一种易位组合交叉算子。

1.首先选取两个个体作为父代，确定交叉基因片段。例如，假设有8个需要服务的需求任务，如图3.2所示(省略车场0)，随机确定两个父代中需要交叉的基因片段。为方便表达，被选定的基因片段用方框框起来。

图3.2 父代个体选取图示

2.将父代1、父代2选中的基因片段易位，并分别插入到父代2最左端的位置和父代1最左端的位置，如图3.3。交叉后会出现一部分需求任务被两辆车服务的情况(如子代1中需求1和6，子代2中需求4)，而且有可能出现同一辆车被安排了两条路径(如子代1中的车辆1)。

图3.3 易位组合交叉图示

3.为消除需求任务和车辆重复的情况，将原父代中与插入基因片段中相同的需求任务取出，设为未安排状态。同时，将与插入基因片段重复的车辆去掉，该车辆服务的需求任务设为未安排状态。操作结果如图3.4。

图3.4 消除重复情况

4.按启发式插入算法将这些未安排需求任务插入两个子代中。一般，子代1中重复的需求被插入子代2中，子代2中重复的需求被插入到子代1中。重复需求被重新插入之后，去掉重复车辆后剩下的需求仍被插入到原来的子代中。在插入的过程中必要时可以增加额外的车辆以确保路径的可行性。操作完成后可获得两个完整的子代，如图3.5所示。

图3.5 交叉子代图

因为组合交叉法[9]是将父代1(父代2)选定的基因片段直接插入到父代2(父代1)中，如图3.6所示，这个交叉操作在两个父代中都增加了车辆，然后再进行3、4两步的操作(消除重复)，因此最终交叉结果要比易位组合交叉的结果容易增加车辆。当然，两种交叉方法的结果也都可能减少车辆。

图3.6 组合交叉示意图

3.5 变异算子

本文采用文献[9]中的变异算子，其主要步骤为：1)从个体中随机选择若干个基因；2)删除选中基因的车辆，同时这些车辆服务的客户点设为未安排状态；3)将这些未安排的客户点用启发式插入算法重新插入该个体中，必要时可以安排新的车辆。

3.6 路径调整策略

本文采用两种路径调整策略，以增加算法的寻优效果。

A．单车路径重排策略

算法描述：

begin

随机选择个体P中的某个基因(车辆路径)i；

在路径i中随机选择l个需求任务(2l个客户点)进行满足前序限制的全排列；

计算满足约束条件的排列的代价，保留代价最小的排列，得到新个体P′；

end

B．需求对换策略

通过对比不同解的结构发现，交换个体P中两条路径中的需求，可以优化路径。

算法描述：

begin

随机选择个体P中两个基因(车辆路径)i,j；

在路径i,j中分别选出对换需求crossi,crossj；

交换crossi,crossj的位置；

if操作可行并能使代价减少

交换crossi,crossj的位置；

end

end

3.7 适应度函数

在遗传算法中，适应度是区分种群中个体优劣的唯一标准，是算法进化的动力。一般适应度函数是根据优化的具体问题，按一定的规则由目标函数值转化得到。

PDPTW问题比较复杂，一般存在多个优化目标，例如车辆数最少，行车总路程最短，总等待时间最少等。本文设计了一个带权重的目标函数，即分别对总路程，车辆数加权求和作为目标函数。设kd为行驶总距离的权重，kv为车辆总数的权重。根据具体需要，可以灵活设置kd、kv的值，以达到所要侧重的目的。一般认为，使用车辆数要比行驶距离重要的多，那么可以设置kv的值远大于kd的值。本文设计的目标函数为：

根据对适应度函数的要求，适应度函数设计如下：

f=zmax-z，

其中，zmax是一个很大的数值，可以取目标函数值的一个上界，也可以取当前种群中或到目前为止目标函数值的最大值。

3.8 改进多策略分组编码遗传算法(IMSGGA)

本文根据上述步骤，包括启发式产生初始种群、分组编码、排序保优、易位组合交叉、变异、单车路径重排策略、需求对换策略等设计了改进多策略分组编码遗传算法(IMSGGA)。在算法中分别对两种调整策略设置了迭代参数，即在不同的迭代次数发生不同的调整策略，参数可以视情况具体调整。下面给出IMSGGA算法描述。

IMSGGA算法描述：

input：popsize(种群规模)，m(最大迭代次数)，m1，m2 (调整策略发生时的迭代次数)

begin

启发式初始化种群P；

计算种群P中每个个体的适应度值，保存适应度值高的个体；

iteration=0；

while(iteration≠m)

对P中的个体进行交叉操作，产生新种群P′；

计算P′中个体的适应度值，排序保优；

ifiteration≥m1

对种群P′实施单车路径重排策略，形成新种群P″；

else

对种群P′进行变异操作，形成新种群P″；

计算种群P″中个体适应度值，排序保优；

iteration++；

end

ifiteration≥m2

对当前种群实施需求对换策略；

iteration++

end

end

return种群中最优个体作为问题的最终解；

end

4 算法测试

4.1 算例说明

本文采用400个客户点的国际通用算例集来测试本文算法的性能。算例集共包含60个算例，每个算例至少有400个客户点。根据客户点的分布情况分为以下几类：lc1和lc2的客户点分布呈聚集状态，可分为若干聚集块，lr1和lr2的客户点分布散乱无规律可循，即它们的客户点分布随机，lrc1和lrc2的客户点分布既有随机性又有聚集性。

4.2 测试结果

对本文算法编程实现并在PC(Intel(R) Core(TM)，2.10GHz)机上运行。由于算法的本质具有一定的随机性，对每个算例进行多次运算，取最好的结果与目前已知最好解进行比较。算法运行时种群规模设为10～200不等，迭代次数设为100～5000不等。实验表明，有些算例种群规模设为10～30，迭代次数100～200，只需几秒时间就得到了与目前相同的已知最优解，而有些算例种群规模设为30～200，迭代次数达5000次，依然没有得到最优解。适应度函数中车辆数权重为10000，距离权重设为1。测试结果见表4.1，14个算例结果与目前最优解相同，4个算例lc2_4_3、lrc1_4_1、lrc2_4_2和lrc2_4_3的行驶总路程有所减少。算例符号说明，以lc2_4_3为例，它表示客户点分布情况属于lc类(客户点分布呈聚集状态)，4表示400个客户点的算例，3表示lc类的第3个算例。

表4 1 400个客户点算例结果比较

5 结语

本文研究了求解PDPTW的多策略分组编码遗传算法，主要改进了GGA的交叉算子和MSGGA的路径调整策略，即提出了易位组合交叉算子、单车路径重排策略及需求对换策略。基本的遗传算法是基于种群的并行搜索机制，仅仅采用了选择算子、交叉算子及变异算子来更新种群。路径调整策略是基于个体的搜索机制，是对并行搜索机制很好的补充，有助于维持种群的多样性及优异个体的产生。文中设计的路径调整策略不仅适用于求解PDPTW，也同样适用于求解其它类型的车辆路径问题。通过求解400个客户点的PDPTW通用算例集，将求解结果与已知最优解对比，结果表明了本文算法的有效性。但该算法并没有得到所有算例的已知最优解，因此还需要进一步研究改进。我们相信在算法中增加合理的路径调整策略可以提高算法的性能，在设计启发式搜索算法中有良好的应用前景。此外，本文设计的算法易于改进，只需稍微改变就可以用来求解类似的问题。例如快递公司带时间窗的信件收发问题(CCPDPTW)、带时间窗的电话叫车问题(DARPTW)、带时间窗的残疾人接送问题(HTPTW)、飞机航线规划等。