导言
在大大都国家，出租车都是一种非常遍及和快捷的交通工具。大都发达国家建设了完善的出租车调度体系，完结了出租车高效运营，如美国，电话预定和站点候客的出租车运营方法占98％，“路抛式”仅占2％；在伦敦、巴黎、新加坡等发达国家城市，除非电话预定，或许在指定的停靠地址，不然很少能看到乘客在街头打车，这大大进步了公共交通资源的运转功率。可是在我国的大大都城市，依然以乘客街头叫车为主，尽管部分城市现已完结了出租车装置GPS设备和实时记载出租车方位信息，可是并没有很好地运用这些GPS方位信息为出租车调度服务，导致许多出租车GPS体系成为铺排。为了进一步进步我国的出租车调度体系的运转功率和进步GPS体系的有用性，很有必要研讨一种结合GPS/GIS技能的快速高效出租车调度体系。
本文规划和完结了一种新式的出租车调度体系，该体系经过改善当时调度体系的叫车方法，并提出依据网格的出租车调度算法，该算法结合通讯渠道上传的出租车GPS方位信息和GIS体系网格信息把出租车分组，完结小组内及小组间出租车高效协作和调度，很大程度上进步了出租车的调度功率。
1 体系规划
本体系包含三个部分：出租车调度终端、通讯渠道和调度中心。调度终端是依据三星S3C2440硬件渠道和WINCE操作体系的智能嵌入式设备，完结了与调度渠道的通讯和现场智能操控；调度终端完结GPS数据的搜集、上报和调度信息的显现；通讯渠道供给精确、高效的信息传输功用；调度中心完结出租车快速调度以及依据GIS的车辆实时监控功用。
1.1 出租车调度终端规划
出租车调度终端在硬件上包含两部分：依据三星S3C2440的体系板和依据VK3224的设备扩展板。体系板和扩展板之间经过SPI接口进行通讯。体系板包含：
S3C2440 ARM9中心处理器、存储器FLASH、SDRAM、电源办理器材、RS232、I/O口空载标识灯接口及上报乘客信息按钮等。接口板包含：VK3224、GPS模块、GPRS模块和RS232等。此调度终端在规划上添加了一个出租车司机上报乘客方位的按钮，其作用是行进在马路上的每个出租车司机都能够上报在路上发现的乘客方位信息，体系收到信息就会调度最近的空载出租车前来服务。
终端的硬件结构如图1所示。
出租车调度终端在软件规划上选用通明通道供给牢靠的数据传输层。通明通道是经过GPRS上面封装TCP/IP协议和服务器进行通讯，当主站操控终端上某个串口设备的时分，将主站发送的数据包中加载串口数据，数据包传输到了终端后，终端将这些串口数据直接发送给对应的串口设备，当串口设备回来数据后，体系将这些数据加载在TCP/IP数据包上，经过GPRS发送到主站，在主站应用层看来和直接操作串口没有差异。调度终端和服务器之间GPS方位信息上传，上报乘客信息，调度指令下发等都是经过通明通道完结的。调度终端软件规划图如图2所示。
1.2 通讯渠道
为了完结渠道和出租车的通讯以及搜集乘客叫车信息，通讯渠道包含M2M通讯模块、短信渠道和呼叫中心三个模块。
（1）M2M通讯模块完结出租车和调度中心的通讯功用，详细包含：出租车方位上传、路旁边乘客方位上传、调度中心指令下发等。M2M通讯模块运用依据GPRS网络上的TCP/IP技能，服务器端选用Windows渠道的完结端口（IOCP）技能，然后确保单个服务器能一起接入很多出租车调度终端（大于5000台）。完结端口的最大长处在于其办理海量衔接时的处理功率，经过操作体系内核的相关机制完结I/O处理的高功率，因为出租车调度进程中衔接量巨大，且每个衔接上收发的数据包比较小，一般只要几k乃至不到1k的字节，因而很合适运用完结端口技能。
（2）短信渠道和呼叫中心模块完结乘客和调度中心之间的通讯，首要功用是乘客方位和打车恳求搜集。短信渠道担任接纳短信调度的短信，再由调度中心剖析短信内容，完结短信调度。呼叫中心担任电话链路，话务员和体系依据来电内容运用调度中心模块完结电话调度。
1.3 调度中心规划
调度中心分为前台应用程序和后台服务程序。
前台应用软件选用B/S架构，首要包含：体系办理、注册办理和调度办理三个部分，
（1）体系办理包含：部分办理、用户办理、人物办理和权限办理等；
（2）注册办理包含：固定电话注册、手机注册。固定电话注册完结固定电话和单个固定叫车方位的相关绑定，如酒店、公司等，经过GIS体系记载该方位的经纬度信息；手机短信注册完结手机号码和几个固定叫车方位的绑定，每个绑定有一个标签短信替代，一起将每个叫车方位在GIS体系中的经纬度信息记载下来。
（3）调度办理包含：司机合作调度、话务员调度、注册电话调度、短信调度等模块。
后台服务程序选用C/S架构，将通讯渠道所搜集到的出租车GPS方位信息和乘客GPS方位信息联系起来，经过下节所讲的依据网格的调度算法完结归纳调度，调度渠道和通讯渠道是一个密切联系的模块，详细联系如图3所示。
图3 调度体系全体架构（拜见右栏）
2 体系要害模块规划
2.1 叫车方法规划
国内外现有出租车调度体系的叫车方法首要分为两种类型：一是乘客打电话陈述自己的方位，调度员或话务员在GIS地图上标示乘客方位；二是乘客触发TAXI站点应招按钮叫车。
本体系在原有方法的基础上添加和改善了叫车方法。
1）在调度终端上添加一个陈述乘客方位按钮，当出租车满载期间在路上行进时如若遇到路旁边等车乘客就触发此按钮，完结出租车司机实时上报乘客方位，此方法表现了一种“我为人人，人人为我”的思维，这种合作协作的查找，扩展了查找乘客的空间规模。
2）在GIS地图中事前注册搭车地址，将该地址的经纬度信息与固定电话号码绑定，乘客用绑定的固定电话拨打调度中心，调度中心即可确认拨入用户的叫车方位，完结电话调度。这样，注册的固定电话（包含：家庭固话和公用电话亭电话等）都等价于出租车应召站点，这种叫车方法，调度中心无须人工参加，体系主动完结调度。
3）短信叫车，乘客事前注册几个自己常常打车的地址，比如说家、公司等，然后将该地址的经纬度信息、手机号码和方位标签相关，乘客需求叫车时发送事前注册好的方位标签短信，调度中心即可确认叫车乘客方位，然后完结短信调度。这三种叫车方法，调度中心端无须调度员人工干预，主动调度，便利乘客，节约资源。
2.2 依据网格的调度算法
现有的出租车调度中心大多规划为人工服务形式，首要调度中心不断搜集在体系中注册的出租车的状况，然后将为空载状况的出租车依照先进先出准则送入一个行列；最终关于每个在线预定的乘客恳求，调度员会依照自己以往的经历，人工确认最便利的一辆出租车，假如一起有多个出租车满意恳求，就依照先进先服务的方法前去服务，这种方法人工成本较高，且服务质量难以进步。
本体系抛弃人工服务方法，选用体系主动调度方法。
本调度服务程序选用依据网格的出租车调度算法，该算法详细进程如下：
（1）区分城市网格。在GIS地图上依据城市巨细，用恰当的矩形框把城市掩盖，获取矩形框对角线的经纬度信息：左上角经纬度值为（a,b）、右下角经纬度值为（c,d）；结合城市出租车数量确认网格数（M×N）。
城市出租车总数为Tsum，出租车空载率为Pec，空载出租车数为Tec=Pec×Tsum。选取网格数约等于空载出租车数Tec≈M×N，为了核算便利，一般M、N挑选为2的幂次数（如：16、32、64、128、……），一起为了确保网格长宽尽量挨近，所以挑选M/N比值尽量接近
值。
（2）区分城市经纬度数组。确认M、N值今后，把所选城市经度规模（a,c）均分为M份，存入经度数组citylongitude[M]中，相邻值距离为
；一起将城市纬度规模（b,d）均分为N份，存入纬度数组citylatitude[N]中，相邻值距离为
。区分经纬度数组是为了下面运用二分法核算出租车和恳求乘客地点网格。
（3）网格信息保护。经过区分城市经纬度数组确认网格数组CityGrid[M][N]，网格数据结构包含网格经纬度等基本信息，一起每个网格动态保护两个链表：网格空车链表和网格乘客链表。城市网格结构如图4所示。
a.网格空车链表初始化。将当时体系中的一切空载出租车依据所在方位，经过二分法核算出租车所属网格，加载到对应网格空车链表中，因为网格空车链表需求依据出租车终端上报的状况信息实时调整，链表的增删操作较为频频，因而本体系中网格空车链表选用双链表结构。链表中的结点数据结构如表1所示。
表1 出租车数据结构
b.网格空车链表动态保护。依据出租车终端实时上报的状况信息，判别是否为空载状况，假如为空载，判别链表中该出租车是否为空载状况，假如为空载判别本次是否需求将出租车调整网格，假如链表中没有该出租车，依据上报的GPS方位信息核算所属网格，将该出租车刺进该网格空车链表中，空载状况核算结束。假如上报状况为满载状况，判别此前出租车是否为空载状况，假如为空载，将其从空车链表中删去，满载状况核算结束。详细处理流程图如图5所示。
未调度的乘客依据所在方位，经过二分法核算乘客所属网格，加载到对应网格乘客链表中，遵从“先恳求先服务”
准则，本体系中网格乘客链表选用链表行列结构，链表中的结点数据结构如表2所示。
表2 乘客数据结构
（4）乘客恳求调度。经过第（3）步将出租车和乘客依照网格分组，单个网格中假如网格乘客链表不为空，从链表挑选一个乘客，一起判别该网格中空车链表是否为空，假如不为空，从该链表中挑选一个空车去满意该乘客恳求；假如该网格中空车链表为空，挑选相邻网格中空车链表中的空车来满意乘客恳求，直到查找到空车停止。查找到空载出租车后把乘客GPS方位和乘客详细文字描述方位发送给出租车终端，发送成功后，将乘客从网格乘客链表中删去，一起将对应的空车从网格空车链表中删去。至此，调度进程完结。
3 模仿与功能测验
咱们经过一台服务器（DELLR710机架式服务器，XEON E5504×2JSDM/4G内存条）作为调度服务器，模仿城市网格区分为64×64=4096的体系调度，一台PC机模仿10000台出租车数据上传GPS方位和状况信息，上传距离为10s，测验内容包含：出租车司机合作调度、电话调度、短信调度。经过模仿测验10000台出租车运转，调度服务器CPU运用率49%，证明此体系是高效可行的。
4 结语
本文依据GPS/GIS规划和完结了一种新式的出租车调度体系，该体系改善了现有出租车调度终端和叫车方法，并提出一种依据网格的出租车调度算法，完结出租车主动调度，最大极限地削减人工参加，经过模仿测验证明该算法高效有用。经过本体系能够有用下降乘客等待时间（CWT）和出租车空驶率（ECP），进步出租车体系运转功率。
