5.3物資調(diào)度與行駛線路優(yōu)化

1、第五章第五章 貨運(yùn)組織優(yōu)化技術(shù)貨運(yùn)組織優(yōu)化技術(shù)5.3 5.3 運(yùn)行調(diào)度與線路優(yōu)化方法運(yùn)行調(diào)度與線路優(yōu)化方法5.3.1 行駛線路種類行駛線路種類車輛行駛路線的種類車輛行駛路線的種類三種：往復(fù)式，環(huán)形式（對(duì)大宗貨物）， 匯集式（對(duì)零擔(dān)運(yùn)輸）5.3.1 行駛線路種類行駛線路種類車輛行駛路線的種類車輛行駛路線的種類-往復(fù)式往復(fù)式包括：?jiǎn)纬逃休d，回程部分有載，雙程有載包括：?jiǎn)纬逃休d，回程部分有載，雙程有載5.3.1 行駛線路種類行駛線路種類車輛行駛路線的種類車輛行駛路線的種類-往復(fù)式往復(fù)式5.3.1 行駛線路種類行駛線路種類 車輛行駛路線的種類車輛行駛路線的種類-往復(fù)式往復(fù)式5.3.1 行駛線路種類行駛

2、線路種類車輛行駛路線的種類車輛行駛路線的種類-環(huán)形行駛線路環(huán)形行駛線路環(huán)形行駛線路：是指車輛在由若干個(gè)裝卸作業(yè)點(diǎn)組成的一條封閉回路上，作連續(xù)單向運(yùn)行的行駛線路。分為：簡(jiǎn)單式；交叉式（三角式）；復(fù)合環(huán)式；5.3.1 行駛線路種類行駛線路種類車輛行駛路線的種類車輛行駛路線的種類-環(huán)形行駛線路環(huán)形行駛線路當(dāng)無(wú)法組織雙程有在往當(dāng)無(wú)法組織雙程有在往復(fù)式行駛路線時(shí)，為提復(fù)式行駛路線時(shí)，為提高里程利用率和經(jīng)濟(jì)效高里程利用率和經(jīng)濟(jì)效果，可組織環(huán)形行駛路果，可組織環(huán)形行駛路線，但要注意，應(yīng)使空線，但要注意，應(yīng)使空車行程之和不大于重車車行程之和不大于重車行程之和，即里程利用行程之和，即里程利用率率0.5，否則，環(huán)

3、形行，否則，環(huán)形行駛線路經(jīng)濟(jì)效果還不如駛線路經(jīng)濟(jì)效果還不如單程有載往復(fù)式行駛路單程有載往復(fù)式行駛路線。線。 當(dāng)無(wú)法組織雙程有在往復(fù)式行駛路線時(shí)，為提高里程利用當(dāng)無(wú)法組織雙程有在往復(fù)式行駛路線時(shí)，為提高里程利用率和經(jīng)濟(jì)效果，可組織環(huán)形行駛路線，但要注意，應(yīng)使空車率和經(jīng)濟(jì)效果，可組織環(huán)形行駛路線，但要注意，應(yīng)使空車行程之和不大于重車行程之和，即里程利用率行程之和不大于重車行程之和，即里程利用率0.5，否則，否則，環(huán)形行駛線路經(jīng)濟(jì)效果還不如單程有載往復(fù)式行駛路線。環(huán)形行駛線路經(jīng)濟(jì)效果還不如單程有載往復(fù)式行駛路線。5.3.1 行駛線路種類行駛線路種類車輛行駛路線的種類車輛行駛路線的種類-匯集式行駛線路

4、匯集式行駛線路是指車輛沿著分布于運(yùn)行路線上各裝卸作業(yè)點(diǎn)，依次完成相應(yīng)的裝卸作業(yè)，且每運(yùn)次的貨物裝卸量均小于該車的額定載質(zhì)量，知道整個(gè)車輛裝滿后返回出發(fā)點(diǎn)的行駛路線。三種形式：分送式：收集式：分送收集式：量；次周轉(zhuǎn)車輛完成的貨運(yùn)為第，式中，貨運(yùn)量：iQQQiZii015.3.1 行駛線路種類行駛線路種類車輛行駛路線的種類車輛行駛路線的種類-匯集式行駛線路匯集式行駛線路某倉(cāng)庫(kù)A有5t貨物，利用5t位的汽車運(yùn)出，分送1，2，3個(gè)點(diǎn)，六個(gè)方案的效果比較。5.3.2 貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策圖上作業(yè)法圖上作業(yè)法基本概念 圖上作業(yè)法是使用圖解的形式進(jìn)行車輛調(diào)度或貨源分配，特點(diǎn)是直觀易懂、計(jì)算簡(jiǎn)單。

5、步驟如下：a.列出貨物運(yùn)輸計(jì)劃平衡表或各點(diǎn)發(fā)到空車差額表；b.繪制運(yùn)輸路線圖；c.作流向圖；d.檢查是否為最優(yōu)方案（最優(yōu)流向圖應(yīng)該既沒(méi)有對(duì)流，也沒(méi)有迂回）；e.調(diào)整到最優(yōu)流向圖后，根據(jù)最優(yōu)流向圖將最優(yōu)方案填入貨運(yùn)計(jì)劃平衡表或空車調(diào)度表。5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策圖上作業(yè)法圖上作業(yè)法當(dāng)運(yùn)輸線路為直線式時(shí)的圖上作業(yè)法：當(dāng)運(yùn)輸線路為直線式時(shí)的圖上作業(yè)法： “ “直線取一端，供需歸零點(diǎn)直線取一端，供需歸零點(diǎn)” 例9.5 某貨運(yùn)公司承接一貨運(yùn)任務(wù)：由B、E 2個(gè)裝貨點(diǎn)（圖9.25），分別有貨物50t、10t，有A、C、D 3個(gè)收貨點(diǎn)，各需物資30t、10t、20t，運(yùn)輸線路如圖9.26所

6、示。根據(jù)上述貨運(yùn)任務(wù)，空車應(yīng)如何調(diào)度才能使運(yùn)輸合理？5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策圖上作業(yè)法圖上作業(yè)法當(dāng)運(yùn)輸線路為直線式時(shí)的圖上作業(yè)法：當(dāng)運(yùn)輸線路為直線式時(shí)的圖上作業(yè)法： “ “直線取一端，供需歸零點(diǎn)直線取一端，供需歸零點(diǎn)”解：列出各收發(fā)點(diǎn)的空車差額表，如表9.11所示收發(fā)點(diǎn) 數(shù)量（t） 項(xiàng)目 A B C D E 合計(jì) 發(fā)量 50 10 60 貨物 收量 30 10 20 60 需要調(diào)進(jìn)（） 50 10 60 空車噸位差額 需要調(diào)出（+） 30 10 20 60 繪制空車流向圖，如圖9.26所示；先取左端點(diǎn)A點(diǎn)，將A點(diǎn)的30t供給B點(diǎn)；再取右端點(diǎn)E,將D點(diǎn)的20t中的10t供給E點(diǎn)

7、，剩下的10t和C點(diǎn)的10t都供給B點(diǎn)，全線安排完畢，各點(diǎn)供需已經(jīng)平衡。檢查方案，經(jīng)檢驗(yàn)沒(méi)有對(duì)流，是最優(yōu)方案。 表9.11 各點(diǎn)收發(fā)空車差額表5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策圖上作業(yè)法圖上作業(yè)法當(dāng)運(yùn)輸線路為直線式時(shí)的圖上作業(yè)法：當(dāng)運(yùn)輸線路為直線式時(shí)的圖上作業(yè)法： “ “直線取一端，供需歸零點(diǎn)直線取一端，供需歸零點(diǎn)”空駛線路空駛線路空車噸位空車噸位（t t）空車記錄空車記錄合計(jì)空駛噸位合計(jì)空駛噸位公里（公里（tkmtkm）起點(diǎn)起點(diǎn)終點(diǎn)終點(diǎn)里程（里程（kmkm）A AB B6060303018001800C CB B30301010300300D DB B70701010700700D

8、DE E25251010250250 表9.12 空車調(diào)度表 填表時(shí)應(yīng)注意：D-C、C-B是連續(xù)流向線，應(yīng)按D-B直達(dá)流量10t和C-B10t填表，不能按圖示的D-C 10t和C-B 20t分段流量填表。5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策圖上作業(yè)法圖上作業(yè)法當(dāng)運(yùn)輸線路為樹(shù)形時(shí)的圖上作業(yè)法：當(dāng)運(yùn)輸線路為樹(shù)形時(shí)的圖上作業(yè)法： “ “先定一干線，分支作流向，余缺歸交點(diǎn)，化成一條線先定一干線，分支作流向，余缺歸交點(diǎn)，化成一條線” 例9.6 如圖9.27所示運(yùn)輸線路圖，有F、G、B、D4個(gè)發(fā)點(diǎn)，各有待運(yùn)貨物50t、20t、80t、50t，E點(diǎn)、A點(diǎn)、C點(diǎn)3個(gè)接貨點(diǎn)，各需運(yùn)輸60t、70t、70t

9、，求空車調(diào)度的最優(yōu)方案。5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策圖上作業(yè)法圖上作業(yè)法當(dāng)運(yùn)輸線路為閉合環(huán)路時(shí)的圖上作業(yè)法：當(dāng)運(yùn)輸線路為閉合環(huán)路時(shí)的圖上作業(yè)法： “ “破圈成線破圈成線”一般甩開(kāi)一段，為圈中較長(zhǎng)段或同時(shí)收及一般甩開(kāi)一段，為圈中較長(zhǎng)段或同時(shí)收及同時(shí)發(fā)點(diǎn)之間的段。同時(shí)發(fā)點(diǎn)之間的段。5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策產(chǎn)銷平衡的運(yùn)輸問(wèn)題產(chǎn)銷平衡的運(yùn)輸問(wèn)題-表上作業(yè)法表上作業(yè)法1、環(huán)形式行駛線路優(yōu)化選擇標(biāo)準(zhǔn) 當(dāng)完成同樣貨運(yùn)任務(wù)時(shí)，里程利用率最高位最佳。以運(yùn)次為基本運(yùn)輸過(guò)程進(jìn)行組織，一個(gè)環(huán)形路線上包含多個(gè)運(yùn)次，多項(xiàng)貨運(yùn)任務(wù)。每個(gè)運(yùn)次的重車路線由貨運(yùn)任務(wù)決定，故重車方向是一定的，無(wú)從選

10、擇。只有合理組織環(huán)形路線上各運(yùn)次的銜接順序，使總空車行程最短，才能里程利用率最高。2、數(shù)學(xué)模型 0min111111ijminjjimijijijnjiijminjijijvQqQQLQQQLQL約束條件：產(chǎn)銷平衡的運(yùn)輸問(wèn)題產(chǎn)銷平衡的運(yùn)輸問(wèn)題表上作業(yè)法u表上作業(yè)法的計(jì)算步驟：分析實(shí)際問(wèn)題列出產(chǎn)銷平分析實(shí)際問(wèn)題列出產(chǎn)銷平衡表及單位運(yùn)價(jià)表衡表及單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案（最小確定初始調(diào)運(yùn)方案（最小元素法或元素法或Vogel弗戈法）弗戈法）求檢驗(yàn)數(shù)（位勢(shì)法）求檢驗(yàn)數(shù)（位勢(shì)法）所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)0找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)，用閉合找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)，用閉合回路調(diào)整，得到新的調(diào)運(yùn)方案回路調(diào)整，得到

11、新的調(diào)運(yùn)方案得到最優(yōu)方案，得到最優(yōu)方案，算出總運(yùn)價(jià)算出總運(yùn)價(jià)表上作業(yè)法u表上作業(yè)法是一種求解運(yùn)輸問(wèn)題的特殊方法，其實(shí)質(zhì)是單純形法。步驟描述方法第一步求初始基行可行解（初始調(diào)運(yùn)方案）最小元素法、元素差額法、第二步求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的檢驗(yàn)數(shù)ij全都非負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù)ij 0，說(shuō)明還沒(méi)有達(dá)到最優(yōu)，轉(zhuǎn)第三步。閉回路法和位勢(shì)法第三步調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對(duì)原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步表上作業(yè)法例例 某運(yùn)輸資料如下表所示：某運(yùn)輸資料如下表所示：?jiǎn)挝?銷地 運(yùn)價(jià) 產(chǎn)地產(chǎn)量311310719284741059銷量36564321 BBBB321AAA問(wèn)

12、：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？表上作業(yè)法u解：第1步 求初始方案方法方法1：最小元素法：最小元素法 基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開(kāi)始供應(yīng)（調(diào)運(yùn)），然后次小，直基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開(kāi)始供應(yīng)（調(diào)運(yùn)），然后次小，直到最后供完為止。到最后供完為止。B1B2B3B4產(chǎn)量A17A2 4A39銷量3656311310192741058341633表上作業(yè)法總的運(yùn)輸費(fèi)總的運(yùn)輸費(fèi)(31)+(64) +(43) +(12)+(310)+(35)=86元元元素差額法對(duì)最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷地的最小運(yùn)價(jià)和次小元素差額法對(duì)最小元素法進(jìn)行了改進(jìn)

13、，考慮到產(chǎn)地到銷地的最小運(yùn)價(jià)和次小運(yùn)價(jià)之間的差額，如果差額很大，就選最小運(yùn)價(jià)先調(diào)運(yùn)，否則會(huì)增加總運(yùn)費(fèi)。例運(yùn)價(jià)之間的差額，如果差額很大，就選最小運(yùn)價(jià)先調(diào)運(yùn)，否則會(huì)增加總運(yùn)費(fèi)。例如下面兩種運(yùn)輸方案。如下面兩種運(yùn)輸方案。85102120151515510總運(yùn)費(fèi)是總運(yùn)費(fèi)是z=108+52+151=105最小元素法：最小元素法：表上作業(yè)法85102120151551510總運(yùn)費(fèi)總運(yùn)費(fèi)z=105+152+51=85后一種方案考慮到后一種方案考慮到C11與與C21之間之間的差額是的差額是82=6，如果不先調(diào)運(yùn)，如果不先調(diào)運(yùn)x21，到后來(lái)就有可能，到后來(lái)就有可能x110，這，這樣會(huì)使總運(yùn)費(fèi)增加較大，從而先樣會(huì)

14、使總運(yùn)費(fèi)增加較大，從而先調(diào)運(yùn)調(diào)運(yùn)x21，再是，再是x22，其次是，其次是x12用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。案。表上作業(yè)法方法方法2：Vogel法法1）從運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該）從運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。表的最右列和最下行。B1B2B3B4產(chǎn)量A17A2 4A39銷量3656311310192741058表上作業(yè)法2）再?gòu)牟钪底畲蟮男谢蛄兄姓页鲎钚∵\(yùn)價(jià)確定供需關(guān)系和供需數(shù)量。當(dāng)產(chǎn)地或）再?gòu)牟钪底畲蟮男?/p>

15、或列中找出最小運(yùn)價(jià)確定供需關(guān)系和供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列。銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列。重復(fù)重復(fù)1)和和2)，直到找出初始解為至。，直到找出初始解為至。B1B2B3B4產(chǎn)量A17A2 4A3 9銷量3656311310192741058表上作業(yè)法單位 銷地 運(yùn)價(jià) 產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額4321 BBBB321AAA71135215表上作業(yè)法單位 銷地 運(yùn)價(jià) 產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額4321 BBBB321AAA713

16、52753表上作業(yè)法單位 銷地 運(yùn)價(jià) 產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額4321 BBBB321AAA11351536312該方案的總運(yùn)費(fèi)該方案的總運(yùn)費(fèi):(13)(46)(35)(210)(18)(35)85元元表上作業(yè)法求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗(yàn)數(shù)來(lái)判斷，記求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗(yàn)數(shù)來(lái)判斷，記xij的檢驗(yàn)數(shù)為的檢驗(yàn)數(shù)為ij，求最小值的運(yùn)輸問(wèn)題的最優(yōu)判別準(zhǔn)則是：，求最小值的運(yùn)輸問(wèn)題的最優(yōu)判別準(zhǔn)則是：所有非基變量的檢驗(yàn)數(shù)都非負(fù)，則運(yùn)輸方案最優(yōu)所有非基變量的檢驗(yàn)數(shù)都非負(fù)，則運(yùn)輸方案最優(yōu)求檢驗(yàn)數(shù)的方法有兩種：求檢驗(yàn)數(shù)

17、的方法有兩種： 閉回路法閉回路法 位勢(shì)法（位勢(shì)法（）表上作業(yè)法用位勢(shì)法對(duì)初始方案進(jìn)行最優(yōu)性檢驗(yàn)：用位勢(shì)法對(duì)初始方案進(jìn)行最優(yōu)性檢驗(yàn)：1）由）由 ij=Cij-（Ui+Vj）計(jì)算位勢(shì)）計(jì)算位勢(shì)Ui ， Vj ，因?qū)兞慷杂?，因?qū)兞慷杂?ij=0，即，即Cij-（Ui+Vj） = 0，令，令U1=02）再由）再由 ij=Cij-（Ui+Vj）計(jì)算非基變量的檢驗(yàn)數(shù)）計(jì)算非基變量的檢驗(yàn)數(shù) ijB1B2B3B4UiA1A2A3Vj311310192741058436313當(dāng)存在非基當(dāng)存在非基變量的檢驗(yàn)變量的檢驗(yàn)數(shù)數(shù) kl 0，說(shuō)明現(xiàn)行方說(shuō)明現(xiàn)行方案為最優(yōu)方案為最優(yōu)方案，否則目案，否則目標(biāo)成本還可

18、標(biāo)成本還可以進(jìn)一步減以進(jìn)一步減小。小。表上作業(yè)法u當(dāng)存在非基變量的檢驗(yàn)數(shù)kl 0 且kl =minij時(shí)，令Xkl 進(jìn)基。從表中知可選X24進(jìn)基。第第3步步 確定換入基的變量確定換入基的變量第第4步步 確定換出基的變量確定換出基的變量以進(jìn)基變量以進(jìn)基變量xik為起點(diǎn)的閉回路中，標(biāo)有負(fù)號(hào)的最小運(yùn)量作為調(diào)整量為起點(diǎn)的閉回路中，標(biāo)有負(fù)號(hào)的最小運(yùn)量作為調(diào)整量，對(duì)應(yīng)的對(duì)應(yīng)的基變量為出基變量，并打上基變量為出基變量，并打上“”以示換出作為非基變量。以示換出作為非基變量。表上作業(yè)法B1B2B3B4UiA1A2A3Vj311197436 13 , 1minmin14,23 xx調(diào)整步驟為：調(diào)整步驟為：在進(jìn)基變

19、量的閉回路中標(biāo)有正號(hào)的變量加上調(diào)整量在進(jìn)基變量的閉回路中標(biāo)有正號(hào)的變量加上調(diào)整量，標(biāo)有負(fù)號(hào)的變量減去調(diào)整量，標(biāo)有負(fù)號(hào)的變量減去調(diào)整量，其余變量不變，得到一組新的，其余變量不變，得到一組新的基可行解。然后求所有非基變量的檢驗(yàn)數(shù)重新檢驗(yàn)?；尚薪狻Ｈ缓笄笏蟹腔兞康臋z驗(yàn)數(shù)重新檢驗(yàn)。表上作業(yè)法當(dāng)所有非基變量的檢驗(yàn)數(shù)均非負(fù)時(shí)，則當(dāng)前調(diào)運(yùn)方案即為最優(yōu)方案，如表此時(shí)當(dāng)所有非基變量的檢驗(yàn)數(shù)均非負(fù)時(shí)，則當(dāng)前調(diào)運(yùn)方案即為最優(yōu)方案，如表此時(shí)最小總運(yùn)費(fèi)：最小總運(yùn)費(fèi)：Z =(13)(46)(35)(210)(18)(35)85元元B1B2B3B4UiA1A2A3Vj311310192741058536312產(chǎn)銷不平

20、衡的運(yùn)輸問(wèn)題產(chǎn)銷不平衡的運(yùn)輸問(wèn)題5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策產(chǎn)銷不平衡的運(yùn)輸問(wèn)題產(chǎn)銷不平衡的運(yùn)輸問(wèn)題（1）若總產(chǎn)量大于總銷量，即）若總產(chǎn)量大于總銷量，即minjjiba11njjmiiba11增加一個(gè)假想的銷地增加一個(gè)假想的銷地j=n+1(j=n+1(實(shí)際上是儲(chǔ)存實(shí)際上是儲(chǔ)存) )，該銷地總需要量為，該銷地總需要量為而在單位運(yùn)價(jià)表中從各產(chǎn)地到假想銷地的單位運(yùn)為而在單位運(yùn)價(jià)表中從各產(chǎn)地到假想銷地的單位運(yùn)為 ，就，就轉(zhuǎn)化成一個(gè)產(chǎn)銷平衡的運(yùn)輸問(wèn)題。轉(zhuǎn)化成一個(gè)產(chǎn)銷平衡的運(yùn)輸問(wèn)題。 , 10inc5.3.2 貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策11( 4)minmnijijijPzc x11,

21、(1, 2,),(1, 2,). .0nijijmijjiijxaimxbjns tx運(yùn)輸問(wèn)題的原模型可寫成（運(yùn)輸問(wèn)題的原模型可寫成（P4P4）產(chǎn)銷不平衡的運(yùn)輸問(wèn)題產(chǎn)銷不平衡的運(yùn)輸問(wèn)題5.3.2 貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策轉(zhuǎn)化成產(chǎn)銷平衡后的運(yùn)輸問(wèn)題的模型可寫成其中產(chǎn)銷不平衡的運(yùn)輸問(wèn)題產(chǎn)銷不平衡的運(yùn)輸問(wèn)題產(chǎn)銷不平衡的運(yùn)輸問(wèn)題產(chǎn)銷不平衡的運(yùn)輸問(wèn)題5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策（2）若總銷量大于總產(chǎn)量，）若總銷量大于總產(chǎn)量，可以在產(chǎn)銷平衡表中增加一個(gè)假想可以在產(chǎn)銷平衡表中增加一個(gè)假想的產(chǎn)地的產(chǎn)地i=m+1，該地產(chǎn)量為，該地產(chǎn)量為njmijjab11在單位運(yùn)價(jià)表上令從該假想產(chǎn)地到各銷

22、地的運(yùn)價(jià)同樣可以轉(zhuǎn)化為一個(gè)產(chǎn)銷平衡的運(yùn)輸問(wèn)題.1,0mjc產(chǎn)銷不平衡的運(yùn)輸問(wèn)題產(chǎn)銷不平衡的運(yùn)輸問(wèn)題存在中間轉(zhuǎn)運(yùn)的物資調(diào)配存在中間轉(zhuǎn)運(yùn)的物資調(diào)配5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題一、問(wèn)題的提出一、問(wèn)題的提出 （1）產(chǎn)地與銷地之間沒(méi)有直達(dá)路線，貨物有產(chǎn)地到銷地必須通過(guò)某中間站轉(zhuǎn)運(yùn)； （2）某些產(chǎn)地既輸出貨物，也吸收一部分貨物；某銷地既吸收貨物，又輸出部分貨物，即產(chǎn)地或銷地也可以起到中轉(zhuǎn)站的作用，或者即是產(chǎn)地也是銷地； （3）產(chǎn)地與銷地之間雖然有直達(dá)路線，但直達(dá)運(yùn)輸?shù)馁M(fèi)用或運(yùn)輸距離分別比經(jīng)過(guò)某些中轉(zhuǎn)站還要高或遠(yuǎn)。 存在以上情況的運(yùn)輸問(wèn)題，統(tǒng)

23、稱為轉(zhuǎn)運(yùn)問(wèn)題。存在中間轉(zhuǎn)運(yùn)的物資調(diào)配存在中間轉(zhuǎn)運(yùn)的物資調(diào)配5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策二、問(wèn)題的描述二、問(wèn)題的描述 某物流系統(tǒng)中有f個(gè)供應(yīng)地，m個(gè)流通中心，n個(gè)需求地，已知工廠AK的生產(chǎn)能力為ak(k=1,2,f),流通中心Ti的配送能力為ti(i=1,2,m)，需求地Bj的需求量bj(j=1,2,n)。由AK經(jīng)Ti運(yùn)到Bj的單位運(yùn)價(jià)為Ckij。求在工廠生產(chǎn)能力一定，流通中心配送能力有限的條件下，滿足需求地需求量的最優(yōu)運(yùn)輸方案。存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題存在中間轉(zhuǎn)運(yùn)的物資調(diào)配存在中間轉(zhuǎn)運(yùn)的物資調(diào)配5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策三、數(shù)學(xué)模型三、

24、數(shù)學(xué)模型 存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題存在中間轉(zhuǎn)運(yùn)的物資調(diào)配存在中間轉(zhuǎn)運(yùn)的物資調(diào)配5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策四、求解方法四、求解方法 一種方法是運(yùn)用一般的線性規(guī)劃方法求解，但是問(wèn)題變量越多，約束條件越多，求解過(guò)程復(fù)雜。 另一種方法是運(yùn)用運(yùn)輸問(wèn)題表上作業(yè)法。補(bǔ)充一些虛擬的產(chǎn)地或銷地，將有中轉(zhuǎn)的運(yùn)輸問(wèn)題轉(zhuǎn)化為無(wú)中轉(zhuǎn)的直達(dá)運(yùn)輸問(wèn)題；再進(jìn)一步轉(zhuǎn)化為供需平衡的運(yùn)輸問(wèn)題；然后再運(yùn)用表上作業(yè)法求解。存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題存在中間轉(zhuǎn)運(yùn)的物資調(diào)配存在中間轉(zhuǎn)運(yùn)的物資調(diào)配-例子例子5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)

25、題存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題 某公司有兩個(gè)工廠生產(chǎn)變壓器，一個(gè)工廠在A市，另一個(gè)在B市，A、B每天生產(chǎn)能力150、200，需求點(diǎn)為C、D，需求量均為130，中間兩個(gè)轉(zhuǎn)運(yùn)站E、F進(jìn)行整合，運(yùn)費(fèi)表如下。求工廠到需求點(diǎn)的最優(yōu)線路。ABEFCDA013461214B130761312E470388F663078C121387017D141288170存在中間轉(zhuǎn)運(yùn)的物資調(diào)配存在中間轉(zhuǎn)運(yùn)的物資調(diào)配-例子例子5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題第一階段將運(yùn)輸模型轉(zhuǎn)換為簡(jiǎn)單的運(yùn)輸問(wèn)題：（1）增加一虛擬行或列來(lái)平衡需求。本例中增加虛擬列，需求量為）增加一

26、虛擬行或列來(lái)平衡需求。本例中增加虛擬列，需求量為350-260=90；（2）構(gòu)造一個(gè)包括所有城市（）構(gòu)造一個(gè)包括所有城市（A-F）作為供需點(diǎn)運(yùn)輸表，形成）作為供需點(diǎn)運(yùn)輸表，形成6*7矩陣。矩陣。（3）確定供需量。方法如下。）確定供需量。方法如下。點(diǎn)的性質(zhì)在運(yùn)輸表中的供應(yīng)值在運(yùn)輸表中的需求值供應(yīng)點(diǎn)（A.B）起始供應(yīng)+總供應(yīng)總供應(yīng)轉(zhuǎn)運(yùn)點(diǎn)（E.F）總供應(yīng)總供應(yīng)需求點(diǎn)（C.D）總供應(yīng)起始供應(yīng)+總供應(yīng)空點(diǎn)0起始供應(yīng)+總供應(yīng)存在中間轉(zhuǎn)運(yùn)的物資調(diào)配存在中間轉(zhuǎn)運(yùn)的物資調(diào)配-例子例子5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題存在中間轉(zhuǎn)運(yùn)的物資調(diào)度問(wèn)題最終運(yùn)輸表最終運(yùn)輸表ABEFCD空列

27、供應(yīng)A0134612140500B1307613120550E4703880350F6630780350C1213870170350D1412881700350需求350350350350480480905.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策環(huán)形行駛路線優(yōu)化環(huán)形行駛路線優(yōu)化-收發(fā)車原則收發(fā)車原則（1）“兩點(diǎn)”循環(huán)路線的發(fā)車原則為：若兩點(diǎn)貨物量相等，則就近發(fā)車，若兩點(diǎn)貨物量不等，則向貨物量多的點(diǎn)發(fā)車。（2）“多點(diǎn)”循環(huán)路線的發(fā)車原則 裝卸貨點(diǎn)都至少有兩個(gè)，且在一條循環(huán)線路上，即為，多點(diǎn)循環(huán)路線。原則：“調(diào)車?yán)锍獭白钚〉难b貨點(diǎn)發(fā)車。調(diào)車?yán)锍逃?jì)算公式： 出車空駛里程+回車空駛里程-第一個(gè)裝點(diǎn)到最

28、后一個(gè)卸點(diǎn)的距離。552585AB5102585AB5.3.2貨物運(yùn)輸調(diào)配決策貨物運(yùn)輸調(diào)配決策環(huán)形行駛路線優(yōu)化環(huán)形行駛路線優(yōu)化-收發(fā)車原則收發(fā)車原則（3）多點(diǎn)裝一點(diǎn)卸的發(fā)車原則 哪個(gè)裝車點(diǎn)到車場(chǎng)的距離減去該點(diǎn)到卸車場(chǎng)的距離最小，哪個(gè)點(diǎn)即為第一個(gè)裝車點(diǎn)。（4）一點(diǎn)裝多點(diǎn)卸的發(fā)車原則 哪個(gè)卸車點(diǎn)到車場(chǎng)的距離減去該點(diǎn)到裝車場(chǎng)的距離最小，哪個(gè)點(diǎn)即為最后一個(gè)回場(chǎng)的收車點(diǎn)。1113CDBA201555.3.3 車輛線路優(yōu)化方法車輛線路優(yōu)化方法車輛調(diào)度問(wèn)題綜述 貨郎擔(dān)問(wèn)題貨郎擔(dān)問(wèn)題也叫旅行商問(wèn)題旅行商問(wèn)題，即TSP問(wèn)題（Traveling Salesman Problem），是數(shù)學(xué)領(lǐng)域中著名問(wèn)題之一。 其一

29、般提法為：有n個(gè)城市，用1，2，n表示，城i,j之間的距離為dij，有一個(gè)貨郎從城1出發(fā)到其他城市一次且僅一次，最后回到城市1，怎樣選擇行走路線使總路程最短？ 旅行商問(wèn)題的提法為：假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。 5.3.3 車輛行駛線路優(yōu)化方法車輛行駛線路優(yōu)化方法匯集式行駛路線優(yōu)化匯集式行駛路線優(yōu)化-車輛調(diào)度問(wèn)題綜述VSP（vehicle schedule planning)：車輛調(diào)度問(wèn)題，分為有時(shí)間窗問(wèn)題、無(wú)時(shí)間窗問(wèn)題。VRP（vehicle r

30、oad planning)：車輛線路安排問(wèn)題，是路線優(yōu)化問(wèn)題。一、問(wèn)題的提出 國(guó)外將物流配送車輛優(yōu)化問(wèn)題歸結(jié)為VSP和VRP。5.3.3 車輛行駛線路優(yōu)化方法車輛行駛線路優(yōu)化方法匯集式行駛路線優(yōu)化匯集式行駛路線優(yōu)化-車輛調(diào)度問(wèn)題綜述二、對(duì)VSP的分類： 可以按任務(wù)特性、任務(wù)性質(zhì)、車輛裝載狀況、車場(chǎng)數(shù)目、車輛類型、車輛對(duì)車場(chǎng)的所屬關(guān)系等進(jìn)行分類，由于分類的不同，車輛調(diào)度問(wèn)題的模型構(gòu)造及算法有很大差異。三、模型以車流為基礎(chǔ)的模型以物流為基礎(chǔ)的模型集覆蓋模型四、基本問(wèn)題與基本方法常用的基本問(wèn)題常用的基本問(wèn)題：旅行商問(wèn)題、分派問(wèn)題、運(yùn)輸問(wèn)題、背包問(wèn)題等。常用的基本理論和方法常用的基本理論和方法：分支定

31、界法、割平面法、線性規(guī)劃法、動(dòng)態(tài)規(guī)劃法、對(duì)偶理論等。5.3.3 車輛行駛線路優(yōu)化方法車輛行駛線路優(yōu)化方法匯集式行駛路線優(yōu)化匯集式行駛路線優(yōu)化-車輛調(diào)度問(wèn)題綜述算法算法一、精確算法分支定界法割平面法網(wǎng)絡(luò)流算法動(dòng)態(tài)規(guī)劃方法二、啟發(fā)式算法構(gòu)造算法兩階段法不完全優(yōu)化算法改進(jìn)算法啟發(fā)式算法：（1）計(jì)算分組數(shù)：（2）選擇每組的配送點(diǎn)：第一點(diǎn)選擇離O（配送中心）最遠(yuǎn)的點(diǎn)Pi，第二點(diǎn)選擇離Pi最近的點(diǎn)，依次選擇，考慮貨運(yùn)量的容量。（3）直到將所有點(diǎn)都納入后，即完成了各組內(nèi)配送點(diǎn)的選擇。（4）完成各組內(nèi)配送點(diǎn)的配送先后順序：采用試算法，通過(guò)編程，將每組內(nèi)各點(diǎn)組合，并算出各組合后的行駛里程，里程最小的即為最優(yōu)方案。5 . 0Hjqqd5.3.3 車輛行駛線路優(yōu)