文摘

本文研究了location-routing应急设施的问题随着时间窗口在需求的不确定性。我们提出一个健壮的数学模型不确定的需求是由两种形式:由红衣主教定义约束集的支持。当救援点的需求价值变化在一个给定的定义集,该模型可以确保每一行的可行性。我们提出一个分支和价格削减算法,其定价问题是一个健壮的资源受限最短路径问题。此外,我们以汶川地震为例来验证该方法的实用性。健壮的模型模拟在不同的不确定性水平和分布并与该计划获得的确定性问题。结果表明,鲁棒模型可以成功运行和维护它的健壮性和健壮的模型提供了更好的保护需求的不确定性。此外,我们发现成本比保护更敏感的不确定性水平层面上,和我们建议的模型还允许控制解决方案的鲁棒性水平通过调整保护水平。在所有的实验中,路由的健壮性成本成本平均增加了13.87%。

1。介绍

环境的恶化,自然灾害,如火灾、地震和海啸也危及人们的生存和发展。因为他们的突然和强大的破坏力,他们经常导致房屋倒塌,道路损坏和人员伤亡,导致大量的生活和医疗材料损失在短期内。灾后救援物资的及时交付是一个重要的保证增加存活率。迅速和有效地运送紧急救灾物资从灾区应急救援设施,满足受灾群众的需求是最重要的任务。特别是在地震多发中国、日本、和沿海国家常见的海啸,建立应急救援设施和救援物资的运输是非常重要的。例如,汶川地震,2008年一场大地震在中国,造成了巨大的伤亡人数由于缺少及时的救援和救灾物资及时交付的失败。总受灾人口达到4625.6万人,造成直接经济损失8451.4亿元。如今,COVID-19还将继续加强,紧急药物输送也至关重要。因此,面对自然灾害,对我们来说是一个很重要的问题建立应急救援设施和应急救援路线合理计划。

然而,自然灾害的不可预知性和救援工作的紧迫性经常紧急部门很难准确获得灾难现场的物质需求。因此,有限的时间和资源的约束下,为了降低物流配送的时间和成本,提高设施选址的鲁棒性,研究是具有重要意义的位置不确定应急救援设施和救援物质分布的安排路线。

事实上,许多决策者通常关注救灾物资的运输。相反,如果不改善应急设施的鲁棒性,不能意识到有效的救灾物资的运输。供给站的位置与整个系统的运作效率也有很大的影响后续材料配送路径规划。材料分布路径的规划直接决定了救援的及时性。因此,有必要整合应急资源位置和路径规划防灾准备。近年来,国内外学者已经做了很多研究应急资源调度和取得了一些结果。

应急设施的研究可以追溯到问题提出的P重心和中心哈基米[1]。Overstreet et al。2]阐述了应急物流规划的复杂性和未来研究方向在梳理大量应急物流的文献;Galindo和出差费3]整理大量文献对应急物流建模从2005年到2012年,发现使用最广泛的应急物流规划仍然是数学规划的方法,并侧重于实用性的假设模型的一部分;Oezdamar et al。4]讨论了自然灾害应急物流和紧急材料分配后,和霍纳唐斯(5]研究了紧急救援物资的分布与GIS相结合;冰斗和霍奇森6)构造一个线性组合模型为紧急避难所的位置;威得恩和霍纳7]讨论了紧急救援的层次位置模型材料。此外,许多学者结合设施选址和鲁棒优化方法。鲁棒优化使健壮的输入数据的不确定性优化模型通过定义的不确定性随机参数集。

有些学者认为应急设施的位置路径问题在某些信息与总成本最小化的目标(8,9]。一些学者也研究了不确定信息下的应急设施位置路径问题。考虑到不确定的研究需求,Caunhye et al。10)建立了一个两阶段随机规划模型与部队的目标最小化设施建设成本和减少救援时间最糟糕的道路。Bodaghi et al。11)研究的问题提供multiresource调度和路由在灾难中逃生。考虑到时间的研究不确定性,艾哈迈迪et al。12)建造了一个模型的目标最小化总救援时间的总和,点球未满足的需求,成本和固定成本的设施单体的基于场景的混合非线性规划优化模型。Zarandi et al。13)对模糊数表示时间的不确定性,建立了模糊机会约束规划模型和总成本最小化的目标。Vahdani et al。14)考虑配送中心能力和仓储能力的不确定性,建立了多周期的连锁和复合三级救援位置路径模型与应急救援时间和最小化最大化的目标路径的可靠性。莫雷诺et al。15]假定需求、供应和道路容量不确定,建立了一个基于场景的两阶段随机规划模型与应急物流和成本最小化的目标成本的未满足的需求在灾区受害者的损失。从这些文献中,我们可以得出结论,在实际问题中,有各种各样的不确定性,有必要考虑鲁棒优化方法来解决这些问题。在文献中,他们的主要方法是描述随机规划、机会约束,和其他方法,或使用鲁棒优化时,只有一个参数仅仅是考虑一个不确定的因素,和使用两个参数来描述需求的不确定性从不同角度并没有参与进来。因此,本文考虑两个参数的变化,也就是说,一个基数约束来描述其需求的不确定性的支持。

在本文中,我们考虑区间不确定性的需求;每个救援点变化的需求,在一个给定的时间间隔。救援点与不确定的需求也不确定的预算限制。这两个约束条件下,救援点的需求定义了不确定支持组,叫做基数约束的支持。不确定性应适用于每一个救援路线,以防止最坏的情况下。此外,像确定性应急设施选址路径,是不可能解决的问题与线性优化。因此,我们使用一个列生成方法鲁棒约束分解成子问题。我们开发一个branch-price和削减算法,子问题的一个健壮的基本资源约束的最短路径问题。在本文中,我们提出一种新的分解策略的情况。该方法应用于一个实际案例(汶川地震)来验证解决方案在强劲的情况下。

1.1。本文的贡献

(1)两个不确定支持集是用来定义需求的不确定性(2)削减branch-price和解决该模型的算法(3)一个真实的案例(汶川地震)是用于验证该算法的有效性和适用性

剩下的纸是组织如下:部分2定义了健壮的应急设施location-routing问题不确定的需求,在不确定性是基于基本约束集的支持。在部分3列生成框架,详细描述了子问题的解决方案,和branch-price削减算法。节4,我们测试我们的模型和解决方案和给的比较鲁棒性与确定性模型的解决方案。

2。鲁棒模型

本文基于托马斯等人的作品。16),一种新的鲁棒路由救灾设施(R-LRP-DR)公式,提出了考虑不确定性的救援需求的材料和交付时间窗口的限制。

2.1。强劲的配方R-LRP-DR

我们可以R-LRP-DR定义为一个有向图 ,和 组节点和吗是弧的集合组成的所有可行的链接,分别。 代表集供应商和 代表集零售商。一组 代表了替代位置建造一些cd,需要构建相应的cd在皮卡和交付过程中基于供应商合作。同时,相同类型的车辆用于皮卡和交付,确保其一致性,和一组被定义为 。每辆车的能力 。在送货的过程中,每个客户 有其相应的时间窗口 和服务时间 。每一位客户 有一个需求 。这里我们考虑到是不确定的。这个不确定的需求参数是随机选择的时间间隔 ,在哪里 表示客户的名义要求 ,和 表示最大的实际需求和名义需求之间的偏差。不失一般性,我们假设 。因此,我们定义一组确定的支持 由于顾客的需求, ,和 。而且,描述偏差的大小变化。因此,在这个时候,可以表现为需求的不确定性和 ;也就是说,可以意识到的不确定性调节的区间范围或价值的 。无论是在小货车或交付的过程中,车辆是有成本的在电弧 。其中,成本在皮卡和交付过程记录 。在皮卡和交付的过程中,车辆必须从每个阶段并返回它。

健壮LRP-DR (R-LRP-DR)的目的是选择一组交叉运输系统和与这些相关的车辆路线交叉运输系统的总成本最小化,包括建立交叉运输系统的固定成本和服务成本的零售商。PDPDC系统中,当零售商的需求订单收到,一系列均匀的车辆从供应商并交付给零售商通过交叉运输系统。应该注意的是,货物必须通过cd和必须不允许直接在车辆之间转移。

为了清晰地描述零售商的需求的不确定性,我们提出一个R-LRP-PDPDC公式如下: 目标函数(1)是减少整个过程的成本,包括应急设施的开放成本和产品的运输成本;约束条件(2)是限制打开的紧急设备的数量;在约束(3),只有一个路径通过每个设施;约束(4)意味着车辆必须进入和离开供应商一旦接和交付过程中,保证了交通流的平衡;约束(5)意味着客户的需求不应超过车辆在整个生产过程能力;约束(6)意味着服务开始时间窗口内,无论是小货车或交付。由Desrochers Laporte [17),我们可以定义 。约束(7)确保交付必须在时间窗内。约束(8)和(9决策变量。如果车辆从节点到节点在上升过程中,= 1,否则,= 0。同样,如果车辆从节点到节点在交付过程中,= 1,否则,= 0。我们注意,因为需求是不确定的,它属于支持设置 ,我们可以进一步写约束(10), 在哪里 指的是向量组决策变量和 ,在哪里是客户的一个子集不超过 ,这样的客户可以访问车辆和客户需求偏差积累和最大化。这样的 确保车辆的负载可以满足任何需求实现和不超过客户的最大需求。

3所示。设置分区配方

我们注意到,在运输期间,每辆车满足约束(10),即使客户的需求是不确定的。在这里,我们使用一种修改版的LRSP设置分区Akc提出的公式(18]。它被认为是是一个可行的路由设置。这些路径相关应急设施。他们从供应商运送至应急设施的应急设施,然后客户;和 是由车辆的路线分配应急设施吗 。然后,给出以下参数和决策变量:参数: 决策变量:

鲁棒LRP-PDP配方如下:

目标函数(13)试图最小化总成本,包括应急设施的开放成本和运输成本。约束(14)确保每个零售商位置有唯一的路线。限制条件(15)确保应急设施的数量。约束(16)和(17)是标准的二元约束变量。

的线性松弛[P]问题是Dantzig-Wolfe (DW)主问题,我们定义一组 这样我们得到约束DW主人的问题。[P]和DW主要问题有大量的变量,和可能的路径的数量通常是如此巨大,以至于明确列举所有相应的列是不切实际的。因此,在这个过程中,我们可以使用列生成(CG)方法(19),通过隐式表达式考虑所有可能的途径 。否则,我们解决子问题找到一个或多个航线-降低成本。让和是双变量与约束(15)和(16)。子问题是一个R-LRP-PDP如下:

R-ESPPRC基本路径和最小的解决方案降低成本。当我们释放基本约束,表示路径的次数p拜访客户 。限制DW主要问题将产生一个疲软下界;R-ESPPRC不同于确定性ESPPRC约束(18)包括内部最大化。

资源约束的最短路径问题通常是通过label-setting算法来解决。鉴于稳健性,Lu和Gzara [20.)提出了一种改进的基于新标签定义算法优势规则。阿尔维斯佩索阿(21)提出了一个不同的标签定义的算法。每个初始解的算法提供了一个虚拟解决方案;每个虚拟解决方案在一定变化范围和使用优势规则不断调整模拟解决方案。另一个选项是检查一系列确定的辅助问题。Bertsimas和Sim卡(22)首次提出这个解决方案策略,健壮的组合不确定目标系数的问题。阿尔瓦雷斯米兰达et al。23)和Goetzmann et al。24]扩展这种策略与不确定的约束组合优化问题。在本文中,我们使用策略推行阿尔瓦雷斯米兰达et al。23)和Goetzmann et al。24]R-ESPPRC转换为一系列确定性ESPPRC和使用经典的算法来解决每个标签定义。

为简单起见,我们先忽略车辆指数并设置作为可行的设置满足约束(17)和(19)- (22)。让的向量 ,让的向量 。定义 为 和 。 和向量的和 ,分别。与 , ,R-ESPPRC重写为

让 ,让二元变量的约束 ,,让二元变量的约束 。因此,我们可以写如下:

然后,公式(26)(P”)可以改写如下:

自(27),而不是最大化内部目标函数 ,我们得到约束(34)。在这个时候,约束(35)和(36)是上述约束(28)和(29日)。现在我们可以直接利用MIP解算器来解决这个问题。然而,为了加快列生成过程中,我们考虑的不确定性转化为确定性,然后选择使用动态编程来解决它,同时生成多个成本减少列。

首先,我们扩展定理Bertsimas和Sim卡的工作22)不确定的情况下约束系数,然后根据阿尔瓦雷斯米兰达et al。23)和Goetzmann et al。24),提供一个替代顺序的方法来解决这一系列的问题 问题。通过约束(28),我们可以得到以下: 。这是由于这一事实 是二进制, 。然后,我们可以把公式(27),

现在我们需要在不同的情况下讨论它。因为它已经假定 ,如果 ;如果 ,为 。因此,我们可以得到以下结果整理:

作为一个结果,可以分解为 子问题: 我们有 ,在这种情况下,当 ,我们可以得到的最优解 。当 ,

方程(42)可以写成:

可以看出, ,(44)是一个一阶线性函数在时间间隔 ;然后最优解获得当 或 。所以,

综上所述,我们可以得到一个分段函数如下:

然后,目标函数可以写成

由于每个子问题都是相互独立的,我们建立一个二级网络为每个仓库 。每个子问题都可以被视为一种资源受限最短路径问题,这里我们提出label-setting算法每个子问题需要解决。参见5获取详细信息。

3.1。预处理

在前面的文献,有些子问题的预处理方案。本研究认为规则相应的启发式Desrochers提出的扩展,Desrosiers,所罗门(25]。

首先,我们考虑局部路径的时间窗口 和 。自约束 的时间窗口在整个生产过程中必须满足,我们将重新定义时间窗口如下所示(见小仲马et al ., 1991):

由于时间窗和约束,一些弧线,不满足可以删除问题的可行解。根据小仲马et al。26),以下弧消除使用问题的约束:(优先级):这些弧直接直接换装是可行的解决方案,所以他们应该被删除: ;和 为 。(时间段):客户的节点必须在自己的时间窗口;也就是说,如果 ,然后删除弧 。[能力]:车辆的容量不能超过;因此,如果 ,然后删除以下弧: 。[时间窗与优先级):皮卡和交付,旅行时间需要满足三角不等式。如果电弧不符合这一标准(包括皮卡和交付的客户),电弧可以删除:如果路径 不可行 ,然后弧 被删除如果路径 不可行 ,然后弧 被删除如果路径 不可行 ,然后弧 被删除如果路径 和 不可行 和 ,删除弧

3.2。分支规则

最后分离算法或最好的解决方案,该变量可以包含noninteger值,此时必须执行的分支。因为有两个不同的二元决策变量的公式,我们采用以下顺序分支阶段:首先,该算法试图分支最接近0.5分变量来产生两个子问题,其中一个是固定的 ,,另一个是固定的 。如果所有变量是整数,那么算法从最小数量的分支变量。

3.3。Label-Setting算法

定价问题的目的是要找到一个旅游最大的树减少消极的成本。考虑到树上拿起货物从仓库到小点,然后传递到小点,最终在仓库,这是合理的去寻找它通过考虑每个传感器的过程。为了解决这个问题,我们提出一种改进的标记算法,提出了弗里亚斯和单27为资源受限的最短路径问题。执行双向搜索,标记扩展向前和向后。在前方,标签从仓库到一辆小点作为第一个访问旅行上的节点树。同样,在相反的方向,标签延伸从仓库到交货点,成为最后一次访问的节点。正向和反向标签树合并,形成一个完整的旅行。广度优先和深度优先搜索方法时使用扩展标签。

4所示。计算实验

4.1。实例描述

本节报道灾难的一组计算结果与“5.12”汶川大地震有关。根据现有需求,模拟生成相关的时间窗口。我们比较健壮的解决方案之间的差异,确定解决方案的成本,使用的车辆数量,不可行方案的平均比例,平均产能利用率。所有算法都是用Java编写的,通过最大化策略和MIP和LP模型是解决12.5。进行测试是一个华硕电脑1.8 GHz处理器,8 GB ram。如果解决方案过程不终止在3小时内,程序终止。

基于“5.12”汶川地震的灾害信息,6候选人应急设施,12灾难站点(如图1),7相同类型的交通工具选择提供食物和帐篷分布服务(假设同样体积的两种类型的材料)。每辆车的固定的使用成本是1500元,每公里的运输成本是5元,和车辆容量是000年40。在表1,我们给的位置和能力六个潜在应急设施和不同的运输成本后离开每个应急设施。我们给每个灾难站点的名义需求表2的基础,在名义值,需求波动在影响点均匀产生很高的不确定性和低的不确定性 。在这个时候,我们描述的最大偏差的影响h_我在需求,只有改变它的值来描述需求偏差的大小,导致需求的不确定性。

4.2。数值实验结果

下面几节介绍的结果我们进行了一系列的实验。这个实验的目的是评估的一系列因素如何影响我们的提议R-LRP-DR解决方案。通过分析这些因素的影响,是否有某些不确定性因素或某些因素的数据变化可以产生一种高风险的解决方案是判断。研究的因素包括需求的不确定性,客户的规模的大小,和一些关键参数相关的不确定性。

4.2.1。准备确定模型的结果

首先,我们解决确定性模型并给出其最优解,如图2。

从图可以看出2当物质需求决定(名义上),设施开放点,D, E, F,设施提供材料需求点4,5,10,11,12;设施D提供材料需求分6和8;设施E提供材料需求点3;和设施F提供材料需求点1、2、7和9。在这个时候,总成本= 72 737.5元。

4.2.2。鲁棒性的和确定的解决方案

为了理解不确定性的最优解的影响,我们比较健壮的解决方案的最优目标值,确定解决方案。首先,我们得到了名义需求下的确定性优化解决方案在这种情况下(如图2)。然后,通过调整需求的不确定性和不确定性,我们得到的数据3和4。在表3,我们给不同的不确定性和平均增长目标价值的健壮的解决方案和不确定性下的可怜的平均最优水平。

接下来,我们观察系统的鲁棒性通过考虑浓度较低的不确定性和不确定性的需求 。

从图可以看出3,在考虑需求较低的不确定性和不确定性参数设置 ,还有四个设施开放点,但他们改变,C, D, F,在设施提供材料需求点4、5、11和12;设施C提供材料需求点3和7;设备需求分6和8 D提供材料;和设施F提供材料需求点1、2、9和10所示。在这个时候,总成本= 73 931.5元。

图4显示设备的开当需求不确定性和不确定性高的设置参数 ,和成本= 75 046.3元。

表3显示了不同的不确定性集和的平均增长目标价值和健壮的解决方案下的平均最优性的不确定性水平。

最后,我们给出了车辆路径在高水平和不确定性 ,如图5。

表3报告的平均统计健壮的和确定的解决方案。数据代表了不同的不确定性,目标值的平均增长,平均时间的增长。从上面的图表中,我们可以看到,在同样的不确定性水平集参数,当不确定的需求增加,设施的位置会改变,成本将会增加。在同样的不确定需求,增加的不确定的水平集参数t,逐渐增加,成本和设施的位置可能会改变。从表可以看出3,当不确定性水平很低,即使 ,增加成本也低于高水平的不确定性 。这表明价格更为敏感的不确定性比水平的保护。在所有的实验中,路由的健壮性成本成本平均增加了13.87%。值得注意的是,我们提出的模型允许解决方案的鲁棒性水平控制通过调整保护水平。

5。结论

自然灾害的发生将导致严重的经济损失,所以应急设施选址路径问题的研究是一个热点。在本文中,我们提出一个健壮的模型设施location-vehicle-routing问题不确定的需求。这个问题的动机是在自然灾害应急材料调度路线。当遇到自然灾害时,它通常是受到环境因素的影响,及其需求通常是随机的,是很难估计的概率分布。因此,鲁棒优化提供了一种更合适的方法和框架。本文通过公式化的处理和分解,我们可以使用列生成方法来解决它。

我们使用基数约束集定义的不确定性支持和提供一个健壮的位置路径公式模型。然后,我们提出一个branch-price切算法,它使用标签算法在切割过程中,为了生成列生成的多个列在每个迭代中,而不是单个列。最后,我们使用实际数据(汶川地震)来验证模型的实用性。实验结果表明,一方面,健壮的模型解决了困难,需求的不确定性问题的线性优化模型不能解决;另一方面,健壮的模型弥补劣势,随机规划取决于准确的概率分布;和健壮的模型仍然保持一定的鲁棒性。此外,分支和削价算法成功解决的优化问题在合理的时间。我们惊奇地发现,当不确定性水平很低,甚至 。成本增加也不到的高不确定性水平 。这表明价格更为敏感的不确定性比水平的保护。在所有的实验中,路由的健壮性成本成本平均增加了13.87%。请注意,我们建议的模型允许解决方案的鲁棒性水平控制通过调整保护水平。

应急设施的location-routing问题是当前研究的热点。同时,本研究应用也有助于为应急管理和可持续发展奠定理论基础。虽然该研究考虑需求不确定性的主要因素,仍有一些不足,例如,应用程序的时间和成本的不确定性和设施中断风险应急设施选址路由。未来的研究可以从这些方面开始。

数据可用性

使用的数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突。

确认

这项研究是由上海社会科学项目(不支持。2020 bgl010)。