本文设计和实现了一种新型的出租车调度系统，该系统通过改进当前调度系统的叫车方式，并提出基于网格的出租车调度算法，该算法结合通信平台上传的出租车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），提高出租车系统运行效率。