基于多目标蚁群算法的共享单车调度优化方法  

A Scheduling Optimization Method of Shared Bicycles Based on a Multi-objective Ant Colony Algorithm

作　　者：薛晴婉 瞿麦青 彭怀军 姚运梅 郭伟伟[1] 谭墍元[1] 王云 XUE Qingwan;QU Maiqing;PENG Huaijun;YAO Yunmei;GUO Weiwei;TAN Jiyuan;WANG Yun(School of Electrical and Control Engineering,North China University of Technology,Beijing 100044,China;BII Transit System(Beijing)Co.,Ltd,Beijing 100101,China;School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China)

机构地区：[1]北方工业大学电气与控制工程学院,北京100144 [2]亿雅捷交通系统(北京)有限公司,北京100101 [3]北京交通大学交通运输学院,北京100044

出　　处：《交通信息与安全》2024年第2期124-135,共12页Journal of Transport Information and Safety

基　　金：国家自然科学基金项目(72371020);北京市教委科技一般项目(KM202310009009);北京京投卓越科技发展有限公司科研课题(BIITT-2022-09)资助。

摘　　要：共享单车作为公共交通接驳“、最后一公里”出行的重要交通工具,存在供需时空不匹配的问题,需要利用调度车实现共享单车的再平衡。针对部分现有共享单车调度方法存在的优化目标单一、调度点只能被访问1次、未考虑连续调度衔接等问题,建立了以总需求不满足度最小和调度成本最小为目标的多目标优化模型。该模型考虑高峰小时调度点需求远大于调度车容量的情况,允许多辆调度车多时段连续调度,且允许调度车重复访问调度点。设计了多目标蚁群算法进行求解,引入非支配排序方法,将解集划分为不同的非支配层级,取最高层级的解,形成1组同时考虑2个目标的Pareto最优解。该算法引入了最大-最小蚂蚁系统,改进了状态转移概率规则和信息素更新规则,使其能够适用于求解多目标优化问题。算例结果表明,该模型能够在保证较低调度成本的同时,减少需求损失,算例调度后的总需求不满足度由不进行调度时的26.48%降低到17.86%。将不同算例规模下多目标蚁群算法与贪心算法求解结果进行比较,多目标蚁群算法在多时段连续调度问题上具有优势,能够统筹安排每辆调度车在每个调度周期的行驶路径和在各调度点的到达时间和共享单车装卸数量。多目标蚁群算法所求得的解的质量优于贪心算法,较大规模算例求解得到的调度成本和总需求不满足度比贪心算法分别降低了62%和23%。As a crucial mode for facilitating public transportation connections and addressing the"last mile"prob-lem,shared bicycles confront the challenge of supply and demand imbalances.To solve this issue,deploying vehi-cles for scheduling purposes becomes an essential step in rebalancing the shared bicycles.In order to address the is-sues of current shared bicycle scheduling methods including single optimization objective,limited visits to schedul-ing sites,and insufficient consideration of continuous scheduling connections,a multi-objective optimization model is developed in this paper to minimize both total demand dissatisfaction and scheduling costs.This model considers the situation that the demand at the scheduling site surpasses the capacity of the scheduling vehicle during peak hours.Consequently,it enables the scheduling vehicle to make multiple trips to the site and allows to conduct contin-uous scheduling in multiple periods of time for multiple vehicles.A multi-objective ant colony algorithm is designed to solve this model by integrating the technique of non-dominated sorting to classify the solution set into vari-ous levels of non-dominance.The solution at the highest level is then utilized to create a Pareto-optimal solution,which considers two objectives concurrently.This algorithm introduces a new ant system incorporating maxi-mum-minimum criteria,modifies the state transition probability rule and pheromone update rule to enhance their ef-ficacy to deal with the multi-objective optimization problem.In order to verify the feasibility of the model and algo-rithm,a case study is carried out.The results show that the model is confirmed to be effective in decreasing demand loss while ensuring the lower scheduling costs.Specifically,the total demand dissatisfaction degree is reduced from 26.48%to 17.86%.Comparing the results of the multi-objective ant colony algorithm and greedy algorithm under various example sizes,the multi-objective ant colony algorithm shows a clear superiority in continuous scheduling of

关 键 词：城市交通 共享单车调度 多目标优化 蚁群算法 

分 类 号：U121[交通运输工程]