基于GPS的新型出租车调度系统设计

度等模块。

　　后台服务程序采用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）步将出租车和乘客按照网格分组，单