基于时间窗与优先级的网络共享停车匹配模型*

路 扬 何胜学 王冬冬 高 蕾

(上海理工大学管理学院 上海 200093)

0 引 言

近些年随着国内机动车保有量的不断攀升，泊位争抢日益激烈，现有的停车泊位数量已无法满足人们的停车需求，且在城市中心区域尤为突出[1].面对巨大的城市停车压力，可以从两方面解决停车问题：提高泊位的绝对数量，即建设大量停车设施，增设停车泊位；提升泊位利用效率，如共享停车.而共享停车相比停车场建设更经济、更科学，因此，以停车挑战为动力，借鉴现有的共享经济理念，通过泊位共享手段可以从一个新的角度来处理停车问题.

现阶段共享停车还处于探索阶段，不少专家学者也从各个方面对其展开研究，期望通过停车时间的互补，以解决长期共享停车用户为核心，充分发挥停车资源的潜在利用价值[2].姚恩建等[3]对共享停车的时间约束及分配原则做出了透彻的分析，对图着色模型进行改进并建立了共享泊位资源优化配置模型，有效地解决待停车辆的最优泊位匹配问题，然而在网络调配层面阐述较少.段满珍等[4-5]发现居民区与其他类型场所停车使用上有一定的互补性，对居民区泊位时间特性进行详细研究，并通过建立双层规划模型解决停车分配不均衡问题，但对于匹配的时间约束问题没有进行分析研究.类似的双层规划模型也被许多学者改进，陈峻等[6]利用双层模型应用到对高校停车场的出租共享分配问题上，分析了多种泊位使用情形，同时考虑高校停车泊位无法满足停车需求时的解决方案，同时对共享停车的需求进行分类，确定不同停车目的的停车行为影响因素，建立两种停车行为选择模型[7].Xiao等[8]在共享停车收费问题的研究中，利用投标手段确定支付规则，但没有明确考虑到停车泊位的空间特性及需求车辆与泊位之间的距离问题.目前对于网络共享停车匹配的研究大都以停车场开放泊位数为研究对象[9]，未考虑共享泊位匹配有着严格的时间约束限制[10-11]，具有一定的局限性，因此,以停车场停车泊位为研究对象有着巨大的研究潜力[12].

文中设计了网络共享停车匹配优化系统，并建立了整数非线性规划模型(INLP).模型综合考虑了需求车辆的优先级、泊位周转时间，以及时间窗冲突问题，同时对整个停车网络的不同供需情形进行分析，使匹配效果更科学、更合理.

1 共享停车问题描述

1.1 共享停车系统

共享停车是指利用停车泊位供需双方的错峰使用特性，将某些时段停车场闲置的空余泊位共享对外出租，通过移动终端APP、网络平台为驾驶员匹配合理的停车泊位，以提高寻车效率及停车场停车泊位利用率.对于司机而言，可以通过共享停车系统快速寻找到目的地周围停车泊位，解决停车问题；对于整个系统而言，高效的寻车效率可以减少城市道路中因寻找车位而产生的无效交通流，保证道路通畅，合理的停车匹配可以提高整个共享停车场的利用率，将城市中有限的停车资源利用最大化.本文针对网络共享停车场的共享停车匹配进行研究，见图1.

图1 共享停车网络匹配流程图

对于每一停车泊位sj，上传系统的信息包括：泊位开放时刻oj、关闭时刻cj、泊位所属停车场ph，以及其位置坐标(xsj,ysj).泊位预约用户di信息向系统平台发送停车请求同时，会提供其出发位置(xdi,ydi) 、出发时间bi、预测到达目的地的行驶时间ti、离开共享停车场的最晚离开时间li.系统接受共享停车的各类数据进行整理，建立相应的系统时间窗，并可以实时更新时间窗、需求车辆总数D、共享泊位总数S等相关数据.将整理后的数据利用共享停车匹配系统确定最优匹配组合，向用户提供泊位所属停车场、停车场位置，待用户确认并到达后完成匹配，并对系统时间窗进行更新.系统还对不同使用频率的用户进行了分类，将需求车辆分为长期用户与临时用户，并设置了优先级系数αi，对短期用户αi设为1，长期用户αi取1.5.通过匹配优先系数的设置，实现长期用户的优先匹配[13].

1.2 基本假设

网络共享停车匹配优化模型在泊位分配过程中遵循以下基本假设：①所有预约车辆到达某处的行驶时间与空间直线距离成比例且相等；②预约用户离开共享泊位的时间固定且已知；③可对车辆到达目的地的行驶时长进行预测.

2 共享停车网络匹配模型

2.1 目标函数的建立

为体现分配结果的合理性及科学性，建立了以δdisj为核心的网络共享供需匹配数学优化模型，对预约停车车辆进行分配.同时对两种不同情形的供需数量关系进行针对性研究，建立了两种相应的目标函数，并考虑到优先匹配问题，力求保证优先级较高的长期预约用户优先获得车位，构建城市共享停车供需匹配优化模型目标函数为

maxZ1=∑D∑Sαi·δdisj·πdi

(1)

maxZ2=∑D∑Sαi·

(2)

当网络区域内的共享泊位处于供不应求状态下，为了使停车资源得到充分利用建立了目标函数.式(1)表示最大化共享泊位出租时长同时兼顾优先级较高的预约用户享有优先获得泊位的权益.其中δdisj为匹配关系变量，表示需求车辆di与供给泊位sj是否匹配成功，当δdisj=1时，需求di与供给sj匹配成功，若未匹配成功，则δdisj=0.

式(2)表示当供给泊位非常充足的情况下，所有车辆均能获得泊位，因此,优先考虑所匹配得泊位与目的地的距离最近，为用户优先选择距离最短的停车场.通过两种目标函数，为不同情形选择合理方案，使模型更具针对性.

2.2 约束条件的建立

(3)

式(3)表示匹配的共享泊位须在需求车辆di的目的地Di的可行范围内，Q为共享单车范围最大距离，可根据城市规模或具体情况进行调整.

(4)

li≤cj

(5)

式(4)～(5)构成了停车匹配过程最基本的时间约束限制，停车需求车辆的停放时段需要处在共享时间窗范围内[14-15].式(4)表示车辆di到达共享停车场ph时泊位sj已经开放共享.需求di匹配过程中，考虑到司机与待选停车场的距离均不相同，需根据已知到达停车场的时间估算出车辆到达不同停车场的时间，与相应共享停车场内的共享泊位开放时间窗比较.方便起见，假设所有单位时间内行驶的空间直线距离相同，实际预测中有更为准确的预测数值，因此，可根据距离估算出到达各共享停车场的行驶时间.式(5)用于表示对车辆的离开时间进行限制，要求车辆在泊位关闭开放之前离开.

∑Sδdisj≤1 ∀D

(6)

(lm-an+k)·(ln-am+k)≤0

(7)

任何车辆使用共享泊位上的一个前提是泊位处于空闲状态，式(6)表示每一个泊位同一时刻只能服务至多一个共享停车用户.k表示预留的泊位准备时间或周转时间，通常取值为5 min.式(7)避免匹配到同一泊位的任意两辆车辆产生时间上的冲突.对于任意一个停车泊位，存在同一共享开放时段内服务多辆需求车辆，但由于停车匹配有着严格的时间约束限制，所有已经匹配的车辆在时间上均不会出现交集.即对于同一泊位、同一共享时段的所有车辆来说，无论车辆数量多少，两两之间时间均不会产生冲突.

(8)

(9)

(10)

(11)

(12)

(13)

3 案例分析

3.1 算例介绍

文中设计了一个简单的网络共享停车匹配系统来检验模型的分配效果.算例网络见图2，针对共享泊位供不应求的情形下进行了模拟仿真，系统共设置了设有3个共享停车场，5个共享泊位以及10个泊位预约车辆，需求车辆各自开往A，B，C，D四个不同的目的地.示意图中的位置坐标以A为参考原点，需求车辆分布在网络的不同方位，对所有车辆、目的地及共享停车场设置坐标，结合其他数据整理得到表1～2.假设车辆单位时间行驶2.9个距离步长，如由d5坐标(-78.6，82.5)及其目的地C的坐标(24.0,-50.0)计算出二者空间直线距离为102.78个距离步长，进而可知行驶时间为35分钟.通过表1发现d2，d4，d6，d8分别为长期预约用户，四者优先级系数为1.5，享有优先匹配车位的权利.在停车需求数据表格中发现，d3与d6，d8，d2与d9的停放时间窗类似，存在泊位竞争关系.值得注意的，由于各停车场及目的地位置方位均匀较大差距，表中的出发时间不等于车辆的到达时间，车辆预测到达不同停车场的时间不同，算例程序会假想车辆到达不同停车场的情况，对各情况分析比较，在满足一定用户的优先匹配前提下，保证系统最优.

除d7外，其余车辆目的地范围内均有两个共享停车场、多个泊位供选择.如预测d10到达目的地的时间，由此估算d10到达p2、p3的时间.这样可以更精确地为系统提供匹配参考，对于两个同一时间开放的泊位来说，可能失去了预约距离较近泊位的机会，但是同样也可以匹配到距离允许范围内的泊位，提高了系统的匹配成功率.

图2 网络供需分布示意图

表1 预约用户预约数据表

表2 共享泊位开放数据表

3.2 算例匹配结果及分析

网络共享泊位分配成功的必要条件要求泊位共享时间窗与所匹配到的车辆停放时间没有冲突，且该泊位处于车辆目的地一定的距离范围内.鉴于这两点对所有泊位进行逐个分析，确定所有满足匹配成功两个基本条件的匹配组合，见图3.以s2为例，其泊位共享时间窗为(09：30，18：00)，共享时长为8 h 30 min，d1，d5，d4，d7，d10均在其时间窗范围内，但s2所属停车场p1均不在d4，d5，d10的目的地允许距离范围内，因此仅d1及d7可与s2建立匹配关系.

图3 共享泊位匹配关系示意图

系统对所有可能的结果进行分析比对，最终得到最优的匹配结果，见图4.由图4发现，10个预约用户有八个成功匹配到合适的泊位，泊位出租总时长为，泊位利用率为.虽有两辆需求车辆未匹配成功，但是所有长期预约用户均成功，如d6预测到达停车场p2的时间为8：30，停放时长为3 h 50 min,若将d3分配到p2预测到达时间为08：07，停放时长4 h 13 min可停放至泊位s1，且停放时间长于d6，但由于d6进行了长期预约，因此系统放弃了一定的利用效率，对d6进行了优先匹配.d8预测到达停车场p1的时间为08:27，停放时长为3 h 23 min.

图4 共享泊位匹配结果示意图

由结果数据表明，所提出的匹配优化模型是可行的.

1) 模型可以较好地实现优先级较高的用户泊位匹配.

2) 考虑优先级的匹配匹配结果与以泊位利用率为目标函数的匹配结果有一定差距.

3) 通过算例发现，经模型优化后的分配效果可以较好地利用共享停车资源.

4 结 束 语

研究网络区域内的共享停车匹配系统，建立了考虑优先级的网络共享停车匹配优化模型.模型对匹配的时间窗约束问题、距离问题及优先级问题做出了描述，对不同情形的供需情况进行分析.通过整数规划逻辑判断理论对模型的改进，使得运行效率更加高效、准确.算例结果表明：模型既能保证泊位总体利用效率的最大化又能兼顾匹配的优先级，模型匹配效果较为理想.同时在未来研究中，会综合考虑以下要素：①考虑到需求车辆的反馈问题；②优化行驶路径及行驶时间预测；③对共享停车分配的网络均衡性做出进一步研究.