1. 赛题拆解从“未来新城”到“可达率”的核心逻辑刚拿到2024年五一数学建模竞赛B题时很多同学可能会被“未来新城”这个宏大的背景唬住觉得是不是要搞什么科幻预测。其实完全不是这道题的核心非常“数学建模”它本质上是一个经典的网络流优化问题披上了一层城市规划的外衣。我参加过不少建模比赛也带过队这种题最怕的就是被背景故事带偏陷入对“未来”的无尽遐想而忽略了题目给出的具体数据和约束。咱们得先拨开云雾看看骨架。题目给了我们一个未来新城的交通网络这个网络由节点可以理解为小区、商业区、交通枢纽和边道路组成。每条边有最大通行能力容量每个节点有交通需求的发生量和吸引量。这里的“需求”不是指现在有多少车想走而是规划意义上的“潜在出行量”——比如一个居住区每天会产生多少通勤出行发生量一个商务区每天会吸引多少上班人流吸引量。问题的核心目标是在道路容量限制下如何分配交通流量使得整个网络中从任意起点到任意终点的出行需求中实际能够被满足的比例即可达率尽可能高。这听起来有点像“在水管网络有粗细限制的情况下如何分配水流让尽可能多的水能从各个水源地流到需要用水的地方”。这里的关键词是“可达率”。它不是简单的“总运量最大化”而是强调出行的成功率。举个例子如果A小区到B商场有100人的出行需求但道路太堵只满足了30人那么这对起讫点OD对的可达率就是30%。我们要优化的是所有OD对可达率的整体表现很可能是一个加权平均比如按需求大小加权目标是让这个整体值最大。这意味着建模时我们不能只盯着几条主干道拼命塞流量而要兼顾那些需求小但路径脆弱的出行否则它们可达率会跌得很惨拉低整体分数。这是第一个需要建立的思维公平与效率的权衡。2. 模型选择为什么是线性规划与网络流理论面对这样一个有容量限制、有供需关系、追求整体最优的问题我们工具箱里的首选武器就是线性规划Linear Programming, LP更具体地说是网络流问题Network Flow Problem中的多商品流问题Multi-commodity Flow Problem的一个变体。为什么是它我们来拆解一下题目要素与模型的对应关系决策变量我们需要决定每条道路上承载的流量是多少。更精细地我们需要决定每一对起点O和终点D之间的出行需求具体选择哪条路径来走以及在这条路径上分配多少流量。这就是x_{ij}^{k}表示从起点k到终点k的出行需求经过道路(i, j)的流量。目标函数我们的目标是最大化整体可达率。假设总共有N个OD对第k个OD对的需求量为d_k实际被满足的流量为f_k即所有从O_k出发、最终到达D_k的流量总和。那么这对OD的可达率为f_k / d_k。整体目标可以是最大化总满足流量Σf_k但这可能偏向于需求大的OD对或者更贴合“可达率”精神的最大化需求加权平均可达率Maximize Σ (d_k * (f_k / d_k)) / Σ d_k Σ f_k / Σ d_k。由于总需求Σ d_k是常数最大化Σ f_k等价于最大化加权平均可达率。但这里有个关键点题目可能要求每对OD的可达率都不能低于某个阈值或者对最低的可达率有要求。这就需要仔细审题。在标准解读下最大化总满足流量是一个合理且可操作的线性目标。约束条件这是模型的核心。道路容量约束对于每条道路(i, j)所有OD对分配在上面的流量之和不能超过该道路的最大容量u_ij。即Σ_{k} x_{ij}^{k} ≤ u_ij。这是最硬的物理限制。流量守恒约束对于每个节点和每个OD对k需要满足“流入等于流出”的定律除了起点和终点。在起点O_k净流出量 f_k该OD对被满足的总流量。在终点D_k净流入量 f_k。在中间节点对于OD对k流入该节点的流量总和等于流出该节点的流量总和。需求约束对于每个OD对k实际被满足的流量f_k不能超过其需求量d_k。即f_k ≤ d_k。非负约束所有流量x_{ij}^{k}和f_k都必须大于等于0。看到没决策变量、目标函数、所有约束都是线性的。所以一个线性规划模型完美契合。如果网络规模很大节点和OD对很多直接为每个OD对、每条路径建立变量会导致变量数爆炸这是多商品流问题的常见难点。这时我们通常采用路径流Path Flow或链路流Link Flowformulation。在建模竞赛中鉴于问题规模通常可控使用商业求解器如Gurobi, CPLEX或优化库如PuLP in Python直接求解这个线性规划问题是完全可行的。3. 求解策略从理论模型到可运行代码思路清晰了模型建立了接下来就是怎么把它变成计算机能解的问题。这里我分享一套经过实战检验的求解策略重点是如何用Python高效地实现。3.1 数据处理与网络构建题目数据通常会以表格形式给出节点信息节点编号、发生量、吸引量和边信息起点、终点、容量。我们的第一步是将其转化为程序中的网络结构。import pandas as pd import numpy as np import pulp # 一个优秀的线性规划建模库 # 1. 读取数据 (假设有nodes.csv和edges.csv) nodes_df pd.read_csv(nodes.csv) # 列可能包括: node_id, generate, attract edges_df pd.read_csv(edges.csv) # 列可能包括: from_node, to_node, capacity # 2. 构建网络字典和需求矩阵 # 节点列表 nodes nodes_df[node_id].tolist() # 边容量字典键为(起点, 终点)值为容量 capacity {(row[from_node], row[to_node]): row[capacity] for _, row in edges_df.iterrows()} # 3. 生成OD需求对 # 这是关键一步。每个节点的发生量需要分配到其他节点作为目的地吸引量来自其他节点。 # 一种常见简化是假设出行需求与发生量、吸引量成正比。 # 例如从节点i到节点j的需求 d_{ij} (generate_i * attract_j) / (总吸引量 - attract_i) * 某个缩放因子 # 更精细的做法可能需要重力模型但赛题常会直接给出或暗示生成规则。 # 这里假设我们已经计算好了一个demand_dict键为(origin, destination)值为需求量。 demand_dict {} # 需要你根据题目具体说明来填充这个字典 # 示例遍历所有节点对根据发生/吸引量计算需求需避免自己到自己 total_attract nodes_df[attract].sum() for _, orig_row in nodes_df.iterrows(): orig orig_row[node_id] orig_gen orig_row[generate] if orig_gen 0: continue for _, dest_row in nodes_df.iterrows(): dest dest_row[node_id] if orig dest: continue # 通常不考虑区内出行或单独处理 dest_attr dest_row[attract] # 简单的重力模型计算α是调节系数可能需要标定或题目给出 d orig_gen * dest_attr / (total_attract - nodes_df.loc[nodes_df[node_id]orig, attract].values[0]) demand_dict[(orig, dest)] d # 获取所有OD对列表 od_pairs list(demand_dict.keys())3.2 线性规划模型构建使用PuLPPuLP库允许我们用非常直观的方式描述线性规划问题。# 1. 定义问题 # 最大化问题问题名称 prob pulp.LpProblem(FutureCity_Transportation_Optimization, pulp.LpMaximize) # 2. 定义决策变量 # 变量1: 为每个OD对和每条边定义流量变量代表该OD对在这条边上的流量。 # 注意变量数量是 |OD对| * |边|如果很大需要考虑简化如先找K短路。 # 这里为了清晰先展示完整定义。实践中对于大规模网络需要结合路径生成。 flow_vars {} for (i, j) in capacity.keys(): for (o, d) in od_pairs: var_name fflow_{o}_{d}_{i}_{j} # 流量非负连续变量 flow_vars[(o, d, i, j)] pulp.LpVariable(var_name, lowBound0, catContinuous) # 变量2: 每个OD对实际被满足的流量 f_{od} f_od_vars {} for (o, d) in od_pairs: var_name ffulfilled_{o}_{d} f_od_vars[(o, d)] pulp.LpVariable(var_name, lowBound0, catContinuous) # 3. 定义目标函数最大化总满足流量 Σ f_{od} prob pulp.lpSum([f_od_vars[(o, d)] for (o, d) in od_pairs]) # 4. 添加约束条件 # (1) 道路容量约束每条边上的总流量所有OD对之和不超过容量 for (i, j) in capacity.keys(): prob pulp.lpSum([flow_vars[(o, d, i, j)] for (o, d) in od_pairs]) capacity[(i, j)] # (2) 流量守恒约束对每个节点每个OD对 for node in nodes: for (o, d) in od_pairs: if node o: # 起点净流出 f_{od} outflow pulp.lpSum([flow_vars[(o, d, node, j)] for j in nodes if (node, j) in capacity]) inflow pulp.lpSum([flow_vars[(o, d, i, node)] for i in nodes if (i, node) in capacity]) prob (outflow - inflow f_od_vars[(o, d)]) elif node d: # 终点净流入 f_{od} outflow pulp.lpSum([flow_vars[(o, d, node, j)] for j in nodes if (node, j) in capacity]) inflow pulp.lpSum([flow_vars[(o, d, i, node)] for i in nodes if (i, node) in capacity]) prob (inflow - outflow f_od_vars[(o, d)]) else: # 中间节点流入 流出 outflow pulp.lpSum([flow_vars[(o, d, node, j)] for j in nodes if (node, j) in capacity]) inflow pulp.lpSum([flow_vars[(o, d, i, node)] for i in nodes if (i, node) in capacity]) prob (inflow outflow) # (3) 需求约束满足流量不超过需求量 for (o, d) in od_pairs: prob f_od_vars[(o, d)] demand_dict[(o, d)] # 5. 求解问题 solver pulp.PULP_CBC_CMD(msgFalse) # 使用CBC求解器不输出日志 prob.solve(solver) # 6. 检查状态并输出结果 print(pulp.LpStatus[prob.status]) if pulp.LpStatus[prob.status] Optimal: total_fulfilled pulp.value(prob.objective) total_demand sum(demand_dict.values()) overall_accessibility total_fulfilled / total_demand print(f总满足流量: {total_fulfilled}) print(f总需求: {total_demand}) print(f整体可达率: {overall_accessibility:.4f}) # 可以查看每个OD对的可达率 for (o, d) in od_pairs: fulfilled pulp.value(f_od_vars[(o, d)]) demand demand_dict[(o, d)] if demand 0: rate fulfilled / demand print(fOD ({o}-{d}): 需求{demand:.2f}, 满足{fulfilled:.2f}, 可达率{rate:.4f})注意上面的代码是一个概念性框架。直接运行可能会因为变量过多OD对数×边数而导致模型过大。在实际竞赛中你需要根据题目给出的网络规模来判断。如果规模很大必须进行优化。3.3 模型优化与降维技巧当网络节点成百上千时上述模型的变量数会达到百万甚至千万级求解变得困难。这时需要一些降维技巧聚合OD对并非所有节点间都有显著需求。可以根据发生/吸引量只保留需求最大的前N对OD或者设定一个需求阈值。使用路径流变量这是更高效的方法。我们不为每条边上的每个OD流建变量而是为每个OD对预先计算几条候选路径如K条最短路径然后决策变量变为“每个OD对在第k条路径上分配多少流量”。这样变量数从|OD| * |E|降为|OD| * K。步骤 a. 使用networkx库的shortest_simple_paths函数为每个OD对找K条最短路按距离或时间。 b. 决策变量变为x_{od}^{p}表示OD对(od)在路径p上的流量。 c. 约束变为 * 路径流量非负。 * 每个OD对在各路径上的流量之和等于其被满足的流量f_od。 * 对于每条边所有经过它的路径的流量之和不超过该边容量。优点变量大大减少模型更紧凑。缺点如果K太小可能漏掉最优解因为最优流量分配可能走非最短路径K太大则变量又变多。需要权衡。启发式或分解算法如果问题规模实在太大可以考虑拉格朗日松弛法、列生成法等高级优化算法但这通常超出本科数模竞赛范围研究生赛可能会涉及。对于五一赛题这种中等规模的题目“路径流”模型通常是性价比最高的选择。下面给出一个简化版的路径流模型代码框架import networkx as nx # 假设我们已经有了一个图G边权可以是距离或1找最少跳数路径 G nx.DiGraph() for idx, row in edges_df.iterrows(): G.add_edge(row[from_node], row[to_node], capacityrow[capacity]) # 为每个OD对寻找K条最短路径这里按跳数最少 K 3 # 每个OD对考虑的路径数可调整 od_paths {} # 键为(origin, destination)值为路径列表路径是节点列表 for (o, d) in od_pairs: if o d: continue try: # 使用yen算法找K条最短简单路径 paths list(nx.shortest_simple_paths(G, o, d)) od_paths[(o, d)] paths[:K] # 取前K条 except nx.NetworkXNoPath: od_paths[(o, d)] [] print(fNo path found for OD ({o}, {d})) # 重新构建PuLP模型使用路径变量 prob_path pulp.LpProblem(Path_Based_Model, pulp.LpMaximize) # 决策变量每个OD对在每条路径上的流量 path_flow_vars {} path_edge_usage {} # 记录每条路径用了哪些边用于后续容量约束 for (o, d), paths in od_paths.items(): for idx, path in enumerate(paths): var_name fpathflow_{o}_{d}_{idx} path_flow_vars[(o, d, idx)] pulp.LpVariable(var_name, lowBound0) # 记录路径经过的边 edges_in_path [(path[i], path[i1]) for i in range(len(path)-1)] path_edge_usage[(o, d, idx)] edges_in_path # 变量每个OD对满足的流量 f_od f_od_vars_path {od: pulp.LpVariable(ffulfilled_path_{od[0]}_{od[1]}, lowBound0) for od in od_pairs} # 目标函数最大化总满足流量 prob_path pulp.lpSum(list(f_od_vars_path.values())) # 约束1: 每个OD对在各路径上的流量之和等于其被满足的流量 for (o, d) in od_pairs: relevant_vars [path_flow_vars[(o, d, idx)] for idx in range(len(od_paths.get((o,d), [])))] prob_path pulp.lpSum(relevant_vars) f_od_vars_path[(o, d)] # 约束2: 每个OD对满足的流量不超过其需求 for (o, d) in od_pairs: prob_path f_od_vars_path[(o, d)] demand_dict[(o, d)] # 约束3: 边容量约束 (这是最关键的约束) # 需要遍历每条边计算所有用到这条边的路径流量之和 edge_flow {edge: 0 for edge in capacity.keys()} # 初始化边上总流量为0 for (o, d, idx), var in path_flow_vars.items(): edges path_edge_usage[(o, d, idx)] for e in edges: if e in edge_flow: edge_flow[e] var # 这是一个表达式累加不是数值累加 # 添加容量约束 for edge, cap in capacity.items(): prob_path edge_flow[edge] cap # 求解 prob_path.solve(solver)4. 结果分析与可视化让论文“亮”起来模型求解完输出一堆数字只是第一步。如何分析并呈现结果是拿高分的关键。你需要从多个维度解读数据。整体指标如前所述计算并报告总满足流量、总需求、整体可达率。这是对方案效果的总体评价。瓶颈识别哪些道路的容量利用率最高接近100%这些就是网络的瓶颈。# 计算每条边的利用率 edge_utilization {} for (i, j), cap in capacity.items(): total_flow_on_edge sum(pulp.value(flow_vars.get((o, d, i, j), 0)) for (o, d) in od_pairs) # 对于边流模型 # 或者从路径流模型结果中反推边上的流量 utilization total_flow_on_edge / cap if cap 0 else 0 edge_utilization[(i, j)] utilization # 找出利用率最高的前10条边 bottlenecks sorted(edge_utilization.items(), keylambda x: x[1], reverseTrue)[:10]在论文中可以列出表格并指出这些瓶颈路段是制约整体可达率提升的关键。可以建议“未来新城”规划时优先对这些路段进行扩容如增加车道、建设高架。公平性分析计算每个OD对的可达率绘制分布直方图或箱线图。如果大部分OD对可达率都很高但少数几对极低说明方案在公平性上有问题。你可以计算可达率的基尼系数或标准差来衡量公平性。在目标函数中引入对最低可达率的考量例如最大化最差OD对的可达率即Max-Min公平是模型的一个高级拓展方向。可视化网络流量热力图使用networkx和matplotlib绘制网络图边的粗细或颜色代表其流量大小。瓶颈路段用醒目的红色标出。import matplotlib.pyplot as plt pos nx.spring_layout(G) # 或其他布局算法 edge_widths [edge_flow.get((u, v), 0) / max(edge_flow.values()) * 5 for u, v in G.edges()] # 宽度按流量比例缩放 edge_colors [red if edge_utilization.get((u, v), 0) 0.9 else gray for u, v in G.edges()] # 利用率90%标红 nx.draw(G, pos, with_labelsTrue, node_size300, widthedge_widths, edge_coloredge_colors) plt.title(Traffic Flow Distribution and Bottlenecks) plt.show()可达率分布图用柱状图展示各OD对的可达率或绘制可达率关于出行距离的散点图观察是否存在“远距离出行可达率普遍偏低”的现象。灵敏度分析加分项探讨关键参数变化对结果的影响。例如容量提升如果将所有道路容量统一提升10%整体可达率能提升多少这能为投资决策提供依据。需求变化如果某个区域如新CBD的吸引量突然增加20%对网络瓶颈和整体可达率有何影响这考验网络的鲁棒性。关键路段失效模拟某条关键桥梁或隧道关闭容量设为0观察可达率的下降情况评估其重要性。进行灵敏度分析时不需要重新手动调整模型。只需写一个循环修改对应的数据capacity或demand_dict然后重新求解模型并记录目标函数值的变化。在论文中用图表展示这种变化关系会极大提升分析的深度。5. 论文撰写与常见陷阱规避有了模型、代码和结果最后一步是把它们组织成一篇逻辑清晰的数学建模论文。这里分享几个容易踩坑的地方和应对技巧。1. 问题重述不是照抄题目要用自己的话提炼出问题的核心要素网络、节点供需、边容量、可达率目标和核心任务分配流量、最大化可达率。可以画一个简单的示意图。2. 模型假设要合理且明确这是论文的基石。对于本题常见的合理假设包括交通流量是连续的可以是非整数这符合宏观交通流模型的特性。出行需求在规划期内是固定的早高峰稳态。出行者路径选择完全服从系统最优分配即我们模型给出的方案不考虑个人随机选择。这是一个典型的系统最优SO模型而非用户均衡UE模型。道路通行能力与流量无关即不考虑拥堵导致的容量下降。这是一个简化如果题目要求考虑拥堵则需要引入速度-流量关系如BPR函数模型会变成非线性复杂度飙升。务必仔细审题看是否要求考虑拥堵。3. 符号说明要清晰制作一个三列表格符号、含义、单位确保文中使用的每个主要符号都有定义。这是规范性体现。4. 模型建立部分要有层次先讲网络流基础介绍图论中的点、边、流量守恒等概念。再定义决策变量和目标清晰写出x_{ij}^{k}和f_k以及目标函数max Σ f_k。然后逐条解释约束容量约束、守恒约束、需求约束。每一条约束都要用文字说明其物理或逻辑意义。最后给出完整的数学模型将目标函数和所有约束用公式集中展示。可以称之为“模型P”或“模型1”。5. 求解方法部分要具体不要只说“我们用线性规划求解”。要说明为什么用线性规划因为目标函数和约束都是线性的。说明你使用的求解器如PuLP调用CBC或MATLAB的linprog或Lingo。如果采用了路径流降维要详细说明K条最短路径是如何生成的算法K值选取理由。给出算法流程图可以用Visio或PPT画清晰美观。6. 结果分析要图文并茂核心结果整体可达率用粗体或放在文本框里突出显示。多用表格对比不同方案或参数下的结果。多用图表网络流量图、可达率分布图、灵敏度分析折线图直观展示。图表务必有编号和标题并在正文中引用如“如图1所示”。7. 模型评价与推广要实事求是优点模型清晰将复杂交通问题转化为可求解的线性规划效率高能快速得到全局最优解易于进行灵敏度分析为规划提供定量支持。缺点假设出行者服从系统最优与实际个体选择行为有偏差未考虑动态拥堵除非你考虑了路径流模型中K值选择可能影响最优性。推广模型可扩展用于评估交通基础设施扩建方案修改容量重新计算可结合土地利用数据发生吸引量进行协同优化可尝试引入更复杂的用户均衡模型进行对比。8. 代码附录要精简可读附录里不要贴全部代码只放核心的模型构建和求解部分几十行即可。确保代码有必要的注释。原始数据读取、预处理等步骤可以简述。最后一个实战心得这类优化题结果往往是一个精确的最优解。如果你的求解器报告了“Optimal”那么你的目标函数值就是理论最大值。不同队伍的结果如果差异很大那很可能是在问题理解、OD需求生成、模型假设上出了根本性分歧。因此在论文中花足够篇幅论证你生成OD需求矩阵的方法、以及模型假设的合理性比单纯追求复杂的算法更重要。很多时候一个简单但假设合理的模型配以严谨的分析比一个复杂但假设牵强的模型更能获得好评。