使用路网数据完成数据库专题训练

使用路网数据完成数据库专题训练

一、总体说明

本次作业我实现的功能如下：

输入一个乘客位置，在可以忍受的时间内输入一个乘客位置，在可以忍受的时间内 (5 -10 秒)，返回不超过5 个有空位的出租车。所返回出租车与乘客距离不超过10km ，若没有合适的出租车，则返回空列表。

返回的所有出租车绕路距离不超过10km。

返回了最优的乘客送达顺序和车辆行进路线。

使用 Electron 框架设计了前端UI界面，可以设定和显示乘客信息、显示接送路径、显示出租车位置。

使用路网数据完成了大作业。

二、程序设计框架

2.1 数据

• 使用 data 文件夹下的数据即可。

• 其中出租车的 D1 数据是预处理好的，用于提高搜索速度。

• GTree 也是实现建立好并保存，用于提高每次加载的速度。

2.2 后端

在 src 目录。

2.2.1 数据结构

• struct Position 保存了路网节点 id 、经纬度数值，用来表示一个点。

• struct Car 保存了出租车的位置、车上乘客数量、每个乘客的目的位置。

• struct Cardist 保存了车辆编号，以及该出租车载当前乘客的绕路距离总和。

• 这里绕路距离总和的定义为：当前乘客与该车的 D2+D3-D1 与 D3-D4 之和，即两个绕路距离之和。

• 全局数据

包括 vector nodes 、 vector cars 、 vector D1 ，即路网节点信息、出租车信息、出租车的 D1 信息（预处理后直接读入）。

GTree	 使用来自于github的 GTree 框架：https://github.com/TsinghuaDatabaseGroup/GTree
1

2.2.2 搜索车辆

输入当前乘客所在位置的节点编号、目的地编号，输出最优出租车编号序列、每个出租车的最佳顺序。

其中，寻找最优出租车编号序列是通过一个递归函数暴力枚举寻找的。

2.2.3 与前端通信

2.2.3 TCP建立

使用了 Linux 的socket结构。其中，TCP的初始化信息为：

前端也建立类似的TCP，从而达到本机的数据通信。

2.2.3 数据格式转换

• TCP通信的数据格式为字符串。

• 由于C++的经纬度信息是浮点数，需要将浮点转化为字符串，然后交给TCP。

• 同理，TCP接收到的字符串信息也需要转为浮点数交给C++。

• 而为了减小误差，要求浮点数强制保留5位小数。

前端 使用 Electron 桌面应用框架，可以用javascript写桌面应用。其中地图使用了百度地图的javascript框架。绘制路径使用的百度地图中的接口，绘制的是真实场景的路径，而不是路网的路径。

算法

2.2.4 寻找车上乘客的最优送达顺序

使用递归来模拟深度优先搜索，搜索所有可能的送达路径，并找到绕路距离总和最小的顺序。

伪代码如下：

2.2.5 查找最优车辆

暴力枚举所有的车辆，找到所有满足绕路距离条件的车辆，保存到一个 vector 中，最终对 vector 进行排序，排序条件是绕路距离总和从小到大，选出其中 min(5, length of vector) 大小的车辆作为候选即可。

其中，寻找最短路径的函数调用了 GPTree 的 tree.search 接口。

搜索时剪枝如下：

若 D2>10000 ，跳过本次搜索；

若绕路距离不满足条件，跳过本次搜索；