公共自行车调度路径优化问题研究

发布时间：2018-01-16 06:41

本文关键词：公共自行车调度路径优化问题研究　出处：《西南交通大学》2015年硕士论文　论文类型：学位论文

【摘要】：当前,公共自行车租赁系统作为一种新兴的公共交通系统在世界范围内蓬勃发展,公共自行车不仅可以在中短距离出行发挥其灵活、高效的优势,还可以有效延伸公共交通的服务范围。但在实际运营中,“租车难”“还车难”问题严重制约公共自行车作用的发挥并影响公共自行车系统的推广发展。“租车难”“还车难”问题的出现与城市功能布局、租赁点分布和规模、居民出行规律等因素有关,而高效的车辆调度有助于这一问题的解决。车辆调度主要解决多个租赁点和调度中心间公共自行车的存量问题,其包含租赁点调度需求预测和调度路径优化问题两部分；本文重点研究的是调度中的路径优化问题,需要重点考虑到调度时间约束、调度中心个数、调度需求变化等因素。本文将公共自行车调度路径优化问题归为多路旅行商问题,对公共自行车调度路径优化问题进行分类研究以适应于不同的调度环境,具体的研究工作包括以下几个方面：(1)根据车辆路径问题的分类标准并结合公共自行车调度路径优化问题的特性,分别对4类问题进行研究。其中第1类问题是单个调度中心无时间窗的公共自行车调度路径优化问题,本文在考虑车辆容量约束和行驶距离约束的前提下建立了以调度路径最短为目标的优化模型,实现了非对称网络的调度路径的求解。根据问题的分类,单调度中心无时间窗调度模型是研究其他几类问题的基础。(2)第2类问题研究的是单个调度中心软时间窗的调度路径优化问题,文中用时间窗约束来衡量调度服务的及时性以提高客户满意度,违反时间窗约束则需要接受一定的惩罚并建立惩罚函数,并通过时间的迭代关系表述车辆到达各个租赁点的时间,从而构造了调度路径最短、客户满意度最高的多目标调度路径优化模型。(3)第3类问题研究的是多个调度中心软时间窗调度路径优化问题,在模型的建立上,削弱了问题的假设条件,本文的研究不要求调度车辆返回原来的调度中心,实现了问题在调度车辆数和调度路径长度两方面的进一步优化。(4)进一步削弱假设条件,对需求动态变化的调度路径优化问题进行研究,通过设立时间轴和关键点,将动态需求问题转化成静态问题,建立了动态需求下的公共自行车调度路径优化模型。文中研究的4类问题,通过对约束条件做适当的松弛或附加不同特性,不断逼近实际调度问题,构建了公共自行车调度路径优化问题的体系,能够满足不同调度环境下问题的要求。(5)通过改进遗传算法对问题进行求解,用Matlab软件编写程序,以潍坊市奎文区22个公共自行车租赁点为调度实例,针对上述4类模型分别进行计算,通过对计算结果的分析,验证了算法的有效性。
[Abstract]:At present, the public bicycle rental system as a new public transport system to flourish in the world, the public bicycle can not only in the short distance travel to play its flexible and efficient advantages, but also can effectively extend the public transport service scope. But in actual operation, "" car car difficult problem restrict public bicycle to play the role and influence of public bicycle system to promote the development of the car difficult. "The car is difficult" problems and the function of the city layout, rental distribution and scale, factors of resident trip distribution, and vehicle scheduling and efficient help to solve this problem is mainly to solve the vehicle scheduling. A number of rental and dispatch center between the stock of public bicycles, including rental demand forecasting and scheduling scheduling path optimization of two part of the paper focuses on the problem; The path optimization problem in scheduling, taking into account the need to focus on scheduling time constraints, the number of dispatch center, scheduling demand changes and other factors. The public bicycle scheduling path optimization problem into multiple travelling salesman problem, scheduling of public bike path optimization problem of research to adapt to different scheduling environment, the specific research work includes the following aspects: (1) according to the classification standard of vehicle routing problem and the combination of public bicycle scheduling optimization characteristics, the paper study 4 kinds of problems. The first problem is a single scheduling center without time window problem of public bicycle path scheduling optimization, considering the vehicle capacity constraints and driving distance constraint the optimization model is established by scheduling the shortest path as the goal, to achieve the scheduling path for asymmetric networks. Based on the problem Classification, single dispatch center without time windows scheduling model is based on other types of problem. (2) study on the second kinds of problems are scheduling path optimization problem single dispatch center soft time windows, timeliness with time window constraints to measure the scheduling service in order to improve customer satisfaction, in violation of time window constraints need accept certain punishment and penalty function was established, and the iterative time expression of vehicle arriving each lease point of time, so as to construct the shortest path scheduling, optimization model of multi objective scheduling path of the highest customer satisfaction. (3) a study of the third class is a multiple dispatch center soft time windows scheduling route optimization problem. On the basis of model, weaken the hypothesis condition of the problem, this paper does not require the return to the original vehicle scheduling and dispatching center, the number of vehicles and scheduling problems in scheduling the path length of the two party The further optimization. (4) to further weaken the assumptions of scheduling path optimization problem of dynamic demand, through the establishment of the time axis and the key points, the dynamic demand problem into static problem, the establishment of public bicycle road scheduling under dynamic demand size optimization model. 4 kinds of problems in this paper, through do the appropriate relaxation of the constraints or with different characteristics, approaching the actual problem, the construction of public bicycle scheduling optimization system can meet different scheduling environment problems. (5) by using the improved genetic algorithm to solve the problem, using Matlab programming software, with 22 public bike rental Kuiwei District of Weifang city for example scheduling, calculated according to the above 4 models respectively, through analysis of calculation results, verify the validity of the algorithm.

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

【参考文献】