研究配送时间窗约束下的车辆调度遗传算法
来源：UC论文网2015-11-30 20:08
摘要：
摘要：通过改进传统的遗传算法，结合中海油服物资配送特点，采用启发式交叉算子的方法，确保了算法迭代中的种群多样性的保持。制定了基于配送时间窗约束情况下模糊预约时间的
摘要：通过改进传统的遗传算法，结合中海油服物资配送特点，采用启发式交叉算子的方法，确保了算法迭代中的种群多样性的保持。制定了基于配送时间窗约束情况下模糊预约时间的钻井平台损失惩罚函数，对可行解的范围进行了限定，从而加速收敛，保证了运算的效率。通过案例进行分析证明了可行性。
论文关键词：遗传算法,启发式,交叉算子,时间窗,惩罚函数
前言
在中海油田服务股份有限公司的生产物资配送中，不但要满足各个钻井平台对实物的需求，还要满足船期对配送时间的限制，针对各个钻井平台的订单往往会考虑一定前置期的特点，钻井平台上尽量减少库存，对配送服务的时间要求比较严格，因此及时配送变得越来越重要。满足钻井平台对配送时间窗的限制，是制定配送车辆路线应该优先考虑的问题。因此，本文主要选择带时间窗约束的VRP问题进行研究。
对配送路线进行优化，一般都要求符合以下约束条件：
(1)必须满足钻井平台对货物到达的时间或时间窗的要求；
(2)对每一辆运输车辆的装载容量有一定的限制，不允许装载量超过车辆的载重量和容量；
(3)满足钻井平台对货物规格、品种和数量的要求，且一次完成配送；
(4)员工的休息时间的限制(工作时间、用餐时间限制)；本文构建的模型所考虑的主要约束条件如上所述。
2．模型建立
2.1时间窗问题
在进行货物配送时，若采购计划没有对配送的时间提出要求，那么物供中心可以根据自己的配送进程来组织车辆配送，但如果采购计划要求在规定的时间段内完成货物的配送，这就需要考虑钻井平台对时间的要求，VRP问题转化为VRPTW问题。
设完成任务i需要的时间(包括装货、卸货)为Ti，同时任务i的开始时间必需要在规定的时间窗(
,
)内，其中表示为任务i最早的允许开始时间，为任务i最迟的允许开始时间。如果配送车辆到达任务i的时间早于,，车辆必须在i处的码头等待装船，如果配送车辆到达任务i的时间晚于，任务i要等下个船期才能进行运输。若
表示车辆到达i点的时间，应满足关系式
。VRPTW问题中的时间窗限制又可以分为软时间窗问题和硬时间窗问题，其中软时间窗VRPTW表示如果配送车辆无法在要求的时间窗内将货物送达钻井平台的客户手中，则必须按照违反时间的长短支付一定的惩罚费用；硬时间窗VRPTW表示每项任务必须在规定的时间范围内将货品送达钻井平台的客户手中，不论是早到或迟到都完全被接受。相对于软时间窗而言，如果车辆在之前到达任务点i，车辆在i处等待，产生了机会成本的损失。如果车辆在之后到达任务点i，服务被延迟，必须支付一定的惩罚费用：对于硬时间窗VRPTW来说，当货品送达的时间超出时间窗范围时，其惩罚值定义为一个非常大的正数M，这表示在硬时间窗的限制下，如果服务超过时间窗范围，配送成本巨大，此时的解为不可行解。
2.2改进惩罚函数
若配送作业违反了采购计划的时间窗约束，势必会造成采购计划的延迟，从而造成企业的损失，配送作业的目标是在追求成本最低化的情况下，实现企业生产利润的最大化。因此有必要将时间成本考虑在内。
在油田生产过程的配送中，钻井平台会在一定程度的时间范围内接受配送服务，而超过这部分的时间范围，会对企业的生产造成影响，我们选择用图2-1所示的罚函数，
在时间窗左侧的是提前到达的情况，这一段时间的函数线条比较平缓，表示，虽然会有惩罚，但是能忍受提前到达的时限范围较长，因为不会造成生产损失；而在时间窗右侧的是滞后到达，这种对企业生产造成的损失巨大，所以线条斜率较大。其中时间区间[ET，LT]表示钻井平台可以忍受的最大损失的服务时间范围，而[ET，LT]表示钻井平台能进行配送服务的时间范围，即模糊预约时间。
图2-1有时间窗的配送损失量函数
从模糊预约时间的界定可以知道，钻井平台损失量可以通过关于模糊预约时间的函数来表示，对于钻井平台i来说，当服务开始的时间为ti时，钻井平台损失惩罚函数可以表示为：
式（2-1）
2.3改进交叉算子
本文采用启发式遗传算法的基因换位算子来实现染色体的交叉，过程如下：
(1)首先在两个父代字符串A，B中随机的选择一个交叉点，并且A，B中随机的选择一个交叉点后的码头作为第一个子染色体对应位置需访问的码头；
(2)将B中对应位置的6与3交换，以避免以后发生结点重复遍历的现象；
(3)比较A，B中结点6与后面结点的距离，如果c>c。，则选择B中的结点7作为子代对应位置的结点，交换A中1与7的位置，以避免后面发生结点重复遍历的现象：
(4)如此反复执行(3)中的操作，直至遍历完两父代字符串的所有结点，此时得具有同时配送和收集需求的车辆路径问题研究到一个子代字符串。
例：A:8207405|6013A’:8207405|6013
父代B:5410780|3602B’:5410780|6302
子代C:*******|6***
采取该算法，即使种群中所有个体都相同，也不会影响算法的运行。这样就很好的摆脱了传统遗传算法对种群多样性的要求，较好的解决了传统遗传算法中早熟和收敛的问题。
2.4车辆调度模型的建立
为构建上述模型，先建立如下变量
模型的目标函数如下：
式(2-2)
S.T.
式(2-3)
式(2-4)
式(2-5)
式(2-6)
式中：式(2-2)为目标函数，表示使车辆完成配送任务时的总配送费用最小，由以下几个部分组成：总配送距离产生的成本，加班工作产生的额外成本，车辆延时造成的配送成本，车辆提前到达增加的配送成本和违反时间窗要求对生产计划造成的损失量，式(2-3)为车辆的装载能力约束，表示某车运输所装载的物资总量不能超过该车辆本身的最大载重量；式(2-4)式(2-5)表示到达某一码头的车辆的约束，即每一个码头可以最多有n辆车同时进行装卸；式(2-6)用来确保平台i由总共小于n辆车完成配送任务。
论文关键词：遗传算法,启发式,交叉算子,时间窗,惩罚函数
前言
在中海油田服务股份有限公司的生产物资配送中，不但要满足各个钻井平台对实物的需求，还要满足船期对配送时间的限制，针对各个钻井平台的订单往往会考虑一定前置期的特点，钻井平台上尽量减少库存，对配送服务的时间要求比较严格，因此及时配送变得越来越重要。满足钻井平台对配送时间窗的限制，是制定配送车辆路线应该优先考虑的问题。因此，本文主要选择带时间窗约束的VRP问题进行研究。
对配送路线进行优化，一般都要求符合以下约束条件：
(1)必须满足钻井平台对货物到达的时间或时间窗的要求；
(2)对每一辆运输车辆的装载容量有一定的限制，不允许装载量超过车辆的载重量和容量；
(3)满足钻井平台对货物规格、品种和数量的要求，且一次完成配送；
(4)员工的休息时间的限制(工作时间、用餐时间限制)；本文构建的模型所考虑的主要约束条件如上所述。
2．模型建立
2.1时间窗问题
在进行货物配送时，若采购计划没有对配送的时间提出要求，那么物供中心可以根据自己的配送进程来组织车辆配送，但如果采购计划要求在规定的时间段内完成货物的配送，这就需要考虑钻井平台对时间的要求，VRP问题转化为VRPTW问题。
设完成任务i需要的时间(包括装货、卸货)为Ti，同时任务i的开始时间必需要在规定的时间窗(
,)内，其中表示为任务i最早的允许开始时间，为任务i最迟的允许开始时间。如果配送车辆到达任务i的时间早于,，车辆必须在i处的码头等待装船，如果配送车辆到达任务i的时间晚于，任务i要等下个船期才能进行运输。若表示车辆到达i点的时间，应满足关系式。VRPTW问题中的时间窗限制又可以分为软时间窗问题和硬时间窗问题，其中软时间窗VRPTW表示如果配送车辆无法在要求的时间窗内将货物送达钻井平台的客户手中，则必须按照违反时间的长短支付一定的惩罚费用；硬时间窗VRPTW表示每项任务必须在规定的时间范围内将货品送达钻井平台的客户手中，不论是早到或迟到都完全被接受。相对于软时间窗而言，如果车辆在之前到达任务点i，车辆在i处等待，产生了机会成本的损失。如果车辆在之后到达任务点i，服务被延迟，必须支付一定的惩罚费用：对于硬时间窗VRPTW来说，当货品送达的时间超出时间窗范围时，其惩罚值定义为一个非常大的正数M，这表示在硬时间窗的限制下，如果服务超过时间窗范围，配送成本巨大，此时的解为不可行解。2.2改进惩罚函数
若配送作业违反了采购计划的时间窗约束，势必会造成采购计划的延迟，从而造成企业的损失，配送作业的目标是在追求成本最低化的情况下，实现企业生产利润的最大化。因此有必要将时间成本考虑在内。
在油田生产过程的配送中，钻井平台会在一定程度的时间范围内接受配送服务，而超过这部分的时间范围，会对企业的生产造成影响，我们选择用图2-1所示的罚函数，
在时间窗左侧的是提前到达的情况，这一段时间的函数线条比较平缓，表示，虽然会有惩罚，但是能忍受提前到达的时限范围较长，因为不会造成生产损失；而在时间窗右侧的是滞后到达，这种对企业生产造成的损失巨大，所以线条斜率较大。其中时间区间[ET，LT]表示钻井平台可以忍受的最大损失的服务时间范围，而[ET，LT]表示钻井平台能进行配送服务的时间范围，即模糊预约时间。
图2-1有时间窗的配送损失量函数
从模糊预约时间的界定可以知道，钻井平台损失量可以通过关于模糊预约时间的函数来表示，对于钻井平台i来说，当服务开始的时间为ti时，钻井平台损失惩罚函数可以表示为：
式（2-1）2.3改进交叉算子
本文采用启发式遗传算法的基因换位算子来实现染色体的交叉，过程如下：
(1)首先在两个父代字符串A，B中随机的选择一个交叉点，并且A，B中随机的选择一个交叉点后的码头作为第一个子染色体对应位置需访问的码头；
(2)将B中对应位置的6与3交换，以避免以后发生结点重复遍历的现象；
(3)比较A，B中结点6与后面结点的距离，如果c>c。，则选择B中的结点7作为子代对应位置的结点，交换A中1与7的位置，以避免后面发生结点重复遍历的现象：
(4)如此反复执行(3)中的操作，直至遍历完两父代字符串的所有结点，此时得具有同时配送和收集需求的车辆路径问题研究到一个子代字符串。
例：A:8207405|6013A’:8207405|6013
父代B:5410780|3602B’:5410780|6302
子代C:*******|6***
采取该算法，即使种群中所有个体都相同，也不会影响算法的运行。这样就很好的摆脱了传统遗传算法对种群多样性的要求，较好的解决了传统遗传算法中早熟和收敛的问题。
2.4车辆调度模型的建立
为构建上述模型，先建立如下变量
模型的目标函数如下：
式(2-2)
S.T.
式(2-3)式(2-4)式(2-5)式(2-6)式中：式(2-2)为目标函数，表示使车辆完成配送任务时的总配送费用最小，由以下几个部分组成：总配送距离产生的成本，加班工作产生的额外成本，车辆延时造成的配送成本，车辆提前到达增加的配送成本和违反时间窗要求对生产计划造成的损失量，式(2-3)为车辆的装载能力约束，表示某车运输所装载的物资总量不能超过该车辆本身的最大载重量；式(2-4)式(2-5)表示到达某一码头的车辆的约束，即每一个码头可以最多有n辆车同时进行装卸；式(2-6)用来确保平台i由总共小于n辆车完成配送任务。
