基于线性规划的“共享单车动态重平衡问题”建模与求解示例
字数 3421 2025-12-23 20:34:47

基于线性规划的“共享单车动态重平衡问题”建模与求解示例

1. 问题描述

在城市共享单车运营中，经常出现站点间的供需失衡：如地铁站早晚高峰期间车辆迅速被骑走，而居民区则堆积大量闲置车辆。运营商需要调度车辆（通过卡车搬运）来重新平衡站点库存，以满足后续需求。此问题即“动态重平衡问题”（Dynamic Bike Rebalancing Problem）。目标是在满足各站点库存上下限、卡车容量等约束下，最小化总调度成本（如行驶距离、时间）或调度次数。

2. 问题建模（整数/线性规划模型）

设有一个有向图 \(G = (V, A)\)，其中 \(V\) 是站点集合，\(A\) 是站点间可行驶的路段集合。我们有：

  • 规划周期：\(T = \{1, 2, ..., \tau\}\) 个离散时间段。
  • 每辆车在时段 \(t\) 开始时停放于某站点 \(i\)。
  • 需求预测：每个站点 \(i\) 在时段 \(t\) 有一个净需求 \(d_{i,t}\)（负数表示供给过剩，正数表示需求缺口）。
  • 卡车：有 \(K\) 辆同质卡车，每辆容量为 \(C\)（可装载的单车数量）。卡车在时段 \(t\) 可以从站点 \(i\) 行驶到 \(j\)，产生成本 \(c_{i,j}\)（如距离）。
  • 站点库存限制：每个站点 \(i\) 在时段 \(t\) 结束时库存必须在 \([L_i, U_i]\) 内。

决策变量：

  • \(x_{i,j,t}^k \in \mathbb{Z}^+\)：时段 \(t\) 卡车 \(k\) 从站点 \(i\) 到 \(j\) 搬运的车辆数。
  • \(y_{i,j,t}^k \in \{0,1\}\)：指示时段 \(t\) 卡车 \(k\) 是否从 \(i\) 行驶到 \(j\)。
  • \(I_{i,t} \in \mathbb{Z}^+\)：时段 \(t\) 结束时站点 \(i\) 的库存。

目标函数：最小化总调度成本（或总行驶成本）

\[\min \sum_{t \in T} \sum_{k \in K} \sum_{(i,j) \in A} c_{i,j} \cdot y_{i,j,t}^k \]

约束条件：

  1. 库存流平衡：对每个站点 \(i\)，每个时段 \(t\)：

\[ I_{i,t} = I_{i,t-1} - d_{i,t} + \sum_{k \in K} \left( \sum_{j: (j,i) \in A} x_{j,i,t}^k - \sum_{j: (i,j) \in A} x_{i,j,t}^k \right) \]

初始库存 \(I_{i,0}\) 已知。此式含义：期末库存 = 期初库存 − 净需求 + 调入车辆 − 调出车辆。

  1. 卡车流平衡：卡车本身也需形成路径。对每个站点 \(i\)，每个时段 \(t\)，每辆卡车 \(k\)：

\[ \sum_{j: (i,j) \in A} y_{i,j,t}^k = \sum_{j: (j,i) \in A} y_{j,i,t}^k \]

即卡车到达某站点也需离开，可形成回路或停留。

  1. 容量约束：卡车搬运数不超过其容量，且只有卡车行驶时才能搬运：

\[ 0 \le x_{i,j,t}^k \le C \cdot y_{i,j,t}^k, \quad \forall (i,j) \in A, t \in T, k \in K \]

  1. 库存上下限：

\[ L_i \le I_{i,t} \le U_i, \quad \forall i \in V, t \in T \]

  1. 卡车起始约束：可设定每辆卡车在 \(t=1\) 时从指定车场出发。

此模型为混合整数线性规划，变量与约束规模随站点、时段增加而快速增大。实践中常采用分解与启发式算法，例如将问题分解为“库存分配”与“车辆路径”两个子问题。

3. 分解求解思路

由于模型复杂，常用列生成（Column Generation）与分支定价（Branch-and-Price）算法求解。其核心是将问题重新建模为“集合划分/覆盖”形式：

  • 主问题：决定哪些“调度任务”（每个任务对应一辆卡车在一天内的完整行驶路径与装载方案）被执行，最小化总成本。
  • 定价子问题：为每辆卡车生成可行的调度任务（即寻找一个路径及每段的装载量），其“负检验数”表示能降低主问题目标的新列。

具体步骤如下：

(1) 主问题建模：
设 \(\Omega^k\) 是卡车 \(k\) 所有可行调度任务的集合。一个任务 \(p \in \Omega^k\) 用参数表示：

  • \(a_{i,t,p}\)：任务 \(p\) 在时段 \(t\) 从站点 \(i\) 装载的单车数量（负值表示卸载）。
  • \(c_p\)：任务 \(p\) 的成本（行驶成本）。

引入决策变量 \(\lambda_p \in \{0,1\}\)，表示是否选择任务 \(p\)。

主问题：

\[\min \sum_{k \in K} \sum_{p \in \Omega^k} c_p \lambda_p \]

\[ \text{s.t.} \quad \sum_{k \in K} \sum_{p \in \Omega^k} a_{i,t,p} \lambda_p = d_{i,t} - (I_{i,t-1} - I_{i,t}), \quad \forall i,t \]

\[ \sum_{p \in \Omega^k} \lambda_p = 1, \quad \forall k \in K \]

\[ \lambda_p \in \{0,1\} \]

第一个约束确保各站点各时段的净调度量等于需求与库存变化之差；第二个约束确保每辆卡车执行一个任务。实际求解中，先松弛 \(\lambda_p \in [0,1]\) 为线性规划。

(2) 列生成迭代：

  1. 初始化：用一组简单可行的调度任务（如空路径）启动主问题。
  2. 求解线性规划松弛主问题，得到对偶变量：
    • \(\mu_{i,t}\)：对应每个库存流平衡约束。
    • \(\pi_k\)：对应每辆卡车任务选择约束。
  3. 定价子问题：对每辆卡车 \(k\)，寻找一个调度任务（即一个路径 + 装载方案）使得其检验数 \(\bar{c}_p = c_p - \sum_{i,t} \mu_{i,t} a_{i,t,p} - \pi_k\) 为负。这等价于在一个扩展网络（节点为（站点，时段）对）上求解一个资源约束最短路径问题（Resource Constrained Shortest Path Problem, RCSPP），其中“资源”是卡车的容量、时间连续性等。可用动态规划（如标号法）求解。
  4. 若找到负检验数列，则加入主问题，重复步骤2-3，直到无负检验数列，得到线性规划松弛最优解。

(3) 获得整数解：
列生成通常得到分数解。需在分支定界框架中嵌入列生成（即分支定价），对变量 \(\lambda_p\) 或原变量 \(y_{i,j,t}^k\) 分支，并在每个节点重新调用列生成求解线性规划松弛。

4. 启发式近似求解

对大规模实时应用，常采用启发式：

  1. 两阶段法：
    • 阶段一（库存分配）：忽略卡车路径，只确定每个时段各站点间的最优调剂量，可建模为最小成本流问题。
    • 阶段二（车辆路径）：基于阶段一的调剂量，为每辆卡车设计路径，转化为带容量与时间约束的车辆路径问题（CVRP），用启发式算法（如节约算法、邻域搜索）求解。
  2. 模型预测控制：在每个决策时刻，求解一个短周期的滚动优化问题，并实施当前时段的决策，之后滚动向前。

5. 总结

本问题展示了线性/整数规划在共享单车重平衡中的建模能力。其核心挑战在于规模与实时性，因此常采用分解算法（如列生成）与启发式策略。通过此模型，运营商可在满足运营约束下，有效降低调度成本，提高系统效率。

基于线性规划的“共享单车动态重平衡问题”建模与求解示例 1. 问题描述 在城市共享单车运营中，经常出现站点间的供需失衡：如地铁站早晚高峰期间车辆迅速被骑走，而居民区则堆积大量闲置车辆。运营商需要调度车辆（通过卡车搬运）来重新平衡站点库存，以满足后续需求。此问题即“动态重平衡问题”（Dynamic Bike Rebalancing Problem）。目标是在满足各站点库存上下限、卡车容量等约束下，最小化总调度成本（如行驶距离、时间）或调度次数。 2. 问题建模（整数/线性规划模型） 设有一个有向图 \( G = (V, A) \)，其中 \( V \) 是站点集合，\( A \) 是站点间可行驶的路段集合。我们有： 规划周期：\( T = \{1, 2, ..., \tau\} \) 个离散时间段。 每辆车在时段 \( t \) 开始时停放于某站点 \( i \)。 需求预测：每个站点 \( i \) 在时段 \( t \) 有一个净需求 \( d_ {i,t} \)（负数表示供给过剩，正数表示需求缺口）。 卡车：有 \( K \) 辆同质卡车，每辆容量为 \( C \)（可装载的单车数量）。卡车在时段 \( t \) 可以从站点 \( i \) 行驶到 \( j \)，产生成本 \( c_ {i,j} \)（如距离）。 站点库存限制：每个站点 \( i \) 在时段 \( t \) 结束时库存必须在 \([ L_ i, U_ i ]\) 内。 决策变量 ： \( x_ {i,j,t}^k \in \mathbb{Z}^+ \)：时段 \( t \) 卡车 \( k \) 从站点 \( i \) 到 \( j \) 搬运的车辆数。 \( y_ {i,j,t}^k \in \{0,1\} \)：指示时段 \( t \) 卡车 \( k \) 是否从 \( i \) 行驶到 \( j \)。 \( I_ {i,t} \in \mathbb{Z}^+ \)：时段 \( t \) 结束时站点 \( i \) 的库存。 目标函数 ：最小化总调度成本（或总行驶成本） \[ \min \sum_ {t \in T} \sum_ {k \in K} \sum_ {(i,j) \in A} c_ {i,j} \cdot y_ {i,j,t}^k \] 约束条件 ： 库存流平衡 ：对每个站点 \( i \)，每个时段 \( t \)： \[ I_ {i,t} = I_ {i,t-1} - d_ {i,t} + \sum_ {k \in K} \left( \sum_ {j: (j,i) \in A} x_ {j,i,t}^k - \sum_ {j: (i,j) \in A} x_ {i,j,t}^k \right) \] 初始库存 \( I_ {i,0} \) 已知。此式含义：期末库存 = 期初库存 − 净需求 + 调入车辆 − 调出车辆。 卡车流平衡 ：卡车本身也需形成路径。对每个站点 \( i \)，每个时段 \( t \)，每辆卡车 \( k \)： \[ \sum_ {j: (i,j) \in A} y_ {i,j,t}^k = \sum_ {j: (j,i) \in A} y_ {j,i,t}^k \] 即卡车到达某站点也需离开，可形成回路或停留。 容量约束 ：卡车搬运数不超过其容量，且只有卡车行驶时才能搬运： \[ 0 \le x_ {i,j,t}^k \le C \cdot y_ {i,j,t}^k, \quad \forall (i,j) \in A, t \in T, k \in K \] 库存上下限 ： \[ L_ i \le I_ {i,t} \le U_ i, \quad \forall i \in V, t \in T \] 卡车起始约束 ：可设定每辆卡车在 \( t=1 \) 时从指定车场出发。 此模型为混合整数线性规划，变量与约束规模随站点、时段增加而快速增大。实践中常采用分解与启发式算法，例如将问题分解为“库存分配”与“车辆路径”两个子问题。 3. 分解求解思路 由于模型复杂，常用 列生成 （Column Generation）与 分支定价 （Branch-and-Price）算法求解。其核心是将问题重新建模为“集合划分/覆盖”形式： 主问题 ：决定哪些“调度任务”（每个任务对应一辆卡车在一天内的完整行驶路径与装载方案）被执行，最小化总成本。 定价子问题 ：为每辆卡车生成可行的调度任务（即寻找一个路径及每段的装载量），其“负检验数”表示能降低主问题目标的新列。 具体步骤如下： (1) 主问题建模 ： 设 \( \Omega^k \) 是卡车 \( k \) 所有可行调度任务的集合。一个任务 \( p \in \Omega^k \) 用参数表示： \( a_ {i,t,p} \)：任务 \( p \) 在时段 \( t \) 从站点 \( i \) 装载的单车数量（负值表示卸载）。 \( c_ p \)：任务 \( p \) 的成本（行驶成本）。 引入决策变量 \( \lambda_ p \in \{0,1\} \)，表示是否选择任务 \( p \)。 主问题 ： \[ \min \sum_ {k \in K} \sum_ {p \in \Omega^k} c_ p \lambda_ p \] \[ \text{s.t.} \quad \sum_ {k \in K} \sum_ {p \in \Omega^k} a_ {i,t,p} \lambda_ p = d_ {i,t} - (I_ {i,t-1} - I_ {i,t}), \quad \forall i,t \] \[ \sum_ {p \in \Omega^k} \lambda_ p = 1, \quad \forall k \in K \] \[ \lambda_ p \in \{0,1\} \] 第一个约束确保各站点各时段的净调度量等于需求与库存变化之差；第二个约束确保每辆卡车执行一个任务。实际求解中，先松弛 \( \lambda_ p \in [ 0,1 ] \) 为线性规划。 (2) 列生成迭代 ： 初始化：用一组简单可行的调度任务（如空路径）启动主问题。 求解线性规划松弛主问题，得到对偶变量： \( \mu_ {i,t} \)：对应每个库存流平衡约束。 \( \pi_ k \)：对应每辆卡车任务选择约束。 定价子问题 ：对每辆卡车 \( k \)，寻找一个调度任务（即一个路径 + 装载方案）使得其 检验数 \( \bar{c} p = c_ p - \sum {i,t} \mu_ {i,t} a_ {i,t,p} - \pi_ k \) 为负。这等价于在一个扩展网络（节点为（站点，时段）对）上求解一个 资源约束最短路径问题 （Resource Constrained Shortest Path Problem, RCSPP），其中“资源”是卡车的容量、时间连续性等。可用动态规划（如标号法）求解。 若找到负检验数列，则加入主问题，重复步骤2-3，直到无负检验数列，得到线性规划松弛最优解。 (3) 获得整数解 ： 列生成通常得到分数解。需在分支定界框架中嵌入列生成（即分支定价），对变量 \( \lambda_ p \) 或原变量 \( y_ {i,j,t}^k \) 分支，并在每个节点重新调用列生成求解线性规划松弛。 4. 启发式近似求解 对大规模实时应用，常采用启发式： 两阶段法 ： 阶段一（库存分配）：忽略卡车路径，只确定每个时段各站点间的最优调剂量，可建模为最小成本流问题。 阶段二（车辆路径）：基于阶段一的调剂量，为每辆卡车设计路径，转化为带容量与时间约束的车辆路径问题（CVRP），用启发式算法（如节约算法、邻域搜索）求解。 模型预测控制 ：在每个决策时刻，求解一个短周期的滚动优化问题，并实施当前时段的决策，之后滚动向前。 5. 总结 本问题展示了线性/整数规划在共享单车重平衡中的建模能力。其核心挑战在于规模与实时性，因此常采用分解算法（如列生成）与启发式策略。通过此模型，运营商可在满足运营约束下，有效降低调度成本，提高系统效率。