1、M201470547 HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY 程論文 現代運籌學算法在物流配送 中的應用 機械學院 工業工程 機碩1407 楊勇 指導教師 李新宇副教授 2014年 12月 29 日 摘要 配送是物流活動中直接與消費者相連的環節。配送成本占物流的各項成本的比例相當高。配送線路合理與否影 (VR P) 響到配送速度、成本和效益，特別是多用戶配送線路的確定是一項復雜的系統工程。因此，物流車輛路線問題 成為國內研究的熱點。 運籌學，用定量化方法了解和解釋運行系統、為管理決策提供科學依據的學科。它把有關的運行系統首先歸結 成數學模型，

2、然后用數學方法進行定量分析和比較，求得合理運用人力、物力和財力的系統運行最優方案。運籌學 有廣闊的應用領域，是軟科學中“硬度”較大的一門學科，兼有邏輯的數學和數學的邏輯的性質，是系統工程學和 現代管理科學中的一種基礎理論和不可缺少的方法、手段和工具。 在運籌學中有解決物流配送問題的有效方法。本文主要介紹了節約法、遺傳算法并用這些方法解決實際物流配送問 題。 關鍵詞：物流配送，節約法，遺傳算法 Abstract Distribution logistics activities directly connected with the consumer segment. The costs of

3、logistics and distribution costs account for a very high proportion. Distribution line is reasonable or not affect the distribution of speed, cost and efficiency, especially multi-user distribution lines to determine is a complex system engineering. Therefore, the logistics vehicle routing p roblem

4、(VR P) has become a hot domestic research. Op erations research, using quantitative methods to understand and expl ain the op erating system, to p rovide a scientific basis for management decisions disc ip lines. It related to the op eration of the system is due to a mathematical model first, and th

5、en use mathematical methods for quantitative analysis and comp arison, and seek the rational use of human, material and financial resources of the system to run the op timal solution. Op erations research has broad app lications, the soft science of hardness of the larger one disc ip line, the natur

6、e of the logic of both mathematics and mathematical logic, is a basic theory of system engineering and modern management science and not lack of methods, means and tools. There are effective ways to solve the logistics p roblems in op erations research. This paper describes the conservation law, sca

7、nning method, tabu search, genetic algorithm and use these methods to solve practical problems of logistics and distribution. Keywords: logistics, saving, scanning method, tabu search, genetic algorithm 1.2 發達國家和地區物流配送現狀 我國的物流配送發展現狀 . 發展物流配送的意義 物流配送路線優化現狀. 1.3 1.4 2理論基礎 2.1 物流配送問題的基本理論 配送路線問題模型 物流配送

8、路線的優化目標 配送車輛路線優化問題的約束條件 配送路線優化問題的分類 2.1.1 2.1.2 2.1.3 2.1.4 2.2 典型配送車輛路線優化問題的數學模型 3現代運籌學方法在物流配送路線優化中的實際應用 3.1 傳統啟發式節約法及其應用 3.1.1節約法描述 3.1.2節約法應用 3.1.3節約法的優缺點分析 3.2 現代啟發式遺傳算法及其應用 遺傳算法概述 編碼 適應度函數 遺傳算子的基因操作 遺傳算法控制參數設定 算法設計 算法實現及結果 3.2.1 3.2.2 3.2.3 3.2.4 3.2.5 3.2.6 3.2.7 4全文總結. 參考文獻 目錄 4 6 6 6 7 8 8 1

9、0 11 11 11 12 16 17 17 19 20 20 22 22 26 26 27 現代運籌學算法在物流配送中的應用 1緒論 1.1發達國家和地區物流配送現狀 理解物流配送概念離不開對物流概念的分析。物流概念最早是在美國形成的，被稱為 “ physiealDistributio n”（即Pn）,譯成漢語是“實物分配”或“貨物配送” 。1963年被引入日本, 物流被定義為“在連接生產和消費間對物資履行保管、運輸、裝卸、包裝、加工等功能，以及作為 控制這類功能后援的信息功能，在物資銷售中起了橋梁作用”。因此，現代物流是以滿足消費者的 需求為目標，把制造、運輸、銷售等市場情況統一起來思考的

10、一個產業概念。配送是物流系統的核 心環節之一，配送在英語中的原語是“delivery ”，是交貨送貨的意思。在日本工業標準Jis中, 將配送定義為“將貨物從物流結點送交收貨人”強調了送貨的含義。可以說，物流配送是連接生產 與消費之間的一種中介服務，是物資供應的種重要形式。配送是“配”和“送”有機結合的形式， 它利用有效的分揀、配貨等理貨工作，使送貨達到一定的規模，以利用規模優勢取得較低的送貨成 本。 推行配送制有利于合理配置資源。由于實施配送可以做到以配送企業的庫存取代社會上千家萬 戶的零散庫存，或者說，可以使庫存相對集中，因此，有條件也有可能按照統一計劃合理分配和使 用資源，做到物盡其用。推

11、行配送制可以降低物流成本，促進生產快速發展。這是因為各種流通要 素相對集中，有益于開展規模經營活動；流通的物質要素相對集中，也便于合理安排各環節上的物 流活動，使總體運動協調一致，最終會減少物流領域內的勞動消耗和費用支出。推行配送制能夠充 分發揮專業流通組織的綜合優勢。推行配送很容易使不同的流通組織聯系在一起，從而構成多功能 的、一體化的物流運動。這種以配送作為媒介而形成的一體化運作較之各個專業企業獨立運作更能 發揮流通組織的整體優勢和綜合優勢。 從20世紀60年代起，商品配送的合理化在美國普遍得到重視。為了在流通領域產生效益，美 國企業采取了以下措施：一是將老式的倉庫改為配送中心；二是引進電

12、腦管理網絡，對裝卸、搬運、 保管實行標準化操作，提高作業效率；三是連鎖店共同組建配送中心，促進連鎖店效益的增長。美 國連鎖店的配送中心有多種，主要有批發型、零售型和倉儲型三種類型。首先是批發型。該類型配 送中心主要靠計算機管理。業務部通過計算機獲取會員店的訂貨信息，及時向生產廠家和儲運部發 出訂貨指示單。其次是零售型。以美國沃爾瑪商品公司的配送中心為典型。該類型配送中心一般為 某零售商獨資興建，專為本公司的連鎖店按時提供商品，確保各店穩定經營。第三是倉儲型。美國 福來明公司的食品配送中心是典型的倉儲式配送中心。它的主要任務是接受獨立雜貨商聯盟的委托 業務，為該聯盟在該地區的若干家加盟店負責商品

13、配送。 在日本，零售業是首先建立先進物流系統的行業之一。便利店作為一種新的零售業態迅速成長， 現己遍及日本，正影響著日本其他的零售商業形式。這種新的零售商業業態需要利用新的物流技術， 以保證店內各種商品的供應順暢。因此，日本的物流配送具有以下特點；第一，分銷渠道發達。許 多日本批發商過去常常把自己定位為某特定制造商的專門代理商， 只允許經營一家制造商的產品。為了保證有效地供應商品，日本許多物流公司不得不對原有的分銷渠 道進行合理化改造，更好地做到與上游或下游公司的分銷一體化。第二，頻繁、小批量進貨。日本的 物流配送企業的很大一部分服務需求來自便利店，便利店依靠的是小批量的頻繁進貨，只有利用先

14、進的物流系統才有可能發展連鎖便利店，因為它使小批量的頻繁進貨得以實現。第三，物流配送體 現出共同化、混載化的趨勢。共同化、混載化的商品配送使原來按照不同生產廠、不同商品種類劃 分開來的分散的商品物流轉變為將不同廠家的產品和不同種類的商品混合起來運送的聚合的商品物 流，從而得以發揮商品物流的批量效益，大大提高了運貨車輛的裝載率。第四，合作型物流配送。在 日本,生產企業、零售企業與綜合商社、綜合物流公司之間基本上都存在一種長期的物流合作關系。 并且，這種合作關系還隨著日本工業生產的國際化延伸到國外。第五，政府規劃在現代物流配送發 展過程中具有重要作用。 1.2我國的物流配送發展現狀 物流配送是現代

15、流通的重要組成部分。近年來，我國物流配送發展出現了積極趨勢，主要體現 在以下幾個方面： 各級政府部門采取措施積極推動物流配送的發展。不少省市己經把發展現代物流列入了日程， 例如，上海、天津、深圳都把物流作為支柱產業。還有許多省市開始制定物流規劃。國家有關部門 對商品物流和配送采取了積極鼓勵和支持的政策，在我國流通領域對外開放政策中，鼓勵國外資本 投資于物流和配送設施等。目前國內物流和配送服務己有較快的發展，物流配送己經成為許多企業 降低成本，提高競爭力的重要手段。例如，相當多實行連鎖經營的零售企業建立了自己的配送中心， 為企業內部的連鎖網點提供物流配送服務，一些連鎖企業配送商品比例己經超過企業

16、經營品種的 50% 在生活資料領域和生產資料領域出現了各具特色的不同類型的現代物流企業。一些傳統的流通 企業，包括運輸和倉儲業通過改造成為物流企業，如中遠集團、中外運集團和中儲集團等；一些國 有商業批發企業和大型零售企業正在積極探索和嘗試開展社會化物流配送服務；一些生產企業開始 介入現代物流，如青島海爾集團；一批專業化的物流企業得到較快發展，物流配送的社會化、專業 化發展趨勢日益明顯，如深圳中海物流都是比較成功的第三方物流公司。外資在物流配送服務領域 的發展也十分迅速，如中國儲運總公司與日本崗谷鋼機株式會社合資組建了天津崗谷物流公司，是 集配送、加工、倉儲、寄售、租賃、修理、展銷和技術咨詢為一

17、體的新型流通組織。像這樣的合資 物流公司，在北京、天津、上海等地已有10家之多，它們主要是為在中國投資的跨國公司提供物流 配送服務。這些企業根據各自特點，發揮特長優勢，積極開拓物流服務領域，形成了服務模式多樣、 多種經濟成份并存的現代物流企業群體。連鎖企業內部的配送中心在硬件設施、管理水平、管理信 息系統等方面的建設，獲得較大發展，有些己經達到較先進的水平。 現代物流技術的開發研究取得一定進展。一些物流配送企業在研究開發物流信息技術和物流配 送管理技術上取得了許多成果，對于推動我國現代物流發展發揮了積極作用。目前已有相當多的物 流和配送技術開始進入中國，并在企業中得到越來越廣泛的應用，例如條形

18、碼技術、計算機支持的 信息管理技術、EDI、MRP等。 盡管我國物流配送業近幾年發展很快，但與發達國家相比還處在起步階段，不可避免地會遇到 這樣或那樣的問題。當前，主要存在以下幾個方面的問題： （1）物流配送市場化程度低，第三方物流配送發展滯后。目前我國大多數物流配送企業技術裝 備和管理手段比較落后，服務網絡和信息系統不健全，物流配送市場化程度低，影響了物流服務的 準確性與時效性。其主要表現是：小（物流配送企業數量小，經營規模小）、少（物流配送市場份額 少、服務功能少，大多數企業還只是被動地按照用戶的要求，從事單一功能的運輸、倉儲和配送， 很少能提供物流策劃、組織及深入到供應鏈的全過程管理，物

19、流增值少）、散（網絡分割、經營秩序 不規范，不能為客戶提供包括物流網絡設計、預測、訂貨管理、存貨管理等系統物流服務）、弱（競 爭力弱和發展滯后，專業化、信息化、標準化還沒跟上，還沒有真正了解國際物流企業的運作方式 和真正意義上的“第三方物流”）。 （2）物流基礎設施落后，物流配送的整體功能低。一是交通運輸設施建設與物流配送的需要不 相適應，即交通運輸能力仍不能滿足運輸需求，主要運輸通道供需矛盾依然突出：二是技術裝備水 平落后；三是物流系統標準化程度低。 （3）物流配送管理體制和相關制度不完善。一方面，市場競爭機制和市場管理法規不健全，發 展物流配送所需的產業政策和產業規劃尚未出臺，物流市場的進

20、入與退出、競爭規則基本上無統一 法律法規可循，對社會性的物流缺乏有效的外部約束，致使不正當競爭較為嚴重。另一方面，物流 配送市場至今仍被人為地按照部門、地區和行業的行政壁壘分割，物流配送市場管理和行業管理還 沒有理順，各地商委、經貿委、交通局、鐵路局、外經貿委等都各自承擔了一部分物流管理職能， 各部門間分工又有交叉，造成了物流管理中條塊分割、重復建設等問題，統一、競爭、有序的物流 配送市場沒有建立起來，嚴重影響了物流配送渠道的暢通和高效運轉，使物流配送很難達到規模經濟 和預期回報。 （4）專業的物流配送管理和技術人才短缺。 1.3發展物流配送的意義 隨著經濟全球化和網絡信息技術發展的加快，物流

21、及配送業作為一個新的經濟增長點引起了國 人的注意。上海、天津、北京等城市紛紛將物流產業作為支柱產業，中儲、中遠、中外運等大型企 業都把現代物流作為重點發展領域。我國證券市場己經形成了由幾十家企業構成的“物流板塊”， 許多商貿流通部門紛紛介入現代物流配送業務中，物流及配送業的發展在全國方興未艾。 2011 年我國社會物流總費用為8.4萬億元，從構成情況看，運輸費用4.4萬億元，占社會物流 總費用的比重為52.4%,保管費用2.9萬億元，占社會物流總費用的比重是34.5%,管理費用1萬億 元，占社會物流總費用的比重為11.9%。運輸成本占物流成本的 50眩右，是影響物流總費用的主要 因素，調查顯示

22、，美國的運輸成本僅占到其GDP勺不到6%日本也僅為6.5%。而我國運輸成本占到 GDP的11%中國倉儲協會對 146家生產企業的調查結果表明，運輸費用占整個物流費用的比例分 別為：生產企業原材料物流中運輸費用占到58%生產企業成品物流中運輸費用占到73%商業物流 中運輸費用占到52%。 由以上數據可以看出運輸費用在總物流費用中所占比重最大，因此節約運輸費用可以極大的降 低物流成本。在物流活動中，配送是很重要的一個環節，運輸成本在配送成本中占有很大的一部分， 因此在配送管理中，有效的使用車輛并確定配送車輛經濟行駛路線，在最短的時間內把商品送到顧 客手中，提高顧客的滿意度，是配送作業的重點。顯然，

23、為了實現以上幾點目標，必須對配送過程 進行合理規劃，這一點可以通過改進運輸方式、進行線路規劃等來實現。近年來，配送車輛路線的 確定問題是物流配送領域的重點研究對象，它是指利用科學的、合理的手段來制定配送線路，對其 進行研究可以提高配送效益、有利于實現配送科學化。 為實現運輸成本的降低，必須對運輸的進行合理規劃。運輸的合理規劃涉及到時間、財務、環 境三方面的因素，首先從時間要考慮準時性、快速響應；財務上要考慮運輸涉及的各種開支（車輛購 置成本和消耗、司機薪酬、油耗等）；環境上要盡可能減少不必要的行駛，避免交通擁擠、空氣以及 噪音等污染。這些可以通過改進運輸方式、線路規劃等交通管理來加以改善。其中

24、運輸方式屬于“硬” 技術的問題。是可以通過設施的完善和提高運輸的效率，降低相應成本。運輸的線路規劃主要是利用 各種先進的信息技術對車輛及其路線進行規劃，實現對車輛合理有效的利用，從而節省大量的時間 和成本。而物流中心配送作業的重點就是如何將車輛有效的使用并決定其最經濟的行駛路線圖，使 商品能在最短的時間內送到顧客的手中。該問題為；從配送中心（物流據點）用多輛車向多個需求點 （顧客）送貨，每個需求點的位置和需求量一定，每輛車的載重量一定，要求合理安排車輛路線，使總 運距最短，并滿足以下條件：（1）每條配送路徑上各需求點的需求量之和不超過車輛載重量；（2）每 條配送路徑的長度不超過車輛一次配送的最

25、大行駛距離；（3）每個需求點必須滿足，且只能由一輛車 送貨。達到一定的目標（如路程最短、費用最少、時間盡量少、使用車輛數盡量少等）。此即為 VRP 問題。 通過科學合理的手段制定配送路線，在配送活動中是很重要的一個環節。合理的選擇配送路線， 對于社會和企業具有重要意義。對于企業，配送路線的優化，可以簡化配送程序、提高配送效率， 充分利用配送車輛運力、降低空載率、減少配送次數、盡量使配送成本降低；同時優化配送路線可 以加快企業對客戶需求的響應速度，準時、快速的把物品送達客戶，提高客戶滿意程度。對于社會， 配送路線優化可以節省作業車輛，進而緩解交通擁堵狀況，減少噪聲、尾氣的排放，為保護生態環 境做

26、出貢獻。所以研究配送車輛路線優化問題及算法具有重要的現實意義。 1.4物流配送路線優化現狀 國內外相關領域對 VRP問題的研究始于50年代，在理論研究和實際應用兩方面都已取得了非常 顯著的成果。隨著研究的深入發展，如何使研究的理論模型更貼近現實中的運輸規劃問題開始成為研 究者們關注的焦點。車輛路線問題（VRP問題）是組合優化領域中著名的NP難題，近二十年來，無論 在國內還是國外，VRP問題都是一個非常活躍的研究領域。目前國內外用于解決該問題的現代數學 方法主要分為以下幾類： （1 ）精確算法 精確算法是采用嚴密的數學手段進行計算的方法，在能夠求得可行解的情況下，其求得的結果 一般要好于啟發算法

27、。常見的精確算法有以下幾種：分枝定界法、割平面法、動態規劃法等。 分支定界法是一種應用范圍很廣的搜索算法，它的基本思想是把給定問題分解為若干個較小的 子問題，每個子問題又可繼續分解，直到子問題不能再分解或不能產生最優解。根據問題的特點和 不同的策略，把問題分解為子問題的過程稱之為分支。在分支過程，為每一子問題估算其對應的目 標值的界限稱之為定界。定界的目的是為了測定界的趨勢，留下有價值的或尚不能判定的分支。刪 除肯定不存在的最優解的分支，稱之為剪支，以達到加速收斂、簡化運算的目的。對為題進行分解， 確定子問題的解值界限，減去非優的子問題，在進行新的分支，這樣一個分支到定界到剪支再到分 支等反復

28、的過程是分支定界法的基本算法步驟。不同的分支規則與定界方法，形成了同一問題的不 同分支定界方法。 割平面法是由高莫瑞 1958年提出的，故又稱為 Gomory的割平面法。它的基本思想是：不斷增 加線性約束條件（幾何術語稱為割平面）將原規劃問題的可行域切割掉一部分，使其切割掉的部分 只包含非整數解，沒有切割掉任何整數可行解，直到切割后得到的可行域有一個整數坐標的極點恰 好是問題的最優解為止。針對求解的決策變量是全部取整還是部分取整問題，割平面算法中就分成 了兩種計算方法，前者稱為分數算法，后者稱為混合整數算法。 ,由每個階段 ,常比線性規劃法更為 ,其基本思路是：按時 ,逆著這個行進方向，從 動

29、態規劃法是20世紀50年代由貝爾曼（R. Bellman ）等人提出，用來解決多階段決策過程問題 的一種最優化方法。所謂多階段決策過程，就是把研究問題分成若干個相互聯系的階段 都作出決策，從而使整個過程達到最優化。許多實際問題利用動態規劃法處理 有效,特別是對于那些離散型問題。實際上，動態規劃法就是分多階段進行決策 空特點將復雜問題劃分為相互聯系的若干個階段，在選定系統行進方向之后 終點向始點計算，逐次對每個階段尋找某種決策 ，使整個過程達到最優，故又稱為逆序決策過程。 精確式算法領域的研究主要是針對某一特定問題而設計，實際應用范圍有限，基本是在傳統物 流配送模式下來考慮問題、改進模型和設計算

30、法。該方法不能保證所得出的最終解是最優整數解， 但其一定是非常接近最優解的。隨著車輛運輸調度系統的復雜化和調度目標的增加，問題的數據量 會變得越來越大，利用精確算法求解問題就會變得十分困難，于是研究者們開始考慮利用啟發算法 來解決這類問題。啟發方法是指人們根據經驗規則來發現問題的滿意解的方法。用啟發式方法求解 問題時往往注重求得滿意解而非最優解。啟發式算法分為傳統啟發式算法和現代啟發式算法兩種。 （2）傳統啟發式算法 傳統的啟發式算法主要有節約法、掃描法等。 節約里程法又稱節約算法或節約法，是指用來解決運輸車輛數目不確定的VRP問題的最有名的 啟發式算法。節約里程法基本規定，利用節約法確定配送

31、路線的主要出發點是，根據配送中心的運 輸能力和配送中心到各個用戶以及各個用戶之間的距離來制定使總的車輛運輸的噸公里數最小的配 送方案。另還需滿足以下條件；1）所有用戶的要求；2 ）不使任何一輛車超載；3 ）每輛車每天的總 運行時間或行駛里程不超過規定的上限；4）用戶到貨時間要求。基本思想是，為達到高效率的配送， 使配送的時間最小距離最短成本最低，而尋找的最佳配送路線。近年來，由于小批量、多批次的及 時配送方式的發展，運輸費用正在逐年提升，許多企業的運費己經超越了庫存費用。選擇有效的配送 路線，己成為控制物流成本的主要措施。那么如何選擇有效的配送路線呢？現代企業已經普遍接受 了一種觀點，即有效的

32、配送路線實際上是在保證商品準時到達客戶指定點的前提下，盡可能地減少 運輸的車次和運輸的總路程。在這種思想的指導下，節約法已成為選擇配送路線的主要方法，并受 到國內外物流界的青睞。 掃描法是 Gillett 和 Miller 于1974年所提出的求解車輛路線問題（Vehicle Routing Problem,VRP）的方法，此方法屬于先分群再排路線的方式。該方法采用極坐標來表示各需求點的區 位，然后任取一需求點為起始點，定其角度為零度，以順時鐘或逆時鐘方向，以車容量為限制條件 進行服務區域之分割，再借由Lin與Kernighan的交換法進行需求點的排序，建構車輛排程路線。 一般情況下，制定從一

33、個物流中心向多個用戶運送貨物的配送計劃時，必須考慮每輛車的運載能力 和行駛距離及時間等的限制。其中掃描法是一種能較好地解決配送路線問題的有效方法，它的基本 思路是采用逐次逼近的方法來解決問題。 （3）現代啟發式算法 現代啟發式算法主要有禁忌搜索算法、遺傳算法、蟻群算法、粒子群算法等。用現代啟發算法 對問題的求解是通過大規模的迭代來實現的，現代啟發算法自身具有一套獨特的搜索規則。為了求 得滿意解，算法在迭代中要不斷采納和分析新信息，必要情況下需要變更原來的策略，建立新的搜 索規則，同時要注意從失敗的搜索中取得經驗教訓，逐漸減小搜索的范圍。隨后從多個可行解中找 出滿意解。 1 ）禁忌搜索法 Gen

34、 dreaut 等人（1991 ）最先將禁忌搜索法應用于車輛路徑優化問題。先構造一系列的解，然 后對所得到的結果不斷地改進。該算法所得到的解不一定是可行解，它們對可行性的偏離程度體現 在目標函數里的懲罰函數值的大小。禁忌搜索法是針對車輛路線優化問題的較好的現代啟發式算法， 在許多經典的車輛路線優化問題的求解中都已經被成功地運用。 2 ）遺傳算法 近年來，一類基于生物學，物理學和人工智能的具有全局優化能力、魯棒性強、通用性強且適于 并行處理的現代啟發式算法得到了發展。因其高效的優化性能、無需問題特殊信息等優點，廣泛用 于計算機科學、優化調度、運輸問題、組合優化、工程優化等領域。遺傳算法是其中具有

35、代表性的 一種現代啟發式方法。 3 ）蟻群算法 蟻群算法蟻群算法（ant colony optimization,，ACO又稱螞蟻算法，是一種用來尋找最優解 決方案的機率型技術。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來源于螞蟻在 尋找食物過程中發現路徑的行為。螞蟻在路徑上前進時會根據前邊走過的螞蟻所留下的分泌物選擇 其要走的路徑。其選擇一條路徑的概率與該路徑上分泌物的強度成正比。因此，由大量螞蟻組成的 群體的集體行為實際上構成一種學習信息的正反饋現象：某一條路徑走過的螞蟻越多，后面的螞蟻 選擇該路徑的可能性就越大。螞蟻的個體間通過這種信息的交流尋求通向食物的最短路

36、徑。蟻群算 法就是根據這一特點，通過模仿螞蟻的行為，從而實現尋優。這種算法有別于傳統編程模式，其優 勢在于，避免了冗長的編程和籌劃，程序本身是基于一定規則的隨機運行來尋找最佳配置。也就是 說，當程序最開始找到目標的時候，路徑幾乎不可能是最優的，甚至可能是包含了無數錯誤的選擇 而極度冗長的。但是，程序可以通過螞蟻尋找食物的時候的信息素原理，不斷地去修正原來的路線， 使整個路線越來越短，也就是說，程序執行的時間越長，所獲得的路徑就越可能接近最優路徑。這 看起來很類似與我們所見的由無數例子進行歸納概括形成最佳路徑的過程。實際上好似是程序的一 個自我學習的過程。 4 ）粒子群算法 Kennedy 和E

37、berhart 在1995年首次提出了粒子群算法，該算法基于對鳥類飛行覓食行為的 模擬，群體達到最優目標是通過鳥群個體之間的協作行為實現的。粒子群算法與遺傳算法類似，它 們的共同點是運算方式基于群體的迭代，但粒子群算法沒有變異、交叉和算子的復制，群體在解可 行域中追逐最優粒子不斷搜索直到找到滿意解。粒子群算法的優點為：個體數量少、計算簡單、魯 棒性好、容易實現，并有著深刻的智能背景，適合于科學研究及工程應用。粒子群算法源于對鳥群 捕食行為的研究。鳥群捕食場景為：鳥群在一片固定區域內尋找食物，但在這個區域內食物只有一 塊，群內的每一只鳥的搜索行為都具有隨機性。鳥群中的所有個體都不清楚在哪里可以找

38、到食物， 但個體知道自身位置與食物間的距離。對于這個群體來說尋找食物的最簡單有效的策略就是搜尋目 前離食物最近的個體周圍的區域，粒子群算法正是基于上述方式解決優化問題的。粒子群算法求解 優化問題時，每一個潛在解可以被看做是空間中進行搜索的一只鳥，我們將之稱為“粒子”。所有 的粒子與相關優化函數之間都有適應值，這個適應值由優化函數決定，粒子自身具有速度，粒子的 速度決定粒子本身的飛行距離和方向。所有的粒子追隨目前的最優粒子在可行區域內搜尋最優解。 粒子群算法隨機初始化一定數量的粒子，它尋找最優解的方式是通過多次迭代。每次迭代粒子追逐 個體極值及全局極值來更新自己。 2理論基礎 2.1物流配送問題

39、的基本理論 2.1.1配送路線問題模型 采用科學的、合理的方法來確定配送線路，成為提高物流配送車輛效益、實現物流配送科學化 的重要途徑。在滿足客戶配送需求的前提下，如何選擇配送路線，是一項很重要的工作。配送作業 的時效性和高效性主要受車輛路線的安排與調度方案優化情況的影響。配送路線優化問題由來已久, 其可以描述如下，見圖 2-1。 o 客戶點 配送中心 圖2-1配送路線優化問題原理圖 ，車輛載重量為Q1, ，Gi。從配送中心出 有一個（或者多個）配送中心，共有配送車輛K輛（一種或者多種車型） Q2, , , Qk共有I位客戶等待被服務，每位客戶都有各自需求量G1, G2, 發的配送車輛對等待服

40、務的客戶進行配送，以滿足客戶的要求（物品品種、數量、規格的要求，配 送時間的要求），最后返回配送中心。要求所有客戶都被服務到，同時配送車輛不能超載。最終求 出車輛配送路線方案，并達到一定的優化目標（如路程最短、費用最少、時間盡量少等）。 路網。各要素具體說明如下。 車輛，其主要屬性有：車輛類型、裝載量、最大行駛距離、配送開始前與完成后所在的配 車輛路線優化問題是 NP難題。自從它被提出以來，由于其應用的廣泛性和在經濟上的價值, 一直受到國內外學者的廣泛關注。配送路線優化問題的主要構成要素為：配送車輛、貨物、客戶、 配送中心、 貨物，其主要屬性有：重量、送達時間和送達地點等。貨物能否裝在同一配送

41、車輛上取決 于貨物屬性。 （3） 客戶，其主要屬性有：需求 （或供應）貨物的種類、接受服務的時間等。 （4）配送中心，其主要是用來進行集貨、分貨、配貨、送貨等物流作業，在不同的路線優化問 題中，配送中心的個數為一個或者多個。 （5）運輸網絡，其組成部分有配送中心、客戶點和車輛行駛路線等。 （1） 送中心。 （2） 2.1.2物流配送路線的優化目標 對車輛配送路線問題進行優化時，必須要有明確的目標和遵循的基本原則。配送路線優化問題的優化目標可以從以下幾個方面考慮： （1）配送效益最高或配送成本最低。 物流企業是以追求效益為主要目標的，通常用企業利潤來表示，即企業通常以利潤的最大化作 為自身經營的

42、目的。配送成本對物流企業利潤有直接的影響，以成本最低作為優化目標與物流企業 利潤的最大化有直接的聯系。當與成本及利潤相關的數據容易得到和計算時，就可以用利潤最大或 以成本最低作為優化目標。 （2）配送里程最短。 當配送成本與配送里程具有較強的相關特性，與除此之外的其它因素相關特性較弱時，配送里 程最短就近似等同于配送成本最低。這時可以考慮用配送里程最短作為優化目標，這樣就可以大大 簡化配送路線優化方法。當配送成本與配送里程的相關性不明顯優于其它因素的時候，如考慮車輛 載重情況、道路運行條件等因素，單以路線最短作為優化目標就變得不適宜。 （3）配送服務水平最優。 當準時性成為配送的第一要求，或當

43、出現某些特殊情況需要確保服務水平而忽略配送成本時， 則應盡量在成本不出現失控的情況下，以服務水平最優為優化目標。優質的服務可以采用較高的服 務價格，從而保證企業的合理利潤。 （4）配送勞動的消耗最小。 它是以物化勞動和活勞動消耗最小為優化目標，在許多情況下，如人員緊張、燃料緊張、車輛 設備緊張等，限制了配送作業，這時就可以考慮以配送所需要的人員、車輛或其它相關資源消耗最 小作為優化目標。實際上，配送路線優化問題的優化目標是多元的，但是考慮到優化目標的目標值 應當符合實際情況，一般要盡可能取得實用性較強的目標值。因此，本文采用成本最低作為優化目 標。 2.1.3配送車輛路線優化問題的約束條件 （

44、1） （2） （3） （4） （5） （6） （7） （8） 現實中，配送車輛路線優化問題存在著很多方面的約束條件，這些約束條件使得該問題在研究 和應用上產生了許多不同的方向和型態，基于前文所述的分類標準，一些最重要的約束條件包括： 容量約束。任意配送車輛所搭載的貨物總量不能超過該車輛的載重能力。 配送中心數目約束。配送中心有一個或者多個。 優先約束。客戶之間服務的次序存在著限制。 車型約束。不同客戶的配送要求需要由不同車型來滿足。 時間窗約束。包括硬時間窗約束和軟時間窗約束。 隨機約束。客戶數量、配送需求、行駛路線等隨機出現。 車速約束。車速是否穩定。 相容性約束。客戶是否可以被不同配送車輛

45、（配送中心）服務。 通過以上分析，本文所要研究的配送車輛路線優化問題所采用的約束條件為：每個客戶只能被 一輛車服務，每個被服務客戶沒有優先次序，配送車輛的載重情況不超過自身的載重能力，每個客 戶對其被服務的時間窗的要求為軟時間窗模式。 2.1.4配送路線優化問題的分類 對配送車輛路線問題類型分析是進一步對問題進行建模和求解的基礎。現有的對 配送路線優化問題的分類大致有以下八種： 分類依據 分類 具體分類說明 按任務 特征分 只送貨問題 只送貨問題的特征為：配送車輛僅考慮從配送中心向客戶送貨；只取貨 問題的特征為：配送車輛僅考慮從各客戶處把供應的貨物取到配送中心； 取送貨混合問題的特征為：既考慮

46、將客戶需求的貨物從配送中心送到各 個客戶 只取貨問題 混合問題 按配送中心 數目分 單一車場問題 單一車場問題的特征為：配送系統中只有一個車場、貨場或 配送中心；多個車場問題的特征為：配送系統中有多個車場、貨場或配 送中心 多個車場問題 按配送車輛 類型數目分 單一車型問題 單一車型問題的特征為：配送作業所用車輛都是同一類型，即車輛的參 數如：載重能力、最長行駛時間和單次作業的最大行 駛距離等相同；反之多種車型問題的特征為配送作業所用的車輛類型不 完全相同 多個車型問題 按配送車輛 路線分 車輛開放問題 車輛封閉問題 車輛開放問題的特征為：車輛完成其配送任務后可以不返回 出發點；車輛封閉問題的

47、特征為：車輛完成其配送任務后必須返回出發 點 按配送車輛 卸載狀況分 滿載問題 滿載問題是指當客戶的需求量或提供量大于或者等于配送車輛的載重能 力時，需要用一輛或者多輛車來完成一項配送作業，其中大多數配送車 輛要滿載運行；非滿載問題是指當客戶的需求量或提供量小于配送車輛 的載重能力時，多個客戶的配送需求都可以由同一配送車輛來滿足，整 個配送過程中配送車輛處于非滿載狀態；滿載和非滿載混合問題是指當 一部分客戶的需求量或提供量大于或者等于配送車輛的載重能力，而一 部分客戶的需求量或提供量小于配送車輛的載重能力時 非滿載問題 混合問題 按客戶時間 需求分 無時間窗問題 無時間窗問題的特點是客戶對服務

48、時間無具體要求；有時間 窗問題的特點是客戶要求配送車輛必須在規定的時間范圍內將貨物送達 或取走。有時間窗問題又可以分為硬時窗問題和軟間窗問題，其中硬時 窗是指，客戶要求必須在指定的時間范圍內進行配送作業，不能提前也 不能拖后否則需要等待或者不能為其服務，軟時窗是指，客戶要求配送 車輛盡可能在規定的時間范圍為其服務但也可以提前或拖后，只是要受 到一定的懲罰，如交罰金 有時間床問題 按優化目標 數分 單目標問題 單目標問題是指選擇某一最優或較優指標作為優化目標，如配送路線最 短。多目標問題則是指同時選擇多個最優或較優的指 標作為優化目標，如同時要求配送路線最短和成本最低。路線優化模型 的指標一般包

49、括：配送時間最短、配送路線最短、成本最低。一般情況 下這三個目標是統一的：距離最短，也就意味著時間最短，成本也最低， 但是很多情況下，也有出現多目標不統一、甚至互相矛盾的可能 多目標問題 按客戶和路 網特點分 靜態問題 靜態問題的特征為：客戶的位置、數目、需求，以及天氣、路況等因素 是確定的和已知的；動態問題的特征為：客戶的位置 數目、需求，以及天氣、路況等因素是隨機變化的。 動態問題 表2-1 2.2典型配送車輛路線優化問題的數學模型 本文此處以經典的帶時間窗配送車輛路線優化問題為例，來說明配送車輛路線優化問題的一般 模型及表達方式。帶時間窗配送車輛路線優化問題的一般描述為：有一個配送中心（

50、含車場），擁 有的配送車輛數為 K輛，容量分別為Qk（ k=1，2，,， K）。有I個客戶點需要被服務，客戶點i LTi表示客戶 ，則配送車輛需 的配送作業將被 的作業量為Gi，配送車輛k到達客戶點i的時刻為kis ，并且客戶點i的配送作業需要在規定 的時間窗ETi，LTi內完成，其中ETi表示客戶點i允許配送作業開始的最早時間， 點i允許配送作業開始的最遲時間。如果配送車輛到達客戶點i的時間早于ETi 要在客戶點i處等待，如果配送車輛到達客戶點 i的時間晚于LTi ,則客戶點i 延遲進行，同時配送車輛需要接受處罰。 一般情況下帶時間窗路線優化問題需要考慮以下幾個約束條件： （1） 各客戶點只

51、可以由一輛車配送且只能被配送一次，不考慮多輛車同時為一個客戶點服務的 情況； （2）配送中心（或車場）只有一個，所有車輛從配送中心出發，車輛在完成所有作業之后需要 回到配送中心； （3）各配送線路上客戶點的作業總量不應大于該線路上作業車輛的載重量； （4） 每個客戶點的配送作業量必須小于為其服務的車輛的最大載重量，即只需一臺配送車輛即 可滿足該客戶點的配送作業需求。 對模型參數定義如下： 車輛k由i到j 其他 客戶i由k車來服務 其他 cij表示客戶點 i 到客戶點j的運輸成本; Pe表示配送車輛由于等待失去的機會成本; Pl表示配送車輛由于遲到需要支付的罰金。 在僅考慮裝載約束和時間窗約束的

52、條件下，帶時間窗的配送車輛路線優化模型可以表示為: / ； KI KI K min 丫丫2%+凡工工皿何-曲 +巴工丫皿（/-”） （0 jOr-l k -ir-l t-1 I Z Giyik Qk i 1 任意的k K 無yik kzi i=1 , 2, I 無xijk i衛 = yjk j=1 I，任意的k I ZXijk j =0 = yik i=1 ,2, I，任意的k Xijk =0 或 1 i , j=1 , 2, ,1，任意的 k yik =0 或 1 i=1 ,2, , , I，任意的k 表示為各客戶點配送的目標是使配送成本最小。 目標函數由兩部分組成, 其中式中的目標函數，

53、前半部分為車輛在線路上進行配送時所消耗的運輸成本，后半部分為車輛在為各個客戶點進行配送 的過程中，由早到所損失的機會成本及遲到所支付的罰金之和。這一目標函數的具體意義為：要在 滿足配送路線最短的條件下，盡量考慮車輛配送的時間窗約束，以使得配送車輛運輸成本及時間成 本兩者所代表的配送成本最低。該模型的不足是忽略了配送車輛載重情況及道路等級情況對車輛運 輸成本的影響。 3現代運籌學方法在物流配送路線優化中的實際應用 3.1傳統啟發式節約法及其應用 3.1.1節約法描述 利用里程節約法確定配送路線的主要出發點是，根據配送方的運輸能力及其到客戶之間的距離 和各客戶之間的相對距離來制定使配送車輛總的周轉

54、量達到或接近最小的配送方案。 配送的是同一種或相類似的貨物； 各用戶的位置及需求量已知； 配送方有足夠的運輸能力； 設狀態參數為tij, tij是這樣定義的: 假設條件： （1） （2） （3） tij=1,表示客戶I， toj =2表示由送貨點 （4） J在同一送貨路線上；0,表示客戶I，J不在同一送貨線路上。 P0向客戶J單獨派車送貨。 jXN Z tij + tij =2（j =1,2,N） 且所有狀態參數應滿足下式：g P十 式中：N-客戶數 利用節約法制定出的配送方案除了使總的周轉量最小外，還應滿足： （1） （2） （3） 方案能滿足所有客戶的到貨時間要求； 不使車輛超載； 每輛車

55、每天的總運行時間及里程滿足規定的要求。 3-1所示，設po為配送中心，分別向用戶Pi和Pj送貨。Po到Pi和Pj的距離分別為doi和doj， Pi和Pj之間的距離為dij，送貨方案只有兩種即配送中心Po向用戶Pi, Pj分別送貨和配送中 Pj同時送貨，如圖11-7a）和b）。比較兩種配送方案： 如圖 兩個用戶 心Po向用戶Pi, 方案a）的配送路線為 poT PiTPoTPjT Po,配送距離為 da=doi+doj 方案b）配送路線poT piT pjT po,配送距離為db=. doi+doj+dij 顯然，da不等于db,我們用Sj表示里程節約量，即方案b）比方案a）節約的配送里程: s

56、ij doi + d oj d ij 配送貨物，在汽 根據節約法的基本思想，如果一個配送中心 po分別向N個客戶Pj（j=1.2 車載重能力允許的前提下，每輛汽車的配送線路上經過的客戶個數越多，里程節約量越大，配送線 路越合理。 31 例：某一配送中心 po向 號內的數字表示客戶的需求量（ 種車輛可供使用，試制定最優的配送方案。 圖3-1 3.1.2節約法應用 1o個客戶Pj（j=1,2, ,1o）配送貨物，其配送網絡如圖3-2所示。圖中括 T），線路上的數字表示兩節點之間的距離。配送中心有2t和4t兩 tl-5) (04) (0旳 10 7 6 10 3 2 9 6 h 2) 8) P Pi

57、 6 PliO 11 S (14) (0.6) 圖3-2 解：第一步：計算最短距離。根據配送網絡中的已知條件，計算配送中心與客戶及客戶之間的 最短距離，結果見表 3-3。 Po 10 Pi 9 4 P2 7 9 5 R 8 14 10 5 P4 8 18 14 9 6 P5 8 18 17 15 13 7 F6 3 13 12 10 11 10 6 R 4 14 13 11 12 12 8 2 F8 10 11 15 17 18 18 17 11 9 F9 7 4 8 13 15 15 15 10 11 8 P10 表3-3 第二步：計算節約里程 Sj,結果見表3-4。 P1 15 P2 8

58、11 F3 4 7 10 F4 0 3 6 10 P5 0 0 0 3 9 0 0 0 0 1 5 P7 0 0 0 0 0 4 5 9 4 0 0 0 1 2 5 P9 13 8 1 0 0 0 0 0 9 P10 表3-4 3-5。 第三步：將節約 Sj,進行分類，按從大到小的順序排列，得表 節約里程項目分類表 序號 路線 節約里程 序號 路線 節約里程 1 P1P2 15 13 P6P7 5 2 P1P10 13 13 P7P8 5 3 P2P3 11 13 P8P9 5 4 P3P4 10 16 P1P4 4 4 P4P5 10 16 P2P9 4 6 P1P9 9 16 P6P8 4

59、 6 P5P6 9 19 P2P5 3 6 P9P10 9 19 P4P6 3 9 P1P3 8 21 P7P9 2 9 P2P 10 8 22 P3P10 1 11 P2P4 7 22 P5P7 1 12 P3P6 6 22 P6P9 1 表3-5 第四步：確定配送線路。從分類表中，按節約里程大小順序，組成線路圖。 So： 148km 2tX 10 配送距離： 配送車輛： (2) 對方案進行修正 Pl0, P2和P3,得修正方案1。 10條 S1: 109km 2tX 6+4t X 1 2)在剩余的Sij中，最大的是 輛的載重量及線路均衡問題，連接 配送線路： 配送距離： 配送車輛： P5都

60、有可能并入線路 A中，但考慮到車 S3, 4和S4, 5,此時P4和 P4和P5形成一個新的線路B,得修正方案2。 6條 S2： 99km 2t X 5+4t X 1 3 載， )接下來最大的Sj是S1, 9和 故只將P6點并入線路B，得修正方案3。 配送線路： 配送距離： 配送車輛： S5, 6,由于此時P1已屬于線路A，若將P9并入線路A，車輛會超 5條 S3： 90km 2tX 3+4t X 2 1 )按節約里程Sij由達到小的順序，連接 P1和P2, P1和 配送線路： 配送距離： 配送車輛： )再繼續按Sij由大到小排出S9 已完成的線路里， 配送線路： 配送距離： 配送車輛： P8