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

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

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

=倉庫平均庫存水平×（出廠單價+運輸費率）×保管費率

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

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

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

（二）綜合評價法選擇運輸方式的步驟二、綜合評價法的運輸方式的選擇

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

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

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

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

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

（三）舉例二、綜合評價法的運輸方式的選擇

④確定各評價指標(biāo)的最優(yōu)點集和最劣點集。可以把最優(yōu)點集標(biāo)紅色，把最劣點集標(biāo)紫色：（三）舉例二、綜合評價法的運輸方式的選擇

（三）舉例二、綜合評價法的運輸方式的選擇（三）舉例二、綜合評價法的運輸方式的選擇

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.舉例

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（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é)點的需求進(jìn)行分組或劃群，然后對每一組按旅行商問題求解，設(shè)計出一條最佳的路線。這種方法也稱為兩階段法，即先對客戶群進(jìn)行劃分，每個客戶群用一輛車來完成配送服務(wù)，然后再確定每個群內(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)化法主要是指運用線性規(guī)劃和非線性規(guī)劃技術(shù)進(jìn)行的最優(yōu)決策。在研究VRP問題的早期，主要解決從單源點派車如何用最短路線或在最短時間內(nèi)對一定數(shù)量需求點運輸?shù)恼{(diào)度問題，即著眼于最優(yōu)算法。隨著運輸系統(tǒng)復(fù)雜化和對調(diào)度的多目標(biāo)要求，獲得整個系統(tǒng)的精確優(yōu)化解越來越困難，而且用計算機求解大型優(yōu)化問題的時間和代價太大，因此精確優(yōu)化法及其簡化算法現(xià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)圖形等抽象概念表示實際運輸系統(tǒng)內(nèi)部狀態(tài)和輸入、輸出的關(guān)系，并通過計算機對模型進(jìn)行實驗，通過實驗取得改善運輸系統(tǒng)或設(shè)計新運輸系統(tǒng)所需的信息。雖然模擬法在模型構(gòu)造、程序調(diào)試、數(shù)據(jù)整理方面的工作量大，但由于運輸系統(tǒng)結(jié)構(gòu)復(fù)雜，不確定因素多，模擬法仍以其描述和求解問題的能力優(yōu)勢而成為復(fù)雜運輸調(diào)度系統(tǒng)建模的主要方法。

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

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