2025年电工杯数学建模

B题 城市垃圾分类运输的路径优化与调度

原题再现：

B 题：城市垃圾分类运输的路径优化与调度

  随着城市化进程加快，城市生活垃圾问题给社会的可持续发展和人类健康带来了严峻的挑战和威胁。2004 年，我国成为全球垃圾产量最大的国家；2016 年，我国垃圾清运量已超过 2 亿吨；2019 年，超过 3.43 亿吨；2023 年已达到 4 亿吨。巨大的垃圾产生量已逼近我国各城市和地区对其处理能力的极限，垃圾管理问题变得越来越突出，这对我国生活垃圾的收集、运输和处理提出了更高的要求。

  当前垃圾分类运输成为城市环境治理的关键环节，需考虑不同垃圾类型（如厨余垃圾、可回收物、有害垃圾、其他垃圾）的收集要求、运输车辆的载重与容积限制、中转站的处理能力及运营时间窗口，同时需兼顾运输成本与碳排放控制。如何通过数学建模优化城市垃圾分类运输路径与调度，提升效率并降低成本，是当前城市管理的重要课题。

  请根据所给数据资料，解决以下问题：

问题一：单一车辆类型下的基础路径优化与调度

  某城区有 $n$ 个垃圾分类收集点，每个收集点每日产生一种类型的垃圾（假设仅考虑“厨余垃圾”单一类型，需由专用车辆运输）。已知各收集点的坐标 $(x_i,y_i)$、垃圾产生量 $w_i$（吨），以及运输车辆的最大载重 $Q$（吨）和固定发车点（垃圾处理厂，编号为 0）。假设车辆从垃圾处理厂出发，完成所有收集点的运输任务后返回垃圾处理厂，且同一车辆可多次往返（即允许分批运输）。请完成以下任务：

  1）建立数学模型，以最小化每日总行驶距离为目标，确定运输车的数量、每辆运输车的运输路径及任务分配（即哪辆车负责哪些收集点，每趟运输的具体路线）。

  2）若给定 $n=30$ 个收集点（坐标及垃圾产生量见附件 1），$Q=5$ 吨，给出此问题数学模型，设计求解算法，求出最优解，并分析模型的时间复杂度。

  3）讨论模型的局限性（如未考虑交通拥堵、车辆行驶速度差异等），并提出至少一种改进方向。

问题二：多车辆协同与载重约束下的优化

  现实中，垃圾分类运输需区分不同垃圾类型（本题中仅考虑 4 类垃圾，即厨余垃圾、可回收物、有害垃圾、其他垃圾），每类垃圾需由专用车辆运输（车辆类型 $k=1,2,3,4$ 分别对应上述 4 类垃圾）。每类车辆的载重限制 $Q_k$、容积限制 $V_k$、单位距离运输成本 $C_k$ 不同（参数见附件 2），且每个收集点可能产生多种类型的垃圾（各类型垃圾量 $w_{i,k}\ge 0$，满足

$$\sum _{k=1}^4{w}_{i,k}=w_i$$  ）。车辆从处理厂出发，完成同类型垃圾收集后返回处理厂，不同类型车辆可独立调度。

  1）建立以最小化每日总运输成本为目标的多车辆协同运输模型。

  2）若附件 1 中 30 个收集点调整为产生 4 类垃圾（数据见附件 3），且附件 2 中 $Q_k$，$V_k$，$C_k$ 给定，说明如何将问题一的算法扩展至本问题（需考虑多车辆调度与类型约束），给出此问题数学模型，分析模型的约束条件变化，并求出最优解。

  3）若增加“车辆每日最大行驶时间”约束，如何修改模型？举例说明时间约束对路径规划的影响（如某车辆因时间不足需拆分任务）。

问题三：含中转站选址与时间窗口的综合优化

  为进一步提升效率，考虑在城区规划若干中转站（候选位置 $m$ 个，编号 $n+1,n+2,\cdots ,n+m$）。中转站可对各类垃圾进行临时存储与分拣，每类垃圾在中转站的最大存储量为 $S_k$ 吨，且中转站仅在固定时间窗口 $[a_j,b_j]$ 内允许车辆停靠（$j$ 为中转站编号）。同时，运输过程需考虑碳排放约束，碳排放尽可能小，碳排放与车辆载重、行驶距离正相关，计算公式为

$$E=\sum _k\sum _{\text{车辆}t}\left(d_{t,k}{\alpha }_k+{\beta }_k\sum _i{w}_{i,k,t}\right)$$

  其中 $d_{t,k}$ 为车辆 $t$ 的行驶距离，${\alpha }_k$，${\beta }_k$ 为碳排放系数（见附件 2），假设中转站每日均可清空。

  1）建立“中转站选址 - 路径优化 - 碳排放最少”的综合数学模型，目标为最小化运输成本与中转站建设成本之和（中转站建设成本为固定值 $T_j$，每个中转站使用期限为 10 年，选址则产生该成本）。

  2）对于附件 1 中的 30 个收集点，假设候选中转站位置为 5 个（中转站候选位置及参数见附件 4），其他参数见附件 2 与附件 3，设计两阶段求解算法：

  第一阶段：确定中转站选址与各收集点对应的中转站分配；

  第二阶段：针对每个中转站，优化各类型车辆的运输路径。

说明两阶段的关联与协同机制（如中转站选址影响路径长度，路径优化需反应中转站容量限制）。

  3）若实际路网存在单行道、禁行时段等非对称约束（即从点 $i$ 到点 $j$ 的距离与 $j$ 到 $i$ 的距离不同），如何修改距离矩阵并调整模型？对比对称路网与非对称路网下路径优化的复杂度差异（城市路网矩阵说明见附件 5）。

  说明：垃圾处理厂的工作时间为 6:00—18:00，所有车辆行驶速度均为 40km/h。

整体求解过程概述(摘要)

  针对问题一，为了刻画单一厨余垃圾专用车辆在载重约束下的最短运输路径，首先对附件1的30个收集点坐标与垃圾量进行数据理解、完整性检验、单位统一和距离矩阵构造。鉴于总垃圾量为70.0 t、车辆载重为5 t，而简单容量下界14趟未必满足不可拆分装载组合，本文引入“可行路线集合—集合划分”精确模型，按字典序先最小化运输趟次、再最小化总距离。模型枚举606条容量可行候选路线，并由MILP证明最少需15趟；在该趟次下最短总距离为1101 km。进一步考虑处理厂6:00—18:00工作窗及单点服务时间情景，采用连续装箱调度将15趟任务分配给3辆物理车辆。与角度扫描法和Clarke-Wright节约法相比，精确模型分别降低总距离14.58%和4.26%，验证了模型的最优性与求解有效性。
  针对问题二，为了处理厨余、可回收物、有害垃圾和其他垃圾的专车专运、质量—容积双重约束及差异化成本，本文在问题一的数据结构与距离矩阵基础上进行增量建模，避免重复清洗。鉴于附件未提供垃圾单位质量体积，本文引入可配置的比体积系数并构造等效质量容量，将双资源约束统一嵌入异构CVRP。求解层面构建“容量约束聚类MILP—最近邻排序—2-opt—跨路线Relocate/Swap—迭代扰动”的混合算法，并与角度扫描和Clarke-Wright方法进行对照。四类垃圾的最优可行方案共行驶1067 km，日运输成本为2825.3元，碳排放指标为875.98 kg；其中有害垃圾质量仅2.305 t，但由于单位距离成本和排放系数较高，其成本达到890.0元。12小时工作窗下各类型所需物理车辆数分别为2、1、1、1；当工作窗收紧为6小时，车辆配置上升为3、2、1、2，说明时间约束会直接触发任务拆分和车辆扩容。
  针对问题三，为了同时决定中转站选址、收集点分配、多类型车辆路径、时间窗口和碳排放，本文构建两阶段容量约束选址—路径协同模型。第一阶段枚举候选站组合并利用0-1分配MILP满足四类存储容量；第二阶段对各站内各垃圾类型执行节约法与局部优化，同时计入中转站至处理厂的干线往返、建设成本10年日均摊销和碳排放。经成本—排放非支配评价，最优站点组合为31号与34号，中转站日均摊销成本287.67元，运输成本4159.8元，总日成本4447.47元，总距离1522 km，排放指标1262.38 kg。进一步依据附件5将单行道与禁行时段转化为有向距离矩阵，固定选址分配后重新优化，非对称路网使总距离增加56 km（3.68%），表明忽略方向性会系统性低估运营成本。
  综合而言，本文形成了“数据理解与探索→数据预处理→特征工程→精确/启发式模型构建→算法求解与对照评估→结果解释与鲁棒性分析”的完整建模链条。问题一给出可验证的全局最优基准，问题二在其基础上扩展至异构多资源车辆，问题三进一步耦合设施选址、时间窗口和环境目标。敏感性与蒙特卡洛分析表明：容积参数变化主要影响有害垃圾的趟次下界；31号站厨余容量利用率接近100%，使当前两站方案对需求扰动较敏感。因此实际部署时应设置容量安全系数、滚动更新需求并采用动态路网重优化。

模型假设：

  假设1：所有收集点的日需求在计划开始前已知，且同一垃圾类型在一天内不随时间继续产生；每个点的某类垃圾在一日计划中由一条路线完整收集，不进行拆分服务。
  假设2：问题一中仅考虑附件1给出的单一厨余垃圾量；问题二和问题三使用附件3的四类垃圾量。附件3被题目描述为“调整后的四类垃圾场景”，故不将其逐点合计强制校正为附件1总量。
  假设3：车辆从指定中心节点出发并返回：问题一、二的中心为处理厂0；问题三的支线收集中心为已分配中转站，垃圾汇集后通过同类型车辆进行中转站—处理厂干线往返。
  假设4：附件5规定对称路网距离按欧氏距离四舍五入取整。除非进入非对称情景，行驶距离满足对称性；车辆平均速度统一为40 km/h。
  假设5：附件未提供收集点服务时长。为完成物理车辆调度和时间窗口验证，设置每点平均服务时间4.8 min；该值为情景参数而非附件观测，代码可通过命令行修改。
  假设6：附件未提供各垃圾类型的单位质量体积。设置厨余、可回收物、有害、其他垃圾的比体积分别为2.0、3.5、4.0、1.5 m³/t，并使用敏感性分析验证±20%扰动；数值结论中明确区分题给参数与情景参数。
  假设7：中转站建设成本按10年、365日等额摊销，不考虑资金时间价值、维修残值和停运日；若实际项目采用折现现金流，可用资本回收因子替代。
  假设8：碳排放按题给线性形式计算，忽略车辆速度、拥堵、怠速和冷启动对排放的非线性影响；碳排放作为第二评价目标，不擅自将其折算为未给定的碳价。
  假设9：中转站每日清空，因而没有跨日库存；站点容量表示单日各类型最大可接收量。
  假设10：单行道和禁行时段通过有向/时变弧权处理。数值对比采用附件5给出的绕行距离作为静态有向情景；理论模型保留d_ij(t)以支持实时禁行。

问题分析：

  问题一问题分析
  本题属于带不可拆分需求的容量约束车辆路径 CVRP 组合优化问题，是整套垃圾分类运输调度体系的基准底层模块。核心难点：总载重理论下界仅为必要条件，受收集点垃圾不可拆分约束，总量下界不一定存在可行装载分组；同时需要同时完成 “收集点分组、组内访问 TSP 顺序、多趟任务向物理车辆分配” 三层耦合决策，传统启发算法难以证明最优性。建模思路：完成坐标、垃圾量数据清洗与对称距离矩阵构建，生成全部满足载重上限的可行候选路线集合，采用集合划分 MILP 字典序双目标模型，优先最小化运输趟次，再最小化总行驶距离；通过枚举小规模候选路线实现精确求解，避免贪心算法局部最优缺陷；引入处理厂 6‑18 小时时间窗口、单点服务时长约束，将多趟路线转化为一维装箱调度分配物理车辆；将角度扫描法、Clarke‑Wright 节约法作为基线对照，验证精确模型的距离缩减效果，输出趟次、路线、车辆调度全套结果，为后两问提供距离计算、时间核算、路线评价统一工具。
  问题二问题分析
  本题属于专车专运下异构双资源 CVRP 优化问题，完全复用问题一坐标、距离矩阵、时间核算体系，新增四类垃圾、对应专用车辆质量‑容积双重硬约束。核心难点：不同垃圾禁止混装，四类子问题相互独立；车辆同时受最大载重、最大容积双重限制，需要换算等效质量容量；有害垃圾产生总量很小，但必须遍历全部收集点，吨量低不等于行驶距离短；车辆每日最大工作时长会直接约束单条路线最大耗时，触发任务拆分、物理车辆数量扩容。建模思路：引入各类垃圾单位质量体积参数，计算等效容量统一刻画双重资源约束；采用 “容量约束 MILP 聚类‑最近邻初序‑2‑opt 内部优化‑Relocate/Swap 跨路线扰动‑迭代局部搜索” 混合启发框架；分四类独立求解，汇总总行驶里程、运输成本、碳排放指标；分别仿真 12h、6h 两种工作窗口，对比时间约束收紧对车辆配置的影响；与扫描法、节约法多算法横向对比择优，识别有害垃圾 “低产量高运输成本” 特殊机理，为中转站综合调度提供成本、排放基础输入。
  问题三问题分析
  本题属于容量约束选址‑路径协同 CLRP 综合优化问题，耦合中转站 0‑1 选址、收集点分配、站内多类型车辆路径、支线 + 干线运输、建设摊销、碳排放、非对称路网多重约束。核心难点：选址决策与路径优化相互耦合，仅按距离就近分配会忽略中转站分类型存储容量限制；中转站建设摊销、运输运行成本属于不同量纲，同时需要兼顾碳排放目标；单行道、禁行时段形成非对称有向路网，反转路径不再等价，会改变整体里程与成本。建模思路：采用两阶段反馈校核策略，第一阶段对全部候选中转站组合做 0‑1 分配 MILP，严格满足分类型存储容量约束，使用代理成本快速筛选可行站点组合；第二阶段对选中站点，站内复用问题二混合路径算法求解支线收集路线，叠加中转站往返处理厂的干线运输，计入建设成本 10 年日均摊销，得到真实总日成本与碳排放；构建 Pareto 评价筛选膝点最优方案；固定最优选址分配方案，将附件单行道规则转化为有向距离矩阵重新求解，量化非对称路网带来的里程与成本增幅；开展容积参数、建设成本、需求蒙特卡洛扰动敏感性分析，识别容量紧约束带来的鲁棒风险，给出容量安全系数、边界点动态重分配工程改进建议，形成 “收集‑中转‑处理” 全链条优化闭环。

模型的建立与求解整体论文缩略图

全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可

程序代码：

部分程序如下:

from __future__ import annotations

import argparse
import os, sys
import itertools
import json
import math
import random
import time
from dataclasses import dataclass
from pathlib import Path
from typing import Dict, Iterable, List, Sequence, Tuple, Optional, Any

import numpy as np
import pandas as pd
from openpyxl import load_workbook
from scipy.optimize import milp, LinearConstraint, Bounds
from sklearn.cluster import KMeans

import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
from matplotlib import font_manager
from matplotlib.patches import FancyArrowPatch


# ------------------------------ 基础配置 ------------------------------
CN_FONT_FILE = "/usr/share/fonts/opentype/noto/NotoSansCJK-Regular.ttc"
SERIF_CN_FONT_FILE = "/usr/share/fonts/opentype/noto/NotoSerifCJK-Regular.ttc"
try:
    font_manager.fontManager.addfont(CN_FONT_FILE)
    CN_FONT = font_manager.FontProperties(fname=CN_FONT_FILE).get_name()
    plt.rcParams["font.family"] = CN_FONT
    plt.rcParams["font.sans-serif"] = [CN_FONT]
except Exception:
    CN_FONT = "DejaVu Sans"
    plt.rcParams["font.sans-serif"] = [CN_FONT]
plt.rcParams["axes.unicode_minus"] = False
plt.rcParams["figure.dpi"] = 150
plt.rcParams["savefig.dpi"] = 220
plt.rcParams["axes.titleweight"] = "bold"
plt.rcParams["axes.grid"] = True
plt.rcParams["grid.alpha"] = 0.22

COLORS = ["#2F6690", "#3A7D44", "#D1495B", "#F4A261", "#7B2CBF", "#008C95", "#8D6E63"]
WASTE_CN = ["厨余垃圾", "可回收物", "有害垃圾", "其他垃圾"]
WASTE_KEYS = ["food", "recyclable", "hazardous", "other"]


@dataclass
class VehicleParam:
    k: int
    waste_type: str
    mass_capacity: float
    volume_capacity: float
    distance_cost: float
    alpha: float
    beta: float
    specific_volume: float

    @property
    def effective_mass_capacity(self) -> float:
        return min(self.mass_capacity, self.volume_capacity / self.specific_volume)


@dataclass
class Station:
    station_id: int
    x: float
    y: float
    construction_cost_wan: float
    open_hour: float
    close_hour: float
    capacities: List[float]

    @property
    def daily_amortized_cost(self) -> float:
        return self.construction_cost_wan * 10000.0 / (10.0 * 365.0)

    @property
    def window_width(self) -> float:
        return self.close_hour - self.open_hour


def round_half_up(x: float) -> int:
    return int(math.floor(x + 0.5))


def safe_float(v: Any) -> float:
    if isinstance(v, str):
        return float(v.strip())
    return float(v)


def parse_list_text(v: Any) -> List[float]:
    if isinstance(v, (list, tuple)):
        return [float(x) for x in v]
    txt = str(v).strip().strip("[]")
    return [float(x.strip()) for x in txt.split(",")]


def resolve_file(data_dir: Path, candidates: Sequence[str]) -> Path:
    for name in candidates:
        p = data_dir / name
        if p.exists():
            return p
    # 容错：按关键词查找
    for p in data_dir.iterdir():
        if p.suffix.lower() == ".xlsx" and any(c.replace(".xlsx", "") in p.stem for c in candidates):
            return p
    raise FileNotFoundError(f"未找到文件，候选名：{candidates}")


def load_data(data_dir: Path, specific_volumes: Sequence[float]) -> Tuple[pd.DataFrame, pd.DataFrame, List[VehicleParam], List[Station]]:
    p1 = resolve_file(data_dir, ["附件1(2).xlsx", "附件1.xlsx"])
    p2 = resolve_file(data_dir, ["附件2(2).xlsx", "附件2.xlsx"])
    p3 = resolve_file(data_dir, ["附件3(1).xlsx", "附件3.xlsx"])
    p4 = resolve_file(data_dir, ["附件4.xlsx"])

    wb = load_workbook(p1, data_only=True)
    ws = wb.active
    rows = []
    for r in range(4, 34):
        rows.append({
            "id": int(ws.cell(r, 1).value),
            "x": safe_float(ws.cell(r, 2).value),
            "y": safe_float(ws.cell(r, 3).value),
            "total_waste": safe_float(ws.cell(r, 4).value),
        })
    points = pd.DataFrame(rows)

    wb = load_workbook(p3, data_only=True)
    ws = wb.active
    rows = []
    for r in range(3, 33):
        rows.append({
            "id": int(ws.cell(r, 1).value),
            "food": safe_float(ws.cell(r, 2).value),
            "recyclable": safe_float(ws.cell(r, 3).value),
            "hazardous": safe_float(ws.cell(r, 4).value),
            "other": safe_float(ws.cell(r, 5).value),
        })
    waste4 = pd.DataFrame(rows)
    waste4["four_type_total"] = waste4[WASTE_KEYS].sum(axis=1)
    points = points.merge(waste4, on="id", how="left")

    wb = load_workbook(p2, data_only=True)
    ws = wb.active
    vehicles: List[VehicleParam] = []
    for idx, r in enumerate(range(3, 7)):
        vehicles.append(VehicleParam(
            k=int(ws.cell(r, 1).value),
            waste_type=str(ws.cell(r, 2).value).strip(),
            mass_capacity=safe_float(ws.cell(r, 3).value),
            volume_capacity=safe_float(ws.cell(r, 4).value),
            distance_cost=safe_float(ws.cell(r, 5).value),
            alpha=safe_float(ws.cell(r, 6).value),
            beta=safe_float(ws.cell(r, 7).value),
            specific_volume=float(specific_volumes[idx]),
        ))

    wb = load_workbook(p4, data_only=True)
    ws = wb.active
    stations: List[Station] = []
    for r in range(3, 8):
        tw = parse_list_text(ws.cell(r, 5).value)
        caps = parse_list_text(ws.cell(r, 6).value)
        stations.append(Station(
            station_id=int(ws.cell(r, 1).value),
            x=safe_float(ws.cell(r, 2).value),
            y=safe_float(ws.cell(r, 3).value),
            construction_cost_wan=safe_float(ws.cell(r, 4).value),
            open_hour=tw[0], close_hour=tw[1], capacities=caps,
        ))
    return points, waste4, vehicles, stations


def build_coordinates(points: pd.DataFrame, stations: Sequence[Station]) -> Dict[int, Tuple[float, float]]:
    coords = {0: (0.0, 0.0)}
    for row in points.itertuples(index=False):
        coords[int(row.id)] = (float(row.x), float(row.y))
    for s in stations:
        coords[s.station_id] = (s.x, s.y)
    return coords


def build_distance_matrix(coords: Dict[int, Tuple[float, float]], asymmetric: bool = False) -> np.ndarray:
    nmax = max(coords) + 1
    D = np.zeros((nmax, nmax), dtype=int)
    for i, (xi, yi) in coords.items():
        for j, (xj, yj) in coords.items():
            D[i, j] = round_half_up(math.hypot(xi - xj, yi - yj))
    if asymmetric:
        # 附件5给出的方向性/绕行示例。禁行时段在静态对比中采用绕行距离。
        overrides = {
            (4, 31): 18, (31, 4): 15,
            (27, 28): 14, (28, 27): 18,
            (23, 0): 45, (0, 23): 40,
            (9, 16): 8, (16, 9): 10,
        }
        for (i, j), d in overrides.items():
            if i < nmax and j < nmax:
                D[i, j] = d
    return D


def route_distance(route: Sequence[int], depot: int, D: np.ndarray) -> int:
    if not route:
        return 0
    return int(D[depot, route[0]] + sum(D[route[i], route[i + 1]] for i in range(len(route) - 1)) + D[route[-1], depot])


def route_load(route: Sequence[int], demand: Dict[int, float]) -> float:
    return float(sum(demand[i] for i in route))


def nearest_neighbor_order(nodes: Sequence[int], depot: int, D: np.ndarray) -> List[int]:
    remaining = set(nodes)
    current = depot
    route: List[int] = []
    while remaining:
        nxt = min(remaining, key=lambda j: (D[current, j], D[depot, j], j))
        route.append(nxt)
        remaining.remove(nxt)
        current = nxt
    return route


def two_opt(route: Sequence[int], depot: int, D: np.ndarray) -> List[int]:
    r = list(route)
    if len(r) < 3:
        return r
    best = route_distance(r, depot, D)
    improved = True
    while improved:
        improved = False
        for i in range(len(r) - 1):
            for j in range(i + 1, len(r)):
                cand = r[:i] + list(reversed(r[i:j + 1])) + r[j + 1:]
                c = route_distance(cand, depot, D)
                if c < best:
                    r, best = cand, c
                    improved = True
                    break
            if improved:
                break
    return r


def clarke_wright(demand: Dict[int, float], capacity: float, depot: int, D: np.ndarray) -> List[List[int]]:
    routes: Dict[int, List[int]] = {i: [i] for i in demand}
    owner = {i: i for i in demand}
    loads = {i: demand[i] for i in demand}
    savings = []
    ids = list(demand)
    for a, b in itertools.combinations(ids, 2):
        savings.append((D[depot, a] + D[depot, b] - D[a, b], a, b))
    savings.sort(reverse=True)
    for _, a, b in savings:
        ra_id, rb_id = owner[a], owner[b]
        if ra_id == rb_id:
            continue
        ra, rb = routes[ra_id], routes[rb_id]
        if loads[ra_id] + loads[rb_id] > capacity + 1e-9:
            continue
        possibilities = []
        if ra[-1] == a and rb[0] == b:
            possibilities.append(ra + rb)
        if ra[0] == a and rb[-1] == b:
            possibilities.append(rb + ra)
        if ra[0] == a and rb[0] == b:
            possibilities.append(list(reversed(ra)) + rb)
        if ra[-1] == a and rb[-1] == b:
            possibilities.append(ra + list(reversed(rb)))
        if not possibilities:
            continue
        merged = min(possibilities, key=lambda r: route_distance(r, depot, D))
        new_id = ra_id
        routes[new_id] = merged
        loads[new_id] += loads[rb_id]
        for node in rb:
            owner[node] = new_id
        del routes[rb_id]
        del loads[rb_id]
    return [two_opt(r, depot, D) for r in routes.values()]


def sweep_greedy(demand: Dict[int, float], capacity: float, depot: int, D: np.ndarray,
                 coords: Dict[int, Tuple[float, float]]) -> List[List[int]]:
    ids = sorted(demand, key=lambda i: math.atan2(coords[i][1] - coords[depot][1], coords[i][0] - coords[depot][0]))
    routes: List[List[int]] = []
    current: List[int] = []
    load = 0.0
    for i in ids:
        if current and load + demand[i] > capacity + 1e-9:
            routes.append(two_opt(current, depot, D))
            current, load = [], 0.0
        current.append(i)
        load += demand[i]
    if current:
        routes.append(two_opt(current, depot, D))
    return routes


def exact_q1_set_partition(demand: Dict[int, float], capacity: float, depot: int, D: np.ndarray) -> Dict[str, Any]:
    ids = list(sorted(demand))
    max_card = int(math.floor(capacity / min(demand.values()) + 1e-9))
    candidates = []
    for r in range(1, max_card + 1):
        for subset in itertools.combinations(ids, r):
            load = sum(demand[i] for i in subset)
            if load <= capacity + 1e-9:
                best_cost = math.inf
                best_path: Tuple[int, ...] = tuple()
                for perm in itertools.permutations(subset):
                    c = route_distance(perm, depot, D)
                    if c < best_cost:
                        best_cost, best_path = c, perm
                candidates.append({"nodes": subset, "load": load, "cost": int(best_cost), "path": list(best_path)})

    A = np.zeros((len(ids), len(candidates)))
    id_pos = {node: idx for idx, node in enumerate(ids)}
    for j, r in enumerate(candidates):
        for node in r["nodes"]:
            A[id_pos[node], j] = 1
    cover = LinearConstraint(A, np.ones(len(ids)), np.ones(len(ids)))
    bounds = Bounds(np.zeros(len(candidates)), np.ones(len(candidates)))
    integrality = np.ones(len(candidates))

    t0 = time.perf_counter()
    phase1 = milp(c=np.ones(len(candidates)), integrality=integrality, bounds=bounds,
                  constraints=cover, options={"time_limit": 60})
    if not phase1.success:
        raise RuntimeError(f"问题一阶段1未求得最优解：{phase1.message}")
    min_routes = int(round(phase1.fun))
    route_count_constraint = LinearConstraint(np.ones((1, len(candidates))), [min_routes], [min_routes])
    phase2 = milp(c=np.array([r["cost"] for r in candidates], dtype=float),
                  integrality=integrality, bounds=bounds,
                  constraints=[cover, route_count_constraint], options={"time_limit": 120})
    if not phase2.success:
        raise RuntimeError(f"问题一阶段2未求得最优解：{phase2.message}")
    elapsed = time.perf_counter() - t0
    selected = [candidates[j] for j, x in enumerate(phase2.x) if x > 0.5]
    selected.sort(key=lambda r: (math.atan2(np.mean([0] + [0]), 1), r["path"]))
    routes = [r["path"] for r in selected]
    return {
        "candidate_count": len(candidates),
        "max_route_cardinality": max_card,
        "min_route_count": min_routes,
        "total_distance": int(round(phase2.fun)),
        "routes": routes,
        "route_loads": [route_load(r, demand) for r in routes],
        "route_distances": [route_distance(r, depot, D) for r in routes],
        "solve_seconds": elapsed,
        "mip_status": phase2.message,
    }

全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可