第七章物流運(yùn)輸優(yōu)化與決策第一節(jié)

物流運(yùn)輸服務(wù)選擇決策一、物流運(yùn)輸方式選擇的原則二、基于物流總成本比較的運(yùn)輸方式選擇三、承運(yùn)人的選擇與評(píng)價(jià)一、物流運(yùn)輸方式選擇的原則（一）安全性原則（二）及時(shí)性原則（三）準(zhǔn)確性原則（四）經(jīng)濟(jì)性原則二、基于物流總成本比較的運(yùn)輸方式選擇基于運(yùn)輸成本與庫(kù)存成本的總成本分析方法：表7-1各種運(yùn)輸方式的基本參數(shù)表7-2各種運(yùn)輸方式成本計(jì)算結(jié)果運(yùn)輸方式費(fèi)率R(元/件)時(shí)間T(天)年運(yùn)送批次平均存貨量Q/2鐵路0.12110100000馱背0路0.252042000航空1.424020250成本類型計(jì)算公式鐵路運(yùn)輸馱背運(yùn)輸公路運(yùn)輸航空運(yùn)輸運(yùn)輸成本R

D70000105000140000980000在途庫(kù)存ICDT/3653624662416448630134521工廠存貨ICQ/2900000418500378000182250倉(cāng)庫(kù)存貨I(C+R)Q/2903000420593380520190755總成本

223546611857379848211387526三、承運(yùn)人的選擇與評(píng)價(jià)（一）影響承運(yùn)人選擇的主要因素1．運(yùn)輸成本2．運(yùn)輸時(shí)間和運(yùn)輸時(shí)間的可靠性3．可到達(dá)性4．服務(wù)能力5．安全性（二）承運(yùn)人的評(píng)價(jià)方法綜合因素加權(quán)求和法表7-3承運(yùn)商評(píng)估報(bào)告示例承運(yùn)人：_____時(shí)期:_____最高分評(píng)價(jià)標(biāo)準(zhǔn)承運(yùn)人分?jǐn)?shù)備注13滿足接貨時(shí)間表1313滿足搬運(yùn)109運(yùn)輸時(shí)間910運(yùn)輸時(shí)間一致性77費(fèi)率53附加費(fèi)1高的住宅搬運(yùn)5運(yùn)營(yíng)比率396.5％增長(zhǎng)4收益性33索賠頻率33索賠解決310賬單錯(cuò)誤79跟蹤能力711設(shè)備可用性l無(wú)平臺(tái)裝貨卡車100總分72第二節(jié)貨物運(yùn)輸調(diào)配決策一、多起迄點(diǎn)間的直達(dá)運(yùn)輸二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配一、多起迄點(diǎn)間的直達(dá)運(yùn)輸（一）產(chǎn)銷平衡的運(yùn)輸問(wèn)題1．產(chǎn)銷平衡運(yùn)輸問(wèn)題數(shù)學(xué)模型2．求解方法單純形法、表上作業(yè)法圖7-1多點(diǎn)之間的物資運(yùn)輸調(diào)撥問(wèn)題示意圖（二）產(chǎn)銷不平衡的運(yùn)輸問(wèn)題1．總產(chǎn)量大于總銷量：則增加一個(gè)假想的銷地Bn+1，其銷量為：2．總銷量大于總產(chǎn)量：則增加一個(gè)假想的產(chǎn)地Am+1，其產(chǎn)量為：二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配（一）問(wèn)題描述圖7-2有中間轉(zhuǎn)運(yùn)的物資運(yùn)輸調(diào)撥問(wèn)題（二）數(shù)學(xué)模型目標(biāo)函數(shù)為：約束條件為：（1）配送量

生產(chǎn)能力的限制：k=1，2，…，f；（2）流通中心發(fā)送能力的限制：

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

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

圖7-3從起點(diǎn)到終點(diǎn)的運(yùn)輸網(wǎng)絡(luò)圖動(dòng)態(tài)規(guī)劃方法

B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G第一階段第二階段第三階段第四階段第五階段第六階段531368766835342138223335526643437597681310912131618該點(diǎn)到G點(diǎn)的最短距離（一）動(dòng)態(tài)規(guī)劃法圖7-4多階段劃分52871220141919（二）Dijkstra方法[例7-3]圖7-5運(yùn)輸網(wǎng)絡(luò)圖E.W.Dijkstra算法（標(biāo)號(hào)算法）算法基本思路分析：（逐步向外搜索）5216582899722121∞∞∞∞∞∞∞22751112121075667991010633xy起點(diǎn)到該點(diǎn)的最短距離起點(diǎn)到該點(diǎn)的最短距離的上界（二）Dijkstra方法[例7-3]圖7-5運(yùn)輸網(wǎng)絡(luò)圖0∞∞∞∞∞∞02542944487714813表7-8Dijkstra算法步驟表步驟P標(biāo)號(hào)點(diǎn)與P點(diǎn)直接相連的T標(biāo)號(hào)點(diǎn)相應(yīng)的總距離第n個(gè)最近點(diǎn)最小總距離最新連接1OA2A2OA2OACB42+2=4CB44OCAB3ABCDEE2+7=94+3=74+4=8E7BE4ABEDDD2+7=94+4=87+1=8DD88BDED5DETT8+5=137+7=14T13DTA起點(diǎn)90B13834866C9084E96D1564875F12050132IH48G150126126J終點(diǎn)

二、物流運(yùn)輸?shù)膬?yōu)化模型按貨物的自然流向組織貨物合理的物流運(yùn)輸是市場(chǎng)經(jīng)濟(jì)規(guī)律的客觀要求，它直接決定著物流的效率與效果。為了制定在產(chǎn)銷平衡條件下的運(yùn)量規(guī)劃方案，必須建立數(shù)學(xué)模型，運(yùn)用數(shù)學(xué)方法來(lái)解決。三、單純形法對(duì)于運(yùn)輸問(wèn)題，一般采用單純形法求解，具體方法和步驟已在前面介紹過(guò)，這里不再列述。經(jīng)驗(yàn)表明，當(dāng)起運(yùn)站和目的地都多于5個(gè)時(shí)，用其它方法求解比較困難或繁瑣，最好用單純形法求解。四、圖表分析法圖表分析法是在分區(qū)產(chǎn)銷平衡所確定的供銷區(qū)域內(nèi)，按照生產(chǎn)地與消費(fèi)地的地理分布，根據(jù)有利于生產(chǎn)、有利于市場(chǎng)供給、近產(chǎn)近銷的原則，應(yīng)用交通路線示意圖和商品產(chǎn)銷平衡表找出產(chǎn)銷之間經(jīng)濟(jì)合理的商品運(yùn)輸路線。五、圖上作業(yè)法

1．運(yùn)輸線路不成圈的圖上作業(yè)法

2．運(yùn)輸線路成圈的圖上作業(yè)法運(yùn)輸線路成圈，就是形成閉合回路的“環(huán)”形路線，包括一個(gè)圈（有三角形、四邊形、多邊形）和多個(gè)圈。成圈的線路流向圖要同時(shí)達(dá)到既無(wú)對(duì)流現(xiàn)象、又無(wú)迂回現(xiàn)象的要求才是最優(yōu)流向圖。對(duì)于成圈運(yùn)輸線路的圖上作業(yè)法，可按下述三個(gè)步驟尋求最優(yōu)方案，如表9-22所示。表9-22成圈運(yùn)輸線路的圖上作業(yè)法的步驟步驟詳述去段破圈確定初始運(yùn)輸方案就是在成圈的線路中，先假設(shè)某兩點(diǎn)間的線路“不通”，去掉這段線路，把成圈線路轉(zhuǎn)化為不成圈的線路，即破圈；按照運(yùn)輸線路不成圈的圖上作業(yè)法，即可得到初始運(yùn)輸方案。檢查有無(wú)迂回現(xiàn)象因?yàn)榱飨蚣^都統(tǒng)一畫在線路右邊，所以圈內(nèi)圈外都畫有一些流向。分別檢查每個(gè)小圈，如果圈內(nèi)和圈外流向的總長(zhǎng)度都不超過(guò)全圈總長(zhǎng)度的1/2，那么，全圈就沒(méi)有迂回現(xiàn)象了，這個(gè)線路流向圖就是最優(yōu)的，對(duì)應(yīng)的就是最優(yōu)運(yùn)輸方案。否則轉(zhuǎn)向第三步。重新去段破圈，調(diào)整流向在超過(guò)全圈總長(zhǎng)1/2的里（外）圈各段流向線上減去最小運(yùn)量，然后在相反方向的外（里）圈流向線上和原來(lái)沒(méi)有流向線的各段上，加上減去的最小運(yùn)量，這樣可以得到一個(gè)新的線路流向圖，然后轉(zhuǎn)到第二步檢查有無(wú)迂回現(xiàn)象。如此反復(fù)，直到得到最優(yōu)線路流向圖為止。如果全圈存在兩個(gè)及兩個(gè)以上的圈，則需分別對(duì)各圈進(jìn)行是否存在迂回線路的檢查，如果各圈的里、外圈都不超過(guò)全圈總線長(zhǎng)的1/2，則不存在迂回現(xiàn)象，此方案為最優(yōu)運(yùn)輸方案。(13)(18)最小樹(shù)問(wèn)題與網(wǎng)絡(luò)設(shè)計(jì)樹(shù)（Tree）和最小樹(shù)樹(shù)是圖論中一類重要的圖，實(shí)際中很多系統(tǒng)的結(jié)構(gòu)都是樹(shù)。樹(shù)——連通且不含圈的圖，簡(jiǎn)記為T。樹(shù)的性質(zhì)：（1）在樹(shù)中，任意兩個(gè)頂點(diǎn)間必有且僅有一條鏈；（2）在樹(shù)中，在不相鄰的頂點(diǎn)中添加一條樹(shù)枝，則恰好得到一個(gè)圈；（3）在樹(shù)中，任意去掉一條樹(shù)枝，就變成分離圖；（4）設(shè)T是棵有n個(gè)頂點(diǎn)的樹(shù)，則T的樹(shù)枝數(shù)為n-1；（5）一棵樹(shù)至少有兩個(gè)懸掛點(diǎn)；（6）樹(shù)是連通且邊數(shù)最少的圖。最小樹(shù)問(wèn)題樹(shù)（Tree）和最小樹(shù)樹(shù)的權(quán)——

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

）=（e）；eTk最小樹(shù)——

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

）=min{(Tk)}最小樹(shù)問(wèn)題樹(shù)（Tree）和最小樹(shù)破圈法，避圈法求最小支撐樹(shù)：圖G1542453134421512最小支撐樹(shù)T最小支撐樹(shù)T1212112123121123

案例：幾家石油公司準(zhǔn)備聯(lián)合建設(shè)一個(gè)輸油管道來(lái)連接西南地區(qū)、東南地區(qū)和中西部地區(qū)的城市，網(wǎng)絡(luò)圖如下圖所示，其中各個(gè)城市之間的英里數(shù)顯示在各個(gè)分支上。確定用最少距離的管道連接10個(gè)城市的管道系統(tǒng)并計(jì)算出需要使用多少英里的管道。29108745631丹佛奧馬哈得梅因印第安納波利斯阿爾伯克基俄克拉何馬城小石城納什維爾圣路易斯堪薩斯城400490520450750240310580210120250250235340260270320260340練習(xí)：我校擬設(shè)立一個(gè)網(wǎng)絡(luò)將主要的校園建筑與計(jì)算機(jī)中心連接起來(lái)提高網(wǎng)絡(luò)服務(wù)。一些電纜需要埋到地下，主要利用現(xiàn)有的電纜通道來(lái)架設(shè)。如下網(wǎng)絡(luò)顯示了節(jié)點(diǎn)1計(jì)算機(jī)中心與不同建筑物之間連接的各個(gè)分支及其距離，試確定網(wǎng)絡(luò)中可以連接所有建筑物的最小樹(shù)及需要的總的電纜長(zhǎng)度。29108745631121411869848821145235391275648295810280186311382089210562718327693716457網(wǎng)絡(luò)流（Flow）與最大流問(wèn)題

最大流問(wèn)題是一類應(yīng)用極為廣泛的問(wèn)題，如運(yùn)輸網(wǎng)絡(luò)中的人流、車流、物流，供水網(wǎng)絡(luò)中的水流，金融系統(tǒng)中的現(xiàn)金流，通信系統(tǒng)中的信息流，等等。20世紀(jì)50年代Ford–Fulkerson建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。一、基本概念1．容量網(wǎng)絡(luò)：（1）

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

容量網(wǎng)絡(luò)：對(duì)所有的弧都給出了容量的有向網(wǎng)絡(luò)，記為D=（V，A，C）或D=（V，A，B）。

（1）流：①弧上的流——網(wǎng)絡(luò)中加在弧上的負(fù)載量。記為fij或xij。②圖上的流——加在網(wǎng)絡(luò)中各條弧上的一組負(fù)載量（即定義在弧集上的一個(gè)函數(shù)）。記為f={f（vi，vj）}={fij}2．流與可行流（2）零流：若網(wǎng)絡(luò)上所有弧上的流均為0，即對(duì)所有的i和j，都有fij=0，則稱相應(yīng)的圖上的流為零流。

（3）可行流：在容量網(wǎng)絡(luò)上，滿足容量限制條件和中間點(diǎn)平衡條件（連續(xù)性定理）的圖上的流。即0≤fij≤cij;其中f為網(wǎng)絡(luò)中從起點(diǎn)s到終點(diǎn)t的流量。問(wèn)：零流是不是可行流？

3．

割（割集、截集）：

設(shè)V為網(wǎng)絡(luò)中所有頂點(diǎn)的集合，將V剖分為兩個(gè)子集和，滿足:稱弧集為分離起點(diǎn)和終點(diǎn)的的割集。組成割集的各條弧容量之和稱為割容量（截量），所有割集中容量最小的割集稱為最小割。

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

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

（2）在容量網(wǎng)絡(luò)中從起點(diǎn)vs到收點(diǎn)vt的一條鏈中，按弧的方向分①前向弧——與鏈的方向一致的弧。前向弧全體記為μ+；②后向弧——與鏈的方向相反的弧。后向弧全體記為μ-

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

從起點(diǎn)vs指向終點(diǎn)vt。例：

：{S，e1，V1，e2，V2，e3，V4，e4，V3，e5，T}V2TV1SV3V4e1e2e3e4e5e7e6e8e9

+=：{e1，e3，e5}

－

=：{e2，e4}5.增廣鏈（流量修正路線）：

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

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

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

二、什么是最大流問(wèn)題？

在滿足容量限制條件和中間點(diǎn)平衡條件的要求下，求取流量值達(dá)到最大的可行流的一類優(yōu)化問(wèn)題。簡(jiǎn)言之，是求容量網(wǎng)絡(luò)中具有最大流量值的可行流問(wèn)題。所求出的該可行流稱為最大流。三、Ford-Fulkerson標(biāo)記化方法的理論基礎(chǔ)

——最大流最小割定理（最大流量最小截量定理）在任一容量網(wǎng)絡(luò)中，從發(fā)點(diǎn)到收點(diǎn)的最大流流量等于該網(wǎng)絡(luò)最小割的割容量。＃網(wǎng)絡(luò)最大流問(wèn)題的標(biāo)號(hào)算法1．確定初始可行流。如果沒(méi)有給定，也難以觀察得出，則將零流作為初始可行流；2．標(biāo)號(hào)過(guò)程（目的是用標(biāo)號(hào)法尋求增廣鏈）（1）標(biāo)號(hào)的意義——符號(hào)vi（vj,

i）表示vi點(diǎn)的標(biāo)號(hào)是（vj，

i），其中vj表示點(diǎn)vi的標(biāo)號(hào)來(lái)自vj

，

i

表示流量的修正量。(2)標(biāo)號(hào)過(guò)程

給起點(diǎn)標(biāo)上標(biāo)號(hào)（0，+∞）；

考察起點(diǎn)的所有相鄰未標(biāo)號(hào)點(diǎn)：對(duì)正向弧(vs,vj)，檢查其是否飽和？是，則不加標(biāo)記；不是，則加標(biāo)記為(vs,

j)，其中

j=csj-fsj；對(duì)反向弧檢查其是否是零流?。渴?，則不加標(biāo)記；不是，則加標(biāo)記為(-vs,

j)，其中

j=fsj；

重復(fù)步驟二，但要注意把vs換成已得到標(biāo)號(hào)的點(diǎn)；可能出現(xiàn)兩種結(jié)局：

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

b.收點(diǎn)得到標(biāo)號(hào)，反向追蹤即可找到一條從起點(diǎn)到收點(diǎn)由標(biāo)號(hào)點(diǎn)及相應(yīng)的弧連接而成的增廣鏈。3．調(diào)整過(guò)程修改流量，其中流量調(diào)整量，指增廣鏈上所有弧的流量修正量；在增廣鏈的正向弧上增加；反向弧上減少；其它弧上流量不變。

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

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

Smith卡車運(yùn)輸公司用廂式貨車從貨主那里取貨。貨物先運(yùn)回倉(cāng)庫(kù)，集中后以更大的批量進(jìn)行長(zhǎng)途運(yùn)輸。下圖列出了一天的取貨量，廂式貨車的載貨量是1000件。完成所有取貨任務(wù)一般需要整整一天的時(shí)間。公司想知道需要多少條運(yùn)輸路線（即多少部車），每條路線上應(yīng)該經(jīng)過(guò)哪些站點(diǎn)，每條路線上的站點(diǎn)應(yīng)該怎樣排序。倉(cāng)庫(kù)200020002000200030001000400020003000300020001000地理區(qū)域取貨點(diǎn)倉(cāng)庫(kù)200020002000200030001000400020003000300020001000路線＃1路線＃2路線＃3二、行車路線制訂的掃描法原理:先以倉(cāng)庫(kù)(物流中心)為原點(diǎn)，將所有需求點(diǎn)的極坐標(biāo)算出，然后依角度大小以逆時(shí)針或順時(shí)針?lè)较驋呙瑁魸M足車輛裝載量即劃分為一群，將所有點(diǎn)掃描完畢后在每個(gè)群內(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第一步：求出各客戶點(diǎn)的極坐標(biāo)。第二步：掃描劃分客戶群。第三步：確定每輛車的最佳路徑。圖7-14客戶位置及掃描法求出的結(jié)果三、行車路線制訂的節(jié)約法基本思想：如果將運(yùn)輸問(wèn)題中的兩個(gè)回路合并成一個(gè)回路，就可縮短線路總里程（即節(jié)約了距離），并減少了一輛卡車。圖7-15節(jié)約法的圖形描述[例7-5]表7-11客戶坐標(biāo)及訂單規(guī)模站點(diǎn)X坐標(biāo)Y坐標(biāo)訂單規(guī)模（件）配送中心顧客1顧客2顧客3顧客4顧客5顧客6顧客7顧客8顧客9顧客10顧客11顧客12顧客1300679152017711520720125151230-2-4-6-6-7-9-15483643925716563057479155381．確定距離方陣表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客戶1312817151520178616211115098917232217182328222701089151391214181420041420201922222624300111616162019222128065111791114220414208716230101646122006813512014197905916013200802．計(jì)算節(jié)約矩陣表7-13第一次計(jì)算的節(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客戶1301121181097305510015151413127210115302818171461111242019191671121452029271242225128033146283415120157293216120816161411088101203218150191601803．將客戶劃歸到不同的運(yùn)輸路線表7-14第一次改進(jìn)后的節(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表7-15第二次改進(jìn)后的節(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表7-16第三次改進(jìn)后的節(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圖7-16配送中心送貨線路規(guī)劃方案第五節(jié)運(yùn)輸工具與貨載的最優(yōu)分配一、航線配船優(yōu)化問(wèn)題二、多車多品種貨載配車優(yōu)化一、航線配船優(yōu)化問(wèn)題（一）問(wèn)題概述（二）數(shù)學(xué)模型的建立1．參數(shù)說(shuō)明2．目標(biāo)函數(shù)

minK=3．約束條件（三）航線配船優(yōu)化舉例表7-17某船公司船型及航線與航次表7-18不同航線和船型的營(yíng)運(yùn)成本123456Ⅰ型船（1500TEU），8艘232312Ⅱ型船（850TEU），12艘343423Ⅲ型船（500TEU），10艘444521航線船型季節(jié)最大航次數(shù)123456Ⅰ型船（1500TEU），8艘302528253532Ⅱ型船（850TEU），12艘242425243028Ⅲ型船（500TEU），10艘182020.518.52332航線船型單船單航次成本（萬(wàn)USD）表7-19不同航線的運(yùn)量和機(jī)會(huì)成本解：（1）目標(biāo)函數(shù)（2）約束條件（3）求解結(jié)果求解得出的航線最優(yōu)配備船舶計(jì)劃如下：航線123456機(jī)會(huì)成本（萬(wàn)USD/TEU）0.150.1250.10.10.150.125運(yùn)量（TEU）600080005000450030007000123456Ⅰ型船（1500TEU），8艘003224Ⅱ型船（850TEU），12艘700001Ⅲ型船（500TEU），10艘011400航線船型航次數(shù)二、多車多品種貨載配車優(yōu)化（一）問(wèn)題描述（二）模型建立1．變量及參數(shù)說(shuō)明2．目標(biāo)函數(shù)3．約束條件（1）每輛車的載重能力限制：（2）每輛車的容積限制：（3）每一批貨物最多只能裝入一輛車：（4）變量約束：（三）啟發(fā)式方法求解算例表7-20貨物信息表1．啟發(fā)式算法簡(jiǎn)介2．求解步驟第一階段：貨物聚類（1）將每批貨物看成是一類,記做G1,G2,…,Gn。計(jì)算其對(duì)應(yīng)貨物的容重比。1234567891011121314vi(m3)2.43.60.535.43.51.42.426.42.41.21.80.5gi(t)312.50.6210.50.60.821.5121（2）確定每批貨物之間的距離dij，。計(jì)算出n種貨物間容重比距離dij(i,j=1,2,…,n)，得到貨物距離關(guān)系表記作D(0)，見(jiàn)表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.232.33.522.71.10.70.40（3）比較D(0)中的每個(gè)非零元素dij，如果任意dij小于臨界值C則停止。如果存在某個(gè)dij大于C則繼續(xù)下一步。（4）把距離最大的兩批貨物合并成一個(gè)新類，記做Gn+1，