Q2_Solution

问题 2 解答

主要思路

问题 2 主要分为两个问，对应了代码中的 2-A 和 2-B 两问。

这里在考虑列车的实际运行时刻以及换乘的情况下，根据乘客的到达时间和到达车站选择乘 客可能乘坐的列车，从而回溯乘客经过的站点。

由于乘客出行的选择的多样性，在设计智能选路算法时，考虑对每条路径赋权，根据路径的长度以及乘客的人数确定其权值， 选取最小权值路。

1. 问题 2-A 解答

   问题 2-A 需要找出乘客的乘车路线，一般可能的乘车线路会有多条。由于只给了入站地点和时间、出站地点和时间，只要给出的出行路线上，到达起点和终点的时间符合因果关系，都可以作为答案。

   问题 2-A 主要采用回溯法求解。根据乘客出站时间，回溯乘客可能乘坐的列车。联系现实情况，乘客在换乘点可能会换乘，所以在回溯的过程中考虑了乘客换乘到另一线路。

   问题 2 涉及到对地图建模，为了方便编程实现，这里将地图表示为有向图。将站点看作图上的顶点，站点之间的列车线路看作边；当然，由于换乘站点在不同线路上属于不同的站点，所以换乘站点之间也存在一条边连接。

   回溯算法的思路：

   • 对基本情况：乘客的出行的起点和终点在同一线路，则乘客会从起点乘坐同一列车到达终点，遍历该线路上的所有列车，尝试找出同时经过起点站和终点站且时间符合因果要求的列车，作为可能的出行线路。
   • 回溯情况： 若起点站和终点站不在同一列车，则出行线路上会有换乘站，回溯找出这样的换乘站。从终点站出发，尝试找可能的换乘站，最为新的终点站，新的出站时间设为列车到达该换乘站点的时间，这样，开始递归查找。
   • 递归底： 递归结束的情况，一种为，遇到了起点站，且时间符合要求，即找到了答案，返回；另一种情况，确定此线路不可能找到可能的出行线路，主要体现为时间已经早于进站时间，时间上不符合因果序。

2. 问题 2-B 解答

   问题 2-B 需要为乘客规划线路，目标是缩短行程、减少拥挤。

   问题 2-B 的解答主要采用 A-star 算法进行最短路的规划，同时对地图上的边进行动态赋权，权值主要与路线长度、路线上的人流量相关，主要想实现的效果是，在给乘客推荐出行时间最短的线路，同时，保证线路上的人流量处于可接受的范围。

   路径规划的主要思路：

   • 对时间进行分片，遍历整天的时间，在每个时间片，选择一批要出行的乘客，利用 A-star 算法求出最短路，最为该乘客的规划线路；然后，每次规划后，更新地图上边的权值，以体现乘客出行对道路客流量（或道路拥塞情况）的影响，是后面的乘客选择路线的时候避开拥塞线路。
   • 每个时间片，对地图上边的权值进行衰减。因为乘客出站后，路线上的拥塞情况会有所减缓，前面乘客择路的结果对后面的乘客择路的影响应该随时间衰减。

3. 问题 2 中涉及到的建模

   • 两个小问中都涉及到的建模

     • 需要对地图进行建模，这里将地铁线路看作双向连通图，问题 2-A 中为无权图，问题 2-B 中为赋权图。每个站点为地图上的一个节点，若两个站点之间存在列车，则两个节点邻接；此外换乘节点之前也视为邻接的，换乘前后的节点视为不同的节点（对应了所给数据中的不同节点 id 号）。

   • 问题 2-B 中涉及到的建模

     • 对图上的边进行赋权，这里权值通过建模后的公式给出
     • 对权值更新策略的建模
     • 对权值衰减策略的建模

4. 问题 2 求解中遇到的问题

   求解问题 2 时主要遇到两大问题：

   • 数据不完整，且有异常数据（参见问题1、3的解答）
   • 数据量太大，跑完所有数据要几天，比赛时时间不允许，这里采用的解决方法是对数据进行采样，用部分数据来评判模型结果

源代码说明

1. 依赖环境

   本代码使用 python3 版本解释器，因为代码没有使用其他 python 包，一般的 python3 解释器均能正常运行。本人使用的解释器为 python 3.6

2. 文件结构说明

   第二题求解的主要代码在 Solution 目录的 Solution2.py 中实现，其他文件夹为问题求解的辅助 python 包

   • main.py 为求解问题的主要代码文件，运行改脚本可分别求得问题二的两个问的解，结果保存在相应的文件中
   • AStar 文件夹为所实现的 A* 算法包
   • Floyd 文件夹为所实现的 Floyd 算法包
   • Graph 文件夹为所实现的有向赋权图模型
   • RouteInfo 文件夹地铁线路信息类
   • UserInfo 文件夹乘客信息类
   • Solution 文件夹为解决问题所用的类
   • data 给的附件中的数据及程序输出保存的目录
   • logs 为代码运行生成的日志文件数据

3. 运行脚本求解问题

   • 切换当前工作目录为 Q2_Solution 目录： 若在 Linux 环境下或者 windows DOS 环境下， 则为 cd 目录所在的绝对路径/Q2_Solution
   • 运行脚本： python main.py
   • 查看结果，两个小问的结果分别保存在 data/user_path_answer_2A.txt 及 data/planed_route_traffic.txt 文件中