學(xué)建模競(jìng)賽實(shí)戰(zhàn)：從車(chē)輛路徑問(wèn)題到算法實(shí)現(xiàn)與論文寫(xiě)作)
1. 項(xiàng)目概述從一道賽題到一套完整解決方案去年帶隊(duì)參加亞太數(shù)學(xué)杯APMCM的經(jīng)歷讓我對(duì)數(shù)學(xué)建模競(jìng)賽的備賽與實(shí)戰(zhàn)有了更深的體會(huì)。特別是2022年的B題它不像一些純理論推導(dǎo)的題目而是緊密貼合了現(xiàn)實(shí)中的資源調(diào)度與路徑優(yōu)化問(wèn)題本質(zhì)上是一個(gè)帶有復(fù)雜約束的組合優(yōu)化難題。這類(lèi)題目在國(guó)賽、美賽乃至企業(yè)實(shí)際項(xiàng)目中都屢見(jiàn)不鮮比如物流中心的車(chē)輛排班、生產(chǎn)線的工序調(diào)度或者我們熟悉的網(wǎng)約車(chē)平臺(tái)訂單與司機(jī)的匹配。題目給出的可能是一個(gè)簡(jiǎn)化場(chǎng)景但背后考察的核心能力是相通的如何將模糊的現(xiàn)實(shí)問(wèn)題轉(zhuǎn)化為清晰的數(shù)學(xué)模型如何為這個(gè)模型匹配合適的算法以及如何通過(guò)編程將算法實(shí)現(xiàn)并得到可信的結(jié)果。很多同學(xué)拿到題目后最容易卡住的兩個(gè)點(diǎn)就是“思路”和“程序”。思路不清就像在迷宮里亂轉(zhuǎn)建出的模型要么過(guò)于簡(jiǎn)單漏掉關(guān)鍵約束要么過(guò)于復(fù)雜根本無(wú)法求解。程序不強(qiáng)再好的思路也只能停留在紙上算不出結(jié)果或者算得太慢錯(cuò)過(guò)提交時(shí)間。這篇內(nèi)容我就以2022年亞太杯B題為引子不局限于這一道題的具體數(shù)據(jù)而是拆解這類(lèi)“資源調(diào)度與路徑優(yōu)化”問(wèn)題的通用破題思路、核心算法選型以及從建模到編程落地的完整流程。無(wú)論你是正在備戰(zhàn)亞太杯、國(guó)賽還是對(duì)數(shù)學(xué)建模感興趣希望這些從實(shí)戰(zhàn)中踩坑總結(jié)的經(jīng)驗(yàn)?zāi)軒湍闵僮邚澛贰?. 核心思路拆解如何將現(xiàn)實(shí)問(wèn)題“翻譯”成數(shù)學(xué)模型面對(duì)一道陌生的賽題第一步不是急著打開(kāi)MATLAB或Python而是拿出紙筆進(jìn)行深度的問(wèn)題分析。2022年B題的典型特征是多點(diǎn)、多資源、有時(shí)序要求。我們需要建立一套系統(tǒng)性的分析框架。2.1 問(wèn)題要素抽象與定義首先把題目中所有“名詞”找出來(lái)并明確它們的數(shù)學(xué)身份。這通常包括實(shí)體Entities誰(shuí)在移動(dòng)誰(shuí)被服務(wù)例如題目中的“服務(wù)點(diǎn)”、“需求點(diǎn)”、“車(chē)輛”、“工作人員”。在數(shù)學(xué)上它們通常被抽象為“點(diǎn)”Node或“智能體”Agent。屬性Attributes每個(gè)實(shí)體有什么特征例如點(diǎn)的位置坐標(biāo)、需求量、服務(wù)時(shí)間窗口車(chē)輛的容量、速度、起始位置工作人員的工作時(shí)長(zhǎng)、技能等級(jí)。這些是模型的參數(shù)。關(guān)系Relationships實(shí)體之間如何交互例如從點(diǎn)A到點(diǎn)B的距離或耗時(shí)通常構(gòu)成一個(gè)成本矩陣車(chē)輛訪問(wèn)點(diǎn)必須滿足其時(shí)間窗點(diǎn)的需求必須被滿足且不能超過(guò)車(chē)輛容量。這些是模型的約束條件。目標(biāo)Objective我們要優(yōu)化什么題目可能要求“總路徑最短”、“總耗時(shí)最少”、“總成本最低”、“滿足需求的點(diǎn)最多”、“車(chē)輛使用數(shù)最少”等。有時(shí)是單目標(biāo)有時(shí)是多目標(biāo)需要權(quán)衡。以2022年B題為例經(jīng)過(guò)抽象我們很可能得到一個(gè)“帶時(shí)間窗和容量約束的車(chē)輛路徑問(wèn)題Capacitated Vehicle Routing Problem with Time Windows, CVRPTW”的變體。明確這一點(diǎn)至關(guān)重要因?yàn)樗苯又赶蛄艘延械慕?jīng)典模型和算法庫(kù)我們不需要從零發(fā)明輪子。2.2 模型假設(shè)的藝術(shù)在精確與可行之間權(quán)衡數(shù)學(xué)建模不是物理仿真不可能100%還原現(xiàn)實(shí)。做出合理且必要的假設(shè)是簡(jiǎn)化問(wèn)題、使模型可解的關(guān)鍵。這里有幾個(gè)原則必要性原則這個(gè)假設(shè)是否為了抓住問(wèn)題核心而不得不做例如假設(shè)車(chē)輛勻速行駛是為了簡(jiǎn)化路徑成本計(jì)算。簡(jiǎn)化性原則這個(gè)假設(shè)能否顯著降低模型復(fù)雜度例如假設(shè)每個(gè)點(diǎn)的需求必須由一輛車(chē)一次完成即需求不可拆分這避免了復(fù)雜的貨物裝載組合優(yōu)化?？赊q護(hù)原則如果評(píng)委質(zhì)疑你的假設(shè)是否有合理的現(xiàn)實(shí)依據(jù)或數(shù)據(jù)支持例如假設(shè)兩點(diǎn)間距離為直線距離歐氏距離你可以說(shuō)明在城區(qū)尺度或數(shù)據(jù)精度下這是一個(gè)可接受的近似如果涉及交通則可能需要改用道路網(wǎng)絡(luò)距離。一個(gè)常見(jiàn)的誤區(qū)是假設(shè)過(guò)于理想化導(dǎo)致模型脫離實(shí)際。例如忽略車(chē)輛的裝卸貨時(shí)間或者在多車(chē)型問(wèn)題中假設(shè)所有車(chē)性能完全相同。在2022年B題中可能需要仔細(xì)考慮“服務(wù)時(shí)間”是否包含在時(shí)間窗內(nèi)以及車(chē)輛在不同路段的速度是否恒定。在論文中必須用單獨(dú)一小節(jié)清晰列出所有主要假設(shè)并簡(jiǎn)要說(shuō)明理由。2.3 決策變量與目標(biāo)函數(shù)的形式化這是將思路轉(zhuǎn)化為數(shù)學(xué)語(yǔ)言的核心步驟。決策變量是模型輸出的結(jié)果是我們要求解的東西。對(duì)于路徑問(wèn)題最經(jīng)典的決策變量是二進(jìn)制變量 ( x_{ijk} )如果車(chē)輛k從點(diǎn)i行駛到點(diǎn)j則為1否則為0。這里i和j包括所有需求點(diǎn)和車(chē)場(chǎng)起點(diǎn)/終點(diǎn)。目標(biāo)函數(shù)則是這些決策變量的函數(shù)。最常見(jiàn)的是最小化總行駛距離( \min \sum_{k} \sum_{i} \sum_{j} cost_{ij} \cdot x_{ijk} )。如果題目要求最小化車(chē)輛數(shù)可以引入一個(gè)關(guān)于車(chē)輛是否被使用的二進(jìn)制變量并將其納入目標(biāo)通常給予一個(gè)很大的權(quán)重。一個(gè)關(guān)鍵技巧當(dāng)目標(biāo)函數(shù)包含多個(gè)方面如既想省錢(qián)又想快時(shí)可以采用加權(quán)求和法將其轉(zhuǎn)化為單目標(biāo)( \min w_1 * TotalDistance w_2 * TotalTime )。權(quán)重的選擇需要謹(jǐn)慎可以通過(guò)敏感性分析來(lái)討論不同權(quán)重對(duì)結(jié)果的影響。另一種更高級(jí)的方法是帕累托優(yōu)化求出一組“非劣解”即在不使其他目標(biāo)變差的情況下無(wú)法再改進(jìn)任何一個(gè)目標(biāo)但這對(duì)算法和編程要求更高。3. 算法選型與策略沒(méi)有銀彈只有合適的選擇模型建立后選擇什么算法求解這取決于模型規(guī)模、復(fù)雜度和你對(duì)結(jié)果的要求最優(yōu)解 vs. 滿意解。3.1 精確算法小規(guī)模問(wèn)題的“標(biāo)準(zhǔn)答案”對(duì)于節(jié)點(diǎn)數(shù)較少例如少于20個(gè)需求點(diǎn)的問(wèn)題可以嘗試使用精確算法求取全局最優(yōu)解。線性/整數(shù)規(guī)劃求解器如果你將問(wèn)題成功構(gòu)建為混合整數(shù)線性規(guī)劃MILP模型那么可以使用像Gurobi、CPLEX這樣的商業(yè)求解器或者開(kāi)源的SCIP、CBC。它們利用分支定界、割平面等算法能保證找到最優(yōu)解。在Python中你可以用PuLP、ortools等庫(kù)來(lái)調(diào)用它們。適用場(chǎng)景與局限精確求解器是驗(yàn)證模型正確性和獲取小規(guī)模問(wèn)題基準(zhǔn)答案的利器。但當(dāng)問(wèn)題規(guī)模擴(kuò)大求解時(shí)間會(huì)呈指數(shù)級(jí)增長(zhǎng)可能幾個(gè)小時(shí)甚至幾天都算不完。因此在競(jìng)賽中除非問(wèn)題特別簡(jiǎn)單否則精確算法通常只作為對(duì)比基準(zhǔn)而非主力求解方法。3.2 啟發(fā)式與元啟發(fā)式算法競(jìng)賽的主力軍對(duì)于競(jìng)賽中常見(jiàn)的中等規(guī)模問(wèn)題啟發(fā)式算法是更實(shí)際的選擇。它們不能在理論上保證最優(yōu)但能在合理時(shí)間內(nèi)給出高質(zhì)量的解。構(gòu)造型啟發(fā)式從零開(kāi)始構(gòu)建一個(gè)可行解。最近鄰法從車(chē)場(chǎng)出發(fā)總是前往距離當(dāng)前點(diǎn)最近且滿足約束的未訪問(wèn)點(diǎn)。簡(jiǎn)單快速但結(jié)果往往一般。節(jié)約算法是解決VRP類(lèi)問(wèn)題的經(jīng)典方法。它先假設(shè)每個(gè)點(diǎn)都用一輛車(chē)單獨(dú)服務(wù)然后計(jì)算合并兩條路線所能“節(jié)約”的距離優(yōu)先合并節(jié)約值最大的路線直到不能合并為止。這種方法能快速得到一個(gè)不錯(cuò)的初始解。元啟發(fā)式算法對(duì)現(xiàn)有解進(jìn)行迭代改進(jìn)的通用框架。這是數(shù)學(xué)建模競(jìng)賽的“明星算法族”。模擬退火靈感來(lái)自固體退火過(guò)程。它允許以一定概率接受比當(dāng)前解差的“壞解”從而有機(jī)會(huì)跳出局部最優(yōu)陷阱。關(guān)鍵參數(shù)是初始溫度、降溫速率和終止溫度。實(shí)操心得降溫速率不宜過(guò)快如0.95比0.99更容易找到好解并且可以增加在同一個(gè)溫度下的多次迭代馬爾可夫鏈長(zhǎng)度。遺傳算法模仿生物進(jìn)化。將解編碼為“染色體”如路徑的順序列表通過(guò)選擇、交叉、變異產(chǎn)生新一代解。關(guān)鍵點(diǎn)路徑問(wèn)題的編碼和交叉算子設(shè)計(jì)需要特別小心要保證生成的新解仍然是有效路徑滿足車(chē)輛容量、時(shí)間窗等。常用的交叉算子有順序交叉、部分映射交叉。蟻群算法模擬螞蟻覓食的信息素機(jī)制。螞蟻根據(jù)路徑上的信息素濃度和啟發(fā)式信息如距離倒數(shù)選擇路徑信息素會(huì)隨著優(yōu)質(zhì)解的發(fā)現(xiàn)而增強(qiáng)。它特別適合求解路徑問(wèn)題。參數(shù)調(diào)優(yōu)經(jīng)驗(yàn)信息素?fù)]發(fā)系數(shù)很重要太高會(huì)導(dǎo)致過(guò)早收斂于局部最優(yōu)太低則搜索隨機(jī)性太強(qiáng)。通常設(shè)置在0.1到0.5之間。算法選擇建議對(duì)于2022年B題這類(lèi)動(dòng)態(tài)性不強(qiáng)、約束明確的靜態(tài)VRPTW問(wèn)題模擬退火和遺傳算法是穩(wěn)健且易于實(shí)現(xiàn)的選擇?？梢韵仁褂霉?jié)約算法生成一個(gè)初始解然后用模擬退火進(jìn)行優(yōu)化。蟻群算法效果通常很好但參數(shù)更多調(diào)優(yōu)更耗時(shí)。3.3 現(xiàn)代求解器與開(kāi)源框架站在巨人的肩膀上你不必所有算法都從頭實(shí)現(xiàn)。利用好開(kāi)源工具能極大提升效率。OR-Tools谷歌開(kāi)發(fā)的開(kāi)源運(yùn)籌學(xué)工具包是數(shù)學(xué)建模競(jìng)賽的“神器”。它內(nèi)置了針對(duì)VRP、VRPTW等問(wèn)題的專(zhuān)用求解器使用的是基于局部搜索的先進(jìn)啟發(fā)式算法。你只需要定義好距離矩陣、車(chē)輛數(shù)量、容量、時(shí)間窗等參數(shù)它就能在秒級(jí)時(shí)間內(nèi)返回一個(gè)高質(zhì)量的解。對(duì)于快速驗(yàn)證模型和獲取基準(zhǔn)解非常有用。VROOM一個(gè)專(zhuān)攻車(chē)輛路徑優(yōu)化的開(kāi)源引擎性能非常強(qiáng)勁。使用策略在競(jìng)賽中可以先用OR-Tools快速求出一個(gè)解作為你自定義算法性能的對(duì)比基準(zhǔn)。同時(shí)你也可以研究這些工具得出的解的結(jié)構(gòu)啟發(fā)你自己的算法設(shè)計(jì)。4. 編程實(shí)現(xiàn)與代碼架構(gòu)思路和算法確定后就要用代碼來(lái)實(shí)現(xiàn)。清晰的代碼結(jié)構(gòu)不僅能讓你調(diào)試更輕松也能在論文中更好地展示你的工作。4.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)一切的基礎(chǔ)良好的數(shù)據(jù)結(jié)構(gòu)是高效算法的前提。對(duì)于VRP問(wèn)題我建議定義以下核心類(lèi)class Point: def __init__(self, id, x, y, demand, ready_time, due_date, service_time): self.id id # 點(diǎn)ID0通常代表車(chē)場(chǎng) self.x x self.y y self.demand demand # 需求量 self.ready_time ready_time # 最早開(kāi)始服務(wù)時(shí)間 self.due_date due_date # 最晚開(kāi)始服務(wù)時(shí)間 self.service_time service_time # 服務(wù)耗時(shí) class Vehicle: def __init__(self, id, capacity, start_point, end_point): self.id id self.capacity capacity self.start_point start_point # 起始點(diǎn)索引 self.end_point end_point # 返回點(diǎn)索引通常與起始點(diǎn)相同 self.route [] # 存儲(chǔ)路徑點(diǎn)ID的列表 self.load 0 # 當(dāng)前載重 self.time 0 # 當(dāng)前時(shí)間 class ProblemInstance: def __init__(self, points, vehicles, distance_matrix, time_matrix): self.points points # 所有點(diǎn)的列表 self.vehicles vehicles # 所有車(chē)輛的列表 self.distance_matrix distance_matrix # 距離矩陣 self.time_matrix time_matrix # 時(shí)間矩陣可由距離和速度算出使用類(lèi)來(lái)組織數(shù)據(jù)比單純使用列表和字典更清晰也更容易實(shí)現(xiàn)與約束檢查、成本計(jì)算相關(guān)的成員方法。4.2 核心算法模塊實(shí)現(xiàn)示例模擬退火以下是一個(gè)用于優(yōu)化VRP路徑的模擬退火算法核心框架。假設(shè)我們已經(jīng)有了一個(gè)初始解用Solution類(lèi)表示它包含了一個(gè)車(chē)輛路徑的列表。import math import random import copy def simulated_annealing(initial_solution, distance_matrix, points, max_iter10000): current_solution copy.deepcopy(initial_solution) current_cost calculate_total_cost(current_solution, distance_matrix, points) best_solution copy.deepcopy(current_solution) best_cost current_cost T 1000.0 # 初始溫度 T_min 1e-3 # 終止溫度 alpha 0.995 # 降溫系數(shù) iteration 0 while T T_min and iteration max_iter: # 1. 在當(dāng)前解附近產(chǎn)生一個(gè)鄰域解 new_solution generate_neighbor(current_solution) new_cost calculate_total_cost(new_solution, distance_matrix, points) # 2. 計(jì)算成本差 delta_cost new_cost - current_cost # 3. 接受準(zhǔn)則如果新解更好則接受如果更差以一定概率接受 if delta_cost 0 or random.random() math.exp(-delta_cost / T): current_solution new_solution current_cost new_cost # 更新歷史最優(yōu) if current_cost best_cost: best_solution copy.deepcopy(current_solution) best_cost current_cost # 4. 降溫 T * alpha iteration 1 return best_solution, best_cost def generate_neighbor(solution): 生成鄰域解常用操作有 neighbor copy.deepcopy(solution) operation random.choice([swap, relocate, 2-opt]) if operation swap: # 隨機(jī)選擇兩條路徑中的兩個(gè)點(diǎn)進(jìn)行交換 r1_idx, r2_idx random.sample(range(len(neighbor.routes)), 2) route1, route2 neighbor.routes[r1_idx], neighbor.routes[r2_idx] if len(route1) 1 and len(route2) 1: i random.randint(0, len(route1)-2) # 避開(kāi)車(chē)場(chǎng) j random.randint(0, len(route2)-2) route1[i], route2[j] route2[j], route1[i] elif operation relocate: # 將一個(gè)點(diǎn)從一條路徑移到另一條路徑 r1_idx, r2_idx random.sample(range(len(neighbor.routes)), 2) route1, route2 neighbor.routes[r1_idx], neighbor.routes[r2_idx] if len(route1) 1: i random.randint(0, len(route1)-2) point_to_move route1.pop(i) # 插入到route2的隨機(jī)位置 j random.randint(0, len(route2)-1) route2.insert(j, point_to_move) # ... 其他操作如2-opt路徑內(nèi)反轉(zhuǎn)一段 return neighbor關(guān)鍵提示generate_neighbor函數(shù)的設(shè)計(jì)至關(guān)重要它決定了算法的搜索能力。好的鄰域結(jié)構(gòu)應(yīng)該既能產(chǎn)生足夠的變化又能保證大部分新解仍是可行的滿足容量、時(shí)間窗約束。在實(shí)際編碼中需要在執(zhí)行操作后立即進(jìn)行約束檢查如果違反則丟棄該操作或進(jìn)行修復(fù)。4.3 可視化與結(jié)果分析讓論文“亮”起來(lái)結(jié)果可視化是論文的加分項(xiàng)。一張清晰的路徑圖勝過(guò)千言萬(wàn)語(yǔ)。import matplotlib.pyplot as plt def plot_solution(solution, points): plt.figure(figsize(10, 8)) colors plt.cm.tab20(np.linspace(0, 1, len(solution.routes))) # 畫(huà)出所有點(diǎn) all_x [p.x for p in points[1:]] # 排除車(chē)場(chǎng) all_y [p.y for p in points[1:]] plt.scatter(all_x, all_y, cgray, alpha0.6, labelDemand Points) # 畫(huà)車(chē)場(chǎng) depot points[0] plt.scatter(depot.x, depot.y, cred, markers, s200, labelDepot, edgecolorsblack) # 畫(huà)出每條路徑 for idx, route in enumerate(solution.routes): if not route: # 空路徑 continue route_points [points[i] for i in route] x_coords [p.x for p in route_points] y_coords [p.y for p in route_points] plt.plot(x_coords, y_coords, ccolors[idx], linewidth2, markero, labelfVehicle {idx1}) plt.xlabel(X Coordinate) plt.ylabel(Y Coordinate) plt.title(Optimized Vehicle Routes) plt.legend(bbox_to_anchor(1.05, 1), locupper left) plt.grid(True, alpha0.3) plt.tight_layout() plt.savefig(optimized_routes.png, dpi300) plt.show()除了路徑圖還應(yīng)生成關(guān)鍵指標(biāo)的表格例如車(chē)輛編號(hào)路徑順序總載重總行駛距離開(kāi)始時(shí)間結(jié)束時(shí)間時(shí)間窗違反容量違反10 - 3 - 5 - 8 - 085156.70245無(wú)無(wú)20 - 1 - 4 - 7 - 092142.30238無(wú)無(wú)........................總計(jì)-354876.5--00這樣的表格清晰地展示了每輛車(chē)的任務(wù)分配和整體方案的質(zhì)量。5. 從模型到論文寫(xiě)作要點(diǎn)與避坑指南編程求解出結(jié)果只完成了工作的一半如何將其組織成一篇邏輯清晰、表達(dá)專(zhuān)業(yè)的論文是決定最終成績(jī)的關(guān)鍵。5.1 論文結(jié)構(gòu)骨架一篇標(biāo)準(zhǔn)的數(shù)學(xué)建模論文應(yīng)包含以下部分并注意突出你的工作亮點(diǎn)摘要重中之重需獨(dú)立成頁(yè)用300-500字概括整個(gè)工作。必須包含問(wèn)題重述、你的主要思路、所用模型、核心算法、關(guān)鍵結(jié)論和數(shù)值結(jié)果如總成本降低了多少。評(píng)委可能只看摘要所以要字斟句酌。問(wèn)題重述與分析不要照抄題目。用自己的語(yǔ)言提煉問(wèn)題背景、已知條件、約束和目標(biāo)并進(jìn)行初步分析指出問(wèn)題的難點(diǎn)和關(guān)鍵點(diǎn)。模型假設(shè)與符號(hào)說(shuō)明假設(shè)要合理且完整列出。符號(hào)說(shuō)明建議用三線表格清晰明了。模型建立與求解這是論文的核心。模型建立詳細(xì)闡述你的數(shù)學(xué)模型。包括決策變量定義、目標(biāo)函數(shù)數(shù)學(xué)公式、約束條件數(shù)學(xué)公式。推導(dǎo)過(guò)程要嚴(yán)謹(jǐn)。算法設(shè)計(jì)解釋你為何選擇該算法描述算法步驟最好配上流程圖說(shuō)明關(guān)鍵參數(shù)如模擬退火的初始溫度、降溫速率是如何設(shè)定的。模型求解與結(jié)果分析數(shù)據(jù)與實(shí)驗(yàn)設(shè)置說(shuō)明你使用的數(shù)據(jù)題目給的或自己生成的實(shí)驗(yàn)的軟硬件環(huán)境。結(jié)果展示用表格、圖形如上面的路徑圖直觀展示結(jié)果。對(duì)結(jié)果進(jìn)行分析解釋為什么這個(gè)方案是合理的。靈敏度分析改變關(guān)鍵參數(shù)如車(chē)輛容量、時(shí)間窗寬窄觀察結(jié)果如何變化。這能體現(xiàn)你對(duì)模型魯棒性的思考是重要的加分項(xiàng)。模型對(duì)比如果你嘗試了多種算法如精確求解、模擬退火、遺傳算法在這里對(duì)比它們的求解時(shí)間和結(jié)果質(zhì)量。模型評(píng)價(jià)與推廣客觀評(píng)價(jià)你模型的優(yōu)點(diǎn)如求解效率高、結(jié)果好和缺點(diǎn)如某些假設(shè)的局限性。討論模型可以推廣到哪些類(lèi)似場(chǎng)景。參考文獻(xiàn)與附錄參考文獻(xiàn)格式要規(guī)范。附錄可以放核心代碼片段不宜過(guò)長(zhǎng)、大型數(shù)據(jù)表格等。5.2 常見(jiàn)“坑”與應(yīng)對(duì)策略根據(jù)多年評(píng)審和參賽經(jīng)驗(yàn)以下是新手最容易失分的地方摘要空洞無(wú)物避免寫(xiě)“本文建立了模型使用了算法得到了結(jié)果”這樣的套話。必須包含具體的模型名稱(chēng)如“帶時(shí)間窗的車(chē)輛路徑規(guī)劃模型”、算法名稱(chēng)如“改進(jìn)的模擬退火算法”和具體的數(shù)值結(jié)果如“將總行駛距離降低了15%”。模型與算法描述脫節(jié)論文前半部分寫(xiě)了一個(gè)復(fù)雜的數(shù)學(xué)模型后半部分算法部分卻只字不提如何求解這個(gè)模型。必須明確指出算法是如何處理模型中的約束如時(shí)間窗、容量的。例如在模擬退火的鄰域操作后你是如何檢查和修復(fù)不可行解的結(jié)果分析只有圖表沒(méi)有文字不要只扔出一張圖和一個(gè)表。必須用文字描述圖表顯示了什么并解釋其含義。例如“如圖3所示5輛車(chē)的負(fù)載均達(dá)到了容量的80%以上說(shuō)明車(chē)輛利用率較高資源配置合理?！焙雎造`敏度分析很多隊(duì)伍只給出一種參數(shù)下的結(jié)果。這是不夠的。你應(yīng)該問(wèn)自己如果需求增加20%怎么辦如果時(shí)間窗變得更緊怎么辦進(jìn)行這些分析能極大提升論文的深度。代碼與論文結(jié)果對(duì)不上這是致命錯(cuò)誤。確保論文中所有數(shù)據(jù)、圖表都來(lái)自你實(shí)際運(yùn)行的程序。在提交前務(wù)必重新運(yùn)行一遍最終代碼核對(duì)關(guān)鍵數(shù)字。排版混亂使用LaTeX是學(xué)術(shù)規(guī)范的最佳選擇它能完美處理公式、圖表編號(hào)和參考文獻(xiàn)。如果使用Word務(wù)必利用樣式功能確保標(biāo)題、正文格式統(tǒng)一圖表編號(hào)自動(dòng)更新。6. 競(jìng)賽實(shí)戰(zhàn)技巧與備賽建議最后分享一些超越單道題目的通用競(jìng)賽技巧。6.1 團(tuán)隊(duì)分工與時(shí)間管理一個(gè)典型的三人團(tuán)隊(duì)建議這樣分工建模手負(fù)責(zé)問(wèn)題分析、模型構(gòu)建、論文核心部分模型、算法的撰寫(xiě)。需要較強(qiáng)的數(shù)學(xué)抽象能力和邏輯思維。編程手負(fù)責(zé)算法實(shí)現(xiàn)、數(shù)據(jù)清洗、結(jié)果計(jì)算和可視化。需要熟練使用Python/MATLAB并對(duì)算法有深刻理解。寫(xiě)作手負(fù)責(zé)論文整體架構(gòu)、摘要、問(wèn)題重述、結(jié)果分析、模型評(píng)價(jià)等部分的撰寫(xiě)以及最終的排版、潤(rùn)色。需要良好的文字功底和邏輯組織能力。時(shí)間管理是生命線。以96小時(shí)賽制為例第1天0-24h所有人共同讀題、討論確定2-3個(gè)可能的建模方向。建模手開(kāi)始細(xì)化最優(yōu)方向的模型編程手開(kāi)始準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)和基礎(chǔ)代碼框架如距離矩陣計(jì)算、初始解生成寫(xiě)作手開(kāi)始撰寫(xiě)問(wèn)題重述和模型假設(shè)。第2-3天24-72h建模手和編程手緊密配合實(shí)現(xiàn)核心算法并調(diào)試。寫(xiě)作手同步撰寫(xiě)模型建立和算法設(shè)計(jì)部分。在第二天結(jié)束前必須跑出第一個(gè)可行解。第3天下午-第4天上午72-90h進(jìn)行大量實(shí)驗(yàn)優(yōu)化算法參數(shù)進(jìn)行靈敏度分析。寫(xiě)作手整合所有結(jié)果完成結(jié)果分析、模型評(píng)價(jià)部分。團(tuán)隊(duì)共同打磨摘要。第4天下午90-96h最后檢查、排版、潤(rùn)色。絕對(duì)不要在這個(gè)時(shí)間段還在修改模型或跑新程序極易出錯(cuò)。留出至少2小時(shí)進(jìn)行最終校對(duì)和提交。6.2 工具鏈準(zhǔn)備工欲善其事必先利其器。賽前準(zhǔn)備好以下工具和環(huán)境編程環(huán)境安裝好Python推薦Anaconda發(fā)行版包含眾多科學(xué)計(jì)算庫(kù)或MATLAB。配置好常用的IDE如PyCharm, VSCode, Jupyter Notebook。核心庫(kù)科學(xué)計(jì)算NumPy,Pandas(數(shù)據(jù)處理)可視化Matplotlib,Seaborn優(yōu)化求解PuLP/ortools(調(diào)用求解器),scipy.optimize算法實(shí)現(xiàn)基礎(chǔ)庫(kù)足夠也可了解DEAP(遺傳算法框架)寫(xiě)作與協(xié)作強(qiáng)烈推薦 LaTeX使用Overleaf在線平臺(tái)進(jìn)行團(tuán)隊(duì)協(xié)作模板統(tǒng)一排版精美。提前熟悉常用數(shù)學(xué)公式、表格、圖片的插入語(yǔ)法。版本控制使用Git配合GitHub/Gitee管理代碼和論文避免版本混亂。文獻(xiàn)與資料庫(kù)提前收集整理經(jīng)典模型線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、圖論模型和經(jīng)典算法各種啟發(fā)式算法的原理介紹、偽代碼和簡(jiǎn)單實(shí)現(xiàn)案例。建立自己的知識(shí)庫(kù)。6.3 心態(tài)調(diào)整與臨場(chǎng)應(yīng)對(duì)選題決策不要糾結(jié)太久。用半天時(shí)間充分討論A、B、C題評(píng)估每道題的數(shù)據(jù)可獲性、模型清晰度和團(tuán)隊(duì)能力匹配度然后果斷選擇并堅(jiān)持做下去。最忌諱中途換題。遇到瓶頸當(dāng)算法調(diào)不通或結(jié)果不理想時(shí)不要集體陷入焦慮。可以1休息半小時(shí)換個(gè)思路2回歸問(wèn)題本質(zhì)檢查模型假設(shè)是否合理3簡(jiǎn)化問(wèn)題先求解一個(gè)子問(wèn)題或放松部分約束再逐步復(fù)雜化。結(jié)果不完美數(shù)學(xué)建模競(jìng)賽很少有“完美”解。只要你的模型合理算法有效分析深入即使最終數(shù)值不是最優(yōu)也能獲得好評(píng)。論文的完整性和邏輯性往往比絕對(duì)的結(jié)果精度更重要。誠(chéng)信為本引用參考文獻(xiàn)務(wù)必注明使用開(kāi)源代碼需在論文中說(shuō)明。絕對(duì)不要抄襲他人論文或購(gòu)買(mǎi)成品一旦查實(shí)后果嚴(yán)重。數(shù)學(xué)建模競(jìng)賽是一場(chǎng)智力的馬拉松更是團(tuán)隊(duì)協(xié)作的試金石。它考驗(yàn)的不僅僅是數(shù)學(xué)和編程能力更是問(wèn)題拆解、快速學(xué)習(xí)、溝通表達(dá)和抗壓能力的綜合體現(xiàn)。以2022年亞太杯B題為鏡掌握從問(wèn)題分析到模型構(gòu)建從算法選型到編程實(shí)現(xiàn)再到論文寫(xiě)作的完整閉環(huán)你收獲的將不只是一份獎(jiǎng)項(xiàng)更是一套解決復(fù)雜現(xiàn)實(shí)問(wèn)題的思維框架和實(shí)踐能力。這份能力無(wú)論是在未來(lái)的學(xué)術(shù)研究還是工業(yè)界項(xiàng)目中都將讓你受益匪淺。 數(shù)學(xué)建模競(jìng)賽實(shí)戰(zhàn)：從車(chē)輛路徑問(wèn)題到算法實(shí)現(xiàn)與論文寫(xiě)作
1. 項(xiàng)目概述從一道賽題到一套完整解決方案去年帶隊(duì)參加亞太數(shù)學(xué)杯APMCM的經(jīng)歷讓我對(duì)數(shù)學(xué)建模競(jìng)賽的備賽與實(shí)戰(zhàn)有了更深的體會(huì)。特別是2022年的B題它不像一些純理論推導(dǎo)的題目而是緊密貼合了現(xiàn)實(shí)中的資源調(diào)度與路徑優(yōu)化問(wèn)題本質(zhì)上是一個(gè)帶有復(fù)雜約束的組合優(yōu)化難題。這類(lèi)題目在國(guó)賽、美賽乃至企業(yè)實(shí)際項(xiàng)目中都屢見(jiàn)不鮮比如物流中心的車(chē)輛排班、生產(chǎn)線的工序調(diào)度或者我們熟悉的網(wǎng)約車(chē)平臺(tái)訂單與司機(jī)的匹配。題目給出的可能是一個(gè)簡(jiǎn)化場(chǎng)景但背后考察的核心能力是相通的如何將模糊的現(xiàn)實(shí)問(wèn)題轉(zhuǎn)化為清晰的數(shù)學(xué)模型如何為這個(gè)模型匹配合適的算法以及如何通過(guò)編程將算法實(shí)現(xiàn)并得到可信的結(jié)果。很多同學(xué)拿到題目后最容易卡住的兩個(gè)點(diǎn)就是“思路”和“程序”。思路不清就像在迷宮里亂轉(zhuǎn)建出的模型要么過(guò)于簡(jiǎn)單漏掉關(guān)鍵約束要么過(guò)于復(fù)雜根本無(wú)法求解。程序不強(qiáng)再好的思路也只能停留在紙上算不出結(jié)果或者算得太慢錯(cuò)過(guò)提交時(shí)間。這篇內(nèi)容我就以2022年亞太杯B題為引子不局限于這一道題的具體數(shù)據(jù)而是拆解這類(lèi)“資源調(diào)度與路徑優(yōu)化”問(wèn)題的通用破題思路、核心算法選型以及從建模到編程落地的完整流程。無(wú)論你是正在備戰(zhàn)亞太杯、國(guó)賽還是對(duì)數(shù)學(xué)建模感興趣希望這些從實(shí)戰(zhàn)中踩坑總結(jié)的經(jīng)驗(yàn)?zāi)軒湍闵僮邚澛贰?. 核心思路拆解如何將現(xiàn)實(shí)問(wèn)題“翻譯”成數(shù)學(xué)模型面對(duì)一道陌生的賽題第一步不是急著打開(kāi)MATLAB或Python而是拿出紙筆進(jìn)行深度的問(wèn)題分析。2022年B題的典型特征是多點(diǎn)、多資源、有時(shí)序要求。我們需要建立一套系統(tǒng)性的分析框架。2.1 問(wèn)題要素抽象與定義首先把題目中所有“名詞”找出來(lái)并明確它們的數(shù)學(xué)身份。這通常包括實(shí)體Entities誰(shuí)在移動(dòng)誰(shuí)被服務(wù)例如題目中的“服務(wù)點(diǎn)”、“需求點(diǎn)”、“車(chē)輛”、“工作人員”。在數(shù)學(xué)上它們通常被抽象為“點(diǎn)”Node或“智能體”Agent。屬性Attributes每個(gè)實(shí)體有什么特征例如點(diǎn)的位置坐標(biāo)、需求量、服務(wù)時(shí)間窗口車(chē)輛的容量、速度、起始位置工作人員的工作時(shí)長(zhǎng)、技能等級(jí)。這些是模型的參數(shù)。關(guān)系Relationships實(shí)體之間如何交互例如從點(diǎn)A到點(diǎn)B的距離或耗時(shí)通常構(gòu)成一個(gè)成本矩陣車(chē)輛訪問(wèn)點(diǎn)必須滿足其時(shí)間窗點(diǎn)的需求必須被滿足且不能超過(guò)車(chē)輛容量。這些是模型的約束條件。目標(biāo)Objective我們要優(yōu)化什么題目可能要求“總路徑最短”、“總耗時(shí)最少”、“總成本最低”、“滿足需求的點(diǎn)最多”、“車(chē)輛使用數(shù)最少”等。有時(shí)是單目標(biāo)有時(shí)是多目標(biāo)需要權(quán)衡。以2022年B題為例經(jīng)過(guò)抽象我們很可能得到一個(gè)“帶時(shí)間窗和容量約束的車(chē)輛路徑問(wèn)題Capacitated Vehicle Routing Problem with Time Windows, CVRPTW”的變體。明確這一點(diǎn)至關(guān)重要因?yàn)樗苯又赶蛄艘延械慕?jīng)典模型和算法庫(kù)我們不需要從零發(fā)明輪子。2.2 模型假設(shè)的藝術(shù)在精確與可行之間權(quán)衡數(shù)學(xué)建模不是物理仿真不可能100%還原現(xiàn)實(shí)。做出合理且必要的假設(shè)是簡(jiǎn)化問(wèn)題、使模型可解的關(guān)鍵。這里有幾個(gè)原則必要性原則這個(gè)假設(shè)是否為了抓住問(wèn)題核心而不得不做例如假設(shè)車(chē)輛勻速行駛是為了簡(jiǎn)化路徑成本計(jì)算。簡(jiǎn)化性原則這個(gè)假設(shè)能否顯著降低模型復(fù)雜度例如假設(shè)每個(gè)點(diǎn)的需求必須由一輛車(chē)一次完成即需求不可拆分這避免了復(fù)雜的貨物裝載組合優(yōu)化?？赊q護(hù)原則如果評(píng)委質(zhì)疑你的假設(shè)是否有合理的現(xiàn)實(shí)依據(jù)或數(shù)據(jù)支持例如假設(shè)兩點(diǎn)間距離為直線距離歐氏距離你可以說(shuō)明在城區(qū)尺度或數(shù)據(jù)精度下這是一個(gè)可接受的近似如果涉及交通則可能需要改用道路網(wǎng)絡(luò)距離。一個(gè)常見(jiàn)的誤區(qū)是假設(shè)過(guò)于理想化導(dǎo)致模型脫離實(shí)際。例如忽略車(chē)輛的裝卸貨時(shí)間或者在多車(chē)型問(wèn)題中假設(shè)所有車(chē)性能完全相同。在2022年B題中可能需要仔細(xì)考慮“服務(wù)時(shí)間”是否包含在時(shí)間窗內(nèi)以及車(chē)輛在不同路段的速度是否恒定。在論文中必須用單獨(dú)一小節(jié)清晰列出所有主要假設(shè)并簡(jiǎn)要說(shuō)明理由。2.3 決策變量與目標(biāo)函數(shù)的形式化這是將思路轉(zhuǎn)化為數(shù)學(xué)語(yǔ)言的核心步驟。決策變量是模型輸出的結(jié)果是我們要求解的東西。對(duì)于路徑問(wèn)題最經(jīng)典的決策變量是二進(jìn)制變量 ( x_{ijk} )如果車(chē)輛k從點(diǎn)i行駛到點(diǎn)j則為1否則為0。這里i和j包括所有需求點(diǎn)和車(chē)場(chǎng)起點(diǎn)/終點(diǎn)。目標(biāo)函數(shù)則是這些決策變量的函數(shù)。最常見(jiàn)的是最小化總行駛距離( \min \sum_{k} \sum_{i} \sum_{j} cost_{ij} \cdot x_{ijk} )。如果題目要求最小化車(chē)輛數(shù)可以引入一個(gè)關(guān)于車(chē)輛是否被使用的二進(jìn)制變量并將其納入目標(biāo)通常給予一個(gè)很大的權(quán)重。一個(gè)關(guān)鍵技巧當(dāng)目標(biāo)函數(shù)包含多個(gè)方面如既想省錢(qián)又想快時(shí)可以采用加權(quán)求和法將其轉(zhuǎn)化為單目標(biāo)( \min w_1 * TotalDistance w_2 * TotalTime )。權(quán)重的選擇需要謹(jǐn)慎可以通過(guò)敏感性分析來(lái)討論不同權(quán)重對(duì)結(jié)果的影響。另一種更高級(jí)的方法是帕累托優(yōu)化求出一組“非劣解”即在不使其他目標(biāo)變差的情況下無(wú)法再改進(jìn)任何一個(gè)目標(biāo)但這對(duì)算法和編程要求更高。3. 算法選型與策略沒(méi)有銀彈只有合適的選擇模型建立后選擇什么算法求解這取決于模型規(guī)模、復(fù)雜度和你對(duì)結(jié)果的要求最優(yōu)解 vs. 滿意解。3.1 精確算法小規(guī)模問(wèn)題的“標(biāo)準(zhǔn)答案”對(duì)于節(jié)點(diǎn)數(shù)較少例如少于20個(gè)需求點(diǎn)的問(wèn)題可以嘗試使用精確算法求取全局最優(yōu)解。線性/整數(shù)規(guī)劃求解器如果你將問(wèn)題成功構(gòu)建為混合整數(shù)線性規(guī)劃MILP模型那么可以使用像Gurobi、CPLEX這樣的商業(yè)求解器或者開(kāi)源的SCIP、CBC。它們利用分支定界、割平面等算法能保證找到最優(yōu)解。在Python中你可以用PuLP、ortools等庫(kù)來(lái)調(diào)用它們。適用場(chǎng)景與局限精確求解器是驗(yàn)證模型正確性和獲取小規(guī)模問(wèn)題基準(zhǔn)答案的利器。但當(dāng)問(wèn)題規(guī)模擴(kuò)大求解時(shí)間會(huì)呈指數(shù)級(jí)增長(zhǎng)可能幾個(gè)小時(shí)甚至幾天都算不完。因此在競(jìng)賽中除非問(wèn)題特別簡(jiǎn)單否則精確算法通常只作為對(duì)比基準(zhǔn)而非主力求解方法。3.2 啟發(fā)式與元啟發(fā)式算法競(jìng)賽的主力軍對(duì)于競(jìng)賽中常見(jiàn)的中等規(guī)模問(wèn)題啟發(fā)式算法是更實(shí)際的選擇。它們不能在理論上保證最優(yōu)但能在合理時(shí)間內(nèi)給出高質(zhì)量的解。構(gòu)造型啟發(fā)式從零開(kāi)始構(gòu)建一個(gè)可行解。最近鄰法從車(chē)場(chǎng)出發(fā)總是前往距離當(dāng)前點(diǎn)最近且滿足約束的未訪問(wèn)點(diǎn)。簡(jiǎn)單快速但結(jié)果往往一般。節(jié)約算法是解決VRP類(lèi)問(wèn)題的經(jīng)典方法。它先假設(shè)每個(gè)點(diǎn)都用一輛車(chē)單獨(dú)服務(wù)然后計(jì)算合并兩條路線所能“節(jié)約”的距離優(yōu)先合并節(jié)約值最大的路線直到不能合并為止。這種方法能快速得到一個(gè)不錯(cuò)的初始解。元啟發(fā)式算法對(duì)現(xiàn)有解進(jìn)行迭代改進(jìn)的通用框架。這是數(shù)學(xué)建模競(jìng)賽的“明星算法族”。模擬退火靈感來(lái)自固體退火過(guò)程。它允許以一定概率接受比當(dāng)前解差的“壞解”從而有機(jī)會(huì)跳出局部最優(yōu)陷阱。關(guān)鍵參數(shù)是初始溫度、降溫速率和終止溫度。實(shí)操心得降溫速率不宜過(guò)快如0.95比0.99更容易找到好解并且可以增加在同一個(gè)溫度下的多次迭代馬爾可夫鏈長(zhǎng)度。遺傳算法模仿生物進(jìn)化。將解編碼為“染色體”如路徑的順序列表通過(guò)選擇、交叉、變異產(chǎn)生新一代解。關(guān)鍵點(diǎn)路徑問(wèn)題的編碼和交叉算子設(shè)計(jì)需要特別小心要保證生成的新解仍然是有效路徑滿足車(chē)輛容量、時(shí)間窗等。常用的交叉算子有順序交叉、部分映射交叉。蟻群算法模擬螞蟻覓食的信息素機(jī)制。螞蟻根據(jù)路徑上的信息素濃度和啟發(fā)式信息如距離倒數(shù)選擇路徑信息素會(huì)隨著優(yōu)質(zhì)解的發(fā)現(xiàn)而增強(qiáng)。它特別適合求解路徑問(wèn)題。參數(shù)調(diào)優(yōu)經(jīng)驗(yàn)信息素?fù)]發(fā)系數(shù)很重要太高會(huì)導(dǎo)致過(guò)早收斂于局部最優(yōu)太低則搜索隨機(jī)性太強(qiáng)。通常設(shè)置在0.1到0.5之間。算法選擇建議對(duì)于2022年B題這類(lèi)動(dòng)態(tài)性不強(qiáng)、約束明確的靜態(tài)VRPTW問(wèn)題模擬退火和遺傳算法是穩(wěn)健且易于實(shí)現(xiàn)的選擇?？梢韵仁褂霉?jié)約算法生成一個(gè)初始解然后用模擬退火進(jìn)行優(yōu)化。蟻群算法效果通常很好但參數(shù)更多調(diào)優(yōu)更耗時(shí)。3.3 現(xiàn)代求解器與開(kāi)源框架站在巨人的肩膀上你不必所有算法都從頭實(shí)現(xiàn)。利用好開(kāi)源工具能極大提升效率。OR-Tools谷歌開(kāi)發(fā)的開(kāi)源運(yùn)籌學(xué)工具包是數(shù)學(xué)建模競(jìng)賽的“神器”。它內(nèi)置了針對(duì)VRP、VRPTW等問(wèn)題的專(zhuān)用求解器使用的是基于局部搜索的先進(jìn)啟發(fā)式算法。你只需要定義好距離矩陣、車(chē)輛數(shù)量、容量、時(shí)間窗等參數(shù)它就能在秒級(jí)時(shí)間內(nèi)返回一個(gè)高質(zhì)量的解。對(duì)于快速驗(yàn)證模型和獲取基準(zhǔn)解非常有用。VROOM一個(gè)專(zhuān)攻車(chē)輛路徑優(yōu)化的開(kāi)源引擎性能非常強(qiáng)勁。使用策略在競(jìng)賽中可以先用OR-Tools快速求出一個(gè)解作為你自定義算法性能的對(duì)比基準(zhǔn)。同時(shí)你也可以研究這些工具得出的解的結(jié)構(gòu)啟發(fā)你自己的算法設(shè)計(jì)。4. 編程實(shí)現(xiàn)與代碼架構(gòu)思路和算法確定后就要用代碼來(lái)實(shí)現(xiàn)。清晰的代碼結(jié)構(gòu)不僅能讓你調(diào)試更輕松也能在論文中更好地展示你的工作。4.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)一切的基礎(chǔ)良好的數(shù)據(jù)結(jié)構(gòu)是高效算法的前提。對(duì)于VRP問(wèn)題我建議定義以下核心類(lèi)class Point: def __init__(self, id, x, y, demand, ready_time, due_date, service_time): self.id id # 點(diǎn)ID0通常代表車(chē)場(chǎng) self.x x self.y y self.demand demand # 需求量 self.ready_time ready_time # 最早開(kāi)始服務(wù)時(shí)間 self.due_date due_date # 最晚開(kāi)始服務(wù)時(shí)間 self.service_time service_time # 服務(wù)耗時(shí) class Vehicle: def __init__(self, id, capacity, start_point, end_point): self.id id self.capacity capacity self.start_point start_point # 起始點(diǎn)索引 self.end_point end_point # 返回點(diǎn)索引通常與起始點(diǎn)相同 self.route [] # 存儲(chǔ)路徑點(diǎn)ID的列表 self.load 0 # 當(dāng)前載重 self.time 0 # 當(dāng)前時(shí)間 class ProblemInstance: def __init__(self, points, vehicles, distance_matrix, time_matrix): self.points points # 所有點(diǎn)的列表 self.vehicles vehicles # 所有車(chē)輛的列表 self.distance_matrix distance_matrix # 距離矩陣 self.time_matrix time_matrix # 時(shí)間矩陣可由距離和速度算出使用類(lèi)來(lái)組織數(shù)據(jù)比單純使用列表和字典更清晰也更容易實(shí)現(xiàn)與約束檢查、成本計(jì)算相關(guān)的成員方法。4.2 核心算法模塊實(shí)現(xiàn)示例模擬退火以下是一個(gè)用于優(yōu)化VRP路徑的模擬退火算法核心框架。假設(shè)我們已經(jīng)有了一個(gè)初始解用Solution類(lèi)表示它包含了一個(gè)車(chē)輛路徑的列表。import math import random import copy def simulated_annealing(initial_solution, distance_matrix, points, max_iter10000): current_solution copy.deepcopy(initial_solution) current_cost calculate_total_cost(current_solution, distance_matrix, points) best_solution copy.deepcopy(current_solution) best_cost current_cost T 1000.0 # 初始溫度 T_min 1e-3 # 終止溫度 alpha 0.995 # 降溫系數(shù) iteration 0 while T T_min and iteration max_iter: # 1. 在當(dāng)前解附近產(chǎn)生一個(gè)鄰域解 new_solution generate_neighbor(current_solution) new_cost calculate_total_cost(new_solution, distance_matrix, points) # 2. 計(jì)算成本差 delta_cost new_cost - current_cost # 3. 接受準(zhǔn)則如果新解更好則接受如果更差以一定概率接受 if delta_cost 0 or random.random() math.exp(-delta_cost / T): current_solution new_solution current_cost new_cost # 更新歷史最優(yōu) if current_cost best_cost: best_solution copy.deepcopy(current_solution) best_cost current_cost # 4. 降溫 T * alpha iteration 1 return best_solution, best_cost def generate_neighbor(solution): 生成鄰域解常用操作有 neighbor copy.deepcopy(solution) operation random.choice([swap, relocate, 2-opt]) if operation swap: # 隨機(jī)選擇兩條路徑中的兩個(gè)點(diǎn)進(jìn)行交換 r1_idx, r2_idx random.sample(range(len(neighbor.routes)), 2) route1, route2 neighbor.routes[r1_idx], neighbor.routes[r2_idx] if len(route1) 1 and len(route2) 1: i random.randint(0, len(route1)-2) # 避開(kāi)車(chē)場(chǎng) j random.randint(0, len(route2)-2) route1[i], route2[j] route2[j], route1[i] elif operation relocate: # 將一個(gè)點(diǎn)從一條路徑移到另一條路徑 r1_idx, r2_idx random.sample(range(len(neighbor.routes)), 2) route1, route2 neighbor.routes[r1_idx], neighbor.routes[r2_idx] if len(route1) 1: i random.randint(0, len(route1)-2) point_to_move route1.pop(i) # 插入到route2的隨機(jī)位置 j random.randint(0, len(route2)-1) route2.insert(j, point_to_move) # ... 其他操作如2-opt路徑內(nèi)反轉(zhuǎn)一段 return neighbor關(guān)鍵提示generate_neighbor函數(shù)的設(shè)計(jì)至關(guān)重要它決定了算法的搜索能力。好的鄰域結(jié)構(gòu)應(yīng)該既能產(chǎn)生足夠的變化又能保證大部分新解仍是可行的滿足容量、時(shí)間窗約束。在實(shí)際編碼中需要在執(zhí)行操作后立即進(jìn)行約束檢查如果違反則丟棄該操作或進(jìn)行修復(fù)。4.3 可視化與結(jié)果分析讓論文“亮”起來(lái)結(jié)果可視化是論文的加分項(xiàng)。一張清晰的路徑圖勝過(guò)千言萬(wàn)語(yǔ)。import matplotlib.pyplot as plt def plot_solution(solution, points): plt.figure(figsize(10, 8)) colors plt.cm.tab20(np.linspace(0, 1, len(solution.routes))) # 畫(huà)出所有點(diǎn) all_x [p.x for p in points[1:]] # 排除車(chē)場(chǎng) all_y [p.y for p in points[1:]] plt.scatter(all_x, all_y, cgray, alpha0.6, labelDemand Points) # 畫(huà)車(chē)場(chǎng) depot points[0] plt.scatter(depot.x, depot.y, cred, markers, s200, labelDepot, edgecolorsblack) # 畫(huà)出每條路徑 for idx, route in enumerate(solution.routes): if not route: # 空路徑 continue route_points [points[i] for i in route] x_coords [p.x for p in route_points] y_coords [p.y for p in route_points] plt.plot(x_coords, y_coords, ccolors[idx], linewidth2, markero, labelfVehicle {idx1}) plt.xlabel(X Coordinate) plt.ylabel(Y Coordinate) plt.title(Optimized Vehicle Routes) plt.legend(bbox_to_anchor(1.05, 1), locupper left) plt.grid(True, alpha0.3) plt.tight_layout() plt.savefig(optimized_routes.png, dpi300) plt.show()除了路徑圖還應(yīng)生成關(guān)鍵指標(biāo)的表格例如車(chē)輛編號(hào)路徑順序總載重總行駛距離開(kāi)始時(shí)間結(jié)束時(shí)間時(shí)間窗違反容量違反10 - 3 - 5 - 8 - 085156.70245無(wú)無(wú)20 - 1 - 4 - 7 - 092142.30238無(wú)無(wú)........................總計(jì)-354876.5--00這樣的表格清晰地展示了每輛車(chē)的任務(wù)分配和整體方案的質(zhì)量。5. 從模型到論文寫(xiě)作要點(diǎn)與避坑指南編程求解出結(jié)果只完成了工作的一半如何將其組織成一篇邏輯清晰、表達(dá)專(zhuān)業(yè)的論文是決定最終成績(jī)的關(guān)鍵。5.1 論文結(jié)構(gòu)骨架一篇標(biāo)準(zhǔn)的數(shù)學(xué)建模論文應(yīng)包含以下部分并注意突出你的工作亮點(diǎn)摘要重中之重需獨(dú)立成頁(yè)用300-500字概括整個(gè)工作。必須包含問(wèn)題重述、你的主要思路、所用模型、核心算法、關(guān)鍵結(jié)論和數(shù)值結(jié)果如總成本降低了多少。評(píng)委可能只看摘要所以要字斟句酌。問(wèn)題重述與分析不要照抄題目。用自己的語(yǔ)言提煉問(wèn)題背景、已知條件、約束和目標(biāo)并進(jìn)行初步分析指出問(wèn)題的難點(diǎn)和關(guān)鍵點(diǎn)。模型假設(shè)與符號(hào)說(shuō)明假設(shè)要合理且完整列出。符號(hào)說(shuō)明建議用三線表格清晰明了。模型建立與求解這是論文的核心。模型建立詳細(xì)闡述你的數(shù)學(xué)模型。包括決策變量定義、目標(biāo)函數(shù)數(shù)學(xué)公式、約束條件數(shù)學(xué)公式。推導(dǎo)過(guò)程要嚴(yán)謹(jǐn)。算法設(shè)計(jì)解釋你為何選擇該算法描述算法步驟最好配上流程圖說(shuō)明關(guān)鍵參數(shù)如模擬退火的初始溫度、降溫速率是如何設(shè)定的。模型求解與結(jié)果分析數(shù)據(jù)與實(shí)驗(yàn)設(shè)置說(shuō)明你使用的數(shù)據(jù)題目給的或自己生成的實(shí)驗(yàn)的軟硬件環(huán)境。結(jié)果展示用表格、圖形如上面的路徑圖直觀展示結(jié)果。對(duì)結(jié)果進(jìn)行分析解釋為什么這個(gè)方案是合理的。靈敏度分析改變關(guān)鍵參數(shù)如車(chē)輛容量、時(shí)間窗寬窄觀察結(jié)果如何變化。這能體現(xiàn)你對(duì)模型魯棒性的思考是重要的加分項(xiàng)。模型對(duì)比如果你嘗試了多種算法如精確求解、模擬退火、遺傳算法在這里對(duì)比它們的求解時(shí)間和結(jié)果質(zhì)量。模型評(píng)價(jià)與推廣客觀評(píng)價(jià)你模型的優(yōu)點(diǎn)如求解效率高、結(jié)果好和缺點(diǎn)如某些假設(shè)的局限性。討論模型可以推廣到哪些類(lèi)似場(chǎng)景。參考文獻(xiàn)與附錄參考文獻(xiàn)格式要規(guī)范。附錄可以放核心代碼片段不宜過(guò)長(zhǎng)、大型數(shù)據(jù)表格等。5.2 常見(jiàn)“坑”與應(yīng)對(duì)策略根據(jù)多年評(píng)審和參賽經(jīng)驗(yàn)以下是新手最容易失分的地方摘要空洞無(wú)物避免寫(xiě)“本文建立了模型使用了算法得到了結(jié)果”這樣的套話。必須包含具體的模型名稱(chēng)如“帶時(shí)間窗的車(chē)輛路徑規(guī)劃模型”、算法名稱(chēng)如“改進(jìn)的模擬退火算法”和具體的數(shù)值結(jié)果如“將總行駛距離降低了15%”。模型與算法描述脫節(jié)論文前半部分寫(xiě)了一個(gè)復(fù)雜的數(shù)學(xué)模型后半部分算法部分卻只字不提如何求解這個(gè)模型。必須明確指出算法是如何處理模型中的約束如時(shí)間窗、容量的。例如在模擬退火的鄰域操作后你是如何檢查和修復(fù)不可行解的結(jié)果分析只有圖表沒(méi)有文字不要只扔出一張圖和一個(gè)表。必須用文字描述圖表顯示了什么并解釋其含義。例如“如圖3所示5輛車(chē)的負(fù)載均達(dá)到了容量的80%以上說(shuō)明車(chē)輛利用率較高資源配置合理?！焙雎造`敏度分析很多隊(duì)伍只給出一種參數(shù)下的結(jié)果。這是不夠的。你應(yīng)該問(wèn)自己如果需求增加20%怎么辦如果時(shí)間窗變得更緊怎么辦進(jìn)行這些分析能極大提升論文的深度。代碼與論文結(jié)果對(duì)不上這是致命錯(cuò)誤。確保論文中所有數(shù)據(jù)、圖表都來(lái)自你實(shí)際運(yùn)行的程序。在提交前務(wù)必重新運(yùn)行一遍最終代碼核對(duì)關(guān)鍵數(shù)字。排版混亂使用LaTeX是學(xué)術(shù)規(guī)范的最佳選擇它能完美處理公式、圖表編號(hào)和參考文獻(xiàn)。如果使用Word務(wù)必利用樣式功能確保標(biāo)題、正文格式統(tǒng)一圖表編號(hào)自動(dòng)更新。6. 競(jìng)賽實(shí)戰(zhàn)技巧與備賽建議最后分享一些超越單道題目的通用競(jìng)賽技巧。6.1 團(tuán)隊(duì)分工與時(shí)間管理一個(gè)典型的三人團(tuán)隊(duì)建議這樣分工建模手負(fù)責(zé)問(wèn)題分析、模型構(gòu)建、論文核心部分模型、算法的撰寫(xiě)。需要較強(qiáng)的數(shù)學(xué)抽象能力和邏輯思維。編程手負(fù)責(zé)算法實(shí)現(xiàn)、數(shù)據(jù)清洗、結(jié)果計(jì)算和可視化。需要熟練使用Python/MATLAB并對(duì)算法有深刻理解。寫(xiě)作手負(fù)責(zé)論文整體架構(gòu)、摘要、問(wèn)題重述、結(jié)果分析、模型評(píng)價(jià)等部分的撰寫(xiě)以及最終的排版、潤(rùn)色。需要良好的文字功底和邏輯組織能力。時(shí)間管理是生命線。以96小時(shí)賽制為例第1天0-24h所有人共同讀題、討論確定2-3個(gè)可能的建模方向。建模手開(kāi)始細(xì)化最優(yōu)方向的模型編程手開(kāi)始準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)和基礎(chǔ)代碼框架如距離矩陣計(jì)算、初始解生成寫(xiě)作手開(kāi)始撰寫(xiě)問(wèn)題重述和模型假設(shè)。第2-3天24-72h建模手和編程手緊密配合實(shí)現(xiàn)核心算法并調(diào)試。寫(xiě)作手同步撰寫(xiě)模型建立和算法設(shè)計(jì)部分。在第二天結(jié)束前必須跑出第一個(gè)可行解。第3天下午-第4天上午72-90h進(jìn)行大量實(shí)驗(yàn)優(yōu)化算法參數(shù)進(jìn)行靈敏度分析。寫(xiě)作手整合所有結(jié)果完成結(jié)果分析、模型評(píng)價(jià)部分。團(tuán)隊(duì)共同打磨摘要。第4天下午90-96h最后檢查、排版、潤(rùn)色。絕對(duì)不要在這個(gè)時(shí)間段還在修改模型或跑新程序極易出錯(cuò)。留出至少2小時(shí)進(jìn)行最終校對(duì)和提交。6.2 工具鏈準(zhǔn)備工欲善其事必先利其器。賽前準(zhǔn)備好以下工具和環(huán)境編程環(huán)境安裝好Python推薦Anaconda發(fā)行版包含眾多科學(xué)計(jì)算庫(kù)或MATLAB。配置好常用的IDE如PyCharm, VSCode, Jupyter Notebook。核心庫(kù)科學(xué)計(jì)算NumPy,Pandas(數(shù)據(jù)處理)可視化Matplotlib,Seaborn優(yōu)化求解PuLP/ortools(調(diào)用求解器),scipy.optimize算法實(shí)現(xiàn)基礎(chǔ)庫(kù)足夠也可了解DEAP(遺傳算法框架)寫(xiě)作與協(xié)作強(qiáng)烈推薦 LaTeX使用Overleaf在線平臺(tái)進(jìn)行團(tuán)隊(duì)協(xié)作模板統(tǒng)一排版精美。提前熟悉常用數(shù)學(xué)公式、表格、圖片的插入語(yǔ)法。版本控制使用Git配合GitHub/Gitee管理代碼和論文避免版本混亂。文獻(xiàn)與資料庫(kù)提前收集整理經(jīng)典模型線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、圖論模型和經(jīng)典算法各種啟發(fā)式算法的原理介紹、偽代碼和簡(jiǎn)單實(shí)現(xiàn)案例。建立自己的知識(shí)庫(kù)。6.3 心態(tài)調(diào)整與臨場(chǎng)應(yīng)對(duì)選題決策不要糾結(jié)太久。用半天時(shí)間充分討論A、B、C題評(píng)估每道題的數(shù)據(jù)可獲性、模型清晰度和團(tuán)隊(duì)能力匹配度然后果斷選擇并堅(jiān)持做下去。最忌諱中途換題。遇到瓶頸當(dāng)算法調(diào)不通或結(jié)果不理想時(shí)不要集體陷入焦慮。可以1休息半小時(shí)換個(gè)思路2回歸問(wèn)題本質(zhì)檢查模型假設(shè)是否合理3簡(jiǎn)化問(wèn)題先求解一個(gè)子問(wèn)題或放松部分約束再逐步復(fù)雜化。結(jié)果不完美數(shù)學(xué)建模競(jìng)賽很少有“完美”解。只要你的模型合理算法有效分析深入即使最終數(shù)值不是最優(yōu)也能獲得好評(píng)。論文的完整性和邏輯性往往比絕對(duì)的結(jié)果精度更重要。誠(chéng)信為本引用參考文獻(xiàn)務(wù)必注明使用開(kāi)源代碼需在論文中說(shuō)明。絕對(duì)不要抄襲他人論文或購(gòu)買(mǎi)成品一旦查實(shí)后果嚴(yán)重。數(shù)學(xué)建模競(jìng)賽是一場(chǎng)智力的馬拉松更是團(tuán)隊(duì)協(xié)作的試金石。它考驗(yàn)的不僅僅是數(shù)學(xué)和編程能力更是問(wèn)題拆解、快速學(xué)習(xí)、溝通表達(dá)和抗壓能力的綜合體現(xiàn)。以2022年亞太杯B題為鏡掌握從問(wèn)題分析到模型構(gòu)建從算法選型到編程實(shí)現(xiàn)再到論文寫(xiě)作的完整閉環(huán)你收獲的將不只是一份獎(jiǎng)項(xiàng)更是一套解決復(fù)雜現(xiàn)實(shí)問(wèn)題的思維框架和實(shí)踐能力。這份能力無(wú)論是在未來(lái)的學(xué)術(shù)研究還是工業(yè)界項(xiàng)目中都將讓你受益匪淺。