解决自行车自行车共享系统的重新定位问题:两阶段随机规划模型

文摘

在这篇文章中,一辆自行车在研究随机需求重新定位问题。问题是制定作为一个两阶段随机规划模型的优化路由和装卸决定重新定位卡车在每个车站和仓库在随机需求。模型的目标是最小化预期的运输成本的总额,预期的惩罚成本站,和仓库的储存成本。研制了一种模拟退火算法来解决模型。数值实验进行的一组实例从20到90车站展示解决方案算法的有效性,提出了两阶段随机模型的准确性。

1。介绍

自行车分享系统(BSS)作为一种可持续的手段和无碳运输可以有效地解决“第一和最后一英里”问题的城市公共交通。BSS近年来已经得到了越来越多的流行是因为它不仅可以减少城市污染排放和交通堵塞,也被认为是一种有效的方法来改善用户的健康(1]。BSS由仓库和几个站,分散在不同的城市的街道。BSS的成功取决于自行车的可用性。由于用户的租赁自行车,经常有在某个车站系统的不平衡的情况下,即,有盈余或没有足够的自行车在车站。换句话说,要么有盈余自行车站时,他们会被浪费,没有用户会需要他们,或者在某些站在那里没有足够的自行车,用户的需求无法满足。确保自行车站在系统的可用性,BSS需要雇佣再分配卡车将自行车从车站到车站,根据需求平衡自行车的数量在每一个车站。这个问题通常被定义为:自行车BSS (BRP)的重新定位问题。BRP的主要目的是为了平衡供给和需求的自行车在车站想提高用户满意度,而与此同时,减少运输成本再分配卡车尽可能多。根据分类Berbeglia et al。2),自行车重新定位问题本质上是一个多对多的皮卡和交付问题,这是第一次被证明是一个np难问题,Benchimol et al。3]。

一般来说,现有的工作假设每个车站的再分配需求BSS中的确定性输入参数(4- - - - - -21]。也就是说,这些模型严重依赖的装卸数量分配卡车在每个车站提前给予。然而,这种强烈的假设通常不能在现实世界的情况,一般在城市公共交通需求包含不确定性和随机性22]。所指出的弗里克和恐吓23),用户需求的不确定性的影响不应被忽视,当学习BSS的性能。作者也表明,将知识的未来需求可能导致更精确的和健壮的决定重新定位。

另一个挑战,可能没有收到足够的重视在BRP考虑仓库的储存成本。BRP的自行车从自行车盈余站转移到另一个车站不足需要实现供需平衡自行车站在BSS来满足用户的需求。这完美的平衡供应和需求重新定位手术后必须首先确保BSS的内部平衡,即。自行车盈余站,自行车的数量应该等于自行车在自行车的数量不足。在实际操作过程中,一些自行车可能丢失或损坏后投入使用。经常发生这种情况,可能会导致固有的BSS的供需失衡。的自行车不能BSS的电台之间的平衡,它们从或交付回仓库的成本增加仓库的储存成本。一些BRP模型只是以为仓库的容量是充分的。因此,一些自行车可以捡起自行车仓库来满足需求的缺乏,和/或一些自行车自行车盈余电台可以带回仓库,为了达到一个完美的供需平衡站在BSS (4- - - - - -7]。不幸的是,这些现有的工作尚未考虑BRP的仓库的储存成本模型。

随机规划是一个技术设计数学规划模型与随机需求,帮助决策者做出更准确的决定当需求的随机性的影响不容忽视。虽然随机规划的优化结果不能满足所有未来的场景,它们帮助获得高于平均水平的性能在处理随机需求。

为了解决上述问题,在本文中,我们考虑的随机性质BRP通过捕获和建模的不确定性系统中使用随机规划再分配需求。特别是,我们提出一个两阶段随机规划模型随机需求的自行车重新定位问题(BRPSD)。在第一阶段,我们确定路由决定,“此时此刻”必须做出决定前再分配需求的实现。然后,进入第二阶段,我们进一步确定装卸决定在每个车站和仓库,在“观望”决策考虑到未来的不确定性。我们将持有成本模型,这样整个BRPSD的目的是为了确定最佳路线的重新定位卡车和最优装卸数量在每个车站和仓库,这样运输成本的预计总额,惩罚成本站,和仓库的储存成本最小化。

本文随机分配要求由一组离散的场景建模,并给出一个预定义的发生概率为每个场景。总结了本文的主要贡献如下:(1)一般的基于场景的两阶段随机规划模型随机需求的自行车重新定位问题(BRPSD)介绍。该模型考虑了仓库的库存持有成本在环境中允许仓库装卸活动。(2)一个高效metaheuristic,即模拟退火算法解决BRPSD定义。(3)考虑再分配需求为随机需求的必要性在BRPSD进一步讨论了数值实验。

本文的其余部分组织如下。我们回顾相关的文献2并描述问题的数学公式3。节4,提出改进的模拟退火算法来解决模型。然后,我们目前的实验结果5本文的结论和讨论潜在的未来的研究部分6。

2。文献综述

我们所知,Benchimol等人第一次正式和地址(BRP的3]。自那时以来,各种模型和解决方案算法BRP的讨论了在过去几十年。

我们简要回顾与本文相关的研究,包括启发式和metaheuristic解决方法,为解决BRP的确定性BRP和模型与随机需求。

2.1。确定性BRP启发式算法解决方案

根据朋友和张8BRP),可以分为完全和部分根据严格的重新定位问题需要进行重新定位。前的问题,实现电台之间的完美平衡的约束被认为是硬约束,后一个问题,它是一种软约束。

在完整的重新定位问题,每个站必须满足的最优库存重新定位后操作。一个迭代局部搜索算法首先应用克鲁斯等。9)解决单车BRP然后用Bulhoes et al。10)解决multivehicle BRP的版本。后来,朋友和张8)静态建模BRP自由浮动的自行车共享系统,提出了一个混合嵌套大邻域搜索变量社区应对BRP下降算法。戴尔中保et al。11)开发了一种破坏和修复metaheuristic算法,利用有效的建设性的启发式和几个一起解决BRP本地搜索过程。总的来说,完整的重新定位问题的目标主要是追求最低运输成本确定路由决策。这是一个挑战,有效地应用这些方法在实际系统中还有其他同样重要的标准,忽视了在这些模型。

部分的重新定位问题,理想的库存重新定位后的每个车站不一定是实现操作。尽管如此,这些问题不仅是追求的目标最低运输成本通过确定路由决策,也尽量减少用户的不满通过确定在每个车站装卸的决定。在文献中,一个3步骤提出的数学启发式multivehicle BRP的形式等。6]。在他们的方法中,电台首先节约启发式集群。然后,通过构造集群的路线。最后,通过站在每个集群路由序列和序列通过集群。最后两个步骤制定为一个混合整数线性模型求解最大化策略。你(12)提出了一种两阶段启发式multivehicle BRP下最低服务需求计划。在他提出的模型中,每一个阶段代表了一个决策过程。在第一阶段,装卸决定每个时间段的所有电台是由一个线性规划模型。然后,在第二阶段,路由决策是由迭代方法通过两个参数敏感的数学模型。

除了分阶段启发式算法,许多启发式和metaheuristic解决方案方法已经提出了解决确定性BRP,仅举几例,禁忌搜索(5,13)、遗传算法(14),化学反应优化算法(15,16),人工蜂群算法(17),约束编程(18,19),可变邻域搜索(20.),迭代局部搜索(21),大的邻域搜索算法(7)等。尽管如此,这些现有的实际应用方法仍然困难,常常带来意想不到的结果。这是因为brp用户需求通常存在于现实世界的不确定性;然而,它还没有被这样的确定性模型。

2.2。与随机BRP的要求

我们所知,有限的文献认为随机BRP的要求。两阶段随机规划与资源模型已成功地用于解决自行车重新定位的问题,因为他们允许modeler代表路由计划和装卸活动一起通过第一阶段的决策变量。戴尔中保et al。24]似乎先锋论文提出了一种基于场景的两阶段随机模型的自行车重新定位的问题,考虑再分配站作为随机变量的要求。作者提供五个具体过程以及启发式算法结合correlation-based建设性的过程与解决BRPSD盾本地搜索方法。启发式算法只考虑运输成本在评估本地搜索移动和只接受一个可行解的可行性检查本地搜索移动通过一个有效的策略。

然而,BRPSD不同于我们在以下三个方面的问题。首先,该模型的目标是最小化预期的总旅行距离的卡车和惩罚成本,而我们的问题最小化预期的旅游总成本的卡车,电台的惩罚成本,仓库和处理成本。第二,在我们的问题中,我们测量使用本地搜索举动不仅运输成本,而且预期的总成本。第三,我们开发一种方法来快速确定可行的装卸数量在所有车站和仓库在任何给定的路线。因此,没有必要检查本地搜索的解决方案的可行性。

也有一些近期作品,研究随机BRP的变体叫做定义的随机需求(OD)而不是站的再分配。例如,Maggioni et al。25]提出两阶段随机规划模型来确定最优的自行车数量分配到每个站,转船的最优数量自行车从一站到另一站,分别。他们使用AMPL和最大化策略来解决模型。燕et al。26)应用时空网络模型来确定最优位置的自行车,自行车车队分配,自行车路由。他们的解决方案基于threshold-accepting-based启发式算法。

从文学的上述评论,我们可以看到,目前学者们提出了一个启发式算法来解决确定性BRP丰富。然而,我们所知,还没有工作,有效地采用metaheuristic算法解决BRP具有随机需求。本文的研究弥补了这种理论空白。

3所示。数学公式

自行车共享系统研究了由一个仓库和一组站。每个站都有一个再分配对每个场景的需求,表明当前的库存水平和最优库存水平为每个场景。对于一个特定的场景,如果再分配需求在一个车站是正的,车站是定义为一个小车站;如果再分配需求在一个车站是负的,那么车站被定义为一个配送站,应该提供自行车从皮卡站;如果再分配需求在一个车站等于0,则称为平衡站车站。平衡的站也必须去。

我们认为只有一个卡车BSS与给定的可用容量。卡车从皮卡收集自行车站和运输配送站。可以从一些自行车或交付回仓库,每个站只允许访问一次。此外,类似于刘et al。16),自行车是假定为停在BSS的任何地方;因此,车站能力约束。

决定有关装卸站和仓库的数量在每一个场景都是独立,根据相应的需求情况。然而,卡车的路由决策必须考虑到所有可能的场景的需求。这意味着路由决策对所有场景都是一样的。因为路由决策,所有的场景都是一样的,但不同的装卸决定每个场景,可能存在短缺或过剩的自行车站在每个场景。在这种情况下,下面的两级自行车重新定位问题随机需求(BRPSD)自然就出现了。在第一阶段,BRPSD旨在构建一个路线的卡车从结束开始在每个车站的仓库只访问一次。在第二阶段,BRPSD旨在确定最优装卸数量在所有车站和仓库,以确保解决方案的可行性后给定的路线在第一阶段。BRPSD的目标是最小化旅行费用之和的卡车(第一阶段目标函数)和预期的总损失成本在所有车站和持有成本得宝(阶段目标函数)。

3.1。两阶段随机规划模型

我们的目标是确定所有的电台访问的顺序最小化运输成本,以及装卸决定在每个场景中最小化总期望损失成本和持有成本。我们制定这个问题作为一个两阶段随机规划问题。鉴于离散概率分布的情形发生,制定SPBSD解决的研究如下: 受

目标函数(1)被定义为加权和运输成本和预期的惩罚成本的电台和持有成本在仓库所有场景。约束(2)指出,卡车离开仓库只有一次并返回到仓库。约束(3)确保卡车可以访问一个车站只有一次。约束(4)确保如果卡车来到车站,车站必须离开。约束(5)是subtour消除约束(27]。约束(6)确保车辆上的负载不能超过卡车容量。约束(7)要求自行车装上的数量或卸载卡车在一个给定的车站从卡车装载之前和之后的区别车站。约束(8)确保辅助变量非负。约束(9)- (10)确保多余的数量/松弛的自行车在车站和卡车上的自行车数量非负整数。约束(11)定义了是一个二进制变量。

4所示。解决方案的算法

场景的数量= 1时,研究BRPSD减少古典确定性自行车重新定位的问题,一个np难组合优化问题。我们采用模拟退火(SA)解决BRPSD研究。SA是一个metaheuristic算法基于本地搜索,可避免陷入局部优化通过接受概率少的贫穷的解决方案的过程中迭代。它已经成功地应用于各种确定性组合问题[28,29日)和随机组合问题(30.,31日]。

我们的算法,称为SA_BRPSD由两个阶段组成:构建最初的解决方案和改进初始解的邻域搜索机制。这部分的结构组织如下。节4.1,我们提出的启发式方法产生初始解。在初始化过程中,两个主要决策必须:路由决定(在部分4.1。1(即)和装卸的决定。、库存决策)(节4.1。2)。然后,在节4.2,我们详细描述中使用的本地搜索运营商这个SA_BRPSD,即交换、搬迁和2-opt。之后,主要基于SA算法流程_BRPSD框架提出了部分4.3。

4.1。构造初始解

自从BRPSD决策过程分为两个阶段,本文决策分为两个阶段:确定路由决策在第一阶段,和装卸的决定是在第二阶段决定的。初始解的构造过程如下,这是大致分为两个主要阶段。

以下4.4.1。构造的初始路由所有场景

自从路线在所有场景都是一样的,贪婪启发式算法用于快速构建初始路线通过忽略随机分配需求。在这部作品中,最近的原则是用来构造初始路线通过插入站。

4.1.2。确定装卸决定为每个场景

对于一个给定的场景和相应的再分配需求在车站我在该方案中,Second-Stage-Opt程序使用一个简单的原则来快速生成初始可行装卸决定,然后使用再优化启发式算子来改善初始加载和卸载的决定。的细节Second-Stage-Opt过程如下。步骤1:确定初始装卸数量的所有车站和仓库。每个车站的装卸数量被定义为相应的再分配需求。因为仓库的需求是0,装卸数量也定义为0。结果,生成BRPSD的初始解,包括两级决策,即路由决策和装卸的决定。很明显,最初的解决方案往往是不可行的。第二步:调整一些电台的装卸数量达到一个可行的初始解。如果自行车的数量直接从站在卡车旅行时我到车站j在场景 ,最初的解决方案是不可行的。在这种情况下,装卸站我应该调整。集 ,然后站的装卸数量我调整减去从原来的数量。步骤3(再优化):再优化算子的基本思想是优化解决方案的启发式方法调整装卸站和仓库之间的数量(5,7]。本文从仓库收集的一些自行车可以满足交付要求的一些站点,还有一些自行车从站可以交付到仓库的重新定位。在这个过程中,有两种情况。在第一种情况下,卡车拿起额外的自行车当它开始从仓库并将他们在一些站点。在第二种情况下,卡车拿起一些站和更多的自行车滴当它结束得宝。

4.2。社区结构

摘要局部搜索算子旨在路由决策。三种经典运营商交换移动,移动搬迁,2-opt移动。这些操作符也经常用于其他BRP问题。每一个新的社区解决方案是由这三个动作以同样的概率。注意,在局部搜索算子执行之后,新的解决方案需要改进Second-Stage-Opt程序获取阶段的决定。交换,N¹从路线:随机选择两个站,然后交换搬迁,N²:随机选择一个电台,删除它从目前的路线,然后插入到另一个位置2-Opt -N³:随机选择两个站,交换两个站的位置,改变路线的方向在两站之间

4.3。拟议中的SA_BRPSD

算法1提供了SA的伪代码_BRPSD。参数T₀表示初始温度;T_E是最后的温度;α是用于控制制冷系数;我_iter显示生成的数量在一定温度下的新的解决方案;和马克斯_iter的最大数量是接受在一定温度下的新的解决方案。在本节中,我们使用年代₀和年代^最好的表示到目前为止获得的初始解决方案和最佳的解决方案,分别。最好的客观价值F(年代^最好的)将目标函数值的最佳解决方案年代^最好的。

	获得初始解年代_0。
	模拟退火的设置参数,T₀,T_E,α,我_iter,马克斯_iter
	集年代^最好的⟵年代₀;年代^当前的⟵年代₀;T⟵T_0。
	而T≥T_E做
	米⟵0;n⟵0;
	而米≤我_iter&n≤马克斯_iter做
	年代⟵本地搜索(年代^当前的,N^k);
	年代^新⟵Second-Stage-Opt(年代);
	Δ⟵F(年代^新)−F(年代^当前的);
	如果Δ≤0然后
	年代^当前的⟵年代^新,n⟵n+ 1;
	如果F(年代^当前的)≤F(年代^最好的)然后
	年代^最好的⟵年代^当前的;
	结束
	其他的
	如果然后
	年代^当前的⟵年代^新,n⟵n+ 1;
	结束
	结束
	米⟵米+ 1;
	结束
	T⟵α⃞T;
	结束
	返回:年代^最好的

所示的算法1SA的内循环_BRPSD算法,随机新邻居的解决方案年代^新最初产生于本地搜索过程改善一期决定然后紧随其后Second-Stage-Opt程序生成阶段的决定。内循环的停止标准是生成的我_iter新的解决方案或接受马克斯_iter新的解决方案在当前温度T。当当前温度T减少到T_E,SA_BRPSD算法终止。

5。数值例子

在本节中,数值例子进行检查的有效性和效率提出模型和求解算法。此外,研究了考虑随机需求的必要性分析完全信息的期望值(EVPI)和随机解的值(VSS)。

在这项研究中,我们考虑的实例24)进行数值实验(实例可用http://www.or.unimore.it/site/home/online-resources)。实例的大小范围从20到90个车站。总共有20实例和30为每个实例场景。在任何情况下,第一站选择仓库。为了更好地分析相关参数对解的影响的随机模型,对于一个给定的集合N₀,站我和站j属于一组N_0,运输时间,我们重新定义参数t_ij作为t_ij=t_ij/分钟{t_ij}。

SA_BRPSD在Matlab编写,所有计算实验进行了电脑的英特尔酷睿i5 - 4590 CPU @ 3.30 GHz和4 GB RAM。每个实例运行10次,最好的和普通的解决方案,10分的平均计算时间被用来评估算法的性能的解决方案。

SA_BRPSD提出了研究依赖于五个参数,即初始温度T₀;最后的温度T_E;系数用于控制冷却α;的数量在一定温度下生成解决方案我_iter;和接受的解决方案的数量在一定温度下的马克斯_iter。一些初步实验后,算法得到的结果通过设置T₀= 20,T_E= 0.1,α= 0.97,我_iter= 3∗|N₀|,马克斯_iter= |N₀|。

5.1。术语和SA算法之间的性能比较

在解的质量和计算效率,表1- - - - - -4显示比较结果行话和SA_BRPSD在不同的卡车容量问,持有成本C_h,站的数量。CPU的平均计算时间(以秒为单位)表明SA_BRPSD分别或行话的计算时间。差距_最好的(%)和差距_Avg(%)表明SABRP的性能相对于基于最好的行话和平均客观值,分别。当|N₀|≥50岁的术语不能获得任何可行的问题解决方案,因此,结果没有显示在表中。它也通常在3600秒内未能获得任何全局最优解甚至小型问题(有四个例外下结果的实例华盛顿(20)2)。从表1- - - - - -4,我们可以看到,SA_BRPSD术语在所有情况下,都要快得多。,我th作为better time efficiency to solve the BRPSD compared to Lingo. For the various sizes of problems from small to large, the average computing time of the SA_BRPSD从66.14到70.22年代不等。


实例	术语		SA_BRPSD			差距_最好的(%)	差距_Avg(%)
实例	最优值	CPU	最好的价值	平均值	CPU	差距_最好的(%)	差距_Avg(%)

华盛顿(20)1	639.15	3600年	639.16	639.17	10.15	0.00	0.00
华盛顿(20)2	576.79	159年	576.79	576.79	24.58	0.00	0.00
芝加哥(20)1	166.24	3600年	153.40	153.40	20.85	−7.72	−7.72
芝加哥(20)2	115.19	3600年	113.46	113.46	14.04	−1.50	−1.50
华盛顿(30)1	450.19	3600年	387.78	388.03	30.77	−13.86	−13.81
华盛顿(30)2	520.39	3600年	403.12	405.09	25.22	−22.53	−22.16
芝加哥(30)1	518.02	3600年	265.71	266.96	54.21	−48.71	−48.47
芝加哥(30)2	204.14	3600年	202.21	204.14	29.48	−0.94	0.00
华盛顿(40)1	797.87	3600年	634.07	638.52	44.71	−20.53	−19.97
华盛顿(40)2	1036.51	3600年	826.68	831.62	29.94	−20.24	−19.77
芝加哥(40)1	1287.45	3600年	424.34	424.34	52.13	−67.04	−67.04
芝加哥(40)2	478.01	3600年	213.10	215.92	48.37	−55.42	−54.83
华盛顿(50)1			546.18	554.30	105.62
华盛顿(50)2			603.40	611.72	77.76
芝加哥(50)			326.32	328.59	70.84
华盛顿(66)			682.51	685.62	101.87
芝加哥(66)			6243.75	6494.41	122.49
华盛顿(80年)1			719.65	732.09	121.20
华盛顿(80年)2			678.58	684.66	159.47
华盛顿(90)			925.21	938.56	196.93
Avg		3335年			66.14	−24.15	−23.85


实例	术语		SA_BRPSD			差距_最好的(%)	差距_Avg(%)
实例	最优值	CPU	最好的价值	平均值	CPU	差距_最好的(%)	差距_Avg(%)

华盛顿(20)1	668.94	3600年	662.46	662.50	12.63	−0.97	−0.96
华盛顿(20)2	576.79	663年	576.79	576.79	24.63	0.00	0.00
芝加哥(20)1	164.14	3600年	164.14	164.14	19.19	0.00	0.00
芝加哥(20)2	136.83	3600年	135.19	135.22	16.13	−1.20	−1.17
华盛顿(30)1	447.37	3600年	393.75	393.75	34.19	−11.99	−11.99
华盛顿(30)2	501.14	3600年	414.52	417.24	28.02	−17.28	−16.74
芝加哥(30)1	300.48	3600年	299.42	300.05	34.42	−0.35	−0.14
芝加哥(30)2	299.76	3600年	242.00	242.69	33.23	−19.27	−19.04
华盛顿(40)1	736.88	3600年	688.63	692.12	60.31	−6.55	−6.07
华盛顿(40)2	911.88	3600年	855.64	863.20	38.21	−6.17	−5.34
芝加哥(40)1	576.94	3600年	449.41	449.41	47.47	−22.10	−22.10
芝加哥(40)2	538.80	3600年	243.16	245.98	50.99	−54.87	−54.35
华盛顿(50)1			581.86	588.84	85.98
华盛顿(50)2			647.38	650.63	75.82
芝加哥(50)			353.99	354.51	69.17
华盛顿(66)			676.54	683.93	90.98
芝加哥(66)			6192.78	6468.38	120.21
华盛顿(80年)1			733.58	744.35	114.69
华盛顿(80年)2			736.77	745.27	183.02
华盛顿(90)			984.90	996.38	228.76
Avg		3355年			68.40	−11.73	−11.49


实例	术语		SA_BRPSD			差距_最好的(%)	差距_Avg(%)
实例	最优值	CPU	最好的价值	平均值	CPU	差距_最好的(%)	差距_Avg(%)

华盛顿(20)1	645.10	3600年	627.85	627.90	13.76	−2.67	−2.67
华盛顿(20)2	556.26	40	556.26	556.26	33.82	0.00	0.00
芝加哥(20)1	134.73	3600年	134.73	134.73	20.53	0.00	0.00
芝加哥(20)2	100.80	3600年	99.60	99.76	17.95	−1.19	−1.04
华盛顿(30)1	414.18	3600年	369.72	369.72	32.90	−10.73	−10.73
华盛顿(30)2	432.25	3600年	392.72	393.61	27.89	−9.15	−8.94
芝加哥(30)1	489.71	3600年	249.47	249.80	35.62	−49.06	−48.99
芝加哥(30)2	321.25	3600年	189.40	191.21	31.73	−41.04	−40.48
华盛顿(40)1	721.11	3600年	617.41	622.76	50.49	−14.38	−13.64
华盛顿(40)2	1021.87	3600年	814.77	819.79	42.10	−20.27	−19.78
芝加哥(40)1	412.36	3600年	408.94	408.94	57.98	−0.83	−0.83
芝加哥(40)2	397.27	3600年	201.52	203.18	50.88	−49.27	−48.86
华盛顿(50)1			526.11	534.88	109.26
华盛顿(50)2			592.72	595.78	79.45
芝加哥(50)			321.13	324.60	69.87
华盛顿(66)			656.99	663.09	105.25
芝加哥(66)			6243.75	6494.41	122.49
华盛顿(80年)1			702.93	716.69	126.66
华盛顿(80年)2			661.88	673.31	171.68
华盛顿(90)			914.40	924.30	204.03
Avg		3303.33			70.22	−16.55	−16.33


实例	术语		SA_BRPSD			差距_最好的(%)	差距_Avg(%)
实例	最优值	CPU	最好的价值	平均值	CPU	差距_最好的(%)	差距_Avg(%)

华盛顿(20)1	665.08	3600年	654.91	655.01	10.76	−1.53	−1.52
华盛顿(20)2	566.26	30.	566.26	566.26	25.00	0.00	0.00
芝加哥(20)1	155.17	3600年	155.17	155.17	19.20	0.00	0.00
芝加哥(20)2	127.97	3600年	127.97	127.97	17.38	0.00	0.00
华盛顿(30)1	449.66	3600年	382.56	382.56	33.10	−14.92	−14.92
华盛顿(30)2	442.69	3600年	410.45	411.18	28.40	−7.28	−7.12
芝加哥(30)1	292.28	3600年	289.57	290.67	33.25	−0.93	−0.55
芝加哥(30)2	236.60	3600年	234.10	234.10	32.92	−1.06	−1.06
华盛顿(40)1	818.25	3600年	681.61	685.40	61.54	−16.70	−16.24
华盛顿(40)2	859.04	3600年	853.74	857.84	47.10	−0.62	−0.14
芝加哥(40)1	500.44	3600年	442.74	442.74	47.85	−11.53	−11.53
芝加哥(40)2	349.26	3600年	239.51	240.61	53.41	−31.42	−31.11
华盛顿(50)1			571.78	579.44	106.77
华盛顿(50)2			638.40	640.92	75.32
芝加哥(50)			352.67	354.72	72.96
华盛顿(66)			664.31	671.87	89.90
芝加哥(66)			6175.14	6472.54	117.22
华盛顿(80年)1			728.64	739.63	114.94
华盛顿(80年)2			722.88	743.14	183.62
华盛顿(90)			984.90	996.38	228.76
Avg		3303年			69.97	−7.17	−7.02

如表所示1- - - - - -4,所有的价值观差距_最好的和差距_Avg是负的。这意味着SA_BRPSD执行比行话。的绝对值平均差距_最好的和差距_Avg通过SA值_BRPSD为测试问= 20比那些更大问= 10。随着重新定位卡车的容量增加,目标函数值下降。这可能是由于这一事实,如果卡车容量增加,卡车可以加载/卸载更多的自行车在一个火车站,导致解决方案空间的扩张。综上所述,我们可以得出结论,提出SA_BRPSD可以获得更好的可行的最优解比行话快得多。

5.2。考虑到需求作为随机参数的必要性

评估的性能我们提出的随机模型,我们使用两个概念的评价方法:完全信息的期望值(EVPI)和随机解的值(VSS) [32- - - - - -34]。EVPI措施的最大数量的决策者将准备支付,以换取完美的未来,信息和VSS措施成本节约的数量时,决策者使用随机参数的期望值代替随机参数模型(成本的数量由于忽略了不确定性)。EVPI定义是观望的解决方案之间的差异(WS)和“当下”解决方案(HN)。在EVPI WS的期望值是远见的解决方案。我们获得的价值平均每个随机场景的结果。HN的解决方案是这个两阶段随机模型的客观价值。VSS的定义是区别使用期望值的问题解决方案的预期结果(EEV)和“当下”的解决方案。在VSS EEV的价值是通过输入优化问题的最优解与平均值的随机需求相关的两阶段随机模型。差距的差距_VSS和差距_EVPIVSS和计算了EVPI VSS / HN和EVPI / WS,分别。

测试实例芝加哥20 (1)用于解释WS的总成本,HN, EEV, EVPI, VSS 20站组成的小型实例。我们设置了卡车的容量问= 10,C_h= 1,C_d= 1,C_t= 1。

在这个测试实例,总成本可以通过SA解决_BRPSD如下:WS = 145.31, HN = 153.40, EEV = 161.31。然后,计算VSS = EEV−环= 7.90,EVPI = HN−WS = 8.09,差距_VSS= 5.15%,缺口_EVPI= 5.57%。EVPI值和VSS导致的结论是,管理者必须多支付5.57%的总成本随机获得一个完美的解决方案再分配对未来需求的信息。忽略了不确定性情况他们会让经理风险支付至少高出5.15%,如果他们只专注于一个场景(确定的解决方案)。

敏感性分析的结果差距_VSS和差距_EVPI卡车的容量问,持有成本C_h、惩罚成本C_d,旅行成本C_t在下面解释。四个参数的值增加了−50%,−25%,+ 25%和+ 50%。表5- - - - - -8总结WS的总成本,HN, EEV, EVPI和VSS差距_EVPI,差距_VSS所有的测试。图1显示了四个参数的敏感性分析结果。在当前设置,上述四个参数产生重大影响的解决方案。从表5- - - - - -8,与理论结果一致,可以成立,WS < HN < EEV在所有测试。我们可以看到,平均差距_VSS都大于平均差距_EVPI。的差距_EVPI随机模型的所有测试是负的,说明的问题BRPSD天生是随机的。此外,差距_VSS在所有测试BRPSD是负的,说明的问题研究适用于随机模型。


问	WS	接下来的	EEV	VSS	差距_VSS(%)	EVPI	差距_EVPI(%)

10	153.86	164.14	168.57	4.43	2.70	10.28	6.68
15	147.66	156.87	163.24	6.37	4.06	9.22	6.24
20.	145.31	153.40	161.31	7.90	5.15	8.09	5.57
25	144.69	151.60	160.97	9.37	6.18	6.91	4.78
30.	144.35	150.87	160.41	9.54	6.32	6.53	4.52
Avg				7.52	4.88	8.21	5.56


C_h	WS	接下来的	EEV	VSS	差距_VSS(%)	EVPI	差距_EVPI(%)

0.5	137.68	144.73	150.29	5.56	3.84	7.05	5.12
0.75	141.89	149.73	155.80	6.07	4.05	7.84	5.53
1	145.31	153.40	161.31	7.90	5.15	8.09	5.57
1.25	147.43	157.02	166.82	9.79	6.24	9.60	6.51
1。5	148.80	160.64	172.32	11.69	7.28	11.84	7.96
Avg				8.20	5.31	8.91	6.16


C_d	WS	接下来的	EEV	VSS	差距_VSS(%)	EVPI	差距_EVPI(%)

0.5	120.92	125.00	128.24	3.24	2.59	4.08	3.38
0.75	133.14	139.57	144.77	5.21	3.73	6.43	4.83
1	145.31	153.40	161.31	7.90	5.15	8.09	5.57
1.25	157.43	167.19	177.84	10.65	6.37	9.76	6.20
1。5	169.50	180.97	194.37	13.40	7.41	11.47	6.77
Avg				8.08	5.05	7.97	5.35


C_t	WS	接下来的	EEV	VSS	差距_VSS(%)	EVPI	差距_EVPI(%)

0.5	96.81	104.30	113.72	9.42	9.04	7.49	7.74
0.75	121.09	128.84	137.51	8.68	6.74	7.75	6.40
1	145.31	153.40	161.31	7.90	5.15	8.09	5.57
1.25	169.49	177.97	185.10	7.13	4.01	8.49	5.01
1。5	193.61	202.07	208.90	6.83	3.38	8.47	4.37
Avg				7.99	5.66	8.06	5.82

(一)

(b)

(c)

(d)

从图1的增加,我们可以看到C_h,C_d,C_t这些地区的增加环。我们也看到的增加问这些地区的减少环。最伟大的参数对HN是单位运输成本的影响C_t。这可能是因为运输成本总目标成本的贡献大于惩罚成本和储存成本。

从图1我们可以看到,问增加,差距_EVPI会减少,但差距_VSS增加。也注意到这一差距_EVPI和差距_VSS倾向于增加时C_h和C_d增加。然而,差距的价值_EVPI和差距_VSS矛盾的增加C_t。上述四个参数的变化的影响上的差距_VSS明显比空白_EVPI。

结果说明,差距_EVPI增加的时候C_h和C_d增加和问和C_t减少,这意味着决策者愿意花更多的钱来获得准确的再分配对未来需求的信息。差距_VSS增加增加的值C_h,C_d,问或减少的值C_t,因此,决策者可以获得更多的成本节约的两阶段随机模型。

6。结论

在这篇文章中,一个通用的基于场景的两阶段规划模型提出了自行车重新定位问题随机分配的要求。在提出的模型中,第一阶段决策对应于路由决策和对应于装卸决策阶段的决策。模型的目标是找到最好的路线和装卸的理想数量在每个车站和仓库,以最小化加权和预期的运输成本、惩罚成本和持有成本。然后,提出了一种模拟退火算法来解决模型。数量的例子执行评估拟议的模型和算法,紧随其后的是一个详细的灵敏度分析,研究几个重要参数的变化如何影响的性能提出了模型和算法的解决方案。该模型和算法具有重要的理论和实践意义的BSS运营商,可以降低操作成本的BSS和提高用户满意度。相反,除了自行车共享,共享经济其他共享设施,如汽车共享,也需要搬迁,所以这类问题有很强的应用背景。

在未来,我们将鲁棒优化模型来解决自行车重新定位问题具有随机需求的自行车共享系统(35]。我们也考虑环境问题通过增加碳排放的两阶段随机规划模型的目标函数(36- - - - - -38]。

符号

集

N:	站的设置
N₀:	节点的集合,包括车站(索引我, )由0和得宝(索引)
:	组场景,被

参数

:	单位成本旅游时间
:	站的旅行时间我到车站j
:	在车站的惩罚成本的自行车
:	每个自行车在仓库储存成本
问:	卡车容量
米:	一个非常大的数量
:	在车站搬迁需求我在场景
:	发生概率的场景

决策变量

:	二进制变量等于1,如果直接从车站卡车旅行我到车站j和0,否则
:	自行车的数量直接从站在卡车旅行时我到车站j在场景
:	自行车的数量过剩我搬迁后操作场景
:	自行车的松量我搬迁后操作场景
:	辅助变量与车站联系在一起我用于subtour消除约束。

数据可用性

所有的数据都包含在本研究可从相应的作者。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者承认中国的国家自然科学基金(批准号71271220)和社会科学成就的项目审查委员会湖南省(批准号XSP20YBZ165)。

引用

y, y, l, n .周和z,“网络结构分析城市自行车分享系统:一个案例研究基于实时数据的公共自行车系统,”可持续性,11卷,不。19日,ID 5425条,2019年。视图:出版商的网站|谷歌学术搜索
g . Berbeglia肯尼迪。Cordeau,即Gribkovskaia, g . Laporte“静态皮卡和交付问题:分类方案和调查,“前,15卷,不。1日至31日,2007页。视图:出版商的网站|谷歌学术搜索
m . Benchimol p . Benchimol b Chappert et al .,“自我平衡的站服务”自行车租赁系统,”RAIRO-Operations研究,45卷,不。1,37 - 61年,2011页。视图:出版商的网站|谷歌学术搜索
t·雷维夫、m . Tzur和中情局形式,“静态定位在一个公共自行车系统:模型和解决方案的方法,”欧元在运输和物流》杂志上,卷2,不。3、187 - 229年,2013页。视图:出版商的网站|谷歌学术搜索
s . c . Ho和w . y . Szeto解决静态定位问题在自行车分享系统使用禁忌搜索算法迭代,”运输研究E部分:物流和运输审查卷,69年,第198 - 180页,2014年。视图:出版商的网站|谷歌学术搜索
中情局福马、t·雷维夫和m . Tzur“3步数学启发式自行车分享系统的静态定位问题,“交通研究B部分:方法论卷,71年,第247 - 230页,2015年。视图:出版商的网站|谷歌学术搜索
s . c . Ho和w . y . Szeto混合大邻域搜索的静态多车bike-repositioning问题,“交通研究B部分:方法论卷,95年,第363 - 340页,2017年。视图:出版商的网站|谷歌学术搜索
答:朋友和y张”,自由浮动的自行车共享:解决现实生活中的大型静态平衡问题,“交通研究部分C:新兴技术卷,80年,第116 - 92页,2017年。视图:出版商的网站|谷歌学术搜索
f·克鲁斯,萨勃拉曼尼亚,b·p·勃拉克和m .八神庵”的启发式算法单一车辆静态自行车共享平衡问题,“电脑与行动研究卷。79年,19-33,2017页。视图:出版商的网站|谷歌学术搜索
t . Bulhoes a萨勃拉曼尼亚、g . Erdoğan和g . Laporte“静态自行车搬迁问题与多个车辆和访问,”欧洲运筹学杂志》上,卷264,不。2、508 - 523年,2018页。视图:出版商的网站|谷歌学术搜索
m·戴尔中保,m .八神庵,s . Novellani”自行车分享再平衡的破坏和修复算法问题,“计算机与操作研究。卷,71年,第162 - 149页,2016年。视图:谷歌学术搜索
psi。你,”一个两阶段启发式方法自行车重新定位的问题,“应用数学建模卷,73年,第667 - 651页,2019年。视图:出版商的网站|谷歌学术搜索
d . Chemla f·莫尼耶,r . Wolfler Calvo”自行车分享系统:解决静态平衡问题,“离散优化,10卷,不。2、120 - 146年,2013页。视图:出版商的网站|谷歌学术搜索
w . y . y . Li Szeto, j .长,和水,“多个类型的自行车重新定位的问题,”交通研究B部分:方法论卷,90年,第278 - 263页,2016年。视图:出版商的网站|谷歌学术搜索
w . y . Szeto、刘y和s . c . Ho "化学反应优化求解静态自行车重新定位的问题,“交通研究D部分:交通和环境47卷,第135 - 104页,2016年。视图:出版商的网站|谷歌学术搜索
w . y . y . Liu Szeto, s . c . Ho”一个静态自由浮动的自行车重新定位问题与多个异构的车辆,多个仓库,和多个访问,”交通研究部分C:新兴技术卷,92年,第242 - 208页,2018年。视图:出版商的网站|谷歌学术搜索
w . y . Szeto和c . s .风水”,准确的装载和卸载策略静态多车自行车重新定位的问题,“交通研究B部分:方法论卷,109年,第211 - 176页,2018年。视图:出版商的网站|谷歌学术搜索
l . d . Gaspero a Rendl, t . Urli“平衡自行车共享系统和约束编程,”约束,21卷,不。2、318 - 348年,2016页。视图:出版商的网站|谷歌学术搜索
l . Di Gaspero a Rendl, t . Urli“平衡自行车分享系统基于约束的方法,”约束编程的原理和实践卷,8124年,页758 - 773,施普林格,柏林,德国,2013年。视图:谷歌学术搜索
m . Rainer-Harbach p . Papazek g . r . Raidl b, c . Kloimullner,“飞行员、掌握和接受自行车分享系统的静平衡的方法,”杂志的全局优化,卷63,不。3、597 - 629年,2015页。视图:出版商的网站|谷歌学术搜索
问:唐,傅z和m .秋”的二层规划模型和算法静态自行车重新定位的问题,“《先进的交通工具卷,2019篇文章ID 8641492, 19页,2019。视图:出版商的网站|谷歌学术搜索
j·沃灵顿和d . Ruchti”两阶段随机近似动态共享流动系统的平衡,”交通研究部分C:新兴技术卷,104年,第134 - 110页,2019年。视图:出版商的网站|谷歌学术搜索
c·弗里克和n .恐吓”激励和再分配的均匀自行车分享系统车站的有限能力,”欧元在运输和物流》杂志上,5卷,不。3、261 - 291年,2016页。视图:出版商的网站|谷歌学术搜索
m·戴尔中保,m .八神庵,s . Novellani和a .萨勃拉曼尼亚”自行车共享随机需求再平衡问题,”交通研究B部分:方法论卷,118年,第380 - 362页,2018年。视图:谷歌学术搜索
f . Maggioni m . Cagnolari l . Bertazzi s w·华莱士,“随机优化模型既转运的问题,“欧洲运筹学杂志》上,卷276,不。1,第283 - 272页,2019。视图:出版商的网站|谷歌学术搜索
燕,J.-R。林,研究。陈,F.-R。谢,“租赁自行车的位置和分配在随机需求下,“计算机与工业工程卷,107年,页1 - 11,2017。视图:出版商的网站|谷歌学术搜索
c·e·米勒,a·w·塔克,r . a . Zemlin的话来说,“旅行推销员问题的整数规划模型。”杂志的ACM (JACM),7卷,不。4、326 - 329年,1960页。视图:出版商的网站|谷歌学术搜索
y,问:赵,Kaku, y,”发展的燃料消耗生产配送车辆路径问题的优化模型,”电脑与行动研究,39卷,不。7,1419 - 1431年,2012页。视图:出版商的网站|谷歌学术搜索
李c, h .郭,y, c,和y王”的非线性整数规划模型集成的位置、库存、和路由决策闭环供应链,”复杂性ID 2726070条,卷。2018年,17页,2018。视图:出版商的网站|谷歌学术搜索
张y、m . Qi W.-H。林,l .苗族“metaheuristic方法可靠的位置在中断路由问题,“运输研究E部分:物流和运输审查卷,83年,第110 - 90页,2015年。视图:出版商的网站|谷歌学术搜索
y Shi, t . Boudouh o .浅滩,d . Wang”建模和解决问题同时交付和提取具有随机旅行和在家庭健康护理服务时间,“专家系统与应用程序卷,102年,第233 - 218页,2018年。视图:出版商的网站|谷歌学术搜索
j . r . Birge f . Louveaux,介绍了随机规划施普林格科学与商业媒体,柏林,德国,2011年。
S.-L。胡,张炳扬。汉族,L.-P。孟,”联合决策的随机优化库存和采购在人道主义救援,”计算机与工业工程卷。111年,39-49,2017页。视图:出版商的网站|谷歌学术搜索
e·萨德·m·Bashiri f·奥利维拉,“两阶段随机规划方法下的医疗药品库存路径问题的不确定性,”计算机与工业工程卷,128年,第370 - 358页,2019年。视图:出版商的网站|谷歌学术搜索
h . y . Liu Lei,吴z d,“灾后救援分布的鲁棒模型预测控制方法,”计算机与工业工程卷,135年,第1270 - 1253页,2019年。视图:出版商的网站|谷歌学术搜索
j .江d·张,李,和y . Liu,“多峰绿色物流网络设计的城市群具有随机需求,”《先进的交通工具卷,2019篇文章ID 4165942, 2019。视图:出版商的网站|谷歌学术搜索
李,王x, z . Wang d . Zhang和y . Liu”集成优化模型的生物质原料碳排放约束和加载一分为二,交付问题”计算机与工业工程文章ID 106013卷,137年,2019年。视图:出版商的网站|谷歌学术搜索
y王,w . y . Szeto静态绿色重新定位与破碎的自行车,自行车共享系统”交通研究D部分:交通和环境卷,65年,第457 - 438页,2018年。视图:出版商的网站|谷歌学术搜索

科学的规划