动态环境下对快递取件和交付过程的实时控制

动态环境下对快递取件和交付过程的实时控制摘要：我们在本论文中介绍了“实时控制下的动态取件和投递问题”（以下简称DPDPRC）来描绘现实世界的紧急快递服务。特别是，DPDPRC考虑了快递服务公司的当日内快递服务病整合了对实际应用至关重要的现实世界的各个方面。车辆有不同的属性并且是在一个现实的公路网络行驶。每天都会有各种各样的动态事件发生例如新到达的请求，交通拥堵，车辆故障都被考虑了进去。由于前面提到的紧急情况，在请求地点最小化延迟就是首要的目标。第二个目标是追求车辆行驶费用的最小化。为了使运输计划可以适应动态事件并且可以及时服务请求，这里应用了一个实时控制方法，它使计划同步适应快递服务的执行。通过一种禁忌收索算法来执行计划的适应性，该算法的收索过程遵循多个领域算子的在集中和分散之间切换的选择方案。我们对融合了不同动态事件的测试情景进行了评价。计算结果显示根据动态事件持续的调整运输计划可以在很多情况下改进解决方法的质量。关键词：取件和派件；实时控制；动态事件；交通堵塞；车辆故障；禁忌搜索1引言对快递服务公司的日常运输服务来说，其主要的特点高度动态的环境，这系统环境经常由于各种动态事件而发生变化。一个关键特点是，从不同的取件地点运至不同的交付地点的请求会在同一天到达。由于这些请求被非常的期望在规定的时间范围内被完成，运输活动经常在高压下被执行。此外，公路网经常很拥堵且不可靠。因此，除了新到达的请求、交通拥堵、运输车辆故障之外，还有例如减速和货物分拣等需要被实时处理。由于信息技术和通信技术的进步，这些只能在货物运输服务过程中到达的关于动态事件的信息才能被利用起来。1.1论文成果在本文中，我们提出了一个新的控制的方法，该方法可以有效的协调快递公司的动态运输服务。为了提供实用的决策支持，该方法是基于一个“扩展的动态取件和投递问题”（以下简称DPDP），DPDP整合了动态事件的各种不同的来源和现实世界中的几个方面。我们把这个新命题命名为“实时控制下的动态取件和投递问题”（以下简称DPDPRC）。它被专门设计出来去有效的控制快递服务公司在现实世界中的紧急运输服务。本论文的主要成果如下：⑴对现实世界不同方面的考虑。DPDPRC通过对几个典型的快递运输服务的现实方面的考虑扩展了DPDP。运输车辆在运输能力、人工成本、运输速度和路线相关的运输成本是不同的。柔性的请求时间框下的不同的延迟费用以及法定的驾驶时间限制被整合在了一起。首要的目标就是在请求地点最小化延迟，次要目标是最小化车辆运作成本。此外，车辆是在一个具体的现实公路网中行驶的。⑵包含不同类型动态事件的动态环境。除了最新到达的请求外，还有诸如交通拥堵、运输车辆减速和故障等动态事件都被整合了进去。这些动态事件的来源的整合在现实的快递服务中都是非常常见的，从而确保了DPDPRC的实用性。⑶实时控制和恰当的解决方法，在DPDPRC中，运输服务被一个实时控制的方法协调着，该方法处理路线规划的可执行性和适应性。为了使现行的运输计划可以有效的适应出现的动态事件，一个专门设计的“禁忌搜索”方法被应用了。由于该方法产生的拓展的适用性，很多有挑战的短时间运输和大量的不同类型的动态事件会被有效的处理。⑷撰写恰当的测试案例。为了评估在不同可能情况下所提出的处理方法的有效性和实用性，包含不同类型的动态事件的不同的测试情景被撰写出来。为了这个独立，我们提出了撰写复杂问题案例的新方法。此外，还介绍一个模拟公路网交通堵塞的新方法。所提出的实施控制方法的实用性将被综合的计算研究方法所评估。1.2文献综述考虑到运输服务可以被模型化为“取件和投递问题”（以下简称PDP）的一个变形，PDP是一个被充分研究的车辆路径问题（以下简称VRP）的推广和“普通取件和投递问题”（以下简称GPDP）的一个特殊情况。PDP的变形由于它们的实际意义已经成为了一个首要的研究领域。一个紧密相关的问题聚焦在对于旅客运输，也就是“拨召车车辆问题”（以下简称DARP），在DARP中，附加的驾驶限制和便捷性目标被考虑了进去。在文献中，对于静态的PDP的解决方法是和动态的区分开来的。在解决静态的PDP方法中，假定问题相关的数据已经很明确的知道了。因此，考虑到不存在动态事件，在执行传输服务的过程中，不需要计划的适应性。相反的，实时的思想可以处理在动态事件引起的不可预测的系统环境的改变。考虑到本论文的焦点，接下来只会描述实时的方法了。关于动态PDP的简介可以再Berbeglia等（2010）中找到。Powell（1988）研究了一个卡车DPDP。他提供了一个不同技术的总览，这些技术可以对在单车和多车情况下的问题建模以及导出不同的确定和随机的模型方程。Swihart和Papastavrou（1999）采用分析的方法研究了出现新请求情况下的单车DPDP。他们获得了在畅通和拥堵交通状况下系统表现的新界限并且评估了不同的派遣策略。Fleischmann等（2004）研究了柔性时间框下的城市车载DPDP，在这时间框下动态的时间新到达的请求和行车过程中的改变所产生动态事件都可能会出现。运输服务是在一个真实的公路网下进行并且目标方程最求请求延迟和运输费用的最小化。不同的解决方案受到了评估。在Yang等（2004）的论文中，一个柔性时间框下的多车车载DPDP被考虑了进去，该时间框下动态到达的请求必须被执行。请求也可以在增加额外费用的情况下被拒绝。目标是最大化通过请求利润、罚金、延迟和运输成本计计算出来的总利润。不同的政策的到了评估，得出再优化方法的性能和其他政策下的方法的性能很接近。Pankratz（2004）研究了一个远程货运途中对于新到达请求的DPDPTW。一个基于遗传算法的解决方案被提了出来。在Attanasio等（2007）的论文中，呈现了一个实时系统，它可以协调动态到达请求和不确定运输时间情况下DPDP。目标是最大化每个快递员的客户服务质量和平均的服务客户数。作者陈述所提出的系统可以提高服务的质量。Saez等（2008）研究出了一个可混合适应的预测控制方法来解决由于新到的客户请求所产生的动态事件DPDP。Ghiani等（2009）一文考虑了一个新到达请求的DPDP。目标是要最大化客户服务质量。两种预测启发方法被评估了。还有，Bock（2010）提出了实施控制的方法来解决一个联运服务和多源动态事件下的动态远程运输问题。随着更多的方法考虑新到达的请求，其他动态事件的来源也在优秀的文献中被研究了。对交通堵塞的建模在Fleischmann等(2004),Attanasio等(2007),Barceló等（2007),HaghaniandYang(2007),Cortés等(2008),andBock(2010)文献中都被研究过了。另外,车辆故障等在Li等(2009)Bock等（2010)和Mu等(2010)等文献中被研究了。最近，大量的方法采用了关于预期请求到达的随机概念。而很多方法处理动态的VRP，也有方法处理DPDP。重定位策略被用于把空闲车辆重定位到可能出现新请求的区域。在Yang等（2004）一文中，研究了关于在预料未来请求任务时直接采用随机概念再优化方法。另外，不同的产生随机概念的不同方法被提出了。在Attanasio等(2007)一文中,通过历史数据衍生出了随机概念，这些历史数据采用了时间序列分解法。Sáezetal.(2008)通过历史数据整合了随机概念，这些历史数据采用了模糊聚类分析法。考虑到对车辆移动的建模，很少有方法涉及到了公路网，而且对于公路等级相关的车辆费用也被忽略了。另一个方法在车辆路线更改方面更具优势。在路线更改时，当一个新请求在车辆接近剩余行驶路线马上要执行下一个任务时到达，那么这个新请求可以马上被服务。然而文献中只有少部分的DPDP方法采用了这个可能性。另外一个实时控制方法的重要方面是计划适应性与计划执行活动的同步性。然而，虽然这是修改实时复杂运输服务方法的先决条件，但很少有文献涉及到该方法来解决动态VRP和总体扩充DPDP，特别需要指出的是，为了提供实用的决策来支持快递服务公司在实际情况下的紧急运输服务，缺少一种扩展DPDP方法整合不同来源的动态事件来解决这个问题。1.3结构本文的剩下的正文是这么来组织的。第二部分是介绍要研究的问题。第三部分描述所提出的实施控制方法和和在运输服务过程中被解决了的静态问题案例的特点。在第四段陈述了“禁忌收索”元启发式算法，它被用来分析解决今天的问题案例。在第五段，生成了测试案例和计算结果。在第六段，本文用一个总结来结尾并展望了未来的研究工作。2问题描述在快递公司的日常运输服务中，一系列的请求需要被一个车队来服务。每一个请求都包括需要从一个取件地点到一个投递地点的货物。每一个请求地点都有在时间框内被服务的要求。时间框是终究是柔性的所以服务可以在一个时间框结束后再提供，但是这也产生了让人失望的延迟。因为客户的限制，在时间框开始之前提供服务也是不可能。然而，一辆车可以在没有罚金的情况下在时间框开始之前在请求地点等待。与每一个请求相应的需要被运输的货物都有自己具体的重量。所以，路径规划需要遵守车辆的运输能力限制。除了持续不断动态出现的新请求之外，还有交通拥堵、车辆减速情况所产生的动态特征。由于事先无法预知有关动态事件的信息，所以这些事件需要被实时的处理。还要注意交通堵塞和车辆故障的持续时间也是未知的。所以，在执行运输服务过程中这些动态事件可能会也可能不会被处理掉。还有转运是禁止的。然而，如果一个车辆抛锚了，已经被装上这辆车的货物可以被在抛锚地点的另一辆车转接收。快递服务公司并不拥有车辆而是和第三方合作的。每一辆车都有一个司机，并且没有初始车辆使用费的发生。主要说明的是可能使用的车辆数量是有限的。因为第三方使用不同类型的车辆类型（例如小轿车、小货车），所以考虑到车辆的运货能力、人工成本、行驶速度以及和路线相应的行驶成本，这些车辆都被认为是异质的。一但一辆车被派遣之后，就需要尝试为它寻找其他的请求。然而，车辆返回车站是不可能的。快递服务公司需要支付每辆预定的车辆返回车站的费用。因此，每一辆都都在同一个车站开始和结束它的路线。车辆运作的费用综合了车辆返回车站之前的路线相关的行驶费和每辆预定车辆的人工成本。车辆在一个真实的公路网行驶并且总是选择两个地点间的最快路径。车辆改变行驶路线允许的。这使得车子可以在行驶到下一个指定地点的途中改道到另外一个地点。还有，司机的调用需要遵守法律对行驶时间的限制。因为快递货物及时的投送是非常重要的，一个层次目标函数被采用了。首要目标是最小化所有以分钟来计算到达请求地点的客户的总延迟时间。需要指出的是，一个对总延迟费用的适当的建模需要一个延迟所导致的客户不便的后果的合适的处理。接下来，通过采用一个延迟产生的每分钟的固定费用因子，并我们假设了一个按Davis和Maggard（1990）根据经验推导和评估得出线性上升的客户不便性。另外，在客户地点发生的总延迟是可以直接对比的。然而要说明的是，因为每一个情况都有一个延迟处罚函数，这线性延迟处罚函数根据应用情况不同也各有优缺点。特别的是，一些客户可能会从另外一些客户被延迟服务的情况下得到好处。然而，一个线性的罚函数在追求平均延迟最小化时不会导致变形，当应用超线性延迟惩罚函数是也是一样的请。第二个目标是，最求车辆运行费用的最小化。本翻译为原文部分内容。