(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202210953233.8 (22)申请日 2022.08.10 (65)同一申请的已公布的文献号 申请公布号 CN 115034522 A (43)申请公布日 2022.09.09 (73)专利权人 深圳市四格互联信息技 术有限公 司 地址 518000 广东省深圳市南 山区粤海街 道滨海社区海天一路11号、 13号、 15 号、 海天二路14号、 海天二路16号软件 产业基地5 栋4层419室 (72)发明人 吴立辉　王雄　但志平　鲍海　 (74)专利代理 机构 深圳市壹 壹壹知识产权代理 事务所(普通 合伙) 44521 专利代理师 库水龙(51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/06(2012.01) G06Q 10/10(2012.01) G06Q 50/30(2012.01) G06K 9/62(2022.01) G06N 3/00(2006.01) (56)对比文件 CN 113450242 A,2021.09.28 CN 114240002 A,202 2.03.25 沈于蓝等.企业班车 管理系统的设计与实 现. 《福建电脑》 .2018,(第01期),第54- 55页. 审查员 罗湘 (54)发明名称 基于员工下班时间及下车站点的通勤班车 动态调度方法 (57)摘要 本发明实施例公开了一种基于员工下班时 间及下车站点的通勤班车动态调度方法， 包括如 下步骤： S1： 采集员工乘车需求数据； S2： 确定每 个班次可调度使用的可载客空车辆名单； S3： 确 定每个班次可乘车的员工名单； S4： 对同班次的 下车站点进行优化； S5： 将站点集合中各站点的 位置进行调整优化； S6： 采用蚁群算法对乘客进 行车辆分配及线路规划； S7： 上报车辆回程时间， 并进行下一班次的调度安排。 本发 明能够更自动 化、 更高效、 更 经济的解决员工下班的通勤问题。 权利要求书4页 说明书8页 附图2页 CN 115034522 B 2022.11.25 CN 115034522 B 1.一种基于员工下班时间及下车站点的通勤班车动态调度方法， 其特征在于， 包括如 下步骤： S1： 采集员工乘车需求数据， 所述员工乘车需求数据包括员工工号、 上车站点、 下车站 点、 上车时间； S2： 确定每 个班次可调度使用的可 载客空车辆名单； S3： 确定每 个班次可乘车的员工名单； S4： 对同班次的下车站点进行聚类算法优化， 将相近的几个下车地点收敛为1个站点， 获得优化后的站点 集合； S5： 将站点 集合中各站点的位置进行调整优化， 得到符合实际情况的各站点实际位置； S6： 根据得到的站点实际位置、 可载客空车辆名单、 员工名单， 采用蚁群算法对乘客进 行车辆分配及线路规划； S7： 上报车辆回程时间， 并进行 下一班次的调度安 排； 步骤S2中采用动态排班模式， 以班次发车时间点预设阈值内可调度的空车辆作为本班 次的最大排班车辆， 其中， 每个班次的可调度 空车辆来源于当前静态空车辆及动态在途回 程空车辆； 步骤S2中采用以下步骤获取 可调度使用的可 载客空车辆名单： S2‑1： 获取运营 车辆的任务状态； S2‑2： 若车辆为静态空 闲， 则将车辆列为可 载客空车辆； S2‑3： 若车辆为任务中， 且车辆未完成载客任务， 则剔除该 车辆； S2‑4： 若车辆为回程中， 且车辆的预计返回到达时间小于预设的阈值， 车辆列为可载客 空车辆； S2‑5： 重复以上S2 ‑1至S2‑4步骤， 直至所有车辆处 理完毕； S2‑6： 获得所有可载客空车辆名单。 2.如权利要求1所述的基于员工下班时间及下车站点的通勤班车动态调度方法， 其特 征在于， 步骤S 3中， 根据获得的可载客空车辆数及每辆车对应的座位， 确定本班次的最大载 客数； 若报名该班次的员工数量小于超过最大载客数且在安排车辆后仍有空车辆， 则该空 车辆可作为下一班次的车辆使用； 若报名该班 次的员工数量超过最大载客数， 则按照员工 报名先后顺序安排座位， 未排上座位的员工将通知其选择下一班次或自行使用其他交通工 具。 3.如权利要求1所述的基于员工下班时间及下车站点的通勤班车动态调度方法， 其特 征在于， 步骤S4中采用DBSCAN 算法对站点进行聚类优化， 步骤S4包括以下步骤： S4‑1： 以各站点的经纬度为输入数据， 利用第三方地图服务平台， 输出各点互相之间的 地理通行距离； S4‑2： 设定Eps、 MinPts参数值； 其中， Eps为站点的密度可达邻域半径，  MinPts为核心 点阈值， 即某站点Eps距离内的其他站点数量达到核心点阈值， 则该站点将作为核心点， 未 达到核心点阈值但该站点落在其他核心站点的邻域内， 则该站点为边缘点， 既不是核心点 也不是边缘点则为噪音点； S4‑3： 从所有站点中任意选取一个站点p， 如果对于参数  Eps 和 MinPts， 所选取的站 点p为核心点， 则找出 所有从p密度可达的其 他站点， 这些站点 集形成一个簇；权　利　要　求　书 1/4 页 2 CN 115034522 B 2S4‑4： 如果选取的站点p是边 缘点， 则选取另一个站点； S4‑5： 重复S4 ‑3、 S4‑4步， 直到所有点被处 理； S4‑6： 通过以上步骤获得优化后的站点 集合。 4.如权利要求1所述的基于员工下班时间及下车站点的通勤班车动态调度方法， 其特 征在于， 步骤S6包括以下步骤： S6‑1： 建立通勤班车路径问题的数 学模型； 假定企业用K辆车对L个站点的员工进行接送， 每个车辆乘客数为 ,每 个站点的人数为 ， 站点i到站点j的行驶距离为 ， 设 为第k辆车通过 的 站点数， 用集合 表示第k条路径， 其中的元素 ,表示站点在路径k中的顺序为i； 令 =0 表示起点， 以运行总里程 最短为目标函数， 建立 通勤班车路径问题的数 学模型为： （1） s.t. （2） ， （3） （4） （5） （6） 其中， 式 （1） 为目标函数， 即要求行驶总里程最短； 式 （2） 保证每条路径上的各站点的总 人数不超过通勤车的最大承载能力； 式 （3） 保证每条路径上的站点数不超过总站点数； 式 （4） 要求每个站点 都得到车辆的接送服务且每个乘客仅能乘 坐一辆车； 式 （5） 表 示每条路径 的站点组成； 式 （6） 表示第 k辆车 是否接送员工； S6‑2： 采用蚁群算法对目标函数进行优化， 从而获得优化后的乘客车辆分配及线路规 划； 设m为蚁群中蚂蚁的总数目， n表示站点数， 蚂蚁k在运动过程中， 根据各条路径上的信 息量决定其转移方向， 用禁忌表tabuk记录蚂蚁k当前所走过的站点 ， 集合随着t abuk做动 态调整； 表示t时刻蚂蚁k由站点 i转移到站点j的状态转移概 率； （7） 式中 ： 蚂蚁k下一 步允许选择的站点；权　利　要　求　书 2/4 页 3 CN 115034522 B 3