物流運輸管理

物流運輸管理第一頁，共九十四頁，編輯于2023年，星期三第一節(jié)

物流運輸服務選擇決策一、物流運輸方式選擇的原則二、基于物流總成本比較的運輸方式選擇三、承運人的選擇與評價第二頁，共九十四頁，編輯于2023年，星期三一、物流運輸方式選擇的原則（一）安全性原則（二）及時性原則（三）準確性原則（四）經(jīng)濟性原則第三頁，共九十四頁，編輯于2023年，星期三二、基于物流總成本比較的運輸方式選擇基于運輸成本與庫存成本的總成本分析方法：表7-1各種運輸方式的基本參數(shù)表7-2各種運輸方式成本計算結(jié)果運輸方式費率R(元/件)時間T(天)年運送批次平均存貨量Q/2鐵路0.12110100000馱背0路0.252042000航空1.424020250成本類型計算公式鐵路運輸馱背運輸公路運輸航空運輸運輸成本RD70000105000140000980000在途庫存ICDT/3653624662416448630134521工廠存貨ICQ/2900000418500378000182250倉庫存貨I(C+R)Q/2903000420593380520190755總成本223546611857379848211387526第四頁，共九十四頁，編輯于2023年，星期三三、承運人的選擇與評價（一）影響承運人選擇的主要因素1．運輸成本2．運輸時間和運輸時間的可靠性3．可到達性4．服務能力5．安全性第五頁，共九十四頁，編輯于2023年，星期三（二）承運人的評價方法綜合因素加權(quán)求和法表7-3承運商評估報告示例承運人：_____時期:_____最高分評價標準承運人分數(shù)備注13滿足接貨時間表1313滿足搬運109運輸時間910運輸時間一致性77費率53附加費1高的住宅搬運5運營比率396.5％增長4收益性33索賠頻率33索賠解決310賬單錯誤79跟蹤能力711設(shè)備可用性l無平臺裝貨卡車100總分72第六頁，共九十四頁，編輯于2023年，星期三第二節(jié)貨物運輸調(diào)配決策一、多起迄點間的直達運輸二、存在中間轉(zhuǎn)運的物資調(diào)配第七頁，共九十四頁，編輯于2023年，星期三一、多起迄點間的直達運輸（一）產(chǎn)銷平衡的運輸問題1．產(chǎn)銷平衡運輸問題數(shù)學模型2．求解方法單純形法、表上作業(yè)法圖7-1多點之間的物資運輸調(diào)撥問題示意圖第八頁，共九十四頁，編輯于2023年，星期三（二）產(chǎn)銷不平衡的運輸問題1．總產(chǎn)量大于總銷量：則增加一個假想的銷地Bn+1，其銷量為：2．總銷量大于總產(chǎn)量：則增加一個假想的產(chǎn)地Am+1，其產(chǎn)量為：第九頁，共九十四頁，編輯于2023年，星期三二、存在中間轉(zhuǎn)運的物資調(diào)配（一）問題描述圖7-2有中間轉(zhuǎn)運的物資運輸調(diào)撥問題第十頁，共九十四頁，編輯于2023年，星期三（二）數(shù)學模型目標函數(shù)為：約束條件為：（1）配送量生產(chǎn)能力的限制：k=1，2，…，f；（2）流通中心發(fā)送能力的限制：

i＝1，2，…，m；（3）滿足零售店需求量：

j=1，2，…，n；（4）變量非負：第十一頁，共九十四頁，編輯于2023年，星期三（三）求解方法運輸問題表上作業(yè)法：[例7-2]表7-4各點間運輸單位費用ABEFCDA013461214B130761312E470388F663078C121387017D141288170第十二頁，共九十四頁，編輯于2023年，星期三表7-5需求和供應量確定準則轉(zhuǎn)運問題中點的性質(zhì)在運輸表中的供應值在運輸表中的需求值供應點起始供應+總供應總供應轉(zhuǎn)運點總供應總供應需求點總供應起始需求+總供應空點0起始供應－起始需求表7-6最終運輸表ABEFCD空列供應A0134612140500B1307613120550E4703880350F6630780350C1213870170350D1412881700350需求35035035035048048090第十三頁，共九十四頁，編輯于2023年，星期三第三節(jié)物流運輸線路的優(yōu)化一、起迄點不同的單一路線優(yōu)化二、起迄點重合的單一路線優(yōu)化第十四頁，共九十四頁，編輯于2023年，星期三一、起迄點不同的單一路線優(yōu)化歸結(jié)為運籌學中的最短路徑問題

圖7-3從起點到終點的運輸網(wǎng)絡圖第十五頁，共九十四頁，編輯于2023年，星期三動態(tài)規(guī)劃方法

B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G第一階段第二階段第三階段第四階段第五階段第六階段531368766835342138223335526643437597681310912131618該點到G點的最短距離16第十六頁，共九十四頁，編輯于2023年，星期三（一）動態(tài)規(guī)劃法圖7-4多階段劃分52871220141919第十七頁，共九十四頁，編輯于2023年，星期三（二）Dijkstra方法[例7-3]圖7-5運輸網(wǎng)絡圖第十八頁，共九十四頁，編輯于2023年，星期三E.W.Dijkstra算法（標號算法）算法基本思路分析：（逐步向外搜索）52165828997221210∞∞∞∞∞∞∞∞2527511121210575667991010633xy起點到該點的最短距離起點到該點的最短距離的上界19第十九頁，共九十四頁，編輯于2023年，星期三（二）Dijkstra方法[例7-3]圖7-5運輸網(wǎng)絡圖0∞∞∞∞∞∞02542944487714813第二十頁，共九十四頁，編輯于2023年，星期三表7-8Dijkstra算法步驟表步驟P標號點與P點直接相連的T標號點相應的總距離第n個最近點最小總距離最新連接1OA2A2OA2OACB42+2=4CB44OCAB3ABCDEE2+7=94+3=74+4=8E7BE4ABEDDD2+7=94+4=87+1=8DD88BDED5DETT8+5=137+7=14T13DT第二十一頁，共九十四頁，編輯于2023年，星期三A起點90B13834866C9084E96D1564875F12050132IH48G150126126J終點第二十二頁，共九十四頁，編輯于2023年，星期三

二、物流運輸?shù)膬?yōu)化模型按貨物的自然流向組織貨物合理的物流運輸是市場經(jīng)濟規(guī)律的客觀要求，它直接決定著物流的效率與效果。為了制定在產(chǎn)銷平衡條件下的運量規(guī)劃方案，必須建立數(shù)學模型，運用數(shù)學方法來解決。第二十三頁，共九十四頁，編輯于2023年，星期三三、單純形法

對于運輸問題，一般采用單純形法求解，具體方法和步驟已在前面介紹過，這里不再列述。經(jīng)驗表明，當起運站和目的地都多于5個時，用其它方法求解比較困難或繁瑣，最好用單純形法求解。第二十四頁，共九十四頁，編輯于2023年，星期三四、圖表分析法圖表分析法是在分區(qū)產(chǎn)銷平衡所確定的供銷區(qū)域內(nèi)，按照生產(chǎn)地與消費地的地理分布，根據(jù)有利于生產(chǎn)、有利于市場供給、近產(chǎn)近銷的原則，應用交通路線示意圖和商品產(chǎn)銷平衡表找出產(chǎn)銷之間經(jīng)濟合理的商品運輸路線。第二十五頁，共九十四頁，編輯于2023年，星期三五、圖上作業(yè)法第二十六頁，共九十四頁，編輯于2023年，星期三

1．運輸線路不成圈的圖上作業(yè)法第二十七頁，共九十四頁，編輯于2023年，星期三第二十八頁，共九十四頁，編輯于2023年，星期三第二十九頁，共九十四頁，編輯于2023年，星期三第三十頁，共九十四頁，編輯于2023年，星期三

2．運輸線路成圈的圖上作業(yè)法

運輸線路成圈，就是形成閉合回路的“環(huán)”形路線，包括一個圈（有三角形、四邊形、多邊形）和多個圈。成圈的線路流向圖要同時達到既無對流現(xiàn)象、又無迂回現(xiàn)象的要求才是最優(yōu)流向圖。對于成圈運輸線路的圖上作業(yè)法，可按下述三個步驟尋求最優(yōu)方案，如表9-22所示。第三十一頁，共九十四頁，編輯于2023年，星期三表9-22成圈運輸線路的圖上作業(yè)法的步驟步驟詳述去段破圈確定初始運輸方案就是在成圈的線路中，先假設(shè)某兩點間的線路“不通”，去掉這段線路，把成圈線路轉(zhuǎn)化為不成圈的線路，即破圈；按照運輸線路不成圈的圖上作業(yè)法，即可得到初始運輸方案。檢查有無迂回現(xiàn)象

因為流向箭頭都統(tǒng)一畫在線路右邊，所以圈內(nèi)圈外都畫有一些流向。分別檢查每個小圈，如果圈內(nèi)和圈外流向的總長度都不超過全圈總長度的1/2，那么，全圈就沒有迂回現(xiàn)象了，這個線路流向圖就是最優(yōu)的，對應的就是最優(yōu)運輸方案。否則轉(zhuǎn)向第三步。重新去段破圈，調(diào)整流向

在超過全圈總長1/2的里（外）圈各段流向線上減去最小運量，然后在相反方向的外（里）圈流向線上和原來沒有流向線的各段上，加上減去的最小運量，這樣可以得到一個新的線路流向圖，然后轉(zhuǎn)到第二步檢查有無迂回現(xiàn)象。如此反復，直到得到最優(yōu)線路流向圖為止。如果全圈存在兩個及兩個以上的圈，則需分別對各圈進行是否存在迂回線路的檢查，如果各圈的里、外圈都不超過全圈總線長的1/2，則不存在迂回現(xiàn)象，此方案為最優(yōu)運輸方案。第三十二頁，共九十四頁，編輯于2023年，星期三(13)(18)第三十三頁，共九十四頁，編輯于2023年，星期三第三十四頁，共九十四頁，編輯于2023年，星期三第三十五頁，共九十四頁，編輯于2023年，星期三最小樹問題與網(wǎng)絡設(shè)計樹（Tree）和最小樹樹是圖論中一類重要的圖，實際中很多系統(tǒng)的結(jié)構(gòu)都是樹。樹——連通且不含圈的圖，簡記為T。樹的性質(zhì)：（1）在樹中，任意兩個頂點間必有且僅有一條鏈；（2）在樹中，在不相鄰的頂點中添加一條樹枝，則恰好得到一個圈；（3）在樹中，任意去掉一條樹枝，就變成分離圖；（4）設(shè)T是棵有n個頂點的樹，則T的樹枝數(shù)為n-1；（5）一棵樹至少有兩個懸掛點；（6）樹是連通且邊數(shù)最少的圖。36第三十六頁，共九十四頁，編輯于2023年，星期三最小樹問題樹（Tree）和最小樹樹的權(quán)——

若Tk是加權(quán)圖G的一棵樹，則樹T的全部邊的權(quán)之和稱為樹Tk的權(quán)，記為（Tk

）=（e）；eTk最小樹——

T*是加權(quán)圖G的一棵最小樹，即（T*

）=min{(Tk)}37第三十七頁，共九十四頁，編輯于2023年，星期三最小樹問題樹（Tree）和最小樹破圈法，避圈法求最小支撐樹：圖G1542453134421512最小支撐樹T最小支撐樹T1212112123121123第三十八頁，共九十四頁，編輯于2023年，星期三

案例：幾家石油公司準備聯(lián)合建設(shè)一個輸油管道來連接西南地區(qū)、東南地區(qū)和中西部地區(qū)的城市，網(wǎng)絡圖如下圖所示，其中各個城市之間的英里數(shù)顯示在各個分支上。確定用最少距離的管道連接10個城市的管道系統(tǒng)并計算出需要使用多少英里的管道。第三十九頁，共九十四頁，編輯于2023年，星期三29108745631丹佛奧馬哈得梅因印第安納波利斯阿爾伯克基俄克拉何馬城小石城納什維爾圣路易斯堪薩斯城400490520450750240310580210120250250235340260270320260340第四十頁，共九十四頁，編輯于2023年，星期三練習：我校擬設(shè)立一個網(wǎng)絡將主要的校園建筑與計算機中心連接起來提高網(wǎng)絡服務。一些電纜需要埋到地下，主要利用現(xiàn)有的電纜通道來架設(shè)。如下網(wǎng)絡顯示了節(jié)點1計算機中心與不同建筑物之間連接的各個分支及其距離，試確定網(wǎng)絡中可以連接所有建筑物的最小樹及需要的總的電纜長度。第四十一頁，共九十四頁，編輯于2023年，星期三2910874563112141113869848821145235391275648295810280186311382089210562718327693716457第四十二頁，共九十四頁，編輯于2023年，星期三網(wǎng)絡流（Flow）與最大流問題最大流問題是一類應用極為廣泛的問題，如運輸網(wǎng)絡中的人流、車流、物流，供水網(wǎng)絡中的水流，金融系統(tǒng)中的現(xiàn)金流，通信系統(tǒng)中的信息流，等等。20世紀50年代Ford–Fulkerson建立的“網(wǎng)絡流理論”，是網(wǎng)絡應用的重要組成部分。43第四十三頁，共九十四頁，編輯于2023年，星期三一、基本概念1．容量網(wǎng)絡：（1）

容量：有向圖中，每條弧上給出的最大通過能力（即加在每條弧上的最大可能負載）稱為該弧的容量。記為:C（vi，vj）或Cij，也常記為bij。（2）

容量網(wǎng)絡：對所有的弧都給出了容量的有向網(wǎng)絡，記為D=（V，A，C）或D=（V，A，B）。第四十四頁，共九十四頁，編輯于2023年，星期三

（1）流：①弧上的流——網(wǎng)絡中加在弧上的負載量。記為fij或xij。②圖上的流——加在網(wǎng)絡中各條弧上的一組負載量（即定義在弧集上的一個函數(shù)）。記為f={f（vi，vj）}={fij}2．流與可行流（2）零流：若網(wǎng)絡上所有弧上的流均為0，即對所有的i和j，都有fij=0，則稱相應的圖上的流為零流。第四十五頁，共九十四頁，編輯于2023年，星期三

（3）可行流：在容量網(wǎng)絡上，滿足容量限制條件和中間點平衡條件（連續(xù)性定理）的圖上的流。即0≤fij≤cij;其中f為網(wǎng)絡中從起點s到終點t的流量。問：零流是不是可行流？第四十六頁，共九十四頁，編輯于2023年，星期三

3．

割（割集、截集）：

設(shè)V為網(wǎng)絡中所有頂點的集合，將V剖分為兩個子集和，滿足:稱弧集為分離起點和終點的的割集。組成割集的各條弧容量之和稱為割容量（截量），所有割集中容量最小的割集稱為最小割。第四十七頁，共九十四頁，編輯于2023年，星期三

4、弧的分類（1）在可行流f={fij}中，按流量的特征分有：

①飽和弧——fij=cij②非飽和弧——fij<cij③零流弧——fij=0④非零流弧——fij>0

第四十八頁，共九十四頁，編輯于2023年，星期三（2）在容量網(wǎng)絡中從起點vs到收點vt的一條鏈中，按弧的方向分①前向弧——與鏈的方向一致的弧。前向弧全體記為μ+；②后向弧——與鏈的方向相反的弧。后向弧全體記為μ-

；其中,鏈的方向規(guī)定為:

從起點vs指向終點vt。第四十九頁，共九十四頁，編輯于2023年，星期三例：：{S，e1，V1，e2，V2，e3，V4，e4，V3，e5，T}V2TV1SV3V4e1e2e3e4e5e7e6e8e9+=：{e1，e3，e5}－

=：{e2，e4}第五十頁，共九十四頁，編輯于2023年，星期三5.增廣鏈（流量修正路線）：

設(shè)f是一可行流，μ是從起點vs到終點vt的一條鏈，若μ滿足下面兩個條件，則稱μ為關(guān)于可行流f的一條增廣鏈：①在弧（vi，vj）∈μ+上，

0≤fij<cij（即前向弧均為非飽和?。谠诨。╲i，vj）∈μ-上，

0<fij≤cij（即后向弧均為非零流?。?/p>

第五十一頁，共九十四頁，編輯于2023年，星期三二、什么是最大流問題？

在滿足容量限制條件和中間點平衡條件的要求下，求取流量值達到最大的可行流的一類優(yōu)化問題。簡言之，是求容量網(wǎng)絡中具有最大流量值的可行流問題。所求出的該可行流稱為最大流。第五十二頁，共九十四頁，編輯于2023年，星期三三、Ford-Fulkerson標記化方法的理論基礎(chǔ)

——最大流最小割定理（最大流量最小截量定理）在任一容量網(wǎng)絡中，從發(fā)點到收點的最大流流量等于該網(wǎng)絡最小割的割容量。＃第五十三頁，共九十四頁，編輯于2023年，星期三網(wǎng)絡最大流問題的標號算法1．確定初始可行流。如果沒有給定，也難以觀察得出，則將零流作為初始可行流；2．標號過程（目的是用標號法尋求增廣鏈）（1）標號的意義——符號vi（vj,i）表示vi點的標號是（vj，i），其中vj表示點vi的標號來自vj

，i

表示流量的修正量。第五十四頁，共九十四頁，編輯于2023年，星期三(2)標號過程給起點標上標號（0，+∞）；考察起點的所有相鄰未標號點：對正向弧(vs,vj)，檢查其是否飽和？是，則不加標記；不是，則加標記為(vs,j)，其中j=csj-fsj；對反向弧檢查其是否是零流??？是，則不加標記；不是，則加標記為(-vs,j)，其中j=fsj；第五十五頁，共九十四頁，編輯于2023年，星期三重復步驟二，但要注意把vs換成已得到標號的點；可能出現(xiàn)兩種結(jié)局：

a.標號過程中斷，收點得不到標號。說明該網(wǎng)絡中不存在增廣鏈，現(xiàn)行的可行流就是最大流；

b.收點得到標號，反向追蹤即可找到一條從起點到收點由標號點及相應的弧連接而成的增廣鏈。第五十六頁，共九十四頁，編輯于2023年，星期三3．調(diào)整過程修改流量，其中流量調(diào)整量，指增廣鏈上所有弧的流量修正量；在增廣鏈的正向弧上增加；反向弧上減少；其它弧上流量不變。

調(diào)整方法：第五十七頁，共九十四頁，編輯于2023年，星期三vsv1v2v3v4vt(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(5,3)(2,1)(vs,4)(-v1,1)(v2,1)(-v2,1)(v3,1)(5,2)(1,0)(1,0)(2,2)(vs,3)例：弧旁的數(shù)是（cij,fij)：（容量，流量）最大流為5.第五十八頁，共九十四頁，編輯于2023年，星期三案例：聯(lián)邦航空局（FAA）批準給全航空一個新的航空許可，準許它運行從洛杉磯到芝加哥的多條航線。每條航線的航班數(shù)顯示在下圖網(wǎng)絡中，確定每天從洛杉磯到芝加哥的最大航班數(shù)，并確定每條路線的航班數(shù)。第五十九頁，共九十四頁，編輯于2023年，星期三1235467810586754476578洛杉磯鳳凰城達拉斯丹佛圣路易斯芝加哥鹽湖城堪薩斯城第六十頁，共九十四頁，編輯于2023年，星期三vsvt(4,3)(1,1)(7,6)(3,2)(3,2)(4,3)(2,2)(8,2)(4,1)(3,2)(4,3)(5,3)練習：求下圖所示網(wǎng)絡的最大流。（cij,fij)第六十一頁，共九十四頁，編輯于2023年，星期三二、起迄點重合的單一路線優(yōu)化（一）旅行商問題TSP模型0-1整數(shù)規(guī)劃模型圖7-6TSP問題示意圖代價矩陣Cij變量矩陣第六十二頁，共九十四頁，編輯于2023年，星期三（二）中國郵遞員問題1．確定可行方案2．判斷最優(yōu)方案第六十三頁，共九十四頁，編輯于2023年，星期三第四節(jié)行車路線及時刻表的制定一、運輸路線及時刻表制訂的原則二、行車路線制訂的掃描法三、行車路線制訂的節(jié)約法第六十四頁，共九十四頁，編輯于2023年，星期三合理路線和時刻表的制定原則（1）安排車輛負責相互距離最接近的站點的貨物運輸。圖7-11合理的車輛分派方案圖7-12不合理的車輛分派方案一、運輸路線及時刻表制訂的原則第六十五頁，共九十四頁，編輯于2023年，星期三(2)安排車輛各日途經(jīng)的站點時，就注意使站點群更加緊湊。倉庫FFFFFTTTTTTFTa)不合理的線路劃分方式：線路交叉第六十六頁，共九十四頁，編輯于2023年，星期三b)較合理的線路劃分方式倉庫FFFFFTTTTTTFT第六十七頁，共九十四頁，編輯于2023年，星期三(3)從倉庫最遠的站點開始設(shè)計路線。要設(shè)計出有效的路線，首先要劃分出距倉庫最遠的站點周圍的站點群，然后逐步劃出倉庫附近的站點群。一旦確定了最遠的站點就應該選定距該核心站點最近的一些站點形成站點群，分派載貨能力能滿足該站點群需要地卡車。然后，從還沒有分派車輛的其他站點中找出距倉庫最遠的站點，分派另一車輛。如此往復，直到所有站點都分派有車輛。第六十八頁，共九十四頁，編輯于2023年，星期三圖（a）是不合理的運行路線，圖（b）是合理的運行路線。圖7-13運輸路線示意圖

（4）卡車的行車路線不交叉，且應呈水滴狀。第六十九頁，共九十四頁，編輯于2023年，星期三（5）盡可能使用最大的車輛進行運送，這樣設(shè)計出的路線是最有效的。（6）取貨、送貨應該混合安排，不應該在完成全部送貨任務之后再取貨。（7）對過于遙遠而無法歸入群落的站點，可以采用其它配送方式。第七十頁，共九十四頁，編輯于2023年，星期三行車路線和時刻表的制定方法1、掃描法（1）在地圖或方格圖中確定所有站點的位置。（2）自倉庫始沿任一方向向外劃一條直線。沿順時針或逆時針方向旋轉(zhuǎn)該直線直到與某站點相交?？紤]：如果在某線路上增加該站點，是否會超過車輛的載貨能力？如果沒有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個站點相交。再次計算累計貨運量是否超過車輛的運載能力。如果超過，就剔除最后的那個站點。繼續(xù)這一過程直到所有站點得到安排。（3）排定各路線上每個站點的順序使行車距離最短。排序時可使用水滴法。第七十一頁，共九十四頁，編輯于2023年，星期三案例：

Smith卡車運輸公司用廂式貨車從貨主那里取貨。貨物先運回倉庫，集中后以更大的批量進行長途運輸。下圖列出了一天的取貨量，廂式貨車的載貨量是1000件。完成所有取貨任務一般需要整整一天的時間。公司想知道需要多少條運輸路線（即多少部車），每條路線上應該經(jīng)過哪些站點，每條路線上的站點應該怎樣排序。第七十二頁，共九十四頁，編輯于2023年，星期三倉庫200020002000200030001000400020003000300020001000地理區(qū)域取貨點第七十三頁，共九十四頁，編輯于2023年，星期三倉庫200020002000200030001000400020003000300020001000路線＃1路線＃2路線＃3第七十四頁，共九十四頁，編輯于2023年，星期三二、行車路線制訂的掃描法原理:先以倉庫(物流中心)為原點，將所有需求點的極坐標算出，然后依角度大小以逆時針或順時針方向掃描，若滿足車輛裝載量即劃分為一群，將所有點掃描完畢后在每個群內(nèi)用最短路徑法求出車輛最佳行駛路徑。[例7-4]表7-10客戶數(shù)據(jù)信息客戶12345678910111213Di(噸)1.92.83.152.4232.252.51.82.151.62.61.5Xi20.018.818.319.118.818.619.519.9320.019.518.719.520.3Yi4.805.175.004.786.425.885.985.935.554.554.555.195.20第七十五頁，共九十四頁，編輯于2023年，星期三第一步：求出各客戶點的極坐標。第二步：掃描劃分客戶群。第三步：確定每輛車的最佳路徑。圖7-14客戶位置及掃描法求出的結(jié)果第七十六頁，共九十四頁，編輯于2023年，星期三三、行車路線制訂的節(jié)約法基本思想：如果將運輸問題中的兩個回路合并成一個回路，就可縮短線路總里程（即節(jié)約了距離），并減少了一輛卡車。圖7-15節(jié)約法的圖形描述第七十七頁，共九十四頁，編輯于2023年，星期三[例7-5]表7-11客戶坐標及訂單規(guī)模站點X坐標Y坐標訂單規(guī)模（件）配送中心顧客1顧客2顧客3顧客4顧客5顧客6顧客7顧客8顧客9顧客10顧客11顧客12顧客1300679152017711520720125151230-2-4-6-6-7-9-1548364392571656305747915538第七十八頁，共九十四頁，編輯于2023年，星期三1．確定距離方陣表7-12客戶及配送中心之間的距離配送中心客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12客戶13客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12客戶131281715152017861621111509891723221718232822270108915139121418142004142020192222262430011161616201922212806511179111422041420871623010164612200681351201419790591601320080第七十九頁，共九十四頁，編輯于2023年，星期三2．計算節(jié)約矩陣表7-13第一次計算的節(jié)約矩陣客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12客戶13客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12客戶130112118109730551001515141312721011530281817146111124201919167112145202927124222512803314628341512015729321612081616141108810120321815019160180第八十頁，共九十四頁，編輯于2023年，星期三3．將客戶劃歸到不同的運輸路線表7-14第一次改進后的節(jié)約矩陣線路客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12客戶13客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12客戶1312345678910612130112118109730551001515141312721011530281817146111124201919167112145202927124222512803314628341512015729321612081616141108810120321815019160180第八十一頁，共九十四頁，編輯于2023年，星期三表7-15第二次改進后的節(jié)約矩陣線路客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12客戶13客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12客戶1312345668910612130112118109730551001515141312721011530281817146111124201919167112145202927124222512803314628341512015729321612081616141108810120321815019160180第八十二頁，共九十四頁，編輯于2023年，星期三表7-16第三次改進后的節(jié)約矩陣線路客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12客戶13客戶1客戶2客戶3客戶4客戶5客戶6客戶7客戶8客戶9客戶10客戶11客戶12客戶1312335668910612130112118109730551001515141312721011530281817146111124201919167112145202927124222512803314628341512015729321612081616141108810120321815019160180第八十三頁，共九十四頁，編輯于2023年，星期三圖7-16配送中心送貨線路規(guī)劃方案第八十四頁，共九十四頁，編輯于2023年，星期三第五節(jié)運輸工具與貨載的最優(yōu)分配一、航線配船優(yōu)化問題二、多車多品種貨載配車優(yōu)化第八十五頁，共九十四頁，編輯于2023年，星期三一、航線配船優(yōu)化問題（一）問題概述（二）數(shù)學模型的建立1．參數(shù)說明2．目標函數(shù)

minK=3．約束條件第八十六頁，共九十四頁，編輯于2023年，星期三（三）航線配船優(yōu)化舉例表7-17某船公司船型及航線與航次表7-18不同航線和船型的營運成本123456Ⅰ型船（1500TEU），8艘232312Ⅱ型船（850TEU），12艘343423Ⅲ型船（500TEU），10艘444521航線船型季節(jié)最大航次數(shù)123456Ⅰ型船（1500TEU），8艘302528253532Ⅱ型船（850TEU），12艘242425243028Ⅲ型船（500TEU），10艘182020.518.52332航線船型單船單航次成本（萬USD）第八十七頁，共九十四頁，編輯于2023年，星期三表7-19不同航線的運量和機會成本解：（1）目標函數(shù)（2）約束條件（3）求解結(jié)果求解得出的航線最優(yōu)配備船舶計劃如下：航線123456機會成本（萬USD/TEU）0.150.1250.10.10.150.125運量（TEU）600080005000450030007000123456Ⅰ型船（1500TEU），8艘003224Ⅱ型船（850TEU），12艘700001Ⅲ型船（500TEU），10艘011400航線船型航次數(shù)第八十八頁，共九十四頁，編輯于2023年，星期三二、多車多品種貨載配車優(yōu)化（一）問題描述（二）模型建立1．變量及參數(shù)說明2．目標函數(shù)3．約束條件（1）每輛車的載重能力限制：（2）每輛車的容積限制：（3）每一批貨物最多只能裝入一輛車：（4）變量約束：第八十九頁，共九十四頁，編輯于2023年，星期三（三）啟發(fā)式方法求解算例表7-20貨物信息表1．啟發(fā)式算法簡介2．求解步驟第一階段：貨物聚類（1）將每批貨物看成是一類,記做G1,G2,…,Gn。計算其對應貨物的容重比。1234567891011121314vi(m3)2.43.60.535.43.51.42.426.42.41.21.80.5gi(t)312.50.6210.50.60.821.5121第九十頁，共九十四頁，編輯于2023年，星期三（2）確定每批貨物之間的距離dij，。計算出n種貨物間容重比距離dij(i,j=1,2,…,n)，得到貨物距離關(guān)系表記作D(0)，見表7-21。表7-21貨物距離關(guān)系表D(0)cidijcjG1G2G3G4G5G6G7G8G9G10G11G12G13G140.83.60.252.73.52.842.53.21.61.20.90.5G10.80

G23.62.80

G30.20.63.40

G454.21.44.80

G52.71.90.92.52.30

G63.52.70.13.31.50.80

G72.820.82.62.20.10.70

G843.20.43.811.30.51.20

G92.51.71.12.32.50.210.31.50

G103.22.40.431.80.50.30.40.80.70

G111.60.821.43.41.11.91.22.40.91.60

G121.20.42.413.81.52.31.62.81.320.40

G130.90.12.70.74.11.82.61.93.11.62.30.70.30

G140.50.33.10.34.52.23