美團配送算法面試經歷：路徑規劃+運力調度+即時決策全考察

美團配送算法面試經歷：路徑規劃+運力調度+即時決策全考察

先說感受：美團的配送算法面試，是我面過最「接地氣」的算法面試。沒有那種純數學推導的題目，每個問題都和真實的配送場景綁定——騎手怎麼分配、路線怎麼規劃、超時怎麼處理。面試官甚至會直接說「你看我們APP上這個場景」，然後讓你現場分析。這種面試風格讓我覺得特別真實，也特別有挑戰。

背景介紹：2年運籌最佳化經驗，美團配送

我碩士學的是運籌學，畢業後在一家物流科技公司做了2年運籌最佳化算法開發。主要做車輛路徑規劃（VRP）和調度最佳化，用的技術棧是Python+Gurobi+OR-Tools。雖然不是網際網路大廠，但物流場景的最佳化問題其實和配送非常接近，所以面試的時候很多問題我都能結合實際經驗來答。

投美團配送是因為想從物流場景切換到即時配送場景——前者的最佳化目標是成本，後者的最佳化目標是時效，挑戰完全不同。投完簡歷大概3天收到面試通知。

一、面試流程覆盤

一面：運籌學+最佳化理論（約60分鐘）

一面是個做調度算法的大哥，先問了幾個運籌學基礎問題熱身。

「線性規劃的對偶問題是什麼？對偶理論在實際中有什麼用？」我從對偶的定義講起，然後講了影子價格和靈敏度分析的應用。面試官追問：「如果你的模型有幾千個約束，靈敏度分析怎麼做？」我講了基變數和非基變數的分類，以及只對非基變數的係數做靈敏度分析的簡化方法。

然後問整數規劃：「VRP問題為什麼是NP-Hard？常用的求解方法有哪些？」我講了VRP可以規約到TSP，而TSP是NP-Hard。求解方法我分精確算法（分支定界、割平面）和啟發式（遺傳算法、禁忌搜尋、ALNS）兩大類來講。面試官追問：「在實際專案中，你會選精確算法還是啟發式？為什麼？」我講了看問題規模——小規模用精確解，大規模用啟發式，中間規模可以先用啟發式找初始解再用精確解最佳化。

一面還問了一道建模題：「把外賣配送的騎手分配問題建模成數學規劃。」我定義了決策變數（騎手i是否分配訂單j）、目標函數（最小化總配送時間）、約束條件（每個訂單只分配一個騎手、騎手容量約束、時間窗約束）。面試官追問了時間窗約束的軟硬之分，我講了硬時間窗（必須滿足）和軟時間窗（允許違反但有懲罰）的區別和適用場景。

二面：路徑規劃+調度算法（約70分鐘）

二面是個更資深的算法專家，問的問題更偏實際場景。

「美團的配送區域怎麼劃分？一個區域內的騎手怎麼調度？」我講了基於地理圍欄的區域劃分，以及區域內的動態調度策略——新訂單來了先預估配送時間，然後根據騎手當前位置、在途訂單數、預計完成時間來匹配。面試官追問：「如果某個區域突然爆單了怎麼辦？」我講了跨區調度、動態擴容、訂單延遲分配的策略。

然後問路徑規劃：「騎手同時送多單的時候，路線怎麼規劃？和傳統VRP有什麼區別？」我講了配送場景的特殊性：取餐點不同、送餐點不同、有時間窗約束、騎手容量有限。面試官追問：「如果騎手已經取了2單正在送，又來了1單，怎麼決定要不要接？」我講了基於預計完成時間的動態插入啟發式——計算插入新訂單後的增量時間，如果不超過閾值就接受。

二面還問了一個特別實際的問題：「配送ETA（預計到達時間）怎麼估算？」我講了基於歷史數據的統計方法（分位數迴歸）和基於即時特徵的機器學習方法（XGBoost/LightGBM），以及兩者的融合方案。面試官追問了特徵工程，我講了時間特徵（時段、星期）、空間特徵（距離、區域）、商家特徵（出餐時間）、騎手特徵（歷史速度）等。

然後問了一道設計題：「設計一個即時調度系統，要求秒級響應、支援動態訂單和騎手狀態變化。」我講了事件驅動架構——訂單事件觸發重新調度，騎手狀態變化觸發重新匹配。核心是增量調度而不是全域重調度，每次只調整受影響的騎手和訂單。面試官追問了系統延遲和調度品質的權衡，我講了分層調度策略——粗調度（秒級）+精調度（分鐘級）。

三面：專案深挖+系統設計（約50分鐘）

三面是部門負責人，問得更宏觀。

「你做過的最有挑戰的最佳化專案是什麼？」我講了一個冷鏈物流的路徑最佳化專案，約束條件特別多（溫控、時效、車輛類型），模型很難求解。面試官追問了具體的技術方案，我講了用列生成+分支定價的精確方法，以及大規模例項下用ALNS的啟發式方法。

然後問了一個系統設計題：「設計一個配送算法平台，要支援多種調度策略的A/B測試和灰度發布。」我講了策略抽象層（統一介面）、實驗框架（分流、指標收集、顯著性檢驗）、灰度發布（按區域/時段逐步放量）的設計。面試官追問了指標體系，我講了時效指標（準時率、平均配送時長）、成本指標（單均配送成本）、體驗指標（客訴率）。

最後問了職業規劃和對即時配送的看法。我說即時配送是運籌最佳化最好的落地場景之一，因為決策頻率高、數據豐富、效果可量化。面試官很認同，說美團配送每天要做上億次調度決策，算法的每個百分點提升都是巨大的業務價值。

二、真題彙總

1. 線性規劃的對偶問題？對偶理論的實際應用？

2. VRP為什麼是NP-Hard？精確算法vs啟發式怎麼選？

3. 把騎手分配問題建模成數學規劃？

4. 配送區域怎麼劃分？區域內騎手怎麼調度？

5. 區域爆單怎麼辦？跨區調度策略？

6. 多單配送的路線規劃？動態插入新訂單？

7. 配送ETA怎麼估算？特徵工程？

8. 設計即時調度系統？增量調度vs全域重調度？

9. 最有挑戰的最佳化專案？列生成+分支定價？

10. 設計配送算法平台？A/B測試和灰度發布？

11. 調度策略的指標體系？

三、心得建議

1. 運籌基礎要扎實，但更要會建模。面試中純理論的問題不多，更多的是「把這個問題建模成數學規劃」。建議多練習建模能力，看到一個問題能快速定義變數、目標、約束。

2. 啟發式算法是重點。實際場景中問題規模都很大，精確算法基本用不上。遺傳算法、禁忌搜尋、ALNS這些啟發式方法要能講清楚原理和適用場景，最好有實際調參經驗。

3. 場景理解很重要。美團配送的面試特別看重你對配送場景的理解。建議面試前去體驗一下美團外賣的配送流程，思考每個環節的最佳化空間。面試官會問你「你覺得我們這個場景有什麼可以最佳化的」，這時候如果你能說出具體的觀察和想法，會很加分。

4. 系統設計要考慮即時性。配送調度是即時系統，不是離線最佳化。面試中一定要強調即時性約束——秒級響應、增量調度、事件驅動。

5. 準備一些業務指標。面試官會問「你怎麼衡量算法效果」，這時候如果你能說出具體的業務指標（準時率、單均成本、騎手利用率等），會顯得你很有業務sense。

四、FAQ

Q：配送算法面試對程式設計能力要求高嗎？

中等要求。不像後端開發那樣考算法題，但會考建模和實作能力。建議熟悉Python的最佳化庫（Gurobi、OR-Tools、PuLP），能快速實作一個最佳化模型。

Q：沒有運籌學背景能面配送算法嗎？

可以，但需要補基礎。運籌學的核心知識（線性規劃、整數規劃、圖論）不複雜，花1-2個月就能入門。關鍵是理解最佳化思維——怎麼把業務問題轉化為數學問題。

Q：美團配送的面試風格和其他大廠有什麼不同？

更接地氣。其他大廠可能更偏理論，美團配送更偏實際場景。面試官會結合真實業務來問，甚至會開啟APP給你看具體場景。建議面試前多關注美團的配送業務。

Q：配送算法的落地效果怎麼衡量？

主要看三個維度：時效（準時率、平均配送時長）、成本（單均配送成本、騎手利用率）、體驗（客訴率、取消率）。算法最佳化通常先保證時效，再最佳化成本，最後提升體驗。

Q：運籌最佳化方向的發展前景？

非常好。即時配送、網約車、共享出行、供應鏈管理，這些領域都需要運籌最佳化人才。特別是隨著AI的發展，「AI+運籌」的混合方法越來越受重視——用AI做預測，用運籌做決策。