運(yùn)輸及配送路線的規(guī)劃

1、第八章 運(yùn)輸及配送路線的優(yōu)化教學(xué)目的：使學(xué)生理解各種運(yùn)輸方式的特點(diǎn)及運(yùn)輸方式選擇的原則，掌握運(yùn)輸方式選擇的定量分析法，理解存在中間運(yùn)轉(zhuǎn)的物資調(diào)配方法，掌握旅行商問(wèn)題和中國(guó)郵遞員問(wèn)題的解法以及掃描法和節(jié)約法。基本要求：1、理解各種運(yùn)輸方式的特點(diǎn)；2、掌握運(yùn)輸方式選擇的定量分析法；3、理解存在中間運(yùn)轉(zhuǎn)的物資調(diào)配方法；4、掌握旅行商問(wèn)題和中國(guó)郵遞員問(wèn)題的解法。教學(xué)重點(diǎn)：掃描法、節(jié)約法教學(xué)時(shí)數(shù)：6學(xué)時(shí)第一節(jié) 運(yùn)輸方式的選擇o 運(yùn)輸方式選擇的原則當(dāng)同時(shí)存在多種運(yùn)輸方式可供選擇的情況下，就需要進(jìn)行選優(yōu)抉擇。通常根據(jù)各種運(yùn)輸方式的經(jīng)濟(jì)特性和服務(wù)特征來(lái)選擇合適的運(yùn)輸方式，即主要依據(jù)運(yùn)輸成本、運(yùn)輸速度、可靠性、

2、安全性等指標(biāo)進(jìn)行判斷和選擇。安全性原則首要的原則及時(shí)性原則準(zhǔn)確性原則經(jīng)濟(jì)性原則主要原則貨物運(yùn)輸?shù)牧蠓绞剑?根據(jù)運(yùn)輸工具的不同，可分為： 水路、公路、鐵路、航空、管道和多式聯(lián)運(yùn)等運(yùn)輸形式。 在各種運(yùn)輸方式中，如何選擇適當(dāng)?shù)倪\(yùn)輸方式是物流合理化的重要問(wèn)題?？梢赃x擇一種運(yùn)輸方式也可以選擇使用聯(lián)運(yùn)的方式。 運(yùn)輸方式的選擇，需要根據(jù)運(yùn)輸環(huán)境、運(yùn)輸服務(wù)的目標(biāo)要求，采取定性分析與定量分析的方法進(jìn)行考慮。 o 運(yùn)輸方式選擇的定性分析法定性分析法主要是依據(jù)完成運(yùn)輸任務(wù)可用的各種運(yùn)輸方式的運(yùn)營(yíng)特點(diǎn)及主要功能、貨物的特性以及貨主的要求等因素對(duì)運(yùn)輸方式進(jìn)行直觀選擇的方法。 1. 單一運(yùn)輸方式的選擇單一運(yùn)輸方式的選擇

3、，就是選擇一種運(yùn)輸方式提供運(yùn)輸服務(wù)。公路、鐵路、水路、航空和管道五種基本運(yùn)輸方式各有自身的優(yōu)點(diǎn)與不足，可以根據(jù)五種基本運(yùn)輸方式的優(yōu)勢(shì)、特點(diǎn)，結(jié)合運(yùn)輸需求進(jìn)行恰當(dāng)?shù)倪x擇。 一般要考慮的因素是： 運(yùn)費(fèi)的高低 運(yùn)輸時(shí)間的長(zhǎng)短 頻度運(yùn)、配送次數(shù) 運(yùn)輸能力運(yùn)量的大小 貨物的安全性運(yùn)輸途中的破損或污染等 到貨時(shí)間的準(zhǔn)確性各種運(yùn)輸方式的比較2.多式聯(lián)運(yùn)的選擇 多式聯(lián)運(yùn)的選擇，就是選擇兩種以上的運(yùn)輸方式聯(lián)合起來(lái)提供運(yùn)輸服務(wù)。在實(shí)際運(yùn)輸中，一般只有鐵路與公路聯(lián)運(yùn)、公路或鐵路與水路聯(lián)運(yùn)、航空與公路聯(lián)運(yùn)得到較為廣泛的應(yīng)用。 鐵路與公路聯(lián)運(yùn)，即公鐵聯(lián)運(yùn)，又稱為馱背運(yùn)輸，是指在鐵路平板車上載運(yùn)卡車拖車進(jìn)行的長(zhǎng)距離運(yùn)輸。

4、公路或鐵路與水路聯(lián)運(yùn)，又稱為魚背運(yùn)輸，是指將卡車拖車、火車車廂或集裝箱轉(zhuǎn)載駁船上或大型船舶上進(jìn)行的長(zhǎng)距離運(yùn)輸。魚背運(yùn)輸最大的優(yōu)勢(shì)是運(yùn)量大、運(yùn)費(fèi)低，所以在國(guó)際多式聯(lián)運(yùn)中被廣泛采用。航空與公路聯(lián)運(yùn)也是被廣泛采用的運(yùn)輸方式，這種將航空運(yùn)輸快捷、公路運(yùn)輸靈活方便的多種優(yōu)勢(shì)融合在一起提供的運(yùn)輸服務(wù)，能以最快的方式實(shí)現(xiàn)長(zhǎng)距離“門到門”的貨物運(yùn)輸。o 運(yùn)輸方式選擇的定量分析法運(yùn)輸方式選擇的定量方法有綜合評(píng)價(jià)法、總成本分析法、考慮競(jìng)爭(zhēng)因素的方法等多種方法，應(yīng)用時(shí)可根據(jù)實(shí)際情況選擇其中的一種進(jìn)行定量分析。主要介紹總成本分析法運(yùn)輸方式與運(yùn)輸費(fèi)用的關(guān)系總成本分析法o 以年總成本最低為原則來(lái)選擇合適的運(yùn)輸方式的分析方

5、法。 總成本=運(yùn)輸成本+庫(kù)存成本其中： 運(yùn)輸成本=運(yùn)輸量×運(yùn)費(fèi)率（單位運(yùn)價(jià)）庫(kù)存成本運(yùn)輸庫(kù)存成本 = 運(yùn)輸量×單位存貨成本×運(yùn)輸時(shí)間存儲(chǔ)庫(kù)存成本 = 平均存貨量×單位存貨成本總成本分析法實(shí)例例8-1 某公司欲將產(chǎn)品從坐落位置 A 的工廠運(yùn)往坐落位置 B 的公司自有的倉(cāng)庫(kù)，年運(yùn)量 D 為70萬(wàn)件，每件產(chǎn)品的價(jià)格 C 為30元，每年的存貨成本 I 為產(chǎn)品價(jià)格的30。公司希望選擇使總成本最小的運(yùn)輸方式。據(jù)估計(jì)，運(yùn)輸時(shí)間每減少一天，平均庫(kù)存水平可以減少1。各種運(yùn)輸服務(wù)的有關(guān)參數(shù)如表8-1 所示，試確定最優(yōu)的運(yùn)輸方式。 表8-1 各種運(yùn)輸方式的基本參數(shù)表8-2 各

6、種運(yùn)輸方式的成本計(jì)算結(jié)果經(jīng)過(guò)比較可知，總成本最低的是公路運(yùn)輸方式，其次是馱背運(yùn)輸方式。按照總成本最低的原則，應(yīng)該選擇公路運(yùn)輸方式。例8-2 某制造商分別向兩個(gè)供應(yīng)商購(gòu)買了4000個(gè)配件，每個(gè)配件單價(jià)150元。目前這4000個(gè)配件是由兩個(gè)供應(yīng)商平均提供的，如供應(yīng)商縮短運(yùn)達(dá)時(shí)間，則可以多得到交易份額，每縮短一天，可從總交易量中多得5%的份額，即200個(gè)配件。供應(yīng)商從每個(gè)配件可賺得占配件價(jià)格（不包括運(yùn)輸費(fèi)用）20%的利潤(rùn)。于是，供應(yīng)商A考慮如果將運(yùn)輸方式從鐵路轉(zhuǎn)到卡車運(yùn)輸或航空運(yùn)輸可能會(huì)增加利潤(rùn)。各種運(yùn)輸方式的運(yùn)費(fèi)率和運(yùn)達(dá)時(shí)間如下表所示：試問(wèn)：供應(yīng)商A該如何決策？求解：顯然，供應(yīng)商A只能根據(jù)他可能獲

7、得的潛在利潤(rùn)來(lái)對(duì)運(yùn)輸方式進(jìn)行選擇決策。 下表8-3所示是供應(yīng)商A使用不同的運(yùn)輸方式可能獲得的預(yù)期利潤(rùn)。如果制造商對(duì)能提供更好運(yùn)輸服務(wù)的供應(yīng)商給予更多份額的交易的承諾實(shí)現(xiàn)，則供應(yīng)商A應(yīng)當(dāng)選擇卡車運(yùn)輸。當(dāng)然，與此同時(shí)供應(yīng)商 A 還要密切注意供應(yīng)商B可能做出的競(jìng)爭(zhēng)反應(yīng)行為。第二節(jié) 物資運(yùn)輸調(diào)配決策物資運(yùn)輸調(diào)配決策是指在多個(gè)供應(yīng)地和多個(gè)需求地之間如何合理調(diào)配物資，以實(shí)現(xiàn)在滿足需求前提下的總運(yùn)輸成本最低的目的。這類決策根據(jù)起訖點(diǎn)之間是否存在中間轉(zhuǎn)運(yùn)分兩種情況進(jìn)行討論一、 多起訖點(diǎn)的直達(dá)運(yùn)輸分為:產(chǎn)銷平衡的運(yùn)輸問(wèn)題產(chǎn)銷不平衡的運(yùn)輸問(wèn)題其解法是：表上作業(yè)法運(yùn)輸問(wèn)題實(shí)例練習(xí)： 有三個(gè)產(chǎn)地 ，生產(chǎn)同一種物品，使

8、用者為 ，各產(chǎn)地到各使用者的單位運(yùn)價(jià)見下表所示。這三個(gè)使用者的需求量分別為10、4和6個(gè)單位。由于銷售需要和客觀條件的限制，產(chǎn)地 至少要發(fā)出6個(gè)單位的產(chǎn)品，它最多只能生產(chǎn)11個(gè)單位的產(chǎn)品； 必須發(fā)出7個(gè)單位的產(chǎn)品； 至少要發(fā)出4個(gè)單位的產(chǎn)品。根據(jù)上述條件用表上作業(yè)法求該運(yùn)輸問(wèn)題的最優(yōu)運(yùn)輸方案。各產(chǎn)地到各使用者的單位運(yùn)價(jià)表：二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配這類問(wèn)題又稱為“轉(zhuǎn)運(yùn)問(wèn)題”（一）問(wèn)題描述（二）數(shù)學(xué)模型（三）求解方法o 思路:將轉(zhuǎn)運(yùn)問(wèn)題化為無(wú)轉(zhuǎn)運(yùn)問(wèn)題,再用表上作業(yè)法求解o 1.首先根據(jù)具體問(wèn)題求出最大可能中轉(zhuǎn)量Qo 2.純轉(zhuǎn)運(yùn)站可視為輸出量和輸入量均為Q的一個(gè)產(chǎn)地和銷地 o 3.兼中轉(zhuǎn)站的產(chǎn)地A

9、i視為一個(gè)輸入量Q的銷地及一個(gè)輸出量為ai+Q的產(chǎn)地o 4.兼中轉(zhuǎn)站的銷地Bj視為一個(gè)輸入量bj+Q 的銷地及一個(gè)輸出量為Q的產(chǎn)地轉(zhuǎn)運(yùn)問(wèn)題輸入、輸出、中轉(zhuǎn)量圖示AiQai+QBjbj+QQZQQ轉(zhuǎn)運(yùn)問(wèn)題：在原運(yùn)輸問(wèn)題上增加若干轉(zhuǎn)運(yùn)站。運(yùn)輸方式有：產(chǎn)地 ® 轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站 ® 銷地、產(chǎn)地 ® 產(chǎn)地、產(chǎn)地 ® 銷地、銷地 ® 轉(zhuǎn)運(yùn)站、銷地 ® 產(chǎn)地等。轉(zhuǎn)運(yùn)問(wèn)題實(shí)例例8-3 某公司有兩個(gè)工廠生產(chǎn)變壓器。一個(gè)工廠在A市，另一個(gè)工廠在B市，它們每天的生產(chǎn)能力分別為150和200。變壓器通過(guò)汽車運(yùn)到需求點(diǎn)C市和D市。C市和D市的需求量均為130。

10、公司還需要兩個(gè)中間轉(zhuǎn)運(yùn)站E市和F市進(jìn)行整合運(yùn)輸，各點(diǎn)間單位運(yùn)輸費(fèi)用如下表所示。試確定從工廠到需求點(diǎn)的最優(yōu)路線。項(xiàng)目ABEFCDA013461214B130761312E470388F663078C121387017D141288170求解：該問(wèn)題可分為兩個(gè)階段求解：第一階段：將實(shí)際的轉(zhuǎn)運(yùn)問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)的運(yùn)輸問(wèn)題。 （1）經(jīng)分析可知，該問(wèn)題的最大可能中轉(zhuǎn)量為350。（2）根據(jù)轉(zhuǎn)運(yùn)問(wèn)題的性質(zhì)，確定A、B產(chǎn)地的供應(yīng)量分別為500（150+350）、550（200+350）；E、F中轉(zhuǎn)地的中轉(zhuǎn)量都是350； C、D需求地的需求量均為480（130+350）。（3）建立新的產(chǎn)銷平衡表如下：第二階段：運(yùn)用

11、求解產(chǎn)銷平衡的運(yùn)輸問(wèn)題的表上作業(yè)法求解。 例8-4 騰飛電子儀器公司在大連和廣州有兩個(gè)分廠生產(chǎn)同一種儀器，大連分廠每月生產(chǎn)450臺(tái)，廣州分廠每月生產(chǎn)600臺(tái)。該公司在上海和天津有兩個(gè)銷售公司負(fù)責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市的儀器供應(yīng)。另外因?yàn)榇筮B距離青島較近，公司同意大連分廠向青島直接供貨，運(yùn)輸費(fèi)用如下圖，單位是百元。問(wèn)應(yīng)該如何調(diào)運(yùn)儀器，可使總運(yùn)輸費(fèi)用最低？1- 廣州、2 - 大連、3 - 上海、4 - 天津、5 - 南京、6 - 濟(jì)南、7 - 南昌、8 - 青島解：設(shè) xij 為從 i 到 j 的運(yùn)輸量，可得到如下列運(yùn)輸問(wèn)題模型： 數(shù)學(xué)模型： Min f = 2x13+ 3x14+ 3x

12、23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x38+ 4x45+ 4x46+ 6x47+ 5x48 s.t. x13+ x14 600 (廣州分廠供應(yīng)量限制） x23+ x24+ x28 450 (大連分廠供應(yīng)量限制） x13+ x23 = x35 + x36+ x37 + x38 （上海銷售公司，轉(zhuǎn)運(yùn)站） x14+ x24 = x45 + x46+ x47 + x48 （天津銷售公司，轉(zhuǎn)運(yùn)站） x35+ x45 = 200 （南京的銷量） x36+ x46 = 150 （濟(jì)南的銷量） x37+ x47 = 350 （南昌的銷量） x38+ x48 + x28 = 3

13、00 （青島的銷量） xij 0 , i,j = 1,2,3,4,5,6,7,8用“管理運(yùn)籌學(xué)”軟件求得結(jié)果： x13 = 550 x14 = 0 ； x23 = 0 x24 = 150 x28 = 300 ； x35 = 200 x36 = 0 x37 = 350 x38 = 0 ； x45 = 0 x46 = 150 x47 = 0 x48 = 0 。例8-5 某公司有A1、A2、A3三個(gè)分廠生產(chǎn)某種物質(zhì)，分別供應(yīng)B1、B2、B3、B4四個(gè)地區(qū)的銷售公司銷售。有關(guān)數(shù)據(jù)如下表所示。試求總費(fèi)用為最少的調(diào)運(yùn)方案。假設(shè)： 1. 每個(gè)分廠的物資不一定直接發(fā)運(yùn)到銷地，可以從其中幾個(gè)產(chǎn)地集中 一起運(yùn)；

14、2. 運(yùn)往各銷地的物資可以先運(yùn)給其中幾個(gè)銷地，再轉(zhuǎn)運(yùn)給其他銷地； 3. 除產(chǎn)銷地之外，還有幾個(gè)中轉(zhuǎn)站，在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。各產(chǎn)地、銷地和中轉(zhuǎn)地之間的運(yùn)價(jià)如下表：解：Step1:把此轉(zhuǎn)運(yùn)問(wèn)題轉(zhuǎn)化為一般運(yùn)輸問(wèn)題： 1.把所有產(chǎn)地、銷地、轉(zhuǎn)運(yùn)站都同時(shí)看作產(chǎn)地和銷地； 2.運(yùn)輸表中不可能運(yùn)輸處的運(yùn)費(fèi)取作M，自身對(duì)自身的運(yùn)費(fèi)為0； 3.產(chǎn)量及銷量可定為：中轉(zhuǎn)站：產(chǎn)銷量均為20，產(chǎn)地：原產(chǎn)量+20，銷地：銷量+20。20為最大可能中轉(zhuǎn)量；擴(kuò)大的運(yùn)輸問(wèn)題產(chǎn)銷平衡表： Step2: 運(yùn)用表上作業(yè)法求解第三節(jié) 單一車輛配送路線的優(yōu)化主要是指對(duì)單一運(yùn)輸車輛從起點(diǎn)到終點(diǎn)間的最短行車路線進(jìn)行優(yōu)

15、化。優(yōu)化的目標(biāo)可以是行車時(shí)間最短、距離最短或運(yùn)輸費(fèi)用最小，一般統(tǒng)稱為最短路徑問(wèn)題。單一車輛的配送路線優(yōu)化可分為兩種類型：起訖點(diǎn)不同的單一路線優(yōu)化和起訖點(diǎn)重合的單一路線優(yōu)化。一、起訖點(diǎn)不同的單一路線優(yōu)化主要方法有：動(dòng)態(tài)規(guī)劃法、Dijkstra法、逐次逼近法等不同的求解方法。本節(jié)主要介紹動(dòng)態(tài)規(guī)劃法。動(dòng)態(tài)規(guī)劃 (Dynamic Programming)o 動(dòng)態(tài)規(guī)劃（DP）是運(yùn)籌學(xué)的一個(gè)分支，是解決多階段決策過(guò)程最優(yōu)化的一種數(shù)學(xué)方法。由美國(guó)數(shù)學(xué)家貝爾曼（Ballman）等人在20世紀(jì)50年代提出。他們針對(duì)多階段決策問(wèn)題的特點(diǎn)，提出了解決這類問(wèn)題的“最優(yōu)化原理”，并成功地解決了生產(chǎn)管理 、 工程技術(shù)等方

16、面的許多實(shí)際問(wèn)題。動(dòng)態(tài)規(guī)劃是求解某類問(wèn)題的一種方法，是考察問(wèn)題的一種途徑，但不是一種特殊算法。學(xué)習(xí)動(dòng)態(tài)規(guī)劃就要首先了解多階段決策問(wèn)題多階段決策問(wèn)題 多階段決策問(wèn)題和我們前面遇到的決策問(wèn)題不同，它是和時(shí)間有關(guān)的。與時(shí)間有關(guān)的活動(dòng)過(guò)程稱為動(dòng)態(tài)過(guò)程，其優(yōu)化方法稱為動(dòng)態(tài)規(guī)劃。而與時(shí)間無(wú)關(guān)的活動(dòng)過(guò)程稱為靜態(tài)過(guò)程，相應(yīng)的的優(yōu)化方法稱為靜態(tài)規(guī)劃。所謂多階段決策問(wèn)題是：把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程，也稱為序貫決策過(guò)程。如下圖所示： 1.最短路徑問(wèn)題：給定一個(gè)交通網(wǎng)絡(luò)圖如下，其中兩點(diǎn)之間的數(shù)字表示距離（或運(yùn)費(fèi)），試求從A點(diǎn)到G點(diǎn)的最短距離（總運(yùn)輸費(fèi)用最?。?23456AB1B2C1C2

17、C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643 2、機(jī)器負(fù)荷的分配問(wèn)題設(shè)有某種機(jī)器可以在高、低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。若在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量x的關(guān)系為g=g(x)，這時(shí)，機(jī)器的年完好率為a;若在低負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量x的關(guān)系為h=h(x)，相應(yīng)的機(jī)器年完好率為b。假設(shè)開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為Q，要求制訂一個(gè)五年的生產(chǎn)計(jì)劃，合理分配機(jī)器負(fù)荷，使總收益達(dá)到最高。 3、資源分配問(wèn)題設(shè)有數(shù)量為a的資源，計(jì)劃分配給n個(gè)項(xiàng)目。設(shè)xi ( i=1, 2, ., n)為分配給第i個(gè)項(xiàng)目的

18、資源量，gi ( xi )為第i個(gè)項(xiàng)目得到數(shù)量為xi 的資源后可提供的收益，問(wèn)如何分配資源a，可使總收益為最高？ 4、背包問(wèn)題 有一個(gè)徒步旅行者，其可攜帶物品重量的限度為A公斤，設(shè)有n 種物品可供他選擇裝入包中。已知每種物品的重量及使用價(jià)值（作用），問(wèn)此人應(yīng)如何選擇攜帶的物品，才能使所起作用（使用價(jià)值）最大？物品 1 2 j n重量（公斤/件） a1 a2 aj an每件使用價(jià)值 c1 c2 cj cn動(dòng)態(tài)規(guī)劃的基本概念（1）階段（stage） 階段變量 i 、階段數(shù) n（2）狀態(tài)（State） 狀態(tài)變量si 、可達(dá)狀態(tài)集合Si n 最短路問(wèn)題中，各個(gè)階段結(jié)點(diǎn)就是狀態(tài)n 機(jī)器負(fù)荷分配問(wèn)題中，各

19、階段的完好機(jī)器數(shù)是狀態(tài)n 物資分配問(wèn)題中，分配給前i個(gè)項(xiàng)目的物資量是狀態(tài)（3）決策（decision） 決策變量xi(si)、允許決策集合Di(si) n 機(jī)器負(fù)荷分配問(wèn)題中，分配高（低）負(fù)荷下的機(jī)器數(shù)n 最短路問(wèn)題中，走哪條路n 物資分配問(wèn)題中，分配給每個(gè)項(xiàng)目的物資量（4）策略（Policy）各階段的決策組成的一個(gè)決策序列稱為一個(gè)策略，記為：從階段i開始的過(guò)程，稱為i子過(guò)程，它包含階段i，階段i+1，階段n。i子過(guò)程的決策序列稱為i子策略，記為（5）狀態(tài)轉(zhuǎn)移方程由某一階段的一個(gè)狀態(tài)到下一階段的另一狀態(tài)的演變稱為狀態(tài)轉(zhuǎn)移。描述狀態(tài)轉(zhuǎn)移規(guī)律的方程稱為狀態(tài)轉(zhuǎn)移方程。記為si+1 = gi (si

20、, xi)，gi 稱為狀態(tài)轉(zhuǎn)移函數(shù)。（6）階段指標(biāo)、指標(biāo)函數(shù)、最優(yōu)指標(biāo)函數(shù)階段指標(biāo)(階段收益)，衡量每一階段決策優(yōu)劣的數(shù)量指標(biāo)。動(dòng)態(tài)規(guī)劃的基本方程逆序解法： fn+1 ( sn+1 ) = 0順序解法： f0 ( s0 ) = 0動(dòng)態(tài)規(guī)劃的求解步驟用動(dòng)態(tài)規(guī)劃求解最短路徑問(wèn)題（1）確定問(wèn)題的階段;（2）確定狀態(tài)變量n 用 Si 表示第 i 階段的狀態(tài)變量及其值（3）確定決策變量n 用 xi表示第 i 階段的決策變量，并以 xi*表示該階段的最優(yōu)決策（4）正確寫出狀態(tài)轉(zhuǎn)移方程 si-1= g(si, xi) 逆序求解 si+1= g(si, xi) 順序求解 （5）正確寫出指標(biāo)函數(shù)和遞推關(guān)系式（6

21、）用正向遞推算法或逆向遞推算法求出每階段的最優(yōu)指標(biāo)值及相應(yīng)的最優(yōu)策略 。最后求得全過(guò)程的最優(yōu)策略。 用動(dòng)態(tài)規(guī)劃求解最短路徑問(wèn)題例8-6、從A 地到E 地要鋪設(shè)一條煤氣管道,其中需經(jīng)過(guò)三級(jí)中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。問(wèn)應(yīng)該選擇什么路線，使總距離最短？ AB2B1B3C1C3D1D2E52141126101043121113965810521C2解：整個(gè)計(jì)算過(guò)程分四個(gè)階段，從最后一個(gè)階段開始。第四階段（D E）： D 有兩條路線到終點(diǎn)E 。 顯然有第三階段（C D）： C 到D 有 6 條路線?？紤]經(jīng)過(guò)C1 的兩條路線(最短路線為 )考慮經(jīng)過(guò)C2 的兩條路線(最短路線為 )考

22、慮經(jīng)過(guò)C3 的兩條路線最短路線為第二階段（B C）： B 到C 有 9 條路線?？紤]經(jīng)過(guò)B1 的3條路線最短路線為考慮經(jīng)過(guò)B2 的3條路線最短路線為考慮經(jīng)過(guò)B3 的3條路線最短路線為第一階段（A B）： A 到B 有 3 條路線。最短路線為（最短距離為19）o 用Dijkstra標(biāo)號(hào)算法求最短路問(wèn)題的實(shí)例略自己在課下練習(xí)二、起訖點(diǎn)重合的單一路線優(yōu)化o 起訖點(diǎn)重合的線路優(yōu)化主要是指從某點(diǎn)出發(fā)訪問(wèn)一定數(shù)量顧客后又回到原來(lái)出發(fā)點(diǎn)的線路優(yōu)化問(wèn)題。現(xiàn)實(shí)生活中存在著許多類似的問(wèn)題，如配送車輛送貨、郵遞員送報(bào)、送奶工送牛奶、垃圾車輛收集垃圾等。 (一)旅行售貨員問(wèn)題（Traveling Salesman P

23、roblem）1. 問(wèn)題描述某售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費(fèi))。他要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一次，最后回到駐地的路線，使總的路程(或總旅費(fèi))最小。TSP也可用網(wǎng)絡(luò)圖或矩陣描述：2. 數(shù)學(xué)模型TSP除了可以用文字?jǐn)⑹龊途W(wǎng)絡(luò)圖來(lái)描述以外，還可以使用模型化的形式來(lái)表達(dá)，即用整數(shù)規(guī)劃模型來(lái)表達(dá)。上述0-1規(guī)劃模型的約束條件的含義：第一組約束表示：每個(gè)城市必去，且僅去一次；第二組約束表示：每個(gè)城市必離，且僅離一次第三組約束表示：不允許有兩個(gè)城市間的循環(huán)；第四組約束表示：不允許有三個(gè)城市間的循環(huán)；以下諸式含義與此類同。3. 求解方法o TSP是一個(gè)典型的NPHard問(wèn)題

24、，對(duì)于大規(guī)模的線路優(yōu)化問(wèn)題，無(wú)法獲得最優(yōu)解，只有通過(guò)啟發(fā)式算法獲得近優(yōu)解。下面介紹兩種比較簡(jiǎn)單的啟發(fā)式算法：（1）貪婪算法（最近鄰點(diǎn)法）Step1:首先選擇離出發(fā)點(diǎn)最近的點(diǎn)；Step2:再?gòu)氖Ｏ碌狞c(diǎn)中選距離已選擇的點(diǎn)最近的點(diǎn)；Step3:如果所有的點(diǎn)都被選了，則停止；否則返回Step2。例8-7 在下圖中，從配送中心A出發(fā)，送貨到B、C、D三個(gè)客戶需求站。任意兩點(diǎn)間的距離已知（如圖中所示），求最佳配送路徑。 最佳配送路線為：ABCDA 總路程 = 22+18+38+45 = 123最近鄰點(diǎn)法極為直觀與簡(jiǎn)單，但結(jié)果的滿意度往往較差。（2）最近插值法（Nearest Insertion）o 最近插

25、值法是Rosenkrantz和Stearns等人在1977年提出的一種用于解決TSP問(wèn)題的算法，它比上面的最近鄰點(diǎn)法復(fù)雜，但是可以得到相對(duì)比較滿意的解。最近插值法的步驟：Step1. 找到距離起點(diǎn)最近的節(jié)點(diǎn)，形成一個(gè)子回路。Step2. 在剩下的節(jié)點(diǎn)中，尋找一個(gè)距離回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn)Vk Step3. 在子回路中找到一條邊(i,，j)，使得 最小，然后將節(jié)點(diǎn)Vk插入到節(jié)點(diǎn) Vi ，Vj 之間，用兩條邊(i，k)、(k，j)代替原來(lái)的邊(i，j)。Step4. 重復(fù)Step2和Step3，直到所有的節(jié)點(diǎn)都加入子回路中。用最近插值法求解例8-7，并分析所得解的滿意性。 練習(xí)求解下列權(quán)系數(shù)矩陣

26、所表示的TSP解法1 最近鄰點(diǎn)法-總路程= 6+5+15+4+12+15 = 57解法2 最近插值法-總路程 = 10+5+8+6+4+8 = 41案例：“最佳災(zāi)情巡視路線” 今年(1998年)夏天某縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。 1）若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線。 2）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車行駛速度V=35公里/小時(shí)。要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳

27、的巡視路線。公路邊的數(shù)字為該路段的公里數(shù)問(wèn)題分析：本題給出了某縣的公路網(wǎng)絡(luò)圖，要求的是在不同的條件下，災(zāi)情巡視的最佳分組方案和路線。將每個(gè)鄉(xiāng)（鎮(zhèn)）或村看作一個(gè)圖的頂點(diǎn)，各鄉(xiāng)鎮(zhèn)、村之間的公路看作此圖對(duì)應(yīng)頂點(diǎn)間的邊，各條公路的長(zhǎng)度（或行駛時(shí)間）看作對(duì)應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問(wèn)題就轉(zhuǎn)化圖論中一類稱之為旅行售貨員問(wèn)題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)O出發(fā)，行遍所有頂點(diǎn)至少一次再回到點(diǎn)O，使得總權(quán)（路程或時(shí)間）最小。本題是旅行售貨員問(wèn)題的延伸多旅行售貨員問(wèn)題。本題所求的分組巡視的最佳路線，也就是m條經(jīng)過(guò)同一點(diǎn)并覆蓋所有其他頂點(diǎn)又使邊權(quán)之和達(dá)到最小的回路。如第一問(wèn)是三個(gè)旅行售貨員問(wèn)題

28、，第二問(wèn)是四個(gè)旅行售貨員問(wèn)題。(二)中國(guó)郵遞員問(wèn)題（Chinese Postman Problem）中國(guó)郵遞員問(wèn)題(CPP)是由中國(guó)著名運(yùn)籌學(xué)家管梅谷教授于1962年首先提出并作了深入研究，其成果得到國(guó)際、國(guó)內(nèi)運(yùn)籌學(xué)界極高的贊譽(yù)，所以被稱為“中國(guó)郵遞員問(wèn)題”或“中國(guó)郵路問(wèn)題”。1. 問(wèn)題描述CPP可以這樣敘述：一名郵遞員負(fù)責(zé)投遞某個(gè)轄區(qū)的郵件。他從郵局出發(fā)，經(jīng)過(guò)投遞轄區(qū)內(nèi)每條街道至少一次，最后返回郵局，問(wèn)：如何安排一條最短的投遞路線？用圖論的語(yǔ)言可描述為：給定一個(gè)連通圖G，每條邊都有一個(gè)非負(fù)權(quán)數(shù)?，F(xiàn)要求一個(gè)圈C 經(jīng)G 的每邊至少一次，且使C 的權(quán)和最小。2. CPP求解的基本思路為了理解CPP

29、求解方法的思路，需要回顧一下歐拉（Euler）解決“哥尼斯堡七橋”問(wèn)題的方法：一筆畫問(wèn)題。該問(wèn)題涉及到一些圖論的基本概念：頂點(diǎn)的度（次）、奇點(diǎn)、偶點(diǎn)、鏈、圈、歐拉圈、歐拉圖等CPP求解基本思路： 如果在郵遞員負(fù)責(zé)的轄區(qū)里，街道圖中沒(méi)有奇頂點(diǎn)，則存在歐拉圈。郵遞員從郵局出發(fā)，經(jīng)過(guò)每條街道一次，且僅一次，最后回到郵局。此時(shí)的投遞路線最短，即最佳投遞路線。如果街道圖中有奇頂點(diǎn)，就必須在某些街道上重復(fù)走一次或多次。重復(fù)的街道必與奇頂點(diǎn)相連。3. 求解方法奇偶點(diǎn)圖上作業(yè)法我們將郵遞員管轄的街道圖視為無(wú)向圖G =（V，E），若G沒(méi)有奇頂點(diǎn)，則G 是一個(gè)歐拉圖，G含的歐拉圈即為所求。若圖中有奇點(diǎn)，則按下述步

30、驟求解：第一步：把圖G 的奇頂點(diǎn)兩兩配對(duì)，并將每對(duì)奇頂點(diǎn)間的通路上的各邊作為重復(fù)邊添加到圖G 上，得到的新圖全部頂點(diǎn)都是偶頂點(diǎn)。 第二步：如果某邊上的重復(fù)邊多于一條，則可從中刪去偶數(shù)條，使每邊的重復(fù)邊最多只有一條。第三步：檢查圖G 中的每個(gè)圈：若所有圈的重復(fù)邊的總長(zhǎng)度都不大于該圈長(zhǎng)度的一半時(shí)，則得到最優(yōu)方案。否則，若有一個(gè)圈，該圈的重復(fù)邊的總長(zhǎng)度大于該圈長(zhǎng)度的一半，就將該圈的原有重復(fù)邊刪去，給該圈原來(lái)沒(méi)有重復(fù)邊的各邊都加上一條重復(fù)邊。重復(fù)這個(gè)過(guò)程，直到?jīng)]有這種圈為止。求解下圖所示網(wǎng)絡(luò)的中國(guó)郵路問(wèn)題（1）確定初始方案（2）判斷方案的最優(yōu)性（3）調(diào)整可行方案（4）繼續(xù)調(diào)整方案o 奇偶點(diǎn)圖上作業(yè)法在

31、實(shí)際運(yùn)用中已作出許多貢獻(xiàn)。它不僅可以提高郵遞員的工作效率，而且對(duì)于街道清掃路線、紡織工看車路線、倉(cāng)庫(kù)員巡視貨物路線等類似問(wèn)題的研究，都有實(shí)際意義。第四節(jié) 多車輛配送路線的優(yōu)化o 多車輛路徑問(wèn)題（Vehicle Routing Problem）VRP最早是由Dantzig和Ramser于1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個(gè)車隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的。由此定義不難看出，旅行商問(wèn)題（TSP）是VRP的特例。VRP的特點(diǎn)：o 屬于節(jié)點(diǎn)

32、服務(wù)的網(wǎng)絡(luò)組合最優(yōu)化問(wèn)題o 除了場(chǎng)站（物流中心）節(jié)點(diǎn)外，其余節(jié)點(diǎn)恰由一輛車服務(wù)一次o 多車輛路線，且車輛具有容量限制o 各車輛路線所服務(wù)的顧客需求總和不得超過(guò)車輛容量o 求解復(fù)雜度屬于NP-hard，大規(guī)模問(wèn)題難以求得最優(yōu)解，實(shí)踐中多采取“啟發(fā)式方法(Heuristics)”求解VRP的求解方法VRP是組合優(yōu)化領(lǐng)域著名的NP難題之一，求解方法一般相當(dāng)復(fù)雜，通常的做法是應(yīng)用相關(guān)技術(shù)問(wèn)題分解或者轉(zhuǎn)化為一個(gè)或多個(gè)已經(jīng)研究過(guò)的基本問(wèn)題（如旅行商問(wèn)題、指派問(wèn)題、最短路問(wèn)題等），再使用相對(duì)比較成熟的基本理論和方法進(jìn)行求解。o 啟發(fā)式方法 它是指通過(guò)經(jīng)驗(yàn)法則來(lái)求運(yùn)輸過(guò)程滿意解的方法。最具代表性的是：掃描法和節(jié)約法。1.掃描法掃描法是一種先分群在尋找最佳路線的算法。其求解過(guò)程分為兩步：第一步是分派車輛服務(wù)的站點(diǎn)和客戶點(diǎn)；第二步是決定每輛車的行車路線。246571380掃描法過(guò)程可闡述如下：（1）在地圖或方格圖中確定所有站點(diǎn)的位置。（2）自物流中心開始沿任一方向向外劃一條直線。沿順時(shí)針或逆時(shí)針?lè)较蛐D(zhuǎn)該直線直到與某站點(diǎn)相交?？紤]：如果在某線路上增加該站點(diǎn)，是否會(huì)超過(guò)車輛的載貨能力？如果沒(méi)有，繼續(xù)旋轉(zhuǎn)