整数线性规划(ILP)求解区间公交组合成本最小化问题

整数线性规划模型构建方案 #

前置参数定义 #

• 出行起点：S（即问题中的start）
• 出行终点：T（即问题中的end）
• 可选公交集合：$I$，单个公交编号为$i \in I$
• 公交$i$的运营区间左端点：$a_i$
• 公交$i$的运营区间右端点：$b_i$
• 公交$i$的单次乘坐成本：$c_i$

决策变量 #

均为0-1布尔变量：

• $x_i$：取1时表示选择乘坐公交$i$，取0时表示不选择
• $y_i$：取1时表示公交$i$可通过起点出发的换乘链到达，取0时表示不可到达

目标函数 #

最小化总出行成本：
$$\min \sum_{i \in I} c_i \cdot x_i$$

约束条件 #

1. 起点可达约束：运营区间包含起点的公交，只要被选中就默认可以从起点到达
   对所有满足$a_i \leq S$的$i \in I$：$y_i \geq x_i$
2. 换乘可达约束：运营区间不包含起点的公交，可到达的前提是存在其他已可达的公交，其运营右端点能覆盖当前公交的左端点
   对所有满足$a_i > S$的$i \in I$：$y_i \leq \sum_{k \in I, k \neq i, b_k \geq a_i} y_k$
3. 选择有效性约束：被选中的公交必须是可到达的
   对所有$i \in I$：$x_i \leq y_i$
4. 终点覆盖约束：至少有一个可到达的公交，其运营右端点能覆盖终点
   $\sum_{i \in I, b_i \geq T} y_i \geq 1$

模型说明 #

• 约束总数量为$O(n)$，$n$为可选公交的总数，符合约束有限的要求
• 无需额外计算上下车具体点位，模型仅通过可达性逻辑保证选中的公交组合可连续覆盖$[S,T]$全程
• 所有变量均为0-1整数变量，符合整数线性规划的建模规范

内容的提问来源于stack exchange，提问作者zvonimir