城市公共自行车系统智能调度优化算法研究

摘要

面对目前日益严重的城市道路的拥堵和不断恶化的气候环境，在政府的大力引导扶持和人们健康环保理念逐渐增强的背景下，自行车这种健康、无污染的交通出行方式又逐渐重新返回人们的视线。然而，由于受到交通流不平衡和通勤出行高峰的影响，城市公共自行车系统（Public Bicycle System,PBS）经常出现因站点无车而无法租车和因站点车位满而无法还车的尴尬现象。这一问题极大地挫伤了人们选择自行车出行的热情，阻碍了城市公共自行车系统作用的有效发挥。
　　本文以当前PBS系统中租车还车困难问题为研究对象，在优化计算理论和车辆路径问题（VRP）的基础上，研究了系统的智能调度优化问题，包括多车调度任务的协调分配、静态调度路线的构建和动态调度任务的在线优化等问题，提出了基于聚类划分的动态区域调度模型、基于遗传算法的调度路线构建方法和基于迭代反馈双层模型的动态调度方案，在满足站点调度请求和保证站点服务能力的基础上实现了调度路线的优化，为系统调度管理提供了决策支持和智能解决方案。首先为解决PBS系统多车调度时的调度车辆的站点分配问题，本文根据区域调度模型提出了基于 K-medoids算法的多阶段再优化动态聚类的多车调度任务分割算法，实现了按照距离、任务量和站点需求的调度区域的动态划分和多车辆任务的协调。其次研究了PBS静态调度问题，建立了以最小化调度费用为目标的整数规划模型，提出了基于VRP问题和自适应遗传算法的调度路线构建方法。本文结合PBS调度问题的实际需要对遗传算法进行了改进，定义了染色体逆序数距离并应用最小误差校正分析技术实现不可行个体的转换，通过基于双向关联度的不变位交叉算子、基于种群多样性和个体适应性的自适应变异算子、2-opt局部优化方法来提高求解精度和加快算法的收敛速度。第三研究了PBS动态调度问题，建立了以最大化站点服务能力和最小化调度费用为目标的数学模型，提出了基于需求预测模型和调度规划模型的迭代反馈动态调度求解方案，采用 GM(1,1)模型预测站点调度需求，采用“需求距离比”和Pareto占优排序两种思路实现调度规划模型，通过禁忌策略防止长时间得不到服务的“饥饿站点”的产生和延迟偏离当前调度路线的“病态站点”的服务时间。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1公共自行车系统及其实践现状

1.2公共自行车系统的研究现状

1.3公共自行车系统组成

1.4当前公共自行车系统存在的问题

1.5本文的主要工作

1.6本文的章节安排

第二章 理论基础和背景问题

2.1理论基础

2.2背景问题

2.3本章小结

第三章 多车调度任务动态分割算法

3.1公共自行车系统动态区域调度模型

3.2相似性测度

3.3多阶段再优化动态聚类划分算法

3.4仿真结果

3.5本章小结

第四章 静态调度路线构建算法

4.1 PBS站点自行车静态调度问题

4.2调度路线构建算法

4.3仿真结果

4.4本章小结

第五章 PBS站点自行车动态调度算法

5.1 PBS动态调度问题

5.2迭代反馈双层调度模型

5.3需求预测模型

5.4调度规划模型

5.5迭代反馈模型禁忌搜索策略

5.6动态调度仿真结果

5.7本章小结

第六章 调度仿真系统设计和算法实现

6.1调度算法的设计和实现

6.2调度仿真系统设计和实现

6.3本章小结

第七章 总结与展望

7.1工作总结

7.2未来展望

参考文献

致谢

攻读硕士学位期间已发表或录用的论文