时间窗罚函数在物流优化计算中的作用研究

李雪阳，魏晓波，赵 凯

（沈阳工业大学，辽宁 辽阳 111000）

0 引言

带时间窗的车辆路径问题（Vehicle Routing Problems with Time Windows，VRPTW）由车辆路径问题（Vehicle Routing Problems，VRP）添加时间窗约束演变而来，一般是指：组织一定的运输车辆以适当的行车路线，在规定的时间窗口范围内，把货物送达给一系列不同需求的客户，并以配送成本最低或路径里程最短，或时间耗费最少等一个方向或多个方向为优化目标。时间窗约束是VRPTW 研究中不可回避的问题，也是多数优化问题需要考虑的充分必要条件，研究带时间窗的物流配送的最优化问题，符合社会生活实际。物流学者研究的VRPTW 优化问题，时间窗呈现不同的表现形式。从时间窗边界来划分，时间窗类型基本可分为硬时间窗、软时间窗、模糊时间窗，本文从时间窗罚函数的角度出发，研究不同时间窗的性质和应用场景。

1 时间窗与罚函数

VRPTW 问题本质上属于有约束的离散变量的寻优问题，一般使用遗传算法、蚁群算法、模拟退火算法、列表搜索算法等启发式算法编程计算。而启发式算法都是从一个或一组初始解出发，在算法程序的控制下产生若干邻域解，这些邻域解中必然包含大量的不可行解，消除这些不可行解的最常用的办法就是构造罚函数，在程序运行迭代过程中从不可行解域移动到可行解域，逐渐淘汰罚函数值较大的个体，实现目标函数值收敛，从而达到寻优目的。

1.1 硬时间窗及其罚函数

硬时间窗是一种刚性时间约束，是客户最早至最晚可接受车辆配送服务的时间区间，客户只在此窗口期接受服务，早到需等待，迟到则不接受服务。常见硬时间窗如图1 所示，客户只在［ET，EL］时间段接受服务，此区间罚函数值为0，区间外罚函数值为，是个足够大的正数。

图1 硬时间窗罚函数

车辆在时刻到达客户，罚函数公式如下：

由硬时间窗构造的罚函数较为简单，使有约束优化问题转化为无约束优化问题，简化了程序处理过程。但硬时间窗罚函数值由于非0 即的函数特性，不能细化函数值，不便于构造满意度函数；同时，由于硬时间窗要求的严苛性，在优化计算中可能存在不可行解，导致优化失败。

1.2 软时间窗及其罚函数

软时间窗是一种弹性时间窗，包含客户的期望服务时间和可接受服务时间。如果把本文上一节提到的硬时间窗看作是客户的期望服务时间，那么软时间窗就是客户的可接受服务时间，可以把软时间窗看作是硬时间窗的有限外延。服务应尽可能在硬时间窗内开始，如有提前或延误也不能超出软时间窗，如图2 所示，［ET，LT］区间为原来的硬时间窗，［EET，ET］和［LT，ELT］区间就是软时间窗。客户在整个［EET，ELT］时间区间内均可接受服务，配送服务早于EET 和晚于ELT 则客户不接受服务。

图2 软时间窗罚函数

车辆在时刻到达客户，罚函数公式如下：

一些学者认为，软时间窗总是存在可行解，在硬时间窗基础上扩展时间段形成软时间窗，则可通过罚函数实现与硬时间窗一样的评价。另外，软时间窗分段函数可以在［EET，ELT］范围内量化函数值，越偏离［ET，LT］时间窗罚函数值越高，软时间窗可以约束服务者的送货准时率，提高服务水平。

部分学者认为软时间窗的线型分段函数，不足以反映时间的紧迫性要求，构建了指数函数形式的分段函数，如图3 所示，越接近最早和最晚的软时间窗上下限，函数图形越陡峭，函数值变化越快；也有学者认为早到只是未达到客户期望，罚函数值较小，构建了图4所示的分段函数，另有学者认为早到对于客户并无损失，构建了如图5 所示的分段函数；还有部分学者考虑了车辆早到等待成本问题，构造了更加复杂的分段函数，如图6 所示。另外，还有其他类型的一些软时间窗罚函数。

图3 软时间窗罚函数类型一

图4 软时间窗罚函数类型二

图5 软时间窗罚函数类型三

图6 软时间窗罚函数类型四

物流配送的及时与否是反映用户满意度的重要指标，考虑加入其他影响满意度的因素，即可构建软时间窗满意度函数，货品越接近客户的期望时间窗送达，客户满意度就越高。

1.3 模糊时间窗及其罚函数

模糊时间窗是学者根据模糊理论，通过建立模糊隶属度函数在硬时间窗的基础上构建的虚时间窗，目的是引入满意度函数，在牺牲部分客户满意度的情况下，进一步压缩物流企业配送成本。多数学者采取定值扩大或随机扩大原有时间窗的方法，理论上对原有时间窗进行模糊化处理，在程序实际运行中再进行去模糊化处理，扩大了可行解范围。两种类型的模糊时间窗罚函数分别如图7、图8 所示，［ET，LT］为原有的硬时间窗，［FET，ET］和［LT，FLT］即为扩展后的模糊时间窗（Fuzzy Windows），模糊时间窗罚函数和软时间窗类似，本文认为模糊时间窗罚函数与软时间窗并无本质区别。

图7 模糊时间窗罚函数类型一

图8 模糊时间窗罚函数类型二

车辆在时刻到达客户，模糊时间窗罚函数转化的满意度函数如下：

式中为客户的时间敏感度，也可取值为1，变成线性分段函数。

模糊时间窗的确立，构建了客户满意度函数，在优化计算中可以在客户满意度和运营成本之间权衡考虑，降低局部客户满意度，达到运营成本最优的目的。

1.4 时间窗特点及应用场景

本文对带有硬时间窗、软时间窗、模糊时间窗的文献进行了研究，三种时间窗的特点和应用场景见表1。

表1 时间窗特点及应用场景

2 结论

在国家加快构建国内统一大市场的背景下，物流行业必将迎来新的发展机遇，优化资源配置、降低企业成本成为不容忽视的问题。物流成本优化越来越凸显其重要性，而时间窗是优化计算中必须考虑的因素。大量研究者提供的优化应用与实践使得各类时间窗体系框架日臻成熟，硬时间窗、软时间窗、模糊时间窗在VRPTW 优化计算中，由于侧重点和优化场景的不同，分别扮演了不同角色。

从优化场景的角度看，优化计算中时间窗的设定应贴近实际情况，在满足客户需求的同时，优化物流企业运营成本。从计算过程角度看，硬时间窗优化计算步骤相对简单，易于实现；软时间窗更能适应复杂多变的现实环境，需要考虑的变量也更加庞杂，计算过程也变得更为复杂；模糊时间窗则能在面对宽松时间窗需求的客户时，利用模糊理论在计算中进行模糊—清晰化处理，把物流企业的成本降低到一个新的水平。