【正文】 客戶訂單的需求制定的 貨物拼裝、車輛選擇與路線選擇 的具體方案 ，它直接影響配送中心的服務(wù)質(zhì)量和成本。 節(jié)點 通路 僅僅指從一個節(jié)點到另外一個節(jié)點的道路，如果從某一個節(jié)點到達(dá)另一個節(jié)點必須經(jīng)過第三個節(jié)點， 即兩個節(jié)點之間沒有直接的通路，其有間接通路， 這個間接通路為第一個節(jié)點到第三個節(jié)點的通路與第三個節(jié)點到第二個節(jié)點的通路的連接。 路線： 是一個節(jié)點的序列， 表示車輛從某一個停車場節(jié)點開始依次經(jīng)過的節(jié)點。 路線必須開始于停車場，結(jié)束于停車場。 車輛運輸調(diào)度問題 ?廣義的配送中心 ，指車輛的出發(fā)地，如物流中心、配送中心、倉庫、車場 等 ? 車輛優(yōu)化調(diào)度問題最早是由 Danzig和Ramser于 1959年提出 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設(shè)計 按 任務(wù)特征 分 純裝貨問題 和 純卸貨問題 （車輛在所有任務(wù)點只裝貨或卸貨，即集貨和卸貨問題） 裝卸貨混合問題 （每個客戶有不同的裝貨點和卸貨點，即集貨、送貨一體化問題） 按 任務(wù)性質(zhì) 分 對弧服務(wù)問題 （如郵遞員問題） 對點服務(wù)問題 （旅行商問題） 混和服務(wù)問題 （如交通車輛路線安排問題） 車輛運輸調(diào)度問題 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設(shè)計 按 車輛載貨狀況 分 滿載問題 （貨運量不小于車輛容量，完成一項任務(wù)需要不只一輛車） 非滿載問題 （ 貨運量小于車輛容量，多項任務(wù)合用一輛車） 按 車庫數(shù)目 分 單車庫問題；多車庫問題 按車輛類型分 單車輛類型問題 （所有車輛容量相同，類型相同） 多車輛類型問題 （執(zhí)行任務(wù)車輛的容量和類型不完全相同） 車輛運輸調(diào)度問題 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設(shè)計 按 車輛對車庫的所屬關(guān)系 車輛開放問題 （車輛可以不返回其出發(fā)車庫） 車輛封閉問題 （車輛必須返回其出發(fā)車庫） 按 優(yōu)化目標(biāo) 分，有 單目標(biāo)問題 和 多目標(biāo)問題 。 復(fù)雜性在于各階段決策之間的相互聯(lián)系，而且計算時間與計算機內(nèi)存空間均隨變量的增加而呈指數(shù)增加 僅適用于較小規(guī)模的尋優(yōu)問題 最優(yōu)化算法 動態(tài)規(guī)劃 （ Dynamic programming） 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設(shè)計 是一種隱枚舉法或 部分枚舉法 ，是枚舉法基礎(chǔ)上的改進 對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的可行解空間恰當(dāng)?shù)剡M行系統(tǒng)搜索 Kolenatal曾利用此方法求解含時間窗約束的車輛巡回問題。 最優(yōu)化算法 分枝定界法 （ Branch and bound） 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設(shè)計 在求解與整數(shù)規(guī)劃相對應(yīng)的線性規(guī)劃上，不斷地增加新的約束，也就是另外 加入線性約束條件，以切掉對應(yīng)于非整數(shù)規(guī)劃的所有可行解的集合 ，以使問題可達(dá)到整數(shù)線性規(guī)劃求解的形式，從而獲得最優(yōu)解?？疾?一條路線的起點與另一條路線的終點相連合并成新的一條路線 。 選擇節(jié)約值最大的可行合并 進行一次路線的合并。 可提高車輛的利用率 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設(shè)計 鄰接算法 它是一種序列構(gòu)造路線法。 在未分配點中篩選出可加入點 （未分配點退可行），并 從可加入點中選取一個點作為當(dāng)前路線的終點，使得路線的成本最小 。這時，如果所有點均已分配，則算法結(jié)束；否則，生成一條新的初始路線，重復(fù)前面的路線擴充程序。 它的流程與鄰接算法相似，也是從初始路線出發(fā)，序列構(gòu)造路線。插入算法的關(guān)鍵是 選擇最合適的未分配點在路線中進行最佳位置的插入。 Mole和 Jameson于 1976年所提出 傳統(tǒng)啟發(fā)式算法 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設(shè)計 掃除算法 傳統(tǒng)啟發(fā)式算法 一種“ 先分組后路線 ”的算法。一種簡單的分組方法是將以車站為原點的坐標(biāo)平面劃分為多個扇形區(qū)域，并初步將 每個扇形區(qū)域的點分派 給一輛車。 如果在進行了一次“分組 路線”的路線構(gòu)造后還存在未分配點，則再進入“分組 路線”程序。 最早由 Gillett和 Miller在 1974年提出 1987年， Solomon將其推廣應(yīng)用于VRPTW問題的路線構(gòu)造。 為了減少搜索的計算量，限定鄰域的方法 為了加速搜索進程，可采用平行機計算技術(shù) 較多算法都以車輛數(shù)最少為優(yōu)化的第一目標(biāo) 最早由 Glover在 1986年提出，是局部搜索算法的擴展 1994年， Garcia等首先將禁忌算法應(yīng)用于VRPTW問題。 該算法 通過染色體的配對和變異過程實現(xiàn)種群的進化，每一次進化則對應(yīng)解的一次迭代 。 最早是由 Holland在 1975年提出，并首先被 De Jong用來解決復(fù)雜問題。 1999年， Homberge和 Gehring提出了應(yīng)用 GA求解 VRPTW問題的進化策略。在搜索的初始階段， 算法跳向遠(yuǎn)點，隨著時間的延伸或“降溫”，跳躍幅度逐漸減小， 最終轉(zhuǎn)向局部搜索下降方法。 – 1996年， Chiang和 Russell提出 VRPTW問題的模擬退火算法， – 2022年， Tan等基于 2interchang法和單調(diào)降的降溫表提出一種快速模擬退火算法。在尋找食物時，螞蟻會在它所經(jīng)過的路徑通過 排放一種外激素 （ pheromone，在算法中稱為信息素） 作出標(biāo)記 ， 排放的量則根據(jù)路徑長度和食物的等級決定 。對于 VRPTW問題，也可以根據(jù)螞蟻覓食原理來進行搜索。并以共用解的方式建立協(xié)作關(guān)系。 現(xiàn)代啟發(fā)式算法 蟻群算法 （ Ant Colony Optimization） 物流中心 物流網(wǎng)點規(guī)劃 物流配送 配送管理 配送方案設(shè)計 基本 方法 優(yōu)點 缺點 計算時間過長 應(yīng)用時間 適用性 動態(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ī)劃 物流配送 配送管理 配送方案設(shè)計 基本方法 優(yōu)點 缺點 應(yīng)用時間 適用性 節(jié)約算法 提高車輛利用率，可以解決大規(guī)膜問題 解是較優(yōu)的可行解，不一定是最優(yōu)解 1983 可以解決規(guī)模問題 鄰接算法 考慮鄰近節(jié)點成本問題 排序時有局限性 適用節(jié)點少的 插入算法 結(jié)合了節(jié)約法和最鄰近法，使原問題的等待時間縮短 速度慢，有局限性 1983 適用于小規(guī)模問題 掃除算法 穿插插入法，將二者有機結(jié)合 掃描每一