文摘
在这项研究中,我们关注的是健壮的标准软时间窗车辆路径问题(VRPSTW)。主要目标是找到一个健壮的解决方案,提供最好的最坏的情况下性能VRPSTW下不确定旅行时间。的标准是用于这个研究,如绝对鲁棒性,健壮的偏差,和相对的鲁棒性作为比较的基础。VRPSTW变得复杂时,旅行时间是不确定的。这种不确定性可能导致交通堵塞,交通事故,或恶劣天气条件。实验使用基准测试问题。场景的数量生成随机旅行时间的间隔,等于4,6,8为每个问题集实例。可以用每组问题实例的比例的不确定性 ,= 0.2,0.4,0.6和0.8。本研究将证明最显示强劲的这些情况是健壮的标准偏差和相对的鲁棒性。决策者的最重要的部分是确定不确定性比例涵盖所有需要考虑的不确定性。
1。介绍
车辆路径问题(VRP)是在运输和物流领域。这对推动智能城市中发挥着重要作用。智能城市的物流应该支持所有物流平台和帮助用户做出重要的决定。的问题,为客户提供从中央仓库运输路线,以节省运输成本提出了Dantzig和公羊1]。软时间窗的车辆路径问题(VRPSTW)是一个VRP的变体。VRPSTW是一组路线的解决方案的客户组成的序列。每个路由的目的是确保在指定的时间内交付框架称为窗口。此外,在VRPSTW,窗户可以调整是否支付一个点球。因此,VRPSTW问题的目的是找到运输路线节省旅行费用和罚款的运输成本。服务时间间隔VRPSTW如图1。Kabcome和Mouktonglang2)提供了一个明确的书面数学模型VRPSTW问题有效地解决了。从数值结果,很明显,通过添加服务惩罚约束,充分可以解决这个问题,它提供了另一个解决问题的办法。Taillard et al。3使用禁忌搜索,metaheuristic方法,软时间窗的车辆路径问题。分钟(4]解决了多目标与软时间窗车辆路径问题的公共图书馆分配系统。
这VRPSTW变得复杂时,旅行时间是不确定的,由于交通条件,如交通堵塞,交通事故,或恶劣的天气条件。阿格拉et al。5VRP)视为一个强劲的对手。他们认为出现在海上运输延误的问题应该被考虑。因此,我们有兴趣研究VRPSTW问题不确定的旅行时间。用于解决问题的一般原则与不确定性分为两类:确定性优化方法和随机优化方法。确定性优化方法有一些好的属性,如数学模型更容易编写和理解。确定性优化问题的规模通常是小于随机的。然而,它也有一些缺点当问题包含的不确定性,因为这种方法发现解决方案通过估算的不确定性在一定值或使用最频繁的情况下代表的问题。解决方案是解决只有选择的情况。不确定性较高时,这种方法的效率立即下降。随机优化方法是找到解决方案从多个不确定性估计。 See [6]更多细节,作者认为随机VRP随着时间的windows版本。此方法需要历史数据的不确定性进行了分析使用统计方法和表达的概率值来表示的不确定性。通过这种方式,随机方法包含不确定性的解决一些问题的能力。然而,如果我们考虑到实际应用,随机方法带来了困难和不回应的需要决策者,因为数据收集需要很长一段时间。随机方法的主要缺点是,解决方案只能来自于期望值的解决方案。在这种情况下,决策者在实际情况发生时必须承担风险最小或最大范围。即使只出现一次这种情况,它可能造成严重后果的可靠性或失去机会。
本研究着重于对决策者提供的实际使用鲁棒优化方法。解决方案必须是适用于不同的使用条件。鲁棒性方法是本研究的一个重要目标,找到最合适的路线,一条是能够承受旅行时间的不确定性。本文提出了一种鲁棒离散优化方法VRPSTW与不确定的旅行时间。通过求解VRPSTW多次,极大极小优化问题成为本文的主要目标(即。健壮的标准下,找到一个健壮的解决方案)。
在下一节中,我们提供了一个回顾相关文献的鲁棒离散优化问题。部分3提出了解决问题的方法。部分4代表了结果和相关讨论。VRP问题的数值实验使用基准数据在所罗门的VRPTW [7]。最后,给出的结论部分5。
2。文献综述
这种不确定性下的决策问题开始讨论1955年由Dantzig [8),是由Charnes和库珀9]。很多不确定性的研究依赖于基于追索权模型或概率的随机规划技术约束和不确定性需求,供应,旅行时间,和许多其他人。我们将Ben-Tal et al。10),这两种方法进行了较为详细的试验研究。在这项研究中,作者感兴趣的是找到解决方案,满足条件承受不确定性或寻找最好的价值在一个糟糕的情况。Kouvelis和Yu (11)描述一个健壮的决策框架,可以用来找到持久的解决方案,包括三个主要部分:(1)创建不确定数据的各种情况,(2)选择标准判断持久的解决方案,和(3)创造持久的决定最合适的模型。
寻找解决方案,对不确定性的过程如下:让是一组场景, , 数据集,是一组数据,根据情况是不确定的 , 是所有可能的解决方案和 , 组决策变量和 ,和 函数用于寻找解决方案的每个场景和每个场景的最优解满足下列问题:
从方程(1),众所周知,解决确定性问题数量=数量的情况。我们使用三个健壮的标准寻找健壮的解决方案,给出如下。
定义1。绝对鲁棒性标准 :让是由决策变量的绝对鲁棒性标准
定义2。健壮的偏差 :让是由决策变量的偏差标准
定义3。相对的鲁棒性 :让是由决策变量的偏差标准
3所示。方法
本节介绍了数学模型解决健壮的解决方案,也就是说,最好的最坏的情况下的性能VRPSTW下不确定旅行时间。第一部分介绍了软时间窗车辆路径问题(VRPSTW)。第二部分介绍了稳健与软时间窗车辆路径(RVRPSTW)。
3.1。软时间窗的车辆路径问题(VRPSTW)
VRPSTW上定义一个有向图 ,在哪里 是一组顶点(是仓库)和弧是一组 代表之间的连接仓库和客户或客户 。
以下介绍了符号制定VRPSTW的数学模型。
3.1.1。指数
索引节点 指数的车辆
3.1.2。集
是一个节点集(是起源和目的地) 是一组客户 是一组车辆
3.1.3。决策变量
是违反程度的软时间窗的上界的客户 是客户的到达时间
3.1.4。输入参数
旅游成本来 是一个时间节点来 是协调的 是协调的 , 是一个客户之间的距离和 是客户的需求 ,和迟到的惩罚成本每小时客户 是早期服务节点而不受惩罚 是最后一次服务而不受惩罚 是最后一次服务节点与惩罚 是一个客户服务时间 车辆的容量
VRPSTW必须满足以下的解决方案:(1)每辆车只在中央仓库开始和结束(2)每个客户都可以由一个且只有一个(3)总额不得超过车辆的容量需求(4)每个客户必须在相关的硬时间窗(5)如果车辆到达早在客户 ,它可以等到时间即时开始服务
数学上VRPSTW可以表示如下: 受
我们最小化目标函数(5),包括两个部分:第一部分是旅行成本和第二个组件的总处罚违反软时间窗。
约束(6流保护车辆。也就是说,对于 ,每辆车结束只有一次在仓库,没有弧源于节点 ;为 ,每辆车开始只有一次在仓库,没有弧终止节点 ;和表明一个车辆进入和离开每个客户节点。
约束(7)要求每个客户服务到底是一次。
约束(8)是描述的流守恒约束车辆路径。
约束(9)确保车辆容量约束并不违背。
约束(10确保时间的可行性。
约束(11)保证服务的起始时间不违反给定硬时间窗。
约束(12软时间窗的违反。
3.2。与软时间窗的车辆路径(RVRPSTW)
的方法求解鲁棒离散优化与确定旅行时间相当于VRPSTW极大极小优化问题。我们使用了一个健壮的决策框架Kouvelis和余11]找到可持续的解决方案。首先,创建数据的不确定性考虑情况下仓库和客户之间的旅行时间和每个客户之间的旅行时间。事实上,让 是所有可能的场景 旅行时间在基地的情况 每个场景的旅行时间依赖如 ,和随机选择的 在每个场景的集合所有可能的解决方案 ,和 决策变量和 在每个场景中是最优的解决方案 该函数用于寻找解决方案吗的每个场景 在每个场景的最优值
因此,对于每一个情况下,我们必须找到最优值从上述VRPSTW问题:
因此,我们可以找到最优值的每个场景使用方程(13)。我们注意到,解决问题(13)的许多倍数量的场景。然后,方程(13)是一个函数来表示的。
之后我们有最优值的VRPSTW对于每个场景,下一步是找到极大极小优化问题的主要目标,这是找到的最优值 。
我们首先找到最高的价值所有的场景。健壮的标准被认为是绝对的鲁棒性定义1中所描述的,健壮的偏差如定义2所述,和相对的鲁棒性定义3中所描述的。
之后,我们选择结果从所有可能的解决方案的健壮的解决方案,提供最低的价值,可以在发生最坏的情况下获得的。
与软时间窗的车辆路径(RVRPSTW)可以表示如下: 受 在哪里 该函数用于寻找解决方案吗每个场景和的最优值是VRPSTW为每个场景。
最后,我们比较三个标准的性能通过使用相对比: 在哪里是一个健壮的解决方案或或和解决方案的基本情况。
这个过程找到RVRPSTW总结如下:(1)构建一个基本的情况由固定的旅行时间 。(2)生成所有可能的场景比例的不确定性通过选择从 。(3)找到最优值和最优解的每个场景 。(4)找到最高的价值所有场景的健壮的标准: (5)找到这是健壮的解决方案 (6)比较三个标准的性能通过使用相对比 。
4所示。结果与讨论
这个演示使用基准测试的所罗门的VRPTW问题[7]。我们随机生成软时间窗的VRPSTW VRPTW的时间框架。所罗门的VRPSTW将问题划分为6类型的实例,包括类型R1、R2, C1, C2, RC1和RC2。在这项研究中,我们发现R101的健壮的解决方案,C101, RC101, R201, C201, RC201客户的数量等于25。场景的数量生成随机旅行时间的间隔,等于4,6,8为每个问题集实例。可以用每组问题实例的比例的不确定性 ,= 0.2,0.4,0.6和0.8。
我们检查情况R101的健壮的解决方案通过使用6一样的场景和0.4为了观察健壮的解决方案的行为。我们从所罗门的进口数据VRPSTW问题,让 , ,和 。从这些进口数据,我们有编码和解决VRPSTW利用AIMMS 4.9。结果给出了表1- - - - - -4。
接下来,我们提出极大极小优化问题,这是找到的最优值。
从表中所示的极大极小优化问题2- - - - - -4过程,我们可以得出结论,显示在表的结果5。
另外,我们考虑到成本问题的健壮的解决方案R101当场景的数量是4,6,8。不确定性的百分比= 0.2,0.4,0.6和0.8。结果给出了表6- - - - - -8。
从健壮的标准解决方案之间的比较,我们发现影响解决方案的重要参数不确定性的百分比 。结果在表6表明,当不确定性的百分比从0.2增加到0.8,最优值也增加。这是因为每个路线的旅行时间是由最小和最大的时期。时的值的增加,时间的范围是广泛的,而场景的数量不会影响的最优值。从表7,我们可以看到,当场景数量的增加,最优值几乎没有变化,没有增加的倾向。我们研究在所罗门的其他类型的问题,所有问题的结果显示了相同的趋势。因此,确定场景的数量不是一个重要的因素影响实验结果的质量。从表8,这一比率强劲的性能标准清楚地表明,本研究的良好的决策标准偏差和相对强劲的鲁棒性。他们为这些情况下提供最佳的性能。
5。结论
在这项研究中,我们提出一个数学模型的RVRPSTW找到健壮的解决方案,提供最好的最坏的情况下的性能VRPSTW下不确定旅行时间。从实验中,我们发现,影响解决方案的重要参数不确定性的百分比。场景不影响鲁棒最优值。这项研究的良好的决策标准偏差和相对强劲的鲁棒性。不同的选择不同的标准创建解决方案的拨款取决于决策者的目的。决策者的重要的事情是确定不确定性比例涵盖所有需要考虑的不确定性。总之,本文的结果可以受益的决策者做出决定同样的问题。
数据可用性
使用的数据来支持这项研究的结果已经在所罗门的VRPTW沉积。
的利益冲突
作者宣称没有利益冲突。
确认
这项研究受到了清迈大学Rajamangala理工大学现代代数学,数学和卓越中心,切,如果大城府Rd,泰国曼谷。