需求不确定的故障共享单车回收PVRP研究

2022-05-30 20:26徐阳,周亚南,苏兵,黎建强,张欣
预测 2022年5期
关键词:近似算法

徐阳,周亚南,苏兵,黎建强,张欣

摘要:为了及时有效地回收城市道路网络中的故障共享单车,本文考虑单车停放站点上回收需求呈现的不确定特征,建立以行驶总距离最小为目标的回收周期性车辆路径选择模型。采用基约束鲁棒优化方法,利用有界区间对不确定的回收量进行描述,并引入扰动系数和控制系数调节模型的鲁棒性和适应性。针对模型设计近似算法进行求解,分析算法近似比的上下界,通过实例分析验证了算法和模型的有效性。

关键词:需求不确定;周期性车辆路径;鲁棒优化;近似算法

中图分类号:C934文献标识码:A文章编号:2097-0145(2022)05-0073-08doi:10.11847/fj.41.5.73

Period Vehicle Routing Problem for Fault-sharing Bicycle

Recycling with Demand Uncertain

XU Yang1,2,3, ZHOU Ya-nan1,2,3, SU Bing1,2,3, LI Jian-qiang4, ZHANG Xin1,2,3

(1.School of Economics and Management, Xian Technological University, Xian 710021, China; 2.Soft Science Base for Ordnance Industry Innovation & Dvelopment in Shaanxi Province, Xian 710021, China; 3.Civil-Military Integration Science and Technology Innovation Research Center of Shaanxis Colleges and Universities, Xian 710021, China; 4.International Business School, Shaanxi Normal University, Xian 710119, China)

Abstract:In order to recover the fault-sharing bicycle in the urban road network timely and effectively, considering the uncertain characteristics of the recovery demand on the single vehicle parking spot, a recovery periodic vehicle route selection model aiming at minimizing the total distance is established. The basis constrained robust optimization method is adopted, the uncertain recovery is described by bounded interval, and the disturbance coefficient and control coefficient are introduced to adjust the robustness and adaptability of the model. The approximation algorithm is designed to solve the model, and the upper and lower bounds of the approximation ratio of the approximation algorithm are analyzed. An example analysis is given to verify the effectiveness of the algorithm and the model.

Key words:demand uncertain; period vehicle routing problem; robust optimization; approximate algorithm

1引言

共享单车作为城市交通的重要组成部分,是实现城市绿色、低碳出行的重要工具,其轻便快捷的优势,是解决城市出行“最后一公里”问题的重要手段。但是共享单车在快速发展的同时,遇到了诸多问题:共享单车因自然损耗、人为损坏等原因会出现故障,需要进行回收处理。而实际中,故障共享单车存在的停放点和产生量往往是不确定的,对所有站点进行单次回收,常常难以满足实际的回收需求。因此,如何根据共享单车这一特殊货物的特性,考虑回收量不确定的情形下,设计科学、有效的周期性回收调度策略是一个亟待解决的问题。

故障共享单车的回收是共享单车运营过程中不可避免的问题。现有对共享单车系统的研究主要集中在共享车辆调度优化与站点需求预测方面。针对考虑库存的车辆调度问题,以公共自行车调运库存量最小为目标,Ines和Anabela[1]首次考虑了共享单车站点的服务水平来平衡库存的共享单车车辆调度问题。Brinkmann等[2]研究了自行车共享系统的随机库存路径问题。Schuijbroek等[3]根据每个公共自行车站点的服务水平,选择车辆路径进行调配。针对解决公共自行车需求不平衡问题,Ghosh等[4]提出基于车辆路径选择的公共自行车动态复位优化方法。Leonardo等[5]提出了根据空间和社会公平的原则对区域中的自由式共享单车系统进行调度的分配策略。针对公共自行车需求预测问题,Xu等[6]提出了一種基于随机森林(RF)的改进预测方法,并利用遗传算法对共享单车调度路线进行优化。Wang等[7]基于深度学习(DL)模型对自行车共享网络短期需求预测进行研究。针对共享单车系统的站点需求预测同时对站点的数量及容量规划安排问题,Chen等[8]基于自行车出行模式的稀疏性和局部性,提出了一个稀疏加权正则化模型分析站点的潜在需求。Dell等[9]运用启发式算法研究了自行车共享再平衡问题。多数车辆调度研究仍使用传统的数学优化方式,也有另辟蹊径的研究者,试图使用激励机制来提高共享单车的使用率。如Tsai等[10]研究通过调节返回焦虑信息值提高共享单车调度的效果。

相对于共享单车的调度研究,故障共享单车的回收研究相对较少。现有对故障共享单车的研究大多假设回收需求量确定。Wang等[11]研究了可用自行车再平衡过程中损坏车辆的回收问题。以系统调度时间最短为目标,肖建华等[12]将故障单车信息的不确定性引入车辆调度中,研究了新车投放、旧车调拨、坏车回收的共享单车联合调度问题。Kaspi等[13]提出了一种EUDF函数用来表示给定时间段内不同租用或还车的用户数量的期望加权之和。

现有研究,大多是假设回收量确定情形下的单周期回收;而实际中,回收工作是一个长期且回收量动态变化的系统工程,但单周期的最优方案不能满足全局最优。因此,引入“全周期管理”(product lifecycle management, PLM)理念,即把回收对象视为一个动态变化的个体,从其分布特点、系统要素等层面进行全周期统筹和全过程整合,以确保整个回收体系形成一个有机的闭环,真正做到运转高效。

鉴于此,本文提出了回收需求不确定的故障共享单车回收周期车辆路径(PVRP)问题。即考虑回收需求不确定下,根据站点上的故障共享单车回收量进行不同周期的回收服务。并以行驶总距离最小为目标,决策每个站点回收量和回收车辆路径,给出可操作性强的故障共享单车回收方案,最终将研究成果应用于实际,为城市共享单车企业高效率回收故障共享单车提供理论依据。

2问题描述与建模

2.1问题描述与分析

已知无向网络G=(V,E),V={v1,…,vi,…,vn}∪{v0}为点集,其中v0表示回收中心,{v1,…,vi,…,vn}表示网络中有n个共享单车停放点,停放点vi上的故障共享单车回收量qi∈[i-i,i+i],i为理想值或均值,i为绝对偏差。一辆容载量为Q的回收车辆空载从回收中心出发进行回收服务,对停放点vi进行hi=「qi/Q次回收,车辆满载后回到回收中心。满载的回收车辆在回收中心卸载后继续进行回收任务,直到服务完所有站点的回收需求。因此,如何选择回收车辆路径,使得车辆满载后返回回收中心的行驶总距离最小。

相关假设:

(1)故障共享单车停放站点已知。

(2)停放点的回收量的均值可通过历史数据获得。

(3)不考虑路段行驶时间对目标的影响。

相关参数定义如下:qdi表示节点vi处在第d回收阶段的回收量;hi表示节点vi需要回收的次数;Q表示回收车辆的最大装载量;cij表示回收车辆从vi到vj的行驶距离;W表示回收中心的容量限制。决策变量定义如下:

xdij:当回收车辆在第d回收阶段从vi行驶到vj为1,否则为0。

ydi:当回收车辆在第d回收阶段对vi进行服务为1,否则为0。

2.2故障共享单车回收PVRP模型建立

综合考虑问题目标和所有的限制条件,建立如下模型

min Z=∑md=1∑ni=0∑nj=0cijxdij(1)

s.t.∑ni=1ydiqdiQ,d=1,2,…,m;i=1,2,…,n(2)

∑md=1ydi=hi,d=1,2,…,m;i=1,2,…,n(3)

∑ni=0xdij=ydi,i=0,1,…,n;i≠j;d=1,2,…,m(4)

∑nj=0xdij=ydi,j=0,1,…,n;i≠j;d=1,2,…,m(5)

∑nj=1xdj0=0,j=1,2,…,n(6)

∑ni=1qi-W0,i=1,2,…,n(7)

∑md=1∑ni=1∑nj=1xdij|S|-1,2|S|n-1(8)

(1)式为目标函数,表示行驶总距离最短;(2)式表示容量约束,保证任一回收阶段内每条路径上的回收量不超过车载容量;(3)式表示停放点被服务的次数等于其回收需求次数;(4)、(5)式表示任一回收阶段内每个站点只服务一次;(6)式表示回收车辆从回收中心出发并返回回收中心;(7)式表示所有停放点的故障单车回收总数量不超过回收中心的容量限制;(8)式表示避免子回路。

3模型分析与求解

车辆路径问题(VRP)是一个NP难问题[14],精确求解较为困难。而PVRP是车辆路径问题的拓展,相当于多个VRP问题的组合,因此求解更为困难。本文针对不确定的回收量的故障共享单车回收PVRP问题,首先引入魯棒优化的思想处理不确定的回收量,然后对构建的回收模型设计近似算法进行求解。

3.1求解思路

针对上述提出回收模型中,约束(2)和(7)含有不确定的回收需求参数qi,本节将qi用基约束鲁棒方法进行处理。

3.1.1基约束鲁棒方法的求解思路

基约束鲁棒方法的基本思想是为了避免绝对的鲁棒优化问题,即在所有的不确定参数中只有一部分参数的变化值达到上限,其余一部分不变或变化较小,在此情况下,求得满足所有约束的解,其具体模型如下

max c′x

s.t.∑aijxj+max{Si′∪{ti}|SiJi,|Si|=Γi」,ti∈Ji\Si}{∑j∈Siijyj+

(Γi-Γi」)itiyt}bi,-0yjxjyj,

lxu,y0

3.1.2不确定需求的表示

停放点上的故障共享单车回收需求量qi的变化范围满足以i为中心,i为步长,即qi∈[i-i,i+i],但停放点实际的回收需求量qi的值是未知的。其中i表示停放点回收需求量qi的名义值(即qi的平均值);i表示停放点回收需求量的最大绝对偏离值,即最大扰动值,i=σi,i0(σ为需求扰动系数)。每个停放点的回收求量qi在上述区间内随机取值。从取值的区间可以看出,停放点的回收需求量qi,都取值均值(或理想值)i或最小值i-i的可能性很小,实际情况中qi的取值在区间的任一位置都是有可能的。为了更好刻画停放点回收需求取值情况,运用鲁棒优化的思想引入需求控制系数Γi和需求偏离系数λi。

定义1停放点回收需求量qi偏离均值的偏离系数λi为

λi=qi-iσi,λi∈[-1,1]

定义2引入回收需求控制系数Γi,使得所有停放点的回收需求偏差系数之和不大于Γi。即

∑|λi|Γi,Γi0

Γi用来描述回收需求变化的情况,即需求发生变化的停放点的个数。当Γi=0时,所有停放点的回收需求量为名义需求值(均值),此时该问题转为需求确定的回收问题;当Γi=n时表示所有停放点的回收需求量达到最大偏离值,此时该问题转为绝对鲁棒问题,鲁棒性最强,但求解所得的解过于保守,解的最优性比较差。因此,当控制系数Γi越大时,停放点的回收需求的不确定性也越大。

第1步需求量的确定。

在停放点回收需求变化扰动系数σ下,为了使停放点回收需求波动后总的回收需求量最大(即鲁棒性达到最大),将停放点平均需求量i从大到小排列1′,2′,…,n′,选择前Γi个停放点需求进行扰动,计算扰动后所有停放点的回收需求之和达到的最大值q′sum,q′sum=∑i′+max{S∪{t}|Sn,|S|=Γ」,t∈n\S}{∑i+(Γi-Γi」)t}。若q′sumW,则确定前Γi个停放点的回收需求进行扰动,qi=i+iλi。

第2步需求波动后停放点回收次数的计算。

根据扰动后的停放点需求量与车辆最大容量的比值,求得各停放点的所需的回收次数hi=「(i+iλi)/Q。

第3步回收车辆路径的求解。

(1)分多个阶段对停放点上的故障共享单车进行回收。首先,以所有的停放点为回收对象V′={v1,…,vi,…,vn},以回收中心v0为回收路径的起点,车辆初始剩余装载量s0=Q,选择距离v0最短的一条边e(v0,vi)加入到路径当中。

(2)判断vi的回收需求量是否大于车辆剩余装载量,若大于则回收车辆满载后找最短路e(vi,v0)回到回收中心,输出回收路径并更新vi的需求量qi=qi-s0;若小于,则回收vi的全部需求量,更新车辆剩余装载量si=s0-qi,搜索距离vi最近的停放点加入到路径当中,直到满载后找最短路回到回收中心,输出回收路径重复上述操作,直到所有停放点都服务了一次y1i=1。

(3)在V′的基础上更新停放点回收服务集合。判断停放点vi被服务的次数是否与其回收次数(周期个数)相等,若相等∑ni=1ydi=hi,则将vi从V′删除,更新停放点服务集合V′。

(4)重复上述步骤直到所有停放点被服务的次数等于其回收次数,∑ni=1ydi=hi。

3.2算法设计

根据以上思路设计算法GA*,如图1所示。

第1步V′={v1,…,vi,…,vn}为初始停放点服务集合,cij为网络边的行驶距离,σ为需求扰动系数,Γi为需求发生波动的站点个数,λi为停放点回收需求偏离均值的权重系数,si为回收车辆服务完vi后的剩余车载容量。

第2步将停放点vi按需求均值i从大到小排列,记为1′,2′,…,n′。

第3步对前Γi个停放点i需求量进行扰动1′,2′,…,n′,计算扰动后的总需求最大值q′sum=max{S∪{t}|Sn,|S|=Γ」,t∈n\S}{∑i+(Γi-Γi」)t}。

第4步若q′sum

第5步计算停放点回收频次hi=「(i+iλi)/Q。

第6步令回收车辆初始剩余装载量s0=Q,计算v0到V′中各个停放点的距离coi,选择距离最短的一条边e(v0,vi)加入到路径p11={e(v0,vi)},从V′中删除vi,令x10i=1,y1i=1。

第7步判断vi的回收量与车辆剩余装载量的大小,若qis0,则装满后回到回收中心,将e(vi,v0)加入到p11={e(v0,vi),e(vi,v0)},更新停放点vi的需求量qi′=qi-s0,转第9步;否则,更新si=Q-∑ni=1qi,寻找距离vi最近的停放点vj,将边e(vi,vj)加入到路径p11={e(v0,vi),e(vi,vj)},vj从V′中删除,令x1ij=1,y1j=1。

第8步判斷vj的回收量与车辆剩余装载量的大小,若qjsi,则装满后回到回收中心,将e(vj,v0)加入到p11={e(v0,vi),e(vi,vj),e(vj,v0)},更新停放点vj的需求量qj′=qj-so,转第9步;否则转第7步。

第9步生成回路集合p11,x1ij,y1i,标记回收路径l11=1。

第10步重复步骤6~9,直到V′=,即V′中所有停放点都服务了一次,输出第一回收阶段的车辆路径集合p11={p11,p12,…,p1u}。

第11步更新停放点服务集合。计算停放点被服务的次数∑d=1∑ni=1ydi,若∑md=1∑ni=1ydi=hi,则将停放点vi从V′={v1,…,vi,…,vn}中删除,得到更新后的停放点服务集合V′。

第12步重复步骤6~11,直到所有停放点的服务次数∑md=1∑ni=1ydi=hi,输出各回收阶段的车辆路径集合Pd,xdij,ydi,ldi。

3.3算法时间复杂度

第1~2步最大计算次数O(n2);第3~4步计算次数不大于O(n);第5步的计算次数为O(n);第6~10步循环的计算次数不大于O(n);第11~12步的循环计算次数小于O(n);所以算法GA*可在O(n2)的时间内求出回收方案。由此得到如下定理。

定理1在回收中心容量限制下,故障共享单车回收PVRP问题算法GA*的时间复杂性为O(n2),其中n为共享单车停放点的数量。

3.4算法GA*的近似比

OPT(I)表示实例I的最优解,A(I)表示应用算法GA*对实例I的解。首先分析最优解并给出以下引理。

引理1对于任一实例I,站点上的故障共享单车回收PVRP问题的最优解OPT(I)下界为(β+1)∑ni=1「qi/Qb*。

证明在无向完全网络中,车辆服务完所有站点的回收需求后所行驶的路径数量不少于回收量之和与车辆最大装载量的比值,即所有回收阶段使用的车辆总数l′=∑ni=1qi/Q,服務所有停放站点的次数为∑ni=1hi,则回收车辆服务完所有站点的需求至少要行驶的边的数量为l′+∑ni=1hi,每条边的行驶距离不小于min{cij},具体证明如下

OPT(I)(l′+∑ni=1hi)min{cij}

=(∑ni=1qi/Q+∑ni=1「qi/Q)b*

=(β+1)∑ni=1「qi/Qb*

其中β=(∑ni=1qi/Q)/∑ni=1「qi/Q,0<β1;b*=min{cij}表示回收车辆行驶的最短路段的距离。应用算法GA*对任一实例I进行求解,算法GA*得到的解为

A(I)=∑md=1∑ni=0∑nj=0cijxdij

=∑d=1∑e(vi,vj)∈Pdicijxdij

(∑md=1∑li=1ldi+∑ni=1hi)max{cij}

=(∑md=1∑li=1ldi+∑ni=1「qi/Q)a*

其中a*=max{cij}表示回收车辆行驶的最长路段的距离。根据以上分析,给出如下定理。

定理2故障共享单车回收PVRP问题算法GA*的近似比为λβ+1(1+∑md=1∑li=1ldi∑ni=1「qi/Q)。

α=A(I)OPT(I)

=(∑md=1∑li=1ldi+∑ni=1「qi/Q)a*(β+1)∑ni=1「qi/Qb*

=λβ+1(1+∑md=1∑li=1ldi∑ni=1「qi/Q)

其中λ是a*=max{cij}与b*=min{cij}的比值。分析可知,算法GA*的近似比α与回收车辆行驶路段的最长边与最短边的比值λ呈正比,与回收量之和∑qi呈反比;当站点间分布相对均匀,且站点的回收量与整车容量差异越小,即β越大时,算法近似比越小。

结合定理2进一步讨论近似比的变化范围并给出以下几个推论。

当∑md=1∑li=1ldi=∑max{hi}时,即服务回收需求次数最大的站点时途经的剩余站点也刚好一起服务完,并且每辆车刚好满载;当且仅当最大需求次数的站点为1时,此时α的值最小。因此分析算法GA*的近似比,得到推论1如下。

推论1故障共享单车回收PVRP问题算法GA*的近似比下界为λβ+1(1+1n)。

α=λβ+1(1+∑md=1∑li=1ldi∑ni=1「qi/Q)

λβ+1(1+∑max{hi}∑ni=1「qi/Q)

λβ+1(1+max{hi}nmax{hi})

=λβ+1(1+1n)

当∑md=1∑li=1ldi=∑ni=1「qi/Q时,即空载回收车辆每次服务任一站点后都会满载,并返回回收中心。此时算法GA*的近似比值α最大。因此分析算法GA*的近似比,得到推论2如下。

推论2故障共享单车回收PVRP问题算法GA*的近似比上界为2λβ+1。

α=λβ+1(1+∑md=1∑li=1ldi∑ni=1「qi/Q)2λβ+1

3.5算例分析

为了验证算法的运行效果,对算法进行仿真模拟。取λ∈[1,4],β∈(0,1],以及回收站点的个数取n=20。使用软件Matlab R2016a,运行环境Intel(R)Core(TM)i7-8550U CPU/ 2.00 GHz。

通过算法近似比上下界的运行结果,进一步分析影响算法运行效果的关键因素,及其影响程度的大小。如图2和图3所示。

从图2和图3可以看出,算法近似比下界最大在3.8左右,上界最大值在8左右(理想最优值α=1),说明算法整体运行的效果较好。随着λ的增大,算法近似比的增幅呈扩大趋势,而β的影响较小。因此,可以得出站点间位置分布的均衡性,对算法运行的效果有重要影响。

4实例分析

西安雁塔区分布着众多高校以及历史人文景点,客流量较大,共享单车使用频繁。本实例选取西安市雁塔区的故障共享单车进行分析。实际回收过程中,共享单车停放站点上的故障单车的回收需求量难以获得准确的数值,由于人为损坏或单车GPS定位失灵以及其他不可抗拒的自然损耗,往往回收数量与共享单车运营后台收到的报修数量有差异。本实例中采用2018年8月某时段,站点的平均回收量作为名义需求量,取最大扰动系数σ=0.3时站点需求变化区间如表1所示。

当回收需求量扰动系数(需求量变化程度)和控制系数(需求量发生变化的停放站点个数)为固定值时,此时该不确定问题转化为需求已知的问题。为了验证模型的有效性,以Γi=0为例,即回收需求量取均值的情况下,应用算法GA*对实例进行求解。

首先根据各站点的需求量计算各站点的回收次数hi=「i/Q,如表2所示。

运用算法GA*对该实例进行求解。求解得到11条回收路径,需要分两个阶段进行回收,回收车辆的行驶总距离为29.6 km,算法的近似比为3.38,说明了该算法实际使用效果较好,求解的回收车辆路径、回收量以及行驶距离如表3所示。

为了更好地验证模型和算法的鲁棒性(稳健性),引入需求扰动系数σ和控制系数Γi,分析当需求发生变时对目标函数值和竞争比的影响。扰动系数σ越大表示需求量取值越大,偏离需求均值的程度越大;控制系数Γi越大表示需求量发生变化的停放点数量越多。本节需求量扰动系数取σ=0.1,0.2,0.3(即需求量变化程度),需求控制系数取Γi=5,10,15(即需求量发生变化的停放站点个数),运用算法GA*求解结果如下。

从表4可以看出,当共享单车停放站点上的故障共享单车回收量变化程度σ给定后,随着控制系数Γi的增大,最短行驶总距离呈现整体上涨趋势;在Γi一定时,即发生需求变化的停放站点数量一定,随着扰动系数σ的增大,最短行驶总距离也逐渐增大,当Γi=10时,最短行驶总距离目标函数值变化不明显,说明该实例中算法具有较强的鲁棒性(稳健性);且相对于扰动系数σ,控制系数Γi对目标函数值的影响更大,即需求发生变化的站点数量比站点回收量变化程度对回收车辆行驶总距离的影响更大。

从表5可以看出,算法的近似比与控制系数Γi呈正比,但与需求扰动系数σ无明显比例关系;總体看算法近似比基本稳定在3.5与4之间;而通过近似比的分析可以得到该实例的近似比上下界为6.84和1.8;实例分析过程中算法的近似比α靠近下界,说明该算法实际使用效果较好。

5结论与启示

本文考虑需求不确定的停放站点上故障共享单车回收PVRP问题。以行驶总距离最小为目标,构建故障共享单车回收PVRP模型。并针对模型中不确定的回收需求量采用鲁棒优化的方法,来刻画回收需求变化情形,并设计近似算法对模型进行求解,进一步分析该算法的近似比和近似比的上下界。最后进行实例分析,结果表明:回收量的波动程度和需求变化的站点数量,都对目标函数值有重要影响,且需求变化的站点数量影响更大。

因此,在实际回收过程中,共享单车企业在设置回收站点时,应当注重站点的位置分布的均匀性,站点数量的上限控制,以及站点容量的整车化,能有效地应对回收需求的不确定性。另外,共享单车回收卡车还会执行共享单车投放任务,面对乘客出行需求呈现的早晚高峰的时间差异,如何错峰回收和需求转移等问题将有待深入研究。

参考文献:

[1]Ines F, Anabela R. Bike-sharing stations: a maximal covering location approach[J]. Transportation Research Part A: Policy and Practice, 2015, 82(9): 216-227.

[2]Brinkmann J, Ulmer M W, Mattfeld D C. Short-term strategies for stochastic inventory routing in bike sharing systems[J]. Transportation Research Procedia, 2015, 10: 364-373.

[3]Schuijbroek J, Hampshire R C, Van H W J. Inventory rebalancing and vehicle routing in bike sharing systems[J]. European Journal of Operational Research, 2017, 257(3): 992-1004.

[4]Ghosh S, Varakantham P, Adulyasak Y. Dynamic repositioning to reduce lost demand in bike sharing systems[J]. Journal of Artificial Intelligence Research, 2017, 58(2): 387-430.

[5]Leonardo C, Rosalia C, Michele O. Planning and design of equitable free-floating bike-sharing systems implementing a road pricing strategy[J]. Journal of Advanced Transportation, 2017, (12): 1-18.

[6]Xu H T, Duan F, Pu P. Dynamic bicycle scheduling problem based on short-term demand prediction[J]. Applied Intelligence, 2019, 49(5): 1968-1981.

[7]Wang B, Vu H L, Kim I, et al.. Short-term traffic flow prediction in bike-sharing networks[J]. Journal of Intelligent Transportation Systems, 2021, (3): 1-18.

[8]Chen L B, Ma X J, Nguyen T M T, et al.. Understanding bike trip patterns leveraging bike sharing system open data[J]. Frontiers of Computer Science, 2017, 11(1): 38-48.

[9]Dell A M, Iori M, Novellani S, et al.. A destroy and repair algorithm for the bike sharing rebalancing problem[J]. Computers & Operations Research, 2016, 71(7): 149-162.

[10]Tsai M F, Chen P, Hong Y J. Enhancing the utilization of public bike sharing systems using return anxiety information[J]. Future Generation Computer Systems, 2019, 92(3): 961-971.

[11]Wang Y, Szeto W Y. Static green repositioning in bike sharing systems with broken bikes[J]. Transportation Research Part D, 2018, 65(12): 438-457.

[12]肖建华,贾楠,潘钰雅,等.基于破损信息不确定的共享单车新车投放-旧车调拨-坏车回收联合调度优化研究[J].数学的实践与认识,2021,(12):89-101.

[13]Kaspi M, Raviv T, Tzur M. Bike sharing systems: user dissatisfaction in the presence of unusable bicycles[J]. IIE Transactions, 2017, (2): 144-158.

[14]Salhi S, Rand G K. Incorporating vehicle routing into the vehicle fleet composition problem[J]. European Journal of Operational Research, 1993, 66(3): 313-330.

猜你喜欢
近似算法
基于订单取消量可预测的制造商原材料库存优化研究
一种最优相似度的公共序列研究
特定材料构建支撑树问题的近似算法研究
多材料Terminal Steiner树拼接问题的近似算法研究
巡检线路的排班模型
哈密尔顿图在快递送货中的应用
应用自适应交叉近似算法快速计算导体RCS
求投影深度最深点的近似算法
机器带故障的三台机排序问题的两个近似算法
旅行售货员问题TSP的模拟退火算法