【正文】 ................................................... 34 實例實驗 ....................................................................... 38 實例數(shù)據(jù) ....................................................................... 38 實例數(shù)據(jù)分析 ................................................................. 38 結(jié) 論 .................................................................................................. 39 參考文獻 ............................................................................................. 41 謝 辭 .................................................................................................. 42 1 引 言 隨著市場經(jīng)濟的發(fā)展，大量經(jīng)營規(guī)模較大的制造企業(yè)和商業(yè)企業(yè)紛紛建立起配送中心向商品流通效率化發(fā)起挑戰(zhàn)，與此同時，相當部分的大型運輸、倉儲和航運企業(yè)開始轉(zhuǎn)向第三方物流經(jīng)營。此外，我國具有強大物流配送資源優(yōu)勢的郵政業(yè)更是在遞送包裹的基礎(chǔ)上為企業(yè)、商家和電子商務(wù)網(wǎng)站積極開展配送業(yè)務(wù)。物流配送開始在我國迅速興起發(fā)展起來，對物流配送的研究引起了國內(nèi)物流專家學者的廣泛關(guān)注。 目前國內(nèi)采用遺傳算法解決物流配送的車輛優(yōu)化調(diào)度問題的研究還處在起步階段。本文針對客戶提出時間約束這 一配送需求，對有時間窗的物流配送車輛優(yōu)化調(diào)度問題（ VSPTW）進行數(shù)學分析，研究探索性能更強的解決 VSPTW的遺傳算法。 本文第 1章研究目前物流配送車輛優(yōu)化調(diào)度問題的研究動態(tài)和水平；第 2章進一步研究有時間窗的物流配送車輛優(yōu)化調(diào)度問題；第 3章闡述和研究所采用遺傳算法的基本理論；第 4章詳細論述如何采用遺傳算法解決有時間窗的物流配送車輛優(yōu)化調(diào)度問題并通過實驗數(shù)據(jù)分析所采用改進的遺傳算法的性能。 2 第 1 章 概 述 研究背景 隨著社會主義市場經(jīng)濟的發(fā)展， 在經(jīng)濟大循環(huán)中提高 經(jīng)濟運作 效率 的物流對經(jīng)濟活動 的影響日益明顯，越來越引起人們的重視。 據(jù)中國物流信息中心統(tǒng)計測算， 2021 年，全國社會物流總額達 萬億元，同比增長 %(按現(xiàn)價計算 )，增幅比上年同期提高 個百分點。 雖然 我國物流發(fā)展 持 續(xù)加速，但與國民經(jīng)濟發(fā)展的要求 還 相差甚遠 ，這就要求我們對物流產(chǎn)業(yè)的各個環(huán)節(jié)進行研究。 配送是物流中一個重要的直接與消費者相連的環(huán)節(jié)。我國國家標準《物流術(shù)語》中對配送的定義是：“在經(jīng)濟合理區(qū)域范圍內(nèi)，根據(jù)用戶要求，對物品進行揀選、加工、包裝、分割、組配等作業(yè)，并按時送達指定地點的物流活動 ［７］ ?！迸渌褪窃诩?貨、配貨基礎(chǔ)上，按用戶要求，包括種類、品種搭配、數(shù)量、時間等方面的要求所進行的運送，是“配”和“送”的有機結(jié)合形式，其主要功能是輸送。配送的流程一般如下圖所示。 圖 11 配送流程圖 在傳統(tǒng)的配送系統(tǒng)中，由于商品的需求量及種類較少，零售商可憑借較多的存貨及較常的定貨周期來減少供貨商的配送頻率，以降低運輸成本。但是在現(xiàn)代的配送系統(tǒng)中，零售商為了減少資金積壓及提供多樣化的商品，勢必要減少各種商品的存貨數(shù)量，而同時又必須考慮到提供最好的服務(wù)品質(zhì) (不允許缺 貨 )。物流中心的功能就在于對商品的倉儲與運輸進行有效的統(tǒng)籌規(guī)劃以降低配送成本。 所謂“物流中心”，根據(jù)美國物流管理協(xié)會 (The Council of Logistics Management, CLM)定義：“以適合顧客要求為目的，對原物料、在制品、制成品與其相關(guān)信息，從產(chǎn)地到消費者的間的流程與保管，為求有效率且最小的機會成本，而進行計劃、執(zhí)行、控制的場所(Depot) ”。 在 物流配送系統(tǒng)中，物流配送中心的成立可有效的簡化配送程序與減少配送的頻率，以i個供應(yīng)商和 j 個零售商為例，傳統(tǒng)的配送模式是假設(shè) j個零售 商的需求都是由 i個供應(yīng)商自行配送，則一共有 ij 次的運送，如圖 12 所示。假設(shè)零售商與供應(yīng)商之間通過一個物流配送中心來配送，則只需 i+j 次配送，如圖 13所示，如此一來即可減少 (ij(i+j))的配送次數(shù)，當供應(yīng)商與零售商數(shù)目越多，節(jié)省的配送次數(shù)也就會越多。 3B 2B 1B 用戶 工廠 1A 2A 3A 進貨 送貨 集貨 存儲 配貨 車輛 配裝 3 圖 12 傳統(tǒng)的物流配送模式 物流中心配送作業(yè)的重點是如何將車輛有效的使用并決定其最經(jīng)濟的行駛路線圖，使商品能在最短的時間內(nèi)送到顧客的手中。國外將此類問題稱之為 Vehicle Scheduling Problem，簡稱為 VSP問題。該問題一般定義為 :對一系列裝（卸）貨點，組織適當?shù)男熊嚲€路，使車輛有序的通過它們，在滿足一定的約束條件 (如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等 )下，達到一定的目標 (如路程最短、費用最少、時間盡量少、使用車輛數(shù)盡量少等 )［３］ 。 圖 13 以物流中心為主的配送模式 1S 2S iS 1R 2R jR 供應(yīng)商（ S） 零售商（ R） 供應(yīng)商（ S） 零售商（ R） 1S 2S iS 1R 2R jR 物流 中心 4 物流配送車輛優(yōu)化調(diào)度的研究動態(tài)和水平 問題的提出 物 流配送車輛優(yōu)化調(diào)度問題最早是由 Dantzig和 Ramser于 1959年首次提出，自此，很快引起運籌學、應(yīng)用數(shù)學、組合數(shù)學、圖論與網(wǎng)絡(luò)分析、物流科學、計算機應(yīng)用等學科的專家與運輸計劃制定者和管理者的極大重視，成為運籌學與組合優(yōu)化領(lǐng)域的前沿與研究熱點問題。各學科專家對該問題進行了大量的理論研究及實驗分析，取得了很大的進展。 國外對物流配送車輛優(yōu)化調(diào)度問題作了大量而深入的研究，例如早在 1983 年 Bodin, Golden 等人在他們的綜述文章中就列舉了 700余篇文獻。在 Christofides(1985)， Golden和 Assad(1988)編 輯的論文集，以及 Altinkermer 和 Gavish(1991)， Laporte(1992)，Salhi(1993)等的綜述文章中都進行了詳盡闡述。該領(lǐng)域的代表人物有 Bodin， Christfids，Golden， Assad， Ball， Laporte， Rinnooy Kan， Lenstra， Desrosiers和 Desrochers等人［１］［３］ 。 國內(nèi)對物流配送車輛優(yōu)化調(diào)度問題的研究相當少，主要研究對象是旅行商問題(Traveling Salesman Problem，簡稱 TSP)、中國郵遞員問題 (Chinese Postman Problem ,簡稱 CPP)、有向中國郵遞員問題 (Directed Chinese Postman Problem，簡稱 DCPP)等，系統(tǒng)性研究還尚未見到。李大為等 (1998)以 TSP的最近距離啟發(fā)式為基礎(chǔ)，通過設(shè)置評價函數(shù)來處理時間窗約束，求解了簡單的 VSP。張震 (1995)針對單車場滿載問題，提出了考慮運輸行程約束的優(yōu)化方法。遺傳算法和神經(jīng)網(wǎng)絡(luò)方法對簡單 TSP的求解取得了一定成果。蔡延光等 (1998)應(yīng)用并行表搜索法和模擬退火法針對簡單情形對滿載問題進行了求解 ［３］［５］ 。 目前，問題的形式己有很大發(fā)展，該問題以不僅僅局限于汽車運輸領(lǐng)域，在水運、航空、通訊、電力、工業(yè)管理、計算機應(yīng)用等領(lǐng)域也有一定的應(yīng)用，其算法己用于航空乘務(wù)員輪班安排、輪船公司運送貨物經(jīng)過港口與貨物安排的優(yōu)化設(shè)計、交通車線路安排、生產(chǎn)系統(tǒng)中的計劃與控制等多種組合優(yōu)化問題。 分類 VSP 被 提 出 后 ， Linus (1981),Bodin 和 Golden(1981) , Bodin(1983) , Assad(1988) ,Desrochers, Lenstra和 Savelsbergh(1990)等許多學 者對 VSP從不同角度，按不同的標準進行了分類。 按任務(wù)特征分，有純裝問題或純卸題 (pure pick up or pure delivery, 車輛在所有任務(wù)點裝貨或卸貨，及集貨或送貨問題 ) 及裝卸混合問題 (bined pick up and delivery，每項任務(wù)有不同的裝貨點和卸貨點，即集貨、送貨一體化問題 )。 按任務(wù)性質(zhì)分，有對弧服務(wù)問題 (如中國郵遞員問題 )和對點服務(wù)問題 (如旅行商問題 )以及混合服務(wù)問題 (如交通車線路安排問題 )。 按車輛載貨狀況分，有滿載問題 (貨運量不小于車輛容量，完成一項任 務(wù)需要不只一輛車 )和非滿載問題 (貨運量小于車輛容量，多項任務(wù)用一輛車 )。 按車場 (或貨場、配送中心等 )數(shù)目分，有單車場問題和多車場問題。 按車輛類型數(shù)分，有單車型問題 (所有車輛容量相同 )和多車型問題 (執(zhí)行任務(wù)的車輛容 5 量不完全相同 )。 按車輛對車場的所屬關(guān)系分，有車輛開放問題 (車輛可以不返回其發(fā)出車場 )和車輛封閉問題 (車輛必須返回其發(fā)出車場 )。 按優(yōu)化目標數(shù)來分，有單目標問題和多目標問題。 由于情況的不同，車輛優(yōu)化調(diào)度問題的模型構(gòu)造及算法有很大的差別。 基本問題與基本方法 為簡化貨運車輛優(yōu) 化調(diào)度問題的求解，常常應(yīng)用一些技術(shù)將問題分解或轉(zhuǎn)化成一個或幾個已經(jīng)研究過的基本問題，再用相應(yīng)比較成熟的基本理論和方法，以得到原貨運車輛優(yōu)化調(diào)度問題的最優(yōu)解或滿意解。 常用的基本問題有：旅行商問題、分派問題、運輸問題、背包問題最短路問題、最小費用流問題、中國郵路問題等。 常用的基本理論和方法有：分枝界定法、割平面法、線性規(guī)劃法、動態(tài)規(guī)劃法、匹配理論、對偶理論、組合理論、線搜索技術(shù)、列生成技術(shù)、概率分析、統(tǒng)計分析、最差情況分析、經(jīng)驗分析等。 算法 貨運車輛優(yōu)化調(diào)度問題的求解方法非常 豐富，目前主要有以下四類： 系統(tǒng)仿真法 (Simulation ) 此方法最早由 Golden 和 Skiscim 于 1986 年提出，主要應(yīng)用于行車線路與物流中心區(qū)位的選擇，優(yōu)點在于可直接觀察系統(tǒng)安排的效率與效果，但由于問題的實際情況多變且具有不確定性，是否能將實際的配送情形系統(tǒng)邏輯化為仿真程序，往往令人質(zhì)疑。 人機互動法 此方法結(jié)合人類決策與計算機計算能力，在求解的過程中，通過高度的人機交互模式，結(jié)合專家的決策信息，并據(jù)以計算出結(jié)果；優(yōu)點是尋優(yōu)的過程中，決策者可以很清楚地看到各約束條件之間的替代關(guān)系，以及 參數(shù)變化可能導(dǎo)致的成本變化。 精確解法 (Exact procedures ) 精確解法指可求出最優(yōu)解的算法，精確解法主要有： 分枝界定法 (Branch and Bound Approach)、割平面法 (Cutting Planes Approach)、網(wǎng)絡(luò)流算法 (Network Flow Approach)、動態(tài)規(guī)劃方法 (Dynamic Programming Approach)。精確算法的計算量一般隨著問題規(guī)模的增大呈指數(shù)增長。 啟發(fā)式解法 (Heuristics) 由于上述三種方法的求解效率 較差，所以大部分的學者都致力于啟發(fā)式解法的發(fā)展。該方法在解題時可減少搜尋的次數(shù)，所以是一種容易且快速的求解困難問題的算法。目前已提 6 出的啟發(fā)式算法很多，按 Cesar Rego 的分類法有以下四類： （ 1）算法 (Constructive Algorithm) 根據(jù)一些準則，每一次將一個不在線路上的點增加進線路，直到所有的點都被安排進線路為止。該類算法的每一步，把當前的線路構(gòu)形（很可能是不可行的）跟另外的構(gòu)形（也可能是不可行的）進行比較并加以改進，后者是根據(jù)某個判別函數(shù)（例如總費用）會產(chǎn)生最大限度的節(jié)約的構(gòu)形，或是 以最小代價把一個在當前構(gòu)形上的需求對象插入進來的構(gòu)形 (Clarke和 Wright， 1964； Mole 和 Jamesson， 1976； Paessens， 1988； Altinkemer 和 Gavish， 1991；Desrochers 和 Verhoog， 1989)。 構(gòu)造算法是最早提出用來解決旅行商問題 (Traveling Salesman Problem,簡稱 TSP)及 VSP的，這些方法一般速度快，也很靈活，但這類方法有時找到的解離最優(yōu)解差的很遠。 （ 2）階段法 (Twophase Algorithm) 兩階段法是： 第一階段得到一可行解，第二階段通過對點的調(diào)整，在始終保持解可行的情況下，力圖向最優(yōu)目標靠近，每一步都產(chǎn)生另一個可行解以代替原來的解，使目標函數(shù)值得以改進，一直繼續(xù)到不能再改進目標函數(shù)值為止 (Gillet