(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211069012.0 (22)申请日 2022.09.02 (71)申请人 北京化工大 学 地址 100029 北京市朝阳区北三环东路15 号 (72)发明人 李想　赵雨薇　冯紫嫣　 (74)专利代理 机构 北京圣州专利代理事务所 (普通合伙) 11818 专利代理师 王杰 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/04(2012.01) G06Q 10/02(2012.01) G06Q 50/26(2012.01) G06Q 50/30(2012.01) (54)发明名称 多车型定制公交运营优化方法 (57)摘要 本发明涉及城市公共交通领域， 公开了一种 多车型定制公交运营优化方法， 包括： 获取定制 公交预约信息； 根据预约信息， 确定多车型定制 公交车队配置和路径优化的目标函数与约束条 件， 其中， 目标函数是最小化运营成本和超时惩 罚成本， 约束条件包括： 所有的乘客都需要被服 务、 车辆服务里程和服务时间限制、 每种类型车 辆的数量限制和乘客时间窗限制； 根据目标函数 和约束条件， 建立混合整数非线性规划模型； 对 混合整数非线性规划模型进行处理， 得到异构车 队配置、 定制公交路线和时刻 表以及订单指派方 案。 从而解决了现有技术无法解决的多车型定制 公交系统运营优化问题， 而且有利于企业降低运 营成本。 权利要求书6页 说明书17页 附图2页 CN 115409388 A 2022.11.29 CN 115409388 A 1.一种多车 型定制公交运营优化方法， 其特 征在于， 包括： 获取定制公交预约信 息； 所述预约信 息包括上车站点、 下车站点、 期望上车时间和期望 下车时间； 根据所述预约信息， 确定多车型定制公交车队配置和路径优化的目标函数与约束条 件， 其中， 所述目标函数是最小化运营成本和超时惩罚成本， 所述约束条件包括： 所有的乘 客都需要被服务、 车辆服务里程和 服务时间限制、 每种类型车辆的数量限制和乘客时间窗 限制； 根据所述目标函数和约束条件， 建立混合整数非线性 规划模型； 对所述混合整数非线性规划模型进行处理， 得到异构车队配置、 定制 公交路线和时刻 表以及订单指派方案 。 2.根据权利要求1所述的多车型定制公交运营优化方法， 所述对所述混合整数非线性 规划模型进 行处理， 得到异构车队配置、 定制公交路线和时刻表以及订单指派方案， 具体包 括： 将所述混合整数非线性规划模型中的非线性目标进行线性化处理， 得到混合整数线性 规划模型， 所述非线性目标包括 运营成本和超时惩罚成本； 使用Dantzig ‑Wolfe(D‑W)分解所述混合整数线性规划模型进行分解重构， 引入新的变 量， 得到限制主问题模型和子问题模型； 采用Cplex求解器求解小规模子问题， 采用启发式算法求解大规模子问题， 优化异构车 队配置、 定制公交路线和时刻表以及订单指派方案 。 3.根据权利要求1所述的多车型定制公交运营优化方法， 所述混合整数非线性规划模 型包括： 目标函数及所述目标函数的约束条件， 具体包括： 所述目标函数如下述公式： min CS＝CF+CO+CP,     (1) 其中， 固定运营成本 CF取决于使用了多少辆车， 表述 为： 可变运营成本 CO取决于车辆类型及线路长度， 表述 为： 惩罚成本 CP定义为超出乘客r可接受的最晚到 达时间的惩罚成本， 表述 为： 所述约束条件如下述公式(5)～(27)所示： 权　利　要　求　书 1/6 页 2 CN 115409388 A 2xkii＝0,k∈K,i∈N                         (8) ATkj≤ATki+HTki+tij+Z(1‑xkij),k∈K,i,j∈V                (9) ATkj≥ATki+HTki+tij‑Z(1‑xkij),k∈K,i,j∈V                (10) ATkd(r)≥ATko(r)‑Z(1‑αrk),k∈K,r∈R                  (11) ATko(r)≤(EDTr+tmax)αrk+Z(1‑αrk),r∈R,k∈K               (16) (EDTr‑tmax)αrk≤ATko(r)+HTko(r),r∈R,k∈K                (17) zka‑Z(1‑xksi)≤zki,i∈N,k∈K                    (20) zka+Z(1‑xksi)≥zki,i∈N,k∈K                    (21) zks＝0,k∈K                         (24) xkij,ymk, αrk∈{0,1}； ATki,HTki,zki≥0,k∈K,i,j∈V,r∈R,m∈M          (27) 其中， 公式(1)～公式(27)所用数 学符号的含义如下： N： 候选站点 集合， i∈N； s,t： 虚拟起 点和终点的索引； V： 所有节点的集 合， 包括候选站和虚拟节点， 即： N∪{s,t}； M： 定制公交的类型， m∈M； K： 车辆集 合， k∈K； R： 订单集 合， r∈R； capm： m型车辆的容 量， 即座位数， m∈M； dij： 站点i和站点j之间的距离， i,j∈V；权　利　要　求　书 2/6 页 3 CN 115409388 A 3