TicketGo

问题描述

设计一个火车票订票系统，要求：

• 包含多车次
• 每一趟车次至少包含 N 个站点，N>10
• 每个站点之间的距离不同，费用也不同
• 用户订票可能为涵盖列车 N 个站点的任意区间（起始站点均匀分布）
• 设计一套出票策略确保单趟列车全程上座率最大，问题描述：

旅客的起点和终点是均匀随机分布的，因此如果不采用任何放票策略，线路中间的车站上座率会高于起始车站（可以验证），当旅客较多时很容易出现线路中间的站点由于短线旅客满座，导致从起点到终点的长途旅客无法买到车票，起始和终点附近的上座率低。设计一套简单的放票策略缓解这个问题，在购票人数较多时提高整体的上座率。

项目概述

本系统为基本的火车票订票系统。本系统采用 Server/Client 模式。当启动 Server 端后，您可以启动多个 Client 进行操作。Server 模拟了一个“线程池”实施异步工作，在一定程度上增加系统的并发能力及确保票在并发时不会同时售出。

本系统支持多车次、不同站点的车辆，查询余票、购票、退票、查看订单及查看总售票收入的功能。

同时，本系统在火车票售票时，对售票问题进行了研究，构建了售票的数据结构，尽可能地提高上座率。

火车票售票算法研究

订票的数据结构

本系统我设计的卖票模型描述如下：

假设某车次有 $N$ 个站点（分别是 $S_0$ 至 $S_{n-1}$），车辆一共可以载客 $M$ 人，则设计数组 train[N-1]，并初始化 train[0]~train[N-2]（即全部）均为 $M$；当某位旅客购买从 $S_i$ 至 $S_j$ 的车票时，执行以下操作（将 train[i] 至 train[j-1] 均减 1。）

for (int k = i; k < j; k++)
  train[k]--;

这样，当每次买票时，只需要检查 train[i] 至 train[j-1] 中任意一个值是否为 0，若为 0 则表示该段售罄，无法出票。

模拟实验

在实验中，我首先写代码模拟这个买票过程，查看结果。我首先设置站点数量 10 个、每辆车可载客 100 人，无数人尝试买票，买票的出发地及目的地是完全随机分布。以第一次因票售罄的订单为标志停止实验。以上述的数据结构存储，每次停止实验时，train 数组的值如下：

train[i] 的 i	0	1	2	3	4	5	6	7	8
模拟 1	59	27	16	2	0	10	15	44	67
模拟 2	63	35	17	0	5	12	22	45	62
模拟 3	60	40	17	3	0	10	20	45	66
模拟 4	54	22	11	6	0	5	10	24	58
模拟 5	57	38	8	1	0	10	28	41	67
模拟 6	65	41	27	0	4	7	15	36	66
平均数	59.7	33.9	16	2	1.5	9	18.4	39.2	64.3

将其图片绘制出来，可以发现其近乎是一个二次函数。使用二次函数进行拟合， $R^2=0.996$ 。因此，我们可以基本确定其为一个二次函数。

理论分析

当确定了其为一个二次函数后，我们可以接着试图寻找其公式推导。以小范围问题分析入手，首先假设有 5 个站点。因为起点和终点都是均匀随机分布的，那么我们可以用 $P$ 代表从任何一点到任何一点的概率。

假设有一个人购票，起点即第 1 个点，则其到 $S_2,S_3,S_4,S_5$ 的概率都是 $P$，我们仍然以本章第一节的数据结构为基础，假设其到各个点的概率。

train[i] 的 i	1	2	3	4
终点为 $S_2$	P
终点为 $S_3$	P	P
终点为 $S_4$	P	P	P
终点为 $S_5$	P	P	P	P

若所有人的起点均为第 1 个点，我们可以得到 train[1] 被减（有人旅程经过）的概率是 train[4] 的 4 倍。我们将这个结论推广到全部：

train[i] 的 i	1	2	3	4
起点为 $S_1$，终点为 $S_2$	P
起点为 $S_1$，终点为 $S_3$	P	P
起点为 $S_1$，终点为 $S_4$	P	P	P
起点为 $S_1$，终点为 $S_5$	P	P	P	P
起点为 $S_2$，终点为 $S_3$		P
起点为 $S_2$，终点为 $S_4$		P	P
起点为 $S_2$，终点为 $S_5$		P	P	P
起点为 $S_3$，终点为 $S_4$			P
起点为 $S_3$，终点为 $S_5$			P	P
起点为 $S_4$，终点为 $S_5$				P

根据规律，我们可以得到 train[1],train[4] 的被减（有人旅程经过）的概率是 $4P$， train[2],train[3] 的被减（有人旅程经过）的概率是 $6P$，再进行归纳，我们可以得到：

假设某车次有 $N$ 个站点（分别是 $S_0$ 至 $S_{n-1}$），train[M] 被减（有人旅程经过）的概率是： $$M(N-M)P$$ 因此，代入这个式子，我们可以得到，站点数量 10 个时，train[4] 售出的票数量应该是 train[1] 的 $$\frac{4(10-4)}{1(10-1)}=\frac{24}{9}$$ 代入上述模拟过程中，当 train[4] 的 100 张票全部售完时，train[1] 理论上应该还剩下 $100-100\times\frac{9}{24}=62.5$ 张票，和我们的模拟结果几乎一致。

对售票的优化

得到了这个公式，我对系统的售票优化过程为：

当有 $N$ 个站台，车的容载量为 $M$ 人时，我们在售票时，对起点 $S_k$ 至终点 $S_j$ 票，查看起点或终点哪个更靠近边缘站点，假设更靠近的为 $S_i$，则该票最多售出（张）： $$\frac{M(N-1)}{(N-(i+1))(i+1)}$$ (因为在实际系统中，站台是从 0 开始的，因此写为 $i+1$)

这样，我们就可以根据比例计算，保留需要用于长途旅行的票，在一定程度上缓解因中间的短途旅行导致更长的长途旅行无法买到票。

系统设计与构建

多线程 Server/Client

本系统基于简单的 Server/Client 的框架，使用 select 轮询函数在所有的客户端 socket 和服务端主 socket 之间等待某个活动（即有客户端发送数据或者服务端接收数据）。在 Server 启动后，系统就开始等待客户端的接入并构建连接。

为了更好地处理多个客户端的工作要求，我定义了 5 个线程，即 task_dealer_ 数组（位于 Server.cc 中）。同时，定义了 task_queue_ 向量 vector，当客户端向服务端发送请求时，服务端会向 task_queue_ 添加 Task 任务。

而 task_dealer_ 的 5 个线程会检查 task_queue_ 是否包含任务。若包含，则任务将会分配给这 5 个线程进行工作，而不占用主线程。工作完后，task_dealer_ 会返回一条信息，信息将传回客户端。

本部分的代码位于 Server.cc void Server::dealTask(int i)

类的设计

本系统分为 2 部分，即 Client 与 Server。

Client 只有 1 个类，即 Client，其负责与 Server 的 socket 连接，发送或接收信息，与 Server 建立连接。同时，也负责和用户交互。Client 的核心方法是 core() 用于接收用户输入 ，其下又分为多个具体的业务函数，而每个业务函数都可以调用 sendRequest() 与 Server 进行通信。 sendRequest() 的具体作用为：

• 传输以多个数字组成的字符串
• 接收 Server 的 doTask() 函数返回的信息并打印在屏幕上。

而上文中提到的每个线程，都会调用 Task 类中的 decode() 解析客户端发来的字符串， 解析后使用 doTask() 方法对任务进行工作，生成一条新的字符串传回 Client。

解析的具体细则如下：

用途	代码	举例	备注
查询余票或者买票	[1] [train_id] [start_station] [destination] [if_buy]	1 0 1 5 1 就是购买车次 0 的从 1 号车站开往 5 号车站的票	if buy 为 0 表示查询余票，1 表示买票
展示所有列车	[2]	2	只需要发送 2 即可
查询订单	[3]	3	只需要发送 3 即可
退票	[4] [order_id]	4 1	退 1 号订单的票
查看收入	[5]	5	只需要发送 5 即可

为了存储信息，还设计了 Station, Train, Ticket 类，分别用于存储站点信息，火车信息及票订单信息，就不在此赘述。

效果展示

如图所示，为 2 个 Client 同时接入 Server 进行购票。（左侧为 Server）

购票及查询余票

（因两个功能几乎相同，合并在一起展示）

========================================
请输入您想进行的操作前面的数字！
[1] 购票
[2] 查看订单
[3] 退票
[4] 查询余票
[5] 查看车票收益
1
========================================
以下为当前开设的列车
[0] (0)北京 -> (1)天津 -> (2)济南 -> (3)青岛 -> (4)徐州 -> (5)苏州 -> (6)合肥 -> (7)杭州 -> (8)舟山 -> (9)上海 -> (10)广州
----------------------------------------
[1] (0)北京 -> (1)天津 -> (2)济南 -> (3)青岛 -> (4)威海 -> (5)徐州 -> (6)南京 -> (7)苏州 -> (8)宿迁 -> (9)芜湖 -> (10)合肥 -> (11)舟山 -> (12)深圳
----------------------------------------
[2] (0)北京 -> (1)石家庄 -> (2)天津 -> (3)济南 -> (4)青岛 -> (5)威海 -> (6)徐州 -> (7)南京 -> (8)苏州 -> (9)宿迁 -> (10)芜湖 -> (11)合肥 -> (12)杭州 -> (13)广州 -> (14)深圳
----------------------------------------
[3] (0)石家庄 -> (1)天津 -> (2)济南 -> (3)苏州 -> (4)宿迁 -> (5)芜湖 -> (6)合肥 -> (7)杭州 -> (8)舟山 -> (9)上海 -> (10)广州 -> (11)深圳
----------------------------------------

请选择您想要购买的列车序号、起始站序号、终点站序号（以空格分隔）。
例如，选择列车[1],第(1)站至第(4)站，请输入 "1 1 4"
请输入：0 3 4
----------------------------------------
您选择的车票当前剩余：39
----------------------------------------
预定成功！您的订单如下：
----------------------------------------
订单号：1
车次：0
站点：青岛 ---> 徐州
售价： ¥135
----------------------------------------

查看订单

请输入您想进行的操作前面的数字！
[1] 购票
[2] 查看订单
[3] 退票
[4] 查询余票
[5] 查看车票收益
2
以下为您的所有订单：
========================================
----------------------------------------
[0]  车次：1,  站点：天津 ---> 威海,  售价： ¥85,  是否退票： 否
[1]  车次：0,  站点：青岛 ---> 徐州,  售价： ¥135,  是否退票： 否

退票

========================================
请输入您想进行的操作前面的数字！
[1] 购票
[2] 查看订单
[3] 退票
[4] 查询余票
[5] 查看车票收益
3
以下为您的所有订单（含已退票），请输入想要退票的订单号：
========================================
----------------------------------------
[0]  车次：1,  站点：天津 ---> 威海,  售价： ¥85,  是否退票： 否
[1]  车次：0,  站点：青岛 ---> 徐州,  售价： ¥135,  是否退票： 否

1
退票成功！退还金额：¥135
========================================

查看收益

请输入您想进行的操作前面的数字！
[1] 购票
[2] 查看订单
[3] 退票
[4] 查询余票
[5] 查看车票收益
5
========================================
----------------------------------------
总收益：¥85
[0]  车次：1,  站点：天津 ---> 威海,  售价： ¥85,  是否退票： 否
[1]  车次：0,  站点：青岛 ---> 徐州,  售价： ¥135,  是否退票： 是

使用说明

build.sh

由于本系统是 Server/Client 框架，因此写了 2 个 build.sh

分别位于：

TicketGo/Client/client_build.sh 及 TicketGo/Server/server_build.sh

• 在使用时，请务必先打开 server_build.sh，然后再打开 client_build.sh，确保客户端可以连接到服务器。
• server 的 socket 位于 8888 端口，如果被占用请先关闭占用应用。

应用使用

应用使用部分已经在第 4 章简要介绍，应用中也包含了指引。