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

表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），提高出租车系统运行效率。