合乘系统路径匹配算法研究与实现

CORC > 沈阳自动化研究所 > 中国科学院沈阳自动化研究所 > 工业控制网络与系统研究室

题名	合乘系统路径匹配算法研究与实现
作者	王子
学位类别	硕士
答辩日期	2015-05-26
授予单位	中国科学院沈阳自动化研究所
授予地点	中国科学院沈阳自动化研究所
导师	周侗
关键词	合乘模型刚性出行弹性出行两阶段EDA算法数据可视化
其他题名	Research and Application on path matching algorithm for carpooling system
学位专业	计算机应用技术
中文摘要	近年来，国民经济生活水平不断提高，城镇化建设不断深入，传统的公共交通设施已经无法满足人们的日常工作、生活需求。为了追求更加便捷舒适的出行，私人汽车受到越来越多家庭的亲睐。私人汽车数量的不断增长，间接带来了诸如资源浪费、空气污染、交通拥堵等问题，严重降低了居民的生活质量。越来越多的大中型城市竞相出台了汽车限购、限行等政策，从汽车数量的源头角度出发解决问题。上世纪90年代，欧美等发达国家从提高小汽车的使用效率角度出发，大力发展合乘政策，经过多年的探索与积累，如今已经发展成为城市交通的重要组成部分。2014年1月2日，北京市交通委《关于北京市小客车合乘出行的意见》的出台，标志着拼车出行正式被认可并登上历史舞台。合乘出行，是指出行线路相似的乘客搭乘同一辆车出行，以此缓解交通压力、减少出行费用、降低污染物排放。国内针对拼车领域的研究较发达国家大约迟20年左右，随着近几年拼车出行在我国的兴起，国内的许多学者如黄肇义、杨东援、夏凯旋、雷孟林、曹忠于等人开始通过分析国外的拼车发展，研究在我国发展合乘的可行性和实现方式；同时，翟泳、车勇、杨金梁等人更深入的探讨了在我国发展实践拼车出行的具体模式。合乘问题是一类特殊的PDP（Pickup and Delivery Problem）问题，涉及到上下车点、时间、路径、车容量等诸多限制条件，复杂度高、求解难度大，属于强NP问题。PDP问题通常采用启发式算法进行求解，具有代表性的有：适应性插入算法、分支定界算法、禁忌搜索算法、模拟退火算法、分组遗传算法、服务需求分派算法等。通过对比，目前的研究主要存在以下局限性： (1) 现有求解未考虑车辆与人之间的隶属关系，不能覆盖到车主之间相互搭乘的情况； (2) 合乘问题建模时，假定车辆集中在一个车场或集中分布在有限几个车场，与实际合乘出行中车辆的离散式分布差别较大； (3) 求解PDP问题大都采用传统启发式算法，未有分布式启发算法应用于合乘问题中的先例； (4) 现有拼车类应用大都是基于论坛交流的方式，整个过程未实现合乘线路的自动匹配和优化；针对合乘问题目前研究中存在的局限性，本文从模型、算法和软件系统三个方面展开研究，主要工作及创新点如下： (1) 提出了一种新的基于柔性及刚性出行的合乘出行模型，有效地解决了车辆和人之间隶属关系的问题，从而能够实现车主之间的相互搭乘； (2) 提出了虚拟车场概念，有效地解决了实际合乘中车辆分散式分布与集中式模型之间的矛盾； (3) 将分布式估计算法应用于新建立的模型中，提出两阶段EDA算法，并针对合乘问题对初始化概率矩阵进行了优化； (4) 实现了多人拼车系统，根据乘客的路径信息进行优化及自动推荐； (5) 将数据可视化技术应用到系统中，实现了对拼车数据的处理及可视化展示。
索取号	TP301.6/W39/2015
英文摘要	In recent years, with the development of the social economy and construction of urbanization, the traditional public transport facilities have been unable to meet the needs of people’s daily work and life. Inorder to pursue a more convenient and comfortable life, private cars become more and more popular. The increasing of private cars brings lots of problems indirectly such as air pollution, car accidents, the waste of resources and the traffic congestion, which greatly reduces the quality of the citizen’s life. Many citys have introduced policies like property-purchasing limitations or driving curbs to reduce the pressure caused by cars. In 90’s, America and Europe begun to develop the research about carpooling system, aiming to improve the usage and efficiency of cars. After years of exploration and accumulation, carpooling has become an important part of the public transportation. In January 2, 2014, Beijing Municipal Traffic Commission launched a policy which encourage the behavior of carpooling among citizen and this was regarded as the beganing of the development of carpooling in our country. Carpooling refers to traveling in the same car when the passengers’ routes are convenient or similar to each other, which can help to reduce the traffic pressure, air pollution as well as travel cost. Research in our country begun 20 years after developed countries. Scholars in our country have already done lots works: Zhaoyi Huang, Dongyuan Yang, Kaixuan Xia, Menglin Lei, Zhongyu Cao figured out the development of carpooling which can be used in our country; Yong Qu, Yong Che, Jinliang Yang did lots of research about the carpooling pattern which can suit the conditions of our cities. The carpooling problem is a special kind of PDP(Pickup and Deliver Problem)problem, which has many restrictions such as the origin, the destination, the route, riding time, car capacity, time window and so on. It’s known as the NP hard problem which is very hard to solve. Generally heuristic algorithms are used to solve the PDP, and the representative algorithm can be the adaptive insertion algorithm, the branch and bound algorithm, the simulated annealing algorithm, the grouping genetic algorithm and the requirement distribution algorithm. Comparison shows that the present study has the following limitations： (1) The tempt solutions haven't considered the relationship between the vehicle and car owner, which can’t cover the situation when car owners ride together in one vehicle; (2) The carpooling models which exist now assume that all the vehicles are managed by one or multiple garage, and this is not suitable in the reality as the vehicles are distributed discrete; (3) There has been no EDA algorithm used in carpooling field which makes this article valuable; (4) The current carpooling applications are mostly based on the way of the forum, which doesn't contain the functions as automatic matching and optimized route; Considering the limitation of the carpooling problem existing in the current research, this paper launches the research from three aspects: model, algorithm and software system. The main work and innovation points are as follwos: (1) Proposed a new carpooling model based on the concept of rigid ride and elastic ride which covers the situation when car owners ride together in one vehicle; (2) Proposed the concept of virtual depot which is suitable for the distribution of vehicles in reality; (3) Proposed two-stage EDA algorithm to solve the problem, optimized the initial probability matrix using the relationship between the vehicles and the passengers; (4) Designed a carpooling system which can optimize and recommend the best route for the passengers; (5) Designed a data visualization interface which makes the data more clearly to see and understand.
语种	中文
产权排序	1
页码	69页
内容类型	学位论文
源URL	[http://ir.sia.ac.cn/handle/173321/16742]
专题	沈阳自动化研究所_工业控制网络与系统研究室
推荐引用方式 GB/T 7714	王子. 合乘系统路径匹配算法研究与实现[D]. 中国科学院沈阳自动化研究所. 中国科学院沈阳自动化研究所. 2015.