混合遗传算法求解双目标带时间窗的车辆调度问题*

张 莹 张浩林

北京电子科技学院，北京市 100070

引言

在国际上，作为国民经济发展的支柱产业——物流行业，其发展程度已经成为衡量一国现代化程度和综合国力的重要标志之一。 物流配送作为物流行业的关键环节，其配送成本在物流成本的比重逐渐增大，减少配送成本，已经成为降低物流成本的主要途径。 早在1959 年，Dantzig 和Ramser 就提出了有关配送的车辆调度问题(Vehicle Scheduling Problem，VSP)，VSP 是经典的运筹学问题，该问题要求在满足一定的约束条件(如货物需求量、车辆容量限制、车辆行驶时间等)下，制定合理的行车路线有序地通过一系列装货点和卸货点，达到一定的目标(如路程最短、费用最小、耗时最少等)。 VSP 在物流运输、交通运输和工业管理等领域有广泛的应用，自提出以来就备受运筹学、应用数学、组合数学、网络分析、图论、计算机应用等学科专家与运输计划制定者和管理者的极大重视，他们相继进行了大量的理论研究及实验分析，取得了很大进展。 带时间窗的车辆调度问题(Vehicle Scheduling Problem With Time Windows，VSPTW)在VSP 的基础上增加了对客户要求访问的时间窗约束，它的出现是企业对其货物送达时间进行更高要求的结果。 对VSPTW 的研究不仅有助于运输企业提高服务质量，为客户提供更加精准、高效的服务，同时在节约成本、提升效率方面也有较为突出的贡献。 本文在传统带时间窗的车辆调度问题模型上，以最小车辆数和最短总行驶距离为目标建立双目标VSPTW 模型，并在遗传算法的基础上加入两元素优化算法，设计新的混合遗传算法求解该优化问题，最后用实验证明新建立的模型和设计的算法具有合理性和有效性。

1 模型

1.1 问题描述

VSP 是关于车辆调度的线性规划问题，该问题最初是为了求解使运输成本尽可能低的情况下应如何派遣车辆(包括车辆数、车辆行驶路线等)以满足客户的位置和货物量的需求。 随着社会生产力的发展，企业之间的竞争日益激烈，在这样的大形势下企业如果只是考虑运输过程中车辆运输费用或者是运输距离这样单一的有形成本是无法让企业实现利润最大化的，这就需要企业把如客户满意度这样无形的成本纳入其考虑的范围之内。

Buffa 和Jackson 在建立基于两类因素的物流公司配送绩效评价模型中将准时交货性纳入了供应商属性中，这表示在解决VSP 时要考虑到时间窗约束，也就是需要对VSPTW 问题进行研究，因为在运输企业运营的时候，提高客户满意度借此维系与老用户的关系所需要的成本，往往要比发展新客户的成本低，而提高客户满意度比较有效的手段，就是准时完成配送。

此外，还有一个重要的条件影响着运输成本，那就是用于配送的车辆数，通常情况下多一辆车的投入就代表着多一份固定成本的投入，而且多一辆车所增加的固定成本往往会超过缩短其配送路径所减少的成本，因而需要尽可能减少车辆的投入。 总得来说，单纯的对配送路线优化所具备的实际意义不大，需要在按照客户要求的时间窗送货的同时，寻求使车辆数尽量少的配送方案，于是本文要研究的是双目标VSPTW 问题——以最少车辆数为主要目标，最短路径为次要目标的VSPTW 问题。

双目标VSPTW 问题具体表述如下:一个配送中心拥有最大载重量为Q 的车辆K 辆，负责完成对给定的客户集N={1，2，…，n}的货物运输工作，已知客户i 的货物需求为gi(i=1，2，…，n)，且gi≤Q，完成对客户i 的货物配送所需的时间为Ti，且该客户希望的服务时间段为[ai，bi]，若车辆到达客户i 的时间早于ai则需要因等待而受到一定的惩罚，如果晚于bi同样会因迟到受到一定的惩罚，每个客户只能被一辆车服务一次，配送车辆完成配送任务后必须返回配送中心，最终目标是在车辆容量限制，时间窗限制等一系列限制条件下，找到使车辆数最少和车辆总行驶路线最短的车辆调度方案。

为能够更好的把实际问题抽象出来，还应做出如下假设:

1.本问题是单向送货问题，车辆只需完成送货任务，不需要取货；

2.配送中心和客户的位置坐标全部已知；

3.车辆在配送过程中不得超过其最大载重量；

4.客户的需求量已知；

5.每条路线都畅通，不会出现堵车等交通问题；

6.车辆类型相同且其最大载重量已知。

1.2 惩罚函数

若配送中心违反了客户的时间窗约束，势必会产生一定的经济损失，这些损失可认为是因违反客户时间窗约束而导致的时间效应成本，也可看作是配送中心违反客户时间窗时所面对的惩罚成本函数，一般车辆到达时间偏离时间窗约束越多，其惩罚成本越高。 本文假设惩罚成本为线性增加以简化问题。 在定义惩罚成本函数之前，对惩罚成本做如下假设:

1.惩罚成本以函数方式表示；

2.当车辆在客户时间窗内服务，配送中心不须支付任何惩罚成本；

3.时间窗宽度越窄者，其惩罚成本的边际效应越高；

4.车辆不论早到或晚到，随着违反程度的增加，惩罚成本呈直线增加。

定义的惩罚成本函数表达式如下:

上式可统一表示为:

其中，

ei——客户i 允许服务时间窗的始点

li——客户i 允许服务时间窗的终点

si——车辆到达客户i 的时间

p——车辆提前到达客户节点产生的等待单位时间的机会成本

q——车辆晚于时间窗到达客户节点的单位时间惩罚值

1.3 数学模型

所建立的双目标VSPTW 模型如下:

其中相关变量和符号定义如下:

N:需要进行货物配送的客户总量；

i，j:代表某一客户，i，j=(0，1…，N)，i，j=0时表示配送中心；

k:车辆编号，k=(1，…，K)；

cij:从客户i 到客户j 的运输距离；

α:车辆单位运输距离的成本；

β:每用一辆车所需要的固定成本；

Q:车辆的最大承载量；

di:客户i 的需求量，且max di≤Q；

ei:客户i 要求的货物最早送达时间；

li:客户i 要求的货物最晚送达时间；

si:车辆k 到达客户i 的时间点，其中s0=0；

tij:车辆从客户i 的位置行驶到客户j 的位置的时间；

fi:车辆在客户i 进行配送所需的服务时间；

wi:车辆如果在客户要求的ei之前到达所需要的等待时间，其中w0= 0；

M: 足够大的正数；

式(1-4)为首要目标函数，最小化调用车辆所需固定成本；

式(1-5)为次要目标函数，最小化行驶距离成本以及因迟到或早到所受到的惩罚成本；

式(1-6)表示从配送中心发出的车辆数应小于车辆总数K；

式(1-7)表示车辆的起止地点都是配送中心；

式(1-8)，(1-9)表示每个客户只能被一辆车服务一次；

式(1-10)表示车辆所分担的运送量不得超过车的最大容量；

式(1-11)表示车辆到某一客户的位置后必须要离开；

式(1-12)表示车辆须在规定的出发和到达时间内进行配送；

式(1-13)表示车辆从客户i 到达客户j 的时间约束；

式(1-14)表示xijk只能取0 或1；

式(1-15)是(1-2)所表示的惩罚函数的具体表达。

本文所建立的模型是在VSP 问题的模型上加入了如(1-12)、(1-13)等时间窗约束条件，此外当车辆数为1 时，本问题即转化为一般的旅行商问题，或者把模型中目标函数只设置为求最短车辆路径，此模型就成了求解最短车辆路径问题。 总得来说，本文所构建的模型考虑的因素比较全面，与实际情况更加符合，扩展性较强。

2 算法

本节将介绍加入两元素优化算法的混合遗传算法，具体算法步骤如下:

第一步:采用排列编码对客户进行编码，生成表达不同配送路线的染色体；

第二步:导入数据，生成个体，完成种群的初始化；

第三步:初始化迭代次数并开始记录，判断是否满足终止条件，若满足则输出结果，反之继续进行；

第四步:开始循环，开始计算个体适应度；

第五步:判断是否满足循环终止条件，若满足返回上一步，反之进入下一步；

第六步:比较个体适应度，通过锦标赛选择法对个体进行筛选；

第七步:进行交叉并通过两元素优化算法实现染色体变异，保持种群个体中染色体的多样性；

第八步:记录进化代数，判断是否满足算法终止条件，若满足则输出结果，反之返回第三步。

2.1 编码与解码

编码是设计遗传算法所需要解决的第一个问题，合适的编码方式能为运用遗传算法解决实际问题打下坚实的基础。 本文所研究的双目标VSPTW 是一种十分具有代表性的需要考虑次序的组合优化问题，其有效解集是车辆访问客户的路径组合，因此为了减少生成无效解，本文选择排列编码这一编码方式。 具体如下:0 代表配送中心，1--n 代表顾客；不同车辆的配送路线之间用0 分隔；对于有n 个顾客，k 辆车的VSP 问题，染色体长度为n+k+1。 这样的编码方式把配送中心0 作为不同路径的分隔符，有利于下面对染色体进行处理。 例如配送中心有3 辆车为9 个客户服务，一条可能的染色体为(0，2，9，0，1，7，3，6，0，8，4，5，0)，这条染色体表示的三辆车的行驶路线为:

第一辆车:0-2-9-0

第二辆车:0-1-7-3-6-0

第三辆车:0-8-4-5-0

解码是编码的逆过程，本文所设计的解码就是根据分隔符0 将染色体还原成单个路径。

2.2 初始化种群

遗传算法是一种在多组数据中进行搜索的算法，因此需要建立由多个个体组成的群体，该群体为遗传算法的起点。 种群规模的大小影响算法结果的可靠性和算法的运行速度，当种群规模过小时，算法很容易陷入局部最优解，而选用较大的群体则可避免这种情况的发生，但使用大规模的群体却会降低算法的效率。 所以一般情况下，种群大小设置在20 ～200 之间。 此外种群个体分布是否均匀也影响算法能否尽可能的跳出局部最优，因此在生成初始种群时采用了随机生成pop_size 个1 到n 个自然数的全排列，并向序列中插入k+1 个0，此序列必须要满足在首尾分别有一个0，且不会出现两个0 连续出现的情况，这pop_size 个个体即为初始种群，其中n 为客户数，k 为车辆数。

2.3 选择

选择的目的是为了避免前一代种群中良好的表现型被遗漏，因此要将这些个体通过复制的方法保存下来，引入下一代产生新的种群，从而逐渐提高种群的适应度。 如果把整个遗传算法比作生物进化的全过程，那么选择就是选择“适者”让其生存，同时淘汰“劣者”。

本文采用的是二元锦标赛选择法，其原理是进行有放回取样，每次从种群中取出两个个体，比较其适应度大小，选择适应度最好的一个进入子代种群，然后不断重复该操作，直到选出的新种群规模大小与原种群规模大小相同为止。 具体的操作步骤如图2-1:

2.4 交叉

交叉模仿的是生物通过交配交换染色体，从而产生新个体的过程。 在遗传算法中交叉就是用于交叉父代种群中个体的染色体从而产生新个体的过程。 这一操作不仅在一定程度上保留了上一代种群中适应度较高的个体基因型，而且还给算法留出了探索新基因型的空间，交叉可以让新的种群继续保持基因型的多样性，从而降低出现局部最优的可能。 通常情况下交叉率在0.6 到0.9 之间。 本文采用的交叉操作其实现过程如图2-2、2-3:

2.5 变异

变异是生物个体基因型突变的情况，这种方法是在一定的概率下，随机改变个体的基因型，虽然这种概率一般比较低，但对于保持群体的多样性起到了辅助作用。 本文所选用的变异方法是借助两元素优化算法来完成。 通过这一变异操作可以在保证车辆数不变的情况下对车辆路径进行优化。

2.6 适应度函数

适应度函数又叫评价函数，是用来判断个体应该被淘汰还是保留的有效工具，本文求的是最小值问题，选取的目标函数值是正值，因此在算法设计时只需要将评价函数设置为求目标函数最小即可。

2.7 终止条件

遗传算法求解问题是一个循环演化的过程，必须要提前设置好终止条件，算法满足要求时便停止循环。 本文的终止条件是提前设置进化代数，应用终止条件的主要原理是每次迭代后判断是否达到提前设置的种群代数，如果达到了则输出结果，反之则继续运行，这一方法可以使算法的运行时长和精准度得到有效约束。

3 实验

3.1 实验数据

实验数据来自Benchmark Problems，Benchmark Problems 是Solomon 在1983 年设计的VRPTW 标准测试题库。 该题库中实例皆假设求解单一配送中心和单一车种的VRPTW，每个客户有相应的时间窗约束及一定的需求量，每辆车有最大允许载重量，每两个客户点间的几何距离即为它们之间的运行时间。 本文采取的数据是R101、R102、R103、R104、R105、C101 中的前26 位，分别记作R10126、R10226、R10326、R10426、R10526、C10126。

3.2 参数设定

(1)模型参数设定如表3.1:

表3.1 模型参数设定

(2)遗传算法运行参数设定

算法参数设定如表3.2 所示:

表3.2 遗传算法参数设置

3.3 结果分析

实验是在处理器为Intel(R)Core(TM)i7-6700HQ CPU @ 2.60GHz 2.59 GHz、已安装的内存(RAM)为16.0 GB(15.8 GB 可用)、操作系统为Windows 10 的计算机上运行的，采用Python 编程，得到的结果如表3.3 所示:

表3.3 实验结果

本算法在生成种群时是按照车辆逆向装载的方式构造初始种群，通过观察实验结果可知，这种种群构造方式比完全随机生成种群更容易贴近最优解，避免了超过车辆最大承载量而导致解为无效解这一情况。 较好的实现了所需车辆数最少这个首要目标和行驶路径最短这个次要目标。

在求解过程中，算法所获得解的最小适应度值和平均适应度值如图3-1 所示:

通过图3-1 可以看出随着优化代数的增加，种群平均适应度值逐渐开始收敛，而种群最小适应度值则保持相对稳定，本算法最优解的收敛速度也较快。

4 结语

在实际问题中投入一辆车所消耗的固定成本要远远高于优化路径所节约的成本，因此本文建立的以最少车辆数为主要目标、以最优化总路径为次目标的带时间窗的车辆调度问题比以最优化总路径为单一目标的车辆调度问题更贴近现实，同时也更节约成本。 利用遗传算法的锦标赛选择法和序列编码等方式使得解满足时间、路程等约束条件；同时，利用两元素优化算法对车辆行驶路径进行局部优化，由此设计了出新的、使所需车辆数尽可能少的混合遗传算法。 最后通过实例对模型和算法进行测试，求出对应双目标VSPTW 的解决方案，证明了本文所建立的模型和算法均具有合理性和有效性。