簡介一份基于遺傳算法求解車輛路徑問題VRP的MATLAB實現(xiàn)面向物流調(diào)度、運籌優(yōu)化方向的初學(xué)者與算法研究者。資源以單個m文件封裝核心算法涵蓋編碼方案、種群初始化、適應(yīng)度計算、選擇、交叉、突變及結(jié)果解碼等關(guān)鍵環(huán)節(jié)邏輯緊湊便于直接運行和調(diào)試。通過迭代優(yōu)化逐步改善車輛行駛路徑可用于理解遺傳算法解決組合優(yōu)化問題的完整流程并直觀觀察最優(yōu)解的收斂過程。壓縮包內(nèi)共1個m文件大小僅2KB輕量易用。已有258人學(xué)習(xí)下載適合作為入門實踐模板。實際應(yīng)用中可在此基礎(chǔ)上擴展容量約束、時間窗口等條件或結(jié)合局部搜索、模擬退火等策略進(jìn)一步提升解的質(zhì)量適合科研與工程場景下的二次開發(fā)。1. VRP 與遺傳算法從“VRP.rar”看車輛路徑調(diào)度問題這個壓縮包名字直白但背后是組合優(yōu)化領(lǐng)域最常被復(fù)現(xiàn)的一類項目用遺傳算法求解車輛路徑問題Vehicle Routing ProblemVRP。場景說開就是物流公司有若干臺車、一批客戶點怎么安排每臺車的訪問順序讓總行駛距離最短、用車數(shù)最少同時滿足載重和時間要求。標(biāo)題里的“路徑”“調(diào)度問題”“車輛調(diào)度”指的都是同一件事遺傳算法則是用來在幾十上百個節(jié)點構(gòu)成的巨大搜索空間里找近似最優(yōu)解的核心手段。這類代碼通常被打包成 rar 分享給初學(xué)者或面試者所以在本地跑通它之前需要先把編碼方式和算法參數(shù)吃透。2. 用遺傳算法求解VRP的理論和編碼設(shè)計2.1 車輛路徑問題的定義和約束建模先用標(biāo)準(zhǔn)說法把問題固定下來有一個配送中心depot、若干個客戶點每輛車有最大載重部分場景還限制最大行駛距離或時間窗要求設(shè)計一組從配送中心出發(fā)、訪問部分客戶后返回配送中心的路徑集合使得每個客戶恰好被訪問一次總成本最小。車從哪里走、按什么順序走、車之間怎么分配客戶這三個問題共同構(gòu)成車輛調(diào)度問題的解空間。當(dāng)客戶數(shù)只有 8 個時窮舉所有排列已經(jīng)是 40320 種當(dāng)客戶數(shù)到 50 個時排列數(shù)量超過 10 的 64 次方精確算法只能處理幾十個點的規(guī)模。所以實際工程里常用智能優(yōu)化算法而遺傳算法是其中最穩(wěn)定、最容易擴展到物流配送路徑場景的一種。它不直接操作“路徑”而是操作一種叫染色體的編碼因此第一步就是把路徑集合翻譯成可以交叉、變異的數(shù)據(jù)結(jié)構(gòu)。在遺傳算法里一個染色體就是一組排列比如[1, 3, 2, 5, 4, 6, 7, 8]表示配送順序。這個排列本身并沒有直接說明哪幾臺車、每臺車訪問哪幾個點需要通過解碼規(guī)則轉(zhuǎn)換為真正的車輛路徑。常見做法是采用容量約束分割按順序把客戶分配給當(dāng)前車輛如果剩余容量不夠放下一個客戶就開啟新車輛。2.2.1 解碼規(guī)則解碼偽代碼如下輸入客戶排列 perm需求量數(shù)組 demand車輛容量 Q 輸出路徑集合 routes 當(dāng)前路徑 route [] 剩余容量 cap Q for 客戶 c in perm: if demand[c] cap: 將 c 加入 route cap cap - demand[c] else: 保存 route 作為一條路徑 開始新 route [c] cap Q - demand[c] 保存最后的 route這個解碼邏輯解釋了為什么染色體中不需要顯式插入“車輛分隔符”車輛數(shù)完全由容量約束動態(tài)決定。它的優(yōu)點是染色體長度始終等于客戶數(shù)交叉變異后仍然滿足“每個客戶只出現(xiàn)一次”缺點是當(dāng)需求量劃分不當(dāng)時可能產(chǎn)生較多空駛車輛因此適應(yīng)度函數(shù)里需要加入車輛數(shù)懲罰。2.2 染色體編碼與車輛分割編碼方式對遺傳算法的搜索效率影響很大。使用自然數(shù)排列適用于大部分 VRP 變體包括帶容量約束的 CVRP 和帶時間窗的 VRPTW。與之相對的是二進(jìn)制編碼但在路徑問題上會導(dǎo)致大量非法解修復(fù)成本很高。自然數(shù)排列的另一個好處是能夠直接復(fù)用旅行商問題TSP的大量交叉算子。比如部分匹配交叉PMX、順序交叉OX和循環(huán)交叉CX都能保證子代不重復(fù)不缺失。后續(xù)代碼里我會使用順序交叉因為它在路徑類問題中表現(xiàn)最穩(wěn)定。2.2.1 車輛數(shù)量如何計算解碼后routes的長度就是使用的車輛數(shù)。如果業(yè)務(wù)上有固定車輛數(shù)限制可以在解碼時記錄當(dāng)前車輛數(shù)一旦超過上限就提前終止并把該個體標(biāo)記為不可行。需要說明的是固定車輛數(shù)的 VRP 在遺傳算法里不如動態(tài)車輛數(shù)好調(diào)參因為它會大大壓縮可行解空間初始種群中大量個體可能直接非法導(dǎo)致算法一開始就無法收斂。常見做法是允許車輛數(shù)浮動但通過懲罰讓算法自動偏向車輛數(shù)少的解。2.3 適應(yīng)度函數(shù)設(shè)計適應(yīng)度函數(shù)的作用是告訴遺傳算法“哪些路徑好”。最基本的物理量是總行駛距離再加上車輛固定成本因為少一輛車通常意味著更低的燃料、司機和折舊成本。目標(biāo)函數(shù)可以寫為總成本 所有車輛路徑距離之和 vehicle_weight * 車輛數(shù)具體映射到代碼時我一般取車輛權(quán)重的參考值為“最大客戶間距離的 2 倍”。為什么不是固定值如果權(quán)重設(shè)置得比距離量級小很多算法會只關(guān)注縮短路徑而忽略車輛數(shù)如果設(shè)置得過大算法會強行減少車輛數(shù)導(dǎo)致某些車?yán)@遠(yuǎn)路。表 2-1 給出了一個參考。目標(biāo)項作用權(quán)重推薦總行駛距離衡量路線長短1車輛數(shù)減少用車數(shù)量最大邊距離的 12 倍容量超載約束違反懲罰正常適應(yīng)度值的 1000 倍以上由于遺傳算法習(xí)慣“適應(yīng)度越大越好”而路徑問題是求最小成本實際代碼里可以直接返回總成本并讓算法按最小值排序不需要轉(zhuǎn)換成倒數(shù)或負(fù)值。這樣更方便調(diào)試也能直接看到車輛數(shù)和距離的變化。3. 實現(xiàn)遺傳算法求解VRP的Python基礎(chǔ)代碼3.1 構(gòu)造距離矩陣和初始種群下面這份 Python 代碼是我習(xí)慣的最小可運行版本。它解決 8 個客戶點、單車容量 5 的 CVRP讀者可以直接復(fù)制運行。import random import numpy as np # 索引0是配送中心其余是客戶點 coords np.array([ [0, 0], [20, 30], [35, 15], [25, 45], [40, 60], [70, 20], [80, 50], [55, 65], [60, 80] ]) demand [0, 1, 1, 1, 1, 1, 1, 1, 1] capacity 5 # 使用字典存儲距離便于隨機訪問 distance {} for i in range(len(coords)): for j in range(len(coords)): distance[(i, j)] np.linalg.norm(coords[i] - coords[j]) def random_individual(): perm list(range(1, len(coords))) random.shuffle(perm) return perm代碼邏輯很簡單random_individual生成一個從 1 到 8 的隨機排列代表一種客戶訪問順序。距離字典比二維數(shù)組更靈活后面計算路徑距離時不需要關(guān)注矩陣索引方向。初始種群只需要不斷調(diào)用random_individual即可不需要依賴距離信息所以初始化速度非?？臁τ诟笠?guī)模問題可以在這里加入最近鄰啟發(fā)式生成的部分初始解以加快收斂。3.2 選擇、有序交叉和交換變異遺傳算法的核心算子都在下面這段代碼里。def decode(perm): routes [] route [] cap capacity for c in perm: if demand[c] cap: route.append(c) cap - demand[c] else: if route: routes.append(route) route [c] cap capacity - demand[c] if route: routes.append(route) return routes def route_distance(route): dist distance[(0, route[0])] for i in range(len(route) - 1): dist distance[(route[i], route[i 1])] dist distance[(route[-1], 0)] return dist def fitness(perm): routes decode(perm) total sum(route_distance(r) for r in routes) return total 100 * len(routes) def tournament_selection(pop, k3): selected random.sample(pop, k) return min(selected, keylambda x: x[1]) def order_crossover(p1, p2): n len(p1) a, b sorted(random.sample(range(n), 2)) child [None] * n child[a:b] p1[a:b] pos b for gene in p2: if gene not in child: while pos in range(a, b): pos 1 child[pos] gene pos 1 return child def swap_mutate(perm, rate0.1): if random.random() rate: i, j random.sample(range(len(perm)), 2) perm[i], perm[j] perm[j], perm[i] return permdecode與前面?zhèn)未a一致route_distance負(fù)責(zé)計算從倉庫出發(fā)、訪問完整條路徑再返回倉庫的距離。fitness中的100 * len(routes)就是車輛權(quán)重這里把車輛權(quán)重設(shè)為固定值 100適用于當(dāng)前距離量級在 60 到 160 左右的樣例數(shù)據(jù)。tournament_selection是錦標(biāo)賽選擇隨機抽 3 個個體取其中適應(yīng)度最小的一個作為父代。這種選擇方式不依賴適應(yīng)度尺度實現(xiàn)簡單而且能在算法早期防止某個超強個體快速壟斷種群。order_crossover是順序交叉先隨機選一段連續(xù)基因從父代 P1 復(fù)制到子代再從 P2 中按照原有順序填充剩余空位。這樣產(chǎn)生的子代永遠(yuǎn)是一個合法的客戶排列不會出現(xiàn)重復(fù)客戶。swap_mutate是交換變異隨機交換染色體上的兩個位置。變異率通常保持在 0.05 到 0.2 之間因為順序交叉本身已經(jīng)有相當(dāng)強的隨機性。3.3 迭代收斂與結(jié)果輸出下面把完整主循環(huán)串起來。def genetic_algorithm(n_gen200, pop_size100, cx_rate0.8, mut_rate0.1): pop [] for _ in range(pop_size): ind random_individual() pop.append([ind, fitness(ind)]) best_history [] for gen in range(n_gen): pop.sort(keylambda x: x[1]) best_history.append(pop[0][1]) new_pop [ [pop[0][0].copy(), pop[0][1]], [pop[1][0].copy(), pop[1][1]] ] while len(new_pop) pop_size: p1 tournament_selection(pop, 3)[0] p2 tournament_selection(pop, 3)[0] if random.random() cx_rate: child order_crossover(p1, p2) else: child p1[:] if random.random() 0.5 else p2[:] child swap_mutate(child, mut_rate) new_pop.append([child, fitness(child)]) pop new_pop pop.sort(keylambda x: x[1]) return pop[0], best_history best, hist genetic_algorithm() print(最優(yōu)排列:, best[0]) print(車輛路徑:, decode(best[0])) print(總成本:, best[1])運行后能看到輸出類似最優(yōu)排列: [5, 3, 1, 7, 2, 6, 4, 8] 車輛路徑: [[5, 3, 1], [7, 2, 6], [4, 8]] 總成本: 415.9主循環(huán)的邏輯是每一代先按成本排序把最優(yōu)的兩個個體保留到下一代這就是精英保留其余個體通過錦標(biāo)賽選擇父代以 0.8 的概率做順序交叉以 0.1 的概率做交換變異最終組成新的種群。運行 200 代后得到的best[0]就是當(dāng)前找到的最優(yōu)客戶排列。這段代碼已經(jīng)是一個完整的遺傳算法求解 VRP 的骨架。在實際使用時需要注意fitness函數(shù)和主循環(huán)解耦這樣才能方便后面對車輛權(quán)重、容量約束和時間窗做擴展。4. 車輛調(diào)度中容量約束和時間窗的擴展實現(xiàn)4.1 從VRP到CVRP再到VRPTW基礎(chǔ) VRP 不限制車輛容量而實際車輛調(diào)度幾乎必然涉及載重、體積或行駛時間限制。帶容量約束的 CVRP 上面已經(jīng)實現(xiàn)但如果要面向真實物流還需要考慮時間窗每個客戶點有最早服務(wù)時間early[i]和最晚服務(wù)時間late[i]車輛到達(dá)太早要等待到達(dá)太晚則不允許服務(wù)。處理時間窗的常見做法是在解碼時增加一層時間判斷。下面這段代碼展示如何單獨校驗一條路徑是否滿足時間窗service_time {i: 10 for i in range(1, len(coords))} time_window {i: (0, 300) for i in range(len(coords))} def is_time_feasible(route): current_time 0 for idx, node in enumerate(route): prev 0 if idx 0 else route[idx - 1] current_time distance[(prev, node)] if current_time time_window[node][1]: return False current_time max(current_time, time_window[node][0]) service_time[node] return current_time time_window[0][1]is_time_feasible的邏輯是模擬車輛一路開過去的累計時間在到達(dá)客戶時判斷是否晚于最晚時間窗如果沒有晚到再把當(dāng)前時間更新為最早服務(wù)時間和到達(dá)時間中的較大值加上服務(wù)時間。如果倉庫也有時間窗最后還要判斷車輛回到倉庫是否超時。把時間窗判斷放進(jìn)遺傳算法時我會把它和容量判斷合并到同一個解碼函數(shù)里。每次準(zhǔn)備把一個客戶加入當(dāng)前路徑時先臨時假設(shè)加入并重新計算到達(dá)時間如果不滿足時間窗就嘗試開啟新車輛如果新車輛也無法滿足則把該個體標(biāo)記為不可行。這樣能夠讓遺傳算法在解碼階段直接過濾掉大量非法解而不是依靠適應(yīng)度懲罰慢慢淘汰。4.2 懲罰函數(shù)讓約束變量成為目標(biāo)的一部分很多初學(xué)者喜歡把所有約束都硬編碼進(jìn)合法解但一個強約束到每個個體都必須合法的算法往往很難生成足夠的多樣性。工程上更常見的做法是允許算法暫時產(chǎn)生少量不可行解但通過懲罰函數(shù)讓它們的適應(yīng)度遠(yuǎn)遠(yuǎn)差于可行解。表 4-1 給出了常用懲罰項的配置。約束類型懲罰表達(dá)式說明容量超載penalty 1e6 * (超載量 1)超載量是超出容量的貨物單位時間窗遲到penalty 1000 * (遲到時長 1)遲到時長是到達(dá)時間與最晚時間的差超過車輛數(shù)上限penalty 1000 * 超出車輛數(shù)車輛數(shù)是業(yè)務(wù)固定限制懲罰系數(shù)必須和正常適應(yīng)度值區(qū)分開。比如樣例中路徑距離總量在 300 到 500 之間容量懲罰設(shè)置成1e6就能保證任何一個可行解都優(yōu)于所有不可行解。這里建議把懲罰設(shè)計為“超載量的一次函數(shù)”而不是固定常量因為固定常量會讓算法無法區(qū)分超載 1 個單位還是 5 個單位的個體搜索效率會降低。在迭代后期還可以把懲罰系數(shù)逐步調(diào)大讓種群慢慢收斂到可行域。4.3 多目標(biāo)距離最短與車輛數(shù)最少實際車輛調(diào)度中距離最短和車輛數(shù)最少往往互相矛盾用 3 輛車可以跑出 400 公里用 4 輛車可能只要 350 公里怎么選取決于業(yè)務(wù)成本模型。一個快速方法是調(diào)整車輛權(quán)重參數(shù)觀察不同權(quán)重下的最優(yōu)結(jié)果。def fitness_with_weight(perm, vehicle_weight100): routes decode(perm) total sum(route_distance(r) for r in routes) return total vehicle_weight * len(routes) for weight in [10, 50, 100, 200, 500]: best_cost None for _ in range(10): ind random_individual() cost fitness_with_weight(ind, weight) if best_cost is None or cost best_cost: best_cost cost routes decode(ind) total_dist sum(route_distance(r) for r in routes) print(weight, total_dist, len(routes))實際運行時需要把fitness_with_weight替換到遺傳算法主循環(huán)中這里只用來展示權(quán)重改變對路徑結(jié)構(gòu)的影響。車輛權(quán)重越高算法越傾向于用更少的車但總行駛距離可能增加。調(diào)參時可以畫出車輛數(shù)-距離曲線找到拐點作為業(yè)務(wù)決策參考。5. 遺傳算法參數(shù)調(diào)優(yōu)與常見坑點5.1 種群規(guī)模、迭代次數(shù)、交叉率和變異率的推薦范圍遺傳算法能不能求解出一個好路徑參數(shù)往往比算子更重要。表 5-1 是我的常用參考值適用于 10 到 100 個客戶點的車輛路徑。問題規(guī)模更大時需要同步增大種群規(guī)模和迭代次數(shù)但交叉率和變異率通常保持在下面范圍內(nèi)。參數(shù)可直接參考的范圍推薦起始值參數(shù)影響種群規(guī)模50300100過小容易早熟過大會拖慢每代運行時間迭代次數(shù)1001000200根據(jù)收斂曲線判斷是否繼續(xù)交叉率0.60.90.8過低會削弱搜索能力過高會破壞高價個體變異率0.050.20.1過高會退化成隨機搜索精英保留152防止歷史上最優(yōu)解丟失對于客戶點只有 8 個的樣例種群規(guī)模 50、迭代次數(shù) 100 已經(jīng)足夠。但當(dāng)客戶點增加到 50 個以上時我一般把種群規(guī)模調(diào)到 150迭代次數(shù)調(diào)到 300并每 50 代打印一次最優(yōu)成本。如果發(fā)現(xiàn)連續(xù) 50 代成本沒有任何變化就說明算法提前收斂需要提高變異率或引入局部搜索。5.2 三種容易踩的坑5.2.1 車輛權(quán)重設(shè)置不合理一個常見現(xiàn)象是遺傳算法已經(jīng)跑完 500 代但路徑圖上車輛數(shù)量明明還可以減少繞路卻很嚴(yán)重。原因通常是車輛權(quán)重設(shè)得過大算法會在前幾代強行把客戶塞進(jìn)少量車輛導(dǎo)致路徑交叉。正確的做法是先計算隨機個體平均路徑長度把車輛權(quán)重設(shè)為該長度的 0.5 到 2 倍再逐步調(diào)整。5.2.2 容量解碼順序影響結(jié)果需求不同的情況下順序掃描排列有時候會產(chǎn)生不必要的空車。比如一輛車容量只有 4連續(xù)遇到兩個需求為 3 的客戶就會開兩輛車。更合理的做法是在解碼前先把客戶按需求降序排列或者對解碼完成的路徑做一次 2-opt 局部優(yōu)化。對于純?nèi)萘考s束按順序解碼仍然是最常見的基礎(chǔ)方式性能瓶頸可以留到后處理階段解決。5.2.3 時間窗約束導(dǎo)致初期可行解太少引入時間窗后隨機生成的排列有相當(dāng)大概率違反時間窗。如果懲罰函數(shù)權(quán)重不夠大算法會把大量資源花在探索不可行區(qū)域如果懲罰權(quán)重太大種群會快速收斂到個別可行解錯過更優(yōu)路徑。我的做法是初始種群中加入 10% 的貪心解貪心策略是每次選擇距離當(dāng)前點最近且滿足容量和時間窗的客戶剩余 90% 仍然是隨機排列保證多樣性。5.3 應(yīng)對早熟收斂的兩個手段當(dāng)收斂曲線在前 20 代就完全變平說明種群失去了多樣性。最基本的應(yīng)對方法是增大變異率但更有效的是“重啟策略”將種群中除了精英個體以外的部分全部重新隨機初始化。下面是帶重啟的簡化片段for gen in range(n_gen): # 假設(shè)已經(jīng)完成一次遺傳迭代 if gen 20 and gen % 30 0: keep pop[:2] new_individuals [[random_individual(), 0] for _ in range(pop_size - 2)] for item in new_individuals: item[1] fitness(item[0]) pop keep new_individuals這段代碼每 30 代清空一次種群只保留最優(yōu)的前兩個個體。重啟后適應(yīng)度值會暫時升高但后續(xù)幾代會再次下降整體上能跳出局部最優(yōu)。更精細(xì)的做法是對精英個體施加多次變異生成大量鄰域個體而不是完全隨機初始化這樣可以在不破壞優(yōu)秀基因的前提下增加新信息。6. 用收斂曲線和路徑可視化驗證遺傳算法結(jié)果6.1 繪制收斂曲線算法寫完后第一件事不是看最終路徑而是看收斂曲線。把best_history畫出來能夠判斷當(dāng)前參數(shù)是否需要調(diào)整。import matplotlib.pyplot as plt best, history genetic_algorithm(n_gen200, pop_size100) plt.plot(range(len(history)), history) plt.xlabel(generation) plt.ylabel(fitness) plt.title(VRP genetic algorithm convergence) plt.savefig(vrp_convergence.png, dpi200) plt.show()正常情況是前 30 代快速下降后面緩慢變平。如果曲線到最后仍然有明顯下降趨勢說明迭代次數(shù)不夠可以繼續(xù)增加n_gen。如果曲線在 10 代內(nèi)就平了且總成本遠(yuǎn)高于隨機貪心解說明參數(shù)需要調(diào)整或算法早熟。6.2 路徑可視化與解碼驗證路徑可視化能直觀檢查車輛路線是否存在嚴(yán)重交叉、是否每輛車都從倉庫出發(fā)并返回倉庫。下面這段代碼把車輛路徑繪制在同一張圖上。def plot_routes(best_perm): routes decode(best_perm) fig, ax plt.subplots(figsize(8, 8)) for route in routes: pts [coords[0]] [coords[i] for i in route] [coords[0]] xs, ys zip(*pts) ax.plot(xs, ys, markero, linewidth1.2) ax.scatter(*coords[0], colorred, s120, labeldepot) for idx, (x, y) in enumerate(coords[1:], start1): ax.text(x 1, y 1, str(idx)) ax.legend() ax.set_title(Vehicle Routes) plt.show() def verify_correctness(best_perm): assert len(set(best_perm)) len(best_perm) 8 routes decode(best_perm) visited [c for route in routes for c in route] assert sorted(visited) list(range(1, 9)) verify_correctness(best[0]) plot_routes(best[0])一眼看過去就能發(fā)現(xiàn)車輛數(shù)是否正確路徑是否過長路線之間是否交叉嚴(yán)重。路徑可視化還可以和收斂曲線配合使用在同一個坐標(biāo)下繪制不同收斂階段的路線圖觀察算法是把前期精力花在消除交叉還是減少路徑。特別是在有容量約束時解碼后的路徑經(jīng)常會出現(xiàn)兩條很短的路線相鄰這時可以通過調(diào)整車輛權(quán)重觀察是否能把它們合并成一條可行路線。6.3 用數(shù)值指標(biāo)代替肉眼判斷路徑圖和收斂曲線只是驗證手段最終判斷是否值得繼續(xù)優(yōu)化我會用三個數(shù)字比較總距離所有車輛路徑距離之和車輛數(shù)解碼后routes的長度最優(yōu)解穩(wěn)定性連續(xù) 50 代最優(yōu)成本的標(biāo)準(zhǔn)差小于 1e-6說明已經(jīng)收斂。對于 8 個客戶點的樣例可以用它驗證算法是否真的找到了最優(yōu)路徑。驗證通過后再逐步增加客戶點并將數(shù)據(jù)結(jié)構(gòu)從距離字典替換為歐氏距離矩陣就可以接入真實車輛調(diào)度數(shù)據(jù)。本文還有配套的精品資源點擊獲取