论文部分内容阅读
【摘要】本文利用移动智能终端技术和无线传感器结合高效的优化匹配算法提出一种出租车公共服务系统。通过移动智能终端的定位功能将乘客和司机的地理位置信息传输到服务器，服务器通过相关匹配算法的计算，为每个乘客匹配距离最佳的出租车，同时将乘客的地理位置信息发送给司机，解决了司机不知道目标乘客位置，而盲目空跑或消极等待的问题，节约了乘客的等待时间和出租车司机的空跑时间。
【关键词】出租车；移动智能终端；匹配算法
1.系统设计
1.1 系统总体结构
本系统有三个部分组成，分别为乘客客户端，司机客户端和服务器端，其中乘客客户端和司机客户端为移动智能终端的应用。
乘客客户端主要负责收集乘客地理位置及相关信息、向服务器发送数据以及与司机客户端的连接。
司机客户端主要负责收集出租车司机地理位置信息和空车信息、向服务器发送数据以及与乘客客户端的连接。
服务器端主要负责记录和分析两个客户端发送来的数据，通过相关算法计算出最佳配对组合，并将结果传送到相应客户端。
1.2 客户端
1.2.1 移动智能终端
移动智能终端是本系统的软件部分，成熟的移动智能终端应用开发技术为本系统的稳定性提供了一定的保证。
乘客客户端，通过移动智能终端的GPS模块或点击地图上的地点来获取乘客的地理位置信息。乘客点击打车后，通过英特网向服务器发送信息，同时接受服务器反馈的信息，其中包括司机的地理位置（实时更新）、计算出来的等待时间和与司机的通讯等相关信息。
司机客户端，通过移动智能终端的GPS模块来获取司机的实时地理位置信息，客户端得到来自空车牌传感器（具体见下节）的空车信息后，通过英特网向服务器发送信息，同时接受服务器的反馈信息，其中包括打车人的位置，与乘客的通讯等相关信息。同时，为了保证司机的行车安全，利用移动智能终端的语音交互，避免了司机在处理相关信息时，注视智能终端屏幕忽略了交通状况而产生的不安全因素。乘客的信息采用语音播报的方式，告知司机，司机可以选择性地通过屏幕查看更具体的信息。司机在操作上也可以通过语音告知智能终端，智能终端通过相关分析得到指令，进行操作。
1.2.2 空车牌传感器
空车牌传感器是系统的硬件部分，安装在空车牌上，方便司机更好地利用本系统。在不改变出租车空车牌原有结构的前提下在其外部增加一个小型蓝牙无线传感装置，与出租车司机客户端建立联系，借助司机对空车牌的放倒和立起来这两个必要的动作自动完成司机客户端向服务器发出空车或已载客的信息。
1.3 服务器模块
服务器是信息处理和交换的枢纽。它把从移动智能终端接收的地理信息及相关数据存储在数据库中，并通过相关算法计算出最佳匹配，将相关信息分别发送到匹配的乘客客户端和司机客户端进行处理和显示。
2.服务流程
服务流程如图2所示：
3.距离计算
在很多关于出租车管理调度系统中，采用直接利用经纬度信息，进行数学计算，这样固然方便、快捷，但是忽略了实际的交通状况，尤其是在如北京、上海等立交桥林立、交通状况复杂的大城市，仅利用经纬度进行计算距离就会造成一定程度上的偏差，无法达到最优的效果。除此之外，通过GIS软件也可以取得两点之间的距离。这样的方式的优点是获取的距离准确，缺点是会消耗一定的网络资源，需要一定的等待时间。
因此综合以上两点因素，和实际服务器关联匹配算法的设计，本系统根据不同场合，利用两种计算方法得出两个距离。
3.1 经纬度信息计算两点之间距离
利用数学知识结合半正矢理论，可以计算出两点之间的距离。公式如下：
R=地球半径（平均半径=6371公里）；
3.2 利用GIS软件获取距离
利用GIS软件的相关接口，即可得到两点之间的实际路程，将这个实际路程作为精确距离。
4.匹配算法
4.1 相关领域的研究背景
对于出租车调度问题相关算法的研究，大都是从数学理论出发，研究限制图上局内出租车的调度方案，而对于实际应用中复杂的交通状况和众多不可预测因素，这类研究仅具有指示意义。因此本文参考了上述研究的成果，提出一种基于实际交通状况的，在现有技术和数据下可行的、相对快速的算法。
4.2 算法设计
本算法首先假设打车的请求足够多，即在较短的时间内，可看作一个静态的最佳匹配问题。
将所有已知空车的地理位置集合记为，将所有已知需要打车乘客的地理位置集合记为。将上文中利用经纬度信息计算两点之间的距离，即粗略距离，记为，利用GIS软件接口计算的距离，即精确距离记为。将乘客的等待时间记为。将乘客对于空车的匹配权记为。
为需要通过实际检验而确定的参数。
（1）乘客在地点发出打车请求。
（2）以为中心，建立邊长为的正方形区域。
（3）若在集合中，存在多个，满足，且未曾与关联过，转入第（4）步；若在集合中，存在唯一，满足，且未曾与关联过，关联、，转入第（7）步；若不满足上面两个条件，则增加的边长，使得，若，则告知乘客目前没有适合车辆，否则，返回第（2）步。
（4）对于每个，计算，比较各个，得到，则为距离最近的空车。关联、。转入第（5）步。。
（5）对于已得到的，若存在除以外的关联，转入第（6）步；若不存在除以外的关联，等待时间后（为随着精确距离的增大而增大的函数），若仍无除以外的关联，则在集合、中，删除、，匹配、，匹配成功，算法结束；若在时间内建立了其他关联，则转入第（6）步。
（6）比较各关联的的权重，得： ，则为最佳乘客，其他乘客在除去返回第（3）步。
（7）在集合、中，删除、，匹配、，匹配成功，算法结束。
4.3 算法说明
在許多关于出租车智能公共服务系统的论文中，对于匹配算法部分，只提出通过经纬度信息计算最短距离的出租车，从而得到匹配。而本文引入等待时间以及匹配权是为了形成一个总体的最佳匹配，从而节约了出租车的总体空跑时间，同时也使得乘客的等待时间不会过长。
当然，本文提出的算法，是在打车的请求足够多的情况下，才能显示其优越性，而若打车请求较稀少，且请求地域较分散，则该算法则会降低整体的效率。所以，整个系统采用何种算法进行匹配，还需要得到实际的检验才能得到最后的结论。
同时，在本文提出的算法中的参数，也是需要通过实际检验，从而得出最优的结果。
4.4 算法用例
下面的例子，简单地说明了利用本算法进行匹配的效果。
①在北京邮电大学西门，有一位乘客发出了打车的请求，如图3中A点所示，称该乘客为乘客A，其他两个出租车图标表示该位置存在空车。（如图3所示）
②以A点为中心建立边长为a的正方形区域，此处a=1000M，发现没有空车处于该正方形区域内，因此扩大正方形区域的边长。（如图4所示）
③扩大正方形边长得到新的边长a，此处a=2000m，发现存在两辆空车都在正方形区域内。调用GIS软件的相关接口，得右侧出租车距离A的路程短，关联右侧出租车和A。（如图5所示）
④在A的乘客等待t时间中，右侧出租车出现另一关联乘客B，经比较得乘客A、B的权重得，B的权重较大，则取消A和右侧出租车的关联，乘客B进入乘客等待时间。（如图6所示）
⑤乘客A重新回到第③步，此时只存在右侧一个合适的出租车，匹配A与右侧出租车。算法结束。
5.结束语
本系统在现有的技术框架下，可以很好地解决乘客不易打车，出租车空跑时间长的问题，更好地分配出租车资源，提高整个出租车服务系统的效率，也一定程度地缓解了城市交通的压力。用移动智能终端作为整个系统的基础，符合当下的流行趋势，即集成化。同时，利用空车牌传感器感知空车牌倒立，在此处还可以添加人文关怀类的功能如，测量车内湿度、车内温度等，并通过移动智能终端提醒司机。该系统不仅为乘客出行提供方便，减少了出租车空跑的时间，也为城市交通的顺畅出了一份力量。
参考文献
[1]Karimi Hassan A，Tom Lockhart J.GPS-based tracking systems for taxi cab fleet operations[C].IEEE.VehicleNavigation&InformationSystemConference，Ottawa，1993：679-682.
[2]徐寅峰，王刊良，丁建华.限制图上的局内出租车调度与竞争算法[J].系统工程学报，1999，14（4）：361-365.
[3]傅丽叶.智能出租车方案与多人多车搭乘算法[J].微型机与应用，2003，1：42-45.
[4]曾翔.基于GPS的出租车动态管理系统设计[J].四川理工学院学报（自然科学版），2010，23（3）：341-343.
【关键词】出租车；移动智能终端；匹配算法
1.系统设计
1.1 系统总体结构
本系统有三个部分组成，分别为乘客客户端，司机客户端和服务器端，其中乘客客户端和司机客户端为移动智能终端的应用。
乘客客户端主要负责收集乘客地理位置及相关信息、向服务器发送数据以及与司机客户端的连接。
司机客户端主要负责收集出租车司机地理位置信息和空车信息、向服务器发送数据以及与乘客客户端的连接。
服务器端主要负责记录和分析两个客户端发送来的数据，通过相关算法计算出最佳配对组合，并将结果传送到相应客户端。
1.2 客户端
1.2.1 移动智能终端
移动智能终端是本系统的软件部分，成熟的移动智能终端应用开发技术为本系统的稳定性提供了一定的保证。
乘客客户端，通过移动智能终端的GPS模块或点击地图上的地点来获取乘客的地理位置信息。乘客点击打车后，通过英特网向服务器发送信息，同时接受服务器反馈的信息，其中包括司机的地理位置（实时更新）、计算出来的等待时间和与司机的通讯等相关信息。
司机客户端，通过移动智能终端的GPS模块来获取司机的实时地理位置信息，客户端得到来自空车牌传感器（具体见下节）的空车信息后，通过英特网向服务器发送信息，同时接受服务器的反馈信息，其中包括打车人的位置，与乘客的通讯等相关信息。同时，为了保证司机的行车安全，利用移动智能终端的语音交互，避免了司机在处理相关信息时，注视智能终端屏幕忽略了交通状况而产生的不安全因素。乘客的信息采用语音播报的方式，告知司机，司机可以选择性地通过屏幕查看更具体的信息。司机在操作上也可以通过语音告知智能终端，智能终端通过相关分析得到指令，进行操作。
1.2.2 空车牌传感器
空车牌传感器是系统的硬件部分，安装在空车牌上，方便司机更好地利用本系统。在不改变出租车空车牌原有结构的前提下在其外部增加一个小型蓝牙无线传感装置，与出租车司机客户端建立联系，借助司机对空车牌的放倒和立起来这两个必要的动作自动完成司机客户端向服务器发出空车或已载客的信息。
1.3 服务器模块
服务器是信息处理和交换的枢纽。它把从移动智能终端接收的地理信息及相关数据存储在数据库中，并通过相关算法计算出最佳匹配，将相关信息分别发送到匹配的乘客客户端和司机客户端进行处理和显示。
2.服务流程
服务流程如图2所示：
3.距离计算
在很多关于出租车管理调度系统中，采用直接利用经纬度信息，进行数学计算，这样固然方便、快捷，但是忽略了实际的交通状况，尤其是在如北京、上海等立交桥林立、交通状况复杂的大城市，仅利用经纬度进行计算距离就会造成一定程度上的偏差，无法达到最优的效果。除此之外，通过GIS软件也可以取得两点之间的距离。这样的方式的优点是获取的距离准确，缺点是会消耗一定的网络资源，需要一定的等待时间。
因此综合以上两点因素，和实际服务器关联匹配算法的设计，本系统根据不同场合，利用两种计算方法得出两个距离。
3.1 经纬度信息计算两点之间距离
利用数学知识结合半正矢理论，可以计算出两点之间的距离。公式如下：
R=地球半径（平均半径=6371公里）；
3.2 利用GIS软件获取距离
利用GIS软件的相关接口，即可得到两点之间的实际路程，将这个实际路程作为精确距离。
4.匹配算法
4.1 相关领域的研究背景
对于出租车调度问题相关算法的研究，大都是从数学理论出发，研究限制图上局内出租车的调度方案，而对于实际应用中复杂的交通状况和众多不可预测因素，这类研究仅具有指示意义。因此本文参考了上述研究的成果，提出一种基于实际交通状况的，在现有技术和数据下可行的、相对快速的算法。
4.2 算法设计
本算法首先假设打车的请求足够多，即在较短的时间内，可看作一个静态的最佳匹配问题。
将所有已知空车的地理位置集合记为，将所有已知需要打车乘客的地理位置集合记为。将上文中利用经纬度信息计算两点之间的距离，即粗略距离，记为，利用GIS软件接口计算的距离，即精确距离记为。将乘客的等待时间记为。将乘客对于空车的匹配权记为。
为需要通过实际检验而确定的参数。
（1）乘客在地点发出打车请求。
（2）以为中心，建立邊长为的正方形区域。
（3）若在集合中，存在多个，满足，且未曾与关联过，转入第（4）步；若在集合中，存在唯一，满足，且未曾与关联过，关联、，转入第（7）步；若不满足上面两个条件，则增加的边长，使得，若，则告知乘客目前没有适合车辆，否则，返回第（2）步。
（4）对于每个，计算，比较各个，得到，则为距离最近的空车。关联、。转入第（5）步。。
（5）对于已得到的，若存在除以外的关联，转入第（6）步；若不存在除以外的关联，等待时间后（为随着精确距离的增大而增大的函数），若仍无除以外的关联，则在集合、中，删除、，匹配、，匹配成功，算法结束；若在时间内建立了其他关联，则转入第（6）步。
（6）比较各关联的的权重，得： ，则为最佳乘客，其他乘客在除去返回第（3）步。
（7）在集合、中，删除、，匹配、，匹配成功，算法结束。
4.3 算法说明
在許多关于出租车智能公共服务系统的论文中，对于匹配算法部分，只提出通过经纬度信息计算最短距离的出租车，从而得到匹配。而本文引入等待时间以及匹配权是为了形成一个总体的最佳匹配，从而节约了出租车的总体空跑时间，同时也使得乘客的等待时间不会过长。
当然，本文提出的算法，是在打车的请求足够多的情况下，才能显示其优越性，而若打车请求较稀少，且请求地域较分散，则该算法则会降低整体的效率。所以，整个系统采用何种算法进行匹配，还需要得到实际的检验才能得到最后的结论。
同时，在本文提出的算法中的参数，也是需要通过实际检验，从而得出最优的结果。
4.4 算法用例
下面的例子，简单地说明了利用本算法进行匹配的效果。
①在北京邮电大学西门，有一位乘客发出了打车的请求，如图3中A点所示，称该乘客为乘客A，其他两个出租车图标表示该位置存在空车。（如图3所示）
②以A点为中心建立边长为a的正方形区域，此处a=1000M，发现没有空车处于该正方形区域内，因此扩大正方形区域的边长。（如图4所示）
③扩大正方形边长得到新的边长a，此处a=2000m，发现存在两辆空车都在正方形区域内。调用GIS软件的相关接口，得右侧出租车距离A的路程短，关联右侧出租车和A。（如图5所示）
④在A的乘客等待t时间中，右侧出租车出现另一关联乘客B，经比较得乘客A、B的权重得，B的权重较大，则取消A和右侧出租车的关联，乘客B进入乘客等待时间。（如图6所示）
⑤乘客A重新回到第③步，此时只存在右侧一个合适的出租车，匹配A与右侧出租车。算法结束。
5.结束语
本系统在现有的技术框架下，可以很好地解决乘客不易打车，出租车空跑时间长的问题，更好地分配出租车资源，提高整个出租车服务系统的效率，也一定程度地缓解了城市交通的压力。用移动智能终端作为整个系统的基础，符合当下的流行趋势，即集成化。同时，利用空车牌传感器感知空车牌倒立，在此处还可以添加人文关怀类的功能如，测量车内湿度、车内温度等，并通过移动智能终端提醒司机。该系统不仅为乘客出行提供方便，减少了出租车空跑的时间，也为城市交通的顺畅出了一份力量。
参考文献
[1]Karimi Hassan A，Tom Lockhart J.GPS-based tracking systems for taxi cab fleet operations[C].IEEE.VehicleNavigation&InformationSystemConference，Ottawa，1993：679-682.
[2]徐寅峰，王刊良，丁建华.限制图上的局内出租车调度与竞争算法[J].系统工程学报，1999，14（4）：361-365.
[3]傅丽叶.智能出租车方案与多人多车搭乘算法[J].微型机与应用，2003，1：42-45.
[4]曾翔.基于GPS的出租车动态管理系统设计[J].四川理工学院学报（自然科学版），2010，23（3）：341-343.