一种avp条件下预约式共享停车供需匹配的自适应演化算法
技术领域
1.本发明涉及共享停车领域，尤其涉及一种在avp条件下预约式共享停车供需匹配的自适应演化算法。
背景技术：2.共享停车作为利用现有停车设施解决停车难问题的一种可行方法，与新建停车设施解决停车难问题相比，不仅改造时间短、成本低，而且效果更加显著。共享停车中车位拥有者通过共享停车平台发布车位空闲时段，出租空闲时段车位获取收益。车辆拥有者通过共享停车平台获取车位信息、停放车辆。共享平台管理方收集信息、发布信息、处理信息，管理停车场的日常事宜。但是，目前预约式共享停车大多关注停车场与目的地之间的距离、停车的费用等，很少考虑共享停车需求与泊位的匹配情况，忽略了不合理的共享停车方案不仅会导致共享停车需求无法得到满足，对停车难问题的缓解有限，还会使得泊位利用率极低，停车资源浪费。
3.自主代客泊车(autonomous va l et parki ng—avp)作为无人驾驶的又一新趋势，正逐步迈入人们的生活。传统共享停车中，车辆在其停车需求时间内只能停放在一个车位，导致车位利用率低、停车需求无法得到满足。而引入了avp 的共享停车，利用avp车辆“空驾”特征，通过自主移车将车辆在不同时段停放于不同泊位，利用共享泊位的空闲小时段进行停车，在满足共享停车需求的同时，大大提高了泊位利用率。但是不合理的停车方案也可能导致车辆的频繁移位，致使用车成本增加的同时，还会增加交通事故的发生率。为解决该矛盾，本发明提出一个以最少avp移车次数最大化满足共享停车需求的自适应演化算法。
技术实现要素：4.本发明的目的是为了解决上述问题，提供一种在avp条件下预约式共享停车供需匹配的自适应演化算法，包括如下步骤：
5.s1：以共享停车需求时间与泊位供给时间的首末时刻为断点，分割共享停车供需时间；
6.s2：在时段分割的基础上，将共享停车需求与供给泊位的关系定义为配对、时间配对、配对方案；
7.s3：通过定义换位和连续换位，分析车辆在给定时段上进行泊位调整的条件和泊位调整对配对方案移车次数的影响，设计avp车辆在分割时段进行泊位调整的自适应优化策略；
8.s4：在已知共享停车需求与泊位供给的前提下，结合上述自适应优化策略，引入变异操作，设计求解avp条件下预约式共享停车供需匹配的自适应算法。
9.进一步地，所述s1中，所述分割共享停车供需时间的具体步骤为：
10.s11：将所有共享停车供需时间的开始时刻和结束时刻放进集合t。
11.s12：剔除集合t内相同的元素，并从大到小排列剩余元素。
12.s13：以集合t内的元素为断点，将共享停车供需时间划分为多个时段。
13.进一步地，所述s3中，以一辆车为例，所述自适应优化策略具体步骤包括：
14.s31：对任一时段i，确定车辆v在时段i和时段i+1停放的泊位p与q。
15.s32：当p＝q，令i：＝i+1，回到s31，当p≠q，进入s33；
16.s33：分别以i和i+1为起始时段，在泊位p与q上搜索停放车辆v的相邻时段，得到与v相关的配对构成的两个集合e
p
和eq；
17.以q为目标泊位，确定连续换位s(e
p
，q)的成本变化量δc(s(e
p
，q))，同理确定δc(s(eq，p))；
18.s34：如果δc(s(e
p
，q))≥max{0，δc(s(eq，p))}，则实施连续换位s(e
p
，q)；否则实施连续换位s(eq，p)，令i：＝i+1，回到s31。
19.进一步地，所述步骤s3中，在连续换位si→
i+m
的作用下，成本变化量δc(si→
i+m
)的计算公式如下：
[0020][0021]
其中，δc(si→
i+m
)表示时段配对集合经过连续换位变为的成本变化量；表示未实施连续交换前，在其内部和与外部紧邻的其他时段配对之间由于车辆的移位产生的移车距离与移车惩罚性成本之和；表示连续换位后内部的移位距离与移车惩罚成本之和；和表示与外部的移车成本。
[0022]
进一步地，所述s4中，所述自适应优化算法包括如下步骤：
[0023]
s41：设置最大迭代次数τ
max
、配对方案自适应优化一次的最大次数α、变异操作系数β以及当前迭代次数τ＝1；
[0024]
s42：随机生成时段配对ei，i∈{1，2，...，n}，将其合理组合成一个配对方案ma，将其作为当前配对方案m
ing
和最优配对方案m
*
；
[0025]
s43：通过上述自适应优化策略对m
ing
进行α次自适应优化得到[m
ing
]
α
，令 m
ing
：＝[m
ing
]
α
。当m
ing
的移车次数小于m
*
的移车次数时，令m
*
：＝m
ing
[0026]
s44：对ming的第一个时段配对e1进行如下操作：
[0027]
生成一个[0，1]之间的随机数γ，如果β＞γ，则随机生成一个新的时段配对令否则，对后一个时段配对进行上述操作；
[0028]
s45：当m
ing
的移车次数为0或τ＝τ
max
，则输出m
*
并结束算法；当m
ing
的移车次数不为0或τ≠τ
max
，令τ：＝τ+1并回到s43。
[0029]
与现有技术相比，本发明的有益效果主要体现在：设计了一个全新的具有变异操作的自适应演化算法，避免算法过早地陷入局部最优；首次以降低移车成本和事故发生率为目标提高共享停车的泊位利用率、满足共享停车需求；考虑了avp车辆自主移位的特征，将共享停车需求时间和供给时间划分为更细小的时段。
附图说明
[0030]
图1为本发明一种在avp条件下预约式共享停车供需匹配的自适应演化算法的总流程图；
[0031]
图2为配对方案自适应优化策略流程图；
[0032]
图3为本发明实施例的时段分割图
具体实施方式
[0033]
下面将结合示意图对本发明一种在avp条件下预约式共享停车供需匹配的自适应演化算法进行更详细的描述，其中表示了本发明的优选实施例，应该理解本领域技术人员可以修改在此描述的本发明，而仍然实现本发明的有利效果，因此，下列描述应当被理解为对于本领域技术人员的广泛知道，而并不作为对本发明的限制。
[0034]
在本发明的描述中，需要说明的是，对于方位词，如有术语“中心”，“横向”、“纵向”、“长度”、“宽度”、“厚度”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”、“顺时针”、“逆时针”等指示方位和位置关系为基于附图所示的方位或位置关系，仅是为了便于叙述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定方位构造和操作，不能理解为限制本发明的具体保护范围
[0035]
如图1所示，一种在avp条件下预约式共享停车供需匹配的自适应演化算法，包括如下步骤：
[0036]
s1、以共享停车需求时间与泊位供给时间的首末时刻为断点，分割共享停车供需时间。
[0037]
s11、所有共享停车供需时间的开始时刻和结束时刻放进集合t。
[0038]
s12、剔除集合t内相同的元素，并从大到小排列剩余元素。
[0039]
s13、以集合t内的元素为断点，将共享停车供需时间划分为更细小的时段。
[0040]
一个共享停车区域8个共享泊位的开放时间为 p1(7:30-12:00,13:00-16:30)、p2(6:00-11:30)、p3(8:30-14:15,16:00-20:00)、 p4(7:15-11:45,13:30-18:15)、p5(9:30-16:00,16:45-19:30)、 p6(6:45-12:45,14:45-18:15)、p7(9:00-13:45,15:00-18:30)、 p8(8:00-15:15,6:00-18:45)，可视化的展示如图3所示。图3中，以1h为时间刻度将一天时间为24份，阴影部分表示泊位不支持共享，空白部分表示该时段泊位开放。以这8个泊位共享时间的始末时刻为断点，分割泊位开放时间。划分后，泊位p1、p2、p3、p4、p5、p6、p7、p8由原来2、1、2、2、2、2、2、 2个时段变为15、7、17、15、16、15、14、19个共享时段。为了简洁，本示例仅考虑共享泊位开放时间的始末时刻。
[0041]
s2、在时段分割的基础上，用e(i,v,p)表示时段i车辆v停放在车位p上的一个配对，e(i,0,p)表示没有车辆停放在泊位p上。ei表示时段i上所有配对构成的一个时段配对。m表示所有时段配对构成的一个配对方案。
[0042]
s3、分析车辆在给定时段上进行泊位调整的条件和泊位调整对配对方案移车次数的影响，设计avp车辆在分割时段上进行泊位调整的自适应优化策略。
[0043]
时段配对ei,e
i+1
之间，因avp车辆移位产生移车成本如式(1)所示。多个在时间上连续的时段配对{ei，e
i+1
，...，e
i+m
}之间的移位成本为}之间的移位成本为
[0044][0045]
式(1)中v表示所有具有停车需求的车辆构成的集合，p表示所有共享泊位构成的集合。n表示经分割得到的时段个数。决策变量表示时段i车辆v是否停放在车位p。如果是，其值为1；否则为0。l
p，q
为从车位p到车位q的移车距离。w表示avp车辆一次移位的惩罚成本。
[0046]
用si＝s(e(i，v1，p1)，p2)表示时段i上任意两个配对e(i，v1，p1)与e(i，v2，p2) 车辆调换停放泊位变为e(i，v2，p1)与e(i，v1，p2)的一次换位操作。s(e，p
′
)表示对e 内所有的e进行s(e，p
′
)。将一组在时间上连续的换位操作{si，s
i+1
，...，s
i+m
}，记为连续换位si→
i+m
，对应的时段配对集合为{ei，e
i+1
，...，e
i+m
}。
[0047]
在换位si的作用下，时段配对变为了记为实施换位si的成本变化量δc(si)如式(2)所示。
[0048][0049]
在连续换位si→
i+m
的作用下，成本变化量δc(si→
i+m
)的计算公式如式(3)。
[0050][0051]
其中，δc(si→
i+m
)表示时段配对集合经过连续换位变为的成本变化量；表示未实施连续交换前，在其内部和与外部紧邻的其他时段配对之间由于车辆的移位产生的移车距离与移车惩罚性成本之和；表示连续换位后内部的移位距离与移车惩罚成本之和；和和表示与外部的移车成本。
[0052]
一个配对方案进行自适应优化的流程如下，并用图2表示一辆车进行一次自适应优化的流程。
[0053]
s31、对每辆车v进行如下操作。对任一时段i，确定车辆v在时段i和时段 i+1停放的泊位p与q。
[0054]
s32、如果p＝q，令i：＝i+1，转s31。否则，转步骤s33。
[0055]
s33、分别以i和i+1为起始时段，向前和向后在泊位p与q上搜索停放车辆v的相邻时段，得到与v相关的配对构成的两个集合e
p
和eq。
[0056]
以q为目标泊位，确定连续换位s(e
p
，q)的成本变化量δc(s(e
p
，q))。同理确定δc(s(eq，p))。
[0057]
s34、如果δc(s(e
p
，q))≥max{0，δc(s(eq，p))}，则实施连续换位s(e
p
，q)；否则实施连续换位s(eq，p)。令i：＝i+1，转s31。
[0058]
s4、在自适应优化策略基础上引入变异操作，设计求解avp条件下预约式共享停车
供需匹配的自适应演化算法。
[0059]
s41、初始化参数。最大迭代次数τ
max
，配对方案自适应优化一次的最大次数α，变异操作系数β。当前迭代次数τ＝1
[0060]
s42、随机生成时段配对ei，i∈{1，2，...，n}，将其合理组合成一个配对方案ma，将其作为当前配对方案m
ing
和最优配对方案m
*
。
[0061]
s43、自适应优化。使用权利要求3给出的方法对m
ing
进行α次自适应优化得到[m
ing
]
α
，令m
ing
：＝[m
ing
]
α
。当m
ing
的移车次数小于m
*
的移车次数时，令 m
*
：＝m
ing
。
[0062]
s44、变异操作。对m
ing
的第一个时段配对e1进行如下操作。生成一个[0，1] 之间的随机数γ，如果β＞γ，则随机生成一个新的时段配对令否则，对后一个时段配对进行上述操作。
[0063]
s45、终止条件判断。如果m
ing
的移车次数为0或τ＝τ
max
，则输出m
*
并结束算法。否则，令τ：＝τ+1，转s43。
[0064]
上述仅为本发明的优选实施例而已，并不对本发明起到任何限制作用。任何所属技术领域的技术人员，在不脱离本发明的技术方案的范围内，对本发明揭露的技术方案和技术内容做任何形式的等同替换或修改等变动，均属未脱离本发明的技术方案的内容，仍属于本发明的保护范围之内。
技术特征：1.一种在avp条件下预约式共享停车供需匹配的自适应演化算法，其特征在于，包括如下步骤：s1：以共享停车需求时间与泊位供给时间的首末时刻为断点，分割共享停车供需时间；s2：在时段分割的基础上，将共享停车需求与供给泊位的关系定义为配对、时间配对、配对方案；s3：通过定义换位和连续换位，分析车辆在给定时段上进行泊位调整的条件和泊位调整对配对方案移车次数的影响，设计avp车辆在分割时段进行泊位调整的自适应优化策略，所述自适应优化策略包括如下步骤：s31：对任一时段i，确定车辆v在时段i和时段i+1停放的泊位p与q。s32：当p＝q，令i:＝i+1，回到s31，当p≠q，进入s33；s33：分别以i和i+1为起始时段，在泊位p与q上搜索停放车辆v的相邻时段，得到与v相关的配对构成的两个集合e
p
和e
q
；以q为目标泊位，确定连续换位s(e
p
,q)的成本变化量δc(s(e
p
,q))，同理确定δc(s(e
q
,p))；s34：如果δc(s(e
p
,q))≥max{0,δc(s(e
q
,p))}，则实施连续换位s(e
p
,q)；否则实施连续换位s(e
q
,p)，令i:＝i+1，回到s31；s4:在已知共享停车需求与泊位供给的前提下，结合上述自适应优化策略，引入变异操作，设计求解avp条件下预约式共享停车供需匹配的自适应算法。2.根据权利要求1所述的在avp条件下预约式共享停车供需匹配的自适应演化算法，其特征在于，所述s1中，所述分割共享停车供需时间的具体步骤为：s11：将所有共享停车供需时间的开始时刻和结束时刻放进集合t。s12：剔除集合t内相同的元素，并从大到小排列剩余元素；s13：以集合t内的元素为断点，将共享停车供需时间划分为多个时段。3.根据权利要求2所述的在avp条件下预约式共享停车供需匹配的自适应演化算法，其特征在于，所述步骤s3中，在连续换位s
i
→
i+m
的作用下，成本变化量δc(s
i
→
i+m
)的计算公式如下：其中，δc(s
i
→
i+m
)表示时段配对集合经过连续换位变为的成本变化量；表示未实施连续交换前，在其内部和与外部紧邻的其他时段配对之间由于车辆的移位产生的移车距离与移车惩罚性成本之和；表示连续换位后内部的移位距离与移车惩罚成本之和；和表示与外部的移车成本。4.根据权利要求3所述的在avp条件下预约式共享停车供需匹配的自适应演化算法，其特征在于，所述s4中，所述自适应优化算法包括如下步骤：
s41：设置最大迭代次数τ
max
、配对方案自适应优化一次的最大次数α、变异操作系数β以及当前迭代次数τ＝1；s42：随机生成时段配对e
i
,i∈{1,2,
…
,n}，将其合理组合成一个配对方案m
a
，将其作为当前配对方案m
ing
和最优配对方案m
*
；s43：通过上述自适应优化策略对m
ing
进行α次自适应优化得到[m
ing
]
α
，令当m
ing
的移车次数小于m
*
的移车次数时，令s44：对m
ing
的第一个时段配对e1进行如下操作：生成一个[0,1]之间的随机数γ，如果β>γ，则随机生成一个新的时段配对令否则，对后一个时段配对进行上述操作；s45：当m
ing
的移车次数为0或τ＝τ
max
，则输出m
*
并结束算法；当m
ing
的移车次数不为0或τ≠τ
max
，令τ：＝τ+1并回到s43。
技术总结本发明公开了一种AVP条件下预约式共享停车供需匹配的自适应演化算法，利用AVP车辆“空驾”特征，在共享停车需求的不同时段将车辆停放在不同泊位，以最少的AVP移位次数最大化满足共享停车需求，提高泊位利用率。具体包括以下步骤：在分割共享停车供需时间的基础上，定义配对、时段配对、配对方案概念；通过分析给定时段上车辆进行泊位调整的条件和泊位变化对于配对方案移车次数的影响，设计AVP车辆在所有时段上进行泊位调整的自适应优化策略；并通过引入变异操作避免自适应演化算法过早陷入局部最优，本发明设计了一个全新的算法，该算法求解中等规模的匹配问题时计算时间小于1秒，可用于实际的共享停车平台在线泊位分配。可用于实际的共享停车平台在线泊位分配。可用于实际的共享停车平台在线泊位分配。
技术研发人员：何胜学 崔允汀 张虎 梁士栋 袁鹏程
受保护的技术使用者：上海理工大学
技术研发日：2022.03.21
技术公布日：2022/7/5
