版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、車輛路徑問題優(yōu)化算法美國物流管理學(xué)會(Council of Logistics Management , CLM)對物流所作的定 義為: “為符合顧客的需要,對原料、制造過程中的存貨與制成品以及相關(guān)信息, 從其起運點至最終消費點之間,做出的追求效率與成本效果的計劃、執(zhí)行與控制 過程?!倍嘘P(guān)資料顯示,物流配送過程 (包含倉儲、分揀、運輸?shù)?)的成本構(gòu)成中,運輸 成本占到 52% 之多。因此,如何在滿足客戶適當(dāng)滿意度的前提下,將配送的運 輸成本合理地降低,成為一個緊迫而重要的研究課題,車輛路徑問題正是基于這 一需求而產(chǎn)生的。2.1 車輛路徑問題的定義 車輛路徑問題可以描述為:給定一組有容量限制的
2、車輛的集合、一個物流中心(或 供貨地)、若干有供貨需求的客戶,組織適當(dāng)?shù)男熊嚶肪€,使車輛有序地通過所 有的客戶,在滿足一定的約束條件(如需求量、服務(wù)時間限制、車輛容量限制、 行駛里程限制等)下,達(dá)到一定的目標(biāo)(如路程最短、費用極小、時間盡量少、 使用車輛數(shù)盡量少等)。 4 因此研究車輛的路徑問題,就是要研究如何安排運輸車輛的行駛路線, 使運輸車 輛依照最短的行駛路徑或最短的時間費用, 依次服務(wù)于每個客戶后返回起點,總 的運輸成本實現(xiàn)最小。車輛路徑問題已被證明是 NP-Hard 問題,因此求解比較困難。然而,由于其在 現(xiàn)實生活中應(yīng)用非常廣泛,使得它無論在理論上還是在實踐上都有極大的研究價 值。P
3、enousal Machado 等人5 指出車輛路徑問題 (vehicle routing problem ,簡稱 VRP)是一個復(fù)雜的組合優(yōu)化問題,是古老的旅行商問題和背包問題的綜合。實 際上,車輛路徑問題通常可被分解或轉(zhuǎn)化成一個或幾個已經(jīng)研究過的基本問題, 再采用相應(yīng)比較成熟的基本理論和方法,以得到最優(yōu)解或滿意解。這些與車輛路徑問題相關(guān)的常用基本問題有; 旅行商問題、運輸問題、背包問題、 最短路問題、最小費用最大流問題、中國郵路問題、指派問題等。旅行商問題可被描述為:一個推銷員欲到 n 個城市推銷商品,每 2 個城市之間的 距離是已知的。如何選擇一條路徑使推銷員依次又不重復(fù)地走遍每個城市后
4、, 回 到起點且所走的路徑最短。運輸問題關(guān)心的是(確實的或是比喻的)以最低的總配送成本把供應(yīng)中心(稱為 出發(fā)地,sources)的任何產(chǎn)品運送到每一個接受中心(稱為目的地, destinations )。運輸問題需要的數(shù)據(jù)僅僅是供應(yīng)量、需求量和單位成本。 背包問題是指有一只固定容量的背包和若干體積、 重量不等的物品,背包的容量 不允許裝下這所有的物品,那么如何選擇適當(dāng)?shù)奈锲费b入背包,使得背包的裝載 量(所裝物品的重量之和)最大。最短路徑問題解決的是在一個網(wǎng)絡(luò)中, 如何尋找兩點之間的最短路徑。這兩點之 間通常沒有直接的通路可達(dá),但可經(jīng)由若干中間結(jié)點相通。最小費用流問題主要解決如何以最小成本在一個
5、配送網(wǎng)絡(luò)中運輸貨物。 最小費用 流問題又稱為網(wǎng)絡(luò)配送問題。最大流問題和最小費用流問題一樣,也與網(wǎng)絡(luò)中的流有關(guān)。但是它們的目標(biāo)不同, 最大流問題不是使得流的成本最小化, 而是尋找一個流的方案,使得通過網(wǎng)絡(luò)的 中國郵路問題是由我國管梅谷同志在 1962 年首先提出的,它可描述為:一個郵 遞員負(fù)責(zé)某一個地區(qū)的信件投遞。 每天要從郵局出發(fā), 走遍該地區(qū)所有的街道再 返回郵局,問應(yīng)該怎樣安排送信路線可以使所走的路程最短。指派問題解決將 n 件工作安排給 m 個人完成的問題。已知不同人完成不同工作 的效率(或成本)不同,指派問題要求以最高的效率(或最小的人工成本)完成 工作的安排。2.2 車輛路徑問題的分
6、類 車輛路徑問題當(dāng)不考慮時間要求, 僅根據(jù)空間位置安排路線時稱為車輛路線安排 問題(Vehicle Routing Problem 簡記VRP);當(dāng)考慮時間要求安排路線時稱為車輛 調(diào)度問題(Vehicle Scheduling Problem 簡記VSP);當(dāng)同時考慮空間位置和時間要 求時稱為路線和調(diào)度混合問題 6 。車輛調(diào)度冋題即有時間要求的車輛路徑冋題(VSP)又被稱為帶時間窗的車輛路 徑問題(Vehicle Routing Problem with Time Windows ,簡記為 VRPTW)。VRPTW 是在VRP的基礎(chǔ)上增加了客戶要求訪問的時間窗口,是一般車輛路徑問題的擴(kuò) 展。其
7、簡單的描述如下: 用于服務(wù)的若干車輛從站點出發(fā), 為處在不同地理位置、 具有不同貨物需求和不同服務(wù)時間窗要求的所有顧客提供服務(wù),然后返回站點, 其中為每個顧客僅提供一次服務(wù)。 其目標(biāo)是在時間窗內(nèi)為顧客提供服務(wù)時, 使車 輛的行駛時間和等待時間之和最短。根據(jù)時間約束的嚴(yán)格與否, 帶時間窗的車輛路徑問題被分為兩類: 軟時間窗車輛 路徑問題和硬時間窗車輛路徑問題。 軟時間窗車輛路徑問題要求配送車輛盡可能 在時間窗內(nèi)到達(dá)訪問,否則將給予一定的懲罰。該懲罰包括兩部分:(1)車輛在要求的最早到達(dá)時間之前到達(dá),必須在任務(wù)點處等待而損失的成本;(2)車輛在要求的最遲到達(dá)時間之后到達(dá), 必須付給客戶預(yù)先約定的罰
8、金。 而硬時間窗車輛 路徑問題則要求必須在時間窗內(nèi)到達(dá)訪問,否則服務(wù)被拒絕。Koskosidis 等人( 1992) 7 指出,軟時間窗模式比硬時間窗更具優(yōu)勢是因為: 第一、軟時窗模式較傳統(tǒng)硬時窗模式更為一般化, 且軟時窗的求解演算法較具彈 性(因限制式較少)。而且若要提高準(zhǔn)點服務(wù)頻率,只需適當(dāng)?shù)奶岣邞土P成本即 可;第二、在現(xiàn)實世界中,時窗限制大多屬于軟時窗限制。配送服務(wù)商沒有在約 定的時間內(nèi)送達(dá)顧客端, 并非一定不可服務(wù), 而是可以服務(wù)但必須付出雙方約定 的懲罰成本。 有較高準(zhǔn)點送達(dá)要求的顧客的懲罰成本大, 不準(zhǔn)時但是在可以忍受 的時間內(nèi)送達(dá)的顧客的懲罰成本相對小些; 第三、軟時窗模式可以有
9、效的反應(yīng)配 送商在車隊營運成本、 規(guī)模和服務(wù)水準(zhǔn)兩者之間的關(guān)系; 第四、軟時窗模式可以 發(fā)現(xiàn)硬時窗模式無法找到的可行解。 特別是在小規(guī)模車隊服務(wù)多數(shù)顧客以及嚴(yán)苛 的時間限制條件狀況下。 在上述的情形得到軟時窗限制下的可行解后, 可再調(diào)整 時間窗讓違反時間窗的情況得到改善。車輛路徑問題還有確定性 (Deterministic) 模式和隨機(jī)性 (Stochastic) 模式之分8 。 確定性模式假設(shè):其一、客戶的數(shù)目在配送開始前是已知且固定的;其二、客戶 的需求量在配送開始前是已知且固定的; 其三、兩點之間的旅行時間僅取決于這 兩點之間的距離。 而隨機(jī)性模式不要求以上一個或多個假設(shè)。 隨機(jī)性模式又
10、稱為 隨機(jī)需求車輛路徑問題。如果考慮裝卸工人的調(diào)配問題, 則車輛路徑問題就稱為帶裝卸工調(diào)配的車輛路徑 問題。帶裝卸工調(diào)配的車輛路徑問題描述如下 9:設(shè)配送中心有n輛貨車都要 向b個客戶裝卸貨物。配送中心可以安排 位裝卸工跟著車輛,也可以安排位裝 卸工固定在客戶 處。已知在客戶 處需要的裝卸工人數(shù)是 ,配送中心應(yīng)該考慮 如何調(diào)配裝卸工,使總的裝卸工人數(shù)最少。除了以上分類, 車輛路徑問題還可以按任務(wù)特征分為裝貨問題、 卸貨問題及裝卸 混合問題; 按任務(wù)性質(zhì)分為對弧服務(wù)問題 (如中國郵遞員問題) 和對點服務(wù)問題 (如旅行商問題)以及混合服務(wù)問題(如校車路線安排問題);按車輛載貨狀況 分為滿載問題和非
11、滿載問題; 按車場數(shù)目分為單車場問題和多車場問題; 按車輛 類型數(shù)分為單車型問題和多車型問題; 按車輛對車場的所屬關(guān)系分為車輛開放問 題(車輛可不返回車場)和車輛封閉問題(車輛必須返回車場);按優(yōu)化目標(biāo)可 分為單目標(biāo)問題和多目標(biāo)問題,等等。針對上述不同的分類方法,車輛路徑問題的模型構(gòu)造及求解算法有很大差別。2.3 車輛路徑問題的構(gòu)成要素 物流配送車輛路徑問題的構(gòu)成因素主要包括貨物、車輛、配送中心、客戶、運輸 網(wǎng)絡(luò)、約束條件和目標(biāo)函數(shù)等要素 10 。2.3.1 貨物 貨物是配送的對象。可將每個客戶需求(或供應(yīng))的貨物看成一批貨物。每批貨 物包括品名、包裝、重量、體積、要求送到(或取走)的時間和地
12、點、能否分批 配送等屬性。貨物的品名和包裝, 是選用配送車輛的類型以及決定該批貨物能否 與其他貨物裝在同一車輛內(nèi)的依據(jù)。 例如,一些貨物因性質(zhì)特殊需要使用專用車 輛裝運;而一些貨物雖然性質(zhì)特殊, 但由于包裝條件很好, 故也能與其它貨物裝 在同一車輛內(nèi)。 另外, 貨物的重量和體積也是進(jìn)行車輛裝載決策的重要依據(jù)。 當(dāng) 某個客戶的需求量 (供應(yīng)量) 的貨物的重量或體積超過車輛的最大裝載量或體積 時,則對該客戶需要采用多臺車輛進(jìn)行配送。2.3.2 車輛 車輛是貨物的運載工具,其主要包括 : 車輛的類型、裝載量、一次配送的最大行 駛距離、配送前以及完成任務(wù)后車輛的停放位置等。 其一、車輛的類型有通用車輛
13、和專用車輛之分, 通用車輛適于運載大多數(shù)普通貨 物,專用車輛適于載運一些性質(zhì)特殊的貨物。 其二、車輛的裝載量是指車輛的最大裝載重量和最大裝載容積, 是進(jìn)行車輛裝載 決策的依據(jù)。在某個配送系統(tǒng)中,車輛的裝載量可以相同也可以不同。 其三、對每臺車輛一次配送的行駛距離的要求可以分為以下幾種情況 : 第一、無 距離限制 ; 第二、有距離限制 ; 第三、有距離限制,但可以不遵守。 其四、車輛在配送前可以是停放在某個停車場、 配送中心或者是客戶所在地。 完 成任務(wù)后,其停放位置一般可以分為以下幾種情形 : 一是必須返回出發(fā)點 ; 二是 必須某個停車場或配送中心 ; 三是可返回任意停車場 ; 四是可停放在任
14、何地點。2.3.3 配送中心 配送中心是從事貨物配備 (集貨、加工、揀選、配貨 ) 和組織對客戶的送貨,以提 高水平實現(xiàn)銷售或供應(yīng)的現(xiàn)代流通設(shè)施。 在某個配送系統(tǒng)中, 配送中心的個數(shù)可 以是一個也可以是多個, 這涉及到配送網(wǎng)絡(luò)問題, 如在某些配送網(wǎng)點多而且配送 范圍廣的情形下, 往往采用多級配送中心進(jìn)行配送, 通過一級配送中心配送到下 一級配送中心再配送, 在多個二級配送中心下, 究竟由哪個配送中心配送, 這涉 及到配送的優(yōu)化問題。其配送示意圖見圖 2-1:圖 2-1 分級配送示意圖2.3.4 客戶 也稱為用戶,包括各盆景展覽館、陳列中心、公司、家庭用戶等。單個客戶一次 所需的盆景數(shù)量可能大于
15、盆景配送車某車輛的最大裝載量, 也可能小于該車輛的 最大裝載量。 而該系統(tǒng)全部客戶的貨物需求 (或供應(yīng))總量可能超過全部車輛的 總裝載量。在以上情形下,當(dāng)貨物一次性需求(或供應(yīng))總量超過運輸能力時, 需要多次(多輛)分批配送;當(dāng)貨物一次性需求(或供應(yīng))量小于某車輛的最大 裝載量時,在可能的情況下,應(yīng)進(jìn)行貨物配載??蛻舻男枨螅ɑ蚬?yīng))盆景的時間,是指要求盆景送達(dá)(或取走)的時間,對配 送時間的要求可分為以下幾種情況 : 第一、無時間限制;第二、要求在指定的時 間區(qū)間(也稱為時間窗)內(nèi)完成運輸任務(wù);第三、有時間限制,但可以不遵守, 只是不遵守時要給予一定的懲罰。2.3.5 運輸網(wǎng)絡(luò) 運輸網(wǎng)絡(luò)是由頂
16、點(指配送中心、客戶、停車場等)、無向邊和有向弧組成 的,邊、弧的屬性包括方向、權(quán)值和交通流量限制等。運輸網(wǎng)絡(luò)中邊或弧的權(quán)值 可以表示距離、 時間或費用。邊或弧的權(quán)值變化可分為以下幾種情況 : 一是固定, 即不隨時間和車輛的不同而變化;二是隨時間而變化;三是隨車輛不同而變化; 四是既隨時間不同而變化,又隨車輛不同而變化。對運輸網(wǎng)絡(luò)權(quán)值間的關(guān)系可以要求其滿足三角不等式,即兩邊之和大于第三邊。 也可以不加限制。運輸網(wǎng)絡(luò)見示意圖 2-2.圖 2-2 運輸網(wǎng)絡(luò)示意圖 對運輸網(wǎng)絡(luò)中頂點、邊或弧的交通流量要求分為以下幾種 : 其一、交通流量隨時 間不同而變化 ; 其二、邊、弧限制,即每條邊、 弧上同時行駛
17、的車輛數(shù)有限制 ; 其 三、頂點限制,即每個頂點上同時裝、卸的車輛數(shù)有限;其四、邊、弧、頂點都 有限制。2.3.6 約束條件 通常說來, 物流配送車輛路徑問題應(yīng)滿足的約束條件主要包括: 第一,滿足所有 客戶對貨物品種、規(guī)格、數(shù)量的要求;第二,滿足客戶對貨物發(fā)到的時間范圍的 要求;第三,在允許通行時間進(jìn)行配送(如有時規(guī)定白天不能通行貨車等);第 四,車輛在配送過程中的實際載貨量不得超過車輛的最大允許裝載量; 第五,在 配送中心現(xiàn)有的運力范圍內(nèi)。2.3.7 目標(biāo)函數(shù)對物流配送車輛路徑問題, 可以只選用一個目標(biāo), 也可以是多個目標(biāo)。 經(jīng)常 選用的目標(biāo)函數(shù)主要有 : 第一,配送總里程最短。 配送里程與
18、配送車輛的耗油量、 磨損程度以及司機(jī)疲勞程度等直接相關(guān), 它直接決定運輸?shù)某杀荆?對配送業(yè)務(wù)的 經(jīng)濟(jì)效益有很大影響。 由于配送里程計算簡便, 它是確定配送路線時用得最多的 指標(biāo)。第二, 配送車輛的噸位公里數(shù)最少。 該目標(biāo)將配送距離與車輛的載重量結(jié) 合起來考慮, 即以所有配送車輛的噸位數(shù) (最大載重噸) 與其行駛距離的乘積的 總和最少為目標(biāo)。 第三,綜合費用最低。 降低綜合費用是實現(xiàn)配送業(yè)務(wù)經(jīng)濟(jì)效益 的基本要求。在物流配送中,與取送有關(guān)的費用包括 : 車輛維護(hù)和行駛費用、路 橋費用、車隊管理費用、貨物裝卸費用、有關(guān)人員工資費用等。第四,準(zhǔn)時性最 高。由于客戶對交貨時間有較嚴(yán)格的要求, 為提高配送
19、服務(wù)質(zhì)量, 有時需要將準(zhǔn) 時性最高作為確定配送路線目標(biāo)。 第五,運力利用最合理。 該目標(biāo)要求使用的較 少的車輛完成配送任務(wù),并使車輛的滿載率最高,以充分利用車輛的裝卸能力。 第六,勞動消耗最低。即以司機(jī)人數(shù)最少、司機(jī)工資時間最短為目標(biāo)。2.4 車輛路徑問題的求解方法 車輛路徑問題通常被構(gòu)造成整數(shù)規(guī)劃模型、圖論或其它模型,這些模型之間 存在著某種聯(lián)系。 但從建立模型時的出發(fā)點考慮, 大多數(shù)模型都可看成是下面三 種模型的變形與組合: 第一,以車流為基礎(chǔ)的模型; 第二,以物流為基礎(chǔ)的模型; 第三,集覆蓋模型。求解方法上,常用的基本理論和方法有:分枝定界法、割平面法、線性規(guī)劃法、 動態(tài)規(guī)劃法、匹配理論
20、、對偶理論、組臺理論、線搜索技術(shù)、列生成技術(shù)、拉格 朗日松弛技術(shù)、狀態(tài)空間松弛技術(shù)、 Benders 分解技術(shù)、扶梯度 (sub gradient) 優(yōu)化技術(shù)、概率分析、統(tǒng)計分析、最差情況分析、經(jīng)驗分折等常用算法基本上可分為優(yōu)化算法和啟發(fā)式算法兩大類。 優(yōu)化算法求解時間長, 算 法效率低且不適合求解規(guī)模較大的問題, 因此在實際應(yīng)用中受到限制; 啟發(fā)式算 法效率較高且能逼近最優(yōu)解, 為此專家們主要把精力花在構(gòu)造高質(zhì)量的啟發(fā)式算 法上。目前已提出的啟發(fā)式算法相當(dāng)多,大體上可分為傳統(tǒng)啟發(fā)式算法 ( Heuristic )和巨集啟發(fā)式算法( Meta-Heuristic )兩大類 11 。 傳統(tǒng)啟發(fā)式
21、算法具有求解速度快、 求得的解較為固定的特點。 已被證明會陷入局 部優(yōu)化解中 11 。巨集啟發(fā)式算法則嘗試以不同的方式跳出局部解,在可接受的 時間內(nèi),求得近似最優(yōu)解,甚至是全局最優(yōu)解。所以在近年來的研究中,多用巨 集啟發(fā)式算法來求解車輛路徑問題, 或者混合使用傳統(tǒng)啟發(fā)式算法和巨集啟發(fā)式 算法。2.4.1 傳統(tǒng)啟發(fā)式算法根據(jù) Bodin 等人12 的研究,用于求解車輛路徑問題的傳統(tǒng)啟發(fā)式算法可 分為: 第一,先分組后安排路線的方法( Cluster-First Route-Second ):這種方法先把 節(jié)點(或?。┑男枨筮M(jìn)行分組或劃群,然后對每一組設(shè)計一條經(jīng)濟(jì)的路線。如 Gillett 和 M
22、iller 于 1974 年提出的掃描( sweep )算法13,14,15 。方法是先以極 坐標(biāo)的方式表示各個客戶點的區(qū)域位置, 再任取一個客戶點作為起點以順時針方 向,以車輛容量為限制條件(或再加入其它限制條件)對區(qū)域進(jìn)行分割,使不超 過車輛容量 (或滿足其它限制條件) 的需求點組成一個區(qū)域, 一個區(qū)域就是一個 組。當(dāng)形成一系列這樣的組后, 再對每一組中的各點安排線路。 這種算法一般僅 適用于裝貨(或卸貨)問題,且車輛是封閉的。 第二,先安排路線后分組的方法( Route-First Cluster-Second ):在不考慮約束 條件的前提下進(jìn)行路線的構(gòu)建, 然后再根據(jù)約束條件對路線進(jìn)行
23、切割。 這種方法 首先構(gòu)造一條或幾條很長的路線 (通常不可行 ),它包括了所有需求對象,然后再 把這些很長的路線劃分成一些短而可行的路線。 具體進(jìn)行時, 一般是先解一個經(jīng) 過所有點的旅行商問題,形成一條路線,然后根據(jù)一定的約束 ( 如車輛容量等 )對 它進(jìn)行分劃。典型的有由 Rosenkrantz 等人16于 1977 年提出的最臨近點法。 思路是以車場為起點, 尋找離車場距離成本最小且沒有加入路線的節(jié)點為起始路 線,重復(fù)以上步驟直至找不到可以滿足車輛限制條件的節(jié)點時, 回到車場重新出 發(fā),另外構(gòu)建一條新的路徑。第三,節(jié)約插入算法( Saving or Insertion ):根據(jù)節(jié)約值的大小
24、來構(gòu)建路線, 直至無法改善或達(dá)到停止條件為止。 該算法的每一步, 把當(dāng)前的線路構(gòu)形 (很可 能是不可行的)跟另外的構(gòu)形(也可能是不可行的)進(jìn)行比較,后者或是根據(jù)某 個判別函數(shù)(例如總費用) 會產(chǎn)生最大程度的節(jié)約的構(gòu)形, 或是以最小代價把一 個不在當(dāng)前構(gòu)形上的需求對象插人進(jìn)來的掏形,最后得到一個較好的可行構(gòu)形。 節(jié)約算法最早是由 Clark 和 Wright 于 1964 年提出的 11 。根據(jù)三角形兩邊之和 大于第三邊的性質(zhì), 以一部車服務(wù)一個客戶作為初始解, 一部車服務(wù)一個客戶然 后就返回車場為其起始狀況, 計算路徑間的合并節(jié)約值。 將算出的節(jié)約值按照降 冪排序并依次合并路徑。 若找不到滿足
25、限制條件的節(jié)點, 便回到車場, 重新構(gòu)建 新的路徑,直到?jīng)]有大于零的節(jié)約值為止。節(jié)約算法是利用節(jié)約值的大小和是否滿足限制條件來決定兩節(jié)點是否相連的。 節(jié) 約值的計算如下:設(shè)0表示示車場,i和j為兩個任務(wù)點,定義點對i和j的節(jié)約 值為 其含義為點i和點j在同一條線路上的距離成本與點i和點j各在不同線路上的距 離成本相比得到的距離成本的節(jié)約值。這種算法與 Sweep 算法的適用范圍差不 多。2.4.2 巨集啟發(fā)式算法 巨集啟發(fā)式算法主要基于改進(jìn)或交換( Improvement or Exchange )的思路,即 先構(gòu)建一個初始解,再用貪婪算法( Greedy)17 ,進(jìn)行路線的優(yōu)化,直至無法 改
26、進(jìn)或達(dá)到停止條件為止。 該算法在始終保持解可行的情況下, 力圖向最優(yōu)目標(biāo) 靠近,每一步都產(chǎn)生另一個可行解以代替原來的解, 使目標(biāo)函數(shù)值得以改進(jìn), 一 直繼續(xù)到不能再改進(jìn)目標(biāo)函數(shù)值為止。 經(jīng)典的遺傳算法、模擬退火算法、禁忌搜索算法、蟻群算法都屬于這一類方法。 遺傳算法( Genetic Algorithm, GA) 最早由 Holland 18 于 1975 年提出,是根據(jù) 達(dá)爾文進(jìn)化論中 “物競天擇,適者生存 ”的自然進(jìn)化法則發(fā)展而來。其基本精神是 進(jìn)化與選擇,利用復(fù)制( reproduction )、交配( crossover )、突變( mutat ion ) 三個基本運算元重復(fù)運作, 以
27、達(dá)到淘汰較差解的目的。 其做法是: 先由數(shù)個可行 解個體產(chǎn)生一母體集合,其中的元素即為基因(gene )。再通過計算第一代母 體中個體目標(biāo)值的方式,選出較優(yōu)秀的個體,以交配、突變等方式產(chǎn)生下一代。 最后依據(jù)停止條件結(jié)束演算。 遺傳算法具有多點平行搜尋可行解的特性, 已逐漸 被運用于高度空間搜尋的組合最佳化問題上。模擬退火算法(Simulated Ann eali ng ,SA),其最初的思想由 Metropolis在 1953 年提出, Kirkpatrick 等人19 在 1983 年成功地將其應(yīng)用在組合最優(yōu)化問題 中。模擬退火算法來源于固體退火原理: 將固體加溫至充分高, 再讓其徐徐冷卻,
28、 加溫時, 固體內(nèi)部粒子隨溫升變?yōu)闊o序狀, 內(nèi)能增大, 而徐徐冷卻時粒子漸趨有 序,在每個溫度都達(dá)到平衡態(tài),最后在常溫時達(dá)到基態(tài),內(nèi)能減為最小。用固體 退火模擬組合優(yōu)化問題,將內(nèi)能 E模擬為目標(biāo)函數(shù)值f,溫度T演化成控制參數(shù) t,由初始解i和控制參數(shù)t的初值開始,對當(dāng)前解重復(fù) 產(chǎn)生新解計算目標(biāo)函 數(shù)差一接受或舍棄”的迭代,逐步衰減t值,并設(shè)定終止條件,即得到解組合優(yōu) 化問題的模擬退火算法。 算法終止時的當(dāng)前解即為所得近似最優(yōu)解, 這是基于蒙 特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。模擬退火算法具有能往目標(biāo)值較差處移動的機(jī)會, 這種隨機(jī)過程產(chǎn)生的機(jī)會使得 該算法有能力避免陷入局部優(yōu)化,而得到全
29、局最優(yōu)解。禁忌搜索法( Tabu Search, TS ),是由 Glover20 于 1977 年提出的, Willard 21 于 1989 年將其用于車輛路徑問題上。其求解的過程是先求得一初始解,然后在 鄰域中搜索較佳解或是移動到較差的區(qū)域搜索該區(qū)域最佳解, 并且記錄曾經(jīng)搜尋 的路徑,作為下次搜索的依據(jù), 以避免陷入局部最優(yōu)解中。 禁忌搜索算法主要包 含移步(Move)、候選列表(Can didate List)、禁忌列表(Tabu List)、渴望 準(zhǔn)則( Aspiration Level )及搜尋停止準(zhǔn)則( Stopping Criterion )等五種要素。 蟻群算法( Ant S
30、ystem, AS )最早由 Macro Dorigo22 于 1992 年提出,其靈感 來自螞蟻覓食時可以在食物和巢穴間找到最短路徑的能力。 螞蟻覓食時會在走過 的路線上留下一種稱為費洛蒙 ( pheromone )的化學(xué)物質(zhì), 費洛蒙的濃度與遺留 時間成反比,與走過該路線的螞蟻的數(shù)量成正比。 當(dāng)一只螞蟻面臨路線的選擇時, 它會優(yōu)先選取費洛蒙濃度高的路線。 就是說, 費洛蒙殘留的濃度越高, 則吸引螞 蟻前來的能力越強(qiáng),越多的螞蟻經(jīng)過某條路線時,該路線的費洛蒙濃度就越高, 從而吸引更多的螞蟻前來。 通過這種方式, 螞蟻就可找出食物與巢穴間的最短路 徑。2.4.3 混合啟發(fā)式算法 一是、基于數(shù)學(xué)
31、規(guī)劃的算法( Mathematical-Programming Based ) 6 是把問題 直接描述成一個數(shù)學(xué)規(guī)劃問題, 根據(jù)其模型的特殊構(gòu)形, 應(yīng)用一定的技術(shù) (如分 解)進(jìn)行分劃,進(jìn)而求解已被廣泛研究過的子問題。典型的有 Fisher 和 Jaikumar 提出的算法。該算法把車輛路線問題構(gòu)造為一個廣 義分派問題, 并提出下述啟發(fā)式算法: 首先把問題描述為一個數(shù)學(xué)規(guī)劃問題, 再 將問題分解成一個旅行商問題和一個分派問題。 對每一輛車將顧客進(jìn)行分派, 這 通過解一般分派問題來得到。 每輛車為它的顧客服務(wù), 以一個近似等于旅行商線 路的費用為目標(biāo), 分派一旦做出, 通過應(yīng)用一些旅行商問題的啟
32、發(fā)式算法或優(yōu)化 算法來得到每輛車的行車路線。二是、交互式優(yōu)化法 6 。即把人的因素結(jié)合到問題的求解過程中,其思想是; 有經(jīng)驗的決策者應(yīng)具有確定和修改參數(shù)的能力, 并且根據(jù)知識經(jīng)驗, 把主觀的估 計加到優(yōu)化模型中去。這通常會增加模型最終實現(xiàn)并被采用的可能性。 如 Cuilew, Jarvis 和 Ratfiff 提出的兩段法: 第一階段: 由有經(jīng)驗的調(diào)度員或是根據(jù)自動生成 規(guī)則選定一些 “組”點,目標(biāo)函數(shù)定義為線性近似 ( ),其中 定義為需求點 i 和“組 點”之間的歐氏距離,根據(jù)確定的 組”點坐標(biāo)求解得出的分派問題,由求出的結(jié) 果再求解得出的定點問題,即重新確定每個 “組”點的位置,以使分派
33、給它的各需 求點離它的總距離最小。 交替求解分派問題和定點問題, 直到目標(biāo)沒有進(jìn)一步的 改進(jìn)。第二階段:用列生成技術(shù)生成新解,直到不能進(jìn)一步改進(jìn)為止。 這幾種啟發(fā)式算法常不是絕對劃分的,有的方法同屬于好幾類。4.1.1 算法描述 模擬退火算法是一種用于求解大規(guī)模優(yōu)化問題的隨機(jī)搜索算法, 它以優(yōu)化問題求 解過程與物理系統(tǒng)退火過程之間的相似性為基礎(chǔ); 優(yōu)化的目標(biāo)函數(shù)相當(dāng)于金屬的 內(nèi)能;優(yōu)化問題的自變量組合狀態(tài)空間相當(dāng)于金屬的內(nèi)能狀態(tài)空間; 問題的求解 過程就是找一個組合狀態(tài), 使目標(biāo)函數(shù)值最小。 大量的研究證明, 模擬退火算法 可在多項式時間內(nèi)求解全局優(yōu)化問題的目標(biāo)。模擬退火算法來源于固體退火原理
34、, 將固體加溫至充分高, 再讓其徐徐冷卻, 加 溫時,固體內(nèi)部粒子隨溫升變?yōu)闊o序狀, 內(nèi)能增大,而徐徐冷卻時粒子漸趨有序, 在每個溫度都達(dá)到平衡態(tài), 最后在常溫時達(dá)到基態(tài), 內(nèi)能減為最小。 用固體退火 模擬組合優(yōu)化問題,將內(nèi)能E模擬為目標(biāo)函數(shù)值f,溫度T演化成控制參數(shù)t, 即得到解組合優(yōu)化問題的模擬退火算法:由初始解 i和控制參數(shù)初值t開始,對 當(dāng)前解重復(fù) 產(chǎn)生新解一計算目標(biāo)函數(shù)差一接受或舍棄”的迭代,并逐步衰減t值, 算法終止時的當(dāng)前解即為所得近似最優(yōu)解, 這是基于蒙特卡羅迭代求解法的一種 啟發(fā)式隨機(jī)搜索過程。模擬退火算法需要一個構(gòu)建好的初始解作為算法的輸入?yún)?shù), 在進(jìn)入迭代后, 每 一次迭
35、代都需要構(gòu)建新解。 本文用最臨近點法來構(gòu)建初始解, 用區(qū)域搜索法來求 得每一次迭代的新解 28 。分別論述如下:1)最臨近點法構(gòu)建初始解:從盆景養(yǎng)護(hù)基地出發(fā),尋找距離它最近的客戶,生 成一條線路;再從該客戶出發(fā),尋找他的最臨近客戶,加入該線路。重復(fù)該過程 直到滿足車輛的最大裝載容量限制 (同時考慮時間窗限制和車輛的最大行駛距離 限制),即完成一條線路的構(gòu)建。返回盆景養(yǎng)護(hù)基地,重復(fù)以上步驟繼續(xù)構(gòu)建線 路,直到所有的客戶都被加入線路中,則初始解的構(gòu)建就完成了。2)區(qū)域搜索法產(chǎn)生新解:區(qū)域搜索法是通過不斷改善路經(jīng)來求得更佳的解,并 以貪婪法則決定是否接受新的改善解。 改善的方法是在同一條線路中隨機(jī)交
36、換節(jié) 點,或在相鄰線路中隨機(jī)交換節(jié)點。有2-opt交換法、3-opt交換法以及Cross-opt 交換法,本文采用 2-opt 交換法。4.1.2 算法步驟 模擬退火算法的主要步驟如下 29 :1)初始化:初始溫度 (充分大 ),初始解狀態(tài) (是算法迭代的起點 ), 每個 值的 迭代次數(shù) ;2)對 重復(fù)以下第 (3)至第(6)步;3)產(chǎn)生新解 ;4)計算增量 ,其中 為評價函數(shù);5)若 則接受 作為新的當(dāng)前解,否則以概率 接受 作為新的當(dāng)前解;6)如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解,結(jié)束程序。終止條件通常取為 連續(xù)若干個新解都沒有被接受時終止算法。否則執(zhí)行下面第 (7) 步;7)逐漸衰減(
37、趨于零),然后轉(zhuǎn)第 (2) 步。4.1.3 重點抽樣與 Metroplis 準(zhǔn)則模擬退火的主要思想是: 在搜索區(qū)間(二維平面中) 隨機(jī)游走(即隨機(jī)選擇點) , 再以 Metropolis 準(zhǔn)則抽樣,使隨機(jī)游走逐漸收斂于局部最優(yōu)解。Metropolis 抽樣準(zhǔn)則是一種有效的重點抽樣法。其思想為:系統(tǒng)從一種狀態(tài)變到 另一種狀態(tài)時,相應(yīng)的能量從 變化到 ,如果 ,系統(tǒng)接收此狀態(tài),否則,以 的 概率接收或丟棄此狀態(tài)。經(jīng)過一定次數(shù)的迭代,系統(tǒng)會逐漸趨于穩(wěn)定狀態(tài)。 重點抽樣時,新狀態(tài)如果向下則接受(局部最優(yōu)),若向上(全局搜索),以一 定概率接受。 模擬退火方法從某個初始解出發(fā), 經(jīng)過大量解的變換后, 可
38、以求得 給定控制參數(shù)值時組合優(yōu)化問題的相對最優(yōu)解。然后減小控制參數(shù) 的值,重復(fù) 執(zhí)行 Metropolis 算法,就可以在控制參數(shù) T 趨于零時,最終求得組合優(yōu)化問題 的整體最優(yōu)解。控制參數(shù)的值必須緩慢衰減。溫度是 Metropolis 算法的重要控制參數(shù)。開始時溫度高 ( 值大 ),算法可能接受 較差的惡化解;隨著 值的減小,只能接受較好的惡化解;最后當(dāng) 趨于 0 時,就 不再接受任何惡化解了。當(dāng) 值足夠大時(即無限高溫),系統(tǒng)立即均勻分布,接受所有提出的變換。 衰 減得越小, 到達(dá)終點的時間就越長, 但可使馬可夫鏈縮短, 使到達(dá)準(zhǔn)平衡分布的 時間縮短。4.1.4 算法重點和難點 模擬退火算法的重點是新解的產(chǎn)生和接受。主要有以下四個步驟: 其一、由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生下一個位于解空間的新解。 為便于后續(xù)的計 算和接受, 減少算法耗時, 通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的 方法,如對構(gòu)成新解的全部或部分元素進(jìn)行置換、 互換等。 產(chǎn)生新解的變換方法 決定了當(dāng)前解的鄰域結(jié)構(gòu),因而對冷卻進(jìn)度表的選取有一定的影響。其二、計算與新解所對應(yīng)的目標(biāo)函數(shù)差。 因為目標(biāo)函數(shù)差僅由變
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 白堊粉市場環(huán)境與對策分析
- 玩耍用玩具娃娃市場環(huán)境與對策分析
- 電子永動器永磁擺動玩具相關(guān)項目實施方案
- 照明設(shè)備和裝置項目可行性實施報告
- 工業(yè)包裝容器用木制蓋子相關(guān)項目建議書
- 狩獵用誘餌相關(guān)項目實施方案
- 殘疾人移位專用吊索相關(guān)項目建議書
- 用作毒藥解毒劑的活性炭項目評價分析報告
- 成都師范學(xué)院《嬰幼兒護(hù)理與急救》2022-2023學(xué)年第一學(xué)期期末試卷
- 成都師范學(xué)院《實變函數(shù)》2023-2024學(xué)年第一學(xué)期期末試卷
- 新生兒配方奶喂養(yǎng) 課件
- 《京劇的誕生與發(fā)展》課件
- 產(chǎn)業(yè)投資概述課件
- 空壓機(jī)崗位操作規(guī)程模版
- 小學(xué)高年級數(shù)學(xué)作業(yè)設(shè)計研究
- 宿遷市泗陽縣2022-2023學(xué)年高一上學(xué)期11月期中數(shù)學(xué)試題(解析版)
- 中國動態(tài)血糖監(jiān)測臨床應(yīng)用指南
- photoshop軟件市場調(diào)研報告
- 防靜電衣管理制度
- 2024年北京農(nóng)商銀行招聘筆試參考題庫含答案解析
- ??谱o(hù)理技術(shù)操作常見并發(fā)癥的處理
評論
0/150
提交評論