冷鏈?zhǔn)称愤\(yùn)輸路線優(yōu)化.doc

1、冷鏈?zhǔn)称愤\(yùn)輸路線優(yōu)化物流 072 班組員：粱利英（ 200700709075）、蘇鳳美（ 200700709071）、周冬梅（ 200700709063）、梁小杰（ 200700709078）、藍(lán)冬菊（ 200700709060）、張欣欣（ 200700709080）、周群 (200700709058 ）、鐘玲 (200700709047)1摘要食品工業(yè)要發(fā)展， 速凍食品是一條必經(jīng)之路。 冷鏈?zhǔn)称芬话愣x為適應(yīng)于 0-4 保存的食品， 冷鏈?zhǔn)称肪哂幸赘?易變質(zhì)的特性。 與一般食品相比較， 冷藏食品運(yùn)輸?shù)奶攸c(diǎn)是運(yùn)輸裝備的特殊性， 即用冷藏設(shè)備進(jìn)行運(yùn)輸： 運(yùn)輸時(shí)效性， 即在冷藏食品保質(zhì)期內(nèi)送達(dá)，

2、 時(shí)效性對(duì)于冷藏食品運(yùn)輸更為重要。 如何在規(guī)定時(shí)間內(nèi)， 以最低成本運(yùn)達(dá)冷藏食品，是冷藏食品運(yùn)輸中要考慮的關(guān)鍵問(wèn)題。 運(yùn)輸成本主要取決于運(yùn)輸路線，因此確定冷藏食品運(yùn)輸?shù)淖顑?yōu)路線是冷藏食品運(yùn)輸決策要考慮的主要問(wèn)題之一。近年來(lái)，物流配送車(chē)輛路徑問(wèn)題的研究已經(jīng)引起了人們的廣泛關(guān)注，但對(duì)于冷藏食品的運(yùn)輸路線優(yōu)化的研究還不多見(jiàn)。 本文根據(jù)冷藏食品運(yùn)輸特性， 以物流運(yùn)營(yíng)商運(yùn)成本最低為目標(biāo)， 考慮超出客戶時(shí)間窗的懲罰成本， 建立了冷藏食品運(yùn)輸路線優(yōu)化模型。 在路線優(yōu)化方面，通過(guò)建立節(jié)約里程模型找出運(yùn)輸?shù)淖罴崖窂剑?從而節(jié)約運(yùn)輸里程、運(yùn)達(dá)時(shí)間，最終降低運(yùn)輸成本。關(guān)鍵詞：冷藏食品運(yùn)輸路線優(yōu)化模型2目錄摘要 .2目

3、錄 .3一、背景介紹.41.1中國(guó)食品冷鏈發(fā)展?fàn)顩r .41.2我國(guó)冷鏈物流運(yùn)輸現(xiàn)狀評(píng)價(jià) .41.3我國(guó)冷凍冷藏食品市場(chǎng)和冷藏鏈物流發(fā)展 .4二、冷藏食品運(yùn)輸路線優(yōu)化模型的建立 .52.1模型建立的基本思路 .52.2目標(biāo)函數(shù)的建立 .52.2.1運(yùn)輸成本 .52.2.2懲罰成本。 .62.2.3冷藏食品運(yùn)輸線路優(yōu)化模型 .6三、模型算法.73.1算法計(jì)算的基本思路 .73.2求解步驟 .8四、算例分析.94.1確定第一條最優(yōu)運(yùn)輸路線 .104.2具體計(jì)算過(guò)程： .114.2.1節(jié)約運(yùn)輸成本的求法步驟： .114.2.2懲罰成本的求法： .124.2.3節(jié)約總成本 .124.3確定第二條最優(yōu)運(yùn)輸

4、路線 .124.4確定第三條最優(yōu)運(yùn)輸路線 .134.5確定第四條最優(yōu)運(yùn)輸路線 .14五、結(jié)論 .14【參考文獻(xiàn)】.153一、背景介紹1.1 中國(guó)食品冷鏈發(fā)展?fàn)顩r中國(guó)食品冷鏈的發(fā)展歷程：冷鏈起源于19 世紀(jì)上半葉冷凍機(jī)的發(fā)明，到了電冰箱的出現(xiàn)，各種保鮮和冷凍食品開(kāi)始進(jìn)入市場(chǎng)和消費(fèi)者家庭。到 20 世紀(jì) 30 年代，歐洲和美國(guó)的食品冷鏈體系已經(jīng)初步建立。40 年代，歐洲的冷鏈在二戰(zhàn)中被摧毀，但戰(zhàn)后又很快重建。現(xiàn)在歐美發(fā)達(dá)國(guó)家已形成了完整的食品冷鏈體系。新中國(guó)的冷鏈最早產(chǎn)生于50 年代的肉食品外貿(mào)出口，并改裝了一部分保溫車(chē)輛。1982年，中國(guó)頒布 “食品衛(wèi)生法 ”，從而推動(dòng)了食品冷鏈的發(fā)展起步。近2

5、0 年來(lái)，中國(guó)的食品冷鏈不斷發(fā)展，以一些食品加工行業(yè)的龍頭企業(yè)為先導(dǎo)， 已經(jīng)不同程度地建立了以自身產(chǎn)品為核心的食品冷鏈體系，包括速凍食品行業(yè)，肉食品加工企業(yè)， 冰淇淋和奶制品企業(yè)和大型快餐連鎖企業(yè)，還有一些食品類外貿(mào)出口企業(yè)。1.2 我國(guó)冷鏈物流運(yùn)輸現(xiàn)狀評(píng)價(jià)隨著城鄉(xiāng)居民生活水平的提高和人們消費(fèi)習(xí)慣的改變，以水產(chǎn)品、 畜產(chǎn)品、 果蔬及花卉為代表的冷鏈物流日漸趨熱，成為人們關(guān)注的焦點(diǎn)。所謂冷鏈物流泛指冷藏冷凍類食品在生產(chǎn)、貯藏運(yùn)輸、 銷售， 到消費(fèi)前的各個(gè)環(huán)節(jié)中始終處于規(guī)定的低溫環(huán)境下，以保證食品質(zhì)量，減少食品損耗的一項(xiàng)系統(tǒng)工程。它是隨著科學(xué)技術(shù)的進(jìn)步、 制冷技術(shù)的發(fā)展而建立起來(lái)的，是以冷凍工藝學(xué)

6、為基礎(chǔ)、以制冷技術(shù)為手段的低溫物流過(guò)程。冷鏈物流的適用范圍包括初級(jí)農(nóng)產(chǎn)品：蔬菜、水果；肉、禽、蛋；水產(chǎn)品、花卉產(chǎn)品。加工食品：速凍食品、禽、肉、水產(chǎn)等包裝熟食、冰淇淋和奶制品；快餐原料。特殊商品：藥品。由于食品冷鏈?zhǔn)且员ＷC易腐食品品質(zhì)為目的，以保持低溫環(huán)境為核心要求的供應(yīng)鏈系統(tǒng)，所以它比一般常溫物流系統(tǒng)的要求更高、更復(fù)雜，建設(shè)投資也要大很多，是一個(gè)龐大的系統(tǒng)工程。業(yè)內(nèi)人士指出，目前，我國(guó)的冷藏物流業(yè)尚處于初級(jí)階段，市場(chǎng)規(guī)模不大，區(qū)域性特征比較強(qiáng)， 缺乏有影響力的、全國(guó)性的第三方冷藏物流行業(yè)領(lǐng)袖。從全國(guó)范圍來(lái)看，原有冷藏鏈設(shè)施一般自成系統(tǒng)、時(shí)有斷裂、不能連網(wǎng)、 效率低下， 距離構(gòu)建現(xiàn)代化低溫物流

7、體系差距甚大。1.3我國(guó)冷凍冷藏食品市場(chǎng)和冷藏鏈物流發(fā)展我國(guó)凍制食品自20 世紀(jì)六十年代開(kāi)始出現(xiàn)，主要是凍肉、凍禽和凍水產(chǎn)品，為保障市場(chǎng)供應(yīng)， 調(diào)節(jié)淡旺季與全國(guó)計(jì)劃調(diào)運(yùn)，國(guó)內(nèi)主要產(chǎn)地與大城市興建了一批大型冷庫(kù)，并由鐵路冷藏車(chē)和水運(yùn)冷藏船相聯(lián)，形成了凍制品產(chǎn)地冷藏貨車(chē)?yán)鋷?kù)市場(chǎng)之間的網(wǎng)絡(luò)。這種以食品原料冷凍、貯存和運(yùn)輸為目的的初級(jí)凍制品冷藏鏈，在較長(zhǎng)時(shí)間內(nèi)，對(duì)保障國(guó)內(nèi)副食品供應(yīng)及出口貿(mào)易起了重要作用。隨著我國(guó)加入WTO ，如何運(yùn)用現(xiàn)代科學(xué)技術(shù)，成功開(kāi)發(fā)各種冷凍冷藏溫度帶食品，建設(shè)完善可靠、 規(guī)范管理的食品冷藏鏈并提高社會(huì)公用化程度，全面提升我國(guó)食品安全與品質(zhì)，充分利用食品資源， 減少易腐食品損失，

8、 加快農(nóng)產(chǎn)品深加工， 適應(yīng)國(guó)內(nèi)外市場(chǎng)需求，是冷凍食品產(chǎn)業(yè)與冷藏鏈設(shè)備制造業(yè)及相關(guān)產(chǎn)業(yè)共同面臨的新課題。4二、冷藏食品運(yùn)輸路線優(yōu)化模型的建立2.1模型建立的基本思路定義路網(wǎng)G=（ V,A ） ,其中， V= v0 ， v1 ， ， vn 為點(diǎn)的集合， A= vi ， v j ： vi ，v j V,i j為路段集合， v0代表冷藏食品運(yùn)輸中心，vi （ i=1,2, ， n）代表所服務(wù)的第 i 個(gè)客戶，客戶 i 的需求量為wi 。運(yùn)輸中心的運(yùn)送車(chē)輛路線用l 表示，共有 m 部運(yùn)送車(chē)輛，故 l=1 ， 2， ， m）。而 Cijl為第 l 部車(chē)輛在路段（vi ， v j）上的運(yùn)輸成本，且 Cijl

9、= C jil 。顯然， i=j 時(shí)， Cijl=0.將超出客戶時(shí)間窗的懲罰成本及隨里程遞增的運(yùn)輸成本作為冷藏食品運(yùn)輸商的運(yùn)輸總成本， 以運(yùn)輸成本最小為目標(biāo)， 求解模型，以獲得最佳的運(yùn)輸路線l 0 。（忽略冷藏食品易腐性造成的貨損成本）2.2目標(biāo)函數(shù)的建立構(gòu)建模型時(shí)，將運(yùn)輸?shù)木C合成本作為目標(biāo)函數(shù)。 冷藏食品的運(yùn)輸綜合成本包括：車(chē)輛運(yùn)輸成本，以及超出客戶時(shí)間窗的懲罰成本。2.2.1運(yùn)輸成本運(yùn)輸成本包括固定成本和變動(dòng)成本， 其中固定成本為常數(shù)， 與運(yùn)輸里程及客戶數(shù)量沒(méi)有直接關(guān)系，這里只考慮運(yùn)輸車(chē)輛的變動(dòng)成本，可表示為：mnnCtr =i 1Cijl xijl（ 1）l 1j 0其中， C l=c

10、w 為第 l 部車(chē)輛在路段（vi ， vj ）上的運(yùn)輸成本，cij 為從第 i 點(diǎn)到ijij ij第 j 點(diǎn)運(yùn)送單位冷藏食品的運(yùn)費(fèi)，wij 為從第 i 點(diǎn)向第 j 點(diǎn)運(yùn)送冷藏食品的數(shù)量；xijl為 0、1 變量，若第 l 車(chē)輛行經(jīng)（ vi ， v j ）路段，則xijl=1，否則 xijl=0。52.2.2懲罰成本。時(shí)間過(guò)長(zhǎng)，冷藏食品易腐爛，故在其運(yùn)輸中對(duì)時(shí)間有嚴(yán)格的限制，即屬于有時(shí)間窗限制的運(yùn)輸問(wèn)題。 在實(shí)際運(yùn)輸中， 運(yùn)輸中心派出的運(yùn)輸車(chē)輛到達(dá)客戶的時(shí)間，有三種情況，即：（1）在要求時(shí)間窗內(nèi)運(yùn)達(dá)；（2）在要求時(shí)間窗之外，客戶可以接受范圍內(nèi)運(yùn)達(dá)；（3）延遲并超出客戶可以接受的范圍內(nèi)運(yùn)達(dá)。第一種

11、情況下運(yùn)達(dá)，可以進(jìn)行貨物交換，沒(méi)有懲罰成本。第二種情況運(yùn)達(dá)，貨物可以交接， 但需要支付相應(yīng)的懲罰成本。第三種情況下運(yùn)達(dá)， 無(wú)法完成運(yùn)輸任務(wù)，在模型中不考慮。設(shè)客戶 j 的時(shí)間窗上線為 t h ，下限為 tl ，可接受的范圍時(shí)間上限Th , Tl 。則懲罰成本表示為：t jT e , t jT hC pj (t j )0T et jt e , t et jt h（ 3） Pwj ( t jt e )t ht jT h式（ 3）中 t j 為冷藏食品運(yùn)達(dá)客戶的時(shí)間，w j 為客戶 j 的貨物數(shù)量；為懲罰系數(shù)。則總的懲罰成本為：nC pj (t j )C p =（ 4）j12.2.3冷藏食品運(yùn)輸線路

12、優(yōu)化模型以運(yùn)輸總成本最小為目標(biāo)， 受約束條件限制， 確定出冷藏食品最優(yōu)的運(yùn)輸路線。線路優(yōu)化模型為：Min FCtr C p(5)6三、模型算法上述建立的運(yùn)輸線路優(yōu)化模型為非線性規(guī)劃問(wèn)題，求解比較復(fù)雜。采用啟發(fā)性算法，簡(jiǎn)化該問(wèn)題的求解。3.1 算法計(jì)算的基本思路采用尋找最鄰客戶法，確定線路中第一位被服務(wù)的客戶。最臨近的客戶是指滿足時(shí)間窗的和車(chē)輛容量限制，并且尚未被排入任一線路的客戶。該客戶加入線路，除了滿足上述兩條件之外， 還應(yīng)該滿足加入成本最低原則，即新加入的客戶能使新增成本最低，從而保證運(yùn)輸成本最低。采用節(jié)約法求解：節(jié)約算法的核心思想是將運(yùn)輸問(wèn)題中存在的兩個(gè)回路（ 0 i,0）和（ 0 j,

13、0 ）合并成一個(gè)回路（ 0 i,j, 0），合并后整個(gè)運(yùn)輸回路的運(yùn)輸距離將發(fā)生變化， 一般優(yōu)化結(jié)果會(huì)使運(yùn)輸距離下降， 下降值稱為路線節(jié)約值。節(jié)約里程法基本原理是幾何學(xué)中三角形一邊之長(zhǎng)必定小于另外兩邊之和。節(jié)約法的目標(biāo)是使所有車(chē)輛的行駛總里程最短， 并且為所有站點(diǎn)提供服務(wù)的卡車(chē)數(shù)量最少。 該方法先假設(shè)每一個(gè)站點(diǎn)都有一輛虛擬的車(chē)輛提供服務(wù)， 隨后返回倉(cāng)庫(kù)，如圖 1-1 所示，這時(shí)的路線里程最長(zhǎng)。下一步，將兩個(gè)站點(diǎn)合并到同一條行車(chē)路線上， 減少一輛運(yùn)輸車(chē)， 相應(yīng)地縮短路線里程， 選擇節(jié)約距離最多的一對(duì)站點(diǎn)合并在一起，修訂后的路線如圖 1-2。繼續(xù)以上過(guò)程， 除了將單個(gè)站點(diǎn)合并在一起外， 還可以將某站

14、點(diǎn)并入已經(jīng)包含多個(gè)站點(diǎn)的路線上。 每次合并都要計(jì)算所節(jié)約的距離， 節(jié)約距離最多的站點(diǎn)就應(yīng)該納入現(xiàn)有路線。 假如由于某些約束條件 （如路線太長(zhǎng)， 無(wú)法滿足時(shí)間窗口的要求，或超過(guò)車(chē)輛的承載能力） ，節(jié)約距離最多的站點(diǎn)不能并入該路線，就要考慮節(jié)約距離次多的站點(diǎn)。重復(fù)該過(guò)程直到所的站點(diǎn)的路線設(shè)計(jì)完成。圖 1 節(jié)約法示意圖如圖 1 所示，假定冷藏食品運(yùn)輸中心為P0 ，P0 到客戶 Pi 和 Pj 的距離分別為 d oi 和doj ，用 Sij 表示路線節(jié)約值，則合并后節(jié)約距離為：7Sij =doi +d oj l ij（ ）7式中 l ij為客戶 Pi 到客戶 Pj 的距離。運(yùn)送車(chē)輛的運(yùn)輸成本與運(yùn)輸里程

15、成正比，故節(jié)約值Sij 越大，其成本越小。運(yùn)輸里程和客戶的貨物量?jī)蓚€(gè)因素決定了冷藏食品在運(yùn)輸途中腐爛的所造成的貨損成本。 線路優(yōu)化不改變客戶的貨物量。 因此冷藏食品的貨損成本優(yōu)化主要由運(yùn)輸里程決定。貨損成本與運(yùn)輸里程成正比。懲罰成本只與運(yùn)達(dá)時(shí)間有關(guān)，由式（ 3）計(jì)算。由此，冷藏食品運(yùn)輸線路優(yōu)化模型的目標(biāo)函數(shù)又可轉(zhuǎn)化為：nnMaxCsiji1 j1nnn=(CijQij1 PQij )SijC pj（ 8）i 1j 1j1式（ 8）中 Csij 為從客戶 i 到客戶 j 運(yùn)輸中的節(jié)約成本， Cij 為單位貨物從 i運(yùn)輸?shù)?j客戶的運(yùn)輸成本。由上，可得搜索新客戶的順序：1、時(shí)間窗先后順序。超出可接

16、受的時(shí)間窗，意味著無(wú)法完成訂單，因此必須按照時(shí)間窗為第一順序原則， 加入新客，保證所有客戶都可接受的范圍內(nèi)被服務(wù)。2、運(yùn)輸里程順序。運(yùn)輸里程直接影響運(yùn)輸成本和貨損成本，對(duì)運(yùn)輸總成本很大，作為第二順序。3.2求解步驟根據(jù)上述算法，具體求解步驟如下：（1）初始化，輸入已知的參數(shù)；（2）由配送中心開(kāi)始尋找“最鄰客戶” ，加入成為第一條路線上的第一位被服務(wù)的客戶；（3）令 i 為某一線路上最后一位加入的客戶。 重復(fù)步驟（ 2），得到下一個(gè)鄰近客戶 j 。依次加入當(dāng)前線路中。若所有尚未被排入任一路線的客戶均無(wú)法滿足時(shí)間窗限制或車(chē)輛容量限制，則重新建立一條新的路線，直到所有客戶全部排入線路為止。8四、算例

17、分析一配送中心，向10 個(gè)客戶 Pj（ j=1 ，2，10）配送酸奶。酸奶保存期限為24 小時(shí)，配送溫度為 0?？蛻舻男枨罅亢蜁r(shí)間窗見(jiàn)表1. 配送 P0 及客戶間的距離（Km）見(jiàn)表 2.運(yùn)輸任務(wù)由配送中心利用q=3t的冷藏車(chē)來(lái)完成，其他參數(shù)見(jiàn)表3。確定最佳運(yùn)輸路線。表 1 客戶貨物需求量和時(shí)間窗客戶P1P2P3P4P5P6P7P8P9P10需求量0.71.50.80.41.41.50.60.82.50.620:321:320:521:5021:0022:021:2022:423:120:00000000時(shí)間窗22:2021:3021:4021:022:021:222:423:123:420:3

18、000000020:021:020:221:2020:3021:420:4022:122:419:30000000接受時(shí)間窗22:0022:2021:0021:322:321:522:5023:123:40:2000000表 2配送中心及客戶之間的距離客戶P0P1P2P3P4P5P6P7P8P9P10P00109788834107P1100491418181314114P294051014171213158P37950591510111713P481410906710121815P581814960710121815P681817151370681715P7313121011106021110

19、P841413111212820911P91011171518181711908P1074813151515101180表 3其他參數(shù)表序號(hào)名稱符號(hào)單位數(shù)值1酸奶價(jià)格P元噸40003懲罰系數(shù)%0.24單位運(yùn)輸成本C元噸公里0.85運(yùn)輸速度V公里小時(shí)306裝卸時(shí)間H分鐘客戶2094.1 確定第一條最優(yōu)運(yùn)輸路線將客戶按時(shí)間的先后順序排列，得表4。計(jì)算每一客戶之間連接的距離節(jié)約值，見(jiàn)表5。表 4 各客戶按時(shí)間先后排序的時(shí)間窗戶客戶P10P1P3P5P7P2P4P6P8P9時(shí) 間20:0020:3020:5021:0021:2021:3021:5022:0022:4023:10窗20:3021:002

20、1:2021:3021:4022:0022:0022:4023:1023:40接 受19:3020:0020:2020:3020:4021:0021:2021:4022:1022:40時(shí) 間窗21:0021:3021:5022:0022:2022:3022:5023:1023:4000:20表 5客戶之間連接的距離節(jié)約值客戶P1P2P3P4P5P6P7P8P9P10P115840000913P215117300048P381110600001P447101030000P50361091000P6000395410P7000015520P8000004550P9940001259P1013810

21、00009按時(shí)間窗先后順序，客戶P10 要求的時(shí)間最早，因此客戶P10 為第一客戶。接下來(lái)客戶選擇見(jiàn)表6和表 7。表 6客戶選擇表 1客戶節(jié)約運(yùn)節(jié)約運(yùn)懲罰節(jié)約選擇輸里程輸成本成本總成本p1137.2807.28是p289.2否p310.64否p400否p50000否p600否p7002.4-2.4否p800否p9918否10表 7客戶選擇表 2客戶節(jié)約運(yùn)節(jié)約運(yùn)懲罰節(jié)約選擇輸里程輸成本成本總成本p12833.63.630.00是p32113.442.1111.33否p4175.440.964.48否p51314.561.8712.69否p61315.6411.6否p7136.2406.24否p8

22、117.04否p92244否4.2 具體計(jì)算過(guò)程：按時(shí)間窗先后順序，客戶P 要求的時(shí)間最早，因此客戶P 為第一客戶。接1010下來(lái)應(yīng)先算出 P10 到各個(gè)客戶之間節(jié)約運(yùn)輸里程、節(jié)約運(yùn)輸成本、懲罰成本。4.2.1節(jié)約運(yùn)輸成本的求法步驟：1、 通過(guò)節(jié)約法原理，求出每一客戶之間連接的距離節(jié)約值。2、 節(jié)約運(yùn)輸成本 =節(jié)約運(yùn)輸里程運(yùn)費(fèi)某一客戶的需求量表 5 中客戶之間連接的距離節(jié)約值是由表2 配送中心及客戶之間的距離計(jì)算可得。例如 : 表 5 中 P1 與 P2 的距離節(jié)約值=P1 到 P0 的距離 + P2 到 P0 的距離- P1 與 P2 的距離 =10+9-4=15。同理可得其它客戶之間連接的

23、距離節(jié)約值。由表 5 可知， P 與 P 的距離節(jié)約值為13 公里，由表 1 可知 P 客戶貨物需求1011量為 0.7噸，由表 3 其他參數(shù)表可知，單位運(yùn)輸成本為0.8 元噸公里，所以 P10與 P1 節(jié)約運(yùn)輸成本為 =130.7 0.8=7.28 同理可得：與 p2 節(jié)約運(yùn)輸成本 =9.2 與 p3 節(jié)約運(yùn)輸成本 =0.64與 p4 節(jié)約運(yùn)輸成本 =0與 p5節(jié)約運(yùn)輸成本 =0與 p6 節(jié)約運(yùn)輸成本 =0與 p7節(jié)約運(yùn)輸成本 =0與 p8 節(jié)約運(yùn)輸成本 =0與 p9節(jié)約運(yùn)輸成本 =18114.2.2懲罰成本的求法：假設(shè)冷藏車(chē)送到客戶 時(shí)，剛好是客戶 的時(shí)間下線，即送到客戶 的時(shí)間是 20:

24、10 ，由于裝卸時(shí)間為 20 分鐘，所以冷藏車(chē)從 20:30 從 出發(fā)；若選擇客戶 P1 ， P1 和 P10 之間的距離為7 公里，運(yùn)送速度是 30 公里小時(shí)，可算出運(yùn)送時(shí)間 t=7/30=0.24h 15 分，即冷藏車(chē)到達(dá) P1 時(shí)是 20:45 ，在 P1 的時(shí)間窗范圍內(nèi)，所以懲罰成本為 0。若選擇客戶 P2， P2和 P10之間的距離為 8 公里，可算出運(yùn)送時(shí)間 t=8/30=0.27h 17 分，即冷藏車(chē)到達(dá) P2 時(shí)是 20:47 ，不在客戶 P2 接受的時(shí)間范圍內(nèi)，即超出了客戶 P2 可接受的時(shí)間 范圍，因此懲罰成本是。同理算得 P3 、P4、 P5、 P6、 P8、 P9。若選

25、擇客戶P7，和 10 之間的距離是10公里，可算出運(yùn)送時(shí)間t=10/30=20P7P分，冷藏車(chē)到達(dá) P7時(shí)是 20:50 ，在客戶 P7 的要求時(shí)間窗之外，在客戶P7 可接受的時(shí)間范圍內(nèi)送達(dá)， 超出了要求時(shí)間 30 分鐘，此時(shí)，需要支付相應(yīng)的懲罰成本。懲罰成本 = Pw j t =0.2% 4000 0.6 (30/60)=2.4.4.2.3節(jié)約總成本節(jié)約總成本 =節(jié)約運(yùn)輸成本懲罰成本選出節(jié)約總成本最大的客戶加入路線。根據(jù)表6、表 7 分析，第一條線路上的客戶為 P 、 P 、 P ，此時(shí)運(yùn)輸車(chē)輛的載重量為Q=0.6+0.7+1.5=2.8t ，剩余的1012載重量無(wú)法滿足剩余的其他任何客戶，

26、所以第一條最優(yōu)運(yùn)輸路線是：P0- P10- P1- P2 - P0 。同樣的道理，可算得冷藏車(chē)的其他幾條最優(yōu)運(yùn)輸路線： P0 - P3 - P5 P4 - P0 、P0 - P7 - P6- P8- P0、 P0- P9 - P0 。具體內(nèi)容如下：4.3 確定第二條最優(yōu)運(yùn)輸路線在剩余的客戶中客戶P3 要求時(shí)間最早， 作為第一個(gè)客戶。 接下來(lái)客戶選擇見(jiàn)12表 8、表 9。表 8客戶選擇表 3客戶節(jié)約運(yùn)節(jié)約運(yùn)懲罰節(jié)約選擇輸里程輸成本成本總成本p4103.21.61.60否p566.7206.72是p6004-4.00否p70000.00否p800否p900否表 9客戶選擇表 4客戶節(jié)約運(yùn)節(jié)約運(yùn)懲罰

27、節(jié)約選擇輸里程輸成本成本總成本p4165.1205.12是p773.360.962.40否p863.8430.84否從表 8 中可見(jiàn)，選擇客戶 P5 ，表 9 中可見(jiàn)，選擇客戶 P4 ，此時(shí)第二條最優(yōu)運(yùn)輸路線為 P0 - P3- P5 - P4 - P0 。4.4 確定第三條最優(yōu)運(yùn)輸路線在剩余的客戶中， 客戶 P7 要求的時(shí)間最早， 客戶 P7 作為第一個(gè)客戶。 接下來(lái)客戶的選擇見(jiàn)表 10 和表 11。表 10客戶選擇表 5客戶節(jié)約運(yùn)節(jié)約運(yùn)懲罰節(jié)約選擇輸里程輸成本成本總成本p6561.564.44是p852.402.40否p921.28否表 11客戶選擇表 6客戶節(jié)約運(yùn)節(jié)約運(yùn)懲罰節(jié)約總選擇輸里程輸成本成本成本P895.7605.76是P96120.6711.33否13根據(jù)表 10 和表 11，第三條線路選擇的客戶