公交同步的进化算法解决方案

# 公交同步的进化算法解决方案 ## 1. 引言 交通运输系统在当今社会中扮演着重要角色，是现代智慧城市的重要组成部分。公共交通在大城市的出行中占比最大，为市民提供了高效且环保的出行方式。然而，要提供优质的公共交通服务，需要对路线、时刻表、公交车、司机等相关子问题进行合理规划。 从用户的角度来看，公交频率的同步是一个重要目标。传统的公共交通网络设计和规划方法认为，拥有多条不同目的地的线路且网络中同步（或换乘）点较少，可以实现更好的交通系统，但这会显著增加运营成本，因为需要更多的线路。而通过减少线路数量并允许线路之间换乘，也能提供优质的服务。在这种情况下，同步问题旨在确定每条线路的频率和发车间隔，以在不增加乘客显著等待时间的前提下，最大化乘客的换乘量。 如今，一些公共交通系统对乘客的换乘次数没有限制，所有公交站点都可能成为同步点，这使得公交同步问题更加复杂。本文以乌拉圭蒙得维的亚的公共交通系统为例，提出了一种特定的进化算法（EA）来有效解决公交同步问题。实验评估基于蒙得维的亚的实际数据构建的实例进行，结果表明，该算法计算出的规划方案比当前规划的同步行程数量最多可提高 13.33%。 ## 2. 公交同步问题 ### 2.1 问题模型 该问题考虑了现代交通系统的主要目标：为市民提供快速可靠的出行方式，同时保持合理的票价。问题模型主要关注为用户提供的服务质量，即减少连续乘坐多辆公交车时的等待时间，提升出行体验。 在提出的模型中，有利于乘客换乘且等待时间有限的事件被称为同步事件。研究旨在解决基于城市公交系统实际数据的真实场景问题，考虑了每个公交站点上不同线路之间换乘的乘客数量。 问题模型的主要思路是根据乘客的需求和出行时间行为，将一天划分为多个规划周期。通过分析历史数据，可以获得类似准确且近乎确定的信息，以构建问题场景。 ### 2.2 问题公式化 公交同步问题的数学公式化考虑了以下要素： - **线路集合**：公交网络的线路集合 \(I = \{i_1, i_2, ..., i_n\}\)。对于每条线路 \(i \in I\)，\(J(i)\) 是可能与线路 \(i\) 同步的线路集合。每条线路的公交车对换乘乘客有最大容量 \(C\)。 - **同步节点集合**：同步节点集合 \(B = \{b_1, b_2, ..., b_m\}\)。每个节点 \(b \in B\) 是一个三元组 \(\lt i, j, d_{ij}^b \gt\)，表示线路 \(i\) 和 \(j\) 在 \(b\) 点同步，且线路 \(i\) 和 \(j\) 的公交站点相距 \(d_{ij}^b\) 距离。 - **规划周期**：规划周期 \([0, T]\)（以分钟为单位），以及每条线路满足乘客需求所需的行程数 \(f_i\)。 - **行驶时间函数**：行驶时间函数 \(TT : I × B → Z\)。\(TT_i^b = TT(i, b)\) 表示线路 \(i\) 的公交车到达同步节点 \(b\) 的时间。 - **步行时间函数**：步行时间函数 \(WT : B × I × I → N\)。\(WT_{i,j}^b = WT(i, j, b)\) 表示行人根据步行速度 \(ws\) 和同步节点 \(b\) 的特定特征（如是否有行人道、拥挤程度、十字路口的交通信号灯等），步行 \(d_{ij}^b\) 距离所需的时间。 - **需求函数**：需求函数 \(P : I × I × B → Z\)。\(P_{ij}^b = P(i, j, b)\) 表示在规划周期内，在同步节点 \(b\) 从线路 \(i\) 换乘到线路 \(j\) 的乘客数量。 - **最大等待时间**：每个同步节点的最大等待时间 \(W_{ij}^b\)，表示乘客在同步节点 \(b\) 从线路 \(i\) 下车并步行到线路 \(j\) 的站点后，愿意等待线路 \(j\) 的最长时间。 - **发车间隔**：同一条线路连续行程之间的发车间隔，定义在区间 \([h_i, H_i]\) 内，其值通常由城市管理部门确定。 同步问题的目标是为每条线路的每个行程找到合适的出发时间，以确保在规划周期 \(T\) 内，所有有换乘需求的线路实现最佳同步。数学模型的公式如下： \[ \begin{align*} &\text{maximize} \sum_{b \in B} \sum_{i \in I} \sum_{j \in J(i)} \sum_{r = 1}^{f_i} \sum_{s = 1}^{f_j} Z_{ij}^{rsb} \times \min(\frac{P_{ij}^b}{f_i}, C) \quad (1a)\\ &\text{subject to}\\ &X_i^1 \leq H_i \quad (1b)\\ &T - H_i \leq X_i^{f_i} \leq T \quad (1c)\\ &h_i \leq X_i^{r + 1} - X_i^r \leq H_i \quad (1d)\\ &(X_j^s + TT_j^b) - (X_i^r + TT_i^b) > WT_{i,j}^b \quad \text{if } Z_{ij}^{rsb} = 1 \quad (1e)\\ &(X_j^s + TT_j^b) - (X_i^r + TT_i^b) \leq W_b + WT_{i,j}^b \quad \text{if } Z_{ij}^{rsb} = 1 \quad (1f)\\ &X_i^r \in \{1, ..., T\}, Z_{ij}^{rsb} \in \{0, 1\} \quad (1g) \end{align*} \] 目标函数（式 1a）旨在最大化同步换乘的数量，并根据每个同步节点的换乘需求进行加权。约束条件（式 1b - 1g）规定了问题的限制。 ## 3. 相关工作 - **Daduna 和 Voß 的研究**：研究了公交网络的时刻表同步问题，以最小化乘客的等待时间。分析了模拟退火和禁忌搜索算法，在基于柏林地铁网络的随机生成示例中，禁忌搜索算法计算出的解决方案优于模拟退火算法。还研究了来自不同德国城市的三个实际案例，建议考虑多目标方法来平衡运营成本和用户效率。 - **Ceder 等人的研究**：研究了在共享站点最大化公交线路同步事件数量的问题，即最大化同时到达的数量。提出了一种基于贪心算法的启发式方法，通过定义自定义时刻表来有效解决问题。研究主