(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111528669.4 (22)申请日 2021.12.14 (71)申请人 武汉理工大 学 地址 430070 湖北省武汉市洪山区珞狮路 122号 (72)发明人 石兵　朱李全　李顺　李帅　 潘玉婷　鲁艳　 (74)专利代理 机构 武汉科皓知识产权代理事务 所(特殊普通 合伙) 42222 代理人 肖明洲 (51)Int.Cl. G06Q 30/02(2012.01) G06Q 10/04(2012.01) G06Q 10/06(2012.01) G06Q 50/30(2012.01) (54)发明名称 一种基于次价定价机制的预约拼车出行系 统及方法 (57)摘要 本发明公开了一种基于次价定价机制的预 约拼车出行系统及方法， 使用机制设计的思想和 方式完成预约拼车出行中的订单分配、 路径规划 和司机定价， 在共享出行的大环境中， 提高司机 的参与度和订单分配率， 最大化拼车平台和司机 的社会福利。 使用次价定价离线机制解决预约拼 车出行中的订单分配、 路径规划和司机定价问 题， 在系统中使用一个中间的决策单元来完成相 应任务； 系统根据订单信息和司机信息使用次价 定价离线机制来帮助平台完成订单分配， 给获得 订单的司机提供相应的行车安排规划， 并计算司 机完成订单后的报酬； 建成一个在线的预约拼车 出行系统， 使得社会福利最大化， 使得乘客能在 更短时间内获得服务， 使 得司机能真实地提供其 成本信息， 并提高其 参与率和收益。 权利要求书3页 说明书8页 附图3页 CN 114331502 A 2022.04.12 CN 114331502 A 1.一种基于次价定价机制的预约 拼车出行系统， 其特征在于： 包括订单信 息获取单元、 司机信息获取 单元、 信息服 务单元、 决策单元和执行单元； 所述订单信息获取单元， 用以获取乘客的出行需求和出行约束， 并预先计算乘客需要 支付的出 行费用； 所述司机信息获取 单元， 用以获取司机提供的服 务信息； 所述信息服 务单元， 用以记录并管理预约拼车 出行系统获取到的订单和司机信息； 所述决策单元， 用以根据所述订单信 息获取单元和所述司机信 息获取单元获取的信 息 去决定订单分配方案， 规划司机 接送乘客的行 车安排， 以及计算司机 完成订单之后的报酬； 所述执行单元， 用以给成功分配的司机与乘客发送相应的信 息,并在司机完成服务后， 收取乘客预 先计算的出 行费用和支付司机之前计算的报酬。 2.一种基于次价定价机制的预约拼车 出行方法， 其特 征在于， 包括以下步骤： 步骤1： 司机和乘客 通过互联网注 册预约拼车 出行系统； 步骤2： 预约拼车 出行系统对司机和乘客的身份进行确认； 步骤3： 司机信息获取 单元获取司机提供的服 务信息； 步骤4： 将步骤3中的信息传输 到信息服 务单元， 等待预约拼车 出行系统决策； 步骤5： 订单信息获取 单元获取乘客 提供的服 务请求； 步骤6： 将步骤5中的信息传输 到信息服 务单元； 步骤7： 决策单元根据获取到的订单信 息和司机信息进行订单分配， 规划司机接送乘客 的行车安排， 以及计算司机 完成订单之后的报酬； 其中采用基于次价定价的离线机制进行订单分配、 规划司机接送乘客的行车安排以及 计算司机 完成订单之后的报酬， 具体实现包括以下子步骤： 步骤7.1： 根据订单的出行费用对其进行排序， 当出行 费用一样时按照出发时间先后顺 序排序； 步骤7.2： 将订单依次取 出， 开始这 一轮的订单分配； 步骤7.3： 根据订单的起始位置和司机已有行 车规划， 为司机 重新规划行车规划； 步骤7.4： 根据新的行车规划求解司机对应的额外行车成本， 寻找额外行车成本最优的 司机d*； 步骤7.5： 暂时性地删除当前额外行车成本最优的司机， 从剩下的司机 中寻找额外行车 成本最优的司机d ′； 步骤7.6： 根据额外行 车成本须小于订单的出 行费用判断司机d*和d′是否存在； 若不存在， 则回转执 行步骤7.2； 若存在， 则执 行步骤7.7； 步骤7.7： 将订单分配给司机d*， 并更新司机d ′的行车规划； 步骤7.8： 根据司机d ′的额外成本来计算司机d*完成该订单 的报酬， 并更新司机d*的总 的报酬； 步骤7.9： 回转执 行步骤7.2， 直至最后一个订单； 步骤8： 判别订单分配是否成功； 若是， 则将成功分配的信息传输 至执行单元， 并顺序执 行步骤9； 若否， 则将为成功分配的订单信息和司机信息回送至信息服务单元， 并回转执行步骤权　利　要　求　书 1/3 页 2 CN 114331502 A 27； 步骤9： 给成功分配的司 机与乘客发送相应的信息， 司机在完成接送之后， 乘客支付预 先计算好的出行费用， 司机获得相应的报酬， 本次预约拼车 出行结束。 3.根据权利要求2所述的基于次价定价机制的预约拼车出行方法， 其特征在于： 步骤3 中所述的司机提供的服务信息包括司机行车 的出发地和目的地、 行车时间窗口、 单位里程 的拼车出行服务需要付出 的成本、 车辆最多可以容纳的乘客数目、 车辆的实时位置和系统 分配给司机的订单集 合。 4.根据权利要求2所述的基于次价定价机制的预约拼车出行方法， 其特征在于： 步骤5 中所述的乘客提供的服务请求包括订单 的出发地和目的地、 订单最早离开出发地的时间、 订单中的乘客数目、 订单的出 行约束和订单的预估出 行费用。 5.根据权利要求2所述的基于次价定价机制的预约拼车出行方法， 其特征在于： 步骤 7.1中， 在预约拼车出行下， 预约拼车出行系统在分配订单之前， 获得了所有订单和司机的 信息； 此时， 所有订单都以预约的形式进入预约拼车出行系统， 司机也提前将自己的私有信 息提交给 预约拼车 出行系统。 6.根据权利要求2所述的基于次价定价机制的预约拼车出行方法， 其特征在于： 步骤 7 .3中， 司机的行车安排tpd表示为一个有序节点序列： 其中， 是分配给司机d的订单的出发地或目的地， 即 为订单o的出发地， 为订单o的目的地， 为平台分配给司机d的订单集合， |tpd|表示是节 点序列的长度， 即 司机d在线下服务乘客的时候， 会按照tpd的节点顺序行车； 在预约拼车出行下， 预约拼 车出行系统会在司机服务乘客的过程中动态调整tpd， 使得司机可以完成新分配的订单； 预 约拼车出行系统以最小化司机的行驶里程 为目标给司机规划行 车安排； 使用disd(tpd)表示司机d在位置ld上按照行车安排tpd行车的行驶里程， 其计算公式为 函数dis(·,·)表示司机从一个节点到另一个节 点的里程开销； 用 表示订单 在行车安排tpd下的实际绕路比， 其计算公式为 函数 表示在行车安排tpd上的任意两个节点之间 的实际行驶里程； 在订单分配之时， 预约拼车出行系统通过订单信息和司机的私有信息， 给出全局的订 单分配方案； 司机d在获得了预约拼车出行系统分配给自己的订单集合 之后， 司机d会线 下按照平台规划的行 车安排tpd行车， 完成分配给自己的订单； 司机d在行 车接送乘客的过程中产生的行 车成本为： costd(tpd)＝cd·disd(tpd)               (1) cd表示司机d提供 单位里程的拼车 出行服务需要付出的成本； 司机的利 润为： ud＝pd‑costd(tpd)                       (2) pd表示预约拼车系统支付给司机d的报酬；权　利　要　求　书 2/3 页 3 CN 114331502 A 3