基于优化的大型应急物资配送供应选址与路径选择方法外文翻译资料

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

基于优化的大型应急物资配送供应选址与路径选择方法

摘要：在紧急救援中，及时向灾区提供重要物资是非常重要的。这涉及仓库选择，路径选择和调度问题，以便在严格的时间内满足需求。一般来说这个问题非常棘手，很难解决。繁忙的交通造成的拥堵进一步加剧了这一问题。为了获得可变的解决方案，开发了一种基于拉格朗日松弛（LR）框架中的连续子问题求解的新方法。拉格朗日乘数放宽了路径容量和位置选择约束，并将问题转化为两级优化问题。在具有收敛保证的双迭代中,连续求解较低层次的子问题, 从而可以将不可分解的位置约束结合起来。在可行性迭代中,将曾经放松的约束重新添加到对偶问题中,提出了一种系统的方法来获得可行的解。提出了该方法的收敛性证明及其性能。数值结果表明,该方法是有效的,可应用于大规模问题。

从业者注意事项——我们的论文的动机是同时解决仓库位置选择以及应急物料交付的路径和调度问题。目前，文献中报道的应急物资供应问题的研究工作大多都集中在位置选择问题或车队布线调度问题上。在许多实际应用中，必须协同考虑和解决这两类问题，以便及时交付材料。由于该问题是非常棘手的，因此一般的整数编程方法很难解决。为了解决这个问题，开发了一种基于连续子问题求解方案的新方法。通过将一次放松的约束反馈添加到双重问题中，系统地获得近似最优解。数值测试结果表明, 该方法可以解决具有满意的对偶间隙的大规模问题，并且比一般的整数编程方法更有效。

关键词：紧急供应，拉格朗日松弛(LR)，位置选择，调度。

2010年8月25日收到的手稿; 2011年1月17日修订; 2011年3月20日接受。出版日期2011年7月5日; 当前版本的日期2011年10月5日。本文由副主编C. Chu和编辑Y. Narahari在评审评论者评论时推荐出版。这项工作得到了国家自然科学基金会（60921003,60736027）的部分支持，部分得到了863高科技发展计划（2007AA04Z154）的支持，部分得到了中国111国际合作计划的支持。

Y.Han就职于清华大学NLIST自动化系智能与网络系统中心合作，北京100084.他还在中国海洋开发中心，北京，100161（电子邮件：hanyj04 @ mails.tsinghua.edu.cn）。

X. Guan就职于清华大学NLIST自动化系智能与网络系统中心合作，北京100084。 他还在西安交通大学SKLMS实验室和MOE KLINNS实验室，西安，710049（电子邮件：xhguan@tsinghua.edu.cn）。

L. Shi在清华大学NLIST自动化系智能与网络系统中心，北京100084。 她还在美国威斯康星州麦迪逊市威斯康星大学麦迪逊分校工业工程系（电子邮件：leyuan@engr.wics.edu）。

本文中一个或多个图片的彩色版本可在http://ieeexplore.ieee.org在线获取。

数字对象标识符10.1109 / TASE.2011.2159838

1介绍

通过提供适当和关键的物料，快速响应灾难救援，吸引了世界上许多研究工作，因为它对社会生活和稳定产生了深远的影响^[1]-[3]。诸如食品，水，药品等救济物资的紧急交付是一个非常重要的问题，具有与常规材料供应不同的以下特征。

1. 快速建立的供应系统，包括临时仓库，临时车队，临时客户等。
2. 在紧密的时间内交付大量材料。
3. 由于满足需求期限非常关键，因此根据其位置选择合适的仓库以及运输车辆的路线和调度非常重要。

为了快速建立供应链并快速交付重要材料，应考虑以下四个方面：供应地点选择，资源分配，路径选择和车队调度。供应地点选择问题是选择适当的仓库，为灾区提供材料和设备，而资源分配问题则优化了从供应地点到灾区的材料和设备数量。车队路线问题考虑通过图表[4]找到一个或多个车辆的最佳路线，并且车队调度问题是指在特定的时间将车辆分配到理想路线。当前关于应急供应的文献中的大多数研究工作分为两类：

1. 位置分配问题^[5]-[19]，它们是供应地点选择和资源分配问题的组合;
2. 车队路线和调度问题^[20]-[29]。

然而，很少有研究工作同时考虑位置分配与车队路由或调度问题^[30]-[32]。

位置分配问题通常是在集覆盖问题^[5]-[10]和p-中值问题^[11]-[16]的基础上提出的。关于位置分配问题的早期工作旨在最大限度地减少满足所有要求的地点数目^[5]-[6]，并将后期工作扩展到最大限度地满足各地点的需求^[7]-[10]。从20世纪90年代开始，大多数位置分配问题都使用一般目标函数，如总距离^[11]，成本^[12]-[13]，或运输时间，距离和成本的加权组合^[14]-[16]。最近，多目标优化被考虑用于位置分配问题^[17]-19]，目标是同时最小化每个总成本和最大限度地满足需求。

车队路由和调度问题通常是基于多商品网络流问题和车辆路径问题（VRP）^[20]-[29]制定的。在文献[20]中开发了以总成本为目标函数的确定性多商品多模态网络流模型，并在文献[21]中提出了考虑随机电弧容量，供给和需求的问题的扩展。至于基于VRP的公式，在相关文献[22]中提出了具有最小化不满足需求的目标函数的机会约束规划模型，其解决了供应大规模灾害区域的车辆调度问题。对于空中紧急物资运送，调度直升机和机组人员的问题是根据VRP分层研究和制定的，目的是最大限度地减少不满足的需求或最大限度地满足需求^[23]-[24]。考虑到关键救援物品的优先级以及可能需要多辆车辆进入灾害区，基于拆分交付VRP（SDVRP）模型^[25]制定了多项目，多车辆，多期灾难救援问题。此外，文献[26]-[30] 中还研究了将多商品网络流量问题与分体式运输车路径问题相结合的混合问题, 以规划协调伤员疏散和物资分配。目标是尽量减少未满足的需求和时间延迟的加权总和。

很少有文献考虑到位置分配问题与紧急交付中的路由或调度问题同时存在。Sherali等^[31]提出一种非线性规划模型，从候选名单中选择一组避难所，并为飓风中的撤离人员规划路线。目标是最大限度地减少总的疏散时间。三阶段算法是为了对灾区，分配资源和选择路线进行连续分组，以便快速响应受灾地区的时变救援需求^[32]。在文献[33]中研究了救灾物资的多期分布问题,以动态分配救援物资并通过路线安排车辆。然而，在文献[31]-[33]中研究的问题既没有考虑繁重交通引起的拥塞，也没有全面解决供应地点选择，资源分配与车队路由和调度问题。

实际的应急应用往往要求在较窄的时间窗内满足关键的需求，因此需要与车辆调度和路径问题(SLSR)协同考虑供应地点的选择。由于供应中心的建设往往是在露天环境下进行的，因此在纸上不考虑供应地点、容量和成本。此外，每一供应源都应能向任何客户提供商品，使供应系统能够充分利用分布式仓库，同时也应考虑到大量交通造成的拥挤。还要求每个需求必须在指定的时间窗口内得到满足。

上面描述的SLSR问题是棘手的^[34]。CPLEX软件包中常用的分支和切分等整数规划方法，在实际计算时间内只能解决中小型问题。由于其复杂的约束条件和问题的规模，有时甚至很难找到可行的解决方案。这造成了另一个方面的困难，因为寻找可行的解往往是元启发式方法的第一步，例如遗传算法、蚁群法等。这些元启发式方法在求解SLSR问题方面的潜力将在以后的研究中得到探讨，因为本文所发展的方法已经在很大程度上找到了该问题的解。

拉格朗日松弛法(LR)是求解可分解结构复杂优化问题最有效的方法之一^[35]-[45]。该方法的主要思想是放宽系统宽耦合约束，形成两级优化框架。分解后的子问题在较小的计算量下单独求解，而拉格朗日乘子则在较高的水平上进行更新。由于对偶解一般是不可行的(即一次松弛的约束条件不满足)，基于最优对偶解的最优可行解是基于LR的方法最具挑战性的问题之一。

针对大规模应急物资配送问题，本文基于LR框架中的连续子问题求解方法^[46]-[47]，提出了一种新的方法。这种方法的主要思想是放宽耦合位置选择约束和流量容量约束，并连续求解各个子问题。新方法的一个显着特征是通过在可行性迭代中连续地将一次松弛约束加回到对偶问题中来系统地获得近似最优解。给出了新算法的收敛性证明，并给出了其性质。对多达180个节点和6个商品的运输网络问题的数值试验结果表明，该方法是有效的，并且相应地获得了近似最优解。与通用整数编程方法相比，新方法更有效。

本文的其余部分如下所示。第二节给出了供应地点选择和路由问题的数学公式，然后在第三节中对该公式进行了两个实际的扩展。新方法在第四节中得到了发展，并在附录中给出了收敛性证明。数值试验结果载于第五节，简要讨论了结果和结束语。

2模型构建

图1给出了一个由方向图表示的逻辑网络拓扑, 其弧线与非负容量、传输时间和成本相关。可用的源和接收器被标记为网络中的一组节点。实际上，源节点0,1和2的位置不是聚类的，可以位于路网中的任何位置, 接收器节点也是如此。在不失去通用性的情况下，假设源节点（或汇聚节点）之间没有直接链接，因为这种情况可以通过添加虚拟节点和虚拟弧来等效转换^[48]。

图1 映射拓扑。

可用源节点: 1–3;接收器节点: 7–9;中间节点: 4–6

每个弧线都具有容量、运输时间和成本。

我们的目标是选择一组源节点作为供应仓库,并安排车辆路线,以最大限度地减少总运输距离(或时间),同时保证在一定的期限内的需求数量供应。我们公式中的假设如下:

（1）每个来源可以容纳任何类型的商品, 并可以供应任何接受器;

（2）假定每个来源都有足够的容量;

（3）中间节点上没有存储或缓冲延迟;

（4） 运输能力充足。

假设（1）确保充分利用来源中的商品; 假设（2）和（3）来自应急响应要求; 例如，临时仓库是在露天场地建造的，紧急交货可能会经历一个不友好的环境。假设（4）表明有足够的运输能力（可用运输车辆的数量），例如，当调动军事运输能力时，可以找到一个可行解决办法，在所需时间窗口内满足各种商品的需求。

为方便演示，我们定义以下符号：

源（供应）节点集;

表示弧上的渡越时间，；

决策变量：,表示在时间内运输车辆进入弧线时的商品的数量; 表示所有商品的矢量; 而表示商品的矢量;表示位置选择变量，如果选择了源s，则设置为1，否则为0; b表示所有位置的矢量。

总运输成本（距离或时间）用于表示所选地点的有效性以及来自所选来源的车辆路线和调度决策。这个问题的目标表述为：

约束如下：

（1）动态流量守恒类似于网络流问题中的动态流守恒。间节点中的缓冲器不允许使用。

（2）容量约束。电弧容量被定义为允许在过境时间窗口中遍历弧线的车辆的最大数量, 并由横向时间乘以车辆流量(单位时间)来估计。在最恶劣条件下的路段发生弧形车辆流量

（3）需求。这些制约因素确保必须满足每个灾区对有最后期限的商品需求, 因此, 这些需求被表述为：

（4）仓库选择的限制。约束指示必须选择具有流出的位置, 但允许选择的最大位置数为：

（5）流量限制。这些限制条件确保了截止日期之后的流量是无效的，并且不应该有来自接受端的流量，也不应该流向源头。

通过参考第1节列出的SLSR问题的三个特征，约束（2）-（5）保证快速建立供应链，约束（4）保证及时向灾区提供材料，约束（3）考虑到运输条件和交通造成的拥堵，车队路由和调度方案可以通过一个简单的启发式来构建。

3扩展问题公式

在实际的紧急交付中，对（1）-（10）中定义的基本模型的一些假设可能不太令人满意。 在本节中，我们进行了两个实际扩展，并在第四节结束时讨论相应的解决方法。

（1）如果运输能力不足，则增加运输能力限制约束:

这里，是商品k的供应地点的运输能力。在约束（11）的情况下，可能违反需求约束（4），并且基本模型不存在可行的解决方案。然后，放松需求约束，并将其添加到目标函数中以最大限度的减少未满足的需求，因此目标函数（1）改为（12）：

公式（12）是最小化总加权运输距离（或时间）和不满足的需求。这里是灾区d需求不足单位的权重。（12）中定义的问题受个别约束（2），（3），（5）-（10）和（11）的制约。

注：与（1）-（10）中定义的基本模型相比，新模型具有不同的目标功能，除了（11）中定义的运输能力约束取代需求约束外，受到几乎相同的约束（4）中的定义。

1. 当灾区的需求随时间而变化时, 一定要满足一段时间内的需求, 因此表示为：

这里，p是时间段P的集合的索引，，并且分别是灾区d和商品k的最后期限和要求。目标函数仍然可以表述为:

（16）中定义的问题受到约束

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

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