系統(tǒng)工程 課件 模塊五 系統(tǒng)優(yōu)化

系統(tǒng)工程模塊五系統(tǒng)優(yōu)化知識(shí)結(jié)構(gòu)導(dǎo)圖（1）理解系統(tǒng)優(yōu)化的含義；（2）掌握總成本分析法、綜合評(píng)價(jià)法運(yùn)輸方式的選擇；（3）理解單車輛路徑優(yōu)化問題；（4）掌握分枝定界法、簡單貪夢(mèng)算法、奇偶點(diǎn)圖上作業(yè)法、動(dòng)態(tài)規(guī)劃法、標(biāo)號(hào)法的單車輛路徑優(yōu)化問題求解；（5）理解多車輛路徑優(yōu)化問題；（6）掌握掃描法、節(jié)約里程法的多車輛路徑優(yōu)化問題求解。教學(xué)目標(biāo)重點(diǎn)（1）運(yùn)輸方式的選擇；（2）單車輛路徑優(yōu)化；（3）多車輛路徑優(yōu)化。難點(diǎn)（1）總成本分析法、綜合評(píng)價(jià)法；（2）分枝定界法、奇偶點(diǎn)圖上作業(yè)法、動(dòng)態(tài)規(guī)劃法；（3）掃描法、節(jié)約里程法、單設(shè)施選址規(guī)劃。系統(tǒng)優(yōu)化的認(rèn)識(shí)任務(wù)一知識(shí)結(jié)構(gòu)導(dǎo)圖一、系統(tǒng)優(yōu)化的含義系統(tǒng)優(yōu)化是在滿足各方面限制條件的情況下，通過科學(xué)的方法，建立與現(xiàn)實(shí)系統(tǒng)相對(duì)應(yīng)的數(shù)學(xué)模型，并合理確定模型的各種參數(shù)，以協(xié)調(diào)各子系統(tǒng)之間的沖突，達(dá)到最佳設(shè)計(jì)目標(biāo)的過程。系統(tǒng)優(yōu)化與系統(tǒng)規(guī)劃的區(qū)別就在于：系統(tǒng)規(guī)劃是從無到有，系統(tǒng)優(yōu)化是對(duì)現(xiàn)有系統(tǒng)存在的不同方面的問題進(jìn)行針對(duì)性的分析，進(jìn)而構(gòu)建優(yōu)化模型并求解，最終使現(xiàn)有系統(tǒng)得到優(yōu)化。二、系統(tǒng)優(yōu)化的方法規(guī)劃論又稱為數(shù)學(xué)規(guī)劃，是運(yùn)籌學(xué)的一個(gè)分支，是研究對(duì)現(xiàn)有資源進(jìn)行統(tǒng)一分配、合理安排、合理調(diào)度和最優(yōu)設(shè)計(jì)以取得最大經(jīng)濟(jì)效果的數(shù)學(xué)理論方法。例如，對(duì)某項(xiàng)確定的任務(wù)，怎樣以最少的人力、物力去完成；對(duì)給定的人力、物力，怎樣能使其最大限度地發(fā)揮作用，從而完成盡可能多的任務(wù)。一般規(guī)劃論可以歸結(jié)為在滿足既定目標(biāo)的要求下，按照某一衡量指標(biāo)尋求最優(yōu)方案的問題。通常把必須滿足的條件稱為約束條件，把衡量指標(biāo)稱為目標(biāo)函數(shù)，用數(shù)學(xué)語言來描述為：求目標(biāo)函數(shù)在一定約束條件下的極值問題。（一）運(yùn)籌學(xué)方法1.規(guī)劃論圖論（GraphTheory）是數(shù)學(xué)的一個(gè)分支，它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間的關(guān)系。圖論也稱為網(wǎng)絡(luò)法，把復(fù)雜的問題轉(zhuǎn)化成圖形直觀地表現(xiàn)出來，能更有效地解決問題。圖論常用來解決各類最優(yōu)化問題，例如，如何使完成任務(wù)的時(shí)間最少、距離最短、費(fèi)用最省等。（一）運(yùn)籌學(xué)方法2.圖論二、系統(tǒng)優(yōu)化的方法排隊(duì)論（QueuingTheory）又稱隨機(jī)服務(wù)系統(tǒng)理論，是運(yùn)籌學(xué)的一個(gè)分支。它是研究系統(tǒng)隨機(jī)聚散現(xiàn)象和隨機(jī)服務(wù)系統(tǒng)工作過程的數(shù)學(xué)理論和方法，通過對(duì)服務(wù)對(duì)象到來及服務(wù)時(shí)間的統(tǒng)計(jì)研究，得出這些數(shù)量指標(biāo)（等待時(shí)間、排隊(duì)長度、忙期長短等）的統(tǒng)計(jì)規(guī)律，然后根據(jù)這些規(guī)律來改進(jìn)服務(wù)系統(tǒng)的結(jié)構(gòu)或重新組織被服務(wù)對(duì)象，使得服務(wù)系統(tǒng)既能滿足服務(wù)對(duì)象的需要，又能使機(jī)構(gòu)的費(fèi)用最經(jīng)濟(jì)或某些指標(biāo)最優(yōu)。（一）運(yùn)籌學(xué)方法3.排隊(duì)論二、系統(tǒng)優(yōu)化的方法排隊(duì)論是研究服務(wù)系統(tǒng)中排隊(duì)現(xiàn)象隨機(jī)規(guī)律的學(xué)科，專門研究因隨機(jī)因素而產(chǎn)生擁擠的方法，可協(xié)調(diào)和解決請(qǐng)求服務(wù)和提供服務(wù)雙方之間存在的相互約束關(guān)系。排隊(duì)論廣泛應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)、生產(chǎn)、運(yùn)輸、庫存等各項(xiàng)資源共享的隨機(jī)服務(wù)系統(tǒng)，如旅客購票排隊(duì)、市內(nèi)電話占線等現(xiàn)象。排隊(duì)論研究的內(nèi)容有3個(gè)方面：統(tǒng)計(jì)推斷，根據(jù)資料建立模型；系統(tǒng)的性態(tài)，即和排隊(duì)有關(guān)的數(shù)量指標(biāo)的概率的規(guī)律性；系統(tǒng)的優(yōu)化問題。排隊(duì)論的目的是正確設(shè)計(jì)和有效運(yùn)行各個(gè)服務(wù)系統(tǒng)，使之發(fā)揮最佳效益。（一）運(yùn)籌學(xué)方法3.排隊(duì)論二、系統(tǒng)優(yōu)化的方法為了解決供應(yīng)（生產(chǎn)）與需求（消費(fèi)）之間的不協(xié)調(diào)（這種不協(xié)調(diào)一般表現(xiàn)為供應(yīng)量與需求量和供應(yīng)時(shí)期與需求時(shí)期的不一致，出現(xiàn)供不應(yīng)求或供過于求），人們?cè)诠?yīng)與需求這兩個(gè)環(huán)節(jié)之間加入存儲(chǔ)這一環(huán)節(jié)，就能緩解供應(yīng)與需求之間的不協(xié)調(diào)。以此為研究對(duì)象，利用運(yùn)籌學(xué)的方法即可解決最合理、最經(jīng)濟(jì)的存儲(chǔ)問題。專門研究這類有關(guān)存儲(chǔ)問題的科學(xué)叫作存儲(chǔ)論，它也是運(yùn)籌學(xué)的一個(gè)分支。存儲(chǔ)論也稱為庫存論，是主要研究物資庫存策略的理論，用于確定物資庫存量、補(bǔ)貨頻率和補(bǔ)貨量等問題。庫存的目的是為生產(chǎn)經(jīng)營活動(dòng)的持續(xù)進(jìn)行提供有力的保障。（一）運(yùn)籌學(xué)方法4.存儲(chǔ)論二、系統(tǒng)優(yōu)化的方法智能優(yōu)化算法從與研究問題有關(guān)的基本模型和算法中獲得啟發(fā)，發(fā)現(xiàn)解決問題的思路和途徑，通過對(duì)過去經(jīng)驗(yàn)的歸納推理以及試驗(yàn)分析來解決問題。具體邏輯思路如圖5-1所示。（二）啟發(fā)式算法1.智能優(yōu)化算法二、系統(tǒng)優(yōu)化的方法圖5-1智能優(yōu)化算法的邏輯思路圖模擬退火算法（SimulatedAnnealing，SA）最早的思想是由N.Metropoli松等人于1953年提出的。該算法來源于固體退火原理，是一種基于概率的算法，將固體加熱至充分高溫，再讓其徐徐冷卻，加熱時(shí)，固體內(nèi)部粒子隨溫度升高變?yōu)闊o序狀，內(nèi)能增大；在徐徐冷卻時(shí)粒子漸趨有序，冷卻過程中每個(gè)粒子都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。（二）啟發(fā)式算法2.模擬退火算法二、系統(tǒng)優(yōu)化的方法用模擬退火算法尋找最優(yōu)解的過程類似于退火現(xiàn)象中尋找系統(tǒng)的最低能量，把優(yōu)化問題的狀態(tài)看作固體內(nèi)部的粒子，把目標(biāo)函數(shù)看作粒子所處的能態(tài)，得到的最優(yōu)解對(duì)應(yīng)于固體最后在常溫時(shí)達(dá)到的基態(tài)。具體邏輯思路如圖5-2所示。（二）啟發(fā)式算法二、系統(tǒng)優(yōu)化的方法圖5-2模擬退火算法的邏輯思路圖2.模擬退火算法遺傳算法（GeneticAlgorithm，GA）最早是由美國的JohnHolland于20世紀(jì)70年代提出的。該算法是根據(jù)大自然中生物體的進(jìn)化規(guī)律而設(shè)計(jì)提出的，是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)制的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。具體邏輯思路如圖5-3所示。（二）啟發(fā)式算法二、系統(tǒng)優(yōu)化的方法圖5-3遺傳算法的邏輯思路圖3.遺傳算法遺傳算法通過數(shù)學(xué)的方式，利用計(jì)算機(jī)進(jìn)行仿真運(yùn)算，將問題的求解過程轉(zhuǎn)換成類似于生物進(jìn)化中染色體基因的交叉、變異等過程。在求解較為復(fù)雜的組合優(yōu)化問題時(shí)，與一些常規(guī)的優(yōu)化算法相比，遺傳算法通常能夠較快獲得較好的優(yōu)化結(jié)果。目前，遺傳算法已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。（二）啟發(fā)式算法二、系統(tǒng)優(yōu)化的方法3.遺傳算法蟻群算法的靈感來自螞蟻尋找最短覓食路徑的過程。蟻群在覓食過程中會(huì)在所經(jīng)過的路徑上留下一種揮發(fā)性分泌物——信息素，信息素能被一定范圍內(nèi)的螞蟻察覺并影響它們的行為。當(dāng)一些路徑上通過的螞蟻越來越多時(shí)，其信息素的強(qiáng)度也越來越大，這樣其他螞蟻選擇該路徑的概率也越來越高。它們不斷發(fā)現(xiàn)更短路徑，逐漸地，這一條最短路徑就會(huì)被大多數(shù)螞蟻重復(fù)，從而形成最短路徑。（二）啟發(fā)式算法二、系統(tǒng)優(yōu)化的方法4.蟻群算法系統(tǒng)仿真法是一種根據(jù)被研究的系統(tǒng)模型，在仿真環(huán)境和條件下，對(duì)系統(tǒng)進(jìn)行研究、分析和試驗(yàn)的方法。系統(tǒng)仿真法按照系統(tǒng)模型的載體種類分為物理仿真、數(shù)學(xué)仿真和半實(shí)物仿真；按照系統(tǒng)模型特性分為連續(xù)系統(tǒng)仿真和離散事件系統(tǒng)仿真。不難發(fā)現(xiàn)，其實(shí)很多系統(tǒng)優(yōu)化的方法同樣適用于系統(tǒng)規(guī)劃的問題研究，因此這些方法都不是專屬于誰的。（三）系統(tǒng)仿真法二、系統(tǒng)優(yōu)化的方法系統(tǒng)的優(yōu)化過程其實(shí)也是一種系統(tǒng)的重新規(guī)劃過程，因此也同樣包括物資調(diào)配、指派、運(yùn)輸系統(tǒng)優(yōu)化、設(shè)施選址與布局等內(nèi)容。系統(tǒng)優(yōu)化的重點(diǎn)內(nèi)容是運(yùn)輸系統(tǒng)優(yōu)化，即：三、系統(tǒng)優(yōu)化的內(nèi)容（一）路徑優(yōu)化（三）運(yùn)輸方式選擇（二）車輛調(diào)度（四）路網(wǎng)規(guī)劃路徑優(yōu)化就是在滿足一系列約束條件的情況下，合理安排運(yùn)輸車輛的行車路徑和時(shí)間，使得車輛把客戶需要的貨物從一個(gè)或者多個(gè)物流中心運(yùn)送到多個(gè)地理上分散的客戶點(diǎn)上，并達(dá)到特定的目標(biāo)（通常是路程最短、運(yùn)費(fèi)最省、時(shí)間最短等）的過程。路徑優(yōu)化主要包括：（1）起詭點(diǎn)相同的單一車輛路徑優(yōu)化問題，比如旅行商問題、中國郵遞員問題、庫內(nèi)最短揀選路徑問題等。（2）起詭點(diǎn)相同的多車輛配送路徑優(yōu)化問題。（3）起詭點(diǎn)不同的單一車輛路徑優(yōu)化問題，比如配送網(wǎng)絡(luò)最大流量問題、配送網(wǎng)絡(luò)最小費(fèi)用問題。三、系統(tǒng)優(yōu)化的內(nèi)容（一）路徑優(yōu)化車輛的調(diào)度就是如何配置車輛，才能使得其既能滿足運(yùn)輸需求，又能最經(jīng)濟(jì)。通?？梢圆捎弥概蓡栴}建模求解的方法、多車輛路徑優(yōu)化問題建模求解的方法等進(jìn)行建模求解。三、系統(tǒng)優(yōu)化的內(nèi)容（二）車輛調(diào)度三、系統(tǒng)優(yōu)化的內(nèi)容（三）運(yùn)輸方式選擇當(dāng)有多種可選擇的運(yùn)輸方式時(shí)，選擇最優(yōu)的運(yùn)輸方式，通常采用總成本分析法、綜合評(píng)價(jià)法等進(jìn)行選擇。假設(shè)給定一些城市，已知每對(duì)城市之間交通線的建造費(fèi)用，要求建造一個(gè)連接這些城市的交通網(wǎng)，且使得總的建造費(fèi)用最小，這就是賦權(quán)圖上的最小生成樹問題。這類問題的求解過程也就是路網(wǎng)規(guī)劃的過程。三、系統(tǒng)優(yōu)化的內(nèi)容（四）路網(wǎng)規(guī)劃運(yùn)輸方式的選擇任務(wù)二知識(shí)結(jié)構(gòu)導(dǎo)圖總成本分析法的要旨是在保持一定服務(wù)水平的條件下，考慮所有有關(guān)成本的項(xiàng)目。對(duì)備選方案進(jìn)行評(píng)價(jià)時(shí)，各種不同方案可能會(huì)導(dǎo)致某些業(yè)務(wù)活動(dòng)的成本增加、減少，或保持不變。該方法的目標(biāo)是選擇總成本最小的方案。由于系統(tǒng)運(yùn)作各環(huán)節(jié)之間的效益相恃，某環(huán)節(jié)成本降低會(huì)導(dǎo)致其他環(huán)節(jié)成本上升，因此需要以總成本分析法為基礎(chǔ)來選擇運(yùn)輸方式。所謂最佳運(yùn)輸服務(wù)，就是使某種運(yùn)輸成本與該運(yùn)輸服務(wù)水平以及相關(guān)的庫存成本之間達(dá)到平衡的服務(wù)，也就是選擇既能滿足客戶需求，又使總成本最低的運(yùn)輸服務(wù)。這是總成本分析法的基本思想。（一）方法介紹一、總成本分析法的運(yùn)輸方式的選擇（1）計(jì)算各方案的年運(yùn)輸成本：（二）總成本分析法選擇運(yùn)輸方式的步驟一、總成本分析法的運(yùn)輸方式的選擇運(yùn)輸成本=運(yùn)輸費(fèi)率×年需求量（2）計(jì)算各方案的在途庫存成本：在途庫存成本=在途庫存價(jià)值×保管費(fèi)率=運(yùn)輸批量×出廠單價(jià)×保管費(fèi)率運(yùn)輸批量=供貨期間需求量=訂貨批量運(yùn)輸批量=訂貨批量當(dāng)訂貨周期=運(yùn)輸時(shí)間時(shí)：當(dāng)訂貨周期≠運(yùn)輸時(shí)間時(shí)：（3）計(jì)算各方案的供貨工廠的存貨成本：（二）總成本分析法選擇運(yùn)輸方式的步驟一、總成本分析法的運(yùn)輸方式的選擇

其中，工廠的期初庫存水平是指已訂待發(fā)的訂貨量，期末庫存水平指發(fā)貨后工廠已訂待發(fā)的量（發(fā)貨后即為0）。另外，通常工廠存貨安全庫存考慮為0。（二）總成本分析法選擇運(yùn)輸方式的步驟一、總成本分析法的運(yùn)輸方式的選擇（3）計(jì)算各方案的供貨工廠的存貨成本：在EOQ模型（EconomicOrderQuantity，經(jīng)濟(jì)訂貨批量，EOQ模型用于研究在什么時(shí)間、以多少數(shù)量、從什么來源補(bǔ)充庫存，使得庫存和補(bǔ)充采購的總費(fèi)用少，再通過費(fèi)用分析求得庫存總費(fèi)用最小時(shí)的每次訂貨批量?，F(xiàn)代化生產(chǎn)管理中，常用EOQ模型確定訂貨批量）中，運(yùn)輸批量—訂貨批量，即Q=EOQ。（4）計(jì)算各方案的需求倉庫存貨成本：（二）總成本分析法選擇運(yùn)輸方式的步驟一、總成本分析法的運(yùn)輸方式的選擇倉庫存貨成本=倉庫平均庫存價(jià)值×保管費(fèi)率

=倉庫平均庫存水平×（出廠單價(jià)+運(yùn)輸費(fèi)率）×保管費(fèi)率

（二）總成本分析法選擇運(yùn)輸方式的步驟一、總成本分析法的運(yùn)輸方式的選擇（4）計(jì)算各方案的需求倉庫存貨成本：其中：到貨量=訂貨批量=運(yùn)輸批量運(yùn)輸批量=供求期間需求量運(yùn)輸批量=訂貨批量當(dāng)訂貨周期=運(yùn)輸時(shí)間時(shí)：當(dāng)訂貨周期≠運(yùn)輸時(shí)間時(shí)在EOQ模型中，訂貨批量=運(yùn)輸批量，即Q=EOQ。（二）總成本分析法選擇運(yùn)輸方式的步驟一、總成本分析法的運(yùn)輸方式的選擇（5）計(jì)算各方案的庫存成本：（6）計(jì)算各方案的總成本：（7）對(duì)比各方案的總成本，選擇總成本最小的方案。庫存成本=在途庫存成本+供貨工廠存貨成本+倉庫存貨成本總成本=運(yùn)輸成本+庫存成本【例5-1】某公司欲將產(chǎn)品從位置A的工廠運(yùn)往位置B的公司自有倉庫，年需求量D=700000件，產(chǎn)品單價(jià)C=30元，年存貨成本I=產(chǎn)品價(jià)格的30%。公司希望選擇使總成本最小的運(yùn)輸方式。據(jù)估計(jì)，運(yùn)輸時(shí)間每減少一天，平均庫存成本可以減少1%。各種運(yùn)輸服務(wù)方式的有關(guān)參數(shù)如表5-1所示（表5-1見教材195頁）。本案例中沒有安全庫存，因此，平均存貨量=運(yùn)輸批量/2，請(qǐng)基于總成本選擇最優(yōu)的運(yùn)輸方式。（三）舉例一、總成本分析法的運(yùn)輸方式的選擇

（三）舉例一、總成本分析法的運(yùn)輸方式的選擇（3）計(jì)算各方案的供貨工廠的存貨成本。根據(jù)計(jì)算公式“供貨工廠存貨成本=供貨工廠平均庫存水平×出廠單價(jià)×保管費(fèi)率，平均庫存調(diào)整系數(shù)=1-減少的運(yùn)輸天數(shù)×1%”可得，鐵路運(yùn)輸?shù)墓┴浌S存貨成本=35000×1×30×30%元=315000元，以此類推，計(jì)算結(jié)果如表5-4所示（表5-4見教材156頁）。（4）計(jì)算各方案的需求倉庫存貨成本。根據(jù)計(jì)算公式“倉庫存貨成本=倉庫平均庫存水平×（出廠單價(jià)+運(yùn)輸費(fèi)率）×保管費(fèi)率”可得，鐵路運(yùn)輸?shù)男枨髠}庫存貨成本=35000×1×（0.1+30）×30%元=316050元，以此類推，計(jì)算結(jié)果如表5-5所示（表5-5見教材197頁）。（三）舉例一、總成本分析法的運(yùn)輸方式的選擇（5）計(jì)算各方案的庫存成本。根據(jù)計(jì)算公式“庫存成本=在途庫存成本+供貨工廠存貨成本+倉庫存貨成本”可得，鐵路運(yùn)輸?shù)膸齑娉杀?630000+315000+316050元=1261050元，以此類推，計(jì)算結(jié)果如表5-6所示。（6）計(jì)算各方案的總成本。根據(jù)計(jì)算公式“總成本—運(yùn)輸成本+庫存成本”可得，鐵路運(yùn)輸?shù)目偝杀?70000+1261050元=1331050元，以此類推，計(jì)算結(jié)果如表5-7所示。（7）對(duì)比各方案的總成本，選擇總成本最小的方案。根據(jù)表中的結(jié)果可以看出，總成本最小的運(yùn)輸方式是馱背運(yùn)輸，總成本為713682元，因此選擇馱背運(yùn)輸。（表5-6、5-7見教材197頁）（三）舉例一、總成本分析法的運(yùn)輸方式的選擇（一）方法介紹二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇1.定義綜合評(píng)價(jià)法是運(yùn)用多個(gè)指標(biāo)對(duì)多個(gè)參評(píng)單位進(jìn)行綜合統(tǒng)計(jì)評(píng)價(jià)的方法，用來判斷企業(yè)的走向和目標(biāo)。（一）方法介紹二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇2.主要要素（1）評(píng)價(jià)者：可以是某個(gè)人或某個(gè)團(tuán)體。評(píng)價(jià)目的的給定、評(píng)價(jià)指標(biāo)的建立、評(píng)價(jià)模型的選擇、權(quán)重系數(shù)的確定都與評(píng)價(jià)者有關(guān)。（2）被評(píng)價(jià)對(duì)象：隨著綜合評(píng)價(jià)技術(shù)理論的發(fā)展與實(shí)踐活動(dòng)的開展，評(píng)價(jià)的領(lǐng)域也從最初的各行各業(yè)經(jīng)濟(jì)統(tǒng)計(jì)的綜合評(píng)價(jià)拓展到后來的技術(shù)水平、生活質(zhì)量、社會(huì)發(fā)展、環(huán)境質(zhì)量、競(jìng)爭能力、綜合國力、績效考評(píng)等方面，這些都可以為被評(píng)價(jià)對(duì)象。（3）評(píng)價(jià)指標(biāo)：從多個(gè)視角和層次反映特定評(píng)價(jià)客體的數(shù)量規(guī)模與數(shù)量水平。（4）權(quán)重系數(shù)：其合理與否關(guān)系到綜合評(píng)價(jià)結(jié)果的可信程度。（5）綜合評(píng)價(jià)模型：是指通過一定的數(shù)學(xué)模型，將多個(gè)評(píng)價(jià)指標(biāo)值合成為一個(gè)整體性的綜合評(píng)價(jià)值。（一）方法介紹二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇3.步驟（1）確定綜合評(píng)價(jià)指標(biāo)體系，這是綜合評(píng)價(jià)的基礎(chǔ)和依據(jù)。（2）收集數(shù)據(jù)，指標(biāo)同度量處理，確定指標(biāo)體系中各指標(biāo)的權(quán)數(shù)，以保證評(píng)價(jià)的科學(xué)性。常用的權(quán)重確定方法有層次分析法（AHP）、專家打分法、問卷調(diào)查法等。（3）選擇適當(dāng)模型計(jì)算綜合評(píng)價(jià)指標(biāo)。常見的綜合評(píng)價(jià)模型主要有綜合指數(shù)法、加權(quán)綜合法、功效系數(shù)法、Topsis法、密切值法、AHP、模糊綜合評(píng)價(jià)法、秩和比法等。（4）根據(jù)綜合評(píng)價(jià)指標(biāo)值或分值的大小，對(duì)被評(píng)價(jià)對(duì)象進(jìn)行排序，并由此得出結(jié)論。（二）綜合評(píng)價(jià)法選擇運(yùn)輸方式的步驟二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇（1）確定影響運(yùn)輸方式選擇的因素，即評(píng)價(jià)指標(biāo)體系，主要考慮經(jīng)濟(jì)性、迅速性、安全性、便利性，當(dāng)然還有環(huán)境影響、社會(huì)效益等。

經(jīng)濟(jì)性主要表現(xiàn)為費(fèi)用（運(yùn)輸費(fèi)、裝卸費(fèi)、包裝費(fèi)、管理費(fèi)等）的節(jié)省，在運(yùn)輸過程中總費(fèi)用支出越少，則經(jīng)濟(jì)性越好。

（二）綜合評(píng)價(jià)法選擇運(yùn)輸方式的步驟二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇

（二）綜合評(píng)價(jià)法選擇運(yùn)輸方式的步驟二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇迅速性指貨物從發(fā)貨地到收貨地所需要的時(shí)間，即貨物的在途時(shí)間，這一時(shí)間越少，迅速性越好。

（二）綜合評(píng)價(jià)法選擇運(yùn)輸方式的步驟二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇安全性通常指貨物的完整程度，以貨物的破損率表示，破損率越小，安全性越好。

各種運(yùn)輸方式的便利性的定量計(jì)算比較困難，實(shí)際中影響因素很多，如換裝次數(shù)、辦理手續(xù)的方便與時(shí)間等。為簡便計(jì)算，在一般情況下，可以近似利用貨物所在地至裝車（船、飛機(jī)）地之間的距離來表示，距離越近，便利性越好。（二）綜合評(píng)價(jià)法選擇運(yùn)輸方式的步驟二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇（二）綜合評(píng)價(jià)法選擇運(yùn)輸方式的步驟二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇

（二）綜合評(píng)價(jià)法選擇運(yùn)輸方式的步驟二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇（3）選擇適當(dāng)模型計(jì)算綜合評(píng)價(jià)指標(biāo)，即運(yùn)輸方式的綜合重要度。通常候選的運(yùn)輸方式有四種：公路、鐵路、水路和航空運(yùn)輸?？捎肎、T、S和H分別表示公路、鐵路、水路和航空運(yùn)輸?shù)木C合重要度，于是有

（4）比較和選擇，即根據(jù)綜合評(píng)價(jià)指標(biāo)值或分值的大小，對(duì)被評(píng)價(jià)對(duì)象進(jìn)行排序，并由此得出結(jié)論。比較四種運(yùn)輸方式的綜合重要度G、T、S和H，數(shù)值大的為最終選擇?！纠?-2】選取南疆線某鐵路路線為實(shí)際工程案例，南疆線東起巴音郭楞蒙古自治州的輪臺(tái)縣，西至阿克蘇地區(qū)的庫車市，全長約為89.1km。這段鐵路線路的速度目標(biāo)值應(yīng)根據(jù)地形平坦開闊、部分地區(qū)曲線較大、橋梁分布稀疏及對(duì)沿線生態(tài)環(huán)境的影響等方面確定，線速目標(biāo)值在120km/h至160km/h之間。其中已知表5-8和表5-9所示的信息，要求應(yīng)用密切值法對(duì)鐵路選線方案進(jìn)行選擇（表5-8、5-9見教材199、200頁）。（三）舉例二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇（1）確定影響運(yùn)輸方式選擇的因素，即評(píng)價(jià)指標(biāo)體系。顯然，本案例是從技術(shù)層、經(jīng)濟(jì)層、環(huán)境影響、社會(huì)效益四個(gè)方面考慮評(píng)價(jià)指標(biāo)的，如表5-10所示（表5-10見教材200~201頁）。（2）確定指標(biāo)體系中各指標(biāo)的權(quán)數(shù)。本案例中已經(jīng)給出了各指標(biāo)的權(quán)數(shù)，所以此步驟省略。（三）舉例二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇（3）選擇適當(dāng)模型計(jì)算綜合評(píng)價(jià)指標(biāo)。本案例中明確了使用密切值法對(duì)鐵路選線方案進(jìn)行選擇。具體內(nèi)容如下：①建立原始數(shù)據(jù)指標(biāo)矩陣。②建立同向指標(biāo)矩陣。本題每個(gè)指標(biāo)的權(quán)重都越大越好，屬于正向指標(biāo)。同向指標(biāo)矩陣如下：（三）舉例二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇

（三）舉例二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇

④確定各評(píng)價(jià)指標(biāo)的最優(yōu)點(diǎn)集和最劣點(diǎn)集?？梢园炎顑?yōu)點(diǎn)集標(biāo)紅色，把最劣點(diǎn)集標(biāo)紫色：（三）舉例二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇

（三）舉例二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇（三）舉例二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇

得出最大和最小歐氏距離如表5-12所示（表5-12見教材203頁）。⑥計(jì)算密切值。根據(jù)密切程度計(jì)算密切值，公式為則密切值為計(jì)算得（三）舉例二、綜合評(píng)價(jià)法的運(yùn)輸方式的選擇

單車輛路徑優(yōu)化任務(wù)三知識(shí)結(jié)構(gòu)導(dǎo)圖運(yùn)輸路徑優(yōu)化問題分為單車輛運(yùn)輸路徑優(yōu)化和多車輛運(yùn)輸路徑優(yōu)化。優(yōu)化的目標(biāo)可以是行車時(shí)間最短、距離最短或運(yùn)輸費(fèi)用最小，一般統(tǒng)稱為最短路徑問題。單車輛運(yùn)輸路徑優(yōu)化主要是對(duì)單一運(yùn)輸車輛從起點(diǎn)到終點(diǎn)間的最短行車路線進(jìn)行規(guī)劃和優(yōu)化。單車輛運(yùn)輸路徑優(yōu)化問題可分為兩種類型：（1）起詭點(diǎn)相同的車輛路徑問題；（2）起詭點(diǎn)不同的車輛路徑問題。單車輛路徑優(yōu)化一輛貨車從某設(shè)施點(diǎn)出發(fā)，為一定數(shù)量的顧客提供送貨服務(wù)后，經(jīng)常還必須返回到原出發(fā)點(diǎn)以進(jìn)行相關(guān)手續(xù)的交接。這種情況下的線路問題就是起詭點(diǎn)重合的線路問題，即一輛車的行走路線是一個(gè)閉回路。例如，企業(yè)使用自有貨車進(jìn)行運(yùn)輸、從某配送中心送貨到各零售點(diǎn)后再返回、市政垃圾的收運(yùn)、流動(dòng)售貨車的行駛等，都會(huì)碰到行車路線如何設(shè)計(jì)的問題。（一）問題介紹一、起訖點(diǎn)相同的單車輛路徑優(yōu)化1.問題描述旅行商問題TSP、中國郵遞員問題等都是起詭點(diǎn)重合的單車輛運(yùn)輸問題。起詭點(diǎn)重合的線路設(shè)計(jì)的一般原則和要求是:（1）車輛要經(jīng)過所有的點(diǎn)；（2）行駛時(shí)間最短或總距離最短。以TSP問題為例，如圖5-4所示，模型可描述為：在一個(gè)由n個(gè)節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)中，要求找出一個(gè)包括所有節(jié)點(diǎn)且耗費(fèi)最?。ň嚯x最短或時(shí)間代價(jià)最?。┑沫h(huán)路。一個(gè)環(huán)路也就是一個(gè)回路，既然回路是包含了所有節(jié)點(diǎn)的一個(gè)循環(huán)，因此可以將任何一個(gè)節(jié)點(diǎn)作為起點(diǎn)終點(diǎn)。（一）問題介紹一、起訖點(diǎn)相同的單車輛路徑優(yōu)化2.模型圖5-4TSP問題模型示意圖（1）如果節(jié)點(diǎn)數(shù)目較少，可運(yùn)用簡單貪夢(mèng)算法或窮舉法求解，且窮舉法可以得到最佳方案。（2）對(duì)于中小規(guī)模的TSP問題，利用運(yùn)籌學(xué)中的分枝定界法和奇偶點(diǎn)圖上作業(yè)法進(jìn)行求解也比較有效。（3）由于枚舉的次數(shù)為（n-1）!/2次，所以對(duì)于大規(guī)模節(jié)點(diǎn)的路徑優(yōu)化問題，一般很難獲得最優(yōu)解，只能通過啟發(fā)式算法（Hopfield神經(jīng)網(wǎng)絡(luò)方法、遺傳算法等）獲得近似最優(yōu)解。本書主要介紹分枝定界法、簡單貪夢(mèng)算法和奇偶點(diǎn)圖上作業(yè)法。（一）問題介紹一、起訖點(diǎn)相同的單車輛路徑優(yōu)化3.求解方法有若干個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)，必須經(jīng)過每一個(gè)城市且在一個(gè)城市只逗留一次，最后回到出發(fā)的城市，如何事先確定一條最短的線路，以保證其旅行費(fèi)用最少？旅行商問題又稱為旅行推銷員問題、貨郎擔(dān)問題，簡稱為TSP問題，是最基本的路線問題，求解方法主要有枚舉法、分枝定界法、簡單貪夢(mèng)算法等。首先，每個(gè)城市都必須被訪問；其次，要使總路徑最短，各城市最好只被訪問一次。按照這兩個(gè)要求，可建立TSP問題的0-1整數(shù)規(guī)劃模型。（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化1.旅行商問題介紹

（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化1.旅行商問題介紹

3）約束條件（1）要求各城市僅被訪問一次，表示為（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化1.旅行商問題介紹

（2）不能出現(xiàn)子回環(huán)，表示為

分枝定界法（BranchandBound）是由三棲學(xué)者查理德.卡普（RichardM.karp）在20世紀(jì)60年代發(fā)明的，該法成功求解了含有65個(gè)城市的旅行商問題，創(chuàng)下了當(dāng)時(shí)的紀(jì)錄。“分枝”即把全部可行解空間反復(fù)地分割為越來越小的子集，“定界”即對(duì)每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界（對(duì)于最小值問題）。分枝定界法的主要思路是：在每次分枝后，對(duì)凡是界限超出已知可行解的那些子集不再做進(jìn)一步分枝（這稱為剪枝），這樣解的許多子集（即搜索樹上的許多節(jié)點(diǎn)）就可以不予考慮，從而縮小了搜索范圍。這一過程反復(fù)進(jìn)行，直到找出可行解為止。該可行解的值不大于任何子集的界限，因此這種算法一般可以求得最優(yōu)解。（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化2.分枝定界法介紹分枝定界法是一種搜索與選代的方法，可選擇不同的分枝變量和子問題進(jìn)行分枝，常用于求解整數(shù)規(guī)劃問題。同時(shí)也能夠應(yīng)用在混合整數(shù)規(guī)劃問題上，其基本思路是：以一般線性規(guī)劃之單形法解得最佳解后，將非整數(shù)值的決策變量分割成最接近的兩個(gè)整數(shù)，分列條件加入原問題中，形成兩個(gè)子問題（或分枝）分別求解，如此便可求得目標(biāo)函數(shù)值的上限（上界）或下限（下界），從中尋得最佳解。一、起訖點(diǎn)相同的單車輛路徑優(yōu)化（二）分枝定界法的TSP問題求解2.分枝定界法介紹分枝定界法求解問題的邏輯示意圖如圖5-5所示。（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化3.分枝定界法的求解步驟圖5-5分枝定界法的邏輯示意圖

（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化3.分枝定界法的求解步驟（2）判斷可行解和最優(yōu)解。因?yàn)槁眯猩虇栴}要求旅行者遍歷各城市一次且僅一次，所以最短路徑中每個(gè)節(jié)點(diǎn)下標(biāo)中的每個(gè)元素只能出現(xiàn)兩次，滿足此條件的解即為可行解。如果初始最短路徑滿足可行解條件，則該初始最短路徑即為最優(yōu)解。如果不是可行解，則根據(jù)分枝定界法進(jìn)行替換驗(yàn)算，具體步驟如下：①對(duì)尚未被洞悉的節(jié)點(diǎn)按照費(fèi)用從小到大依次排序。②進(jìn)行第一輪替換驗(yàn)算。以最小費(fèi)用尚未被洞悉的節(jié)點(diǎn)，依次去替換初始最短路徑中不合理的節(jié)點(diǎn)，形成第一層新的分枝，并重新判斷其是否為可行解。（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化3.分枝定界法的求解步驟（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化3.分枝定界法的求解步驟③判斷是否有可行解。如果第一層新分枝中無可行解，則直接進(jìn)入第二輪替換驗(yàn)算。如果第一層新分枝中有可行解，則計(jì)算該可行解對(duì)應(yīng)節(jié)點(diǎn)的下限值（LowerBound，即為可行最短路徑的最小費(fèi)用），找出最小下限值。如果最小下限值>Z值，則停止驗(yàn)算，該最小下限值對(duì)應(yīng)的可行解即為最優(yōu)解。如果最小下限值<Z值，則更新Z值，來到第二輪替換驗(yàn)算。（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化3.分枝定界法的求解步驟④進(jìn)行第二輪替換驗(yàn)算。以下一個(gè)最小費(fèi)用尚未被洞悉的節(jié)點(diǎn)重復(fù)步驟②③,繼續(xù)替換驗(yàn)算，直到?jīng)]有尚未被洞悉的節(jié)點(diǎn)為止。如果最后一層新分枝中仍無可行解，則說明不可能包含可行解，驗(yàn)算停止。如果最后一層新分枝中有可行解，則該最小下限值對(duì)應(yīng)的可行解即為最優(yōu)解，驗(yàn)算停止。（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化4.舉例

（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化4.舉例求解過程：（1）構(gòu)建費(fèi)用（代價(jià)）矩陣D，求得初始最短路徑。本案例已經(jīng)給出了費(fèi)用矩陣D，即

由于本案例中涉及5座城市，需要求得5段路徑費(fèi)用的最小可行解。將矩陣D對(duì)角線以上的元素從小到大排列為

（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化4.舉例顯然,前5段路徑的費(fèi)用最少，取最小的5個(gè)費(fèi)用求和得可表示為

（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化4.舉例

（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化4.舉例

圖5-6第一次替換結(jié)果

（二）分枝定界法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化4.舉例這個(gè)唯一可行解對(duì)應(yīng)的下限，就是最小下限。圖5-7最優(yōu)解分析示意圖

（三）簡單貪樊算法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化1.簡單貪夢(mèng)算法介紹簡單貪夢(mèng)算法在對(duì)問題進(jìn)行求解時(shí)，總是做出當(dāng)前情況下的最好選擇，每次選擇得到的都是局部最優(yōu)解。選擇的策略必須具備無后效性，即某個(gè)狀態(tài)以前的過程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。（三）簡單貪樊算法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化2.算法步驟（1）從某一個(gè)城市開始，每次選擇一個(gè)城市，直到走完所有的城市。（2）每次在選擇下一個(gè)城市的時(shí)候，只考慮當(dāng)前情況，保證迄今為止經(jīng)過的路徑總距離最小。（3）如果所有位置都被選擇了，則停止，否則返回到第（2）步?！纠?-4】如圖5-8所示，要求車輛從配送中心A出發(fā)，送貨到B、C、D三個(gè)客戶后再返回配送中心。任意兩點(diǎn)間的距離已知，即線段上的數(shù)字，用簡單貪夢(mèng)算法求最佳配送路徑。（三）簡單貪樊算法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化3.舉例圖5-8路網(wǎng)示意圖求解過程：（1）選擇距出發(fā)點(diǎn)最近的顧客位置。由于B點(diǎn)距A點(diǎn)最近，故先選擇B點(diǎn)。（2）從剩下的節(jié)點(diǎn)中選擇離當(dāng)前已選擇節(jié)點(diǎn)最近的顧客，即找出離B點(diǎn)最近的點(diǎn)，由圖可知是C點(diǎn)。（3）如果所有位置都被選擇了，則停止，否則返回到第（2）步。明顯地，由于只剩下D點(diǎn)沒被選擇，所以D點(diǎn)成為繼C點(diǎn)之后的顧客，然后返回A。這樣，圖中的最佳送貨路線為A—B—C—D—A，總行駛距離=22+18+38+45=123。（三）簡單貪樊算法的TSP問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化3.舉例中國郵遞員問題即中國郵路問題，是我國數(shù)學(xué)家管梅谷于1960年首次提出的。其問題模型可以描述為：一位郵遞員從郵局選好郵件去投遞，然后返回郵局，他必須經(jīng)過由他負(fù)責(zé)投遞的每條街道至少一次，為這位郵遞員設(shè)計(jì)一條投遞線路，使其耗時(shí)最少。（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化1.中國郵遞員問題介紹中國郵遞員問題與七橋問題（一種著名的古典圖論）聯(lián)系很密切，七橋問題又稱為一筆畫問題，如圖5-9所示。七橋問題模型可描述為：河中有兩個(gè)島嶼，河的兩岸和島嶼之間有七座橋相互連接。一般問法為：一個(gè)人怎樣才能不重復(fù)、不遺漏地走過這七座橋，最終回到原出發(fā)地？中國郵遞員問題與七橋問題這兩個(gè)問題模型可以歸結(jié)為：在平面上給出一個(gè)連通的線性圖，要求將這個(gè)線性圖從某點(diǎn)開始一筆畫出（允許重復(fù)），并且最后仍回到起點(diǎn)，問怎樣畫才能使重復(fù)路線最短。（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化1.中國郵遞員問題介紹圖5-9七橋問題示意圖1）奇偶點(diǎn)圖上作業(yè)法的要點(diǎn)提煉（1）給定一個(gè)連通多重圖G。①若存在一條鏈能過每邊一次且僅一次，則稱該鏈為歐拉鏈。②若存在一個(gè)簡單圈能過每邊一次且僅一次，則稱該圈為歐拉圈。③一個(gè)圖若有歐拉圈，則稱為歐拉圖。顯然，一個(gè)圖若能一筆畫出，這個(gè)圖必然是歐拉圖。（2）連通多重圖G有歐拉圈，當(dāng)且僅當(dāng)G中無奇點(diǎn)。（3）連通多重圖G有歐拉鏈，當(dāng)且僅當(dāng)G恰有2個(gè)奇點(diǎn)。（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化2.奇偶點(diǎn)圖上作業(yè)法介紹（4）如果在某郵遞員所負(fù)責(zé)范圍內(nèi)的街道圖中沒有奇點(diǎn)，那么他就可以從郵局出發(fā)，走過每條街道一次且僅一次，最后回到郵局，這樣他所走的路程就是最短的路程。（5）對(duì)于有奇點(diǎn)的街道圖，就必須在某些街道上重復(fù)走一次或多次。（6）在任何一個(gè)圖中，如有奇點(diǎn)，奇點(diǎn)個(gè)數(shù)必為偶數(shù)。因此，在圖中，奇點(diǎn)可以配成對(duì)。（7）因?yàn)閳D是連通的，因此，每一對(duì)奇點(diǎn)之間必有一條鏈，把這條鏈上所有邊作為重復(fù)邊加到圖中去，形成的新連通圖中必定無奇點(diǎn)，即可得到一個(gè)可行方案。（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化2.奇偶點(diǎn)圖上作業(yè)法介紹2）奇偶點(diǎn)圖上作業(yè)法的定理重復(fù)邊總權(quán)最小的充分必要條件如下：（1）每條邊最多重復(fù)一次；（2）對(duì)圖G中每個(gè)初等圈來講，重復(fù)邊的長度之和不超過圈長的一半。重復(fù)邊的總權(quán)最小，即為最優(yōu)解。（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化2.奇偶點(diǎn)圖上作業(yè)法介紹（1）尋找初始可行方案。①先檢查圖中是否有奇點(diǎn)，如無奇點(diǎn)則已是歐拉圖，找出歐拉回路即可。②如有奇點(diǎn)，把它們兩兩配成對(duì)。每對(duì)奇點(diǎn)之間必有一條鏈（圖是連通的），我們把這條鏈的所有邊作為重復(fù)邊追加到圖中去，這樣得到的新連通圖必?zé)o奇點(diǎn)，這就給出了初始投遞路線。（2）調(diào)整可行方案，使重復(fù)邊最多為一次，總長不斷減少。（3）檢查圖中每個(gè)初等圈是否滿足定理“每條邊最多重復(fù)一次”和“對(duì)圖G中每個(gè)初等圈來講，重復(fù)邊的長度之和不超過圈長的一半”，如不滿足則調(diào)整到滿足為止。（4）檢查最終圖形中的每個(gè)圈。若定理（1）（2）均已滿足，則圖中的歐拉回路就是最優(yōu)路線。（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化3.奇偶點(diǎn)圖上作業(yè)法的步驟4.舉例

（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化圖5-10郵局以及派件位置示意圖4.舉例

（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化4.舉例

（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化圖5-11第一次添加重復(fù)邊的結(jié)果4.舉例

（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化

圖5-12第二次添加重復(fù)邊的結(jié)果4.舉例

（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化4.舉例③從圖5-12中去掉偶數(shù)條重復(fù)邊得如圖5-13所示的結(jié)果。（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化圖5-13去掉偶數(shù)條重復(fù)邊的結(jié)果

4.舉例

（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化4.舉例

（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化圖5-14調(diào)整過后的結(jié)果4.舉例

（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化圖5-15繼續(xù)調(diào)整后的結(jié)果此時(shí)該重復(fù)邊的總權(quán)重為11，小于該圈總長的一半。4.舉例（4）檢查最終圖形中的每個(gè)圈。經(jīng)檢查，圖中每個(gè)圈都同時(shí)滿足“圖的每一邊上最多有一條重復(fù)邊”和“圖中每個(gè)圈上的重復(fù)邊的總權(quán)不大于該圈總權(quán)的一半”兩個(gè)條件，所以，圖中的任何一個(gè)歐拉回路都是郵遞員的最優(yōu)郵遞路線。（四）奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解一、起訖點(diǎn)相同的單車輛路徑優(yōu)化1.問題描述現(xiàn)有A、E兩座不同的城市，有一批貨需要從A運(yùn)送到E，如何選擇路徑才能使得從A到E的距離最短，這就是起詭點(diǎn)不同的單車輛運(yùn)輸路徑優(yōu)化問題。（一）問題介紹二、起訖點(diǎn)不同的單車輛路徑優(yōu)化2.模型（一）問題介紹用節(jié)點(diǎn)代表經(jīng)過的縣市或站點(diǎn)，箭頭表示兩點(diǎn)間是連通的；箭頭線上的數(shù)字表示兩點(diǎn)間的運(yùn)輸代價(jià)，如圖5-16所示。運(yùn)輸代價(jià)可以是時(shí)間、距離或時(shí)間與距離的加權(quán)平均。以路徑最短為目標(biāo)構(gòu)建模型，確定出從起點(diǎn)A到終點(diǎn)E的最佳運(yùn)輸路線，這類問題被歸結(jié)為運(yùn)籌學(xué)中的最短路徑問題。圖5-16起詭點(diǎn)不同的單車輛運(yùn)輸問題示意圖二、起訖點(diǎn)不同的單車輛路徑優(yōu)化3.求解（一）問題介紹

二、起訖點(diǎn)不同的單車輛路徑優(yōu)化1.Dijkstra方法介紹（二）Dijkstra方法的最短路徑問題求解Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家E.W.Dijkstra于1959年提出的，又叫標(biāo)號(hào)法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有權(quán)圖中最短路徑問題。在此算法思想基礎(chǔ)上，人們演繹出了幾十種不同的路徑優(yōu)化算法，盡管如此，Dijkstra方法仍是目前求解最短路徑問題最常用的方法。Dijkstra算法的主要特點(diǎn)是從起始點(diǎn)開始，采用貪夢(mèng)算法的策略，每次遍歷到距離始點(diǎn)最近且未訪問過的頂點(diǎn)的鄰接節(jié)點(diǎn)，直到擴(kuò)展到終點(diǎn)為止。從廣義上說，“最短路徑”不單指“純距離”意義上的最短路徑，它可以是“經(jīng)濟(jì)距離”意義上的最短路徑，“時(shí)間”意義上的最短路徑，“網(wǎng)絡(luò)”意義上的最短路徑等。二、起訖點(diǎn)不同的單車輛路徑優(yōu)化1.Dijkstra方法介紹（二）Dijkstra方法的最短路徑問題求解

二、起訖點(diǎn)不同的單車輛路徑優(yōu)化1.Dijkstra方法介紹（二）Dijkstra方法的最短路徑問題求解

二、起訖點(diǎn)不同的單車輛路徑優(yōu)化2.步驟（二）Dijkstra方法的最短路徑問題求解

二、起訖點(diǎn)不同的單車輛路徑優(yōu)化2.步驟（二）Dijkstra方法的最短路徑問題求解

二、起訖點(diǎn)不同的單車輛路徑優(yōu)化

3.舉例（二）Dijkstra方法的最短路徑問題求解圖5-17某公路運(yùn)輸?shù)穆肪W(wǎng)示意圖二、起訖點(diǎn)不同的單車輛路徑優(yōu)化

3.舉例（二）Dijkstra方法的最短路徑問題求解圖5-18第一輪標(biāo)號(hào)結(jié)果示意圖二、起訖點(diǎn)不同的單車輛路徑優(yōu)化

3.舉例（二）Dijkstra方法的最短路徑問題求解

二、起訖點(diǎn)不同的單車輛路徑優(yōu)化3.舉例（二）Dijkstra方法的最短路徑問題求解修改結(jié)果如圖5-19所示。圖5-19第一次調(diào)整標(biāo)號(hào)的結(jié)果示意圖

二、起訖點(diǎn)不同的單車輛路徑優(yōu)化3.舉例（二）Dijkstra方法的最短路徑問題求解

圖5-20第二次調(diào)整標(biāo)號(hào)的結(jié)果示意圖二、起訖點(diǎn)不同的單車輛路徑優(yōu)化3.舉例（二）Dijkstra方法的最短路徑問題求解最終處理好的結(jié)果如圖5-21所示。圖5-21最終結(jié)果示意圖

二、起訖點(diǎn)不同的單車輛路徑優(yōu)化1.方法介紹（三）動(dòng)態(tài)規(guī)劃法的最短路徑問題求解在現(xiàn)實(shí)生活中，有一類活動(dòng)由于它的特殊性，可將過程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過程達(dá)到最好的活動(dòng)效果。因此各個(gè)階段決策的選取不能任意確定，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過程的一條活動(dòng)路線，這種把一個(gè)問題看作一個(gè)前后關(guān)聯(lián)且具有鏈狀結(jié)構(gòu)的多階段過程稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，各個(gè)階段采取的決策一般來說是與時(shí)間有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動(dòng)態(tài)”的含義，這種解決多階段決策最優(yōu)化的過程被稱為動(dòng)態(tài)規(guī)劃法。二、起訖點(diǎn)不同的單車輛路徑優(yōu)化1.方法介紹（三）動(dòng)態(tài)規(guī)劃法的最短路徑問題求解動(dòng)態(tài)規(guī)劃（DynamicProgramming，DP）是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程最優(yōu)化的過程。20世紀(jì)50年代初，美國數(shù)學(xué)家貝爾曼（R.Bellman）等人在研究多階段決策過程的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃的應(yīng)用極其廣泛，包括經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)、最優(yōu)控制、工業(yè)生產(chǎn)、軍事以及自動(dòng)化控制等領(lǐng)域，并在背包問題、生產(chǎn)經(jīng)營問題、庫存管理、資金管理問題、資源分配問題、設(shè)備更新問題、最短路徑問題和復(fù)雜系統(tǒng)可靠性問題、排序問題、裝載問題等中取得了顯著的效果。二、起訖點(diǎn)不同的單車輛路徑優(yōu)化（1）根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)特征將整個(gè)線路網(wǎng)絡(luò)劃分為多個(gè)階段。（2）對(duì)每個(gè)階段的決策問題求解。通常采用從終點(diǎn)到起點(diǎn)的逆序法進(jìn)行決策，因此決策階段編號(hào)是按逆序進(jìn)行的。以每一個(gè)階段的初始狀態(tài)為基礎(chǔ)確定下一階段的可選狀態(tài)，并計(jì)算各狀態(tài)的代價(jià)（指各狀態(tài)點(diǎn)到終點(diǎn)的距離），然后從中選擇代價(jià)最小的狀態(tài)。（3）從最后一個(gè)階段開始，將每個(gè)階段決策的距離最短的點(diǎn)依次連接起來，即得到從起點(diǎn)到詭點(diǎn)的最短路線。2.步驟（三）動(dòng)態(tài)規(guī)劃法的最短路徑問題求解二、起訖點(diǎn)不同的單車輛路徑優(yōu)化【例5-7】某貨運(yùn)公司要將一批貨物從A市運(yùn)送到E市。該公司根據(jù)這兩個(gè)城市之間可選擇的行車路線的地圖，繪制了如圖5-22所示的公路網(wǎng)絡(luò)，圖中的字母表示節(jié)點(diǎn)，節(jié)點(diǎn)代表經(jīng)過的站點(diǎn)或城市，箭頭代表兩個(gè)節(jié)點(diǎn)之間的公路，箭頭上的數(shù)字表明兩點(diǎn)之間的運(yùn)輸里程。求A市到E市的最短路。3.舉例（三）動(dòng)態(tài)規(guī)劃法的最短路徑問題求解圖5-22A市到E市的公路網(wǎng)絡(luò)示意圖二、起訖點(diǎn)不同的單車輛路徑優(yōu)化求解過程：（1）根據(jù)本案例中的公路網(wǎng)絡(luò)情況，可將其分成四個(gè)階段，如圖5-23所示。3.舉例（三）動(dòng)態(tài)規(guī)劃法的最短路徑問題求解圖5-23階段劃分示意圖二、起訖點(diǎn)不同的單車輛路徑優(yōu)化

3.舉例（三）動(dòng)態(tài)規(guī)劃法的最短路徑問題求解二、起訖點(diǎn)不同的單車輛路徑優(yōu)化

3.舉例（三）動(dòng)態(tài)規(guī)劃法的最短路徑問題求解二、起訖點(diǎn)不同的單車輛路徑優(yōu)化

3.舉例（三）動(dòng)態(tài)規(guī)劃法的最短路徑問題求解二、起訖點(diǎn)不同的單車輛路徑優(yōu)化多車輛路徑優(yōu)化任務(wù)四知識(shí)結(jié)構(gòu)導(dǎo)圖

（一）問題介紹一、多車輛路徑優(yōu)化問題介紹（1）單一貨運(yùn)中心，多部車輛配送。（2）每個(gè)需求點(diǎn)由一輛車服務(wù)，每個(gè)客戶的貨物需求量不超過車輛的載重容量。（3）車輛為單一車種，即視為相同的載重量，且有容量限制。（4）無時(shí)間窗限制的配送問題。（5）客戶的位置和需求量均為已知。（6）配送的貨物視為同一種商品，便于裝載。（二）多車輛路徑問題數(shù)學(xué)模型一、多車輛路徑優(yōu)化問題介紹1.假設(shè)

（二）多車輛路徑問題數(shù)學(xué)模型一、多車輛路徑優(yōu)化問題介紹2.參數(shù)說明

（二）多車輛路徑問題數(shù)學(xué)模型一、多車輛路徑優(yōu)化問題介紹3.決策變量這是一個(gè)多目標(biāo)優(yōu)化問題，通常會(huì)以車輛數(shù)量最少且總行駛里程最短為目標(biāo)，即（1）保證車輛數(shù)最少：（2）總行駛距離最少：（二）多車輛路徑問題數(shù)學(xué)模型一、多車輛路徑優(yōu)化問題介紹4.目標(biāo)函數(shù)

（1）每個(gè)客戶點(diǎn)只能被一輛車訪問（除了配送中心被所有車輛訪問以外）：（二）多車輛路徑問題數(shù)學(xué)模型一、多車輛路徑優(yōu)化問題介紹5.約束條件

（2）車輛的載重能力約束：

（3）進(jìn)入和離開某個(gè)客戶的是同一輛車：

（4）消除子回環(huán)：（二）多車輛路徑問題數(shù)學(xué)模型一、多車輛路徑優(yōu)化問題介紹5.約束條件

（6）所需最少車輛數(shù)：

多車輛路徑問題的求解方法主要有：（三）多車輛路徑問題求解方法一、多車輛路徑優(yōu)化問題介紹

4.人工智能法

6.啟發(fā)式方法

5.模擬法

3.精確優(yōu)化法

2.節(jié)約里程法

1.掃描法（三）多車輛路徑問題求解方法一、多車輛路徑優(yōu)化問題介紹

1.掃描法掃描法是比較有代表性的啟發(fā)式方法，它是由Gillette和Miller提出的。該方法先將節(jié)點(diǎn)的需求進(jìn)行分組或劃群，然后對(duì)每一組按旅行商問題求解，設(shè)計(jì)出一條最佳的路線。這種方法也稱為兩階段法，即先對(duì)客戶群進(jìn)行劃分，每個(gè)客戶群用一輛車來完成配送服務(wù)，然后再確定每個(gè)群內(nèi)的最短路線。

2.節(jié)約里程法（三）多車輛路徑問題求解方法一、多車輛路徑優(yōu)化問題介紹節(jié)約里程法（SavingMethod）是最具代表性的啟發(fā)式方法，它是由Clarke和Wright在1964年提出的。許多成功的車輛調(diào)度軟件就是根據(jù)該方法或其改進(jìn)方法開發(fā)的。

3.精確優(yōu)化法（三）多車輛路徑問題求解方法一、多車輛路徑優(yōu)化問題介紹精確優(yōu)化法主要是指運(yùn)用線性規(guī)劃和非線性規(guī)劃技術(shù)進(jìn)行的最優(yōu)決策。在研究VRP問題的早期，主要解決從單源點(diǎn)派車如何用最短路線或在最短時(shí)間內(nèi)對(duì)一定數(shù)量需求點(diǎn)運(yùn)輸?shù)恼{(diào)度問題，即著眼于最優(yōu)算法。隨著運(yùn)輸系統(tǒng)復(fù)雜化和對(duì)調(diào)度的多目標(biāo)要求，獲得整個(gè)系統(tǒng)的精確優(yōu)化解越來越困難，而且用計(jì)算機(jī)求解大型優(yōu)化問題的時(shí)間和代價(jià)太大，因此精確優(yōu)化法及其簡化算法現(xiàn)在常用于運(yùn)輸調(diào)度的局部優(yōu)化問題。

4.人工智能法（三）多車輛路徑問題求解方法一、多車輛路徑優(yōu)化問題介紹人工智能技術(shù)及其應(yīng)用的不斷發(fā)展，尤其是模擬退火算法、遺傳算法以及人工神經(jīng)網(wǎng)絡(luò)和專家系統(tǒng)等新技術(shù)的發(fā)展，為解決大規(guī)模、多目標(biāo)車輛調(diào)度問題提供了新的途徑。（三）多車輛路徑問題求解方法一、多車輛路徑優(yōu)化問題介紹

5.模擬法模擬法是指利用數(shù)學(xué)公式、邏輯表達(dá)式、圖表、坐標(biāo)圖形等抽象概念表示實(shí)際運(yùn)輸系統(tǒng)內(nèi)部狀態(tài)和輸入、輸出的關(guān)系，并通過計(jì)算機(jī)對(duì)模型進(jìn)行實(shí)驗(yàn)，通過實(shí)驗(yàn)取得改善運(yùn)輸系統(tǒng)或設(shè)計(jì)新運(yùn)輸系統(tǒng)所需的信息。雖然模擬法在模型構(gòu)造、程序調(diào)試、數(shù)據(jù)整理方面的工作量大，但由于運(yùn)輸系統(tǒng)結(jié)構(gòu)復(fù)雜，不確定因素多，模擬法仍以其描述和求解問題的能力優(yōu)勢(shì)而成為復(fù)雜運(yùn)輸調(diào)度系統(tǒng)建模的主要方法。

6.啟發(fā)式方法（三）多車輛路徑問題求解方法一、多車輛路徑優(yōu)化問題介紹用啟發(fā)式方法解決問題時(shí)，強(qiáng)調(diào)的是“滿意”解，而不是去追求最優(yōu)性。用啟發(fā)式方法求解問題是通過不斷的選代過程實(shí)現(xiàn)的，因而需擬定出一套解的搜索規(guī)則。為了能得到滿意解，在整個(gè)選代過程中要不斷吸收新的信息，必要時(shí)還要改變?cè)瓉頂M定的不合適策略，建立新的搜索規(guī)劃，注意從失敗中吸取教訓(xùn)，并逐步縮小搜索范圍。啟發(fā)式方法就是通過經(jīng)驗(yàn)法則來求取運(yùn)輸過程的滿意解。它能同時(shí)滿足詳細(xì)描繪問題和求解的需要，與精確優(yōu)化法相比，啟發(fā)式方法更加實(shí)用；其缺點(diǎn)是難以判斷解的滿意度。本書主要介紹掃描法和節(jié)約里程法來求解多車輛路徑優(yōu)化問題。掃描法是一種先確定客戶分群再確定車輛最低路線的算法。求解過程分為兩步：第一步是指派車輛服務(wù)的站點(diǎn)或客戶點(diǎn)；第二步是決定輛車的行車路線。分派車輛的過程可以通過手工計(jì)算或直接在圖紙上完成，也可以利用計(jì)算機(jī)程序求解，計(jì)算速度快、計(jì)算準(zhǔn)確。該方法的缺點(diǎn)是，不能處理有時(shí)間窗的VRP問題。掃描法的原理：先以貨運(yùn)中心為原點(diǎn)，將所有需求點(diǎn)的極坐標(biāo)算出，然后依角度大小以逆時(shí)針或順時(shí)針方向掃描，若滿足車輛裝載容量即劃分為一群，將所有點(diǎn)掃描完畢后在每個(gè)群內(nèi)部用最短路徑法求出車輛行駛路徑。（一）方法介紹二、采用掃描法的多車輛路徑優(yōu)化（1）以貨運(yùn)中心為原點(diǎn)建立坐標(biāo)系，將所有需求點(diǎn)坐標(biāo)標(biāo)出來。（2）掃描劃分客戶群，以零角度為極坐標(biāo)軸，按順時(shí)針或逆時(shí)針方向，依角度大小開始掃描。（3）將掃描經(jīng)過的客戶點(diǎn)需求量進(jìn)行累加，當(dāng)客戶需求總量達(dá)到一輛車的載重量限制且不超過載重量極限時(shí)，就將這些客戶劃分為一個(gè)群，即由同一輛車完成送貨服務(wù)。（4）重復(fù)步驟（3），按照同樣的方法將其余客戶劃分為新的客戶群，指派新的車輛，直到所有的客戶都被劃分到相應(yīng)群中。（5）在每個(gè)群內(nèi)部可以用簡單貪夢(mèng)算法求出車輛行駛最短路徑。（二）步驟二、采用掃描法的多車輛路徑優(yōu)化【例5-8】某運(yùn)輸公司為其客戶提供取貨服務(wù)，貨物運(yùn)回倉庫集中后將以更大的批量進(jìn)行長途運(yùn)輸。所有取貨任務(wù)均由載重量為10噸的貨車完成。已知運(yùn)輸公司倉庫的坐標(biāo)為（19.50，5.56），要求合理安排車輛，并確定各車輛行駛路線，使總運(yùn)輸里程最短?，F(xiàn)在有13家客戶有取貨要求，各客戶的取貨量、客戶的地理位置坐標(biāo)如表5-16所示（表5-16見教材222頁）。（三）舉例二、采用掃描法的多車輛路徑優(yōu)化求解過程：（1）建立坐標(biāo)系。如圖5-24所示，在圖上標(biāo)出客戶的坐標(biāo)位置，并在各客戶編號(hào)旁邊的方框中標(biāo)出該客戶的貨運(yùn)量。以倉庫為極坐標(biāo)原點(diǎn)，向右的水平線為零角度線。（三）舉例二、采用掃描法的多車輛路徑優(yōu)化圖5-24客戶的坐標(biāo)位置示意圖（2）掃描劃分客戶群。以零角度線為起始位置，按逆時(shí)針方向進(jìn)行掃描，經(jīng)過客戶6、5、7、8，此時(shí)的客戶取貨量為3+2+2.25+2.5=9.75，如果再增加一個(gè)客戶，就會(huì)超過10噸的極限，所以客戶6、5、7、8由第一輛車完成任務(wù)，并得到1#路線，我們用藍(lán)色虛線將其隔開，如圖5-25所示。（三）舉例二、采用掃描法的多車輛路徑優(yōu)化圖5-25確定第一個(gè)配送客戶群同理，客戶9、13、1、10、12五個(gè)客戶被相繼掃描，五個(gè)客戶的取貨量為1.8+1.5+1.9+2.15+2.6=9.95<10，不超過車輛的載重極限，2#路線被確定。接著客戶4、11、3、2相繼被掃描，取貨量為2.4+1.6+3.1+2.8=9.9<10，沒有超出車輛載重極限，3#路線被確定，結(jié)果如圖5-26所示。（三）舉例二、采用掃描法的多車輛路徑優(yōu)化圖5-26確定得到的三個(gè)配送客戶群（3）確定每個(gè)車輛的最佳路線。根據(jù)不超過載重極限又要最大限度提高車輛利用率的原則，13家客戶的取貨任務(wù)可由3輛載重量為10噸的貨車完成。根據(jù)簡單貪夢(mèng)算法，確定這三個(gè)客戶群的最佳行車路線。求解結(jié)果如下：1#路線經(jīng)過的客戶點(diǎn)序列是：0—6—5—7—8。2#路線經(jīng)過的客戶點(diǎn)序列是：0—9—13—1—10—12—0。3#路線經(jīng)過的客戶點(diǎn)序列是：0—4—11—3—2—0。（三）舉例二、采用掃描法的多車輛路徑優(yōu)化節(jié)約里程法能靈活處理許多現(xiàn)實(shí)的約束條件，當(dāng)節(jié)點(diǎn)數(shù)不太多時(shí)，能較快地計(jì)算出結(jié)果，且結(jié)果與最優(yōu)解很接近。用于多車輛路徑問題時(shí)，該方法能同時(shí)確定車輛數(shù)及車輛經(jīng)過各站點(diǎn)的順序，是解決VRP模型非常有效的啟發(fā)式方法。節(jié)約里程法的目標(biāo)是使所有車輛行駛的總里程最短，并使提供服務(wù)的車輛總數(shù)最少。算法的基本思想是：如果將運(yùn)輸問題中的兩個(gè)回路合并成一個(gè)回路，就可以縮短線路的總里程（即節(jié)約了距離），并減少了一輛車。（一）方法介紹三、采用節(jié)約里程法的多車輛路徑優(yōu)化

（一）方法介紹三、采用節(jié)約里程法的多車輛路徑優(yōu)化圖5-27節(jié)約里程法原理示意圖1.確定距離方陣計(jì)算出兩兩客戶以及配送中心到各個(gè)客戶之間的距離，并列成表格。2.計(jì)算節(jié)約矩陣計(jì)算兩兩客戶加上一個(gè)配送中心所構(gòu)成的三角形路徑之間通過合并路線所節(jié)約的里程數(shù)，并列成表格。（二）步驟三、采用節(jié)約里程法的多車輛路徑優(yōu)化3.將客戶劃歸到不同的運(yùn)輸路線將客戶劃歸到不同運(yùn)輸路線的目的是使合并路線的客戶群的配送路線節(jié)約距離最大化。這里要遵循兩個(gè)原則：一是保證兩條線路的合并是可行的，如果兩條運(yùn)輸線路上的運(yùn)輸總量不超過卡車的最大載重量，那么二者合并就是可行的；二是試圖使節(jié)約最大的兩條線路合并成一條新的可行線路。這一過程一直持續(xù)到不能再有新的合并方案產(chǎn)生才算結(jié)束。4.確定每輛車的送貨順序通常采用簡單貪夢(mèng)算法進(jìn)行求解，確定出各個(gè)客戶群體的配送順序。（二）步驟三、采用節(jié)約里程法的多車輛路徑優(yōu)化【例5-9】某貨運(yùn)站要為13個(gè)客戶提供配送服務(wù)，貨運(yùn)站的位置、客戶的坐標(biāo)及客戶的訂單規(guī)模如表5-17所示（表5-17見教材225頁）。貨運(yùn)站共有4輛卡車，每輛車的載重量是200件。由于送貨成本與車輛行駛總里程之間密切相關(guān)，公司經(jīng)理希望獲得總行駛距離最小的方案。如何分配客戶？如何確定車輛行駛路徑？（三）舉例三、采用節(jié)約里程法的多車輛路徑優(yōu)化求解過程：（1）確定距離方陣，計(jì)算客戶之間及客戶與貨運(yùn)站之間的距離，結(jié)果如表5-18所示（表5-18見教材225頁）。（2）計(jì)算所有客戶之間的節(jié)約矩陣，結(jié)果如表5-19所示。（3）合并客戶路線?？蛻艟€路合并原則是使節(jié)約的距離最大，且不超過車輛載重量。這是一個(gè)反復(fù)進(jìn)行的過程。（三）舉例三、采用節(jié)約里程法的多車輛路徑優(yōu)化觀察表5-20,最大的節(jié)約34來自客戶6與客戶11的合并，合并后的總運(yùn)量=16+91=107<200件,合并是可行的。因此,首先應(yīng)將這兩個(gè)客戶合并在一條線路，如表5-20中第二列所示（表5-20見教材226頁），節(jié)約的34在下一步中不必再考慮。下一個(gè)最大的節(jié)約是客戶7和客戶6，合并后可節(jié)約距離33。合并后的總運(yùn)量=107+56=163<200件，所以這一合并也是可行的，將客戶7添加到線路6中，如表5-21所示（表5-21見教材227頁）。（三）舉例三、采用節(jié)約里程法的多車輛路徑優(yōu)化接下來考慮的最大節(jié)約是客戶10與客戶11（即線路6），合并后可節(jié)約32。但是，合并