【正文】 速度慢 1987 VRPTW的傳統(tǒng)啟發(fā)式算法 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 基 本方法 優(yōu)點 缺點 應用時間 適用性 禁忌搜索算法 可以通過規(guī)則提高搜索效率 可能搜索到局部最優(yōu)解 1994 適用于帶軟時間窗的VRP問題 遺傳算法 具有魯棒性，且全局搜索能力強所需時間較少 不能保證每次搜索結(jié)果一樣 1991 適用于復雜優(yōu)化問題 模擬退火算法 采用隨機松馳枝巧 搜索結(jié)果不能保證是最優(yōu)的 2022 適于對已有路徑進行改造 蟻群算法 可以將目標構(gòu)造成兩組相互協(xié)調(diào)的蟻群 需要不斷調(diào)整變量 1999 適用于多目標的優(yōu)化問題 VRPTW的現(xiàn)代啟發(fā)式算法 。 1999年， Gambardellaetal應用蟻群算法對VRPTW進行路線改進。 首先構(gòu)造兩組相互協(xié)作的人工蟻群，其中第一個蟻群用于最小化車輛數(shù)，第二個蟻群用于最小化總路長。這些外激素 為其它螞蟻提供信息 ，并吸引他們前去搬運食物。 – 2022年， Li等在應插入算法和掃除算法初始化路線后，將鄰域搜索方法與模擬退火程序相結(jié)合實現(xiàn)路線改進 現(xiàn)代啟發(fā)式算法 模擬退火算法 （ Simulated Annealing， SA） 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 模擬了蟻群搜索食物的行為 。 快速模擬退火算法： 當?shù)竭_最低溫度后，通過參考初始溫度和到達最好解時的溫度設置一個新的溫度，然后重新啟動模擬退火搜索過程。 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 實際上是一種隨機松弛技巧，它模擬了退火過程。 1991年， Thangiah首先將 GA用于求解VRPTW問題。 當?shù)螖?shù)達到最大次數(shù)限制或群體中的個體無顯著差異時，迭代終止。 禁忌搜索算法 tabu Search 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 遺傳算法 （ Geic Algorithms， GA） 現(xiàn)代啟發(fā)式算法 是借用適者生存規(guī)律進行 局部搜索 改進的一類算法。 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 現(xiàn)代啟發(fā)式算法 該算法通過 利用一個禁忌表記錄已經(jīng)到達過的局部最優(yōu)點， 并在后面的搜索中，根據(jù)某種限制循環(huán)的規(guī)則和禁忌表中記錄的信息在 當前搜索鄰域中取一個合適的解 。如此反復，直到所有點均已分配為止。 所謂的“路線”，是指在每個區(qū)域內(nèi)，采用 掃除法選擇未分配點，然后應用插入算法擴充路線 。 所謂分組，即指分派給每輛車一組點。 Solomon于 1983年將此方法應用于求解 VRPTW問題。并在不存在可行插入時新增一條初始路線。 “距離” 未必指實際的距離，而是關(guān)于距離和時間等因素的函數(shù) 傳統(tǒng)啟發(fā)式算法 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 插入法 結(jié)合 鄰接算法 與 節(jié)約算法 ，依序?qū)㈩櫩忘c插入路徑中以構(gòu)建配送路線。 如此不斷對路線進行擴充，直到路線不存在可加入點為止。 算法從一條只含一個配送點的路線出發(fā)（通常取 “距離” 配送中心最近的點）。當不存在可行合并時，算法結(jié)束。 如果合并后的路線滿足約束條件（車輛容量、時間窗），則說這樣的合并是可行的，并將合并的節(jié)約值定義為連接這兩條路線的邊的節(jié)約值。 求解時間過長，不適用于大規(guī)模問題 最優(yōu)化算法 切平面法 （ Cutting planes） 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 傳統(tǒng)啟發(fā)式算法 節(jié)約算法（ Saving Method） 將每條路線只含一個配送點的 n條路線作為初始解，其中，每條路線中第一個和最后一個配送點分別稱為 路線的起點和終點 。 適用于求解小型問題 Held和 Karp指出分枝定界法的求解效率與其界限設定的寬緊有極大的關(guān)系。 按 不同的數(shù)學模型 TSP問題（ Traveling Salesman Problem, 旅行商問題） VRP問題 （ Vehicle Routing Problem, 車輛路由問題） PDP問題（ Pickup and Delivery Problem, 裝卸貨問題） 車輛運輸調(diào)度問題 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 多配送中心的車輛路徑問題 (Multipledepot VRP) 帶能力約束的車輛路徑問題 (Capacitated VRP) 帶時間窗的車輛路徑問題 (VRP with Time Windows) 追求最佳服務時間的車輛路徑問題 (VRP with Defined Time) 多種車型的車輛路徑問題 (Fleet Size and mix VRP) 考慮回程運輸?shù)穆窂絾栴} (VRP with Backhauls) 動態(tài)需求路徑問題 (Dynamic VRP) 車輛運輸調(diào)度問題 VRP 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 基本思路是 把多階段過程轉(zhuǎn)化為一系列單階段問題逐個求解， 從而簡化計算過程。 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 對一系列裝貨點和（或）卸貨點，規(guī)劃適當?shù)男熊嚶肪€，使車輛有序地通過它們，滿足一定的約束條件 （如時間窗口約束、車輛容量限制、車輛行駛里程限制、司機最大工作時間限制等） ，達到一定的目標（如車輛行駛路程最短、運輸費用最少、使用車輛數(shù)最少，服務質(zhì)量最高等） 。 配送計劃要素 屬性： 車輛所在的停車場，車輛的容積、載重及車輛類型 路線有 總里程 等屬性。 配送計劃要素 重量，體積和類型 ， 某些特殊的運載單元必須由特殊類型的車輛運載 停車場 是路線的起點和終點 裝載點 一般是配送中心，運載單元在此裝載 卸載點 一般是客戶，運載單元在此卸載 屬性： 起始節(jié)點、終止節(jié)點和長度 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 車輛： 從 停車場 出發(fā)，由 通路 到達其它節(jié)點，沿著路線規(guī)定的順序，在裝載點裝載運載單元，在卸載點卸下運載單元，最后到達 停車場 。 配送計劃的制定 配送路線選擇 ?單對多；多對多 ?運載單元 ?節(jié)點 ?通路車輛 ?路線 配送模型分析 提早 /延時 確定時間罰則 ?貨物重量、體積和類型 ?車輛最大載重容積 /類型 貨物運載單元 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 運載單元： 不可劃分的貨物單元 ， 從某一裝載點裝載到某一配送車輛上，經(jīng)過若干節(jié)點，在某一卸載點卸下。 ? 配送網(wǎng)絡結(jié)構(gòu) 是指物品從生產(chǎn)區(qū)域到消費區(qū)域的空