文摘

自行车可以帮助城市实现碳中和目标共享。清洁和消毒程序共享自行车的维护是至关重要的,特别是在COVID-19流行因为共享自行车可能是病毒的传播媒介。本研究提出了一种优化模型的清洁和消毒方案dockless自行车共享。认为晚上进行消毒,使用时最低。关于消毒人员,当销售员Multidepot模型是制定为一个扩展的多旅行商问题(MDMTSP)。目标函数是最小化总成本;由成本与消毒工作人员的工作时间和人均成本。启发式算法相结合 - - - - - -意味着集群和采用遗传算法(K-GA)找到下界的解决方案。然后,K-GA-adjustment算法采用寻找满足约束的解决方案。减少所需的计算时间,下界的一个近似函数最优数量的消毒工作人员是通过构造一个连续近似(CA)模型。案例研究基于真实位置数据共享的自行车在成都,中国,说明如何执行维护部门可以采取优化框架来设计一个有效的计划来清理和消毒,共享自行车。

1。介绍

近年来,随着机动车所有权的增加,交通运输已成为碳排放的主要来源。实现碳中和的目标,它是特别重要的减少二氧化碳排放的交通领域。城市低碳交通方式有很多,比如ride-sourcing [1,2),e-scooter分享,和自行车共享。作为一个典型的低碳旅游模式,自行车共享已经被世界各地的城市。然而,有各种挑战的操作和维护自行车共享。没有适当的维护,大量的自行车可以取消共享,成为“僵尸车”(3]。清洁和消毒是必要的程序共享自行车的日常维护(4]。研究表明,自行车消毒可以提高公民的意愿使用共享自行车(5]。这可以减少使用其他运输模式,尤其是高二氧化碳排放私家车和出租车等,从而减少排放的6]。

COVID-19流行病的爆发,它变得更加迫切需要清理和消毒,定期自行车共享。一方面,自行车共享已经成为一种公共交通工具,因为旅客尽量避免接触别人由于害怕疾病传播7]。另一方面,自行车可能是病毒的传播方法(8),特别是通过车把和座位9]。因此,及时清洗和消毒的自行车很重要,防止疾病的传播,增加共享自行车的吸引力。

许多国家已经开发出标准共享自行车的清洁和消毒。例如,中国第一批标准自行车共享消毒,“网络租赁自行车卫生操作规范,保证”2020年3月被释放。公共卫生的标准要求,当紧急情况发生,车把,篮子,锁,和其他地方方便骑自行车必须清洗和消毒每天不少于一次10]。

然而,我们最好的知识,没有研究进行清洁和消毒的共享战略自行车。在实践中,经营者通常没有一个设计良好的消毒自行车的计划。如果没有这样的计划,一些自行车可能排除消毒而其他自行车可能会多次消毒。本研究的目的是开发一个模型来优化方案消毒自行车共享。自dockless自行车共享比停靠更广泛使用的自行车共享和自行车停车地点不受限制,dockless共享自行车更重要的消毒和复杂的停靠。因此,我们关注的消毒dockless共享自行车在这个研究。

根据标准的清洁和消毒,员工需要清洁所有共享自行车通过喷洒消毒剂等措施(11]。假设每个消毒人员通过他或她负责所有的自行车。因此,这个问题类似于Multidepot多旅行商问题(MDMTSP)。基于MDMTSP的设置,本研究假设消毒工作人员的数量等于仓库的数量。优化目标是最小化总成本,由成本与员工的工作时间和每个员工的人均成本(12]。

因为它非常耗费时间获得此问题的解决方案,我们将问题划分为两个子问题。第一个是确定下界的消毒工作人员需要通过构造一个CA模型。第二个是获取特定的路线为每个消毒人员通过使用一种混合算法。

本研究的贡献如下:(我)本研究提出了一种routing-based模型来描述自行车共享的消毒过程(2)我们延长MDMTSP通过设置仓库的数量等于旅行推销员的数量,考虑成本不仅与旅行推销员的工作时间也是固定成本每个销售员的招聘(3)消毒的自行车共享问题是由连续近似(CA)模型,和封闭下限解消毒人员的数量。通过这样做,获得所需的时间最后消毒方案可以大大减少(iv)我们采用K-GA-adjustment算法找到具体消毒自行车共享计划和调整的解决方案可以满足重载约束

本研究的结构如下。下一节介绍论文相关操作和路由优化共享的自行车。第三部分介绍了具体的清洁和消毒过程共享自行车和模型框架。在第四部分中,算法和实验工作。成都,一个案例研究和结果分析了在第五部分。最后一部分总结了未来工作的结论和建议。

2。文献综述

由于共享自行车的消毒是一个维护操作的一部分,我们总结了论文相关维护操作的自行车共享。因为接近MDMTSP消毒操作问题,他们也回顾了相关的研究。

2.1。研究相关的共享自行车的维护操作

共享自行车的维护操作研究一直得到广泛的研究,主要分为两个方面:调整和维修。

平衡指的是重新分配的过程中共享的自行车,以满足旅游需求的骑自行车的人。再平衡问题主要分为静态自行车平衡问题(SBRP)和动态(DBRP)自行车平衡问题。SBRP,共享自行车通常骑自行车时重新分配的需求很低(例如,在夜间),而在DBRP,分享自行车重新分配。另一个区别是,DBRP认为需求在一天的时间变化和采用不同的平衡策略基于使用预测(13,14]。平衡问题是变异的经典车辆路径问题(VRP)和np难问题(15]。由于没有准确的算法对大规模平衡问题(16),研究人员通常采用启发式算法(17- - - - - -19]。几项研究采用基于集群算法来解决城市规模调整的问题。Lv et al。15)设计了一个聚类策略将原问题分解为TSP和multidepot VRP和自适应可变邻域搜索算法用于路由优化。Lv et al。20.)提出了一种模糊聚类策略考虑距离和库存的因素。尽管研究人员很难获得最优解的问题使用基于集群算法,研究人员可以有效地找到一个算法的解决方案。本研究还采用这种基于集群的方法来寻找一个解决方案的城市规模共享自行车消毒问题。

关于自行车修理,有些学者构建模型来解决这一问题的如何收集和提供损坏的自行车仓库最低的成本。收集和提供损坏的自行车通常结合再平衡过程,被认为是在一个优化模型(21- - - - - -25]。

2.2。研究相关MDMTSP

本研究制定了清洁和消毒模型基于MDMTSP的结构,这是一个茶匙的变体。TSP和它的变体被广泛研究领域的研究人员操作研究和运输。多旅行商问题(MTSP)是一个扩展的TSP和相当于VRP问题没有能力约束(26]。由Bektas (MTSP的最近的研究进行了综述26]和Cheikhrouhou Khoufi [27]。MDMTSP是项目的一个分支。它第一次被提出的卡拉和Bektas28),已被应用于许多领域。例如,高et al。29日)制定无人机MDMTSP调度问题,设计了分组蚁群优化算法来解决这个问题。陈等人。30.)制定multirobot系统MDMTSP和使用一个蚁群文中针对迷因算法来解决这个问题。这些研究主要采用启发式算法来解决这些问题,而这些问题通常是小规模的。在处理大规模问题,通常是在现实世界中,即使这些启发式算法不能在合理的时间内找到一个令人满意的解决方案。因此,CA方法一直采用研究人员来处理这些问题,并得到实证的解决方案可以很容易地用于处理相关问题。

路由优化问题通常是np难;很难开发一个算法来获得大规模问题的最优解。因此,许多研究使用CA模型来获得一个算法解决路由问题。Daganzo [31日)提供了一个全面的视图的CA TSP和VRP的函数。接着说下去! (32)使用机器学习的方法来推导balanced-dynamic MTSP CA模型。一些学者采用CA解决大规模路由问题,如救灾(33),校车路由(34),和无人机路由(35]。有兴趣的读者可以参考朗之万et al。36和安萨里等。37)的研究综述,CA模型领域的路由优化。

总之,操作共享的自行车上的先前的研究主要集中在调整和维修。水和Szeto38)进行这些研究的全面审查。然而,我们最好的知识,共享自行车的最佳的清洁和消毒方案没有被调查。因此,本研究试图探讨这个话题。因为这个问题可以被看作是一个扩展的MDMTSP np难问题,结合CA方法和启发式算法被用来解决这个问题。

3所示。问题描述和模型

本节描述自行车清洁和消毒过程和模型的假设。

3.1。清洁和消毒过程

在夜间执行清洁和消毒。消毒人员需要去指定的地点的自行车平台和消毒这辆自行车和其他自行车停在一个小区域的位置。钟上的锁可以帮助消毒人员区分负责自行车。

假设消毒人员开始从一个自行车,自行车的位置访问需要消毒,并返回到第一个自行车。每个自行车至少需要消毒一次。因此,在这项研究中要解决的问题可能被视为MDMTSP。旅行推销员(消毒人员)的数目等于仓库的数量。是仓库的起点。一个例子是显示在图1。的清洁和消毒任务被分配到整个区域消毒工作人员。

3.2。模型的假设

模型的假设如下:(我)每个员工从一个自行车并返回到自行车形成闭环。回到起点可以证明,员工通常从接近他/她的自行车回家(或其他地方),并完成消毒任务后,他/她需要回家,这可能被视为回到第一个自行车(2)自行车的位置在消毒过程中不会改变。这是接近实际情况,因为在夜里进行清洁和消毒(3)共享自行车之间的距离以欧氏距离来衡量,这是一个合理的简化的道路网络,尤其是在城市地区,十字路口的密度高(39- - - - - -42]。

3.3。符号

3.4。模型框架

我们制定这个模型MDMTSP的基础上。所不同的是,就业成本的目标函数是由人均的消毒工作人员12)和成本相关的消毒工作人员的工作时间,如函数(1)所示。对于工作时间成本,选择平均价值的原因是自行车的消毒需要尽可能快,和平均工作时间是平均效率的消毒工作。

应该注意的是,通常消毒剂消毒所有的自行车在一个领域无论平台共享,共享属于自行车。自行车的数量,可以消毒与消毒剂的工作时间呈正相关,在路上花费的时间到下一个自行车的位置也应算作工作时间,我们认为这是合理的就业成本计算消毒剂基于基本工资和工作时间。

因为每个自行车需要消毒,消毒用品的消费相关的成本和总清洁和消毒时间是固定的。因此,这个成本不需要考虑目标函数。决策变量包括和 。模型中每个变量的解释如表所示1。

受

约束(2)表明,每个消毒工作人员负责至少2自行车共享,确保路径可以形成一个循环。约束条件(3)和(4)表明,每个自行车需要访问一次,还有两条边连接到每一个点。约束(5)表明,之间没有交叉共享自行车的集消毒由不同的员工和所有的自行车共享需要清洗。基于Dantzig et al。43),约束(6)是用来消除subtour。在函数(7),如果员工= 1k从点对点 ,和0。约束(8)确保消毒员工不加班:第一项是每个员工的旅行时间,第二项是自行车每个员工的清洁和消毒时间。

4所示。近似函数和启发式算法

由于共享自行车的数量需要在一个城市进行了清理和消毒是非常大的,它是具有挑战性的设计一个算法解决大规模的np难问题,在合理的时间内获得全局最优解。即使是经典启发式算法需要计算时间生成一个令人满意的解决方案。因此,我们提出一个CA方法找到一个下界的解决方案的数量消毒人员加班工作约束放松。相反,如果我们用一维搜索算法(44]寻找解决消毒人员的数量,总计算时间等于搜索的数量乘以CA方法的计算时间。CA方法可以得到一个近似函数,它可以直接计算下界解决消毒人员的数量。基于CA的结果,我们设计一个启发式算法查找算法的解决方案。所需的解决方案包括消毒人员的数量和他们的旅行路线自行车消毒。

我们首先介绍了CA方法。之前的研究使用CA方法获取函数表达的平均最短路径长度TSP(45,46),与 (31日]。CA模型的设计如下:客户是随机分布在一个地区 。每个客户都有一个随机需求数量的期望值 。每辆车可以单位的需求。是仓库之间的距离和区域的中心 。 和是常数。以来的平均最短路径长度MDMTSP尚未研究,基于之前的研究,我们认为,平均长度也可以通过使用CA方法近似函数。通过设置 ,(1)可以转化为函数 。如果有一个函数来表达的平均最短路径长度MDMSTP,术语 取而代之的是这个函数。找到的下限解 ,我们放松约束(8)到约束(9),以确保员工的平均工作时间不超过最大值。

然后,问题可以转化为一个简单的用一个决策变量优化问题 。

为了获得函数,它通常是一个回归模型,根据CA方法,我们需要开发一系列问题与不同的设置和使用一个算法来解决这些问题。的数据问题的解决方案和设置将用于训练回归模型。

我们首先假设是一个固定的参数和 被转换为 ,这可以被视为一个MDMTSP。许多研究人员采用启发式算法来解决MDMTSP [29日,30.]。本研究采用遗传算法(GA)也是一个优秀的启发式算法来解决MDMTSP首先分配所有点(自行车)消毒工作人员随机和执行交叉和变异找到解决方案47,48]。另一方面,K-GA的组合 - - - - - -意味着算法和遗传算法,旨在减少通过聚类计算,在短时间内获得更好的可行的解决方案。自行车的聚类的一个例子是图所示2。

我们已经进行了实验,随机生成一千点广场面积400公里²。GA和K-GA都用来解决这个问题。2019年MATLAB软件用于编码。计算机系统的操作参数是英特尔(R) (TM)核心i7 - 4720总部(电子邮件保护)GHz和16 G内存操作。遗传算法的初始参数如下:人口规模是80和100倍的迭代次数的自行车共享的数量需要消毒。

通过遗传算法的解决方案和K-GA如图3。可以看到,当消毒人员数量的增加,获得的最短路径的遗传算法变得长而获得的最短路径K-GA波动约520公里。这表明解决方案获得通过K-GA优于遗传算法。图4比较了两种算法的计算时间。GA,消毒人员数量的增加,计算时间逐渐增加。但是K-GA,减少计算时间。这是因为当解决问题,耗时的部分是寻找最短路径。随着员工数量的增加,有更多的集群和可能在每个集群少点,这样可以减少所需的时间搜索最短路径。总之,K-GA可能产生比GA在短时间内更好的解决方案。因此,K-GA用于生成最短路径在下面工作。

以前的研究方法后(45,46,49),我们执行以下步骤构建CA模型,得到近似函数:设计不同的实验情况,生成随机问题在每个实验情况下,解决问题获得解决方案,和培训的近似函数基于实验的设置和解决方案。

在这项研究中,实验场景的设计是通过结合不同的服务领域,数量的自行车,和员工的数量。服务区域被认为是广场,边长设置为5,10,15和20。自行车需要清洗的数量设置为200,400,600,800,1000。

消毒工作人员的数量设置为从1到30的间隔1。结合四个服务领域,五个级别的自行车号码,和30水平的员工人数,有600个实验场景生成。均匀分布假设自行车,自行车的位置是随机生成的每个实验50次的场景。每个实验获得的最短路径使用K-GA。的平均最短路径长度计算每个实验场景。结果如图所示5。

从图可以看出5,几乎没有影响 。因此,近似函数的平均最短路径长度不需要包括 。本研究采用广泛使用的函数形式为预期的TSP的最短路径的长度,这是 ,提出Beardwood et al。46]。当边长和自行车的数量是固定的,不同数量的消毒人员导致最短路径的变化不大。因此,我们选择所有样品以适应模型。结果表明,的价值是0.826,达到0.997,RMSE等于4.931,模型具有重要意义。因此, 可以用0.826近似 。

后 是由CA函数,函数的决策变量(1)仅仅是吗 ,和函数显然是一个单峰凸函数。大规模搜寻最优值是可以避免的。通过求导,near-minimum下界可以近似为点 。自值可能不是整数,计算和比较需要执行,以确定数量应该是圆形向上或向下,这可能为代表 。当约束(9)可以满足,near-minimum下界点可以被视为全球最低下限点。在这种情况下,可以近似转化为约束(9) 。否则,下界的解决方案可以通过等号的约束(9),也就是说, ; 意味着围捕。总之,

用通过CA功能,我们可以获得封闭下界的解决方案:

因此,在实践中,下界的解决方案可以通过函数(10)。K-GA算法可以用来获得自行车的集群,每个工作人员负责清洁和消毒的具体工作时间。员工的工作时间超过了工作时间的限制,我们设计K-GA-adjustment算法分配一些自行车他们负责其他的员工不超载。同时,这个过程可以提高每个员工的工作负载的平衡。具体K-GA-adjustment算法算法所示1。

5。案例研究

在这个案例研究中,我们使用自行车共享访问数据的一个最流行的自行车共享公司在成都证明我们提出的方法的应用。旅行在第一环道路3月1日,2018年,用于开发静态清洁和消毒方案。有3632自行车共享,需要消毒3月1日,2018年。我们收集这些共享的最终位置自行车。根据中国第一共享自行车消毒组标准,他们都需要消毒和清洁。该地区在第一环城公路27.85公里²。如果我们不考虑工作时间限制,第一个函数方程(9)可以用来计算员工的数量,这是13。然而,在这种情况下,工作时间约束违反。因此,第二个函数的方程(9)是用来计算员工的数量。CA结果表明,16消毒需要员工,和总成本(目标函数)是80.39(美元/天)。

我们应用K-GA解决具体消毒计划得到初始解,然后应用K-GA-adjustment算法来调整每个员工避免过度劳累。结果如表所示2。可以看出K-GA-adjustment算法不仅可以避免过度劳累,也降低了总工作时间。具体消毒路线如图6。不同的颜色代表不同的消毒的人员。指定路径的细节可以显示员工的手机。总成本是83.84(美元/天),略高于结果的近似函数的误差为4.11%。其原因可能是自行车的空间分布不均匀分布。这个例子的计算时间= 1.52小时。没有近似函数,常用的方法是应用一维搜索算法(44)找到最佳的消毒工作人员的数量。需要至少三次CA方法的计算时间。这说明,通过使用近似函数,计算时间可以很大程度上减少,使得该方法适用于大规模问题。

调查成本系数的影响(和 )结果,我们通过CA模型进行灵敏度分析。数据7和8显示的值消毒人员和总成本的变化和 ,范围从0.1到100(美元)。可以看出,如果满足约束(9),招聘成本系数的增加消毒人员( )导致减少消毒人员的数量。成本系数的增加相关工作时间( )导致增加消毒人员的数量。当约束(9)不满意,消毒人员的数量将保持在16的价值。显然,成本系数的增加和导致总成本的增加。

6。结论

共享自行车的清洁和消毒是必要的部分的操作和维护工作。根据清洁标准,每个自行车需要每天至少清洗一次。COVID-19大流行期间,它已成为更重要的清理和消毒,共享的自行车,因为他们可以传播疾病的一种方法。因为这个话题并没有得到研究,在这项研究中,我们研究这一主题提出了一个方法来设计最优消毒方案。问题可以被视为MDMTSP的一种变体,本研究提出了一种优化模型来描述的消毒过程共享自行车和一个有效的方法获取消毒方案,它允许操作和维护人员消毒所需的所有共享自行车。目标函数是由人均就业成本的消毒工作人员和成本与消毒工作人员的工作时间有关。决策变量是消毒人员的数量和他们的路线。在解决问题的过程需要大量的计算,CA模型的目的是获得一个近似函数的下界最佳员工的数量。基于确定最优的下界的消毒工作人员通过使用近似函数,K-GA可以应用获得最初的解决方案,和K-GA-adjustment算法可以得到特定的消毒方案。这个过程可以很大程度上减少计算时间。 A case study based on the real world bike location data of Chengdu has been presented. Results show that the proposed method could be used for large-scale disinfection problems. The results indicate that the CA method can obtain the near-optimal number of staff with relatively short computing time. The proposed method can also be used in other scenarios, such as the cleaning and disinfection of shared e-scooters [50,51),汽车共享,共享权力银行,和共享的篮球。

这项研究仍有可能在将来得到的一些限制。首先,由于均匀分布的假设,使用K-GA-adjustment算法可以获得令人满意的结果。如果共享自行车的分布不是均匀的,近似函数可能不准确的下界估计消毒人员的数量,它可能需要更长的时间K-GA-adjustment算法来找到一个解决方案。因此,可以探索不同的自行车分布下的消毒方案。其次,虽然该研究选择最低的时期客流量消毒,少量的自行车共享使用仍可能干扰消毒过程。第三,本研究的重点是提出一个解决问题的框架。当该方法应用于真实世界的问题,有必要考虑实际的道路网络,启发式算法比遗传算法更有效,和高级编程语言,如Java和c++。

数据可用性

使用的数据来支持这个研究的发现可以从相应的要求。

的利益冲突

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

确认

这项研究是由中国国家自然科学基金(格兰特数字71704145、71831006和51774241),中国博士后科学基金会、四川省青年科技基础创新研究团队项目(批准号2019 jdtd0002和2020 jdtd0027),和教育部人文社会科学基金(批准号18 yjczh138)。