（计算机科学与技术专业论文）基于多人合乘模式的出租车智能调度管理系统设计与研究.pdf

摘要 摘要 随着国民经济的飞速发展，人民收入水平的不断提高，城市车辆迅速增加， 乘坐出租车的入越来越多。与此同时，废气污染、交通堵塞等一系列问题也困 扰着城市交通的发展。加快城市公共交通事业发展已经成为当务之急。作为公 交系统的重要组成部分，提高出租车的运营效率成为缓解交通压力的有效途径。 通过对出租车行业的调查及车辆调度相关技术的深入研究，本文设计了一 种基于模式匹配、g p s 、g i s 、g s m g p r s 的出租车智能调度系统。本系统采用 字符串模式匹配解决了多人合乘情况下出租车行驶路径的匹配难题。将目前车 辆监控调度系统中使用最为广泛的g s m 短消息通信和g p r s 通信方式作了合 理的融合，设计了监控调度中心对两种通信方式数据的接收方法。整个系统基 于c s ( 客户端n 务器) 结构，采用了中间件技术。由中间件完成调度中心与车载 终端的通信，通过中间件对车辆信息进行了新的、统一的封装，在中间件和客 户端之间采用更高层的通信协议。同时对监控调度中心软件的功能进行了设计， 如导航、跟踪等。另外，系统具有实时监控与调度、防盗报警等功能，大大提 高了车辆管理效率。整个系统具有大容量、高效率、高精度、低费用等优势。 关键词：模式匹配；中间件；g p s ；g i s ；g p r s ；g s m ；智能调度 a b s t r a c t ab s t r a c t w i t ht h er a p i dd e v e l o p m e n to fn a t i o n a le c o n o m ya n di m p r o v e m e n to f p e o p l e s i n c o m i n g ，t h e r ea r em o r ea n dm o r ea u t o si nc i t i e sa n dm o r ea n dm o r ep e o p l et a k et a x i a tt h es a m et i m e ，t h e d e v e l o p m e n to fm u n i c i p a lt r a f f i ci sb e s e tw i t has e r i a lo f p r o b l e m s ，l i k ea i rp o l l u t i o n sa n dt r a f f i cc o n g e s t i o n s i th a sb e e na nu r g e n tp r o b l e m t h a th o wt os p e e du pu r b a np u b l i ct r a n s p o r t sd e v e l o p m e n t t ob et h ei m p o r t a n tp a r t o fp u b l i ct r a n s p o r t ，i ti sa ne f f e c t i v ew a yt o i m p r o v et h er u n n i n ge f f i c i e n c ya n d r e l i e v et h ep r e s s u r eo f t r a n s p o r t w i t ht h ei n v e s t i g a t i o no ft a x ib u s i n e s sa n dt h ei n t e n s i v es t u d yo fc o r r e l a t i o n t e c h n i q u e ，i ti sd i s c u s s e dt h a tt h es y s t e mo ft a x ii n t e l l i g e n td i s p a t c h e rw h i c hi sb a s e d o np a t t e mm a t c h i n g ，g p s ，g i s ，g s m g p r s t h ed i s p a t c h e rp r o b l e mo fm u l t i r i d ei s s o l v e db yu s ec h a r a c t e rs t r i n gm a t c h i n g t h em o s tp o p u l a rw a y so fn o w a d a y sg s m s h o r t m e s s a g ec o m m u n i c a t i o na n dg p r sc o m m u n i c a t i o ni sm i x e d t o g e t h e r r e a s o n a b l y , a n db o t h o ft h e ma r ea c c e p t e df o rm o n i t o ra n dd i s p a t c h e rc e n t e r m i d d l e w a r ei su s e di nt h i ss y s t e mw h i c hi sb a s e do nc l i e n t s e r v e rc o n s t r u c t i o n y h e c o m m u n i c a t i o nb e t w e e nd i s p a t c h e rc e n t e ra n dc a rt e r m i n a l ，a n di n f o r m a t i o no fc a r s e n c a p s u l a t e du n i f o r m l y i n an e ww a ya r ed o n e b y m i d d l e w a r e h i g h e r c o m m u n i c a t i o np r o t o c o li sa d o p t e db e t w e e nm i d d l e w a r ea n dc l i e n t a tt h es a m et i m e 。 f u n c t i o no fn a v i g a t i n ga n d t r a c k i n ga r ea d d e di nt h i ss y s t e m b e s i d e s ，t h es y s t e mh a s t h ef u n c t i o no fr e a lt i m em o n i t o r i n g ，d i s p a t c h e r , g u a r d i n g ，a l a r ma n ds oo n a n dw i t h t h a t ，t h ee f f i c i e n c yi si m p r o v e dr a p i d l y t h es y s t e mh a st h e a d v a n t a g e so fg r e a t c a p a c i t y , h i g he f f i c i e n c y , h i g hd e g r e eo fa c c u r a c ya n d l o wc o s t k e yw o r d ：p a t t e r nm a t c h i n g ，m i d d l e w a r e ，g p s ，g i s ，g p r s ，g s m ，i n t e l l i g e n t d i s p a t c h e r i i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的e o , n 本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：辛国 a d 吖年歹月占日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：牟穷 a 雌年多月? e l 第1 章引言 1 1 研究的背景 第1 章引言 1 1 1 我国城市出租车现状 随着国民经济和城市化的飞速发展，城市机动车拥有量不断攀升，带来了 交通需求量的剧增，各项矛盾日益突出，集中体现在交通拥挤、环境污染、交 通安全以及用地紧张等方面。城市交通问题己经成为影响城市功能正常发挥和 可持续发展的一个全局性问题。 在我国的大中城市的交通问题中，出租车占有举足轻重的地位。出租车作 为公交车的必要的有益的补充，在大中城市的发展是迅猛的。出租车严格来说 应该属于公共交通，但是其出行特性却不同于普通意义上的公交，也不同于私 家车的出行。在运量上它不如普通公交车，但是其出行灵活，它可以做到门到 门的服务，服务质量高于普通公交车；同时其出行的频率又大大高于私家车和 公家车。出租车的使用群体主要有：收入较高人士、外地来本市的出差人员、 携带笨重行李人员、交通弱势群体( 老、残、病) 、恶劣天气( 雨、雪等) 时的出行 人员等。 由于以上的优点，我国的出租车系统在大中城市中发展迅猛，据建设部副 部长黄卫在2 0 0 4 年1 1 月召开的“国际城市可持续能源发展市长论坛”上的讲话： 最近1 0 年是我国城市交通发展最快的十年，无论是公共交通的设施规模还是公 共交通的客运量都有非常大的提高。从1 9 9 3 年至2 0 0 3 年，我国出租汽车从1 9 万辆猛增到8 8 4 力辆，年均增长达到了1 6 6 。北京市现有出租车6 3 万辆，上 海市约有4 2 万辆，广州1 6 万辆，济南1 万辆，天津市出租车约3 2 万辆。 出租车行业的迅速发展，受到越来越多出行者的青睐，但同时也给城市综 合客运交通体系带来了新的问题和挑战。 一是成为城市交通阻塞的重要原因。由于出租车载客容量小，而且大多数 时候载的是单个乘客，行驶的时候每辆出租车所占的路面虽然只有公交车( 按 标准载客量为6 0 人的普通客车) 的一半，每个乘客所占的路面却是公交车中每 第1 章引言 个乘客的3 0 倍。2 0 0 2 年6 月安徽省蚌埠市交通调查表明，2 0 个交叉口中，出 租车交通量占总交通量超过3 0 的占了6 5 ，而且出租车交通量比例大于4 0 的路口均在城市中心或交通主干道，然而从居民出行方式调查结果得知，出租 车出行比例不到1 。 二是居高不下的出租车空驶率浪费了石油、加剧了拥堵、污染了城市环境。 由于目前我国绝大部分城市对出租车缺乏有效的调度管理，使得城市出租车的 空驶率居高不下。据统计，北京市的出租车空驶率接近于5 0 ，上海的出租车 空驶率为4 8 ，沈阳每天的空驶率都在4 0 左右，西安市的出租车的空驶率在 4 5 左右，济南的出租车空驶率为5 0 5 。这种无效益的行驶白白浪费了大量的 宝贵石油资源，既加剧了道路的拥挤，排放的尾气还污染了城市的环境，成为 当前城市大气污染的重要源头。 三是屡屡上调的出租车费排斥了广大乘客，影响了出租车行业的经营，带 来了恶性循环。受国际石油价格上涨的影响，国内成品油价格不断提价，为保 证经营利润，全国各城市的出租车普遍提高了起步价和每公里行驶费。高昂的 车费使众多的乘客望而怯步，低靡的乘坐率促使司机不断空驶揽客，大量的空 驶既加速了汽车的折旧又浪费了宝贵的能源，使得出租车的成本不断上升，形 成一个恶性循环。 交通拥挤、环境污染、能源短缺是当前世界各国面临的共同问题。解决交 通问题的传统办法是扩建新修道路，增加运营车辆等。但无论是哪个国家的大 城市可供修建道路的空问越来越小，增加运营车辆必然带来更大程度的拥挤。 交通经济学里有一条非常著名的定律“当斯定律”( d o w n sl a w ) 。这条定律的内 容是：“在政府对城市交通不进行有效管理和控制的情况下，新建的道路设施会 诱发新的交通量，而交通需求总是倾向于超过交通供给。”从这条定律我们可以 得出这样一个结论：在加大对城市交通建设投资的同时，必须强化对城市交通 的有效管理和控制，才能较好地解决城市交通中出现的各种问题。 1 1 2 智能交通发展状况 面对同益严峻的交通问题，国内外交通专家普遍认为：单纯靠修路来提高 交通供给方面的对策，很难从根本上解决城市交通中供求不平衡的矛盾，提出 了交通需求管l 里( t d m ) 的概念，明确了从供求两个方面解决城市交通问题的思 2 第1 章引言 想，这是在交通规划和解决城市交通问题指导思想上的一个转变。 同时，随着计算机技术、通信技术、电子控制技术的发展，人们意识到利 用这些新技术把车辆、道路、使用者紧密的结合起来，不仅能够有效解决交通 问题，而且对于环境保护、节约能源都有显著的效果，这就是综合运用各种科 学知识和技术手段，解决城市交通问题的智能交通系统( i n t e l l i g e n tt r a n s p o r t s s y s t e m ，简称i t s ) 。 i t s 在r 本、美国、英国和西欧发展得最快，在欧洲又称之为道路交通信息 通讯系统( r t t ) 。智能交通系统( i t s ) 最初是在以监控为主体的交通工程( 包括交 通管理) 基础上发展起来的，开始只进行道路和车辆智能化的研究，而现在己经 扩展到交通运输的全部过程及其有关部门。目前，其研究范围己逐渐涉及到铁 路、水运及航空等各种交通方式，旨在形成一整套为用户及交通管理部门提供 全方位交通信息的新型交通系统。 i t s 在国内的研究始于7 0 年代的城市交通控制系统的开发应用，如北京、 上海等城市建立的交通信号控制和电视监视系统、警车定位系统、交通地理信 息系统，以及交通事故、车辆和驾驶员档案等静态信息系统等。在某些省市还 建立了不停车自动收费系统和驾驶员i c 卡管理系统，这大大提高了城市交通网 络的通行能力。 出租车调度系统是智能交通系统( i n t e l l i g e n tt r a n s p o r ts y s t e m ) 的重要组成部 分，主要是利用g p s 、g i s 以及无线通讯技术实现对车辆的监控调度，并通过利 用g i s 中的相关信息，使车辆以最小的代价( 时间、距离或其他) 到达目的地，同 时也可以为用户提供其它信息服务。上世纪9 0 年代，随着计算机和无线电技术 的飞速发展，车辆定位和导航进入一个实用阶段，特别是美国全球卫星定位系 统( g p s ) 的建立，为全球范围内的用户提供了一种廉价、实用的定位手段，从而 为出租车调度系统的发展提供了很好的技术支持，使车辆定位与导航系统发展 进入一个高潮阶段。 国外对出租车调度监控系统的研究较早，9 0 年代中后期就己经有许多比较 成熟的产品投放到市场。目前，国际上流行的出租车调度系统是美国模块公司 的d i s p a t c h 。它是综合监控系统，软、硬件功能都很强，经过多年的发展，现 己能实现g p s 定位、对设备转台自动监控、自动派车等功能，己经在世界范围 内得到了广泛的使用。在西方很多发达国家的城市，如伦敦、巴黎、新加坡等， 在马路上很难找到一辆空驶的出租车，除非电话预约，或者在指定的停靠地点， 3 第1 章引言 很少能看到在街头打车的人，一般都是电话叫车。 我国从9 0 年代初期才开始出租车调度监控系统的研究，并在1 9 9 4 年至1 9 9 5 年形成第一个高潮。当时有上百家公司争相抢占g p s 车辆调度监控系统的市场。 然而由于当时的市场尚未形成，用户对出租车调度监控系统的需求还不强烈， 并且一些关键技术还不够成熟，所以成功者不多，很多公司亏损并退出该领域。 1 9 9 9 年7 月北京奇华通讯有限公司就采用g p s 卫星定位等高新技术建成北 京奇华出租汽车调度中心，一个有8 个信道，1 6 个调度终端的系统覆盖北京城 区和近郊区。安装一套设备综合成本要9 0 0 0 多元，而且使用的司机每月还要交 纳6 0 元的服务费。建网后三年只卖出了1 0 0 0 多台车载g p s 定位系统，相对于 当时北京7 0 ，0 0 0 多辆出租车的总数字，奇华公司花巨资建立的g p s 服务网确 实付出了沉重的代价。 北京市目前己经有部分出租车( 约几千辆) 安装了g p s 全球卫星定位呼叫系 统，预计到2 0 0 8 年之前完成所有出租车的g p s 监控系统的安装。在系统使用的 初期阶段，使用出租车的2 0 0 0 人次当中，只有1 次是电话叫车，在后来收取一 定的预定费后，叫车数更是急剧下降。另外，北京现有的调度系统中由于网内 车辆较少，无法保证高准确率地完成叫车服务，同时人们也已经习惯了站在街 头打车的方式，所以出租车调度系统并没有真正发挥作用。 上海是我国出租车管理水平较高的城市，2 0 0 5 年该市出租车行业才开始着 手“智能化营运”的项目，丌始有2 0 0 0 辆车进入装车试验，并在部分区域试运作， 预计到2 0 0 7 年底可以覆盖全行业4 2 力辆出租车。这一模式的核心就是依托先 进的通讯、计算机及网络技术，构建统一高效的行业信息服务( 调度) 中心，与出 租车车载系统、出租车站点组合成一个现代化调度运作网络，使全市出租车资 源达到最优化配置。但即使在上海，目前也只有1 4 以上的出租车业务能够通过 调度系统以电话叫车方式完成。 2 0 0 1 年厦门雅讯网络股份有限公司运作的“厦门出租车卫星定位报警调度 系统”，系统容量4 0 0 0 辆，每秒同时监控3 0 辆车。2 0 0 5 年1 0 月，四川移动成 都分公司、四川众一传媒、三零凯天通信，与四川( 中日) 出租汽车有限责任公司 签约，开始在成都市出租车上全面安装g p s 移动多媒体系统，这种系统安装运 行就可以实现乘客电话叫车功能。 综上所述，我国的出租车调度系统无论是在技术水平还是在应用方面和发 达国家相比还存在着较大的差距，尚处于初级阶段。 4 第1 章引言 1 2 课题研究的目的和意义 目前，造成出租车运营困境的根本原因在于：一是相对于中国老百姓的收 入水平，出租车的费用太高，使得许多有心“打的”的人，望“的”怯步，造成出租 车的客源偏少。二是在我们的许多城市，出租车的发展速度快于城市道路建设 速度，使得出租车成为交通堵塞的一个重要原因。三是缺乏高效的管理手段， 使得出租车的使用率偏低，空驶率畸高，运营成本居高不下。 同时，随着市场经济的发展，拜金主义的思潮泛滥，犯罪分子往往把价值 不菲的出租车作为抢劫的对象，司乘人员的生命、财产安全受到威胁。如何采 用现代信息技术，多快好省地解决出租车运营中存在的问题，成为当前出租车 运营管理的焦点。 近几年来，随着计算机技术、网络技术、移动通信技术、全球定位系统( g p s ) 、 地理信息系统( g i s ) 的发展和普及，建设基于多人合乘模式的出租车智能调度 管理系统成为可能。所谓“合乘”，是指两名或两名以上的乘客共同搭乘一辆出租 车，而且各方分别计算车费的一种租车行为。通过计算机调度系统“撮合”，实现 合乘出租车，对乘客、运营商和社会三方都具有很大的意义： 1 降低乘客费用和运营方成本。合乘方式下，乘客只需付单独租车时5 0 左右的费用( 根据合乘人员的多少而有所不同) 。车费显著下降有利于提高出租 车的乘坐率。由于乘坐率提高，加上计算机的调度，使得空驶的折旧和油耗减 少，有利于运营方降低成本。 2 增加运营方的收入。尽管单个乘客的费用降低了，但由于合乘时，司机 收取的是各乘客费用的总和，此值必将大于原来单独租车的费用。加上车费下 调，将会有更多的乘客选择出租车，势必增加运营商的收入。 3 缓解交通紧张局面。虽然各个城市都有大量的出租车，基本能够满足社 会需求，但在上下班和雨雪天气等情况下，仍存在“打的”难的问题。合乘方式的 推广，必将在一定程度上解决这一问题。 4 减少污染。合乘方式的推广，可以提高出租车的利用率，在不增加车辆 运行距离的情况下，提高了载客人数，降低了空驶率，也就相应减少了车辆对 环境的污染。 5 提高运营安全。出租车智能调度系统采用卫星定位和无线通信，可以准 确测定车辆位置，及时发出警报信息，显著提升了出租车的运营安全性。 5 第1 章引言 1 3 本文所做的工作 本文所做的工作是基于多人合乘模式的出租车智能调度管理系统的设计与 研究，其中包括： 1 - 监控调度中心的设计与研究。监控调度中心的设计与研究包括地理信息 系统g i s 的功能设计、监控调度功能设计、系统数据管理的设计，以及最短路 径、车辆跟踪定位、多人合乘的研究。 2 无线链路的设计。采用中间件技术，对g s m 和g p r s 通信模块进行设计 和研究，协议转换及客户端通信的实现方法。 3 各分系统的设计。包括车载终端的设计、乘客终端的设计、合乘计价器 的设计。 1 4 论文的组织结构 本文首先介绍了基于多人合乘模式的出租车智能调度管理系统所涉及的相 关知识，对交通分配、g p s 、g s m 、g p r s 及g i s 等技术进行了阐述，然后对基于 多人合乘模式的出租车智能调度管理系统的总体结构进行了设计，引入了中间 件技术，对系统具备的功能及功能的实现进行了设计和研究，全文的具体组织 结构如下： 第一章：绪论。介绍了与本文研究有关的背景知识、发展现状、主要研究内 容及论文组织结构。 第二章：出租车智能调度系统的关键技术概述。对基于多人合乘模式的出租 车智能调度管理系统所涉及到的相关技术( 交通分配模型、地理信息系统、无 线电定位以及中间件技术) 作了介绍。 第三章：出租车智能调度系统总体设计。提出了基于多人合乘模式的出租车 智能调度管理系统的总体设计思想及工作流程，设计了总体结构，阐述了车载 终端、乘客终端、合乘计价器的设计原理。 第四章：无线通讯系统的设计与研究。对集群无线电通讯、g s m 、g p r s 三种 无线通讯方式进行了分析比较，引入了中间件的概念，阐述了中间件的功能设 计方法，以及g p r s 、g s m 短消息通讯模块的实现方法。 第五章：监控调度中心的设计与研究。设计了系统软件的结构和功能，并对 6 第1 章引言 其实现方法进行了研究。 第六章：三个关键技术的解决。对基于多人合乘模式的出租车智能调度管理 系统中的三个关键技术( 最捷路径、车辆跟踪、多人合乘) 提出了合理可行的 实现方法。 第七章：结论与展望。对全文进行了总结。 7 第2 章出租车智能调度系统的关键技术概述 第2 章出租车智能调度系统的关键技术概述 基于多人合乘模式的出租车智能调度系统应用了交通分配模型、地理信息 系统( g i s ) 、中间件、无线电通讯与定位技术。 2 1交通分配 所谓交通分配是指将各分区之间出行分布量分配到交通网络的各条边上去 的工作过程，通常称为t a p ( t r a f f i ca s s i g n m e n tp r o b l e m ) 。交通分配模型是本方 案设计的理论基础。 2 1 1交通均衡问题 为方便以后的讨论，有关交通网络的一些相关定义如下： 定义2 1路段：交通网络上相邻两个节点之间的交通线路称作“路段”。 定义2 2 路径：交通网络上任意一对节点之间的一串连通的路段的有序排 列叫作这对节点之间的路径。一对节点可以有多条路径。 定义2 3 最短路径：一对节点之间的路径中总阻抗最小的路径叫“最短路 径”。一对节点之间的最短路径也可能不止一条。 定义2 4 交通阻抗：交通网络上路段或路径之间的运行距离、时间、费用、 舒适度，或这些因素的综合。具体到不同交通网络其含义随人们的关注点不同 而有所偏重。 如果两点之间有很多条路线可供出行者选择，那每个出行者自然都选择最 短路径。但随着这两点之间交通量的增大，其最短路径上的交通流量也会随之 增加，增加至一定程度之后，这条最短路径的走行时间就会因为拥挤或堵塞而 变长，以至长过次短路径的走行时间，于是就有一部分道路利用者会选择次短 路。随着次短路径上交通流量的增加，一部分道路利用者就会选择次次短路。 如此循环，两点之间的所有道路都有可能被利用。 如果所有的道路利用者都准确知道各条道路所需的行走时间，并选择走行 时间最短的道路，最终两点之间被利用的各条道路的走行时间会相等。没有被 利用的道路和走行时间会更长，这种状态被称之为道路网的均衡状态。1 9 5 2 年 8 第2 章出租车智能调度系统的关键技术概述 w a r d r o p 给这种均衡状态下了准确定义。 实际道路网中一般有许多对节点，每对节点之间的各条路径都是由很多独 立的路段组成，由这些独立的路段又可组合成许多条不同的路径，因此实际道 路网的每对节点间都有很多条路径。另外，各对节点问的路径也互相重叠。因 此，实际道路网的均衡状态是非常复杂的。由于这种复杂性，从1 9 5 2 年w a r d r o p 提出道路网均衡的概念和定义之后，如何数学描述和求解这个均衡问题成了一 个难题。1 9 5 6 年，b e c h m a n n 等提出了描述这个均衡问题的一个数学规划模型。 经过2 0 年之后，即1 9 7 5 年才由l e b l a n c 等学者设计出了求解b e c h m a n n 模型的 算法，从而形成了现在的实用解法。w a r d r o p 原理- - ，b e c h m a n n 模型- - l e b l a n c 算 法这三点突破是交通分配问题研究的三个里程碑，也是现在交通分配理论的基 础。 w a r d r o p 的道路网交通均衡的准确定义是： 定义2 5 在道路网的利用者都知道网络的状态并试图选择最短路径时，网 络会达到这样一种均衡状态，每对节点之间各条被利用的路径的走行时问都相 等而且是最小的走行时间，而没有被利用的路径的走行时间都大于或等于这个 最小的走行时间。 这条定义通常称为w a r d r o p 的第一原理。 在交通规划中，把使用w a r d r o p 原理的模型称为“均衡模型”，不使用w a r d r o p 原理的模型叫“非均衡模型”。 2 1 2 全有全无分配方法 全有全无分配方法是一种非均衡分配方法。 定义2 6 设路段的阻抗为常数，即假定起先时间不受路段上流量的影响， 一次将一个p a 点对的出行分布量全部分配到它们之间的最短路径上去的方法叫 做“全有全无分配方法”。该法又叫“最短路径分配法”，或“o 1 分配法”。这是一 种最简单的分配方法，是其它分配方法的基础。 全有全无分配方法认为出行时间与流量没有关系，即交通流量对阻抗没有 影响。对于交通网络，如城市轨道交通网，这种假设是基本合乎实际情况的。 但另一些交通网络就不是这样的。有些交通网络上流量越大，阻抗越小。如公 交车上乘客量的多少与公交车的速度没有关系，但是公交线路上乘客流量越大， 9 第2 章出租车智能调度系统的关键技术概述 可能开行的公交车辆越多，从而发车频率就越大，乘客在各站点的候车时间就 越小，整个出行时间也就越小。对于另一些交通网络，如公路网和城市道路网， 情况恰好相反，由于路段上容量( 通行能力) 是有限的，路段上的车辆越多，拥挤 程度加大，车辆速度降低，从而行驶时间就会增加。这样一来，流量越大，阻 抗也越大。目前城市中的出租车出行就是这种情况。 2 1 3 w a r d r o p 第一原理 在2 1 1 节中，我们曾介绍过交通网络的w a r d r o p 均衡原理，1 9 5 6 年 b e c k m a n n 提出了一种满足w a r d r o p 均衡原理的数学规划模型，正是这个数学规 划模型奠定了研究交通分配问题的基础。后来的许多分配模型，都是在b e c k m a n n 模型的基础上扩展得到的。下面我们介绍b e c k m a n n 的交通分配数学模型。 首先，我们介绍模型中使用的变量和参数。 x 。：路段a 上的交通流量，它们组成的向量为x = ( ，x 。，) ： f 。路段a 的交通阻抗j ，。( x 。) ：路段a 的以流量为自变量的阻抗函数j 疗：点对佛删的第k 条路径的交通流量，其向量为：厂= ( ，劈，) c f ：点对佛删的第k 条路径阻抗j u 。：点对伍砂间最短路径的阻抗，即最小阻抗，所组成的向量为“= ( ， 。，) ： 觋：路段一路径相关变量， 形。：点对向赃间的所有路径的集合j 。f1 ，如果路段口在( r s ) l f l j 第k 条路径上； d a ，k2 10 ，其它情况 饥：点对佛北问的翩交通量。 其次，我们用数学语言直接表达w a r d r o p 均衡原理。该原理的内容是： 在交通网络达到均衡时，所有被利用的路径具有相等而且最小阻抗，未被 利用的路径与其具有相等或更大的阻抗。 根据上述定义，可以写出( 以下各式对v r ，s ，v k 畈成立) ： c k “。 ( 2 1 ) f f 0 ( 2 2 ) 1 0 第2 章出租车智能调度系统的关键技术概述 c ：2 ur ；jf 0 = 0 容易证得，以上三式等价于： c 女i s u 。 嚣2 0 ：苌- - r 、= 0 ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) 厅和c ? 都是路径的参数。另外还有一组参数，那就是路段的参数：x 。和，。这两 组参数存在密切的关系，那就是： 路段上的流量是由各个p a 点对间的途经该路段的路径的流量累加而成，即： 矗= 瞄 v a ( 2 7 ) r sk e wr s 路径的阻抗虑等丁它途经的各个路段的阻抗之和： = 乞( ) 啄 ( 2 8 ) b e c k m a n n 提出的数学规划模型是： m i n z ( x ) = r 乞( w ) 咖 ( 2 9 ) s j 疗= q 。门r ，s q 1 0 ) k 疗0 ，v r ，s( 2 1 1 ) 其中，x a = 斤吩 v a ( 2 1 2 ) ，jk 模型中约束条件( 2 1 0 ) 是“出行量守衡”，即任意点对间的出行分布量等于它 们之间各条路径上流量之和。这是易于理解的。但模型的目标函数却很难作出 直观的物理解释。然而，又可以通过数学推导，证明它与w a r d r o p 均衡原理是一 致的，这正是该模型的绝妙之处。 b e c h m a n n 模型是建立在w a r d r o p 均衡原理之上的，其中的核心是：交通网 络的用户都试图选择最短路径，而最终使被选择的路径的阻抗相同且为最小， 从而达到一种均衡状态。因此又称这种均衡状态为“用户均衡状态( u s e r e q u i l i b r i u m ) ”，这个原理又称作“用户最优原理”，简称为u e 。 2 1 4 w a r d r o p 第二原理 除了“用户最优原理”外，w a r d r o p 还提出了另一个原理系统最优原理。 第2 章出租车智能调度系统的关键技术概述 定义2 7 在交通网络中的交通量应该按某种方式分配，以使网络中所有交 通元的总阻抗最小。这种原理称为系统最优原理。 为了区别起见，用户最优原理称为w a r d r o p 第一原理，系统最优原理称为 w a r d r o p 第二原理。 第一原理反映了用户对路径的选择的行为准则。我们知道，任何系统中的 有行为选择能力的个体总是以自己利益最大化来决定自己的行为。因此该原理 其实正是反映了交通网络中的用户的实际选择出行路径的情形，按b e c h m a n n 模 型和f w 算法计算出来的结果也正是实际交通网络上的交通分配结果。而第二 原理反映的则是系统的管理者的主观愿望，一般情况下它与交通网络上的实际 交通分配情况存在差距。但是它可以作为对系统的评价指标，为管理者提供一 种决策方法。 系统最优原理比较容易用数学规划模型来表示，其目标函数是网络中所有 用户总的阻抗最小。约束条件是用户均衡模型相同。 m i n ：z ( x ) = 乞( 屹) a s l 嚣= qr s 门r ，s k 0 ，v r ，s ，k 其中，x a = 吩 v a r s七 ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) 该模型称为系统最优模型，简写作：s o ( s y s t e mo p t i m i z a t i o n ) 。相应地， b e c k m a n n 模型简为：u e ( u s e re q u i l i b r i u m ) 。 2 1 5 随机用户均衡分配 在2 1 3 节中研究的均衡分配问题是一种极理想情形下的u e 问题，称之为 基本的u e 问题。但实际上，由于交通网络的复杂性和路段上交通状况的多变性， 以及各个出行者主观判断的多样性，某节点对之问不同出行者所感知的最短路 径将是不同的、随机的，因此这些出行者所选择的“最短路径”不一定是同一条， 从而出现多路径选择的现象。关于它的交通分配叫做“多路径分配”，或“随机分 配”。我们知道随机分配其实是一种非常常见的现象。将均衡的概念引入随机分 配之中，形成随机用户均衡分配的模型和算法。随机用户均衡分配简记为 1 2 第2 章出租车智能调度系统的关键技术概述 s u e ( s t o c h a s t i cu s e re q u i l i b r i u m ) ，定义是： 定义2 8 交通网络中每个用户都认为自己所选择的路径是“阻抗”最小的路 径，再没有用户相信能依靠单方面改变路径，可以减少其阻抗。在这种选择行 为下交通网络所达到均衡称为随机用户均衡。 应该注意，定义中的“阻抗”是用户的感知阻抗，是一个随机变量：一个用户 所感知的最小阻抗不一定就是真正最小阻抗路径；某对节点x c ( r , s ) 之间所有已被 选用的路径也并不一定有相同的实际阻抗。其中某条路径k 被选中的概率就是 其感知阻抗在( r ，s ) 间各条路径的感知阻抗中为最小的概率。设此概率为节，则 路径七上的流量为 嚣= q ，醭= qr ；p r 蜒：c ? ，v l 、)q 1 7 、) 对应于s u e 的数学规划模型是 m ，i n ：z ( x ) = 一吼s c r s ( x ) 】+ 乞( ) 一r 。t o ( w ) d w ( 2 1 8 ) 其中， s k ”( x ) 】- e m i n r c ”( x ) 】 ( 2 1 9 ) 是以各路段实际阻抗为条件的感知阻抗的数学期望，称作“期望感知阻抗”： c ”( x ) = ( ，c f ( x ) ，) 是( r ，s ) 间各条路径的实际阻抗组成的向量；c f 是( r ，s ) 间第k 条路径的感知阻抗；e 是数学期望符号。 2 1 6 交通分配模型的指导意义 根据w a r d r o pu e 平衡模型，出租车出行应该选择最快捷的路径出行，但是 由于现有的里程表计费模式是网络距离最短制模式，乘客往往选择最短路出行， 这并不满足交通平衡规律。不仅造成了u e 与系统最优相悖的情况，而且也造成 了时间最捷与几何最短路出行的不一致，由此加剧城市交通的压力，造成拥挤 或阻塞。如果对出租车这一现象不加以解决，那么不但不可能达到系统最优的 状态，而且连用户平衡的合理模式都实现不了，形成的往往是全有一全无的羊 群效应不合理状态。如何利用用户平衡出行达到系统最优网络状态是交通管理 的主要目的。随着信息技术的发展，我们可以将基于多人合乘模式的出租车智 能调度管理系统与交通网络平衡理论和谐地结合起来，协调好司机与乘客的关 系，缓解道路承载能力，极大地减轻交通拥挤或阻塞，保证路网通行顺畅，使 1 3 第2 章出租车智能调度系统的关键技术概述 人、车、路达到一种最优的平衡状态。 2 2 地理信息系统 2 2 1 地理信息系统概念 地理信息系统( g e o g r a p h i c a li n f o r m a t i o ns y s t e m ，简称g i s ) 是一种将空间位 置信息和属性数据结合在一起的系统，是一种为了获取、存储、检索、分析和 显示空问定位数据而建立的计算机化的数据库管理系统( 1 9 9 8 年，美国国家地理 信息与分析中心定义) 。这里的空间定位数据是指采用不同方式的遥感与非遥感 手段所获得的数据，它有多种数据类型，包括地图、遥感、统计数据等，他们 的共同特点都有确定的空间位置。地理信息系统的处理对象是空间实体，其处 理过程正是依据空间实体的空间位置和空间关系进行的。 地理信息系统是一种决策支持系统，它具有信息系统的各种特点，地理信 息系统与其他信息系统的主要区别在于其存储和处理的信息是经过地理编码 的，地理位置及与该位置有关的地理属性信息成为信息检索的重要部分。在地 理信息系统中，现实世界被表达成一系列的地理要素和地理现象，这些地理特 征至少由空间位置参考信息和非位置信息两个组成部分。g i s 是用于处理地理数 据的应用系统，它至少应该包含输入输出、数据库管理系统和分析工具三个具 有不同功能，但又相互依存和相互作用的组件构成。 地理信息系统的定义是由两个部分组成的。一方面，地理信息系统是一门 学科，是描述、存储、分析和输出空间信息的理论和方法的一门新兴的交叉学 科：另一方面。地理信息系统是一个技术系统，是以地理空间数据库( g e o s p a t i a l d a t a b a s e ) 为基础，采用地理模型分析方法，适时提供多种空间的和动态的地理 信息，为地理研究地理决策服务的计算机技术系统。 地理信息系统的外在表现为计算机软硬件系统：其内涵却是由计算机程序 和地理数据组织而成的地理空间信息模型。当具有一定地理学知识的用户使用 地理信息系统时，他所面对的数据不再是毫无意义的，而是把客观世界抽象为 模型化的空间数据。用户可以按应用的目的观测这个现实世界模型的各个方面 的内容，取得自然过程的分析和预测的信息，用于管理和决策，这就是地理信 息系统的意义。一个逻辑缩小的、高度信息化的地理系统，从视觉、计量和逻 1 4 第2 章出租车智能调度系统的关键技术概述 辑上对地理系统在功能上进行模拟，信息流动以及信息流动的结果，完全由计 算机程序的运行和数据的变换来仿真。地理学家可以在地理信息系统支持下提 取地理系统各不同侧面、不同层次的空间和时间特征，也可以快速地模拟自然 过程演变成思维过程的结果，取得地理预测或“实验”的结果，选择优化方案，用 于管理与决策。 一个完整的g i s 主要由四个部分构成的，即计算机硬件系统、计算机软件 系统、地理数据( 或空间数据) 和系统管理操作人员。其核心部分是计算机系统( 硬 件和软件) ，地理数据反映g i s 地理内容，而管理人员和用户则决定系统的工作 方式以及信息表示方式。 2 2 2 地理信息系统的发展历史及现状 1 地理信息系统的发展历史及现状 g i s 技术起源于本世纪5 0 年代地理学的定量革命，并脱颖于机助制图技术。 当时定量地理学随着统计方法和计算机的介入，正在着手解析空问分析方面的 探讨，并开始了机助制图的研究。g i s 的发展依赖于计算机技术的发展，尤其是 计算机图形学的发展。g i s 萌芽于2 0 世纪6 0 年代初，是由加拿大的r o g e r 提出 的。7 0 年代，美国人口调查局为g i s 技术的发展奠定了基础，它们把数学中的 一个分支一一拓扑学用于人口统计中，并成为地图学的新方法，即用点、线、 多边形来描述地图特征、边界和面积，并使之与现实世界中的空间实体一一对 应。用拓扑学原理建立的数字图形文件中包含了拓扑信息，通过它们可以确定 地图中各特征之间的相邻和连接关系，为用数字和数学方法进行地图研究提供 了时髦的空间分析方法。相对于早期仅仅提供了对空间特征和边界图形跟踪的 “面条”文件来说，这些文件有很大的进步，因为用拓扑结构文件不仅降低了数字 图形文件的大小，同时也促使了地理基础文件二元独立地图编码系统 f g b f d i m e ) 的发展。目前g b f d i m e 系统在拓扑集成地理编码参照t i g e r 中 仍然使用，并是当今许多城市g i s 系统中地理数据库的主要技术。 g i s 技术成熟于8 0 年代，伴随工作站和微机的出现，计算机软硬件的成本 迅速降低，功能不断增强，同时随着关系数据库管理系统( r d b m s ) 的广泛使用， 使计算机制图系统和g i s 成本也开始下降。同时，对计算机制图与g i s 的区别 也有了统一的认识，认为除了机助制图功能外，g i s 还具有空间分析功能，它应 1 5 第2 章出租车智能调度系统的关键技术概述 该是一个综合系统，可以通过其软件对关系数据库管理系统( r d b m s ) 以及地理 属性数据进行控制，允许对数字图形文件进行解析分析。这样，空间分析功能 便成了g i s 的主要特征。尽管拓扑学在数字地图文件中的应用，为g i s 中空间 数据库的建立奠定了基础，但许多地理空间分析功能仍然只能通过诸如多边形 叠加等图形方法实现，即用传统上数字图形文件的矢量和栅格格式进行。但由 于这两种格式受不同系统的限制，在空间应用上很难形成统一的分析方法，并 存在着一定的数据转换误差，所以最近g i s 应用领域开始引进诸如专家系统和 面向对象等技术方法，以便形成一种统一的空问数据分析格式。当然，这一问 题还有待进一步探讨。销售商对g i s 的发展也起了很大的推动作用，他们最初 只提供计算机制图系统，然后加了空间分析模块，使其软件系统具有g i s 功能， 这种转换在桌面制图软件包中尤为明显。目前，仅美国从事g i s 产业的公司约 有1 6 0 多个，他们提供包括数字化、数据转换和专业应用方面的不同服务。其 中环境系统研究所( e r s i ) 和i n t e r g r a p h 公