1. 从赛题到方案一次完整的数学建模实战复盘又到了一年一度的MathorCup看着今年A题《新能源城市配送优化》的题目是不是感觉既熟悉又头疼熟悉的是这又是一个典型的运筹优化问题核心离不开车辆路径规划、资源调度和成本控制头疼的是题目里那些“动态需求”、“充电策略”、“时间窗”的约束还有“新能源”这个背景带来的额外复杂度怎么把它们揉成一个逻辑自洽、可求解的模型再变成能跑出结果的代码每一步都够喝一壶的。我指导过不少队伍也自己上手做过很多次发现大家最大的瓶颈往往不是某个具体的算法而是从拿到题目到交出论文这个完整链条的断裂。很多人模型建得天花乱坠但代码实现不了或者代码跑出来了但论文里讲不清楚逻辑。今天我就以2024年MathorCup A题虽然具体题目细节未公开但结合“新能源城市配送优化”这一高度相关的热词我们可以构建一个极具代表性的分析框架为引子抛开那些华而不实的理论从头到尾拆解一遍数学建模的完整实战过程。我会重点分享我们是怎么想的、为什么这么选、以及实现过程中那些教科书里不会写的“坑”。目标很简单让你看完之后不仅能复现出一个完整的项目更能掌握一套应对这类优化问题的通用思考框架和工程化方法。2. 破题与抽象把现实问题翻译成数学语言拿到一个像“新能源城市配送优化”这样的题目第一步绝对不是打开MATLAB或者Python就开始写代码。那等于蒙着眼睛跑步大概率会撞墙。我们首先要做的是当好一个“翻译官”把充满现实细节的题目描述精准地翻译成严谨的数学语言。2.1 核心要素提取与定义题目通常会给出一个故事背景比如“某物流公司拥有若干辆新能源货车需要服务分布在城市的多个客户点客户有确定的需求量和服务时间窗车辆从配送中心出发电量有限途中可能需要充电...”。我们的任务就是从这段话里把所有的“零件”都拆解出来并给它们起好数学名字。实体定义配送中心 (Depot)通常记为节点0是所有车辆的起点和终点。客户点 (Customers)记为节点集合C {1, 2, ..., n}。每个客户i都有一系列属性这是后续建模的基石。车辆 (Vehicles)记为集合K {1, 2, ..., m}。这里的关键是“新能源”属性意味着每辆车k有一个初始电量Battery_k一个最大容量Q_k载重以及一个耗电率通常与行驶距离和载重相关。参数与变量梳理客户参数对于每个客户i我们需要明确其需求量d_i重量或体积服务时间s_i卸货耗时以及最重要的——时间窗[e_i, l_i]。这意味着车辆到达客户i的时间必须在e_i之后且在l_i之前开始服务。这是硬约束违反则方案不可行。网络参数任意两点i和j之间的距离d_ij或行驶时间t_ij。这里要注意城市配送中时间往往比单纯的欧氏距离更重要可能需要考虑路网、拥堵等因素题目数据有时会直接给出时间矩阵。新能源特性参数这是区别于传统车辆路径问题 (VRP) 的关键。包括车辆百公里耗电量或单位距离耗电函数。电池容量。充电站信息如果有的话位置、充电功率快充/慢充、充电成本。充电策略是充满电再走还是可以充到任意电量充电时间如何计算通常是充电量除以充电功率。决策变量定义这是模型的“心脏”它描述了我们的方案到底是什么。最核心的是一组二进制变量x_{ijk}如果车辆k从节点i行驶到节点j则为1否则为0。为了处理时间窗和电量我们还需要引入一系列辅助变量如车辆k到达节点i的时间A_{ik}离开节点i的时间D_{ik}以及在节点i服务后的剩余电量E_{ik}。为什么这么定义因为x_{ijk}这种流变量的定义方式是描述路径问题最经典和强大的工具它能自然地与图论、网络流理论结合方便我们写出流平衡约束每个客户点只能被访问一次车辆从仓库出发最后返回仓库。而时间A_{ik}和电量E_{ik}作为状态变量是串联起整个顺序决策过程的关键它们的前后依赖关系构成了模型的核心动态。2.2 目标函数确立我们到底要优化什么题目问“优化”优化哪个指标成本最低时间最短车辆最少还是综合考量MathorCup的题目通常会有明确导向也可能需要你自行定义一个合理的目标。对于城市配送常见的目标有总成本最小化这是最务实的。成本可能包括固定成本使用的车辆数 * 每车固定成本、运输成本与总行驶距离成正比、时间成本司机工时或早到/晚到的惩罚、充电成本。Minimize: α * (车辆数) β * (总行驶距离) γ * (总行驶时间) δ * (总充电成本) ζ * (时间窗违反惩罚)这里的系数 α, β, γ, δ, ζ 可能需要根据题目赋予权重或者通过层次分析法等确定。总行驶距离/时间最小化在车辆数固定的情况下这是一个很直接的目标。使用的车辆数最小化这有助于降低固定资产和司机成本。在我们的模拟分析中我们假设一个以总成本最小化为核心的复合目标因为它最贴近商业实际。我们需要在模型中为每一种成本找到对应的数学表达式。例如时间窗违反惩罚可以设计为软约束如果早于e_i到达产生等待成本如果晚于l_i到达产生延迟惩罚惩罚函数可以是线性的也可以是阶梯式的。2.3 约束条件形式化给解决方案戴上“紧箍咒”约束是把我们的数学方案拉回现实的缰绳。必须一条条罗列清楚流平衡约束确保每个客户点被且仅被一辆车访问一次车辆从仓库出发并返回仓库。∑_k ∑_j x_{ijk} 1 对于所有客户点i。每个客户只被服务一次∑_j x_{0jk} 1 对于所有车辆k。每辆车从仓库出发∑_i x_{ihk} - ∑_j x_{hjk} 0 对于所有节点h和车辆k。路径连续性即到达某点后必须离开∑_i x_{i0k} 1 对于所有车辆k。每辆车返回仓库载重量约束车辆在任何路段上的累计载重不能超过其最大容量。这需要引入新的辅助变量Load_{ik}表示车辆k离开节点i时的载重。约束为Load_{jk} Load_{ik} d_j - M*(1 - x_{ijk})其中M是一个很大的数。这确保了如果车辆k从i走到j那么在j点的载重必须等于i点载重加上j点的需求量。时间窗约束这是难点之一。首先有时间传递关系A_{jk} D_{ik} t_{ij} - M*(1 - x_{ijk})。即如果从i到j那么到达j的时间至少是离开i的时间加上路程时间。服务时间D_{ik} A_{ik} s_i假设服务立即开始。硬时间窗要求e_i A_{ik} l_i。如果是软时间窗则将其放入目标函数作为惩罚项。电量约束核心难点这是新能源VRP (E-VRP) 的灵魂。电量消耗模型最简单的假设是耗电量与距离成正比e_ij c * d_ij。更复杂的模型可能考虑载重影响e_ij (c0 c1 * Load) * d_ij。电量传递关系E_{jk} E_{ik} - e_ij M*(1 - x_{ijk})。即到达j点的电量小于等于离开i点的电量减去路途消耗。电量边界约束0 E_{ik} Battery_max。电量不能为负也不能超过电池容量。充电决策整合如果模型包含充电站记为节点集合F复杂度激增。我们需要决定是否去充电站、去哪个、充多少。这需要引入新的二进制变量y_{ifk}表示是否在节点i可能是客户点或仓库后去充电站f以及充电量变量Ch_{ik}。电量约束将变为分段函数在普通节点间消耗在充电站节点补充。实操心得在纸上或白板上画出所有这些约束的依赖图理解变量之间如何相互影响是构建正确模型的关键。很多同学模型报错“不可行”根源就是约束之间存在隐藏的矛盾比如时间窗太紧而车辆速度太慢导致无论如何都无法满足。这时可能需要回头检查问题假设或者引入软约束。3. 模型求解策略精确解与启发式的权衡当我们把目标函数和所有约束都用数学公式写出来后一个完整的混合整数线性规划 (MILP) 模型就诞生了。你可以用CPLEX,Gurobi,OR-Tools等求解器直接去求解。对于小规模问题比如客户点50这可能行得通。但对于稍具规模的实际问题客户点100MILP模型可能会因为计算复杂度过高而无法在比赛时间内得到最优解甚至得不到可行解。这时就必须诉诸启发式算法。我们的策略通常是“分而治之逐步优化”。3.1 初始解构造先有一个“能用”的方案“从零到一”比“从一到优”更重要。一个快速的初始解构造算法能为后续优化提供起点。常用方法最近邻法从仓库出发总是选择距离当前点最近且满足所有约束时间窗、电量、载重的未服务客户点加入路径。如果无法加入则派出一辆新车。这种方法速度快但解的质量一般。节约算法这是解决VRP的经典启发式。其核心思想是比较将两个客户点分别用两辆车服务与合并到同一辆车服务所带来的距离“节约值”优先合并节约值大的点对。我们需要在合并时实时检查约束是否满足。针对新能源的适配在构造初始解时就必须考虑电量。一个简单的策略是在最近邻选择时不仅看距离还看前往该客户后剩余电量是否足够返回最近的可能充电点或仓库。这相当于增加了一个“电量安全边际”的检查。代码片段示意最近邻法思路def construct_initial_solution(customers, vehicle_capacity, battery_capacity, distance_matrix): routes [] unserved customers.copy() while unserved: current_route [0] # 从仓库开始 current_load 0 current_battery battery_capacity current_time 0 while True: # 找出所有未服务且满足约束的候选客户 candidates [] for cust in unserved: if (current_load cust.demand vehicle_capacity and current_battery distance_matrix[current_route[-1]][cust.id] * energy_rate and current_time travel_time cust.time_window_end): # 简化检查 # 计算一个综合得分如距离倒数 紧急程度 score 1.0 / distance_matrix[current_route[-1]][cust.id] (1.0 / (cust.time_window_end - current_time)) candidates.append((score, cust)) if not candidates: break # 当前车无法再添加客户结束路径 # 选择得分最高的客户 _, next_cust max(candidates, keylambda x: x[0]) current_route.append(next_cust.id) current_load next_cust.demand current_battery - distance_matrix[current_route[-2]][next_cust.id] * energy_rate current_time travel_time next_cust.service_time unserved.remove(next_cust) # 简单电量检查如果电量不足以返回仓库则提前结束路径实际中应考虑充电 if current_battery distance_matrix[current_route[-1]][0] * energy_rate: break current_route.append(0) # 返回仓库 routes.append(current_route) return routes注意这是一个极度简化的示意忽略了时间窗的精确计算、充电决策等复杂情况但它展示了如何将约束检查融入解构造过程。3.2 局部搜索与元启发式优化让方案变得“更好”有了初始解我们就可以开始“折腾”它寻找更好的方案。核心是定义一系列邻域动作然后搜索这些动作。常用邻域动作Relocate将一个客户点从一条路径移动到另一条路径的某个位置。Swap交换两条路径中的两个客户点。2-opt在一条路径内部反转一段子路径的顺序。这对优化单条路径的行驶距离非常有效。Cross-exchange交换两条路径中的两段子路径。优化框架局部搜索遍历当前解的所有可能邻域动作接受第一个能使目标函数改进的动作然后在新解上重复此过程直到找不到改进动作为止。容易陷入局部最优。模拟退火允许以一定的概率接受恶化解从而有机会跳出局部最优。核心参数是初始温度、降温速率和终止温度。变邻域搜索系统性地切换不同的邻域结构进行搜索当在一个邻域中找不到更好解时就切换到另一个更大的邻域。遗传算法将路径编码为染色体通过选择、交叉、变异等操作模拟进化过程。编码和交叉算子的设计需要技巧要保证生成的后代仍是可行解。为什么选择VNS或模拟退火对于数学建模竞赛变邻域搜索是一个非常好的选择。它结构清晰易于实现和调试而且通常能取得不错的效果。模拟退火需要对温度参数有较好的把握。遗传算法则更复杂调整参数多在有限时间内不一定能调出最佳性能。3.3 针对新能源特性的特殊优化算子除了通用的路径优化算子我们必须设计专门针对电量约束的算子充电站插入/删除/移动在路径中智能地插入充电站访问。策略可以是当检测到某段行程后电量可能不足时在沿途寻找最近的充电站插入或者评估移除一个充电站是否仍能满足全程电量要求。电量可行的路径片段交换在进行Swap或Cross-exchange时交换后的新路径片段必须重新进行电量模拟确保从片段起点到终点的电量消耗是可行的。如果不可行则需要尝试在片段内部或附近插入充电站。基于电量的路径分割与合并对于一条过长的路径可以基于电量约束将其在合适的位置如充电站附近分割成两条反之也可以尝试合并两条电量允许的短路径。实操心得在实现这些优化算子时可行性检查函数的效率至关重要。你需要一个快速函数给定一条路径包含客户点和可能的充电站序列能迅速判断其是否满足载重、时间窗和电量约束。这个函数会被调用成千上万次它的效率直接决定了整个优化过程的快慢。建议将路径的累积载重、累积时间、累积耗电量等状态预先计算并缓存避免每次检查都从头计算。4. 代码实现与工程化要点模型和算法设计得再好最终都要落地为代码。这里我用Python为例分享几个关键的实现模块和踩坑点。4.1 数据结构设计一切效率的基础不要用简单的列表套列表来管理一切。设计清晰的数据结构能让你的代码更健壮、更高效。class Customer: def __init__(self, id, x, y, demand, service_time, time_window_start, time_window_end): self.id id self.x x self.y y self.demand demand self.service_time service_time self.tw_start time_window_start self.tw_end time_window_end class Vehicle: def __init__(self, id, capacity, battery_capacity, energy_rate): self.id id self.capacity capacity self.battery_capacity battery_capacity self.energy_rate energy_rate # 单位距离能耗 class ProblemInstance: def __init__(self): self.customers [] # 索引0通常是仓库 self.vehicles [] self.distance_matrix None self.time_matrix None self.charging_stations [] def calculate_matrices(self): # 预计算所有点之间的距离和时间矩阵 # 这是一个O(n^2)的操作但只需做一次可以节省大量后续计算 pass4.2 核心算法模块实现初始解生成器实现前面提到的节约算法或最近邻法并确保返回的是一个包含多条路径的可行解。邻域动作生成器实现relocate,swap,2-opt等操作。关键是要生成增量变化而不是每次都对整个解进行深拷贝和全量评估。def generate_relocate_moves(solution): moves [] for route_from_idx, route_from in enumerate(solution.routes): for i, node_i in enumerate(route_from[1:-1]): # 跳过首尾的仓库 for route_to_idx, route_to in enumerate(solution.routes): if route_from_idx route_to_idx: continue for j in range(1, len(route_to)): # 插入到路径中的位置 # 创建一个“移动”对象记录从哪条路、哪个位置、移到哪条路、哪个位置 move RelocateMove(route_from_idx, i, route_to_idx, j) # 快速评估这个移动的成本变化 delta_cost delta_cost evaluate_relocate_delta(solution, move) moves.append((delta_cost, move)) return moves可行性检查与成本评估这是最核心的模块。对于一条给定的路径序列需要模拟车辆行驶过程计算到达每个点的时间、剩余电量并检查约束。def evaluate_route(route, problem, vehicle): current_time 0 current_load 0 current_battery vehicle.battery_capacity total_cost 0 feasible True prev_node problem.depot for node in route[1:]: # route[0]是仓库 # 计算距离和时间 dist problem.distance_matrix[prev_node.id][node.id] travel_time problem.time_matrix[prev_node.id][node.id] # 检查电量 energy_consumed dist * vehicle.energy_rate if current_battery energy_consumed: feasible False break current_battery - energy_consumed # 检查时间窗假设为硬约束 arrival_time current_time travel_time if arrival_time node.tw_start: current_time node.tw_start # 等待 elif arrival_time node.tw_end: feasible False break else: current_time arrival_time # 服务 current_time node.service_time current_load node.demand if current_load vehicle.capacity: feasible False break # 累加成本例如距离成本 total_cost dist * cost_per_km prev_node node # 最后返回仓库 dist_back problem.distance_matrix[prev_node.id][problem.depot.id] if current_battery dist_back * vehicle.energy_rate: feasible False total_cost dist_back * cost_per_km return feasible, total_cost, current_time注意这个函数在优化循环中会被调用无数次。任何微小的优化都能带来显著的加速比如使用numpy数组进行矩阵运算缓存部分计算结果。4.3 调试与可视化相信你的眼睛在复杂的优化算法中Bug难以避免。除了看日志可视化是终极武器。路径可视化使用matplotlib绘制所有车辆的行驶路径用不同颜色区分。一眼就能看出路径是否交叉、是否合理、是否有车辆空跑。import matplotlib.pyplot as plt def plot_solution(solution, problem): plt.figure(figsize(10, 8)) colors plt.cm.tab10(np.linspace(0, 1, len(solution.routes))) for route, color in zip(solution.routes, colors): x_coords [problem.customers[node_id].x for node_id in route] y_coords [problem.customers[node_id].y for node_id in route] plt.plot(x_coords, y_coords, o-, colorcolor, linewidth2, markersize8) # 标注路径顺序 for i, node_id in enumerate(route): plt.annotate(str(node_id), (x_coords[i], y_coords[i]), fontsize9) # 标出仓库 depot problem.depot plt.plot(depot.x, depot.y, ks, markersize12, labelDepot) plt.legend() plt.grid(True, alpha0.3) plt.title(Vehicle Routes) plt.show()收敛曲线绘制每次迭代后最优解的成本变化曲线。这能帮你判断算法是否在有效搜索、是否已收敛、模拟退火的温度设置是否合适。关键变量跟踪在日志中输出每次重要邻域动作后的成本变化、可行性状态帮助你定位是哪个算子或哪个检查函数出了问题。踩坑实录我曾遇到一个Bug2-opt算子优化后路径的总距离确实缩短了但总成本却增加了。排查了很久才发现我的成本计算函数只考虑了距离成本但2-opt改变了客户访问顺序导致某些客户的时间窗被违反产生了高额惩罚而我在评估动作时只快速计算了距离变化没有重新计算时间窗惩罚。教训是任何邻域动作的增量评估必须覆盖目标函数的所有组成部分。5. 从结果到论文如何讲好你的建模故事代码跑出了结果只算成功了一半。另一半是把你的工作清晰、有说服力地呈现在论文里。论文不是代码的流水账而是一个有逻辑的故事。5.1 模型阐述清晰性与严谨性并重符号说明表这是论文的门面务必清晰、完整。按照实体、集合、参数、决策变量的顺序列出并给出单位如距离km时间minute。模型公式将你在“破题”阶段写出的目标函数和约束用专业的数学公式排版。建议使用LaTeX环境如Overleaf撰写论文这是数学建模的标配。公式要编号并在文中引用。模型解释不要假设评委能一眼看懂你的公式。在公式下方用一两句话解释这个约束的物理或商业含义。例如在写出电量约束后可以说明“该约束确保了车辆在任意路段的电量消耗不会导致其剩余电量为负模拟了电池的物理限制”。5.2 算法描述突出你的创新与适配流程图是必备的用清晰的流程图展示你算法的整体框架比如“初始解构造 - 变邻域搜索主循环包含几个邻域算子 - 接受准则 - 终止条件”。这比大段文字描述直观得多。伪代码对于核心算法如你的变邻域搜索主循环、关键的邻域算子给出伪代码。伪代码应介于编程语言和自然语言之间突出逻辑而非语法细节。强调针对性的设计专门用一小节说明你是如何适配“新能源”和“时间窗”特性的。例如“在初始解构造中我们加入了电量安全边际检查”“在邻域动作的可行性验证中我们设计了一个快速的电量模拟函数其时间复杂度为O(L)其中L为路径长度”。5.3 实验设计与结果分析用数据说话基准数据集如果题目没有给数据你需要自己生成或寻找公开的基准数据集如Solomon的VRPTW数据集。说明你生成数据的规则客户点分布、时间窗宽度、需求量范围等以保证实验的可复现性。对比实验这是体现你算法价值的关键。至少对比不同初始解策略的效果对比最近邻法、节约算法等对最终结果的影响。不同优化算法的效果对比纯局部搜索、模拟退火、你的VNS算法在求解质量和时间上的差异。关键参数敏感性分析例如分析电池容量大小对总成本、车辆使用数的影响或者分析时间窗严格程度对路径规划可行性的影响。这能体现你对问题深度的理解。结果可视化表格清晰列出不同算法/参数下的目标函数值、计算时间、车辆使用数等关键指标。图表除了前面提到的路径图、收敛曲线还可以绘制柱状图对比不同方案的成本构成固定成本、运输成本、惩罚成本各占多少绘制折线图展示参数敏感性。5.4 模型检验与鲁棒性讨论这是很多论文的薄弱环节但却是加分项。你需要证明你的模型和方案是可靠的。极端情况测试设计一些极端场景比如某个客户的需求量突然极大或者某个路段临时封闭距离设为无穷大看你的算法能否给出合理的应对方案如启用备用车辆、路径重规划。数据扰动分析对客户需求量、服务时间等参数加入微小随机扰动例如±10%重新运行算法观察结果的变化是否在可接受范围内。这体现了模型对数据误差的鲁棒性。灵敏度分析报告系统地汇报某个关键参数如单位运输成本、时间窗惩罚系数在一定范围内变动时最优解如何变化。这能为决策者提供有价值的参考。个人体会写论文时一定要站在评委的角度思考。评委时间有限他们希望快速抓住你的核心工作。因此摘要要精炼突出问题、方法、主要结果和结论图表要自明不看正文也能懂个七八分模型和算法部分要逻辑连贯像讲故事一样层层递进。最后检查全文的格式、编号、参考文献引用这些细节决定了论文的专业第一印象。数学建模竞赛既是智力的比拼也是工程实现和学术表达的全面考验。从理解问题到编码实现再到撰写报告每一个环节的扎实程度最终都会体现在你的论文里。
