带时间窗的容量约束多取在线食品配送问题:一种分支切割算法外文翻译资料

带时间窗的容量约束多取在线食品配送问题:一种分支切割算法

摘 要

如今，在线送餐公司允许顾客订购一家或多家餐厅的菜肴组合。为了满足顾客的需求，该公司安排轻型货车从不同的餐馆取货，可能距离很远，然后把它们送到顾客手中。该公司通过有限的车队数量来迎合他们客户的需求。在本文中，在取货和交货地点的时间窗口和车量数的约束下，我们提出了一个增加的二指标公式来寻找满足顾客需求集的最小成本车辆路线。我们使用分支-切割算法来解决基准问题实例。提出的公式和问题特定的有效不等式比现有的公式具有更有效的解决性能。计算实验表明，该方法可以解决大多数节点数为25、35和50的基准问题实例，其中许多实例在现有文献中还没有得到正确解决。

关键词：食品配送，多取配送问题，分支切割，车辆路径问题

第一章 绪论

在一个典型的组织中，总的业务成本主要由与多方面的运输业务相关的成本组成。这意味着，对于一个组织来说，一个设计良好的交通规划可以极大地提高其盈利能力、竞争力和信誉。因此，找到一组最优的车辆配送路线，既能降低成本，又能提高服务质量，是运营决策的关键之一。不出我们所料，许多基于智能手机，用于车辆高校路径的创新应用程序已经出现。

许多业务情况需要车辆从预先确定的几个地点进行连续的物品接收，一旦所有接收完成，该车辆必须将物品送到相应的送货地点。

合作牛奶收集配送公司就是一个经典的例子，在将收集到的牛奶送到处理中心之前，一辆车在给定的时间窗口内以预先指定的顺序访问所有的收集中心。由于产品的易腐烂性，时间窗起着非常重要的作用。另一个例子是达巴瓦拉公司, 1890 年它在印度孟买(BomBay)(现在改名为Mumbai)开创了自制食品送返体系。目前，每天有超过20万个午餐盒在早上被取走，在午餐时间之前送到，然后在晚上将空餐盒送回客户家。

像这样在多位置的时间窗口约束下，包含一组这样的交付请求的问题，被称为带有时间窗口的多点配送问题(MPDPTW)。MPDPTW最近由Naccache等人(2018年)和Aziez等人(2020年)在文献中介绍，但是是一种无容量限制的形式。

这类典型问题的设置完全适合在线订餐应用程序，并且这一类应用程序正在快速发展，尤其是现在，在COVID-19疫情下，相比于去餐馆吃饭，人们更喜欢在网上订餐。情形设置可以理解如下。不同的顾客联系一家配送公司，并且他们在一家或几家的餐馆下单了一种或几种菜肴。 为了满足不同顾客的要求，这家公司必须安排一辆配送车从选定的餐厅接收所有需要的菜肴，然后把它们送到顾客手中。当然，该公司基于运营经济学的考虑，可能会结合不同客户对同一配送车行程的需求，并为配送车队创建一套整体最优行程，以满足所有客户的要求。此外，由于餐品的易腐烂性程度不同，餐厅特定餐品(包括早餐、午餐、晚餐)营业时间的不同以及客户空闲时间的不同，取货点和送餐地需要在特定的时间窗口内到达。向JUST EAT、Uber eats和SkipTheDishes等公司都是在这种设置情形下运营的全球领先公司。

在本文中，我们考虑了在配送点容量有限下的MPDPTW,并对这个知识体系提出了三个贡献。首先，我们为MPDPTW提出了一种增广的双指标公式(ATIF)，由于这种方法具有相对较少的变量数量，与高阶公式相比，该算法具有更高的求解效率。该公式与MPDPTW现有的双指标公式不同，它使用抽象变量表示请求到请求的连接性。这个公式还包含了另一个实际操作情况，即对每辆配送车的容量做出了限制，据作者所知，现有文献没有考虑到这一点。由于配送车辆容量的限制，一辆配送车能够处理的请求数量通常是有限的，考虑这一限制使问题更加具有实际性。其次，对于已知的不可行请求集，我们引入了新的特定问题有效不等式。第三，我们报告了MPDPTW的现有基准问题实例集的结果，并证明了所提出的方法可以解决大多数具有25、35和50个节点的实例，其中许多实例都在现有文献中表明未得到完全解决。

我们提出的研究可以为相关人员带来很大的价值，尤其是在在线食品配送业务中，主要有两个方面。首先，可以提供最优的路线计划，特别是对较小规模的问题，第二，可以提供对基于启发式算法的特定业务测试问题的测试、调优解决方案，通常在实践中使用。值得注意的是，启发式算法被开发来提供足够好的解决方案，几乎是实时的，而不是需要花费时间的精确解决方法。在这种情况下，研究假设有更大的实际相关性，对于实际需求者十分有用。

本文的其余部分结构如下。在第2章中提出关于车辆路径问题及其相关的扩展，以及与解决方法相关现存文献的概述。在第三章中，我们定义了MPDPTW的数学模型和符号，并提出了一个增广的双指标数学公式，以及所提出的有效不等式。在第4章中，我们描述了解决方法。在第5章中，我们呈现了得到的结果。第六章中，我们对以上工作进行了结论，并且在第七章中对未来的工作方向进行展望。

第二章 文献综述

2.1 经典车辆路径问题（VRP）

车辆路径问题（Vehicle routing problem，VRP）是由Dantzig和Ramser(1959)正式提出的，它可能是与物流优化相关的运筹学研究中被研究最广泛的问题。VRP最初主要是针对一队运输物品的车辆，设计一种有效的调度方案，服务于具有特定需求的一群客户，以最小化运营成本为目标。在一个典型的VRP中(见图1)，位于基地仓库的有数量限制的同种类型车辆车队的路线设计如下：

1. 一组客户，各有一个已知的需求，每个用户仅由一辆车访问一次；
2. 每辆车路线必须在基地仓库开始和终止；
3. 车辆路线上的负载，在指定的路线上的任何时候都不能超过车辆的运载能力。

由于VRP在物流运输行业的广泛应用，它仍然是一个密集的研究领域(Braekers等人，2016)。

2.2 经典车辆路径问题（VRP）的扩展

研究人员提出并研究了经典VRP的几个变体，这些变体捕捉了在实践中不断演变的物流过程的细微差别和独特要求，比如包含位置(节点)的时间窗口、多车量的车队、供应链中的回程、同时交货和取货等。

图2说明了我们感兴趣的VRP类问题的广泛分类。

在许多应用程序中，定义了服务时间窗，它限制了车辆可能为各个位置提供服务的时间段。因此，VRP的一个主流的扩展方向是带时间窗口的车辆路由问题(Vehicle Routing Problem with Time Windows，VRPTW)。VRPTW的一个经典例子是收取停车费问题。为了开展收费站的工作，一名员工从她（或他）驻守的一个给定的仓库开始她（或他）的旅程，用一个专用的密钥从特定的过路费中获取货币，并最终存入特定的交付地点。虽然，没有具体的命令访问一组收费站，但收费站必须在雇员交付货币之前被访问，只有在这之后，下一个密钥将提供给她（或他）。可以理解的是，完成访问有时间窗口限制。

VRP另一个有用的扩展方向包括在路途中的地点取货和交付，被称为取货和交付问题(Pickup and Delivery Problems，PDP)。在PDP类问题中(见图3)，每个客户请求都有其关联的取货(原点)和相应的交付(目的地)。这意味着，针对预先确定的需求，从特定的客户取货地点收集货物，然后到相应的客户取货地点进行交付。带时间窗的取货和交付问题(Pickup and Delivery Problems with Time Windows,PDPTW)是PDP的扩展，在各个地点(基地仓库、取货和交付)提供时间窗口服务。PDPTW有许多实际应用，如校车的路线规划和调度，降低成本和碳排放的集中运输，城市快递服务，轻卡车运输等。

关于PDPTW及其变形的重要研究见表1(表2)。

本研究感兴趣的问题是PDPTW的扩展，其中我们考虑针对多个客户的多个取货请求的交付请求。该问题被称为带时间窗口的多取货交付问题(Multi Pickup and Delivery Problem with Time Windows，MPDPTW)。MPDPTW 是VRP(和PDP)类问题的一个相对较新的扩展，文献中很少研究(见表3)。

2.3 解决方法

VRP已知是一个NP难问题(Savelsbergh, 1990)。作为VRP的扩展，大多数的PDPs和一些特别的MPDPTW显然也具有NP难的特性。对于NP难问题，很难通过数学方法得到精确解决方法，特别是对于大型问题实例。因此，大多数研究都集中在启发式方法的开发，以在合理的时间内获得接近最优的解。Pisinger和Ropke(2007)使用自适应大邻域搜索算法，阮等人(2017)使用禁忌搜索算法，Subramanian(2010)等人使用平行邻域下降法，Ai和Kachitvichyanukul(2009)，Goksal等人(2013)以及El-Hajj等人(2020)都使用粒子群优化算法，来解决取货和交付问题。Fischetti等人(1998)通过分支-切割算法解决了定向问题。而EI-Hajj等人(2016)则采用切割平面法来解决团队定向问题。然而，针对VRPs 和变体的精确方法研究在一定程度上受到了限制。关于VRPs和变体的精确解决方法的简要工作可以在表2中看到。

关于VRP精确解决方法的广泛文献调查，读者可以参考Baldacci等人(2010)的文献。

2.4 关于MPDPTM已完成的工作

据我们所知，Naccache等人(2018)首次正式描述、建模并通过适当地纳入相关复杂的多提取功能解决了这个问题。他们用三指数公式来解决这个问题。他们结合启发式驱动的混合自适应大邻域搜索(adaptive large neighborhood search，ALNS)，使用分支定界方法解决了这个问题。作为第一个引入MPDPTW的人，他们还从PDPTW的现有实例中获得灵感，开发了一组问题实例的基准测试。他们证明了他们的方法可以有效地解决包含400个节点的问题实例，特别是关于应用于数学模型的精确解决方法，使用了CPLEX求解器。

Aziez等人(2020)首次尝试用精确的数学方法解决这一问题。作者们比较了三种不同的公式(2-指数，3-指数和ARF)，得出结论，非对称代表公式(Asymmetric Representative Formulation，ARF)是最强和最有效的公式。作者认为，ARF克服了对称解决方案的问题，即同一组请求被重新分配给多个同类型车辆，产生弱松弛，结果是一个重复的分支和边界树。使用ARF，他们解决了这个难题的120个基准问题实例中的60个。

2.5 现有文献的不足

在现存的文献中可以看到一些不足，这也是本研究背后的动机。首先，在问题领域只做了有限的工作，主要是因为它是最近才加入研究领域的。这提供了一个扩展知识体系的机会。第二，问题的容量限制形式在文献中没有被考虑。为了使问题切实可行和切合实际，需要考虑这方面的问题。第三，文献中用于测试解决方法效率的基准问题在很大程度上仍未解决。这提供了改进解决方案方法的可能性。

第三章 问题建模

MPDPTW公式的目的是在以下约束条件下生成路线图：

(a)生成的路径数量不超过车辆队伍规模，K。

(b)每名顾客以及她（或他）的要求只和一条路线或一辆车辆相匹配，并可能与其他人的请求结合。这意味着，对于每一项请求，其所有取餐和相应的交付必须在同一条路线上，由同一辆车承担。这个约束被称为耦合约束。

(C)对于每项要求，相应的取餐和

剩余内容已隐藏，支付完成后下载完整资料

英语原文共 22 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[596107]，资料为PDF文档或Word文档，PDF文档可免费转换为Word