《系統(tǒng)工程》 教案 模塊五 系統(tǒng)優(yōu)化

系統(tǒng)工程教案課程信息課程名稱系統(tǒng)工程授課專業(yè)交通運(yùn)輸類課程類型必修課公共課（）；專業(yè)基礎(chǔ)課（）；專業(yè)課（√）；選修課限選課（）；任選課（）；專業(yè)拓展課（）授課方式講授（√）；實(shí)踐課（√）；其它（）考核方式考試（）；考查（√）課程教學(xué)總學(xué)時(shí)數(shù)32學(xué)時(shí)學(xué)分?jǐn)?shù)2學(xué)分教材名稱系統(tǒng)工程作者謝家貴、馬悅出版社西安電子科技大學(xué)出版社書號978-7-5606-6788-1出版時(shí)間2023.3（2023.4重?。┌嗉壵n程名稱系統(tǒng)工程授課教師授課課時(shí)4學(xué)習(xí)課題系統(tǒng)優(yōu)化教學(xué)基本要求（1）理解系統(tǒng)優(yōu)化的含義；（2）掌握總成本分析法、綜合評價(jià)法運(yùn)輸方式的選擇；（3）理解單車輛路徑優(yōu)化問題；（4）掌握分枝定界法、簡單貪夢算法、奇偶點(diǎn)圖上作業(yè)法、動態(tài)規(guī)劃法、標(biāo)號法的單車輛路徑優(yōu)化問題求解；（5）理解多車輛路徑優(yōu)化問題；（6）掌握掃描法、節(jié)約里程法的多車輛路徑優(yōu)化問題求解。教學(xué)重點(diǎn)、難點(diǎn)運(yùn)輸方式的選擇；單車輛路徑優(yōu)化；多車輛路徑優(yōu)化。教學(xué)方法、手段案例導(dǎo)入法、講授法、小組討論法教學(xué)過程設(shè)計(jì)導(dǎo)入——專題講解——問題分析討論——練習(xí)——?dú)w納總結(jié)參考案例來自教材、相關(guān)參考書教具、教材教學(xué)課件PPT、教學(xué)錄像片

教師學(xué)期授課教案授課提綱及重難點(diǎn)分析教學(xué)方法設(shè)計(jì)時(shí)間分配及旁注案例引入約10min任務(wù)一系統(tǒng)優(yōu)化的認(rèn)識一、系統(tǒng)優(yōu)化的含義系統(tǒng)優(yōu)化是在滿足各方面限制條件的情況下，通過科學(xué)的方法，建立與現(xiàn)實(shí)系統(tǒng)相對應(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)化是對現(xiàn)有系統(tǒng)存在的不同方面的問題進(jìn)行針對性的分析，進(jìn)而構(gòu)建優(yōu)化模型并求解，最終使現(xiàn)有系統(tǒng)得到優(yōu)化。二、系統(tǒng)優(yōu)化的方法（一)運(yùn)籌學(xué)方法1.規(guī)劃論規(guī)劃論又稱為數(shù)學(xué)規(guī)劃，是運(yùn)籌學(xué)的一個(gè)分支，是研究對現(xiàn)有資源進(jìn)行統(tǒng)一分配、合理安排、合理調(diào)度和最優(yōu)設(shè)計(jì)以取得最大經(jīng)濟(jì)效果的數(shù)學(xué)理論方法。例如，對某項(xiàng)確定的任務(wù)，怎樣以最少的人力、物力去完成；對給定的人力、物力，怎樣能使其最大限度地發(fā)揮作用，從而完成盡可能多的任務(wù)。一般規(guī)劃論可以歸結(jié)為在滿足既定目標(biāo)的要求下，按照某一衡量指標(biāo)尋求最優(yōu)方案的問題。通常把必須滿足的條件稱為約束條件，把衡量指標(biāo)稱為目標(biāo)函數(shù)，用數(shù)學(xué)語言來描述為：求目標(biāo)函數(shù)在一定約束條件下的極值問題。2.圖論圖論（GraphTheory）是數(shù)學(xué)的一個(gè)分支，它以圖為研究對象。圖論中的圖是由若干給定的點(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)用最省等。3.排隊(duì)論排隊(duì)論（QueuingTheory）又稱隨機(jī)服務(wù)系統(tǒng)理論，是運(yùn)籌學(xué)的一個(gè)分支。它是研究系統(tǒng)隨機(jī)聚散現(xiàn)象和隨機(jī)服務(wù)系統(tǒng)工作過程的數(shù)學(xué)理論和方法，通過對服務(wù)對象到來及服務(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ù)對象，使得服務(wù)系統(tǒng)既能滿足服務(wù)對象的需要，又能使機(jī)構(gòu)的費(fèi)用最經(jīng)濟(jì)或某些指標(biāo)最優(yōu)。排隊(duì)論是研究服務(wù)系統(tǒng)中排隊(duì)現(xiàn)象隨機(jī)規(guī)律的學(xué)科，專門研究因隨機(jī)因素而產(chǎn)生擁擠的方法，可協(xié)調(diào)和解決請求服務(wù)和提供服務(wù)雙方之間存在的相互約束關(guān)系。4.存儲論為了解決供應(yīng)（生產(chǎn)）與需求（消費(fèi)）之間的不協(xié)調(diào)（這種不協(xié)調(diào)一般表現(xiàn)為供應(yīng)量與需求量和供應(yīng)時(shí)期與需求時(shí)期的不一致，出現(xiàn)供不應(yīng)求或供過于求），人們在供應(yīng)與需求這兩個(gè)環(huán)節(jié)之間加入存儲這一環(huán)節(jié)，就能緩解供應(yīng)與需求之間的不協(xié)調(diào)。以此為研究對象，利用運(yùn)籌學(xué)的方法即可解決最合理、最經(jīng)濟(jì)的存儲問題。專門研究這類有關(guān)存儲問題的科學(xué)叫作存儲論，它也是運(yùn)籌學(xué)的一個(gè)分支。存儲論也稱為庫存論，是主要研究物資庫存策略的理論，用于確定物資庫存量、補(bǔ)貨頻率和補(bǔ)貨量等問題。庫存的目的是為生產(chǎn)經(jīng)營活動的持續(xù)進(jìn)行提供有力的保障。（二)啟發(fā)式算法1.智能優(yōu)化算法智能優(yōu)化算法從與研究問題有關(guān)的基本模型和算法中獲得啟發(fā)，發(fā)現(xiàn)解決問題的思路和途徑，通過對過去經(jīng)驗(yàn)的歸納推理以及試驗(yàn)分析來解決問題。具體邏輯思路如下圖所示。2.模擬退火算法模擬退火算法（SimulatedAnnealing，SA）最早的思想是由N.Metropoli松等人于1953年提出的。該算法來源于固體退火原理，是一種基于概率的算法，將固體加熱至充分高溫，再讓其徐徐冷卻，加熱時(shí)，固體內(nèi)部粒子隨溫度升高變?yōu)闊o序狀，內(nèi)能增大；在徐徐冷卻時(shí)粒子漸趨有序，冷卻過程中每個(gè)粒子都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。用模擬退火算法尋找最優(yōu)解的過程類似于退火現(xiàn)象中尋找系統(tǒng)的最低能量，把優(yōu)化問題的狀態(tài)看作固體內(nèi)部的粒子，把目標(biāo)函數(shù)看作粒子所處的能態(tài)，得到的最優(yōu)解對應(yīng)于固體最后在常溫時(shí)達(dá)到的基態(tài)。具體邏輯思路如下圖所示。3.遺傳算法遺傳算法（GeneticAlgorithm，GA）最早是由美國的JohnHolland于20世紀(jì)70年代提出的。該算法是根據(jù)大自然中生物體的進(jìn)化規(guī)律而設(shè)計(jì)提出的，是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)制的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。具體邏輯思路如下圖所示。遺傳算法通過數(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í)、信號處理、自適應(yīng)控制和人工生命等領(lǐng)域。4.蟻群算法蟻群算法的靈感來自螞蟻尋找最短覓食路徑的過程。蟻群在覓食過程中會在所經(jīng)過的路徑上留下一種揮發(fā)性分泌物——信息素，信息素能被一定范圍內(nèi)的螞蟻察覺并影響它們的行為。當(dāng)一些路徑上通過的螞蟻越來越多時(shí)，其信息素的強(qiáng)度也越來越大，這樣其他螞蟻選擇該路徑的概率也越來越高。它們不斷發(fā)現(xiàn)更短路徑，逐漸地，這一條最短路徑就會被大多數(shù)螞蟻重復(fù)，從而形成最短路徑。（三)系統(tǒng)仿真法系統(tǒng)仿真法是一種根據(jù)被研究的系統(tǒng)模型，在仿真環(huán)境和條件下，對系統(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)優(yōu)化的內(nèi)容系統(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)化，即路徑優(yōu)化、車輛調(diào)度、運(yùn)輸方式選擇、路網(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)用問題。（二)車輛調(diào)度車輛的調(diào)度就是如何配置車輛，才能使得其既能滿足運(yùn)輸需求，又能最經(jīng)濟(jì)。通?？梢圆捎弥概蓡栴}建模求解的方法、多車輛路徑優(yōu)化問題建模求解的方法等進(jìn)行建模求解。（三)運(yùn)輸方式選擇當(dāng)有多種可選擇的運(yùn)輸方式時(shí)，選擇最優(yōu)的運(yùn)輸方式，通常采用總成本分析法、綜合評價(jià)法等進(jìn)行選擇。（四)路網(wǎng)規(guī)劃假設(shè)給定一些城市，已知每對城市之間交通線的建造費(fèi)用，要求建造一個(gè)連接這些城市的交通網(wǎng)，且使得總的建造費(fèi)用最小，這就是賦權(quán)圖上的最小生成樹問題。這類問題的求解過程也就是路網(wǎng)規(guī)劃的過程。約40min任務(wù)二運(yùn)輸方式的選擇一、總成本分析法的運(yùn)輸方式的選擇（一)方法介紹總成本分析法的要旨是在保持一定服務(wù)水平的條件下，考慮所有有關(guān)成本的項(xiàng)目。對備選方案進(jìn)行評價(jià)時(shí)，各種不同方案可能會導(dǎo)致某些業(yè)務(wù)活動的成本增加、減少，或保持不變。該方法的目標(biāo)是選擇總成本最小的方案。由于系統(tǒng)運(yùn)作各環(huán)節(jié)之間的效益相恃，某環(huán)節(jié)成本降低會導(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)輸成本：（2）計(jì)算各方案的在途庫存成本：（3）計(jì)算各方案的供貨工廠的存貨成本：（4）計(jì)算各方案的需求倉庫存貨成本：（5）計(jì)算各方案的庫存成本：（6）計(jì)算各方案的總成本：（7）對比各方案的總成本，選擇總成本最小的方案。（三）舉例二、綜合評價(jià)法的運(yùn)輸方式的選擇（一)方法介紹1.定義綜合評價(jià)法是運(yùn)用多個(gè)指標(biāo)對多個(gè)參評單位進(jìn)行綜合統(tǒng)計(jì)評價(jià)的方法，用來判斷企業(yè)的走向和目標(biāo)。2.主要要素（1）評價(jià)者：可以是某個(gè)人或某個(gè)團(tuán)體。評價(jià)目的的給定、評價(jià)指標(biāo)的建立、評價(jià)模型的選擇、權(quán)重系數(shù)的確定都與評價(jià)者有關(guān)。（2）被評價(jià)對象：隨著綜合評價(jià)技術(shù)理論的發(fā)展與實(shí)踐活動的開展，評價(jià)的領(lǐng)域也從最初的各行各業(yè)經(jīng)濟(jì)統(tǒng)計(jì)的綜合評價(jià)拓展到后來的技術(shù)水平、生活質(zhì)量、社會發(fā)展、環(huán)境質(zhì)量、競爭能力、綜合國力、績效考評等方面，這些都可以為被評價(jià)對象。（3）評價(jià)指標(biāo)：從多個(gè)視角和層次反映特定評價(jià)客體的數(shù)量規(guī)模與數(shù)量水平。（4）權(quán)重系數(shù)：其合理與否關(guān)系到綜合評價(jià)結(jié)果的可信程度。（5）綜合評價(jià)模型：是指通過一定的數(shù)學(xué)模型，將多個(gè)評價(jià)指標(biāo)值合成為一個(gè)整體性的綜合評價(jià)值。3.步驟（1）確定綜合評價(jià)指標(biāo)體系，這是綜合評價(jià)的基礎(chǔ)和依據(jù)。（2）收集數(shù)據(jù)，指標(biāo)同度量處理，確定指標(biāo)體系中各指標(biāo)的權(quán)數(shù)，以保證評價(jià)的科學(xué)性。常用的權(quán)重確定方法有層次分析法（AHP）、專家打分法、問卷調(diào)查法等。（3）選擇適當(dāng)模型計(jì)算綜合評價(jià)指標(biāo)。常見的綜合評價(jià)模型主要有綜合指數(shù)法、加權(quán)綜合法、功效系數(shù)法、Topsis法、密切值法、AHP、模糊綜合評價(jià)法、秩和比法等。（4）根據(jù)綜合評價(jià)指標(biāo)值或分值的大小，對被評價(jià)對象進(jìn)行排序，并由此得出結(jié)論。（二)綜合評價(jià)法選擇運(yùn)輸方式的步驟（1）確定影響運(yùn)輸方式選擇的因素，即評價(jià)指標(biāo)體系，主要考慮經(jīng)濟(jì)性、迅速性、安全性、便利性，當(dāng)然還有環(huán)境影響、社會效益等。（2）確定影響因素的權(quán)重系數(shù)，即確定指標(biāo)體系中各指標(biāo)的權(quán)重。確定權(quán)重系數(shù)是為了顯示每個(gè)影響因素在運(yùn)輸方式選擇中所具有的重要程度，分別給予不同的比例系數(shù)（也稱加權(quán)）。（3）選擇適當(dāng)模型計(jì)算綜合評價(jià)指標(biāo)，即運(yùn)輸方式的綜合重要度。通常候選的運(yùn)輸方式有四種：公路、鐵路、水路和航空運(yùn)輸。（4）比較和選擇，即根據(jù)綜合評價(jià)指標(biāo)值或分值的大小，對被評價(jià)對象進(jìn)行排序，并由此得出結(jié)論。（三）舉例約40min任務(wù)三單車輛路徑優(yōu)化運(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)化主要是對單一運(yùn)輸車輛從起點(diǎn)到終點(diǎn)間的最短行車路線進(jìn)行規(guī)劃和優(yōu)化。單車輛運(yùn)輸路徑優(yōu)化問題可分為兩種類型：（1）起詭點(diǎn)相同的車輛路徑問題；（2）起詭點(diǎn)不同的車輛路徑問題。一、起詭點(diǎn)相同的單車輛路徑優(yōu)化（一)問題介紹1.問題描述一輛貨車從某設(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)、流動售貨車的行駛等，都會碰到行車路線如何設(shè)計(jì)的問題。2.模型旅行商問題TSP、中國郵遞員問題等都是起詭點(diǎn)重合的單車輛運(yùn)輸問題。起詭點(diǎn)重合的線路設(shè)計(jì)的一般原則和要求是:（1）車輛要經(jīng)過所有的點(diǎn)；（2）行駛時(shí)間最短或總距離最短。3.求解方法（1）如果節(jié)點(diǎn)數(shù)目較少，可運(yùn)用簡單貪夢算法或窮舉法求解，且窮舉法可以得到最佳方案。（2）對于中小規(guī)模的TSP問題，利用運(yùn)籌學(xué)中的分枝定界法和奇偶點(diǎn)圖上作業(yè)法進(jìn)行求解也比較有效。（3）由于枚舉的次數(shù)為（n—1）!/2次，所以對于大規(guī)模節(jié)點(diǎn)的路徑優(yōu)化問題，一般很難獲得最優(yōu)解，只能通過啟發(fā)式算法（Hopfield神經(jīng)網(wǎng)絡(luò)方法、遺傳算法等）獲得近似最優(yōu)解。（二)分枝定界法的TSP問題求解1.旅行商問題介紹有若干個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)，必須經(jīng)過每一個(gè)城市且在一個(gè)城市只逗留一次，最后回到出發(fā)的城市，如何事先確定一條最短的線路，以保證其旅行費(fèi)用最少？旅行商問題又稱為旅行推銷員問題、貨郎擔(dān)問題，簡稱為TSP問題，是最基本的路線問題，求解方法主要有枚舉法、分枝定界法、簡單貪夢算法等。首先，每個(gè)城市都必須被訪問；其次，要使總路徑最短，各城市最好只被訪問一次。按照這兩個(gè)要求，可建立TSP問題的01整數(shù)規(guī)劃模型。1）決策變量xij2）目標(biāo)函數(shù)3）約束條件2.分枝定界法介紹分枝定界法（BranchandBound）是由三棲學(xué)者查理德.卡普（RichardM.karp）在20世紀(jì)60年代發(fā)明的，該法成功求解了含有65個(gè)城市的旅行商問題，創(chuàng)下了當(dāng)時(shí)的紀(jì)錄?！胺种Α奔窗讶靠尚薪饪臻g反復(fù)地分割為越來越小的子集，“定界”即對每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界（對于最小值問題）。分枝定界法的主要思路是：在每次分枝后，對凡是界限超出已知可行解的那些子集不再做進(jìn)一步分枝（這稱為剪枝），這樣解的許多子集（即搜索樹上的許多節(jié)點(diǎn)）就可以不予考慮，從而縮小了搜索范圍。這一過程反復(fù)進(jìn)行，直到找出可行解為止。該可行解的值不大于任何子集的界限，因此這種算法一般可以求得最優(yōu)解。3.分枝定界法的求解步驟分枝定界法求解問題的邏輯示意圖如下圖所示。假設(shè)有n個(gè)城市節(jié)點(diǎn)，分枝定界法的步驟如下：（1）構(gòu)建費(fèi)用（代價(jià)）矩陣D，求得初始最短路徑。（2）判斷可行解和最優(yōu)解。4.舉例（三)簡單貪樊算法的TSP問題求解1.簡單貪夢算法介紹簡單貪夢算法在對問題進(jìn)行求解時(shí)，總是做出當(dāng)前情況下的最好選擇，每次選擇得到的都是局部最優(yōu)解。選擇的策略必須具備無后效性，即某個(gè)狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。2.算法步驟（1）從某一個(gè)城市開始，每次選擇一個(gè)城市，直到走完所有的城市。（2）每次在選擇下一個(gè)城市的時(shí)候，只考慮當(dāng)前情況，保證迄今為止經(jīng)過的路徑總距離最小。（3）如果所有位置都被選擇了，則停止，否則返回到第（2）步。3.舉例（四)奇偶點(diǎn)圖上作業(yè)法的中國郵遞員問題求解1.中國郵遞員問題介紹中國郵遞員問題即中國郵路問題，是我國數(shù)學(xué)家管梅谷于1960年首次提出的。其問題模型可以描述為：一位郵遞員從郵局選好郵件去投遞，然后返回郵局，他必須經(jīng)過由他負(fù)責(zé)投遞的每條街道至少一次，為這位郵遞員設(shè)計(jì)一條投遞線路，使其耗時(shí)最少。中國郵遞員問題與七橋問題（一種著名的古典圖論）聯(lián)系很密切，七橋問題又稱為一筆畫問題。七橋問題模型可描述為：河中有兩個(gè)島嶼，河的兩岸和島嶼之間有七座橋相互連接。一般問法為：一個(gè)人怎樣才能不重復(fù)、不遺漏地走過這七座橋，最終回到原出發(fā)地？中國郵遞員問題與七橋問題這兩個(gè)問題模型可以歸結(jié)為：在平面上給出一個(gè)連通的線性圖，要求將這個(gè)線性圖從某點(diǎn)開始一筆畫出（允許重復(fù)），并且最后仍回到起點(diǎn)，問怎樣畫才能使重復(fù)路線最短。2.奇偶點(diǎn)圖上作業(yè)法介紹1）奇偶點(diǎn)圖上作業(yè)法的要點(diǎn)提煉（1）給定一個(gè)連通多重圖G。（2）連通多重圖G有歐拉圈，當(dāng)且僅當(dāng)G中無奇點(diǎn)。（3）連通多重圖G有歐拉鏈，當(dāng)且僅當(dāng)G恰有2個(gè)奇點(diǎn)。（4）如果在某郵遞員所負(fù)責(zé)范圍內(nèi)的街道圖中沒有奇點(diǎn)，那么他就可以從郵局出發(fā)，走過每條街道一次且僅一次，最后回到郵局，這樣他所走的路程就是最短的路程。（5）對于有奇點(diǎn)的街道圖，就必須在某些街道上重復(fù)走一次或多次。（6）在任何一個(gè)圖中，如有奇點(diǎn)，奇點(diǎn)個(gè)數(shù)必為偶數(shù)。因此，在圖中，奇點(diǎn)可以配成對。（7）因?yàn)閳D是連通的，因此，每一對奇點(diǎn)之間必有一條鏈，把這條鏈上所有邊作為重復(fù)邊加到圖中去，形成的新連通圖中必定無奇點(diǎn)，即可得到一個(gè)可行方案。2）奇偶點(diǎn)圖上作業(yè)法的定理重復(fù)邊總權(quán)最小的充分必要條件如下：（1）每條邊最多重復(fù)一次；（2）對圖G中每個(gè)初等圈來講，重復(fù)邊的長度之和不超過圈長的一半。重復(fù)邊的總權(quán)最小，即為最優(yōu)解。3.奇偶點(diǎn)圖上作業(yè)法的步驟（1）尋找初始可行方案。（2）調(diào)整可行方案，使重復(fù)邊最多為一次，總長不斷減少。3）檢查圖中每個(gè)初等圈是否滿足定理“每條邊最多重復(fù)一次”和“對圖G中每個(gè)初等圈來講，重復(fù)邊的長度之和不超過圈長的一半”，如不滿足則調(diào)整到滿足為止。（4）檢查最終圖形中的每個(gè)圈。若定理（1）（2）均已滿足，則圖中的歐拉回路就是最優(yōu)路線。4.舉例二、起詭點(diǎn)不同的單車輛路徑優(yōu)化（一)問題介紹1.問題描述現(xiàn)有A、E兩座不同的城市，有一批貨需要從A運(yùn)送到E，如何選擇路徑才能使得從A到E的距離最短，這就是起詭點(diǎn)不同的單車輛運(yùn)輸路徑優(yōu)化問題。2.模型用節(jié)點(diǎn)代表經(jīng)過的縣市或站點(diǎn)，箭頭表示兩點(diǎn)間是連通的；箭頭線上的數(shù)字表示兩點(diǎn)間的運(yùn)輸代價(jià)。運(yùn)輸代價(jià)可以是時(shí)間、距離或時(shí)間與距離的加權(quán)平均。以路徑最短為目標(biāo)構(gòu)建模型，確定出從起點(diǎn)A到終點(diǎn)E的最佳運(yùn)輸路線，這類問題被歸結(jié)為運(yùn)籌學(xué)中的最短路徑問題。3.求解要求解這類問題的最短線路,最直接的方法就是窮舉法,如下圖所示的網(wǎng)絡(luò)中,從A到E的線路共計(jì)16條,全部列出來并逐一計(jì)算各線路的總距離進(jìn)行比較,很快就能找出最短路是“A一B2一C1一D1一E”。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)較少的時(shí)候,窮舉法是最有效的方法。但是,當(dāng)節(jié)點(diǎn)增加后,可行方案呈指數(shù)倍增加,就需要借助其他方法來進(jìn)行求解,主要有Dijkstra法、動態(tài)規(guī)劃法、逐次逼近法等。本書主要介紹Dijkstra方法和動態(tài)規(guī)劃法。（二)Dijkstra方法的最短路徑問題求解1.Dijkstra方法介紹Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家E.W.Dijkstra于1959年提出的,又叫標(biāo)號法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法,解決的是有權(quán)圖中最短路徑問題。在此算法思想基礎(chǔ)上,人們演繹出了幾十種不同的路徑優(yōu)化算法,盡管如此,Dijkstra方法仍是目前求解最短路徑問題最常用的方法。2.步驟3.舉例（三)動態(tài)規(guī)劃法的最短路徑問題求解1.方法介紹在現(xiàn)實(shí)生活中，有一類活動由于它的特殊性，可將過程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過程達(dá)到最好的活動效果。因此各個(gè)階段決策的選取不能任意確定，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過程的一條活動路線，這種把一個(gè)問題看作一個(gè)前后關(guān)聯(lián)且具有鏈狀結(jié)構(gòu)的多階段過程稱為多階段決策過程，這種問題稱為多階段決策問題。動態(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)立了動態(tài)規(guī)劃。動態(tài)規(guī)劃的應(yīng)用極其廣泛，包括經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)、最優(yōu)控制、工業(yè)生產(chǎn)、軍事以及自動化控制等領(lǐng)域，并在背包問題、生產(chǎn)經(jīng)營問題、庫存管理、資金管理問題、資源分配問題、設(shè)備更新問題、最短路徑問題和復(fù)雜系統(tǒng)可靠性問題、排序問題、裝載問題等中取得了顯著的效果。2.步驟（1）根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)特征將整個(gè)線路網(wǎng)絡(luò)劃分為多個(gè)階段。（2）對每個(gè)階段的決策問題求解。通常采用從終點(diǎn)到起點(diǎn)的逆序法進(jìn)行決策，因此決策階段編號是按逆序進(jìn)行的。（3）從最后一個(gè)階段開始,將每個(gè)階段決策的距離最短的點(diǎn)依次連接起來即得到從起點(diǎn)到詭點(diǎn)的最短路線。3.舉例約30min任務(wù)四多車輛路徑優(yōu)化一、多車輛路徑優(yōu)化問題介紹（一)問題描述某貨運(yùn)中心要為q個(gè)客戶提供服務(wù)，已知每個(gè)客戶的地理位置及其貨運(yùn)需求量，貨運(yùn)中心需要調(diào)用多輛貨車來滿足這些客戶的服務(wù)需求，每輛汽車的載重量一定。要求指派多輛貨車，為每輛車分配一定的客戶，并確定客戶的服務(wù)順序，即行車路徑，目的是使總服務(wù)成本（如距離、時(shí)間等）最低。此外，還有一些約定的要求，例如，每條路線的貨運(yùn)量不能超過汽車載重量,每個(gè)客戶的需求必須且只能由一輛汽車來完成，等等。這種問題就是多車輛路徑問題（VehicleRoutingProblem,VRP）。（二)多車輛路徑問題數(shù)學(xué)模型1.假設(shè)（1）單一貨運(yùn)中心,多部車輛配送。（2）每個(gè)需求點(diǎn)由一輛車服務(wù),每個(gè)客戶的貨物需求量不超過車輛的載重容量。（3）車輛為單一車種,即視為相同的載重量,且有容量限制。（4）無時(shí)間窗限制的配送問題。（5）客戶的位置和需求量均為已知。（6）配送的貨物視為同一種商品,便于裝載。2.參數(shù)說明3.決策變量4.目標(biāo)函數(shù)5.約束條件（三)多車輛路徑問題求解方法多車輛路徑問題的求解方法主要有掃描法、節(jié)約里程法、精確優(yōu)化法、人工智能法、模擬法、啟發(fā)式方法等。1.掃描法掃描法是比較有代表性的啟發(fā)式方法,它是由Gillette和Miller提出的。該方法先將節(jié)點(diǎn)的需求進(jìn)行分組或劃群,然后對每一組按旅行商問題求解,設(shè)計(jì)出一條最佳的路線。這種方法也稱為兩階段法,即先對客戶群進(jìn)行劃分,每個(gè)客戶群用一輛車來完成配送服務(wù),然后再確定每個(gè)群內(nèi)的最短路線。2.節(jié)約里程法節(jié)約里程法（savingMethod）是最具代表性的啟發(fā)式方法,它是由clarke和wright在1964年提出的。許多成功的車輛調(diào)度軟件就是根據(jù)該方法或其改進(jìn)方法開發(fā)的。3.精確優(yōu)化法精確優(yōu)化法主要是指運(yùn)用線性規(guī)劃和非線性規(guī)劃技術(shù)進(jìn)行的最優(yōu)決策。在研究VRP問題的早期,主要解決從單源點(diǎn)派車如何用最短路線或在最短時(shí)間內(nèi)對一定數(shù)量需求點(diǎn)運(yùn)輸?shù)恼{(diào)度問題,即著眼于最優(yōu)算法。4.人工智能法人工智能技術(shù)及其應(yīng)用的不斷發(fā)展,尤其是模擬退火算法、遺傳算法以及人工神經(jīng)網(wǎng)絡(luò)和專家系統(tǒng)等新技術(shù)的發(fā)展,為解決大規(guī)模、多目標(biāo)車輛調(diào)度問題提供了新的途徑。5.模擬法模擬法是指利用數(shù)學(xué)公式、邏輯表達(dá)式、圖表、坐標(biāo)圖形等抽象概念表示實(shí)際運(yùn)輸系統(tǒng)內(nèi)部狀態(tài)和輸入、輸出的關(guān)系,并通過計(jì)算機(jī)對模型進(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)勢而成為復(fù)雜運(yùn)輸調(diào)度系統(tǒng)建模的主要方法。6.啟發(fā)式方法用啟發(fā)式方法解決問題時(shí)，強(qiáng)調(diào)的是“滿意”解，而不是去追求最優(yōu)性。用啟發(fā)式方法求解問題是通過不斷的選代過程實(shí)現(xiàn)的，因而需擬定出一套解的搜索規(guī)則。為了能得到滿意解，在整個(gè)選代過程中要不斷吸收新的信息，必要時(shí)還要改變原來擬定的不合適策略，建立新的搜索規(guī)劃，注意從失敗中吸取教訓(xùn)，并逐步縮小搜索范圍。啟發(fā)式方法就是通過經(jīng)驗(yàn)法則來求取運(yùn)輸過程的滿意解。它能同時(shí)滿足詳細(xì)描繪問題和求解的需要，與精確優(yōu)化法相比，啟發(fā)式方法更加實(shí)用；其缺點(diǎn)是難以判斷解的滿意度。本書主要介紹掃描法和