【正文】 配送中心最近的點）。 在未分配點中篩選出可加入點 （未分配點退可行），并 從可加入點中選取一個點作為當前路線的終點，使得路線的成本最小 。 如此不斷對路線進行擴充，直到路線不存在可加入點為止。這時，如果所有點均已分配，則算法結束；否則，生成一條新的初始路線，重復前面的路線擴充程序。 “距離” 未必指實際的距離，而是關于距離和時間等因素的函數(shù) 傳統(tǒng)啟發(fā)式算法 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 插入法 結合 鄰接算法 與 節(jié)約算法 ，依序?qū)㈩櫩忘c插入路徑中以構建配送路線。 它的流程與鄰接算法相似，也是從初始路線出發(fā)，序列構造路線。并在不存在可行插入時新增一條初始路線。插入算法的關鍵是 選擇最合適的未分配點在路線中進行最佳位置的插入。 Solomon于 1983年將此方法應用于求解 VRPTW問題。 Mole和 Jameson于 1976年所提出 傳統(tǒng)啟發(fā)式算法 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 掃除算法 傳統(tǒng)啟發(fā)式算法 一種“ 先分組后路線 ”的算法。 所謂分組，即指分派給每輛車一組點。一種簡單的分組方法是將以車站為原點的坐標平面劃分為多個扇形區(qū)域，并初步將 每個扇形區(qū)域的點分派 給一輛車。 所謂的“路線”，是指在每個區(qū)域內(nèi)，采用 掃除法選擇未分配點，然后應用插入算法擴充路線 。 如果在進行了一次“分組 路線”的路線構造后還存在未分配點，則再進入“分組 路線”程序。如此反復，直到所有點均已分配為止。 最早由 Gillett和 Miller在 1974年提出 1987年， Solomon將其推廣應用于VRPTW問題的路線構造。 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 現(xiàn)代啟發(fā)式算法 該算法通過 利用一個禁忌表記錄已經(jīng)到達過的局部最優(yōu)點， 并在后面的搜索中，根據(jù)某種限制循環(huán)的規(guī)則和禁忌表中記錄的信息在 當前搜索鄰域中取一個合適的解 。 為了減少搜索的計算量，限定鄰域的方法 為了加速搜索進程，可采用平行機計算技術 較多算法都以車輛數(shù)最少為優(yōu)化的第一目標 最早由 Glover在 1986年提出，是局部搜索算法的擴展 1994年， Garcia等首先將禁忌算法應用于VRPTW問題。 禁忌搜索算法 tabu Search 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 遺傳算法 （ Geic Algorithms， GA） 現(xiàn)代啟發(fā)式算法 是借用適者生存規(guī)律進行 局部搜索 改進的一類算法。 該算法 通過染色體的配對和變異過程實現(xiàn)種群的進化，每一次進化則對應解的一次迭代 。 當?shù)螖?shù)達到最大次數(shù)限制或群體中的個體無顯著差異時，迭代終止。 最早是由 Holland在 1975年提出，并首先被 De Jong用來解決復雜問題。 1991年， Thangiah首先將 GA用于求解VRPTW問題。 1999年， Homberge和 Gehring提出了應用 GA求解 VRPTW問題的進化策略。 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 實際上是一種隨機松弛技巧，它模擬了退火過程。在搜索的初始階段， 算法跳向遠點，隨著時間的延伸或“降溫”，跳躍幅度逐漸減小， 最終轉(zhuǎn)向局部搜索下降方法。 快速模擬退火算法： 當?shù)竭_最低溫度后，通過參考初始溫度和到達最好解時的溫度設置一個新的溫度，然后重新啟動模擬退火搜索過程。 – 1996年， Chiang和 Russell提出 VRPTW問題的模擬退火算法， – 2022年， Tan等基于 2interchang法和單調(diào)降的降溫表提出一種快速模擬退火算法。 – 2022年， Li等在應插入算法和掃除算法初始化路線后，將鄰域搜索方法與模擬退火程序相結合實現(xiàn)路線改進 現(xiàn)代啟發(fā)式算法 模擬退火算法 （ Simulated Annealing， SA） 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 模擬了蟻群搜索食物的行為 。在尋找食物時，螞蟻會在它所經(jīng)過的路徑通過 排放一種外激素 （ pheromone，在算法中稱為信息素） 作出標記 ， 排放的量則根據(jù)路徑長度和食物的等級決定 。這些外激素 為其它螞蟻提供信息 ，并吸引他們前去搬運食物。對于 VRPTW問題，也可以根據(jù)螞蟻覓食原理來進行搜索。 首先構造兩組相互協(xié)作的人工蟻群，其中第一個蟻群用于最小化車輛數(shù)，第二個蟻群用于最小化總路長。并以共用解的方式建立協(xié)作關系。 1999年， Gambardellaetal應用蟻群算法對VRPTW進行路線改進。 現(xiàn)代啟發(fā)式算法 蟻群算法 （ Ant Colony Optimization） 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 基本 方法 優(yōu)點 缺點 計算時間過長 應用時間 適用性 動態(tài)規(guī)劃法 可以求得最優(yōu)解 占用內(nèi)存量隨變量的增加成指數(shù)倍增長 1987 適用于投資規(guī)模較小的問題 分枝定界法 內(nèi)存使用常有不足現(xiàn)象發(fā)生 用于解組合優(yōu)化的小型問題 切平面法 所需內(nèi)存大 適用于解小規(guī)模 問題 VRPTW的最優(yōu)化算法 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 基本方法 優(yōu)點 缺點 應用時間 適用性 節(jié)約算法 提高車輛利用率，可以解決大規(guī)膜問題 解是較優(yōu)的可行解，不一定是最優(yōu)解 1983 可以解決規(guī)模問題 鄰接算法 考慮鄰近節(jié)點成本問題 排序時有局限性 適用節(jié)點少的 插入算法 結合了節(jié)約法和最鄰近法，使原問題的等待時間縮短 速度慢，有局限性 1983 適用于小規(guī)模問題 掃除算法 穿插插入法，將二者有機結合 掃描每一個點。速度慢 1987 VRPTW的傳統(tǒng)啟發(fā)式算法 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設計 基 本方法 優(yōu)點 缺點 應用時間 適用性 禁忌搜索算法 可以通過規(guī)則提高搜索效率 可能搜索到局部最優(yōu)解 1994 適用于帶軟時間窗的VRP問題 遺傳算法 具有魯棒性，且全局搜索能力強所需時間較少 不能保證每次搜索結果一樣 1991 適用于復雜優(yōu)化問題 模擬退火算法 采用隨機松馳枝巧 搜索結果不能保證是最優(yōu)的 2022 適于對已有路徑進行改造 蟻群算法 可以將目標構造成兩組相互協(xié)調(diào)的蟻群 需要不斷調(diào)整變量 1999 適用于多目標的優(yōu)化問題 VRPTW的現(xiàn)代啟發(fā)式算法