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