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