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

发布时间：2018-03-04 06:14

本文选题：城市公共自行车系统　切入点：调度优化算法　出处：《上海交通大学》2015年硕士论文　论文类型：学位论文

【摘要】：面对目前日益严重的城市道路的拥堵和不断恶化的气候环境,在政府的大力引导扶持和人们健康环保理念逐渐增强的背景下,自行车这种健康、无污染的交通出行方式又逐渐重新返回人们的视线。然而,由于受到交通流不平衡和通勤出行高峰的影响,城市公共自行车系统(Public Bicycle System,PBS)经常出现因站点无车而无法租车和因站点车位满而无法还车的尴尬现象。这一问题极大地挫伤了人们选择自行车出行的热情,阻碍了城市公共自行车系统作用的有效发挥。本文以当前PBS系统中租车还车困难问题为研究对象,在优化计算理论和车辆路径问题(VRP)的基础上,研究了系统的智能调度优化问题,包括多车调度任务的协调分配、静态调度路线的构建和动态调度任务的在线优化等问题,提出了基于聚类划分的动态区域调度模型、基于遗传算法的调度路线构建方法和基于迭代反馈双层模型的动态调度方案,在满足站点调度请求和保证站点服务能力的基础上实现了调度路线的优化,为系统调度管理提供了决策支持和智能解决方案。首先,为解决PBS系统多车调度时的调度车辆的站点分配问题,本文根据区域调度模型提出了基于K-medoids算法的多阶段再优化动态聚类的多车调度任务分割算法,实现了按照距离、任务量和站点需求的调度区域的动态划分和多车辆任务的协调。其次,本文研究了PBS静态调度问题,建立了以最小化调度费用为目标的整数规划模型,提出了基于VRP问题和自适应遗传算法的调度路线构建方法。本文结合PBS调度问题的实际需要对遗传算法进行了改进,定义了染色体逆序数距离并应用最小误差校正分析技术实现不可行个体的转换,通过基于双向关联度的不变位交叉算子、基于种群多样性和个体适应性的自适应变异算子、2-opt局部优化方法来提高求解精度和加快算法的收敛速度。第三,本文研究了PBS动态调度问题,建立了以最大化站点服务能力和最小化调度费用为目标的数学模型,提出了基于需求预测模型和调度规划模型的迭代反馈动态调度求解方案,采用GM(1,1)模型预测站点调度需求,采用“需求距离比”和Pareto占优排序两种思路实现调度规划模型,通过禁忌策略防止长时间得不到服务的“饥饿站点”的产生和延迟偏离当前调度路线的“病态站点”的服务时间。此外,基于模块化和面向对象的设计方法实现了本文的调度优化算法,并用宜兴市PBS运营数据和TSP/VRP测试实例库对本文算法进行了仿真分析。最后采用B/S架构的Web服务模式开发了调度仿真系统,为用户提供了从浏览器调用本文算法和显示执行结果的接口。
[Abstract]:In the face of the increasingly serious city road congestion and worsening of the climate and environment, in the government's strong support and guide people to the concept of environmental health gradually under the background of the bicycle health, no pollution of the traffic mode and gradually return to people's attention. However, due to influence of the traffic flow imbalance and commuting peak the city public bicycle system (Public Bicycle System, PBS) often appear due to car rental and car free site by site parking is full to the car of the embarrassing phenomenon. This problem greatly dampened the enthusiasm of people cycling, hinder the effective play the role of city public bicycle system. Based on the car the car is difficult problem in current PBS system as the research object, theoretical calculation and optimization of vehicle routing problem (VRP) on the basis of the study of intelligent scheduling system Optimization problems, including multi vehicle scheduling task allocation, online optimization problems such as construction of static scheduling and dynamic route scheduling tasks, and proposes a dynamic scheduling model based on regional clustering, genetic algorithm scheduling route construction method and dynamic scheduling scheme based on double iterative feedback model, to meet the site scheduling request and guarantee based on site service ability to realize the optimization of scheduling route, provide decision support and intelligent solutions for system scheduling management. Firstly, the problem of distribution system for the site PBS vehicle scheduling of vehicles based on regional scheduling model segmentation algorithm is proposed to multi vehicle scheduling optimization of multi stage dynamic clustering based on the K-medoids algorithm, realized by distance, dynamic coordination and regional task partition scheduling and the site needs and multi task vehicle Secondly, this paper studies the PBS static scheduling problem, integer programming model is established to minimize the scheduling cost as the goal, proposed the construction method for the VRP problem and the adaptive genetic algorithm based on the actual needs. Route scheduling based PBS scheduling problem to improve the genetic algorithm, the definition of reverse distance and chromosome analysis technology to achieve infeasible individual conversion using the minimal error correction, the fixed position of two-way crossover operator based on correlation, adaptive mutation operator of population diversity and individual adaptability based on the solution to improve the precision of 2-opt local optimization method and accelerate the convergence speed. Third, this paper studies the PBS dynamic scheduling problem, establishes the mathematical model with the greatest the site service capacity and minimizing the scheduling cost as the goal, proposed an iterative model and scheduling planning model based on demand forecasting Dynamic feedback scheduling scheme, using GM (1,1) model to predict site scheduling needs, the demand distance ratio and Pareto dominant sort of two ideas to achieve planning scheduling model, the tabu strategy is not a long time to prevent the service "the Hunger Site" and delayed to deviate from the current route scheduling "sick site" the Business Hours. In addition, the modular design method and object-oriented scheduling optimization algorithm based on the use of Yixing city PBS operation data and TSP/VRP test case base on this algorithm are simulated and analyzed. Finally the B/S architecture of the Web service model developed a scheduling simulation system, this algorithm provides from the browser and display the results of the implementation of interface for the user.

【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U495;U491.225

【参考文献】