122 lines
6.5 KiB
Markdown
122 lines
6.5 KiB
Markdown
# 20260116 美赛模拟：食物分发（MFP）
|
||
|
||
本仓库包含对 2019 年 MFP 站点数据的频次分配（任务一）与全年排班优化（任务二）脚本。
|
||
核心数据文件：`prob/MFP Regular Sites 2019.xlsx`。
|
||
|
||
## Task 1: 频次分配（Visit Frequency Allocation）
|
||
|
||
目标：在总车次约束下，为每个站点分配年度访问次数 `f_i`，并评估有效性/公平性（含最低10%平均、基尼系数等）。
|
||
|
||
- 运行：`python3 kmin_effectiveness.py`
|
||
- 输出（写入 `data/`）：
|
||
- `data/kmin_effectiveness.png`：k_min 与指标曲线图
|
||
- `data/kmin_effectiveness_data.csv`：每个 `k_min` 的汇总指标 + 各站点 `visits_01..visits_N`
|
||
- `data/kmin_effectiveness_sites.csv`：`visits_XX` 与站点名称/顺序映射
|
||
|
||
说明：`kmin_effectiveness.py` 当前使用 Monte Carlo（引入 `StDev(Demand per Visit)`）对有效性做多次模拟平均。
|
||
|
||
|
||
|
||
## Scheduling (Step 2)
|
||
|
||
Optimize a 365-day schedule with at most 2 visits per day and minimum gap constraints:
|
||
|
||
- `python3 scheduling_optimization.py --days 365 --daily-capacity 2 --gap-min 14`
|
||
- Outputs are written to `data/` (e.g., `data/schedule_optimized_kmin6.8_gap14.csv`), using `data/kmin_effectiveness_data.csv` as the frequency source.
|
||
|
||
### Visualization (Plan A)
|
||
|
||
- `python3 visualize_schedule.py`
|
||
- Outputs: `data/schedule_barcode_*.png` and `data/schedule_gap_deviation_*.png`
|
||
- Site label rule: remove first 4 chars, then take 12 chars.
|
||
|
||
|
||
|
||
|
||
|
||
## Task 3: 双站点同车方案（Two-stop trips）
|
||
|
||
目标：允许同一辆车在一次出车中访问两个站点，需要在**站点配对、访问日期**以及**第一站分配量**上共同决策，并评估有效性/公平性。
|
||
|
||
### 算法框架（基于 Task 1/2 输出）
|
||
|
||
1. **需求与频次基线**
|
||
使用 `kmin_effectiveness.py` 得到各站点年度访问频次 `f_i` 与需求分布（均值、标准差）。
|
||
记单车载量 `C=15000lb`（或折算为服务人数上限 `C_OPT`），每次出车总量不超过 `C`。
|
||
|
||
2. **候选配对生成（Manhattan 距离，基于经纬度）**
|
||
设站点 `i` 的坐标为 `(lat_i, lon_i)`，在不使用道路网的情况下，用曼哈顿距离近似“同日可达性”。
|
||
推荐用“纬度/经度分别折算为里程”的加权曼哈顿：
|
||
```
|
||
d_ij = 69.0 * |lat_i - lat_j| + 69.0 * cos(lat0) * |lon_i - lon_j|
|
||
```
|
||
其中 `lat0` 可取所有站点纬度均值（单位：英里）。若仅需相对距离，也可用
|
||
`|lat_i - lat_j| + |lon_i - lon_j|` 作为无量纲近似。
|
||
具体配对流程（可直接脚本化）：
|
||
- **距离筛选**：对每个站点 `i`，计算与所有 `j != i` 的 `d_ij`，取 `k` 个最近邻
|
||
（默认 `k=6`），得到近邻集合 `N(i)`。
|
||
- **运载量筛选**：对候选 `(i, j)`，要求 `mu_i + mu_j <= 250`
|
||
（将每次访问的平均客户数视为需求均值），确保双站总需求不超过单车载量。
|
||
- **波动风险筛选**：若 `sigma_i` 或 `sigma_j` 过大（如 `sigma / mu > 0.5`），
|
||
则优先作为第二站（或直接剔除）以降低不确定性风险。
|
||
- **最终候选集**：`P = {(i, j) | j in N(i) 且满足需求/波动筛选}`，
|
||
再去重（`(i, j)` 与 `(j, i)` 合并）并记录候选对的 `d_ij` 与需求统计。
|
||
|
||
3. **第一站分配量优化（核心不确定性）**
|
||
假设 `D_i ~ Normal(mu_i, sigma_i)` 与 `D_j ~ Normal(mu_j, sigma_j)`，选择第一站上限 `q_i`：
|
||
- 实际服务：`S_i = min(D_i, q_i)`
|
||
- 剩余载量：`R = C - S_i`
|
||
- 第二站服务：`S_j = min(D_j, R)`
|
||
用一维搜索/网格或解析近似，选择 `q_i*` 最大化期望目标：
|
||
```
|
||
maximize E[S_i + S_j]
|
||
- alpha * E[unmet_i + unmet_j]
|
||
- beta * E[waste_i + waste_j]
|
||
- gamma * |E[S_i / D_i] - E[S_j / D_j]|
|
||
```
|
||
期望可用 Monte Carlo（与 `kmin_effectiveness.py` 一致）或截断正态闭式近似；得到每个候选对的 `(q_i*, score)`。
|
||
|
||
4. **排程与配对选择（CP-SAT / MIP）**
|
||
在 Task 2 的日程框架上，将“单站访问”与“可配对双站访问”视作不同任务，决策变量：
|
||
- 是否在某天为一辆车选择 `(i, j)`
|
||
- 其他站点仍按单站访问
|
||
约束：每站点访问次数 = `f_i`；每日出车数 ≤ 2；每辆车最多一条路线。
|
||
目标：最大化总期望有效性得分，并在目标函数中加入公平性惩罚（如 Gini 或最低 10% 均值惩罚）。
|
||
|
||
5. **有效性 & 公平性评估**
|
||
复用 Task 1 指标：
|
||
- 有效性：总体服务率、总未满足需求、总浪费
|
||
- 公平性：基尼系数、最低 10% 站点平均服务比例、最小服务比例
|
||
对双站路线进行 Monte Carlo 汇总，给出与单站方案的对比提升/退化幅度。
|
||
|
||
### 直观规则（工程可用的简化版）
|
||
|
||
- **配对规则**：优先将“高需求站点 + 低需求站点”或“需求相近且近邻”的站点配对，降低极端不公平。
|
||
- **第一站分配**：`q_i` 取 `D_i` 的 60%~80% 分位数作为保守上限，剩余量留给第二站；必要时按历史波动调整分位数。
|
||
- **动态修正**：若某站点连续出现“后站不足”，在后续排程中降低其作为第一站的概率或提高 `q_i` 分位数阈值。
|
||
|
||
该方案与当前脚本兼容：`kmin_effectiveness.py` 提供需求统计与 Monte Carlo 框架；`scheduling_optimization.py` 的 CP-SAT 可扩展为“单站/双站二选一”的排程模型。
|
||
|
||
### 候选配对生成脚本
|
||
|
||
- `python3 candidate_pairs.py --k 6 --capacity 250`
|
||
- 输出：`data/candidate_pairs_k6_cap250.csv`
|
||
|
||
### 第一站分配量优化脚本
|
||
|
||
- `python3 two_stop_allocation.py --input data/candidate_pairs_k6_cap250.csv`
|
||
- 输出：`data/ordered_pairs_allocation_k6_cap250.csv`
|
||
- 说明：对每个无序候选对生成 `(i -> j)` 与 `(j -> i)` 两条有序记录，并用 Monte Carlo
|
||
在 `q_i ∈ [0, C]` 上搜索最优第一站分配量。
|
||
|
||
### Task 3 频次分配（双站合并出车）
|
||
|
||
- `python3 p3_kmin.py --input-pairs data/ordered_pairs_allocation_k6_cap250.csv`
|
||
- 输出：
|
||
- `data/p3_kmin_data.csv`：扫 `k_min` 的有效性/公平性指标 + 出车统计
|
||
- `data/p3_kmin_sites.csv`：每站单独次数/双站次数统计
|
||
- `data/p3_kmin_pairs.csv`：有序双站出车次数 + 第一站上限 `q_opt`
|
||
- `data/p3_kmin_effectiveness.png`：Task 3 的 `k_min` 指标曲线图
|
||
|
||
|