本发明涉及一种基于轨迹数据的单向共享汽车系统选址优化方法。可以对现有共享汽车系统进行重新选址规划，也可以对新建城市进行共享汽车投放规划，为运营商的初始规划提供理论指导与实践支撑。具体实施方案是：对车辆轨迹数据进行分割，提取潜在共享汽车需求；对研究区域进行网格划分，统计每个网格的潜在需求量，选择候选点；计算需求中心到候选点的距离衰减程度；统计历史经验数据，得到车队规模限制约束，构建共享汽车站点选址优化模型；最后求解模型，得到站点位置、站点容量以及初始车辆。本发明使用的数据较为普遍，易于获得，能够在合理时间内得到具有可行性的选址方案，具有实际的操作价值。
一种基于轨迹数据的单向共享汽车系统选址优化方法
技术领域
[0001] 本发明涉及智能交通系统技术领域，特别涉及一种基于轨迹数据的单向共享汽车系统选址优化方法。
背景技术
[0002] 自第一辆汽车诞生以来，汽车行业快速发展，由此带动了经济的迅速发展，同时也带来了一系列的交通问题，主要表现为：交通堵塞、环境污染、停车困难、资源浪费等。各大城市都深受交通问题的困扰，交通压力的日益凸显，已经严重影响了城市活动的正常运行。共享汽车作为中国新兴的交通运输服务业，是满足人民群众个性化出行、商务活动需求和保障重大社会活动的重要交通方式，是综合运输体系的重要组成部分，对人们的出行及城市交通体系带来了有益影响。
[0003] 在移动互联网与物联网技术的发展和支持下，共享汽车(也称短时租赁)出行快速发展，并逐渐成为能够满足用户多样性出行需求的新的交通方式。目前，共享汽车系统主要有三种类型：双向共享汽车系统，单向共享汽车系统和自由停放系统。双向系统要求车辆必须在用户取车的站点还车；单向系统允许用户在共享汽车系统中任意站点还车，这两种类型都是基于站点式的系统，而自由停放系统类似于共享单车，没有固定的网点供用户借还车，用户可在可停车的任何地方停车。由于车辆和共享单车属性的不同，以及运营调度的难度较大，自由停放系统的应用较少，相关研究更是寥寥无几。绝大部分研究都是基于站点式的，尤其是应用广泛的单向共享汽车系统。在基于站点式的共享汽车系统中，站点的布局选址是一个关键问题。由于共享汽车系统前期投入的成本较大，营业网点一旦建设就很难再迁址，因此对共享汽车系统进行科学合理的规划布局显得尤为重要。对当前汽车共享系统的选址研究总结发现，基于数据驱动的选址方法，主要是对汽车共享系统的初始站点布局选址，而基于数学规划的优化方法更侧重于考虑后期运营状况的选址。良好的初始选址应能够尽量满足后期运营的状态，从而尽量减少后期因为站点调整产生的额外成本。基于此，本文结合两类方法，提出了一种基于数据驱动的优化选址方法，该方法基于实际数据，挖掘需求的时空分布，考虑需求距站点的距离衰减程度，以及后期运营过程中站点之间的租车往来，建立了混合线性整数规划模型。经过数据验证，本发明可以得到合理有效的选址方案，并且普适性和可行性较强。
发明内容
[0004] 本发明所要解决的技术问题：
[0005] 站点选址问题是单向共享汽车系统规划的一个重要方向，不合理的选址规划不仅给用户的出行带来不便，从而引起可不流失，还会给运营商带来巨大的经济损失。静态的选址问题是更符合实际需求的，但目前关于共享汽车选址的研究更多地是采用需求覆盖模型，没有考虑到共享汽车的特征。本发明提供了一种基于轨迹数据的单向共享汽车系统选址优化方法，可以对现有共享汽车系统进行重新选址规划，也可以对新建城市进行共享汽车投放规划，为运营商的初始规划提供一定的理论与实践支撑。
[0006] 为了实现上述目的，本发明提供了基于轨迹数据的单向共享汽车系统选址优化方法，包括以下步骤：
[0007] 步骤1：对车辆轨迹数据分割，提取共享汽车潜在出行需求；
[0008] 车辆轨迹数据是车辆行驶过程中的GPS轨迹点数据，是由一系列带时间戳的数据点组成的序列，每个数据点都包含车辆编号，时间，经度，纬度，速度等信息。
[0009] 步骤2：将研究区域按1km*1km的方格进行网格划分；根据潜在出行需求中的终点信息，统计每个区域的潜在出行到达量，根据潜在出行达到量的分布选择候选点；
[0010] 步骤3：统计候选点之间的出行需求、最短期望时间及站点之间租车量比例；
[0011] 步骤4：采用距离衰减函数，计算各个需求中心到各个候选点的距离衰减程度，所述需求中心为网格中心；
[0012] 步骤5：统计现有共享汽车系统的实际用车辆和实际满足的需求，对两者进行拟合。
[0013] 步骤6：基于共享汽车的短时租赁特征构建站点选址优化模型，模型以运营商的最小总成本为目标，约束条件则考虑基于距离衰减的需求覆盖、站点之间的租车往来、需求满足程度以及车队规模约束；
[0014] 步骤7：设置参数，代入已知数据，固定模型中的整数变量，采用改进Benders分解算法，进行模型求解。
[0015] 在上述方案的基础上，步骤1具体包括如下步骤：
[0016] 步骤1.1：将每一辆车的轨迹数据表示为：
[0017] Trii＝
[0018] {(vii,t1,lon1,lat1,speed1),(vii,t2,lon2,lat2,speed2),…(vii,tn,lonn,latn,speedn)} (1)
[0019] 其中，T表示该车辆的数据点数目，vii表示车辆ii的车辆编号，tn,n＝1,2,…,T,表示第n个数据点对应的时间戳，lonn,n＝1,2,…,T,表示时间tn时车辆所在位置对应的经度，latn,n＝1,2,…,T,表示时间tn时车辆所在位置对应的纬度，speedn,n＝1,2,…,T,表示时间tn时车辆的瞬时速度；
[0020] 判断某个数据点与其连续的下一个数据点的平均速度是否小于事先设定的速度阈值，如果是，标记为‑1，表示其是静止点，否则，标记为1，表示其为运动点，其运动状态表示为：
[0021] STri＝{s1,s2,…sn} (2)
[0022] 其中，sn,n＝1,2,…,T,表示第n个数据点对应的运动状态；
[0023] 步骤1.2：将步骤1.1得到的轨迹对应的运动状态划分为若干个静止段和运动段，静止段和运动段分别用‑1和1标记，表示为：
[0024] DTri＝{d1,d2,…,df,…dF} (3)
[0025] 步骤1.3：计算每个静止段的时间和每个运动段的距离，如果某个静止段的时间小于事先设定的时间阈值tthresh，即
[0026]
[0027] 其中，dk表示车辆的状态，f＝1,2,…,F，F表示状态段数；‑1表示静止段，1表示运动段， 为静止段f结束时间， 为静止段f开始时间，tthresh为设定的时间阈值。
[0028] 则将该静止段视为运动途中的短暂停留，并将其状态由静止改为运动。
[0029] 如果某个运动段的距离小于事先设定的距离阈值Dthresh，即
[0030]
[0031] 其中， 为运动段f结束时间， 为运动段f开始时间，Dthresh为设定的距离阈值。
[0032] 则将该运动段视为静止过程中的轻微挪动，并将其状态由运动改为静止；
[0033] 步骤1.4：将步骤1.3更改后运动状态相同且相邻的状态段进行合并，并提取每一个运动段的起、终点信息及时间和距离，组成需求信息。
[0034] 步骤1.5：根据参考信息对得到的需求信息进行对比分析，剔除不合理潜在需求，得到潜在出行需求。
[0035] 在上述方案的基础上，步骤1.1所述速度阈值为0.51m/s；
[0036] 步骤1.3所述时间阈值tthresh为120s,所述距离阈值Dthresh为200m；
[0037] 步骤1.5所述其他参考信息包括研究区域范围，最大、小出行时间，最长、短出行距离。
[0038] 在上述方案的基础上，步骤3具体包括如下步骤：
[0039] 步骤3.1：所述最短期望时间由候选点之间的距离、自由流速度计算；
[0040]
[0041] 其中，dik表示候选点i,k之间的最短距离，Vf表示道路交通的自由流速度；
[0042] 步骤3.2：统计候选点之间的出行需求。
[0043] 步骤3.3：站点之间租车量比例按候选点之间的出行需求比例计算得到,公式如下：
[0044]
[0045] 其中，qik为步骤3.2中计算的候选点i,k之间的潜在出行需求；
[0046] 在上述方案的基础上，步骤4所述的距离衰减函数如下：
[0047]
[0048] 其中，w1为待定参数，表示站点的最大服务半径，wtji为需求中心j到达候选点i的步行时间，sji为需求中心j到达候选点i的距离衰减程度；
[0049] 在上述方案的基础上，步骤5所述的拟合采用如下函数进行：
[0050] V≥βU+β0 (9)
[0051] 其中，V,U分别表示车队总规模大小及满足的需求量，β和β0为待定参数，可以根据实际需求进行标定；
[0052] 在上述方案的基础上，步骤6所述的站点选址优化模型如下：
[0053]
[0054]
[0055]
[0056]
[0057]
[0058]
[0059]
[0060]
[0061]
[0062] ∑j∑iDjzjisji≥β∑jDj (19)
[0063]
[0064]
[0065] f(V,U)≥0 (22)
[0066]
[0067]
[0068] 其中，I为候选点集合、J为需求中心集合、Cs,Cp,Cv,Ce分别为单位站点、停车位、和车辆的固定成本，以及单位时间内耗电成本；α,β,M,Pmax均为常数，分别为弹性系数、需求满足率，一个足够大的正整数和站点最大容量；Xi,Pi,Vi分别表示候选点i是否建站、停车位数，车辆数；zji表示需求区域j的需求被候选点i满足的比例；uik表示从候选点i到候选点k的租车量；Tik表示从候选点i到候选点k的最短期望时间；Dj为需求区域j的潜在需求量；
[0069] 公式(11)‑(14)表示站点的基本设施约束，公式(15)‑(19)表示基于距离衰减的需求满足约束，公式(20)‑(21)表示租车量约束，公式(22)中的f(V,U)表示车队规模与满足的需求之间的函数关系，即步骤5中的拟合函数，公式(23)、(24)表示模型中的变量约束，为此，公式(22)可替换为：
[0070] β∑i∑kuik+β0≤∑iVi (25)
[0071] 在上述方案的基础上，步骤7所述参数包括单位站点、停车位、和车辆的固定成本；所述已知数据包括需求区域j的潜在需求量Dj。
[0072] 本发明的有益效果：
[0073] 本发明基于车辆轨迹数据分割，挖掘潜在共享汽车出行需求。对现有共享汽车系统需求时空特征进行分析后，得到共享汽车车队规模与满足需求的函数关系。综合考虑基于距离衰减的需求空间覆盖、站点之间租车往来以及现有系统的经验，建立以运营商总成本最小为目标的选址模型。本发明可以给新建城市(无共享汽车)或现有共享汽车系统的重新规划选址提供一定的理论指导，且具有普适性。本发明主要基于车辆轨迹数据，易于获取，可以是共享汽车轨迹数据，也可以是其他车辆数据，经验数据可由其他共享系统获得，通过改进Benders算法能够快速得到合理的选址规划方案，获得选址地点、站点容量和初始车辆分配数量，且延伸性较好，实际操作性强。
附图说明
[0074] 本发明有如下附图：
[0075] 图1为本发明的基于轨迹数据的单向共享汽车系统选址优化方法的总体流程图。
[0076] 图2为本发明挖掘的潜在共享汽车出行需求。
[0077] 图3为本发明的研究区域及候选点分布。
[0078] 图4为本发明的衰减函数变化曲线。
[0079] 图5为需求满足率为0.7时的求解结果
具体实施方式
[0080] 以下结合附图1～5对本发明作进一步详细说明。
[0081] 本发明是一种基于轨迹数据的单向共享汽车系统选址优化，包括以下步骤，如图1所示：
[0082] 步骤1：对车辆轨迹数据分割，提取共享汽车潜在需求。车辆轨迹数据隐含了用户的潜在出行需求，将车辆轨迹数据按照一定的方法进行合理的分割可以得到有效的潜在需求集。车辆轨迹数据是车辆行驶过程中的GPS轨迹点数据，是由一系列带时间戳的数据点组成的序列，每个数据点都包含车辆编号，时间，经度，纬度，速度等信息。如图2所示；
[0083] 步骤1.1：将每一辆车的轨迹数据表示为：
[0084] Trii＝
[0085] {(vii,t1,lon1,lat1,speed1),(vii,t2,lon2,lat2,speed2),…(vii,tn,lonn,latn,speedn)} (1)
[0086] 其中，T表示该车辆的数据点数目，vii表示车辆ii的车辆编号，tn,n＝1,2,…,T,表示第n个数据点对应的时间戳，lonn,n＝1,2,…,T,表示时间tn时车辆所在位置对应的经度，latn,n＝1,2,…,T,表示时间tn时车辆所在位置对应的纬度，speedn,n＝1,2,…,T,表示时间tn时车辆的瞬时速度；
[0087] 判断某个数据点与其连续的下一个数据点的平均速度是否小于事先设定的速度阈值,所述速度阈值为0.51m/s，如果是，标记为‑1，表示其是静止点，否则，标记为1，表示其为运动点，其运动状态表示为：
[0088] STri＝{s1,s2,…sn} (2)
[0089] 其中，sn,n＝1,2,…,T,表示第n个数据点对应的运动状态；
[0090] 步骤1.2：将步骤1.1得到的轨迹对应的运动状态划分为若干个静止段和运动段，静止段和运动段分别用‑1和1标记，表示为：
[0091] DTri＝{d1,d2,…,df,…dF} (3)
[0092] 步骤1.3：计算每个静止段的时间和每个运动段的距离，如果某个静止段的时间小于事先设定的时间阈值tthresh，所述时间阈值tthresh为120s,即
[0093]
[0094] 其中，df表示车辆的状态，f＝1,2,…,F，F表示状态段数；‑1表示静止段，1表示运动段， 为静止段f结束时间， 为静止段f开始时间，tthresh为设定的时间阈值。
[0095] 则将该静止段视为运动途中的短暂停留，并将其状态由静止改为运动。
[0096] 如果某个运动段的距离小于事先设定的距离阈值Dthresh，所述距离阈值Dthresh为200m,即
[0097]
[0098] 其中， 为运动段f结束时间， 为运动段f开始时间，Dthresh为设定的距离阈值。
[0099] 则将该运动段视为静止过程中的轻微挪动，并将其状态由运动改为静止；
[0100] 步骤1.4：将步骤1.3更改后运动状态相同且相邻的状态段进行合并，并提取每一个运动段的起、终点信息及时间和距离，组成需求信息。
[0101] 步骤1.5：根据参考信息对得到的需求信息进行对比分析，所述其他参考信息包括研究区域范围，最大、小出行时间，最长、短出行距离，剔除不合理潜在需求，得到潜在出行需求。
[0102] 步骤2：将研究区域按1km*1km的方格进行网格划分，根据潜在出行需求中的终点信息，统计每个网格的潜在出行到达量，根据潜在出行达到量的分布选择候选点(候选点的空间分布如图3中的灰色圆点所示)；
[0103] 步骤3：统计候选点之间的潜在出行需求、最短期望时间及站点之间租车量比例；
[0104] 步骤3.1：所述最短期望时间由候选点之间的距离、自由流速度计算；
[0105]
[0106] 其中，dik表示候选点i,k之间的最短距离，Vf表示道路交通的自由流速度；
[0107] 步骤3.2：统计候选点之间的出行需求，即OD需求量。考虑用户的就近选择行为，例如潜在需求d的起点为O，终点为D，离起点O最近的候选点为lnear，离终点D最近的候选点为mnear，则将需求d计入候选点lnear,mnear之间的OD需求；
[0108] 步骤3.3：站点之间租车量比例按候选点之间的OD需求比例计算，所述OD需求比例是依据步骤3.2统计的候选点之间的出行需求计算得到,公式如下：
[0109]
[0110] 其中，qik为步骤3.2中计算的候选点i,k之间的潜在出行需求；
[0111] 步骤4：采用如下距离衰减函数，计算各个需求中心到各个候选点的距离衰减程度，所述需求中心为网格中心，也可根据实际设为网格内需求点分布的重心，衰减函数变化曲线如图4所示；
[0112]
[0113] 其中，w1为待定参数，表示站点的最大服务半径，wtji为需求中心j到达候选点i的步行时间，sji为需求中心j到达候选点i的距离衰减程度；
[0114] 步骤5：统计现有共享汽车系统的实际用车辆和实际满足的需求，对两者进行拟合，拟合函数作为选址模型中的车队规模限制约束，新建城市可参考类似城市的共享汽车系统；拟合函数采用如下所示：
[0115] V≥βU+β0 (9)
[0116] 其中，V,U分别表示车队总规模大小及满足的需求量，β和β0为待定参数，可以根据实际需求进行标定；
[0117] 步骤6：基于共享汽车的短时租赁特征，以运营商的最小总成本为目标，目标函数考虑站点建站成本、停车位成本，车辆固定成本以及能耗成本，约束考虑基于距离衰减的需求覆盖、站点之间的租车往来、需求满足程度以及车队规模约束，构建站点选址优化模型如下：
[0118]
[0119]
[0120]
[0121]
[0122]
[0123]
[0124]
[0125]
[0126]
[0127] ∑j∑iDjzjisji≥β∑jDj (19)
[0128]
[0129]
[0130] f(V,U)≥0 (22)
[0131]
[0132]
[0133] 其中，I为候选点集合、J为需求中心集合、Cs,Cp,Cv,Ce分别为单位站点、停车位、和车辆的固定成本，以及单位时间内耗电成本；α,β,M,Pmax均为常数，分别为弹性系数、需求满足率，一个足够大的正整数和站点最大容量；Xi,Pi,Vi分别表示候选点i是否建站、停车位数，车辆数；zji表示需求区域j的需求被候选点i满足的比例；uik表示从候选点i到候选点k的租车量；Tik表示从候选点i到候选点k的最短期望时间；Dj为需求区域j的潜在需求量；
[0134] 公式(11)‑(14)表示站点的基本设施约束，公式(15)‑(19)表示基于距离衰减的需求满足约束，公式(20)‑(21)表示租车量约束，公式(22)中的f(V,U)表示车队规模与满足的需求之间的函数关系，即步骤5中的拟合函数，公式(23)、(24)表示模型中的变量约束，为此，公式(22)可替换为：
[0135] β∑i∑kuik+β0≤∑iVi (25)
[0136] 步骤7：设置单位站点、停车位、和车辆等成本参数，代入需求区域j的潜在需求量Dj等数据，采用改进的Benders分解算法，进行模型求解。求解结果示例如图4所示。
[0137] 本说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。
