【正文】 取得了很大的成績，特別是利用啟發(fā)式算法和智能算法。盡管國內(nèi)學(xué)者在VRP的研究方面已經(jīng)有了一定的成果，但是總的說來還是處在起步階段。（3）對天津金雅達(dá)貨運(yùn)站進(jìn)行研究，進(jìn)行理論分析。本課題的研究步驟：（1）復(fù)習(xí)專業(yè)課基礎(chǔ)知識，收集并整理資料，對資料進(jìn)行綜合分析。參考文獻(xiàn)：[1] 陳輝，劉春草，[J].西安電子科技大學(xué)學(xué)報(bào)(社會科學(xué)版)，2006，16(5):1620[2] [M].廣州:中山大學(xué)出版社，2001[3] 丁立言，[M].北京: 清華大學(xué)出版社，2002[4] 高曉亮，伊俊敏，[M].[5] [M].[6] [M].[7] [M].北京：經(jīng)濟(jì)科學(xué)出版社，2003[8] 李繼玲，盧才武，《東北大學(xué)學(xué)報(bào)（自然科學(xué)版）》[J]，2004（1）[9] ：內(nèi)涵、特征和目標(biāo)[J]．物流技術(shù)，2007（11）：4951[10] 蔣琦瑋，[J].系統(tǒng)工程，2007，25（4）：2729[11] 李軍，[M].北京:中國物資出版社，2001[12] 孫學(xué)農(nóng)，[J].科學(xué)信息（學(xué)術(shù)研究），2007，（12）：225226[13] 鄭玲玲，[J].物流技術(shù)，2008，1:1619[14] Laporte G., Nobert Y.. Exact algorithms for the vehicle routing problem.[M].Amsterdam: [15] Dimitris J B , David S. A new generation of vehicle routing research [J]. Survey, Expository amp。通過對運(yùn)輸路徑優(yōu)化，我們可以提高企業(yè)的運(yùn)作效率，降低配送成本，實(shí)現(xiàn)物流科學(xué)化。關(guān)鍵詞：貨物運(yùn)輸 運(yùn)輸路徑 優(yōu)化TianJin JinYaDa Cargo Terminal Transportation Route Optimization ResearchABSTRACTTransportation is the main lifeline of the national economy, affecting citizens’ economic activity and life. With the rapid development of market economy, as the third profit source logistics on economic activity has bee increasingly apparent, the influence of increasingly attracted people39。而運(yùn)輸是物流的一個核心流程，物流成本的多少關(guān)系到整個物流環(huán)節(jié)運(yùn)營的優(yōu)劣。最終產(chǎn)品和中間品均承擔(dān)10%的從價(jià)運(yùn)費(fèi)，會使得生產(chǎn)國的產(chǎn)品增加值減少30%（與零運(yùn)輸成本的國家相比），如果從價(jià)運(yùn)費(fèi)增加至20%，生產(chǎn)國的產(chǎn)品增加值將減少60%，從價(jià)運(yùn)費(fèi)增加至30%，生產(chǎn)國的產(chǎn)品增加值將減少90%。而對于運(yùn)輸相關(guān)企業(yè)，提高運(yùn)輸效率是提高企業(yè)競爭力的關(guān)鍵要素。而在當(dāng)今物流發(fā)展逐漸完善的情形下，與一些高水平的企業(yè)相比，金雅達(dá)貨運(yùn)站還是有很大的發(fā)展空間，該企業(yè)的運(yùn)輸路線規(guī)劃并不是完全合理科學(xué)。因此,研究貨物運(yùn)輸系統(tǒng)中的問題對降低企業(yè)成本，提高工作效率，進(jìn)而提高企業(yè)在市場的競爭力是尤其重要的。第三章 天津金雅達(dá)貨運(yùn)站情況介紹，對天津金雅達(dá)貨運(yùn)站進(jìn)行簡單的情況介紹，列出了金雅達(dá)貨運(yùn)站的基本作業(yè)流程，站在貨運(yùn)站效益最大化的角度上通過層次分析法計(jì)算出合理安排車輛路線更加有助于提高公司效益。本文中專指“物”的載運(yùn)及輸送。 ⑵物流運(yùn)輸合理化，可以消除運(yùn)輸中的種種浪費(fèi)現(xiàn)象，提高商品運(yùn)輸質(zhì)量，充分發(fā)揮運(yùn)輸工具的效能，節(jié)約運(yùn)力和勞動力。按物流的概念，物流是“物”的物理性運(yùn)動，這種運(yùn)動不但改變了物的時(shí)間狀態(tài)，也改變了物的空間狀態(tài)。運(yùn)輸是國民經(jīng)濟(jì)的基礎(chǔ)和先行。二是，在社會上，運(yùn)輸是生產(chǎn)過程的繼續(xù)，這一活動聯(lián)結(jié)生產(chǎn)與再生產(chǎn)，生產(chǎn)與消費(fèi)的環(huán)節(jié)，聯(lián)結(jié)國民經(jīng)濟(jì)各部門、各企業(yè)，聯(lián)結(jié)著城鄉(xiāng)，聯(lián)結(jié)著不同國家和地區(qū)。通過運(yùn)輸，將“物”運(yùn)到場所效用最高的地方，就能發(fā)揮“物”的潛力，實(shí)現(xiàn)資源的優(yōu)化配置。消耗的絕對數(shù)量大，其節(jié)約的潛力也就大。 物流運(yùn)輸模式海上貨物運(yùn)輸⑴海上貨物運(yùn)輸?shù)奶攸c(diǎn)。由于商船的體積大，水流的阻力大，加之裝卸時(shí)間長等其他各種因素的影響，所以貨物的運(yùn)輸速度比其他運(yùn)輸方式慢。⑵海上貨物運(yùn)輸?shù)淖饔?。在我國運(yùn)費(fèi)支出一般占外貿(mào)進(jìn)出口總額10%左右，尤其大宗貨物的運(yùn)費(fèi)占的比重更大，貿(mào)易中假若充分利用貿(mào)易術(shù)語，爭取我方多派船，不但節(jié)省了外匯的支付，而且還可以爭取更多的外匯收入。運(yùn)輸量比較大。 運(yùn)輸耗油約是汽車運(yùn)輸?shù)亩种弧Ｕ加猛恋?，其初期投資大大超過其他運(yùn)輸方式。我國貿(mào)易進(jìn)出口貨物運(yùn)輸大多都要通過鐵路運(yùn)輸這一環(huán)節(jié)，鐵路運(yùn)輸在我國貨物運(yùn)輸中發(fā)揮著重要作用。汽車投資少、收效快、港口集散可爭分奪秒，突擊搶運(yùn)任務(wù)多。公路運(yùn)輸可以配合船舶、火車、飛機(jī)等運(yùn)輸工具完成運(yùn)輸?shù)娜^程，是港口、車站、機(jī)場集散貨物的重要手段。航空貨物運(yùn)輸運(yùn)送速度快。由于航空運(yùn)輸速度快，商品在途時(shí)間短、周期快，存貨可相對減少，資金可迅速收回。⑵航空貨物運(yùn)輸?shù)淖饔?。采用了航空運(yùn)輸，可保鮮成活，又有利于開辟遠(yuǎn)距離的市場，這是其他運(yùn)輸方式無法相比的。在運(yùn)輸企業(yè)中，表現(xiàn)為完成一定運(yùn)輸任務(wù)的勞動耗費(fèi)和勞動占用，同獲得有用成果的對比關(guān)系。從物流的角度看，貨物運(yùn)輸是現(xiàn)代物流的重要基礎(chǔ)和核心，貨物運(yùn)輸經(jīng)濟(jì)效益直接影響了物流供應(yīng)鏈的效益，貨物運(yùn)輸效益既是國民經(jīng)濟(jì)效益的組成部分，又是國民經(jīng)濟(jì)效益的重要基礎(chǔ)。降低成本，就是要以盡可能少的勞動消耗來完成盡可能多的運(yùn)輸任務(wù)；提高效率，就是要加快運(yùn)輸速度，縮短運(yùn)輸時(shí)間，擴(kuò)大運(yùn)輸規(guī)模。 我國運(yùn)輸經(jīng)濟(jì)效益狀況⑴貨物運(yùn)輸成本總體偏高。運(yùn)輸成本居高不下嚴(yán)重影響了貨物運(yùn)輸經(jīng)濟(jì)效益，也是導(dǎo)致我國物流總成本過高的主要因素。根據(jù)世界銀行官方網(wǎng)站最新公布的全球150個國家物流績效指數(shù)（LPI）的得分和排名，排名第30位[8]。從表1不難看出，我國在通關(guān)效率，基礎(chǔ)設(shè)施，國際貨運(yùn)安排，物流競爭力（如運(yùn)輸運(yùn)營商、代理商等），物流跟蹤服務(wù)，物流成本（如運(yùn)輸、場站處理、倉儲）和運(yùn)輸及時(shí)性等直接或間接反映運(yùn)輸效率的分項(xiàng)指標(biāo)得分都較低，與發(fā)達(dá)國家相比仍有較大差距[9]。 車輛路線問題分類車輛路線優(yōu)化中，根據(jù)因素是否確定，可分兩種情況:第一種為確定型路線優(yōu)化，第二種為隨機(jī)型的車輛路線優(yōu)化[1012]。當(dāng)然，在隨機(jī)型下車輛也必須從配送中心出發(fā)，完成配送任務(wù)，回到配送中心但是同一客戶的需求可以由多輛車或同一輛車多次送貨完成。金雅達(dá)貨運(yùn)站注冊資金1050萬人民幣，員工人數(shù)200余人，企業(yè)內(nèi)部有35輛貨車，公司設(shè)有業(yè)務(wù)部、運(yùn)輸部、信息技術(shù)部、財(cái)務(wù)部、人事部、客服部等多個部門。 天津金雅達(dá)貨運(yùn)站基本運(yùn)作流程貨運(yùn)站的基本作業(yè)一般包括訂單處理、進(jìn)貨作業(yè)、搬運(yùn)作業(yè)、存儲作業(yè)、揀貨作業(yè)、流通加工作業(yè)、補(bǔ)貨作業(yè)和配送作業(yè)等方面內(nèi)容，各種作業(yè)有機(jī)結(jié)合形成一個完整的流程。配送中心收到和匯總門店的訂貨單后，首先要確定配送貨物的種類和數(shù)量，然后要查詢配送中心現(xiàn)有庫存中是否有所需的現(xiàn)貨。采用一定的手段對接收的貨物進(jìn)行檢驗(yàn)，包括數(shù)量的檢驗(yàn)和質(zhì)量的檢驗(yàn)。⑶儲存。配送中心的工作人員根據(jù)信息中心打印出的要貨單上所要的商品、要貨的時(shí)間、儲存區(qū)域，以及裝車配貨要求、門店位置的不同，將貨物挑選出的一種活動。⑸配裝。⑹加工。送貨包括裝車和送貨兩項(xiàng)活動。⑻信息處理。 層次分析法是將決策問題按總目標(biāo)、各層子目標(biāo)、評價(jià)準(zhǔn)則直至具體的備選方案的順序分解為不同的層次結(jié)構(gòu)，然后得用求解判斷矩陣特征向量的辦法，求得每一層次的各元素對上一層次某元素的優(yōu)先權(quán)重，最后再加權(quán)和的方法遞階并各備選方案對總目標(biāo)的最終權(quán)重，此最終權(quán)重最大者即為最優(yōu)方案。及其所對應(yīng)的特征向量W，歸一化后，即為某一層次指標(biāo)對于上一層次某相關(guān)指標(biāo)的相對重要性權(quán)值[13]。 19的標(biāo)度及描述Table 19 Scale and description標(biāo)度含義（比較因素與）標(biāo)度含義（比較因素與）1因素與一樣重要9因素與絕對重要3因素與稍微重要2，46，8兩相鄰判斷因素的中間值5因素與明顯重要7因素與強(qiáng)烈重要倒數(shù)當(dāng)比較因素與時(shí)構(gòu)造判斷矩陣，我們可以用標(biāo)度法對層次結(jié)構(gòu)圖中的同層次如下，按各元素,……, 的相對重要性賦予權(quán)重，構(gòu)造判斷矩陣，假設(shè)A層次中元素與下一層次元素,……,有聯(lián)系的，: 判斷矩陣Table judgment matrix …… …… …… …… …… …… …… …… …… …… …… 在構(gòu)造判斷矩陣時(shí)，為避免受個人能力水平等方面的限制，判斷矩陣可運(yùn)用專家評比法、德爾菲法等方法進(jìn)行比較判斷，使之更加合理。但一般而言，在層次分析法中計(jì)算判斷矩陣的最大特征值與特征向量，并不需要高的精度，故用近似法計(jì)算即可。在層次分析法中我們引入作為度量判斷矩陣偏離一致性的指標(biāo)。這一步驟是由上而下逐層進(jìn)行，最終計(jì)算得出最低層次元素，即決策方案優(yōu)先順序的相對權(quán)重和整個遞階層次模型的判斷一致性檢驗(yàn)結(jié)果。建立計(jì)算機(jī)管理系統(tǒng)：在配送作業(yè)中運(yùn)用計(jì)算機(jī)管理系統(tǒng)。從上已知，，，所以，從而可以計(jì)算出=類似的對于BC矩陣有，=；對于BC矩陣有，=⑵一致性檢驗(yàn)比較判斷矩陣的最大特征值為=，可以得到=，查表可知，時(shí)，則=，所以比較矩陣具有滿意的一致性。利用層次分析法得到的結(jié)果說明了，在從貨運(yùn)站效益最大化的角度，對車輛路線進(jìn)行合理的優(yōu)化效果較好。天津金雅達(dá)貨運(yùn)站對9個客戶進(jìn)行運(yùn)輸貨物，汽車載重，（距離單位：公里）。所以針對這一情況進(jìn)行優(yōu)化是很有必要的。式()保證了每輛車都不超載。根據(jù)以上假設(shè)，把VRP中的配送網(wǎng)絡(luò)抽象成一個圖。01234 運(yùn)輸網(wǎng)絡(luò)按步分成集合圖Fig. Transportation network steps into set figure由圖可知，根據(jù)分區(qū)規(guī)則客戶1，客戶2，客戶3屬于區(qū)域1，客戶4屬于區(qū)域2。故=算法描述：令⑴若，轉(zhuǎn)2，否則轉(zhuǎn)6；⑵在此時(shí)的網(wǎng)絡(luò)中選擇區(qū)域數(shù)最大且需求不為0的任意一點(diǎn)，不失一般性，記該點(diǎn)為利用動態(tài)規(guī)劃求得和0之間的最短路徑，假設(shè)為，設(shè)該路線上的需求量為，若，即該路線上的總需求大于汽車載重。選擇與該路線終點(diǎn)所相鄰的客戶點(diǎn)，若相鄰的點(diǎn)不止一個那么選取需求量最大的一個，不失一般性設(shè)為，若那么舍去點(diǎn)，再在終點(diǎn)相鄰的其他點(diǎn)中尋找擴(kuò)展點(diǎn)，若終點(diǎn)的任意一相鄰點(diǎn)，都有那么該路線不能再擴(kuò)展，已經(jīng)是最佳路線。記最終的路線為。 動態(tài)規(guī)劃概述 動態(tài)規(guī)劃相關(guān)概念要了解動態(tài)規(guī)劃的概念，首先要知道什么是多階段決策問題。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果[18]。如果過程可以在任何時(shí)刻作出決策，且在任意兩個不同的時(shí)刻之間允許有無窮多個決策時(shí)，階段變量就是連續(xù)的。換句話說，過程的每一次實(shí)現(xiàn)可以用一個狀態(tài)序列表示，在前面的例子中每階段的狀態(tài)是該線路的始點(diǎn)，確定了這些點(diǎn)的序列，整個線路也就完全確定。⑷決策：一個階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個狀態(tài)的一種選擇（行動）稱為決策。描述決策的變量稱決策變量，因狀態(tài)滿足無后效性，故在每個階段選擇決策時(shí)只需考慮當(dāng)前的狀態(tài)而無須考慮過程的歷史。一個問題滿足最優(yōu)化原理也稱其擁有最優(yōu)子結(jié)構(gòu)性質(zhì)[19]。當(dāng)然，各個階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展，當(dāng)各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線，這種把一個問題看作是一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。 ⑷根據(jù)狀態(tài)變量確定費(fèi)用函數(shù)和目標(biāo)函數(shù)。適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。 無后效性將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個狀態(tài)。其中的關(guān)鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。天津金雅達(dá)貨運(yùn)站對9個客戶進(jìn)行運(yùn)輸貨物，汽車載重。 ，==。令客戶 1，5，7 的需求為 0。 客戶需求表Table Customer demand list客戶123456789需求量（t）040300000此時(shí)區(qū)域3中所有客戶的需求均得到滿足，在區(qū)域2中選擇客戶4，由動態(tài)規(guī)劃得到最短路徑=（0，2，4）。相比貨運(yùn)站原來的車輛路線安排，不僅減少了一條路線，減少車輛，而且還提高了每輛車的裝載率，從而達(dá)到提高效益的目的。天津金雅達(dá)貨運(yùn)站在運(yùn)輸路徑上存在運(yùn)輸車輛裝載率低，運(yùn)輸效率不高的現(xiàn)象，所以針對這一過程進(jìn)行優(yōu)化可以在提高車輛裝載率的基礎(chǔ)上，進(jìn)一步提高了運(yùn)輸效率，使得運(yùn)輸經(jīng)濟(jì)效益增加，降低了運(yùn)輸成本，最終達(dá)到了企業(yè)自身效益的提高。對于VRP問題，雖然專家學(xué)者已經(jīng)研究了幾十年，但是卻還存在著一些新問題等待進(jìn)一步的研究解決，在我國， 隨著國民經(jīng)濟(jì)健康穩(wěn)定的高速發(fā)展， 市場經(jīng)濟(jì)日益發(fā)達(dá)， 各種生產(chǎn)經(jīng)營方式發(fā)展得十分迅速。因此， 如何針對各地地形條件、各行業(yè)物流配送運(yùn)輸?shù)奶攸c(diǎn)， 結(jié)合不同的啟發(fā)式算法進(jìn)行優(yōu)勢互補(bǔ)和消除缺陷， 設(shè)計(jì)出通用性好、運(yùn)算速度快、精度高的優(yōu)良算法， 將是研究發(fā)展的方向， 還有待于各學(xué)科專家學(xué)者們作深入細(xì)致的研究。四年的大學(xué)生活已近尾聲，借此畢業(yè)論文完稿的機(jī)會，由衷地感謝幾年來關(guān)心、幫助和支持過我的所有老師和同學(xué)們，因?yàn)槟銈?，我的大學(xué)生活而得以完