英语原文共 10 页

具有驾驶员一致性的定期车辆路径问题

关键词：路由、定期车辆路线、驾驶员一致性、有效的不平等、分支切割

摘要：定期车辆路径问题是经典的容量车辆路径问题的概括，其中确定了几天的规划范围的路线。每个客户都有一组相关的允许访问时间表，问题的目的是设计一组最低成本路线，为所有客户提供服务，满足他们的访问要求。在本文中，我们研究了这个问题的一个新变体，其中我们强制要求每个客户在所有访问中都应由同一车辆/司机服务。我们将此问题称为具有驱动程序一致性的定期车辆路径问题。我们提出了一个问题的整数线性规划公式，并推导出几个有效不等式族。我们使用精确的分支切割算法来解决它，并在各种随机生成的实例上显示计算结果。

1. 介绍

由Beltrami和Bodin（1974）引入的定期车辆路径问题（PRVP）是经典的容量车辆路径问题（VRP）的概括，其中针对多个时段的规划范围确定路线，其中一些客户要求多次访问。 访问每个客户有几种可能的时间表。 例如，如果我们正在制定周一至周五的计划，并且如果客户需要在连续访问之间至少一天和最多两天之间访问两次，那么周一至周三，周一至周四，周二至周四，周二 至周五，周三至周五可能是该客户的访问时间表。问题是同时决定时间表和路线，以最大限度地减少总运输成本。

在Beltrami和Bodin（1974）中，已经针对城市垃圾收集研究了这个问题，并提出了一种启发式方法。 自从这项开创性工作以来，已经提出了许多启发式方法来解决PVRP及其变体。 参见，例如，Chao，Golden和Wasil（1995），Christofides和Beasley（1984），Cordeau，Gendreau和Laporte（1997），Drummond，Ochi和Vianna（2001），Gaudioso和Paletta（1992），Hemmelmayr ，Doerner和Hartl（2009a），Russell和Gribbin（1991），Russell和Igo（1979），Tan和Beasley（1984）。 另一方面，PVRP及其变体的确切方法很少见。Mourgaya和Vanderbeck（2007）提出了一个列生成，用于确定访问时间表和车辆客户分配的问题，而不考虑路线上客户的顺序。 巴特勒，威廉姆斯和亚罗（1997）为两期旅行商问题提出了一种分支切割算法。 Francis，Smilowitz和Tzur（2006）研究了一种变体，其中访问频率也是决策。 他们提出了一种基于拉格朗日松弛和分支定界的解决方案。 Baldacci，Bartolini，Mingozzi和Valletta（2011）提出了一种精确的PVRP算法，通过首先计算近似最优的双解，然后使用双重信息来限制路径集而不失去最优解，从而解决了基于路径的公式。

PVRP的应用包括规划向诊所运送医院床单（Banerjea-Brodeur，Cordeau，Laporte，＆Lasry，1998），预防性维护或质量保证的访问（Blakely，Bozkaya，Cao，Hall，＆Knolmajer， 2003; Hadjiconstantinou＆Baldacci，1998），向医院提供血液制品（Hemmelmayr，Doerner，Hartl和Savelsbergh，2009b），访问供应链中的供应商或客户（Alegre，Laguna，＆Pacheco，2007; le Blanc， Cruijssen，Fleuren和de Koster，2006; Claassen＆Hendriks，2007; Gaur＆Fisher，2004; Golden＆Wasil，1987; Ronen＆Goodhart，2007），参观收集可回收材料和废物（Baptista，Oliveira，＆Zuacute;quete， 2002; Bommisetty，Dessouky，＆Jacobs，1998; Coene，Arnout，＆Spieksma，2010; Nuortio，Kytouml;joki，Niska，＆Brauml;ysy，2006; Shih＆Chang，2001; Shih＆Lin，1999; Teixeira，Antunes，＆de Sousa ，2004），彩票销售路线（Jang，Lim，Crowe，Raskin，＆Perkins，2006），或访问在家的学生或患者（An，Kim，Jeong，＆Kim，2012; Maya，Sorensen，＆Goos，2012）。

有关PVRP的应用，解决方案和变体的更多详细信息，我们请读者参考Campbell和Wilson（2014）以及Francis，Smilowitz和M. Tzur（2008）的调查。

Groeuml;r，Golden和Wasil（2009）介绍了一致的VRP，其中每个客户应该由同一辆车访问，并且大约在一天的同一时间。与PVRP不同，每个客户都有一个独特的访问时间表，并且事先已知。 Zhu，Zhu，Che和Lim（2008）以及Luo，Qin，Che和Lim（2015）研究了具有时间窗的多期车辆路径问题，其中客户最多可以服务于一定数量的不同车辆规划期限。 Kovacs，Golden，Hartl和Parragh（2015a）也研究了一种概括，它允许一定数量的车辆访问节点并惩罚目标函数中的时间不一致，而不是通过约束来强制执行它。 Kovacs，Parragh和Hartl（2015b）通过考虑三个目标函数来扩展问题的广义版本：到达时间一致性，驾驶员一致性和旅行成本。 Campelo，Neves-Moreira，Amorim和Almada-Lobo（2018）最近在一家医药分销公司中提出了一致的VRP，客户每天都有多个交付和不同的服务水平协议，如时间窗和发布日期。

在本研究中，我们介绍了具有驾驶员一致性的周期性车辆路径问题（PVRP-DC），其中我们通过强制在所有访问时应该由同一车辆访问每个客户来限制PVRP。这个问题的动机来自软饮料公司的应用程序，该公司通过定期访问其客户来收集需求。每周访问客户的次数是一次，两次或三次，具体取决于销售量，所有访问都由同一名员工执行。在交付系统中遇到类似的问题，其中车辆访问零售商以接受订单并同时交付物品。在该系统中，驾驶员了解零售商的需求，并根据他们的预测决定如何使用不同的物品装载他们的车辆。至关重要的是，每次访问时，相同的驾驶员都会访问零售商以获得驾驶员的学习。这些是行业中需要驱动程序一致性的两个示例。第三个工业实例是访问连锁超市的商家的路线，以重新填充空架子，以更好地展示产品和促销。同样的商人访问同一超市与超市的知识同样非常重要，客户档案非常重要。还有家庭护理应用，例如专业护理人员为老年人或有特殊需要的人定期家访。护理人员与所拜访者之间的联系在这些应用中至关重要。在对这些示例进行建模时，我们会考虑具有单位需求的客户，因为访问的持续时间大致相等，并且我们限制了一天内驾驶员可以访问的客户数量，以确保服务质量。

需要注意的一个重要问题是一致性要求确实对PVRP的解决方案产生影响，如图1和2所示。这些图显示了PVRP和PVRP-DC在具有10个客户（节点1到10），位于节点0的仓库，两个周期或天的时间范围以及两辆车中每辆车最多可以访问四个用户的实例的最佳解决方案。客户1,2,4,5,8和9必须在两天内访问。客户10必须在第一天完全访问，而客户7必须仅在第二天访问。客户3和6必须在第一天或第二天访问一次。如图1所示，该实例的最佳PVRP解决方案的成本等于688.64。为了区分两辆车的路线，用虚线或实线表示。我们可以看到客户1在第一天被车辆访问，而第二天则被另一个访问。如果我们要求驾驶员一致性，则最佳解决方案如图2所示。在此解决方案中，所有客户始终由同一驱动程序访问，但是，正如预期的那样，这会导致成本增加。

1. Mip 配方

在本节中，我们给出了PVRP-DC的正式定义，并给出了整数规划公式。

设V = {0,1，...，n}是一组节点，节点0对应于软件仓库，其他节点对应于客户。让E = {esub;V：| e | = 2}是边缘集合，Ce表示与边缘eisin;E相关的运输成本。 我们考虑规划期限T = {1 ,hellip;hellip;.,tau;}的tau;个时期。 在规划期间，每个客户都需要访问一定次数，始终由同一车辆访问。 我们将Pi定义为客户iisin;V\ {0}的可能访问时间表的集合。同质舰队K = { 1 , . . . , m }在车辆段中可以获得m个车辆，并且每个车辆可以在每个时段内访问2个和q个客户。

PVRP-DC的目的是为每个客户选择一个访问时间表，并为每个时期设计路线，以便最大限度地减少规划期内的总运输成本。

我们使用以下二元决策变量来表示问题。我们定义Zkip 为1如果如果调度pisin;Pi被选择为服务客户iisin;V\ {0}并且如果该调度中的所有访问都由车辆kisin;K完成，否则为0。我们也定义Xtke是1如果在时间tisin;T中车辆kisin;K遍历边eisin;E，否则为0，并且Ytk0是1如果在时间段tisin;T中使用车辆kisin;K，则否则使用0。化简表示法，我们让Ytki= Sigma;pisin;Pi；tisin;PZkip。对于iisin;V\ {0}，tisin;T和kisin;K。如果客户i在时段t中被车辆k访问则该变量为1，否则为0。

我们使用一些额外的表示方法。如果S sube;V ,设delta;(S)={eisin;E: |Scap;e|=1}。如果S = {i}，我们写delta; ( i )而不是delta;（{i}）。另外，对于边E、sube;E的给定子集，我们定义xtk（E、）=Sigma;eisin;E、Xtke。

PVRP-DC可以被如下建模：

目标函数（1）是最小化总路由成本。约束（2）确保每个客户由一辆车提供服务，并遵循其允许的访问时间表之一。变量y和z通过约束相关（3）。 约束（4）是仓库和客户的程度约束。

约束（5）确保车辆路线的连通性。他们声明如果在时段t中车辆k访问了客户iisin;S，则在该时间段内切割delta;（S）必须至少两次乘以车辆k。当S=V\{0}时，对于任何给定的iisin;S约束（5）可以写成x^tk（delta;（0））ge;2y^tk_i，其使用等式Eq.(4)对于车厂，如果在该时段内没有使用车辆k，则这些不等式避免在时段t中通过车辆k访问客户i。约束（6）是容量约束，并且最多限制车辆k在时段t中可以访问的客户的数量。 如果在时段t中没有使用该车辆，他们还避免在时段t中通过车辆k访问节点。 最后，约束（7） - （9）是可变限制

1. 有效的不平等

在本节中，我们提出了几个有效不等式的族，以加强PVRP-DC的LP弛豫。 这些不等式的有效性将在后面的专门讨论计算结果的部分讨论。 设X是上述模型的可行解集。
第一类有效不等式通常用于解决类似的车辆路径问题; 因此，我们提出它没有证据。 这个家庭是:

这些不等式确保，如果在时段t中车辆k横穿车辆库i的边缘，则在同一时段t中车辆k访问其另一个端点。
第二个家族的灵感来自于广义的多极不等式.(见 Letchford, Eglese, amp; Lysgaard, 2002).

命题1 ：

证明：不等式（12）的左侧是车辆k进入并且在时段t中离开集合S的次数。很明显是此数字的下限，因为是S期间必须由车辆k服务的客户数量。 但请注意，这可以通过考虑在访问客户iisin;S之前或之后立即访问的时段t中服务的所有客户来增加。 因此，（12）是有效的。 接下来的两个有效不等式族是专门为PVRP-DC导出的。

命题2：

证明：这种不等式是有效的，因为在T期间被分配给K中的车辆的集合S的节点数等于 集合S中的节点数减去S中由车辆在集合K中服务但不在T中的任何一天服务的节点数量，以及S中未分配给集合K中的车辆的节点数量。因此，在 一个可行的解决方案，我们必须有

这种不平等的右边大于或等于不平等的右边（13）

命题3：

1. 分支切割算法

我们设计了一种分支切割算法来优化PVRP-DC。 这种类型的算法结合了用于探索决策树的分支定界方法，以及通过解决由有效不等式改进的LP弛豫来计算下界的切割平面方法。 接下来我们将描述算法的主要特征。

1. 预处理

在开始分支定界搜索之前，我们执行预处理阶段以减少问题的大小和复杂性。

1. 可变固

定某些变量可以固定为零，如下所示。为每个客户iisin;V\ {0}并且每个周期tisin;T我们检查t是否属于任何pisin;Pi与否。 如果答案是否定的，即，如果t没有出现在客户i的任何允许访问时间表中，我们设置所有车辆的y^tk_i = 0。

1. 对称破坏

PVRP-DC在其定义中具有一些固有的对称性，并且为了避免它们而使用规则进行计数是有效解决它的必要条件我们应用以下对称性破坏策略。 对于每辆车kisin;{1 ,hellip; ,|K|-1}，我们选择客户i_kisin;V\ {0}并为所有车辆k设置pisin;P_ikz^k_ik，p = 0 k^lsquo;isin;K这样k^lsquo;gt; k。 这可以防止I_k将被分配给索引大于k的任

资料编号：[3715]