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

旧城等待， 2024-04-05 06:39 43阅读 0赞

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

## 一、总体说明 ##

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

输入一个乘客位置，在可以忍受的时间内输入一个乘客位置，在可以忍受的时间内 (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

#### 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框架。绘制路径使用的百度地图中的接口，绘制的是真实场景的路径，而不是路网的路径。