物流管理第七章

物流管理第七章第1頁/共97頁企業(yè)物流管理第2頁/共97頁第七章運輸決策商學(xué)院企業(yè)物流管理3第3頁/共97頁運輸是物流決策中的關(guān)鍵所在。除采購產(chǎn)品的成本外，一般來講，運輸成本比任何其他物流成本所占的比重都高。盡管運輸決策的形式多種多樣，但其中首要的不外乎運輸方式選擇、承運人運輸路線的規(guī)劃、車輛調(diào)度和合并運輸?shù)软梼?nèi)容。本章將介紹進行這些重要決策的方法。4第4頁/共97頁7.1運輸服務(wù)的選擇運輸方式的選擇或某運輸方式內(nèi)服務(wù)內(nèi)容的選擇取決于運輸服務(wù)的眾多特性。6個服務(wù)變量對運輸服務(wù)選擇非常重要：(1)運輸費用；(2)可靠性；(3)在途時間；(4)滅失、損壞、投訴處理和貨物跟蹤查詢；(5)托運人市場特征；(6)承運人特征在途時間(速度)和運輸時間的波動(可靠性)是主要決定因素，其次是成本。5第5頁/共97頁7.1.1基本的成本權(quán)衡如果選擇速度慢、可靠性差的運輸服務(wù)，物流渠道中就需要有更多的庫存。這樣，就需要考慮庫存持有成本升高抵消運輸服務(wù)成本降低的情況。因此現(xiàn)有方案中最合理的應(yīng)該是既能滿足顧客需求，又使總成本最低的服務(wù)。(見資料7．1)資料7．1例子

卡利奧箱包公司(Carry-ALLLuggageCompany)是生產(chǎn)系列箱包產(chǎn)品的公司。公司的分撥計劃是將生產(chǎn)的成品先存放在工廠，然后由公共承運人運往公司自有的基層倉庫。目前，公司使用鐵路運輸將東海岸工廠的成品運往西海岸的倉庫。鐵路運輸?shù)钠骄鶗r間為了T=21天，每個存儲點子均儲存100000件行李箱包，箱包的平均價值C=30美元，庫存成本I=30％／年。6第6頁/共97頁公司希望選擇使總成本最小的運輸方式。據(jù)估計，運輸時間從目前的21天每減少一天，平均庫存水平可以減少1％。每年西誨岸倉庫賣出D=700000件箱包。公司可以利用以下運輸服務(wù)：其中，采購成本和運輸時間的變化忽略不計。7運輸服務(wù)方式運輸費率（美元/單位）門到門運送時間(天)每年運輸批次鐵路運輸0.102410馱背運輸0.151420卡車運輸0.20520航空運輸1.40240第7頁/共97頁圖7-1是當前公司分撥系統(tǒng)的圖示。選擇不同運輸方式將影響貨物的在途時間。在途貨物可以用年需求(D)的一定比例(即T／365)表示，其中了表示平均運送時間，因此，在途庫存的持有成本就為ICDT/365。8第8頁/共97頁分撥渠道兩端的平均庫存大約是Q／2，其中Q是運輸批量。每單位貨物的庫存成本為I×C，但產(chǎn)品價值C在分撥渠道的不同地點是不同的。例如在工廠，C是產(chǎn)品的出廠價；而在倉庫，c是產(chǎn)品的出廠價加上運輸費率。用運輸費率乘年需求量就得到每年的總運輸成本R×D。針對每種運輸方式計算四種相關(guān)成本，計算結(jié)果在表7-1列出。由此可以看出，雖然采用鐵路運輸時的運輸費率最低，采用航空運輸時的庫存成本最低，但卡車運輸?shù)目偝杀咀畹?。如果使用卡車運輸，運輸時間減少到5天，兩個端點的庫存水平將減少50％。9第9頁/共97頁10第10頁/共97頁7.1.2考慮競爭因素如果供應(yīng)渠道中的買方從多個供應(yīng)商那里購買商品，那么物流服務(wù)就會和價格一樣影響買方對供應(yīng)商的選擇。相反，如果供應(yīng)商針對各自的銷售渠道選擇不同的運輸方式，就可以控制其物流服務(wù)的各項要素，進而影響買方的購買。對買方而言，更好的運輸服務(wù)(運送時間更短，波動更小)意味著可以保有較少的庫存和或完成運作計劃的把握更大。為鼓勵供應(yīng)商選擇最理想的運輸服務(wù)，進而降低成本，買方惟一能采取的行動就是：購買。買方的做法就是將采購訂單轉(zhuǎn)給能提供更優(yōu)質(zhì)運輸服務(wù)的供應(yīng)商。業(yè)務(wù)的擴大將帶來利潤的增加，彌補由于選擇快速運輸服務(wù)帶來的成本，因而鼓勵供應(yīng)商尋求吸引買方的運輸服務(wù)形式，而不是單純降低運輸服務(wù)的價格。11第11頁/共97頁如果分撥渠道中有多個供應(yīng)點可供選擇，運輸服務(wù)的選擇就會成為供應(yīng)商和買方的聯(lián)合決策。供應(yīng)商通過選擇運輸方式來爭取買方的訂單，理智的買方則會通過更多地購買來回應(yīng)供應(yīng)商的選擇。買方增加購買的數(shù)量取決于互相競爭的供應(yīng)商提供運輸服務(wù)的差異。在動態(tài)的競爭環(huán)境下，只提供單一運輸服務(wù)的供應(yīng)商是很難生存的，因為其他供應(yīng)商會通過提供更多的服務(wù)來反擊競爭對手，且運輸服務(wù)的選擇與買方潛在的購買興趣之間的關(guān)系是很難估量的。12第12頁/共97頁下面舉一個簡單的例子，其中假定競爭對手在服務(wù)方面沒有反擊手段，且由于供應(yīng)商提供的運輸服務(wù)較有吸引力，購買量的增加額是已知的。(見資料7.2)資料7．2例子

位于匹茲堡的一家設(shè)備制造商需要從兩個供應(yīng)商那里購買3000箱塑料配件，每箱配件的價格是100美元。目前，從兩個供應(yīng)商采購的數(shù)量是一樣的。兩個供應(yīng)商都采用鐵路運輸方式，平均運送時間也相同。但如果其中一個供應(yīng)商能將平均交付時間縮短，那么每縮短一天，制造商會將采購訂單的5％(即150箱)轉(zhuǎn)給這個供應(yīng)商。如果不考慮運輸成本，供應(yīng)商每賣出一箱配件可以獲得20％的利潤。供應(yīng)商A正在考慮如果將鐵路運輸方式改為航空或卡車運輸，是否可以獲得更多的收益。各種運輸方式下每箱配件的運輸費率和平均運送時間已知如下：13第13頁/共97頁14供應(yīng)商A僅根據(jù)可能得到的潛在利潤進行選擇。表7—2從供應(yīng)商A的角度列出了不同運輸方式下可獲得的利潤。如果該設(shè)備制造商能夠恪守承諾，供應(yīng)商A應(yīng)該轉(zhuǎn)而采用卡車運輸。當然，供應(yīng)商A應(yīng)該注意供應(yīng)商B可能采取的任何反擊手段，一旦對手采取相應(yīng)措施可能會導(dǎo)致優(yōu)勢消失。第14頁/共97頁9.1.3對選擇方法的評價在考慮運輸服務(wù)的直接成本

的同時，有必要考慮運輸方式對庫存成本和運輸績效對物流渠道成員購買選擇的影響。除此之外，還有其他一些因素需要考慮.首先，如果供應(yīng)商和買方對彼此的成本有一定了解將會促進雙方的有效合作。其次，如果分撥渠道中有相互競爭的供應(yīng)商，買方和供應(yīng)商都應(yīng)該采取合理的行動來平衡運輸成本和運輸服務(wù)，以獲得最佳收益。當然，無法保證各方都會理智行事。第三，這里沒有考慮對價格的影響。假如供應(yīng)商提供的運輸服務(wù)優(yōu)于競爭對手，他或她很可能會提高產(chǎn)品的價格來補償增加的成本。因此，買方在決定是否購買的同時應(yīng)考慮產(chǎn)品價格和運輸績效。第四，運輸費率、產(chǎn)品種類、庫存成本的變化和競爭對手可能采取的反擊措施都增加了問題的動態(tài)因素，在此并沒有直接涉及。第五，這里沒有考慮運輸方式的選擇對供應(yīng)商存貨的間接作用。15第15頁/共97頁7.2路線選擇思考：為什么要把路線選擇作為討論議題？由于在整個物流成本中運輸成本占1／3—2／3，因而最大化地利用運輸設(shè)備和人員，提高運作效率是我們關(guān)注的首要問題。最常見的決策問題就是，找到運輸工具在公路網(wǎng)、鐵路線、水運航道和航空線運行的最佳路線以盡可能地縮短運輸時間或運輸距離，從而在降低運輸成本的同時改善客戶服務(wù)。16第16頁/共97頁盡管路線選擇問題種類繁多，但我們可以將其歸為幾個基本類型：

一是起訖點不同的單一路徑規(guī)劃；

二是多個起訖點的路徑規(guī)劃；

三是起點和終點相同的路徑規(guī)劃。17第17頁/共97頁7.2.1起訖點不同的單—路徑問題這類運輸路徑規(guī)劃問題可以通過特別設(shè)計的方法很好地加以解決。最簡單、最直接的方法就是最短路徑法(ShortestRouteMethod)。該方法描述如下：已知一個由鏈和節(jié)點組成的網(wǎng)絡(luò)，其中節(jié)點代表由鏈連接的點，鏈代表節(jié)點之間的成本(距離、時間或距離和時間的加權(quán)平均)。最初，所有的節(jié)點都是未知解；也就是說，沒有通過各個節(jié)點的明確的路線，已解的節(jié)點已知經(jīng)過路線的點，開始時只有起點是已解的節(jié)點。盡管以上過程看起來有些復(fù)雜，但舉一個例子就可以發(fā)現(xiàn)它其實很簡單(見資料7.3)。也可以用網(wǎng)上的地圖和駕車里程軟件，如Mapquest解決這一問題。如果數(shù)據(jù)量增多，無法手工計算可以用LOGWARE中的ROUTE解決該問題。18第18頁/共97頁資料7.3例子問題如圖7-2所示，我們要找到得克薩斯州的阿馬里洛與沃思堡之間行車時間最短的路線。節(jié)點之間的每條路線上都標有相應(yīng)的行車時間，節(jié)點代表公路的連接處。19第19頁/共97頁20我們首先列出一張如表7-3所示的表格。第一個已解的節(jié)點就是起點或點A。與A點直接連接的未解的節(jié)點有B、c和D點。第一步，我們可以看到B點是距A最近的節(jié)點，記為AB。由于B點是惟一選擇，所經(jīng)它成為已解的節(jié)點。第20頁/共97頁21第21頁/共97頁隨后，找出距A點和B點最近的未解的節(jié)點。列出距各個已解的節(jié)點最近的連接點，我們有A-C和B-C。記為第二步。注意從起點通過已解的節(jié)點到某一節(jié)點所需的時間應(yīng)該等于到達這個已解節(jié)點的最短時間加上已解節(jié)點與未解節(jié)點之間的時間。也就是說，從A點經(jīng)B點到達C點所需的總時間是AB+BC，即(90+66)分鐘=156分鐘。比較到達未解節(jié)點的總時間，最短時間是從A點到C點的138分鐘，這樣C點就成為已解節(jié)點。第三次迭代要找到與各已解節(jié)點直接連接的最近的未解節(jié)點。如表7-4所示，有三個候選點，從起點到這三個候選點的總時間分別是348分鐘、174分鐘和228分鐘。最短時間是產(chǎn)生在BE上，因此正點就是第三次迭代的結(jié)果。22第22頁/共97頁重復(fù)上述過程直到到達終點J，即第八步。最短路徑的時間是384分鐘，連接各段路徑，得到的最佳路徑為A-B-E-I-J，這些路徑在表中加①表示。23第23頁/共97頁最短路徑法非常適合利用計算機進行求解。把網(wǎng)絡(luò)中鏈和節(jié)點的資料都存人數(shù)據(jù)庫中，選好某個起點和終點后，計算機可以很快就能算出最短路徑。絕對的最短距離路徑并不說明穿越網(wǎng)絡(luò)的最短時間，因為該方法沒有考慮各條路線的運行質(zhì)量。因此，對運行時間和距離都設(shè)定權(quán)數(shù)就可以得出比較具有實際意義的路線。(見資料7.4)24第24頁/共97頁資料7.4應(yīng)用PC*Miler和COMPUMAP是兩種商用軟件，可用來在網(wǎng)絡(luò)中尋找最佳路徑。假定一輛卡車要從衣阿華州的阿什頓到德幕安斯(DesMoines)。路線規(guī)劃的目標就是找到最短的可行路徑(時間與距離的混合)PC*Miler得出的報告如圖7—3所示，地圖見圖7-4。25第25頁/共97頁26第26頁/共97頁27第27頁/共97頁這里，司機可以得到非常具體的指令，包括經(jīng)過的確切道路；在各交叉路口走哪條路；各段行程的距離，每條路上預(yù)計行駛時間等。在本例中，可行線路233英里長，預(yù)計行駛5小時33分鐘。這些軟件除找出最短路徑外，還給出各州的過路費、最新的道路施工情況，報告燃油稅、GPS定位和在各州的行駛里程。這些拓展功能減少了費率爭議、罰款，提高了監(jiān)管效率，進而提高客戶服務(wù)水平，改進配送報告情況、資產(chǎn)利用率和司機隊伍的穩(wěn)定性。28第28頁/共97頁找到最短路徑的一種最新方法就是螞蟻的集體行動法，該方法俗稱“昆蟲智慧”，觀察在自我組織、監(jiān)督、工作不多的情況下，一群螞蟻之間的信息交流幫助它們找到復(fù)雜路徑問題的最佳解，利用放置、跟蹤化學(xué)物質(zhì)的方法觀測螞蟻是如何工作找到通往食物源的最短路徑的。很簡單，兩只螞蟻在同樣的時間離開洞穴，沿不同的路線到達食物源，沿途會留下信息素(某種吸引螞蟻的化學(xué)物質(zhì))。走最短路徑的螞蟻會先回到洞穴，這條從洞穴到食物，再返回洞穴的路線與第二只螞蟻的路線相比有雙倍的化學(xué)氣味?；氐蕉囱ǖ奈浵伨蜁蛔顝娏业臍馕端ｋS著更多的螞蟻走上這條路，就會有更多的信息素留在路上，強化了最短路徑。路線的選擇決定于兩個基本規(guī)則：留下信息素和跟蹤別人的路線。從昆蟲智慧中總結(jié)出來的原則已經(jīng)被用于解決電信、航空貨物運輸和卡車運輸?shù)穆窂絾栴}。29第29頁/共97頁7.2.2多起訖點問題如果有多個貨源地可以服務(wù)多個目的地，那么我們面臨的問題是：指定各目的地的供貨地，同時要找到供貨地、目的地之間的最佳路徑。該問題經(jīng)常發(fā)生在多個供應(yīng)商、工廠或倉庫服務(wù)于多個客戶的情況下。如果各供貨地能夠滿足的需求數(shù)量有限，則問題會更復(fù)雜。解決這類問題常?？梢赃\用一類特殊的線性規(guī)劃算法，就是所謂的運輸方法。(見資料7．5)30第30頁/共97頁資料7.5例子某玻璃制造商與三個位于不同地點的純堿供應(yīng)商簽訂合同，由它們供貨給三個工廠，·條件是不超過合同所定的數(shù)量，但必須滿足生產(chǎn)需求。圖7—5是該問題的圖示，其中還指明了各運輸線路上每噸貨物的運輸費率。這些費率是每個供應(yīng)商到每個工廠之間最短路徑的運輸費率。供求都以噸為單位進行計算。在解決這類問題時常常使用一種特殊的線性規(guī)劃算法，稱為運輸法(Tnmsportationmethod)。31第31頁/共97頁32第32頁/共97頁利用計算機軟件TRAMLP可以解決這個問題，輸出結(jié)果如下：33對該結(jié)果的解釋如下：

貨運計劃

從供應(yīng)商A運輸400噸到工廠1。

從供應(yīng)商B運輸200噸到工廠1。

從供應(yīng)商B運輸200噸到工廠2。

從供應(yīng)商B運輸300噸到工廠3。

從供應(yīng)商C運輸300噸到工廠2。該運行線路計劃的成本最低，為6600美元。第33頁/共97頁7.2.3起訖點重合的問題物流管理人員經(jīng)常會遇到起訖點相同的路徑規(guī)劃問題。在企業(yè)自己擁有運輸工具時，該問題是相當普遍的。我們熟悉的例子有：34配送飲料到酒吧和飯店安排時間和線路將現(xiàn)鈔送到自動提款機動態(tài)采購和運輸燃油問題收集飯店的油脂家用商品的維修、服務(wù)和配送網(wǎng)上雜貨店的配送取牛奶和送牛奶收集來自各家各戶的捐贈品臨時衛(wèi)生間的安放、收回和服務(wù)監(jiān)獄和法庭之間犯人的運送問題

沿鐵路線動物尸體和生病動物的搜集掃雪機和掃雪路線從醫(yī)院到實驗室運送實驗樣本用箱式車和出租車運送殘疾人垃圾收集和轉(zhuǎn)運從倉庫到零售點的配送郵車的配送路線校車路線送報路線送餐車路線第34頁/共97頁這類路徑問題是起訖點不同問題的擴展形式，但是由于要求車輛必須返回起點行程才結(jié)束，問題的難度提高了。我們的目標是找出途經(jīng)點的順序，使其滿足必須經(jīng)過所有點且總出行時間或總距離最短的要求。起訖點重合的路徑問題一般被稱為“流動推銷員”問題，人們已提出不少方法來解決這類問題。如果某個問題中包含很多個點，要找到最優(yōu)路徑是不切實際的，因為許多現(xiàn)實問題的規(guī)模太大，即使用最快的計算機進行計算，求最優(yōu)解的時間也非常長。感知式和啟發(fā)式求解法是求解這類問題的好辦法。(見資料7.6)35第35頁/共97頁資料7.6應(yīng)用中央谷學(xué)區(qū)(theCentralValleySchoolDistrict)靠近華盛頓斯波坎(Spokane)。他們首先應(yīng)用技術(shù)管理信息系統(tǒng)制訂每天校車行車計劃，和以前的方法相比，所費時間和成本都非常少。多年來，學(xué)區(qū)都使用紙介的地圖，也許用塑料的幻燈片和彩筆來設(shè)計校車路線。每個學(xué)生的家庭住址都會用手工方式標記在紙制的地圖上。管理人員借助自己的判斷，將鄰近的學(xué)生組合在一起，標出接送點，為學(xué)區(qū)的學(xué)生安排出250多輛的校車路線。在使用定制的軟件后，學(xué)區(qū)管理人員不必再用一周的時間制訂計劃，上報給州政府，而且將線路減為5-9條，又節(jié)約了12.5萬美元。36第36頁/共97頁1．各點空間相連37實際生活中，可以利用人類認知能力的模式可以很好地解決“流動推銷員”問題。我們知道，合理的經(jīng)停路線中各條線路之間是不交叉的，并且只要有可能路徑就會呈凸形，或水滴狀。圖7—6舉例說明了合理和不合理的路徑設(shè)計。根據(jù)這兩條原則，分析員可以很快畫出路線規(guī)劃圖，而計算機可能要花許多個小時才能得出。第37頁/共97頁38另外，也可以使用計算機模型來尋找送貨途中經(jīng)停的順序。如果各停車點之間的空間關(guān)系并不代表實際的運行時間或距離，那么利用計算機模型比采用感知法好。當途中有關(guān)卡、單行線或交通擁堵時，尤其如此，盡可能明確各點的地理位置(如使用坐標點)能夠減少需要采集的數(shù)據(jù)量，從而簡化問題。然而，一個簡單的問題可能需要上千個距離或時間的數(shù)據(jù)。計算機的任務(wù)就是估計這些距離或時間。目前人們已開發(fā)出的計算機程序可以迅速解決空間位置的描述問題，并得到接近最優(yōu)解的結(jié)果。(見資料7．7)第38頁/共97頁資料7.7例子39安休瑟—布喜公司(Anheuser-BushCompany)利用售貨員通過流動卡車銷售啤酒和其他飲料，卡車由當?shù)亟?jīng)銷人員所有。公司售貨員同當?shù)亟?jīng)銷人員一樣都收取傭金，因而都不希望每天向各客戶提供服務(wù)時花費不必要的時間，行走多余的路程。他們將圖釘固定在地圖上以確定某推銷員現(xiàn)有客戶的位置。圖7-7a所舉的是一個20個客戶的例子．客戶點的信息已經(jīng)被轉(zhuǎn)換到網(wǎng)格地圖上，圖中的坐標與距離相關(guān)。我們的問題是找出卡車從倉庫出發(fā)，經(jīng)過所有的客戶點，再回到倉庫，這個運行過程中的最短路徑。你可以試試感知法，將所得出的解與軟件ROUTE的計算結(jié)果(見圖7-7b)相比較。整個行程的總成本為37.59距離單位。這是一個很好的解，但不一定是最優(yōu)的。第39頁/共97頁40第40頁/共97頁41第41頁/共97頁2．空間上不相連點的問題42如果無論是將行程中的各經(jīng)停點繪制在地圖上還是確定其坐標位置，都難以確立各點之間的空間關(guān)系，或者，如果各點之間的空間關(guān)系由于前文所提到的實際原因而被扭曲，就應(yīng)該具體說明每對點之間的確切距離或時間。這里，感知法基本上不適用，我們必須借助多年來人們提出的各種數(shù)學(xué)方法來解決這類問題。雖然我們可以得到我們想要的各點間的準確距離或運行時間，但計算程序一般給出的是近似結(jié)果。(見資料7．8)第42頁/共97頁43資料7.8例子

圖7-8是一個以某倉庫為基地，包括四個經(jīng)停站點的小型配送問題。要得到點與點之間的運行時間，首先要選擇最合適的路徑，然后乘以運行速度就可以算出經(jīng)過該距離所需的時間。這里假定每對站點之間往返雙向的運行時間是一樣的。

利用STORM“流動推銷員”模塊可以得

圖7-8以分鐘為單位的運行時間的配送問題舉例到整個行程經(jīng)過站點的順序W—D—C—B—A—W，全程的總運行時間是156分鐘。第43頁/共97頁7.3行車路線和時刻表的制定行車路線和時刻表的制定問題是運輸路徑問題的擴展形式。其中更接近實際的限制條件包括：441)在每個站點既要取一定量的貨，又要送一定量的貨；2)使用多部車輛，每部車的載貨重量和容積不同；3)司機的總駕駛時間達到一定上限時，就必須休息至少8小時(運輸部門的安全限制)；4)每個站點每天只允許在特定的時間內(nèi)取貨和／或送貨(稱為時間窗口(TimeWindows))；5)途中只有在送貨后才能取貨；6)允許駕駛員每天在特定的時間休息和用餐。第44頁/共97頁這些限制條件增加了問題的復(fù)雜性，也使我們尋找最優(yōu)解的努力受挫。但是，運用制定合理路線和時刻表的原則或啟發(fā)式求解法仍然可以得到該類問題比較好的解。我們要討論的路線和時刻表問題是針對有多輛卡車從倉庫出發(fā)，送貨到若干個站點，然后在當天返回倉庫這種情況的。45第45頁/共97頁7.3.1合理路線和時刻表的制定原則運用八條原則，經(jīng)過一番努力，決策者(如車輛調(diào)度員)可以制定出合理行車路線和時刻表。這八條原則簡述如下：46(1)安排車輛負責(zé)相互距離最接近的站點的貨物運輸。第46頁/共97頁47Da)不合理的劃分方式第47頁/共97頁48江西師范大學(xué)商學(xué)院企業(yè)物流管理48Db)合理的劃分方式第48頁/共97頁49(2)

安排車輛各日的途經(jīng)站點時，應(yīng)注意使站點群更加緊湊。如果一周內(nèi)各日服務(wù)的站點不同，就應(yīng)該對一周內(nèi)每天的路線和時刻表問題分別劃分站點群。各日站點群的劃分應(yīng)避免重疊。這樣可以使為所有站點提供服務(wù)所需的車輛數(shù)降至最低，同時使一周內(nèi)卡車運行的時間和距離最少。圖7-10舉例說明了好、壞劃分方式。第49頁/共97頁50第50頁/共97頁(3)從距倉庫最遠的站點開始設(shè)計路線。51要設(shè)計出有效的路線，首先要劃分出距倉庫最遠的站點周圍的站點群，然后逐步找出倉庫附近的站點群。一旦確定了最遠的站點．就應(yīng)該選定距該核心站點最近的一些站點形成站點群，分派載貨能力能滿足該站點群需要的卡車。然后，從還沒有分派車輛的其他站點中找出距倉庫最遠的站點，分派另一車輛。如此往復(fù)，直到所有的站點都分派有車輛。第51頁/共97頁(4)卡車的行車路線應(yīng)呈水滴狀。52安排行車路線時各條線路之間應(yīng)該沒有交叉，且呈水滴狀。時間窗口和送貨之后才能取貨的限制條件可能會造成線路交叉。第52頁/共97頁(5)盡可能選用最大的車輛送貨，這樣設(shè)計出的路線是最有效的。53理想狀況下，用一輛足夠大的卡車運送所有站點的貨物將使總的行車距離或時間最小。因此，在車輛可以實現(xiàn)較高的利用率時，應(yīng)該首先安排車隊中載重量最大的車。第53頁/共97頁(6)取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨。54應(yīng)該盡可能在送貨過程中安排取貨以減少線路交叉的次數(shù)(如果在完成所有送貨任務(wù)之后再取貨，就會出現(xiàn)線路交叉的情況)。線路交叉的程度取決于車輛的結(jié)構(gòu)、取貨數(shù)量和貨物堆放對車輛裝卸的影響程度。第54頁/共97頁(7)對過于遙遠而無法歸人群落的站點，可以采用其他配送方式。55那些孤立于其他站點群的站點(特別是貨運量較小的站點)，為其提供服務(wù)所需的運送時間較長，運送費用較高?？紤]到這些站點的偏遠程度和貨運量，采用小型卡車進行服務(wù)可能更經(jīng)濟。此外，利用外租的運輸服務(wù)也不啻為一個很好的選擇。第55頁/共97頁(8)避免時間窗口過短。56各站點的時間窗口過短會使得行車路線偏離理想模式。因為時間窗口的限制常常不是絕對的，所以如果某個站點或某些站點的時間窗口限制導(dǎo)致整個路線偏離期望的模式，就應(yīng)該重新協(xié)議時間窗口的限制，最好放寬該限制。第56頁/共97頁資料7.9例子凱斯壽材公司(TheCaseCasketCompany)生產(chǎn)一系列殯葬產(chǎn)品，并向各殯儀館送貨。殯儀館會保存少量流行樣式的庫存，但顧客常常從產(chǎn)品目錄中進行選擇。通常，殯儀館的經(jīng)理會訂購棺木以補充存貨或滿足顧客的特殊要求。訂貨量常常很小，經(jīng)常一次不超過一個。為服務(wù)市場，凱斯公司在全美建了50多家配送倉庫。圖7—11列出了其中一家倉庫的位置及其服務(wù)區(qū)域，同時還列出了有代表性的一周訂貨量和訂貨點的位置。倉庫使用兩輛特制的卡車送貨，該種卡車最多可運送18副棺木，每周送貨五天。我們要做的是制定該地區(qū)的行車路線和時刻表。57第57頁/共97頁58第58頁/共97頁59根據(jù)合理路線和時刻表的制定原則，首先要將該區(qū)域劃分為五個每日的客戶群，根據(jù)原則3，我們知道，應(yīng)該從距離最遠的客戶開始劃分，然后逐步向倉庫方向靠攏，增加客戶。因此，我們將邊遠地區(qū)的站點分為四組，在一周的前四天送貨，倉庫附近的站點群成一組，在第五天送貨。我們需要對每組站點的貨運量進行平衡，以免使用兩部以上的卡車。因為在有些天，第三輛車的利用率會非常低。

我們首先從倉庫開始向外推進，尋找總訂貨量能裝滿兩卡車的站點；其次，由于底特律是個大市場，所以我們分兩天送貨。再向四面八方推進，我們就得到了送貨量大致相等的四個站點群，如圖7—12所示。第59頁/共97頁60第60頁/共97頁61下一步要做的是安排車輛裝運，設(shè)計行車線路。

每天的情況分別考慮，從最遠的站點開始，我們要在相鄰的區(qū)域內(nèi)會聚足夠多的貨以裝滿第一輛卡車。

然后，從剩余的站點中找出最遠點，重復(fù)上述過程，裝滿另一輛車。對于分派給同一輛卡車的各站點，經(jīng)過的順序應(yīng)該使得線路沒有交叉，且路徑的形狀是凸形的。一周內(nèi)每天路線設(shè)計結(jié)果如圖7-13所示。第61頁/共97頁62第62頁/共97頁7.3.2行車路線和時刻表的確定方法隨著限制條件的增加，尋找行車路線和時刻表最優(yōu)解的工作變得越來越困難。時間窗口、載重量和容積各不相同的車輛、司機途中總駕駛時間的上限要求、不同地區(qū)對速度的不同要求、途中的障礙(湖泊、迂回的道路、山脈)、司機的休息時間等都是實際路線設(shè)計中需要考慮的因素。有許多方法可以處理這類復(fù)雜的問題，我們主要介紹其中兩種方法。一種很簡單(“掃描”法)，另一種則較復(fù)雜、準確且處理能力較強(“節(jié)約”法)。其他解決方法有：(1)作圖算法；(2)二段算法；(3)不完全優(yōu)化算法；(4)改進法63第63頁/共97頁1．掃描法(TheSweepMethod)路線設(shè)計中的掃描法很簡單，即使問題規(guī)模很大，也可以通過手工計算得出結(jié)果。如果利用計算機程序計算，能夠很快求出結(jié)果，所需的計算機內(nèi)存也不大。對于各類問題，該方法的平均誤差率預(yù)計約在10％’。如果我們需要很快得出結(jié)果，且只要求結(jié)果是合理的(而不是最優(yōu)的)，那么該誤差水平還是可以接受的。該方法的缺陷與路線構(gòu)成方式有關(guān)。求解過程分為兩步：第一步是分派車輛服務(wù)的站點；第二步是決定行車路線。因為整個過程分成兩步，所以對諸如在途總運行時間和時間窗口等時間問題處理得不好。64第64頁/共97頁掃描法可闡述如下：(1)在地圖或方格圖中確定所有站點(含倉庫)的位置。(2)自倉庫始沿任一方向向外劃一條直線。沿順時針或逆時針方向旋轉(zhuǎn)該直線直到與某點相交?？紤]：如果在某線路上增加該站點，是否會超過車輛的載貨能力?如果沒有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個站點相交。再次計算累計貨運量是否超過車輛的運載能力(先使。用最大的車輛)。如果超過，就剔除最后的那個站點，并確定路線。隨后，從不包含在上一條路線中的站點開始，繼續(xù)旋轉(zhuǎn)直線以尋找新路線。繼續(xù)該過程直到所有的站點都被安排到路線中。(3)排定各路線上每個站點的順序使行車距離最短。排序時可以使用“水滴”法或求解’流動推銷員”問題的任何算法。(見資料7．10)。

65第65頁/共97頁如果：(1)每個經(jīng)停點的貨量只占車輛運力的很小比重；(2)所有車同樣大；(3)路上沒有時間限制，則“掃描”法可以得到很好的解。66第66頁/共97頁67資料7．10例子

史密斯卡車運輸公司(P．K．SmithTrickingCompany)用廂式貨車從貨主那里取貨。貨物先運回倉庫，拼車后以更大的批量進行長途運輸。圖7-14a列出了典型的一天的取貨摹，單位是件。廂式貨車的載貨量是10000件。完成所有取貨任務(wù)一般需要整整一天的時間。公司想知道需要多少條運輸路線(即多少部車)，每條路線上應(yīng)該經(jīng)過哪些站點和經(jīng)停的順序。

首先，向北畫一條直線，進行逆時針方向“掃描”。這些都是隨機決定的。逆時針旋轉(zhuǎn)該直線，直到裝載的貨物能裝上一輛載重10000件貨物的卡車，同時又不超重。一旦所有的站點都分派有車輛，就可以利用“水滴”法安排經(jīng)過各站點的順序。圖7-14b所列出的是最終的路線設(shè)計。第67頁/共97頁68第68頁/共97頁2．節(jié)約法(TheSavingsMethod)多年來，克拉克·懷特(Clarke-Wright)的節(jié)約法’一直是一種頗為出色的方法，它能夠靈活處理許多現(xiàn)實中的約束條件，對站點數(shù)量不太多的問題能較快算出結(jié)果，且結(jié)果與最優(yōu)解很接近。對僅有幾個約束條件的小型問題，比較研究顯示，利用節(jié)約法得到的結(jié)果平均只比最優(yōu)解高2％。該方法能夠處理有眾多約束條件的實際問題，主要因為它可以同時確定路線和經(jīng)過各站點的順序。69第69頁/共97頁節(jié)約法的目標是使所有車輛行駛的總里程最短，并進而使為所有站點提供服務(wù)的卡車數(shù)量最少。該方法首先假設(shè)每一個站點都有一輛虛擬的卡車提供服務(wù)，隨后返回倉庫，如圖7-15a所示。這時的路線里程是最長的。下一步，將兩個站點合并到同一條行車路線上，減少一輛運輸車，相應(yīng)地縮短路線里程。在決定哪些站點要合并到一條路線時，需要計算合并前后節(jié)約的運輸距離。由與其他任何不在同一條運輸路線上的兩點(A和B)合并所節(jié)約的距離就是圖7-15a中路線的里程減去圖7-15b中路線的里程，節(jié)約值為S=dO,A+dB,O-dAB。對每對站點都進行這樣的計算，并選擇節(jié)約距離最多的一對站點合并在一起，修訂后的路線見圖7-15b。70第70頁/共97頁71第71頁/共97頁節(jié)約法強大的處理能力使得它能夠包含實際應(yīng)用中許多重要的約束條件。該方法可以在指定各路線途經(jīng)站點的同時確定站點的先后順序。因此，在將站點歸人某條路線之前，應(yīng)該預(yù)先考查加入新站點后路線的情況。此外，還要考慮一系列有關(guān)路線規(guī)劃的問題，如行車時間是否超過允許的最長駕駛時間，是否滿足司機休息時間的要求，是否有足夠載運量的車裝載所有的貨物，各站點時間窗口的要求是否得到滿足等等。不滿足這些條件可能導(dǎo)致該站點不能并人這條路線或者說明該站點在新路線中的排列順序不當。接著就要按照最大節(jié)約值原則選取下一個站點，重復(fù)考慮上述問題。因為擴展問題的難度較大，節(jié)約法不能保證將得到最優(yōu)解，但能夠獲得合理解。(見資料7．11)72第72頁/共97頁73資料7.11例子

瑞格爾金屬公司(Re班Metals)生產(chǎn)商用樓衛(wèi)生間用的鋼制隔板。位于俄亥俄州托萊多(Toledo)的工廠(X=460。r；720)將訂單貨物累積起來每周向各建筑工地送貨一次。工廠擁有五輛載重40000磅的卡車。該公司某一周的送貨情況如下：第73頁/共97頁74第74頁/共97頁75車輛調(diào)度的原則包括：本周所有的訂貨要一次性發(fā)出；托萊多的發(fā)車時間不能早于早晨7：00；不能超過卡車的載貨能力；所有的卡車都必須返回到托萊多的工廠。其他的限制條件有：送貨時間為早晨7：00和下午6：00之間；駕駛員在中午12：00以后有一小時的午餐時間，晚上7：00以后有一整晚(12小時)的休息時間；在太湖區(qū)(GreatLakes)行車受特別限制，平均車速為每小時50英里，各站點的卸貨時間為30分鐘。據(jù)估計，公路里程要比用坐標計算的直線距離長21％。司機和卡車的成本為1．30美元／英里。如果不外出送貨，就會安排司機在廠內(nèi)工作。第75頁/共97頁76軟件ROUTER能夠處理節(jié)約法中附加的約束條件，據(jù)此作出的路線計劃見圖7—16。表7-4列出的是行車路線，表7—5列出是行車時間?？偱渌统杀緸?776英里×1.30美元／英里=7508.80美元。第76頁/共97頁77第77頁/共97頁78資料7.12應(yīng)用

達美樂比薩(Domina`sPizza)是一家擁有25億美元銷售額的全國連鎖店，以迅速將比薩送到客戶家中而聞名。但背后的物流工作卻早在他或她接到比薩之前就開始了。公司的18個配送點每周數(shù)次向4256家零售店配送新鮮的原料和補給，全年的運輸總成本高達3000萬美元，或達莢樂全公司預(yù)算的65％。為160輛卡車制訂運輸計劃是一項艱巨的工作，需要用到巨大的掛圖和無數(shù)的圖釘。這項工作每年做一次，利用手工完成，無法從日常運作角度考慮問題，也不能對變化的環(huán)境作出反應(yīng)。解讀線和別針組成的迷宮也不可能每天進行。

面對更加激烈的競爭，公司安裝了軟件來設(shè)計行車路線和時間安排，成效非常顯著。在康涅狄格配送中心(公司最大的配送中心之一)，只用兩天時間就可以繪制出主計劃，每周還減少了7000英里的行車距離，降幅達21％，車隊規(guī)模也由22部卡車減為16部。

就整個網(wǎng)絡(luò)來講，達美樂縮短100萬英里的行駛里程，每個DC平均下降至少10％。現(xiàn)在，每天制訂運輸計劃，而不是像以前那樣每年作一次。第78頁/共97頁7.3.3運輸路線的排序在利用上述行車路線和時刻表的制定方法指定路線時，假設(shè)對每條線路都只分派一部車，如果路線較短，那么在剩余的時間里這部車的利用率就很低。但在實際生活中，如果完成一條路線后開始另一條路線，那么就可以分派同一部車負責(zé)第二條路線。因此，將所有運輸路線首尾相連按順序排列，使車輛的空閑時間最短，就可以決定所需車輛數(shù)。在某行車路線問題中假設(shè)卡車的載重量都相同，行經(jīng)路線見表7-6。79第79頁/共97頁80第80頁/共97頁將這些路線在一天內(nèi)按時間進行排序，就可以使車輛的空閑時間最短，據(jù)此制定的計劃見圖7-17。按照該種方式對行車路線進行排序就能夠盡量減少服務(wù)所有線路所需的車輛數(shù)。雖然時間排序可以手工完成，但也可以編寫計算機軟件完成這項工作，并把路線選擇和時間安排問題合并在一起，為卡車運營提供完整的方案。81第81頁/共97頁82第82頁/共97頁排序問題的另一種常見形式就是對在一段特定時間內(nèi)按不同頻率配送的各點安排計劃。例如，卡車可能每周送貨或兩周送貨一次，送貨的頻率取決于客戶量，送貨到離倉庫較近的客戶會很快，卡車可以在一周內(nèi)回到倉庫并準備送另一次貨。問題產(chǎn)生了：如何在某特定周指定非每周送貨的客戶。有些客戶可以在第一周、第三周送貨，其余的在第二周、第四周送貨，仔細研究經(jīng)停地點和每周的貨運量，平衡每周的貨載，可以有助于將車隊規(guī)?？刂圃谧钚?。83第83頁/共97頁7.3.4行車路線和時刻表確定方法的應(yīng)用行車路線和時刻表的問題種類繁多，其約束條件的數(shù)量和種類也不計其數(shù)。網(wǎng)絡(luò)各站點間的零擔(dān)貨物運輸問題(如聯(lián)邦快遞、聯(lián)合包裹服務(wù)公司，或其他零擔(dān)運輸?shù)墓策\輸人所面臨的問題)就與校車或個體應(yīng)答運輸服務(wù)(如電話叫車服務(wù)Dial—A—Ride)的路徑問題大不相同。此外，在日常運作中，總會需要處理一些例外情況。研究人員在努力應(yīng)付每個行車路線和時刻表規(guī)劃問題帶來的難題時，似乎針對每個問題都需要有特別的方法來解決。即使這樣，這些方法也不能徹底解決這個問題。要想將這些方法應(yīng)用于實踐，實施時一定要小心謹慎。84第84頁/共97頁在運作環(huán)境中應(yīng)用定量分析的可行方法之一是三階段法(即預(yù)覽—求解—審核)。假設(shè)要在合理時間內(nèi)解決問題，且要求解達到一定的質(zhì)量標準，就可以建立起一個盡量切合實際問題的模型。由于那些最難以處理的內(nèi)容沒有包含在模型之中，因而常?？捎米顑?yōu)法求解。解決實際問題的過程分三步，第一步，分析人員預(yù)覽實際問題，考察有無例外情況(需要特別處理的送貨)或明顯無須求解的送貨／取貨(滿載運輸)；第二步，通常要求助于計算機，就是對簡化后的問題求解并將結(jié)果呈送分析人員；第三步，分析人員對數(shù)學(xué)求解的結(jié)果進行審核，根據(jù)實際情況對結(jié)果加以修正。(見資料7.13)85第85頁/共97頁86資料7．13應(yīng)用

某大型石油公司為加油站提供配送服務(wù)，這些加油站需要某一等級或多個等級的燃油。公司利用特別設(shè)計的帶隔斷的油罐車負責(zé)配送，不同油罐車的設(shè)計不同，可用來裝運不同數(shù)量、不同等級的燃油。當?shù)嘏渌椭行牡恼{(diào)度員每天都會接到本服務(wù)區(qū)內(nèi)加油站的訂單，但訂貨量和訂貨地點總在變化。

該公司開發(fā)了一個整數(shù)規(guī)劃模型來對20-50個站點的行車路線進行一次性計劃。設(shè)計該模型是為了處理最常見的問題，計算時需要從通用數(shù)據(jù)庫中獲取公路距離、行車時間、現(xiàn)有油罐車和司機等數(shù)據(jù)，但該模型不能處理所有錯綜復(fù)雜的每日路線安排問題。

調(diào)度員不能完全依賴這個模型，因為它不可能在所有情況下都設(shè)計出合理的路線。首先調(diào)度員要查看每天的訂單，找出有特別送貨要求和例外情況的訂單，包括緊急送貨、整車運輸和不能與常規(guī)產(chǎn)品混裝的特殊產(chǎn)品。上述情況都要由人工設(shè)計配送路線，其余的則交給計算機模型去處理。盡管計算機模型能保證求出路徑問題數(shù)學(xué)上的最優(yōu)解，但調(diào)度員只是把它作為實際問題的指導(dǎo)解，還需要進一步審核解的合理性。出于某些原因，比如遵守工會規(guī)定、途中臨時繞行和晚到的訂單等，還需要對行車時間表做一些調(diào)整。因此，調(diào)度員要和計算機一起，花費合理的時間和精力，找出一個能既令客戶滿意，又能實現(xiàn)成本最小化目標的合理的行車時間表。第86頁/共97頁7.4船舶航線和船期計劃這類問題的特點是在滿足不同港口約定裝卸日期的條件下，盡量減少所需的船舶數(shù)量。假設(shè)始發(fā)港和目的港之間的運力充足，各港口間的航行時間已知，可以利用線性規(guī)劃中的運輸問題來處理此類難題。(見資料7．14)87第87頁/共97頁88資料7．14例子

某歐洲煉油企業(yè)沿歐洲海岸線有三個煉油廠(DI，D：和D3)，所用原油來自中東的兩個港口(i：和6：)。裝貨港和卸貨港之間采用油輪運輸原油。以天數(shù)計算的港口間航行時間加裝卸時間由以下矩陣列出：為簡化問題，假定港口間的航行時間與航行方向無關(guān)，且裝卸時間相等，根據(jù)以后兩個月的需求情況，煉油廠要求貨物在下列時間運到(從現(xiàn)在開始起計)：第88頁