(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210997798.6 (22)申请日 2022.08.19 (71)申请人 东北大学秦皇岛分校 地址 066004 河北省秦皇岛市经济技 术开 发区泰山路143号 (72)发明人 郭戈　孙天宇　高振宇　 (74)专利代理 机构 沈阳东大知识产权代理有限 公司 21109 专利代理师 李珉 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 50/06(2012.01) H02J 7/00(2006.01) (54)发明名称 一种基于排队理论的多等级充电与再平衡 联合调度方法 (57)摘要 本发明提供一种基于排队理论的多等级充 电与再平衡联合调度方法， 涉及 按需出行系统的 控制技术领域。 本发明结合多等级充电调度与基 于站点的再平衡策略解决充电延迟和系统失衡 问题， 并构建乘客等待队列和车辆充电队列， 提 出一种基于静态平衡的联合调度方案， 使系统达 到响应时间和运营成本最小化的目标。 其中构建 的按需出行系统的考虑充电规模的多等级充电 调度与基于站点的再平衡策略相结合联合调度 模型。 考虑了可充电客运站与独立充电站相结合 的模型。 同时， 将充电桩 数量作为优化变量， 给 予 最小充电桩的数量的同时以保证充电站服务的 效率。 权利要求书7页 说明书17页 附图7页 CN 115375132 A 2022.11.22 CN 115375132 A 1.一种基于排队理论的多等级充电与再平衡联合调度方法， 其特征在于， 包括以下步 骤： 步骤1、 根据车辆的荷电状态以及乘客行程距离将车辆和乘客分成K个等级； 根据车辆的剩余电量由低到 高将车辆进行分级， 根据乘客的行程距离由短到长将乘客 进行分级； 步骤2、 设计过低电量车辆， 即0级车充电机制， 以及其他车辆， 即k级车充电机制， k∈ {0,…,K}； 步骤3、 设计不需要 充电车辆的调度机制以及完成充电任务车辆的调度机制； 步骤4、 根据排队理论搭建充电队列模型， 推导队列稳定性条件； 步骤5： 设计车辆对乘客的服 务机制以及搭建服 务队列模型， 推导系统稳定性条件； 步骤6、 分析系统均衡状态， 设计基于站点的再平衡的联合调度策略， 建立多目标联合 调度问题的优化模型， 使系统最大响应时间T和运营成本 C最小化； 步骤7、 利用拉格朗日分析和KKT条件推导出多目标联合调度问题的优化模型的解析解 下界。 2.根据权利要求1所述的一种基于排队理论的多等级充电与再平衡联合调度方法， 其 特征在于， 步骤2中所述 k级车充电机制如下： 车辆完成上一个任务到达客运站后： 1)不充电直接服务乘客 2)在本站点进行部分 充电后服务于乘 客 3)去充电站部分充电后服务于乘 客 其中 表示k级车辆不 充电的概率， 表示k级车辆部分充电的概率， oi表示k级车辆在本站点充电的概率， 表 示k级车辆前往充电站m充电的概 率； 其中部分充电为车辆从k级 充电到k+1级； 所述0级车充电机制如下： 若到达车辆为过低电量的车： 1)在本站点进行全车充电后服务乘客 2)在本站点进 行部分充电后服 务乘客 3.根据权利要求1所述的一种基于排队理论的多等级充电与再平衡联合调度方法， 其 特征在于， 步骤3中所述不需要充电车辆的调度机制： 车辆完成上一个任务后： 1)留在该客 运站PS i， 为该客 运站乘客提供服务oi； 2)前往P S j站， 为j站 乘客提供服务 所述完成充电任务车辆的调度机制： 1)在本站点i完成充电任务的车辆则和上述不需 要充电车辆的调度机制相同； 2)在CS  m完成充电的车辆， 需要前往有需求的PS  j站为乘客 提供服务hmj。 4.根据权利要求1所述的一种基于排队理论的多等级充电与再平衡联合调度方法， 其 特征在于， 步骤4中所述搭建充电队列模型具体为： 客运站PS全车充电被建模为M/M/1/1队 列、 客运站PS部分充电被建模为M /M/ri/K队列， 充电站CS部分充电被建模为M /M/rm/K队列； 1)、 客运站PS充电： 载客户车辆到达PSi站的过程被建模 为泊松过程,预期速率为 则 PS i站的k级载客车辆达到率 表示为 其中pk代表到达系统的车辆电荷量状态属 于k级的概率， 不需要充电的车辆 需要在该客运站充电的k级车辆为 由于0级车辆没有多余的电量服务乘客以及前往附近充电站CS充电， 因此0权　利　要　求　书 1/7 页 2 CN 115375132 A 2级车辆只能在所到的客运站充电， 需要在该客运站充电的0级车辆为 其中 表示i站的0级载客车辆 达到率； 2)、 充电站CS充电： i站到达车辆选择去CSm充电的车辆 到达率 λim如下： 其中， N为客运站的集 合， i∈{1, …,N}， M为充电站的集 合， m∈{1, …,M}, 所述队列稳定性条件具体为： 每个充电点的车辆进站率必须小于其总服务率， 以避免 充电延迟； 1)客运站PSi站部分充电队列的稳定性条件： 其中p0代表到达车辆为0级车辆的概 率； 2)客运站PSi站完全充电队列的稳定性条件： μig为客运站PSi站充电桩提供的充电速率， ri为客运站PSi站充电桩的数量； 3)充电站CSm站充电队列稳定性条件： 其中rm为充电站m的充电桩数量， 为m站充电桩提供的充电速率。 5.根据权利要求1所述的一种基于排队理论的多等级充电与再平衡联合调度方法， 其 特征在于， 步骤5中所述车辆对乘客的服 务机制如下： 1)FCFS规则： 乘客队列被建模为M /M/1/K‑FCFS队列， 客户队列的第一 位优先分配车辆； 2)同级服 务和子集服 务： 完成充电的车辆或者 不进行充电的k级车辆以 的 概率为l级的乘客 提供服务， 其中k≥l； 所述服务队列模型如下： 客运站PSi站的k级可用车辆达到率λik包括客运站PSi站点本身的车辆λiak， 客运站PS  j 站再平衡到客 运站PSi站的车辆 以及充电站CSm站分配到i站的车辆 i站为k级顾客提供的服 务率 其中λid代表i站可用的d级车辆， 代表d级车辆为 k级乘客提供服务的概率； 所述系统稳定性包括 服务队列稳定性以及各站车流 量稳定性； 其中所述 服务队列的稳定性 为： 为乘客 提供的服 务率大于乘客到 达率：权　利　要　求　书 2/7 页 3 CN 115375132 A 3