基于快速非支配排序遗传算法的共享电单车归还策略.pdf

收稿日期:2 0 2 2 1 0 3 1基金项目:国家自然科学基金面上项目(6 1 8 7 3 3 3 8);中国博士后基金资助项目(2 0 1 8 M 6 3 0 3 0 3)。作者简介:王 丹(1 9 7 9),女,辽宁沈阳人,博士,教授。第3 5卷 第5期2 0 2 3年 1 0月沈阳大学学报(自然科学版)J o u r n a l o fS h e n y a n gU n i v e r s i t y(N a t u r a lS c i e n c e)V o l.3 5,N o.5O c t.2023文章编号:2 0 9 5-5 4 5 6(2 0 2 3)0 5-0 4 2 5-0 6基于快速非支配排序遗传算法的共享电单车归还策略王 丹,韩丰元(沈阳大学 装备制造综合自动化重点实验室,辽宁 沈阳 1 1 0 0 4 4)摘 要:为满足当前共享电单车随取随停的需求,解决其缺乏规范管理而导致的乱停乱放现象及其所呈现出的“多、散、乱”的状态与区域性供给不平衡问题,构建了基于多目标规划模型的平衡状态下的共享电单车归还模型。首先,应用快速非支配排序遗传算法(N S G A-)确定平衡状态下的归还点分配方案;然后,结合专家打分、C OWA算子、博弈论组合赋权法和TO P S I S法,从帕累托最优解集中选出最佳方案;最后,通过对比普通归还点分配方案里的用户所需付出的步行代价、时间代价和共享电单车的区域供给性,来验证实验结果的有效性。关 键 词:N S G A-遗传算法;多目标优化模型;用户出行模型;共享电单车;专家打分评估法中图分类号:T P 3 0 1.6 文献标志码:AR e t u r nS t r a t e g yo f S h a r e dE-b i k e sb a s e do nF a s tN o n d o m i n a t e dS o r t i n gG e n e t i cA l g o r i t h mWANGD a n,HANF e n g y u a n(K e y L a b o r a t o r y o f M a n u f a c t u r i n g I n d u s t r i a lI n t e g r a t e d A u t o m a t i o n,S h e n y a n g U n i v e r s i t y,S h e n y a n g1 1 0 0 4 4,C h i n a)A b s t r a c t:I no r d e r t om e e t t h e c u r r e n t n e e do f t h e s h a r e de-b i k e s t h a t a r ep a r k e do nd e m a n d,s o l v e t h ep r o b l e mo fd i s o r d e r l yp a r k i n gc a u s e db yt h e l a c ko fs t a n d a r d i z e dm a n a g e m e n t,a sw e l la st h ep r o b l e m o f“m u l t i p l e,s c a t t e r e d,a n dd i s o r d e r l y”s t a t ea n dr e g i o n a ls u p p l yi m b a l a n c e,ar e t u r n m o d e lo fs h a r e de-b i k e su n d e rb a l a n c e ds t a t eb a s e do nt h e m u l t i-o b j e c t i v ep r o g r a mm i n gm o d e lw a sc o n s t r u c t e d.M o r e o v e r f a s tn o n d o m i n a t e ds o r t i n gg e n e t i ca l g o r i t h m(N S GA-)w a sa p p l i e dt od e t e r m i n et h er e t u r na d d r e s sa l l o c a t i o ns c h e m eu n d e rt h es t a t e o f e q u i l i b r i u m.C o m b i n i n g e x p e r t s c o r i n g,C OWA o p e r a t o r,g a m e t h e o r yc o m b i n a t i o nw e i g h t i n gm e t h o da n dTO P S I Sm e t h o d,t h eb e s t s c h e m ew a ss e l e c t e df r o mt h eP a r e t oo p t i m a ls o l u t i o ns e t.F i n a l l y,t h ee f f e c t i v e n e s so ft h ee x p e r i m e n t a lr e s u l t s w a sv e r i f i e db yc o m p a r i n gt h ew a l k i n gc o s t,t i m ec o s ta n dt h er e g i o n a la v a i l a b i l i t yo fs h a r e de-b i k e s t h a tu s e r sn e e dt op a y i nt h eg e n e r a l r e t u r na d d r e s s e sd i s t r i b u t i o ns c h e m e.K e y w o r d s:NAGA-;m u l t i-o b j e c t i v e o p t i m i z a t i o n m o d e l;u s e rt r a v e l m o d e l;s h a r e de-b i k e s;e x p e r t s c o r i n ga n de v a l u a t i o nm e t h o d共享电单车比普通的自行车更加快捷省力,骑行体验更加舒适,是城市公共交通系统中重要的一环。相比其他交通工具而言,最后一公里问题得到了完美的解决。近几年,由于环境保护和健康意识的普及,低碳交通成为了当前城市交通系统中的主题,这使得公共交通系统有了巨大的改变,共享电单车不但缓解了公交车拥挤的压力,还使得城市的经济发展享受了共享概念的红利1。然而,共享电单车在给人们带来便利的同时,也因为过于饱和,给人行道带来拥堵,严重侵占了城市公共空间,给市政管理和运营商管理带来巨大压力2。有些区域供给不足导致行人需要花费大量时间找车,有时由于距离过远,刚到达地图上显示的共享电单车位置,却发现车已被人占用。当前调度方法主要是人工调度,运营商雇佣调度车进行统一的调度,花费大量的人力物力成本,效果差且维持时间短3。本文主要将共享电单车归还问题作为研究对象,通过预测区域内共享电单车区域性需求给出相应停车方案4。与以往的共享电单车调度方案入手角度不同,希望从用户的角度,采用快速非支配排序遗传算法(N S GA-)构建共享电单车合理归还模型5。在归还共享电单车时设计出1套合理的停车点推荐方案。使得共享电单车的饱和问题与供给不均的问题得到持续有效解决,促进城市的公共交通系统长久健康发展。1 基于多目标优化模型的共享电单车归还模型建立多目标优化是多个目标函数一同优化的问题,在多限制条件领域广泛使用。以往的共享电单车调度方法通常是运营商调用调度车进行大量的城市统一调度,这种调度方式不但要耗费大量成本,而且维护效果持续时间短6。本文从用户的角度入手,在根源上解决问题。根据模型所需参数的特点,针对运营商的需求与用户的体验感,做出以下假设:1)人们步行的速度v0保持恒定,共享电单车的行驶速度v1保持恒定,用户类别具有普遍性;2)研究范围仅为特定时间段内的区域性研究。用户每日骑行习惯不变,目的地不会改变;3)共享电单车整体运营正常,每辆共享电单车都可以正常使用,并且电量满足用户骑行至目的地;4)每个停车点有容量上限,超过停车点最大容量时,将产生惩罚成本;5)客户在寻找电单车时,加入决策范围的概念,在超出用户所能接受的寻找范围时,用户将放弃继续寻找,寻找范围的半径为固定值,并且假定所有用户相同;6)在计算停车点与目的地之间的初始距离时,不将停车点的区域面积算在内,停车点仅视为一个中心点作为研究对象。基于上述模型假设,建立以下数学模型:m i nG(x)=x3x1v1+x2v0 x2v0+HY(Qj-x3);(1)m i nK(x)=x4Mj+x1v1CjL。(2)在该模型中:G归还产生的代价值;K区域供给平衡性;用户决策系数;道路非直线平均系数;v1骑行速度;v0步行速度;Y单位超量所产生的费用;Qj当前区域所有停车点最大容量;H当前区域容量是否超标;Mj当前区域停车数量;Cj当前进入区域的电单车数量;L当前区域共享电单车的最佳数量。式(1)表示这个区域一段时间内所有用户要花费的总时间代价,式(2)表示当前区域停车点饱和度达到最优的容量大小7。本文优化目标是通过对用户骑行到停车点距离x1,停车点步行到目的地距离x2,一定时间内进入624沈阳大学学报(自然科学版)第3 5卷区域的单车数量x3,用户愿意听从选择的概率系数x4,共4个随机变量8,得出归还代价值最小和区域性供给不平衡性最小,即:m i nG(x1,x2,x3,x4),m i nK(x1,x2,x3,x4);(3)s.t.0 x15 0 0,x11 0 0N,0 x25 0 0,x21 0 0N,1 0 x33 0,x3N,0 x41,x40.1N。(4)式中,N为正整数。以上得出的多目标规划模型是一个非线性模型,仅适用于用户骑行出行的共享电单车归还分配研究,为得出最终研究结果,需要将多目标模型转化为单目标模型,转化完如式(5),m i nF=1K(x)+2G(x)。(5)式中:F为最优水平接触值;1、2为各目标大于0的权重系数,且满足1+2=1。2 N S G A-算法的双目标优化及决策过程本文优化目标函数G(x1,x2,x3,x4)和K(x1,x2,x3,x4)为加权均衡值,两者无法一同达到最小值。所以,F不存在同时最优的2个目标解,只能通过以下步骤得出2个优化目标均衡的解集9。1)求出帕累托最优解集;2)将解集中的全部元素进行评选的结果对比,分别从达到最优水平的帕累托解集中选出与对应的2个目标函数的解。目前带有快速非支配多目标优化算法有着特殊的精英保留策略,是一种基于帕累托最优解的多目标优化算法,其算法计算量大。N S GA-I I算法使用了快速非支配排序法,将算法的计算复杂度由O(mN3)降到了O(mN2),使得算法的计算时间大大减少。具体优化过程如图1所示。图1 N S G A-I I遗传算法优化过程F i g.1 N S G A-I I g e n e t i ca l g o r i t h mo p t i m i z a t i o np r o c e s s724第5期 王 丹等:基于快速非支配排序遗传算法的共享电单车归还策略由于本文的调度方案是从用户的角度入手,归还点分配选择中的目标优化涉及到用户的自行判断,而另一个要优化的目标则涉及到运营商考虑的成本问题,两者要考虑的主观因素占比高,所以,基于优化目标的特性来评估2个目标时,其重要性的大小是关键指标1 0。基于C OWA算子算出的评估指标的客观比重,继而利用博弈论来组合,修改主观权重,进而得出的综合比重会大幅度削弱最优解集中不可靠的解对客观权比的影响1 1。最后利用熵权法对解集的各个元素进行评价。具体的决策过程如下:1)主观权重n的计算(专家打分法)。n=ga=1Aa nga=12n=1Aa n。(6)式中,Aa n为专家a对指标n进行评估1 2。2)从最优解集的元素i中选出2个目标函数作为评估指标,进而得出指标矩阵S。S=(sm n)i*2(m=1,2,i;n=1,2)。(7)3)将各个元素进行标准化。S*m n=sm nsm a x。(8)式中,sm a x为每列的最大元素。4)基于C OWA计算出每个指标的客观权重*n。*n=*n2n=1*n=tn=1vmS*m n,(9)vm=Cm-1t-1t-1i=0Cm-1t-1=Cm-1t-12t-1。(1 0)式中,*n、vm为随机选择m-1个解的集合。5)得到的综合权重根据每个线性组合的客观权重与主观权重进行计算,1、2为每个不同组合,n为主观权重,*n为客观权重,用博弈论的方法降低n。n=1*n+2n。(1 1)6)权重矩阵D(每个解都被赋权)。D=(dm n)t 2(m=1,2,t;n=1,2)。(1 2)式中,dm n=S*m nn。7)矩阵中每列最小解为最优解T+n,最大解作为最劣解T-n。T+n=m i n(d1n,d2n,dt n);(1 3)T-n=m a x(d1n,d2n,dt n)。(1 4)8)计算权重矩阵中所有解的dm n与T+n,T-n的距离P+m,P-m。P+m=(dm n-T+n)2;(1 5)P-m=(dm n-T-n)2。(1 6)9)解出接近最优水平指数Dm,从大到小进行排列。Dm=P-mP+m+P-m。(1 7)3 优化及决策结果分析通过MAT L A B编程对前文所构建的共享电单车归还模型进行编码求解。参数设定为初始种群3 0 0代,迭代次数为5 0 0,如图2所示。1 0位专家对归还共享电单车代价G和区域供给平衡性K2个指标的重要性进行打分(相当重要为5分,重要为4分,比较重要为3分,一般重要为2分,不重要为1分),分数见表1。824沈阳大学学报(自然科学版)第3 5卷图2 帕累托最优解集结果F i g.2 P a r e t oo p t i m a l s o l u t i o ns e t r e s u l t s表1 专家对2个指标的打分T a b l e1 E x p e r t s s c o r e so n t h et w o i n d i c a t o r s专家序号GK1352453444355556347448559341 035 利用式(6)计算得到共享电单车归还代价值G和区域供给平衡性K2个指标的主观权重分别是0.4 4 58与0.5 5 42。利用式(9)计算得到共享电单车归还代价值G和区域供给平衡性K的客观权重为0.7 0 6 6和0.2 9 34。其线性组合的系数为0.6 5 66和0.3 4 34,进而根据式(1 2)在得到了线性组合的系数后,计算出综合权重分别为0.5 8 77和0.4 1 23。得到以上权重后,利用熵权法组合评估,进而得出解集中排名前1 0的解,见表2。表2 评估出最优解集中排名前1 0的解T a b l e2 T o p1 0s o l u t i o n so fP a r e t oo p t i m a l s o l u t i o ns e t o b t a i n e db yd e c i s i o n序号设 计 变 量用户区域内与目的地的距离m停 车 点 到目的地距离m进入区域内的电 单 车 数 量辆停车点饱和度用户愿意选择系数目 标GK15 0 03 0 01 50.7 80.52 6 6.4 3 71 3.0 4 424 0 04 0 01 60.6 10.12 4 9.9 6 51 3.2 3 835 0 05 0 01 81.1 20.72 8 2.7 2 91 2.8 4 743 0 03 0 02 01.4 30.42 3 3.5 8 41 3.4 3 054 0 04 0 02 51.5 40.82 9 9.1 1 11 2.6 4 664 0 04 0 02 61.6 20.92 6 1.8 8 81 3.1 5 675 0 05 0 01 81.7 71.02 6 2.8 8 01 3.1 4 682 0 02 0 01 91.7 80.52 7 8.2 7 01 2.9 6 391 0 01 0 02 01.8 30.92 5 7.2 5 11 3.2 1 61 01 0 01 0 02 21.8 50.22 7 3.6 3 31 3.0 2 3 由于要与普通方案进行对比,所以要控制变量。即2种方案用户骑行到停车点的距离一致,由于普通方案的优化目标只有距离最短,导致优化方案与普通方案选择的停车点不一样。所以,通过对比普通方案选择的停车点下的最优水平接近值,来验证优化方案是否可行、有效,结果见表3,普通方案选择优化方案帕累托前1 0的解的初始距离直接进行比照。表3 对比普通方案与优化方案最优水平接近值T a b l e3 C o m p a r i s o no f a p p r o x i m a t ev a l u eo f t h eo p t i m a l l e v e l b e t w e e n t h eg e n e r a l a n d t h eo p t i m i z a t i o n序号停车点到目的地距离/m优化方案普通方案最优水平接近值普通方案优化方案13 0 02 5 00.4 4 62 30.7 1 81 224 0 02 0 00.4 4 32 90.7 1 76 535 0 02 5 00.4 4 26 70.7 1 76 444 0 01 5 00.4 4 22 30.7 1 62 453 0 02 0 00.4 3 12 20.7 1 61 3序号停车点到目的地距离/m优化方案普通方案最优水平接近值普通方案优化方案62 0 02 0 00.4 3 01 90.7 1 49 274 0 02 5 00.4 2 97 70.7 1 48 583 0 01 0 00.4 2 96 80.7 1 45 392 0 05 00.4 2 95 50.7 1 45 11 04 0 05 00.4 2 89 90.7 1 44 9 通过对比帕累托前1 0组数据,普通方案的最优水平接近值总和为4.4 6 23,优化后的方案1 0组最优水平接近值总和为7.1 6 63,优化后的方案最优水平指数增加了6 0.9%,证明优化方案推荐的停车点924第5期 王 丹等:基于快速非支配排序遗传算法的共享电单车归还策略位置使得这段时间区域内的最优水平指数大幅度增加,在平衡了区域的供给性的同时又减少了停车点的饱和度,验证了优化后的方案有效可行。4 结 论本文基于多目标规划模型构建了平衡状态下的共享电单车归还模型,同时分析了优化目标的有效性。并用N S GA-I I确定最平衡状态下的归还点分配,基于熵权法与博弈论的组合来求出多目标权重比,再结合专家打分法从帕累托解集中得出有利的方案。通过对比普通方案的归还点分配下的代价值,来验证实验结果的有效性,可以有效解决共享电单车停车点饱和与区域性供给不平衡问题。参考文献:1 王丹,李佳洋,李蓓蕾.城市复杂动态交通路网模型与拥塞分析J.沈阳大学学报(自然科学版),2 0 1 7,2 9(1):3 1 3 6.WAN GD,L I JY,L IBL.U r b a nc o m p l e xd y n a m i ct r a f f i cn e t w o r km o d e la n ds i m u l a t i o na n a l y s i so fc o n g e s t i o nJ.J o u r n a lo fS h e n y a n gU n i v e r s i t y(N a t u r a lS c i e n c e),2 0 1 7,2 9(1):3 1 3 6.2 杜婉露.公共管理视角下城市共享单车规范化管理探究J.商业观察,2 0 2 1(1 5):5 4 5 6.D U W L.R e s e a r c ho ns t a n d a r d i z e dm a n a g e m e n to fu r b a nb i k e-s h a r i n gf r o mt h ep e r s p e c t i v eo fp u b l i cm a n a g e m e n tJ.B u s i n e s sO b s e r v a t i o n,2 0 2 1(1 5):5 4 5 6.3 种颖珊,韩晓明.基于随机森林与时空聚类的共享单车站点需求量预测J.科学技术与工程,2 0 1 8,1 8(3 2):8 9 9 4.C HON GYS,HANX M.P r e d i c t i o no fs h a r e db i c y c l es i t ed e m a n db a s e do nr a n d o mf o r e s ta n ds p a t i o t e m p o r a lc l u s t e r i n gJ.S c i e n c eT e c h n o l o g ya n dE n g i n e e r i n g,2 0 1 8,1 8(3 2):8 9 9 4.4 周奕杉.共享单车需求预测及优化调度算法的研究与应用D.西安:西安电子科技大学,2 0 2 1.Z HOUYS.R e s e a r c ha n da p p l i c a t i o no fb i k e-s h a r i n gd e m a n df o r e c a s t i n ga n do p t i m a ls c h e d u l i n ga l g o r i t h mD.X i a n:X i d i a nU n i v e r s i t y,2 0 2 1.5 胡子纯.基于改进遗传算法的高峰期共享单车调度优化研究D.南京:南京财经大学,2 0 2 1.HUZC.R e s e a r c ho no p t i m i z a t i o no fb i k e-s h a r i n gs c h e d u l i n gi np e a kt i m eb a s e do ni m p r o v e dg e n e t i ca l g o r i t h mD.N a n j i n g:N a n j i n gU n i v e r s i t yo fF i n a n c e&E c o n o m i c s,2 0 2 1.6 程磊.城市轨道交通车站周边共享单车需求预测及动态调配研究D.北京:北京交通大学,2 0 2 1.C HE N GL.R e s e a r c ho nd e m a n df o r e c a s ta n dd y n a m i ca l l o c a t i o no fb i k e-s h a r i n ga r o u n du r b a nr a i l t r a n s i ts t a t i o nD.B e i j i n g:B e i j i n gJ i a o t o n gU n i v e r s i t y,2 0 2 1.7 张晨岳.城市早高峰共享单车潮汐点调度策略研究D.上海:东华大学,2 0 2 1.Z HAN GCY.S t u d yo ns c h e d u l i n gs t r a t e g yo f t i d a lp o i n t s i nb i k e-s h a r i n gd u r i n gu r b a nm o r n i n gp e a kD.S h a n g h a i:D o n g h u aU n i v e r s i t y,2 0 2 1.8 曹青青.考虑故障单车回收的共享单车系统再平衡问题研究D.成都:西南交通大学,2 0 2 1.C AOQQ.R e s e a r c ho nr e b a l a n c i n go fb i k e-s h a r i n gs y s t e mc o n s i d e r i n gt h e r e c o v e r yo f f a u l t e db i c y c l e sD.C h e n g d u:S o u t h w e s tJ i a o t o n gU n i v e r s i t y,2 0 2 1.9 赵建宇.基于T OWA算子的新能源供电企业应急能力评估研究J.中国安全生产,2 0 2 1,1 6(7):4 8 4 9.Z HAOJY.R e s e a r c ho ne m e r g e n c yc a p a c i t ye v a l u a t i o no fn e we n e r g yp o w e rs u p p l ye n t e r p r i s e sb a s e do nT OWAo p e r a t o rJ.C h i n aO c c u p a t i o n a lS a f e t ya n dH e a l t h,2 0 2 1,1 6(7):4 8 4 9.1 0 王晓形.基于AH P及专家打分法的大跨度隧道风险评估J.现代隧道技术,2 0 2 0,5 7(增刊1):2 3 3 2 4 0.WAN GXX.R i s ka s s e s s m e n to ft h el a r g e-s p a nt u n n e lb a s e do n AH Pa n de x p e r ts c o r i n g m e t h o dJ.M o d e r n T u n n e l l i n gT e c h n o l o g y,2 0 2 0,5 7(S u p p l 1):2 3 3 2 4 0.1 1 刘鹏,王莉芳,许燕.基于“专家打分法”的D E A交叉效率聚集方法J.科技管理研究,2 0 1 9,3 9(2):2 4 8 2 5 3.L I UP,WAN G LF,XU Y.D E Ac r o s s-e f f i c i e n c ya g g r e g a t i o nm e t h o db a s e du p o ne x p e r ts c o r i n gJ.S c i e n c ea n dT e c h n o l o g yM a n a g e m e n tR e s e a r c h,2 0 1 9,3 9(2):2 4 8 2 5 3.1 2 郭东旭,侯发林.基于专家打分法的自航水雷使用可用度评估方法J.数字海洋与水下攻防,2 0 1 8,1(3):4 1 4 4.GUODX,HOUFL.E v a l u a t i o nm e t h o df o ro p e r a t i o n a l a v a i l a b i l i t yo fs e l f-p r o p e l l e dm i n eb a s e do ne x p e r ts c o r i n gm e t h o dJ.D i g i t a lO c e a n&U n d e r w a t e rW a r f a r e,2 0 1 8,1(3):4 1 4 4.【责任编辑:肖景魁】034沈阳大学学报(自然科学版)第3 5卷