软时间窗车辆路径优化惩罚函数研究综述

摘 要：软时间窗车辆路径问题作为车辆路径问题中的一部分，对于提高配送满意度至关重要，直接影响企业的发展。文章总结国内外研究的一些软时间窗惩罚函数类型、对相关研究人员研究的模型以及求解算法进行总结，并在此的基础上，对今后软时间窗的类型以及适用范围进行相应的展望。

关键词：软时间窗;惩罚函数;车辆路径问题

随着社会的进步和信息技术的发展，人们对于生活水平的要求也有所提高，对于服务质量要求也有所提高，关注的方面也逐步上升到服务的速度方面。而运输速度的体现的标准之一就是到达客户点的时间，因此，时间窗便成为了运输业需要考虑的一个方面。对于服务行业而言，顾客满意度也是制约企业发展的重要因素。对于运输行业而言，运输成本最低是获利的有效途径，而运输成本的高低衡量的标准是车辆路径的长短。因此，时间窗也就随之和车辆路径优化相结合在一起，对于运输行业而言，运输的要求不仅仅在于将货物运输到顾客手中，还要在顾客所限制的时间范围内，对此，这类问题的研究就显得尤为重要。

1 软时间窗车辆路径惩罚函数类型

依据惩罚函数的形状可以分为线性软时间窗和非线性软时间窗，依据时间窗的图形的类型可以分为全软时间窗和半软时间窗。目前，国内研究的软时间窗类型多集中于线性全软时间窗。图1为原先开始研究的惩罚函数图形，随着研究的深入，于2004年左右，对于原始图的最低点有所上升，形成图2所示的图形。到2015年左右，考虑到：服务车辆早到，客户没有损失;服务车辆晚到，降低客户满意度，带来的影响比较大，因此设置的惩罚系数较大。因此，形成了图3所示的图形。此外，也存在只考虑到达时间较晚的惩罚，而允许等待较早到达而不需要任何代价。再次基础之上形成了相应的惩罚函数图形，见图4。至2018年，有研究人员在原始的基础之上提出软时间窗的折线惩罚函数，见图5。

针对软时间窗的惩罚函数国内也有非线性，尤其是针对生鲜冷链物流运输问题。最常见的一种类型是指数类型的，主要考虑的因素是顾客的需求和满意度，一般而言，消费者在购买生鲜产品时，会倾向于购买距保质期限较长的产品，生鲜产品被销售出的概率随着到达销售端时所剩下的保质时间的长度而递减，并且递减的速度随着接近保存期限的程度而增加。因此选择指数类型的惩罚函数进行表示，见图6。此外，也有研究者认为：线性函数并不能反映实际情况，早到对于顾客没有损失，但是对于企业会有其他方面损失，晚到有必要体现客户被服务的体验。因此，形成了图7的惩罚函数类型。还有针对医药物流的运输问题，所提出的两种非线性惩罚函数。

国外对于软时间窗车辆路径的惩罚函数主要研究都集中于线性软时间窗，对于研究其创新的方面主要集中于算法方面，主要是分为六种类型，见图10-图11。

2 软时间窗车辆路径优化模型

国内软时间窗车辆路径问题构建的模型大致分为两种：一种是将时间窗加入约束条件，目标函数以路径最短，另外一种是将时间窗加入目标函数之中，有文献是将其作为二级目标函数，以违反时间窗约束的时间最短，也有结合相应的惩罚成本，只构建一个目标函数。约束条件方面所考虑的因素是：每一个客户只被服务一次，避免车辆路径的迂回，进出客户点的车辆数相等等。与原始的车辆路径模型方面存在差异的部分在于目标函数，以及约束中要加入时间窗约束。解决这类问题的算法和车辆路径问题所使用的算法一致，目前，仍以启发式算法居多，精确算法的研究较少一些。

3 结论和展望

针对软时间窗车辆路径优化的研究，目前国内国外的非线性研究比较少一些，对于线性时间窗车辆路径的研究居多，模型上的改变多数集中于软时间窗的惩罚函数的变化，算法上的改进也是占据主流的一部分。惩罚函数的主要出发角度在于顾客的满意度，对于不同的行业而言，软时间窗的类型应该是不一样的，对于这个方面，目前看来生鲜冷链物流上面有具体试用的软时间窗，其他类型的物流是没有的。因此，这个问题可以作为研究软时间窗车辆路径问题的一个角度。此外，很明显线性软时间窗是简化了现实情况下因素而形成的，非线性软时间窗更加贴合实际，因此，非线性软时间窗应该也可以作为一个研究的角度。

参考文献：

[1]赵冰洁.配送中心配送方案优化研究[D].西南交通大学，2004.

[2]葛显龙，辜羽洁，谭柏川.基于第三方带软时间窗约束的车辆路径问题研究[J].计算机应用研究，2015，32（03）：689-693.

[3]Ali Gul Qureshi，Eiichi Taniguchi，Tadashi Yamada.Exact solution for the vehicle routing problem with semi soft time windows and its application[J].Procedia -Social and Behavioral Sciences，2010，2（3）.

[4]韩亚娟，彭运芳，魏航，史保莉.超启发式遗传算法求解带软时间窗的车辆路径问题[J/OL].计算機集成制造系统，1-16[2019-03-29].

[5]李泽华.带时间窗约束的生鲜产品配送车辆路径优化问题研究[D].大连海事大学，2009.

[6]贺小涵.带软时间窗的动态车辆路径规划问题研究与实现[D].哈尔滨工业大学，2017.

[7]武佳佳.时间窗约束下医药物流配送路径优化研究[D].山东师范大学，2018.

[8]Fu Z，Eglese R，Li L Y O.A unified tabu search algorithm for vehicle routing problems with soft time windows[J].Journal of the Operational Research Society，2008，59（5）：663-673.

作者简介：陈婷（1995-），女，汉族，江苏人，研究生在读，研究方向：时间窗车辆路径优化问题。