配送时间窗约束下车辆调度遗传算法研究

黄瑞铭 （中海油田服务股份有限公司，河北 三河 065201）

·交通运输·

配送时间窗约束下车辆调度遗传算法研究

黄瑞铭 （中海油田服务股份有限公司，河北 三河 065201）

在中海油田服务股份有限公司的生产物资配送中，不但要满足各个钻井平台对实物的需求，还要满足船期对配送时间的限制，针对各个钻井平台的订单往往会考虑一定前置期的特点，钻井平台上尽量减少库存，对配送服务的时间要求比较严格，因此及时配送变得越来越重要[1]。满足钻井平台对配送时间窗的限制，是制定配送车辆路线应该优先考虑的问题[2]。因此，本文主要选择带时间窗约束的VRP问题进行研究。

对配送路线进行优化，一般都要求符合以下约束条件：

（1）必须满足钻井平台对货物到达的时间或时间窗的要求；

（2）对每一辆运输车辆的装载容量有一定的限制，不允许装载量超过车辆的载重量和容量；

（3）满足钻井平台对货物规格、品种和数量的要求，且一次完成配送；

（4）员工休息时间的限制 （工作时间、用餐时间限制）；本文构建的模型所考虑的主要约束条件如上所述[3]。

1 模型建立

1.1 时间窗问题

在进行货物配送时，若采购计划没有对配送的时间提出要求，那么物供中心可以根据自己的配送进程来组织车辆配送，但如果采购计划要求在规定的时间段内完成货物的配送，这就需要考虑钻井平台对时间的要求，VRP问题转化为VRPTW问题[4]。

设完成任务i需要的时间 （包括装货、卸货）为Ti，同时任务i的开始时间必需要在规定的时间窗 （ETi,LTi）内，其中ETi表示为任务i最早的允许开始时间，LTi为任务i最迟的允许开始时间。如果配送车辆到达任务i的时间早于ETi，车辆必须在i处的码头等待装船，如果配送车辆到达任务i的时间晚于LTi，任务i要等下个船期才能进行运输。若ti表示车辆到达i点的时间，应满足关系式ETi≤ti≤LTi。VRPTW问题中的时间窗限制又可以分为软时间窗问题和硬时间窗问题，其中软时间窗VRPTW表示如果配送车辆无法在要求的时间窗内将货物送达钻井平台的客户手中，则必须按照违反时间的长短支付一定的惩罚费用；硬时间窗VRPTW表示每项任务必须在规定的时间范围内将货品送达钻井平台的客户手中，不论是早到或迟到都完全被接受。相对于软时间窗而言，如果车辆在ETi之前到达任务点i，车辆在i处等待，产生了机会成本的损失。如果车辆在LTi之后到达任务点i，服务被延迟，必须支付一定的惩罚费用：对于硬时间窗VRPTW来说，当货品送达的时间超出时间窗范围时，其惩罚值定义为一个非常大的正数M，这表示在硬时间窗的限制下，如果服务超过时间窗范围，配送成本巨大，此时的解为不可行解。

1.2 改进惩罚函数

若配送作业违反了采购计划的时间窗约束，势必会造成采购计划的延迟，从而造成企业的损失，配送作业的目标是在追求成本最低化的情况下，实现企业生产利润的最大化。因此有必要将时间成本考虑在内。

在油田生产过程的配送中，钻井平台会在一定程度的时间范围内接受配送服务，而超过这部分的时间范围，会对企业的生产造成影响，我们选择用图1所示的罚函数。

图1 有时间窗的配送损失量函数

在时间窗左侧的是提前到达的情况，这一段时间的函数线条比较平缓，表示，虽然会有惩罚，但是能忍受提前到达的时限范围较长，因为不会造成生产损失；而在时间窗右侧的是滞后到达，这种对企业生产造成的损失巨大，所以线条斜率较大。其中时间区间 [ETi,LTi]表示钻井平台可以忍受的最大损失的服务时间范围，而 [ETd,LTd]表示钻井平台能进行配送服务的时间范围，即模糊预约时间。

从模糊预约时间的界定可以知道，钻井平台损失量可以通过关于模糊预约时间的函数来表示，对于钻井平台i来说，当服务开始的时间为ti时，钻井平台损失惩罚函数可以表示为：

1.3 改进交叉算子

本文采用启发式遗传算法的基因换位算子来实现染色体的交叉，过程如下：

（1）首先在两个父代字符串A，B中随机地选择一个交叉点，并且A，B中随机的选择一个交叉点后的码头作为第一个子染色体对应位置需访问的码头；

（2）将B中对应位置的6与3交换，以避免以后发生结点重复遍历的现象；

（3）比较A，B中结点6与后面结点的距离，如果c61＞c67。，则选择B中的结点7作为子代对应位置的结点，交换A中1与7的位置，以避免后面发生结点重复遍历的现象；

（4）如此反复执行 （3）中的操作，直至遍历完两父代字符串的所有结点，此时得具有同时配送和收集需求的车辆路径问题研究到一个子代字符串。

例：A:8 2 0 7 4 0 5|6 0 1 3 A':8 2 0 7 4 0 5|6 0 1 3

父代B:5 4 1 0 7 8 0|3 6 0 2 B':5 4 1 0 7 8 0|6 3 0 2

子代C:*******|6***

采取该算法，即使种群中所有个体都相同，也不会影响算法的运行。这样就很好的摆脱了传统遗传算法对种群多样性的要求，较好的解决了传统遗传算法中早熟和收敛的问题。

1.4 车辆调度模型的建立

为构建上述模型，先建立如下变量：

模型的目标函数如下：

式中：式 （2）为目标函数，表示使车辆完成配送任务时的总配送费用最小，由以下几个部分组成：总配送距离产生的成本，加班工作产生的额外成本，车辆延时造成的配送成本，车辆提前到达增加的配送成本和违反时间窗要求对生产计划造成的损失量，式 （3）为车辆的装载能力约束，表示某车运输所装载的物资总量不能超过该车辆本身的最大载重量；式 （4）、式 （5）表示到达某一码头的车辆的约束，即每一个码头可以最多有n辆车同时进行装卸；式 （6）用来确保平台i由总共小于n辆车完成配送任务。其中，θtp表示第p辆车的行车时间，t0为发车时间，为收车时间；eθtp表示第 p辆车的加班时间，eθtp=max

2 车辆调度遗传算法案例

2.1 问题描述

处理过的塘沽物供中心的数据如表1、2所示：

表1 库房和码头之间的距离表

表2 码头装船8点到9点之间的配送量和配送时间窗

2.2 编码及初始种群的生成

由于VRP问题用二进制编码具有先天性的不足，为了弥补这一缺的，本案例采用序数编码，其中0代表库房，自然数表示码头的编号，本案例中有8个码头，随机产生一个序列23786154，然后按以下步骤进行染色体的生成操作：

（1）从左向右累计码头需要运输量，一旦累计运输量大于运输车辆容量时，记录此时的累计次数i，记录断点一为i-1，累计量清零；

（2）从序列的第i个数字重新累计码头需要运输量，当累计需求量大于运输车辆容量时，记录此时的次数j，记录断点二为i+j-l，累计量清零；

（3）重复以上操作直至结束，生成断点集；

（4）对断点集进行操作，在每个断点的后面插入 “0”，表示重新从库房出发；

（5）在序列首未位添加 “0”，染色体生成完成。

现以序列23786154为例说明解码过程，设生成的断点集合为式3,6,（）5 ，则首先在序列的第2、第5及第7位后加 “0”，序列变为23078601504。然后在序列前段加 “0”，则染色体为023078601504，表示配送方案由4条路线组成，其中运输车辆l的路线为：库房0—码头2—码头3；运输车辆2的路线为库房0—码头7—码头8—码头6；运输车辆3的路线为库房0—码头1—码头5；运输车辆4的路线为库房0—码头4。至此完整的染色体生成，然后通过重复染色体生成过程，直至达到种群规模，即为算法的初始种群。

2.3 选择算子

选择算子的实现具体操作如下：

（1）首先随机生成n组序列，通过序列加 “0”，生成n个染色体；

（2）对这n个染色体进行按适应函数进行适应值fk计算；

（5） 生成呈均匀分布的随机数r（ 0≤r≤1 ）， 若r≤d1， 则选择第1个染色体， 若以dk-1≤r≤dk（l=2,3,…,n ），则选择第k个染色体，重复以上操作直至选择的染色体达到种群规模。由于选择的随机性，在染色体选择后，当代群体中的最佳染色体可能会丧失繁殖能力，为了提高算法的性能，在轮盘赌的基础上再采用精英保留策略。

2.4 算法的终止

由于遗传算法搜索路径具有较大的随机性，根据启发式算法的终止条件，本文给定适当的终止参数e、λ、Y。只要算法满足下列条件之一，就认为算法收敛。

（1）计算每代群体中染色体的适应度方差，当方差小于e时，则认为算法收敛；

（2）计算每代群体中适应度的均值，当均值与最佳染色体适应度的比值大于λ时，认为算法收敛；

（3）由于计算时间是有限的，计算代数不能无限长，故当迭代次数达到规定的Y时，停止计算。

3 结 论

考虑生产计划损失量函数对车辆调度的情况下计算得出最终优化解为4 226元。最后得到车辆的行驶路线为0—5—2—0；0—4—3—0；0—8—7—6，总的行驶距离为460km。经检验，此路径安排完全满足各码头的运输需求量约束和装载车辆的承载量约束，是此问题的一个较优的可行解。

此结果表明，经过改进遗传遗传算法优化之后，钻井平台的采购计划可以在最大程度上满足，而且能尽量避免因为配送延迟造成的生产计划的延时，从而使企业能将生产成本控制在比较低的范围。

[1] 郎茂祥，胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学，2002,10(5)：51-56.

[2] 邢文川，谢金星.现代优化计算方法[M].北京：清华大学出版社，1999.

[3] 李军.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社，2000.

[4] 林郁丞.基于聚类分析和遗传算法的带时间窗车辆路径问题研究[D].福州：福建农林大学，2009.

Research on the Genetic Algorithm for Vehicle Routing Problem with Delivery Time Windows

HUANG Rui-ming (China Oilfield Services Limited,Sanhe 065201,China)

通过改进传统的遗传算法，结合中海油服物资配送特点，采用启发式交叉算子的方法，确保了算法迭代中的种群多样性。制定了基于配送时间窗约束情况下模糊预约时间的钻井平台损失惩罚函数，对可行解的范围进行了限定，从而加速收敛，保证了运算的效率。通过案例进行分析证明了可行性。

遗传算法；启发式；交叉算子；时间窗；惩罚函数

By improving the traditional genetic algorithm,we combine with the material distribution characteristics of COSL.We use the method of heuristic crossover operator,ensure that the iteration of the algorithm to maintain the diversity.Application of the penalty function about the increase of costs oil platform with delivery time windows,the scope of the feasible solution has limited and convergence has been accelerated.Ensure the efficiency of operations.Through a case analysis proves the feasibility of the research method.

genetic algorithm;heuristic algorithm;crossover operators;time windows;penalty function

TP301.6

A

2011-01-28

黄瑞铭（1964-），男，广东潮州人，中海油田服务股份有限公司，工程师，研究方向：企业信息化。

1002-3100(2011)04-0116-04