1. 項(xiàng)目背景與問(wèn)題拆解當(dāng)數(shù)學(xué)建模遇上“送餐危機(jī)”去年帶學(xué)生參加數(shù)維杯A題“外賣(mài)騎手的送餐危機(jī)”一出來(lái)我們團(tuán)隊(duì)就樂(lè)了。這題太“接地氣”了簡(jiǎn)直就是把每天發(fā)生在你我身邊的外賣(mài)配送問(wèn)題抽象成了一個(gè)經(jīng)典的運(yùn)籌優(yōu)化模型。但樂(lè)完就發(fā)現(xiàn)題目背后藏著不少“坑”。所謂的“送餐危機(jī)”核心矛盾是什么是騎手在有限時(shí)間內(nèi)面對(duì)動(dòng)態(tài)涌入的訂單、復(fù)雜的路網(wǎng)、不確定的交通狀況和嚴(yán)格的平臺(tái)規(guī)則時(shí)如何規(guī)劃路徑才能最大化送達(dá)效率、最小化超時(shí)和成本。這聽(tīng)起來(lái)像是一個(gè)帶時(shí)間窗的車(chē)輛路徑問(wèn)題VRPTW但實(shí)際建模時(shí)你會(huì)發(fā)現(xiàn)它比教科書(shū)上的VRPTW復(fù)雜得多——訂單不是一次性給全的路況是實(shí)時(shí)變化的騎手還可能同時(shí)接多個(gè)順路單。網(wǎng)上能找到的很多優(yōu)秀論文或開(kāi)源代碼比如針對(duì)“蟻群算法解決連續(xù)問(wèn)題”、“全局搜索增強(qiáng)的改進(jìn)鯨魚(yú)算法”或者“AGV的A*算法”都為我們提供了寶貴的思路工具箱。但直接套用往往水土不服。比如你用標(biāo)準(zhǔn)的遺傳算法去解可能很快得到一個(gè)“理論上”的優(yōu)化路徑但這個(gè)路徑是否考慮了非機(jī)動(dòng)車(chē)道的限制是否考慮了寫(xiě)字樓等電梯的等待時(shí)間是否考慮了午高峰餐館出餐慢的隨機(jī)延遲這些細(xì)節(jié)才是把論文從“紙上談兵”變成“真槍實(shí)彈”的關(guān)鍵。所以這篇內(nèi)容不是簡(jiǎn)單地復(fù)現(xiàn)我們當(dāng)時(shí)的論文和程序而是想以一個(gè)過(guò)來(lái)人的身份拆解我們面對(duì)這道題時(shí)的完整思考過(guò)程、模型建立時(shí)的多次迭代、算法選型時(shí)的權(quán)衡對(duì)比以及編程實(shí)現(xiàn)中那些教科書(shū)不會(huì)寫(xiě)的“騷操作”和“踩坑實(shí)錄”。無(wú)論你是正在備戰(zhàn)數(shù)維杯、國(guó)賽、美賽的同學(xué)還是對(duì)路徑優(yōu)化、數(shù)學(xué)建模感興趣的朋友希望這些從實(shí)戰(zhàn)中沉淀下來(lái)的經(jīng)驗(yàn)?zāi)芙o你帶來(lái)一些不一樣的啟發(fā)。2. 模型構(gòu)建從現(xiàn)實(shí)問(wèn)題到數(shù)學(xué)語(yǔ)言的精確翻譯拿到題目第一步不是急著找算法而是把模糊的“送餐危機(jī)”翻譯成清晰的數(shù)學(xué)問(wèn)題。我們團(tuán)隊(duì)當(dāng)時(shí)花了將近半天時(shí)間來(lái)定義邊界、做出合理假設(shè)并確定優(yōu)化目標(biāo)。這一步走穩(wěn)了后面的算法和編程才有意義。2.1 核心要素定義與假設(shè)我們首先明確了模型中的幾個(gè)核心實(shí)體和它們的屬性騎手定義為移動(dòng)的配送單元。每個(gè)騎手有初始位置通常為配送站或上一個(gè)送達(dá)點(diǎn)、載貨容量能同時(shí)攜帶的訂單數(shù)本題中通常設(shè)為有限值如3-5單、移動(dòng)速度一個(gè)變量受路況影響。訂單每個(gè)訂單包含商家位置、顧客位置、期望送達(dá)時(shí)間窗通常是一個(gè)時(shí)間點(diǎn)如“30分鐘內(nèi)送達(dá)”我們將其處理為一個(gè)軟時(shí)間窗允許超時(shí)但需懲罰、預(yù)計(jì)備餐時(shí)間、實(shí)際重量/體積用于容量約束。路網(wǎng)我們將配送區(qū)域抽象為一個(gè)帶權(quán)圖。節(jié)點(diǎn)包括所有商家、所有顧客、配送站、重要的道路交叉口。邊的權(quán)重不是簡(jiǎn)單的歐氏距離而是預(yù)估騎行時(shí)間。這個(gè)時(shí)間是動(dòng)態(tài)的與時(shí)間段平峰/高峰、天氣等因素有關(guān)?；谶@些實(shí)體我們做出了幾個(gè)關(guān)鍵假設(shè)以平衡模型的復(fù)雜性與可求解性假設(shè)1訂單已知性我們采用“靜態(tài)-動(dòng)態(tài)”混合策略。在每一個(gè)調(diào)度周期如每5分鐘將已知的、尚未被分配的訂單視為靜態(tài)輸入進(jìn)行一波路徑規(guī)劃。這避免了完全動(dòng)態(tài)規(guī)劃的極端復(fù)雜性。假設(shè)2時(shí)間離散化將整個(gè)工作時(shí)間如午高峰11:00-13:00離散化為以分鐘為單位的時(shí)間片便于在算法中計(jì)算和追蹤時(shí)間。假設(shè)3速度簡(jiǎn)化騎手速度不是一個(gè)恒定值。我們將其建模為分段函數(shù)在商家/顧客點(diǎn)停留時(shí)速度為0在道路騎行時(shí)根據(jù)道路等級(jí)主干道、次干道、小巷賦予一個(gè)平均速度并在高峰時(shí)段乘以一個(gè)擁堵系數(shù)如0.7。假設(shè)4等待與懲罰騎手到達(dá)商家后若餐未備好則需等待。超時(shí)送達(dá)會(huì)產(chǎn)生懲罰成本懲罰函數(shù)我們?cè)O(shè)計(jì)為指數(shù)形式超時(shí)越久懲罰成本急劇上升這比線(xiàn)性懲罰更能體現(xiàn)平臺(tái)對(duì)用戶(hù)體驗(yàn)的重視。注意這些假設(shè)需要在論文中明確寫(xiě)出并論證其合理性。例如解釋為什么采用靜態(tài)-動(dòng)態(tài)混合策略是因?yàn)橥耆珜?shí)時(shí)調(diào)度對(duì)數(shù)據(jù)通信和計(jì)算能力要求極高而周期性批量處理是工業(yè)界的常見(jiàn)折中方案。2.2 多目標(biāo)優(yōu)化模型的建立送餐問(wèn)題天然是一個(gè)多目標(biāo)優(yōu)化問(wèn)題。平臺(tái)關(guān)心效率送得多、成本跑得省和體驗(yàn)不超時(shí)。我們將其整合為一個(gè)加權(quán)單目標(biāo)模型便于求解。決策變量x_{ijk} 0-1變量表示騎手k是否從節(jié)點(diǎn)i商家或顧客前往節(jié)點(diǎn)j。目標(biāo)函數(shù)最小化Minimize Z w1 * T_total w2 * C_distance w3 * P_delay其中T_total所有訂單的總配送完成時(shí)間makespan。最小化它意味著提升整體吞吐效率。C_distance所有騎手行駛的總距離或總時(shí)間。最小化它意味著降低油耗/電耗和騎手勞動(dòng)強(qiáng)度。P_delay所有訂單的超時(shí)懲罰總和。計(jì)算公式為 Σ max(0, t_actual - t_due)^2 * penalty_rate。使用平方項(xiàng)是為了讓算法極度厭惡嚴(yán)重超時(shí)。約束條件流量平衡每個(gè)騎手從配送站出發(fā)最終返回配送站或結(jié)束于最后一個(gè)顧客點(diǎn)。訂單服務(wù)唯一性每個(gè)訂單必須被且僅被一個(gè)騎手服務(wù)一次包括取餐和送餐。時(shí)間窗約束騎手到達(dá)每個(gè)顧客點(diǎn)的時(shí)間t_arrive應(yīng)盡量在期望時(shí)間t_due之前否則計(jì)入懲罰。容量約束騎手在任意時(shí)刻攜帶的訂單數(shù)不能超過(guò)其最大容量。取送順序約束對(duì)于任何一個(gè)訂單騎手必須先訪問(wèn)商家節(jié)點(diǎn)i才能訪問(wèn)對(duì)應(yīng)的顧客節(jié)點(diǎn)j。即t_arrive_i t_arrive_j。時(shí)間連續(xù)性約束騎手到達(dá)下一個(gè)節(jié)點(diǎn)j的時(shí)間等于離開(kāi)上一個(gè)節(jié)點(diǎn)i的時(shí)間 在i點(diǎn)的服務(wù)時(shí)間取餐或送餐 從i到j(luò)的行程時(shí)間。這個(gè)模型本質(zhì)上是一個(gè)帶容量約束、軟時(shí)間窗、同時(shí)取送貨的車(chē)輛路徑問(wèn)題VRPSPDTW并且是動(dòng)態(tài)分批輸入的。其復(fù)雜度是NP-Hard的對(duì)于稍大規(guī)模的問(wèn)題如50個(gè)訂單10個(gè)騎手精確算法如分支定界在有限比賽時(shí)間內(nèi)基本無(wú)法求得最優(yōu)解因此必須依賴(lài)啟發(fā)式或元啟發(fā)式算法。3. 算法選型與設(shè)計(jì)在“最優(yōu)”與“可行”之間尋找平衡明確了模型接下來(lái)就是選擇“武器”。我們調(diào)研了熱詞中提到的多種算法并進(jìn)行了組合與改進(jìn)。3.1 核心算法框架大規(guī)模鄰域搜索LNS為主干我們最終沒(méi)有采用單一的蟻群、遺傳或鯨魚(yú)算法而是選擇了大規(guī)模鄰域搜索LNS作為主框架。原因在于VRP問(wèn)題中解的優(yōu)劣往往取決于幾個(gè)關(guān)鍵的局部結(jié)構(gòu)。LNS通過(guò)“破壞”和“修復(fù)”兩個(gè)階段迭代改進(jìn)解非常靈活。破壞Destroy隨機(jī)從當(dāng)前解中移除一定比例如20%-30%的訂單。我們?cè)O(shè)計(jì)了多種破壞算子隨機(jī)移除簡(jiǎn)單隨機(jī)選擇訂單移除。最差成本移除計(jì)算每個(gè)訂單對(duì)總成本的邊際貢獻(xiàn)移除貢獻(xiàn)最負(fù)即移除后成本下降最多的訂單。這能引導(dǎo)搜索跳出局部最優(yōu)。時(shí)間窗緊迫度移除優(yōu)先移除那些時(shí)間窗最緊迫即將超時(shí)的訂單為后續(xù)重新安排留出空間。修復(fù)Repair將移除的訂單重新插入到當(dāng)前部分解中。這里我們采用了貪婪插入和后悔值插入兩種策略。貪婪插入對(duì)于每個(gè)待插入訂單遍歷所有騎手路徑的所有可能插入位置選擇使目標(biāo)函數(shù)增加最小的位置進(jìn)行插入。后悔值插入這是關(guān)鍵技巧。不是看最優(yōu)插入位置的成本而是計(jì)算每個(gè)訂單的“第二好”插入位置與“最好”插入位置的成本差即后悔值。優(yōu)先插入后悔值最大的訂單因?yàn)槿绻F(xiàn)在不把它插到最好的位置后續(xù)可能被迫插到更差的位置代價(jià)更高。LNS框架的優(yōu)勢(shì)在于破壞和修復(fù)算子可以像樂(lè)高積木一樣自由組合和擴(kuò)展方便我們?nèi)谌肫渌惴ǖ乃枷搿?.2 嵌入智能優(yōu)化算法進(jìn)行初始解生成與局部增強(qiáng)單純的LNS需要一個(gè)不錯(cuò)的初始解并且其搜索能力有時(shí)會(huì)陷入平臺(tái)期。我們引入了熱詞中提到的兩種算法進(jìn)行增強(qiáng)初始解生成改進(jìn)的鯨魚(yú)優(yōu)化算法WOA標(biāo)準(zhǔn)的WOA模擬鯨魚(yú)氣泡網(wǎng)捕食行為在連續(xù)空間搜索能力強(qiáng)。但我們的問(wèn)題解是離散的路徑序列。我們對(duì)其進(jìn)行了離散化改造編碼采用“顧客-騎手”關(guān)聯(lián)編碼。一個(gè)鯨魚(yú)個(gè)體解表示為一個(gè)列表列表長(zhǎng)度等于訂單數(shù)每個(gè)位置的值表示負(fù)責(zé)該訂單的騎手編號(hào)。至于訂單在騎手路徑中的具體順序則通過(guò)一個(gè)簡(jiǎn)單的最近鄰插入法根據(jù)這個(gè)分配關(guān)系來(lái)生成。位置更新離散化WOA中鯨魚(yú)的位置更新公式會(huì)產(chǎn)生連續(xù)值。我們通過(guò)一個(gè)隨機(jī)鍵Random Key策略將其離散化。例如將連續(xù)的位置值通過(guò)排序映射到騎手編號(hào)的排列上。作用改進(jìn)的離散WOA被用來(lái)快速生成一批多樣化的初始解種群然后從中選擇最好的一個(gè)作為L(zhǎng)NS的起點(diǎn)。這比完全隨機(jī)生成初始解質(zhì)量高得多。局部搜索變鄰域搜索VNS作為修復(fù)后的增強(qiáng)在LNS的修復(fù)階段得到一個(gè)完整新解后我們并不直接接受它而是以這個(gè)新解為起點(diǎn)進(jìn)行一輪快速的變鄰域搜索VNS在局部尋找更優(yōu)解。鄰域結(jié)構(gòu)我們?cè)O(shè)計(jì)了多種小規(guī)模鄰域操作如2-opt反轉(zhuǎn)路徑中的一段。Relocate將一個(gè)訂單從一條路徑的一個(gè)位置移到同一條或另一條路徑的另一個(gè)位置。Exchange交換兩條路徑中的兩個(gè)訂單。搜索策略依次嘗試這些鄰域結(jié)構(gòu)一旦某個(gè)結(jié)構(gòu)找到了改進(jìn)解就移動(dòng)到新解并從頭開(kāi)始如果所有結(jié)構(gòu)都嘗試完仍無(wú)改進(jìn)則跳出。這樣我們的算法就形成了一個(gè)“改進(jìn)WOA生成初始解 → LNS主循環(huán)破壞修復(fù)→ 內(nèi)嵌VNS局部爬坡”的三層混合架構(gòu)。LNS負(fù)責(zé)大范圍的“探索”VNS負(fù)責(zé)精細(xì)的“挖掘”WOA則提供了高質(zhì)量的起點(diǎn)。3.3 動(dòng)態(tài)事件的處理機(jī)制題目隱含了動(dòng)態(tài)性新訂單實(shí)時(shí)涌入。我們的處理方法是周期性重優(yōu)化。系統(tǒng)內(nèi)部維護(hù)一個(gè)時(shí)鐘和事件隊(duì)列。每過(guò)固定的時(shí)間間隔如5分鐘或當(dāng)新訂單積累到一定數(shù)量時(shí)觸發(fā)一次重優(yōu)化。重優(yōu)化時(shí)輸入包括所有尚未完成的訂單包括正在配送途中的、所有騎手的當(dāng)前位置和狀態(tài)攜帶哪些訂單、當(dāng)前路徑。將騎手的當(dāng)前位置視為新的“虛擬配送站”將已攜帶但未送達(dá)的訂單視為必須服務(wù)的點(diǎn)然后調(diào)用上述混合算法重新規(guī)劃所有騎手從當(dāng)前時(shí)刻往后的路徑。將新的路徑下發(fā)給騎手在模型中模擬。這種方法在比賽中是可行的它平衡了實(shí)時(shí)性和最優(yōu)性。在實(shí)際系統(tǒng)中這可能就是后臺(tái)調(diào)度引擎每隔幾十秒到幾分鐘執(zhí)行一次的邏輯。4. 編程實(shí)現(xiàn)與仿真環(huán)境搭建模型和算法是大腦程序就是手腳。我們用Python來(lái)實(shí)現(xiàn)因?yàn)槠鋷?kù)豐富適合快速原型開(kāi)發(fā)。4.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)清晰的數(shù)據(jù)結(jié)構(gòu)是復(fù)雜程序的基礎(chǔ)。class Order: def __init__(self, id, merchant_loc, customer_loc, prep_time, ready_time, due_time, weight): self.id id self.merchant merchant_loc # (x, y) self.customer customer_loc # (x, y) self.prep_time prep_time # 備餐時(shí)間分鐘 self.ready_time ready_time # 預(yù)計(jì)備餐完成時(shí)間 self.due_time due_time # 期望送達(dá)時(shí)間 self.weight weight class Rider: def __init__(self, id, start_loc, capacity, speed): self.id id self.location start_loc self.capacity capacity self.speed speed # 米/分鐘 self.route [] # 路徑列表元素為 (node_type, node_id, arrive_time, depart_time) self.load 0 # 當(dāng)前負(fù)載 self.current_orders [] # 當(dāng)前攜帶的訂單ID class Solution: def __init__(self): self.rider_assignments {} # rider_id - list of order_ids (按取送順序) self.total_cost float(inf) # 可以緩存一些中間計(jì)算結(jié)果如時(shí)間矩陣、距離矩陣4.2 關(guān)鍵模塊實(shí)現(xiàn)1. 時(shí)間矩陣計(jì)算模塊這是整個(gè)仿真的基石。我們不能每次計(jì)算兩點(diǎn)間時(shí)間都去調(diào)用路徑規(guī)劃API比賽中也不允許。我們采用了簡(jiǎn)化方法預(yù)先根據(jù)路網(wǎng)節(jié)點(diǎn)商家、顧客點(diǎn)的經(jīng)緯度計(jì)算直線(xiàn)距離。根據(jù)道路類(lèi)型和時(shí)段賦予一個(gè)速度折減系數(shù)和繞路系數(shù)。例如直線(xiàn)距離乘以1.3作為實(shí)際騎行距離再根據(jù)高峰/平峰除以不同的速度得到行程時(shí)間。將結(jié)果存儲(chǔ)在一個(gè)二維數(shù)組時(shí)間矩陣中并假設(shè)在同一個(gè)調(diào)度周期內(nèi)是固定的。2. 目標(biāo)函數(shù)評(píng)估模塊這個(gè)函數(shù)會(huì)被調(diào)用成千上萬(wàn)次必須高效。def evaluate_solution(solution, orders, riders, time_matrix, current_time): total_cost 0.0 total_distance 0.0 total_delay 0.0 for rider_id, order_seq in solution.rider_assignments.items(): rider riders[rider_id] current_loc rider.location current_time_for_rider current_time current_load 0 for order_id in order_seq: order orders[order_id] # 去商家 travel_time_to_merchant time_matrix[current_loc][order.merchant] arrive_at_merchant current_time_for_rider travel_time_to_merchant # 等待取餐如果提前到了 wait_at_merchant max(0, order.ready_time - arrive_at_merchant) depart_from_merchant arrive_at_merchant wait_at_merchant 1 # 1分鐘取餐操作 current_load order.weight # 檢查容量約束 if current_load rider.capacity: return float(inf) # 違反硬約束返回?zé)o窮大成本 # 去顧客 travel_time_to_customer time_matrix[order.merchant][order.customer] arrive_at_customer depart_from_merchant travel_time_to_customer # 計(jì)算延遲 delay max(0, arrive_at_customer - order.due_time) total_delay delay ** 2 # 平方懲罰 depart_from_customer arrive_at_customer 1 # 1分鐘送餐操作 current_load - order.weight total_distance (travel_time_to_merchant travel_time_to_customer) * rider.speed current_loc order.customer current_time_for_rider depart_from_customer # 騎手最后返回配送站可選 # ... 計(jì)算返回行程并加入總距離 total_cost w1 * (current_time_for_rider - current_time) w2 * total_distance w3 * total_delay return total_cost實(shí)操心得評(píng)估函數(shù)中對(duì)硬約束如容量超限的處理直接返回一個(gè)極大的懲罰值如float(inf)可以有效地引導(dǎo)搜索算法自動(dòng)避開(kāi)不可行解區(qū)域比用復(fù)雜的約束處理邏輯更簡(jiǎn)潔高效。3. LNS破壞與修復(fù)算子實(shí)現(xiàn)以“最差成本移除”和“后悔值插入”為例。def worst_cost_removal(current_solution, orders, riders, num_remove): 移除對(duì)當(dāng)前解成本貢獻(xiàn)最負(fù)的num_remove個(gè)訂單 order_marginal_cost {} for order_id, order in orders.items(): if order_id in current_solution.assigned_orders: # 計(jì)算移除該訂單前后的成本差 cost_with evaluate_solution(current_solution, ...) # 臨時(shí)創(chuàng)建一個(gè)移除該訂單后的新解需要深拷貝并調(diào)整路徑 temp_solution remove_order_from_solution(current_solution, order_id) cost_without evaluate_solution(temp_solution, ...) marginal_cost cost_without - cost_with # 如果為負(fù)說(shuō)明移除它成本降低 order_marginal_cost[order_id] marginal_cost # 按邊際成本排序從最負(fù)到最正選擇最負(fù)的前num_remove個(gè)訂單移除 orders_to_remove sorted(order_marginal_cost, keyorder_marginal_cost.get)[:num_remove] return orders_to_remove def regret_insertion(partial_solution, orders_to_insert, orders, riders): 使用后悔值啟發(fā)式插入訂單 uninserted orders_to_insert.copy() while uninserted: regrets {} for order_id in uninserted: best_cost float(inf) second_best_cost float(inf) best_position None # 遍歷所有騎手和所有可能插入位置考慮取送配對(duì) for rider_id, rider in riders.items(): # 生成該訂單所有可能的插入位置在現(xiàn)有路徑中插入商家點(diǎn)和顧客點(diǎn) possible_positions generate_insertion_positions(partial_solution, rider_id, order_id) for pos in possible_positions: temp_solution insert_order_at_position(partial_solution, rider_id, order_id, pos) cost evaluate_solution(temp_solution, ...) if cost best_cost: second_best_cost best_cost best_cost cost best_position (rider_id, pos) elif cost second_best_cost: second_best_cost cost # 計(jì)算后悔值 regret second_best_cost - best_cost regrets[order_id] (regret, best_position) # 選擇后悔值最大的訂單進(jìn)行插入 order_to_insert max(regrets, keylambda k: regrets[k][0]) rider_id, pos regrets[order_to_insert][1] partial_solution insert_order_at_position(partial_solution, rider_id, order_to_insert, pos) uninserted.remove(order_to_insert) return partial_solution4.3 仿真循環(huán)與可視化我們搭建了一個(gè)簡(jiǎn)單的離散事件仿真循環(huán)來(lái)模擬時(shí)間推進(jìn)和新訂單到達(dá)。import matplotlib.pyplot as plt def simulation(start_time, end_time, order_stream, riders): current_time start_time current_orders [] solution initial_solution(riders) # 初始為空解 event_log [] while current_time end_time: # 1. 接收新訂單 new_orders get_new_orders(order_stream, current_time) current_orders.extend(new_orders) # 2. 判斷是否觸發(fā)重優(yōu)化例如每5分鐘或新訂單超過(guò)5個(gè) if should_reoptimize(current_time, len(new_orders)): # 3. 調(diào)用混合優(yōu)化算法輸入當(dāng)前騎手狀態(tài)和所有未完成訂單 new_solution hybrid_optimization_algorithm(current_orders, riders, current_time) if new_solution.total_cost solution.total_cost: solution new_solution # 4. 更新騎手路徑在仿真中就是更新route列表 dispatch_solution_to_riders(solution, riders) # 5. 推進(jìn)時(shí)間模擬騎手移動(dòng)和訂單完成 current_time TIME_STEP update_rider_positions(riders, TIME_STEP) completed check_order_completion(riders, current_time) for order_id in completed: remove_order_from_current_list(current_orders, order_id) event_log.append((current_time, delivered, order_id)) # 6. 記錄數(shù)據(jù)用于分析 record_metrics(current_time, riders, current_orders) # 仿真結(jié)束輸出統(tǒng)計(jì)結(jié)果和可視化 print_statistics(event_log) plot_rider_routes(riders, orders)可視化部分我們用matplotlib繪制了騎手路徑的動(dòng)畫(huà)直觀展示隨著時(shí)間推移騎手們?nèi)绾未┧笕∷筒?。靜態(tài)圖則可以展示最終所有騎手的路徑和訂單分布以及目標(biāo)函數(shù)收斂曲線(xiàn)。5. 參數(shù)調(diào)優(yōu)、結(jié)果分析與論文寫(xiě)作要點(diǎn)算法跑起來(lái)只是第一步調(diào)參和結(jié)果分析才是拉開(kāi)差距的地方。5.1 關(guān)鍵參數(shù)敏感性分析我們的混合算法中有多個(gè)參數(shù)需要調(diào)整權(quán)重系數(shù) (w1, w2, w3)這直接決定了優(yōu)化導(dǎo)向。我們通過(guò)網(wǎng)格搜索并觀察不同權(quán)重下解的帕累托前沿Pareto Front最終選擇了一組在總時(shí)長(zhǎng)、總距離和超時(shí)率上相對(duì)均衡的權(quán)重例如 0.5, 0.2, 0.3。LNS破壞比例破壞比例太大搜索隨機(jī)性強(qiáng)收斂慢太小跳出局部最優(yōu)能力弱。我們通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)在20%-35%之間效果較好并采用了自適應(yīng)策略如果連續(xù)多次迭代沒(méi)有改進(jìn)則增大破壞比例。改進(jìn)WOA的參數(shù)種群大小、迭代次數(shù)。由于WOA只用于生成初始解我們不需要它完全收斂因此種群大小設(shè)為20-50迭代次數(shù)50-100次即可重在多樣性。VNS的鄰域搜索深度我們?yōu)槊總€(gè)鄰域操作設(shè)置了最大嘗試次數(shù)如100次避免在局部搜索中花費(fèi)過(guò)多時(shí)間。踩坑實(shí)錄最初我們沒(méi)做參數(shù)敏感性分析隨便設(shè)了一組值。結(jié)果算法要么瘋狂追求最短路徑導(dǎo)致嚴(yán)重超時(shí)要么為了不超時(shí)讓騎手跑了很多冤枉路。后來(lái)我們固定其他參數(shù)每次只調(diào)一個(gè)觀察目標(biāo)函數(shù)各分量的變化并繪制了趨勢(shì)圖才找到了相對(duì)合理的參數(shù)組合。這個(gè)過(guò)程在論文中可以作為“模型穩(wěn)健性分析”的一部分來(lái)寫(xiě)非常加分。5.2 結(jié)果對(duì)比與有效性驗(yàn)證為了證明我們模型和算法的有效性我們?cè)O(shè)計(jì)了對(duì)比實(shí)驗(yàn)基準(zhǔn)策略最近鄰策略騎手總是前往距離當(dāng)前位置最近的未完成訂單點(diǎn)。先到先得策略訂單按產(chǎn)生時(shí)間分配給最近的空閑騎手騎手按訂單順序執(zhí)行。消融實(shí)驗(yàn)僅LNS不使用WOA生成初始解也不在修復(fù)后使用VNS。LNS VNS使用隨機(jī)初始解但修復(fù)后使用VNS。完整混合算法我們的最終方案。評(píng)價(jià)指標(biāo)除了總成本Z我們還單獨(dú)統(tǒng)計(jì)了訂單平均送達(dá)時(shí)間、騎手總行駛里程、訂單超時(shí)率、超時(shí)訂單平均超時(shí)時(shí)長(zhǎng)。實(shí)驗(yàn)結(jié)果用表格呈現(xiàn)最為清晰策略總成本 (Z)平均送達(dá)時(shí)間(分鐘)總行駛里程(km)超時(shí)率算法運(yùn)行時(shí)間(秒)最近鄰1520.538.2145.325%1先到先得1380.735.8132.118%1僅LNS980.328.5108.78%45LNSVNS865.426.199.45%68混合算法(本文)795.824.795.23%82從表格可以明顯看出我們的混合算法在各項(xiàng)配送效率指標(biāo)上均顯著優(yōu)于基準(zhǔn)策略。消融實(shí)驗(yàn)則證明了WOA提供優(yōu)質(zhì)初始解和VNS進(jìn)行局部增強(qiáng)的有效性雖然增加了些許計(jì)算時(shí)間但帶來(lái)的效益提升是值得的。5.3 論文寫(xiě)作的核心技巧數(shù)學(xué)建模競(jìng)賽論文是最終交付物。編程和求解只是過(guò)程。摘要用一段話(huà)概括問(wèn)題、你的方法、模型、算法和核心結(jié)論。務(wù)必包含關(guān)鍵數(shù)據(jù)如“相比基準(zhǔn)策略總成本降低了42%超時(shí)率降低了22個(gè)百分點(diǎn)”。問(wèn)題重述與分析不要照抄題目要用自己的話(huà)分析問(wèn)題的本質(zhì)、難點(diǎn)和關(guān)鍵約束。畫(huà)出概念圖如騎手、訂單、路網(wǎng)的關(guān)系圖。模型假設(shè)清晰列出并說(shuō)明為什么合理。這是體現(xiàn)你思考深度的部分。模型建立公式要完整、規(guī)范。對(duì)每個(gè)符號(hào)進(jìn)行說(shuō)明。目標(biāo)函數(shù)和約束條件要分點(diǎn)闡述。算法設(shè)計(jì)這是亮點(diǎn)。用流程圖可以手繪拍照展示算法框架。詳細(xì)說(shuō)明LNS、改進(jìn)WOA、VNS是如何結(jié)合在一起的。偽代碼不要太多挑核心的寫(xiě)1-2個(gè)。仿真與結(jié)果分析展示參數(shù)設(shè)置。用表格和圖表折線(xiàn)圖、柱狀圖、路徑示意圖多維度呈現(xiàn)結(jié)果。分析要深入比如“超時(shí)率從25%降到3%主要得益于后悔值插入算法優(yōu)先處理了時(shí)間窗緊迫的訂單”。模型評(píng)價(jià)與推廣客觀評(píng)價(jià)自己模型的優(yōu)點(diǎn)如高效、靈活和缺點(diǎn)如對(duì)歷史數(shù)據(jù)依賴(lài)、未考慮極端天氣。提出改進(jìn)方向如接入實(shí)時(shí)交通API引入機(jī)器學(xué)習(xí)預(yù)測(cè)備餐時(shí)間。說(shuō)明模型可以推廣到其他即時(shí)配送場(chǎng)景如快遞、生鮮配送。附錄與代碼將核心代碼如評(píng)估函數(shù)、LNS主循環(huán)整理后放入附錄。代碼要簡(jiǎn)潔有必要的注釋。最后在提交前一定要反復(fù)檢查論文的排版、圖表編號(hào)、公式編號(hào)、參考文獻(xiàn)引用。一篇排版精美、邏輯清晰、結(jié)果扎實(shí)的論文是獲得好名次的基石。我們的程序可能不是最快的算法也不是最前沿的但整個(gè)解決過(guò)程體現(xiàn)出的系統(tǒng)思維、對(duì)細(xì)節(jié)的考量以及清晰的表述才是數(shù)維杯這類(lèi)競(jìng)賽真正看重的。