详情

原文传递合乘动态匹配多级筛选方法

专利名称：	合乘动态匹配多级筛选方法
摘要：	本发明涉及一种合乘动态匹配多级筛选方法，属于智能交通动态合乘自动匹配系统领域。本系统借助互联网或移动无线网络作为信息交互平台，经过注册的开车人和搭车人向提供搭乘信息服务的服务器发出查询请求并提供相应信息，由服务器进行动态搭乘信息网络构建及数据装载，并进行分级匹配处理，最后将搭乘组合匹配结果和搭乘路径发送回查询人。服务器是按如下步骤进行三级匹配处理：1)根据时间及绕行约束的一级优选；2)根据就近原则的二级优选；3)根据用户喜好的三级优选。该系统能够快速对搭乘双方进行匹配，得到满足条件的搭乘匹配组合及推荐的搭乘路径供用户选择。该系统能有效提高合乘效率，减少城市交通拥阻。
专利类型：	发明专利
申请人：	北京工业大学
发明人：	陈艳艳;王东柱
专利状态：	有效
申请日期：	2008-01-11T00:00:00+0800
发布日期：	2019-01-01T00:00:00+0800
申请号：	CN200810056015.4
公开号：	CN101216913
分类号：	G06Q10/00(2006.01)I
申请人地址：	100022北京市朝阳区平乐园100号
主权项：	1、合乘动态匹配多级筛选方法，其特征在于：本方法借助互联网或移动无线网络作为信息交互平台，开车人和搭车人向提供搭乘信息服务的服务器发出查询请求并提供相应信息，由服务器进行匹配处理，并将搭乘组合匹配结果和搭乘路径发送回查询人；服务器进行匹配处理时，以用户输入的实时信息及服务器上的地图信息为依据，根据搭乘点对相互间地理位置关系，通过多级的优化筛选过程来保证自动搭乘匹配组合的最优；本方法所用电子地图须包含以下路段属性信息：路段编号、路段名称、左右端节点坐标、路段长度，路段速度，路段类型；以及地址数据信息：地址编号，地址名称、与之对应的地址坐标信息和该地址的类型，数据库中通过地址名称得到该地址的坐标；动态匹配多级筛选的具体步骤如下： 1)注册开车人及搭车人向服务器发送“姓名、电话号码、家庭住址、常去地址”，并设置用户名及密码完成注册； 2)发出匹配请求当有合乘需求时，开车人或搭车人提交用户名及密码登陆服务器，发出匹配请求，并提供相关信息；搭车人和开车人的请求信息通过数据库形式存于服务器上；开车人发送匹配请求的信息包括：出行的起点地址和终点地址、开车人出发时间Ti、绕行距离约束；搭车人发送匹配请求的信息包括：出行的起点地址和终点地址、搭车人期望出发时间Tj、搭车人可接受的推前或推后时间约束T0；开车人绕行距离约束包括相对约束条件值Cc和绝对约束条件值Ce；其中，绝对约束条件值是绕行搭乘的绝对距离，以米或分钟为单位；相对约束条件值是实际绕行距离与自己起点终点的直接距离的比值； 3)动态装载搭乘信息网络将搭乘信息网络装入系统； 4)动态合乘匹配服务器用绕行路权优选、就近原则优选和最后用户挑选的三级优选的方法使用户得到最优的搭乘组合；具体步骤如下： (1)虚拟搭乘网络的构建服务器将开车人和搭车人的请求分别处理，建立搭乘网络及开车网络；所述的搭乘网络的构建方法是将系统中所有搭车人出行起点与该开车人出行起点相连，所有搭车人终点与该开车人终点相连；所述的开车网络的构建方法是将系统中所有开车人的起点与该搭车人的起点相连，所有开车人的终点与该搭车人的终点相连； (2)动态合乘组合分级筛选匹配算法；服务器对开车人的匹配请求和搭车人的匹配请求分别进行处理；服务器对开车人的匹配请求按如下步骤进行处理：步骤0：初始化及数据准备对任一开车请求点αi，起点记为i，终点记为i’，搭车请求点βj，起点为 j，终点为j’；假设系统中所有开车人的个数为N，所有搭车人的个数为M；步骤1，装载数据库中所有搭车人βj搭乘数据到内存，通过查询地图数据库，将搭车人的起点和终点的地址信息转换为平面坐标为：(xj，yj)、(xj’，yj’)；将开车人αi的起始地址和终点地址，通过查询地图数据库，转换为平面坐标(xi，yi)、(xi’，yi’)；步骤2：计算开车人起点αi经过搭车起点βj及搭车终点βj’(j，j’＝1，2...M) 到目的地αi’的绕行权重估计值；令Lii’为αi到αi’的直接距离估计，Lij为αi到βj的距离估计，Ljj’为βj到 βj’的距离估计，Lj’i’为βj’到αi’的距离估计，L’ii’为αi经βj到βj’到αi’的绕行距离估计；以Lij为例，其值用下式计算： Lij＝\|(xj-xi)\|+\|(yj-yi)\| Ljj’＝\|(xj’-xj)\|+\|(yj’-yi)\| Lj’i’＝\|(xi-xj’)\|+\|(yi’-yj’)\| 绕行权重估计值为： L’ii’＝Lij+Ljj’+Lj’i’ 步骤3：根据时间及绕行约束条件进行初级筛选；判断：\|Ti+Lij/V-Tj\|＜＝_T0 (1) Lij+Ljj’+Lj’i’＜Cc·Lii’ (2) \|Lij+ Ljj’+Lj’i’-Lii’\|＜Ce (3) 其中：Ti为开车人出发时间，V为αi到βj的平均车速，Tj为搭车人期望出发时间，T0为搭车人可接受的推前或推后时间；Cc为相对约束条件值，无量纲，1＜Cc≤1.5，Ce为绝对约束条件值，市区范围内，0公里＜Ce＜10公里；记录L’ii’值，将所有的同时满足(1)、(2)或同时满足(1)(3)条件的βj (j＝1，2...M)按L’ii’值从小到大的顺序排序，取前n个L’ii’较小值点，其中：n＝5～10)，放入一级合理点集U1；步骤4：根据就近搭乘原则进一步筛选最佳搭乘组合将U1点集中Lij＞L0的搭乘点删除，其中：L0为系统设定的开车人起点到搭车人起点的距离上限；并把剩余的搭乘点按Lij值由小到大的顺序，将排在前m(m＜n)个的搭乘点，放入二级合理点集U2；若剩余的搭乘点过少，则可取消此约束，或增加L0；步骤5：计算搭乘路径，根据用户选择进行三级筛选根据二级筛选后得到的搭乘匹配组合结果，即m对开车人和搭车人的起始点和终点信息，用A*或Dijkstra算法计算相应的实际搭乘最短路径及路长，供用户参考，并作最终选择； 5)匹配结果发布包括匹配成功的搭车人、开车人信息和路径的匹配结果通过网络发送给查询人，同时存入搭乘数据库作为存档；当服务器接收到的搭车请求时，与开车请求处理方法一样。
所属类别：	发明专利