基于ITS的智能乘客信息系统研究
|
摘要
在我国众多大城市普遍存在交通拥挤问题，造成交通拥挤的首要原因是城市交通基础设施的建设远远落后于城市交通需求的增长。大力发展公共交通是解决城市交通拥挤问题的首选措施。
选择路径是公交信息系统中的关键技术，有很多经典的算法解决最短路径问题，如Dijkstra算法和Floyd算法，但大都不适合于公交查询最短路径。一是由于运算速度慢，二是由于计算结果含有大量无用数据。
当乘客乘车时，他的首要目标是尽快到达目的地，第二目标是花费少。因此本文提出一个新的解决方法。第一目标是换乘车次最少，第二目标是出行路程最短。如果乘客换乘车次增多，因此而产生的不可预知的因素也会增多，另外由于大多数城市采取单一票制，所以换乘车次最少也就保证了花费最少。
本算法基于宽度优先并用蚂蚁算法优化，蚂蚁算法是一种基于真实蚁群的人工智能系统，常用于解决组合优化问题，如旅行商问题(TSP)，在蚂蚁算法中一组蚂蚁团结合作，寻找TSP问题的最优解。合作的方式是利用在寻找最优解时在TSP图的边上留下的信息素，是一种间接的通信方式。
在一个城市中，如果它的公交车运营线路是稳定的，那么从一个车站到达另一个车站的路线也应该是比较稳定的。因此我们可以将每对站点之间的路径全部求出，再加上关于本路径的一些信息如长度、信息素等全部放在数据库中，当一个乘客需要查找时就从此数据库中选择。每条路径包含一项信息素用以表示路径的优先级，选择某条路径的乘客越多，这条路径的优先级就会变得越高，以后被选择的机会也大。但是当一条路径被堵时优先级会降低。因此，这个系统使用时间越长，系统越智能化，越能为乘客提供有效的信息。
最后，本文提出了发展适合我国城市的公交乘客信息系统的设想和建议，解决了公交乘客信息系统的一项关键技术—公交乘客出行路径优化模型，并研究开发了唐山市公交问路系统。
Traffic congestion exists widely in China large cities. The first reason is the providing of transportation facilities is much less than the development of transportation demand. To develop public transportation is the first choice in solving the problem of congestion.
Choosing route for passengers is the key technology in the bus information system. There are many classic algorithms such as Dijkstra algorithm and Floyd algorithm to solve the problem. But they don't fit for this problem. The first reason is that it doesn't have a high speed; the second is that its result has large numbers of unuseful data.
When a passenger take a bus, his first aim is to arrive at the destination as soon as possible; the second is to pay as least as possible. So a new algorithm is put forward in my paper. The primary object is to use the least transfer times, the second is to choose the shortest route distance. There will be more factors we can't forecast if a passenger transfer more bus. Furthermore the cost to take a bus is uniform in many cities, so the less time he transfers bus the less he will pay for it.
The algorithm is based on the breadth-first search and optimized by ant algorithm. Ants system is an artificial system based on the behavior of real ant colonies, which is often used to solve combinatorial problems, such as Traveling Salesman Problem (TSP). In ant colony system (ACS), a set of cooperating agents called ants cooperate to find good solutions to TSP. Ants cooperate using an indirect form of communication mediated by pheromone they deposit on the edges of the TSP graph while building solutions.
I apply the ant algorithm as follows. In a city, if it has stable bus route, it will has stable route from a stop to another by bus. Then we can calculate all possible routes and store them and its length in a database. A passenger can choose them from the database when he need it. Each route has an pheromone to express the route's priority. The more passengers choose the route the higher its priority will become,and have more chance to be choosed later. But if a route is obstructed the priority will be decreased. So the longer the system is used the more information it can provide for passengers.
At last some suggestions and recommendations have been raised to develop suitable transit passenger information system for Chinese cities. A GIS-based passenger route choice model has been raised in this thesis. It is based on a new shortest path algorithm that uses the least transfer times as primary object and shortest path distance as second object. Application of this model in Tangshan public transportation network show that it is efficient and practical.
选择路径是公交信息系统中的关键技术，有很多经典的算法解决最短路径问题，如Dijkstra算法和Floyd算法，但大都不适合于公交查询最短路径。一是由于运算速度慢，二是由于计算结果含有大量无用数据。
当乘客乘车时，他的首要目标是尽快到达目的地，第二目标是花费少。因此本文提出一个新的解决方法。第一目标是换乘车次最少，第二目标是出行路程最短。如果乘客换乘车次增多，因此而产生的不可预知的因素也会增多，另外由于大多数城市采取单一票制，所以换乘车次最少也就保证了花费最少。
本算法基于宽度优先并用蚂蚁算法优化，蚂蚁算法是一种基于真实蚁群的人工智能系统，常用于解决组合优化问题，如旅行商问题(TSP)，在蚂蚁算法中一组蚂蚁团结合作，寻找TSP问题的最优解。合作的方式是利用在寻找最优解时在TSP图的边上留下的信息素，是一种间接的通信方式。
在一个城市中，如果它的公交车运营线路是稳定的，那么从一个车站到达另一个车站的路线也应该是比较稳定的。因此我们可以将每对站点之间的路径全部求出，再加上关于本路径的一些信息如长度、信息素等全部放在数据库中，当一个乘客需要查找时就从此数据库中选择。每条路径包含一项信息素用以表示路径的优先级，选择某条路径的乘客越多，这条路径的优先级就会变得越高，以后被选择的机会也大。但是当一条路径被堵时优先级会降低。因此，这个系统使用时间越长，系统越智能化，越能为乘客提供有效的信息。
最后，本文提出了发展适合我国城市的公交乘客信息系统的设想和建议，解决了公交乘客信息系统的一项关键技术—公交乘客出行路径优化模型，并研究开发了唐山市公交问路系统。
Traffic congestion exists widely in China large cities. The first reason is the providing of transportation facilities is much less than the development of transportation demand. To develop public transportation is the first choice in solving the problem of congestion.
Choosing route for passengers is the key technology in the bus information system. There are many classic algorithms such as Dijkstra algorithm and Floyd algorithm to solve the problem. But they don't fit for this problem. The first reason is that it doesn't have a high speed; the second is that its result has large numbers of unuseful data.
When a passenger take a bus, his first aim is to arrive at the destination as soon as possible; the second is to pay as least as possible. So a new algorithm is put forward in my paper. The primary object is to use the least transfer times, the second is to choose the shortest route distance. There will be more factors we can't forecast if a passenger transfer more bus. Furthermore the cost to take a bus is uniform in many cities, so the less time he transfers bus the less he will pay for it.
The algorithm is based on the breadth-first search and optimized by ant algorithm. Ants system is an artificial system based on the behavior of real ant colonies, which is often used to solve combinatorial problems, such as Traveling Salesman Problem (TSP). In ant colony system (ACS), a set of cooperating agents called ants cooperate to find good solutions to TSP. Ants cooperate using an indirect form of communication mediated by pheromone they deposit on the edges of the TSP graph while building solutions.
I apply the ant algorithm as follows. In a city, if it has stable bus route, it will has stable route from a stop to another by bus. Then we can calculate all possible routes and store them and its length in a database. A passenger can choose them from the database when he need it. Each route has an pheromone to express the route's priority. The more passengers choose the route the higher its priority will become,and have more chance to be choosed later. But if a route is obstructed the priority will be decreased. So the longer the system is used the more information it can provide for passengers.
At last some suggestions and recommendations have been raised to develop suitable transit passenger information system for Chinese cities. A GIS-based passenger route choice model has been raised in this thesis. It is based on a new shortest path algorithm that uses the least transfer times as primary object and shortest path distance as second object. Application of this model in Tangshan public transportation network show that it is efficient and practical.
引文
[1] 杨荫凯．智能交通系统(ITS)概述及我国的发展对策选择．地理科学进展，1999年9月
[2] 李峰．智能交通系统在国外的发展趋势．国外公路，1999年2月
[3] 路遥．未来交通指挥系统—智能交通系统．国外科技动态，1997年第3期
[4] 杨冰．智能交通系统(ITS)的开发与动向．科技导报，1997年第12期
[5] 陈旭梅，于雷，郭继孚．美国智能交通系统ITS的近期发展综述．中外公路，2003年4月第23卷第2期
[6] 李峰．智能交通系统在国外的发展趋势．国外公路，1999年2月
[7] 史其信，陆化晋．中国智能交通发展战略构想．道路交通管理，1998年第11期
[8] 尚刚．智能交通系统(ITS)在日本的发展综述．华东公路，1999年6月20日
[9] 张永强．智能交通系统中动态用户最优路径选择问题的解决途径．现代计算机，总第117期
[10] 张志秀，王平．高速发展的智能交通系统．2003年9月第17卷第3期山东轻工业学院学报
[11] 黄解军，潘和平，万幼川．构建智能交通推动数字城市的发展．城市规划汇刊，2002年第3期
[12] 李庆利，陈曙，刘允才．基于ITS的智能公共交通管理系统．电子技术2003年第8期
[13] 希光第．首都公共交通发展的几点设想．北京规划建设，1998年第4期
[14] 顾尚华．优先发展公共交通势在必行．现代城市研究，1997年第1期
[15] 李春明．公交优先与环境保护．城市公共交通，2000年第6期
[16] 杨兆升，胡坚明．中国智能公共交通系统框架与实施研究．交通运输系统工程与信息，2001年2月
[17] 陈林菁．公交优先!现代城市交通的选择．城市道桥与防洪，2001年04期
[18] 黄肇义，徐慰慈，杨晓光．ITS对国内城市交通规划影响的探讨．城市规划，1999年06期
[19] 范文毅．公交优先模型的建立和计算机仿真分析．上海交通大学学报，2000年增刊
[20] 王炜．城市交通规划理论与方法．北京：人人交通出版社，1992年4月
[21] 刘灿齐，杨佩昆．基于最短路径的城市干道网规划的算法研究．中国公路学报2000年4月
[22] 徐业昌，李树详．基于地理信息系统的最短路径搜索算法．中国图像图形学报，1998，3(1)：39～43
[23] 蒋冰蕾．美国智能公共交通领域发展近况．国外城市规划，1999年第1期
[24] 陆化普．日本智能公共交通系统的开发应用现状与展望．国外城市规划，1999年第1期
[25] 辛健成．公交车站上的乘客信息系统．商用汽车，2002年第5期
[26] 石小法，王炜，卢林等．交通信息影响下的动态路径选择模型研究．2000年8月公路交通科技
[27] 高铁杠，顾巧论．智能公交信息查询系统．城市公共交通，2003年第3期
[28] 傅冬绵．交通问路系统中最短路径的新算法．华侨大学学报，2001年4月
[29] 乐阳，龚健雅．Dijkstra最短路径算法的一种高效率实现．武汉测绘科技大学学报，1999年24期
[30] 陈芳，袁保宗．智能信息查询系统的研究与实现．北方交通大学学报，1997年第5期
[31] 刘玉海，肖江阳，张锡恩．一种新型最短路径搜索算法的研究．计算机工程与应用，2001年17期
[32] 马良．来自昆虫世界的寻优策略——蚂蚁算法．自然杂志，第21卷第3期
[33] Marco Dorigo, Gianni Di Caro. ant algorithms for Discrete Optimization. Artificial Life, Vol. 5, No. 3,
[34] 马良，姚俭，范炳全．蚂蚁算法在交通配流中的应用．科技通报，2003年9月第19卷第5期
[35] Jose Aguilar. A General Ant Colony Model to solve Combinatorial Optimization Problems. Revista colombiana de computacion volumen 2 number 1
[36] 黄岚，王康平，周春光等．基于蚂蚁算法的混合方法求解旅行商问题．吉林大学学报(理学版)，2002年10月
[37] 马良，蒋馥．多目标旅行售货员问题的蚂蚁算法求解．系统工程理论方法应用，1999年第8卷第4期
[38] Marco dorigo. The Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on systems, Man, and Cybernetics-Part B, Vol 26, No. 1 1996
[39] 马良．TSP及其扩展问题的混合型启发式算法．上海理工大学学院，1999年第21卷第1期
[40] 游道明，陈坚．用蚂蚁算法解决多目标TSP问题．小型微型计算机系统，2003年第10期
[41] Gerth S B, Worst-Case Efficient Priority Queues 7th ACM-SIAM symposium on discrete algorithm, 1997
[42] Boris Y C, Andrew V G, Buckets, heaps, lists, and Monotone priority Queues, Proceeding of the 7th annual ACM-SIAM symposium on discrete algorithms, 1997
[43] Marco dorigo. The Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on systems, Man, and Cybernetics-Part B, Vol 26, No. 1 1996
[44] 张纪会，徐心如．一种新的进化算法—蚁群算法．系统工程理论与实践，1999年3月
[45] 林震，杨浩．出行者心理与交通信息系统存在问题分析．公路，2002年12月
[46] 严蔚敏，吴伟民．数据结构．北京：清华大学出版社1997年4月
[47] 杨新苗 王炜 马文腾．基于GIS的公交乘客出行路径选择模型．东南大学学报2000年11月
[48] 邬伦，张晶，赵伟．地理信息系统．北京：电子工业出版社，2002年7月第一版
[49] 魏思兵．地理信息系统的技术与发展．现代计算机，1997年第2期
[50] 杨正洪，郑齐健．中文SQL Server 2000关系数据库系统管理和开发指南．北京：机械工业出版社，2001年9月
[2] 李峰．智能交通系统在国外的发展趋势．国外公路，1999年2月
[3] 路遥．未来交通指挥系统—智能交通系统．国外科技动态，1997年第3期
[4] 杨冰．智能交通系统(ITS)的开发与动向．科技导报，1997年第12期
[5] 陈旭梅，于雷，郭继孚．美国智能交通系统ITS的近期发展综述．中外公路，2003年4月第23卷第2期
[6] 李峰．智能交通系统在国外的发展趋势．国外公路，1999年2月
[7] 史其信，陆化晋．中国智能交通发展战略构想．道路交通管理，1998年第11期
[8] 尚刚．智能交通系统(ITS)在日本的发展综述．华东公路，1999年6月20日
[9] 张永强．智能交通系统中动态用户最优路径选择问题的解决途径．现代计算机，总第117期
[10] 张志秀，王平．高速发展的智能交通系统．2003年9月第17卷第3期山东轻工业学院学报
[11] 黄解军，潘和平，万幼川．构建智能交通推动数字城市的发展．城市规划汇刊，2002年第3期
[12] 李庆利，陈曙，刘允才．基于ITS的智能公共交通管理系统．电子技术2003年第8期
[13] 希光第．首都公共交通发展的几点设想．北京规划建设，1998年第4期
[14] 顾尚华．优先发展公共交通势在必行．现代城市研究，1997年第1期
[15] 李春明．公交优先与环境保护．城市公共交通，2000年第6期
[16] 杨兆升，胡坚明．中国智能公共交通系统框架与实施研究．交通运输系统工程与信息，2001年2月
[17] 陈林菁．公交优先!现代城市交通的选择．城市道桥与防洪，2001年04期
[18] 黄肇义，徐慰慈，杨晓光．ITS对国内城市交通规划影响的探讨．城市规划，1999年06期
[19] 范文毅．公交优先模型的建立和计算机仿真分析．上海交通大学学报，2000年增刊
[20] 王炜．城市交通规划理论与方法．北京：人人交通出版社，1992年4月
[21] 刘灿齐，杨佩昆．基于最短路径的城市干道网规划的算法研究．中国公路学报2000年4月
[22] 徐业昌，李树详．基于地理信息系统的最短路径搜索算法．中国图像图形学报，1998，3(1)：39～43
[23] 蒋冰蕾．美国智能公共交通领域发展近况．国外城市规划，1999年第1期
[24] 陆化普．日本智能公共交通系统的开发应用现状与展望．国外城市规划，1999年第1期
[25] 辛健成．公交车站上的乘客信息系统．商用汽车，2002年第5期
[26] 石小法，王炜，卢林等．交通信息影响下的动态路径选择模型研究．2000年8月公路交通科技
[27] 高铁杠，顾巧论．智能公交信息查询系统．城市公共交通，2003年第3期
[28] 傅冬绵．交通问路系统中最短路径的新算法．华侨大学学报，2001年4月
[29] 乐阳，龚健雅．Dijkstra最短路径算法的一种高效率实现．武汉测绘科技大学学报，1999年24期
[30] 陈芳，袁保宗．智能信息查询系统的研究与实现．北方交通大学学报，1997年第5期
[31] 刘玉海，肖江阳，张锡恩．一种新型最短路径搜索算法的研究．计算机工程与应用，2001年17期
[32] 马良．来自昆虫世界的寻优策略——蚂蚁算法．自然杂志，第21卷第3期
[33] Marco Dorigo, Gianni Di Caro. ant algorithms for Discrete Optimization. Artificial Life, Vol. 5, No. 3,
[34] 马良，姚俭，范炳全．蚂蚁算法在交通配流中的应用．科技通报，2003年9月第19卷第5期
[35] Jose Aguilar. A General Ant Colony Model to solve Combinatorial Optimization Problems. Revista colombiana de computacion volumen 2 number 1
[36] 黄岚，王康平，周春光等．基于蚂蚁算法的混合方法求解旅行商问题．吉林大学学报(理学版)，2002年10月
[37] 马良，蒋馥．多目标旅行售货员问题的蚂蚁算法求解．系统工程理论方法应用，1999年第8卷第4期
[38] Marco dorigo. The Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on systems, Man, and Cybernetics-Part B, Vol 26, No. 1 1996
[39] 马良．TSP及其扩展问题的混合型启发式算法．上海理工大学学院，1999年第21卷第1期
[40] 游道明，陈坚．用蚂蚁算法解决多目标TSP问题．小型微型计算机系统，2003年第10期
[41] Gerth S B, Worst-Case Efficient Priority Queues 7th ACM-SIAM symposium on discrete algorithm, 1997
[42] Boris Y C, Andrew V G, Buckets, heaps, lists, and Monotone priority Queues, Proceeding of the 7th annual ACM-SIAM symposium on discrete algorithms, 1997
[43] Marco dorigo. The Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on systems, Man, and Cybernetics-Part B, Vol 26, No. 1 1996
[44] 张纪会，徐心如．一种新的进化算法—蚁群算法．系统工程理论与实践，1999年3月
[45] 林震，杨浩．出行者心理与交通信息系统存在问题分析．公路，2002年12月
[46] 严蔚敏，吴伟民．数据结构．北京：清华大学出版社1997年4月
[47] 杨新苗 王炜 马文腾．基于GIS的公交乘客出行路径选择模型．东南大学学报2000年11月
[48] 邬伦，张晶，赵伟．地理信息系统．北京：电子工业出版社，2002年7月第一版
[49] 魏思兵．地理信息系统的技术与发展．现代计算机，1997年第2期
[50] 杨正洪，郑齐健．中文SQL Server 2000关系数据库系统管理和开发指南．北京：机械工业出版社，2001年9月