【正文】 的研究還處在起步階段。 本文第 1章研究目前物流配送車輛優(yōu)化調(diào)度問題的研究動態(tài)和水平；第 2章進(jìn)一步研究有時間窗的物流配送車輛優(yōu)化調(diào)度問題；第 3章闡述和研究所采用遺傳算法的基本理論；第 4章詳細(xì)論述如何采用遺傳算法解決有時間窗的物流配送車輛優(yōu)化調(diào)度問題并通過實驗數(shù)據(jù)分析所采用改進(jìn)的遺傳算法的性能。 據(jù)中國物流信息中心統(tǒng)計測算， 2021 年，全國社會物流總額達(dá) 萬億元，同比增長 %(按現(xiàn)價計算 )，增幅比上年同期提高 個百分點(diǎn)。 配送是物流中一個重要的直接與消費(fèi)者相連的環(huán)節(jié)?！迸渌褪窃诩?貨、配貨基礎(chǔ)上，按用戶要求，包括種類、品種搭配、數(shù)量、時間等方面的要求所進(jìn)行的運(yùn)送，是“配”和“送”的有機(jī)結(jié)合形式，其主要功能是輸送。 圖 11 配送流程圖 在傳統(tǒng)的配送系統(tǒng)中，由于商品的需求量及種類較少，零售商可憑借較多的存貨及較常的定貨周期來減少供貨商的配送頻率，以降低運(yùn)輸成本。物流中心的功能就在于對商品的倉儲與運(yùn)輸進(jìn)行有效的統(tǒng)籌規(guī)劃以降低配送成本。 在 物流配送系統(tǒng)中，物流配送中心的成立可有效的簡化配送程序與減少配送的頻率，以i個供應(yīng)商和 j 個零售商為例，傳統(tǒng)的配送模式是假設(shè) j個零售 商的需求都是由 i個供應(yīng)商自行配送，則一共有 ij 次的運(yùn)送，如圖 12 所示。 3B 2B 1B 用戶 工廠 1A 2A 3A 進(jìn)貨 送貨 集貨 存儲 配貨 車輛 配裝 3 圖 12 傳統(tǒng)的物流配送模式 物流中心配送作業(yè)的重點(diǎn)是如何將車輛有效的使用并決定其最經(jīng)濟(jì)的行駛路線圖，使商品能在最短的時間內(nèi)送到顧客的手中。該問題一般定義為 :對一系列裝（卸）貨點(diǎn)，組織適當(dāng)?shù)男熊嚲€路，使車輛有序的通過它們，在滿足一定的約束條件 (如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等 )下，達(dá)到一定的目標(biāo) (如路程最短、費(fèi)用最少、時間盡量少、使用車輛數(shù)盡量少等 )［３］ 。各學(xué)科專家對該問題進(jìn)行了大量的理論研究及實驗分析，取得了很大的進(jìn)展。在 Christofides(1985)， Golden和 Assad(1988)編 輯的論文集，以及 Altinkermer 和 Gavish(1991)， Laporte(1992)，Salhi(1993)等的綜述文章中都進(jìn)行了詳盡闡述。 國內(nèi)對物流配送車輛優(yōu)化調(diào)度問題的研究相當(dāng)少，主要研究對象是旅行商問題(Traveling Salesman Problem，簡稱 TSP)、中國郵遞員問題 (Chinese Postman Problem ,簡稱 CPP)、有向中國郵遞員問題 (Directed Chinese Postman Problem，簡稱 DCPP)等，系統(tǒng)性研究還尚未見到。張震 (1995)針對單車場滿載問題，提出了考慮運(yùn)輸行程約束的優(yōu)化方法。蔡延光等 (1998)應(yīng)用并行表搜索法和模擬退火法針對簡單情形對滿載問題進(jìn)行了求解 ［３］［５］ 。 分類 VSP 被 提 出 后 ， Linus (1981),Bodin 和 Golden(1981) , Bodin(1983) , Assad(1988) ,Desrochers, Lenstra和 Savelsbergh(1990)等許多學(xué) 者對 VSP從不同角度，按不同的標(biāo)準(zhǔn)進(jìn)行了分類。 按任務(wù)性質(zhì)分，有對弧服務(wù)問題 (如中國郵遞員問題 )和對點(diǎn)服務(wù)問題 (如旅行商問題 )以及混合服務(wù)問題 (如交通車線路安排問題 )。 按車場 (或貨場、配送中心等 )數(shù)目分，有單車場問題和多車場問題。 按車輛對車場的所屬關(guān)系分，有車輛開放問題 (車輛可以不返回其發(fā)出車場 )和車輛封閉問題 (車輛必須返回其發(fā)出車場 )。 由于情況的不同，車輛優(yōu)化調(diào)度問題的模型構(gòu)造及算法有很大的差別。 常用的基本問題有：旅行商問題、分派問題、運(yùn)輸問題、背包問題最短路問題、最小費(fèi)用流問題、中國郵路問題等。 算法 貨運(yùn)車輛優(yōu)化調(diào)度問題的求解方法非常 豐富，目前主要有以下四類： 系統(tǒng)仿真法 (Simulation ) 此方法最早由 Golden 和 Skiscim 于 1986 年提出，主要應(yīng)用于行車線路與物流中心區(qū)位的選擇，優(yōu)點(diǎn)在于可直接觀察系統(tǒng)安排的效率與效果，但由于問題的實際情況多變且具有不確定性，是否能將實際的配送情形系統(tǒng)邏輯化為仿真程序，往往令人質(zhì)疑。 精確解法 (Exact procedures ) 精確解法指可求出最優(yōu)解的算法，精確解法主要有： 分枝界定法 (Branch and Bound Approach)、割平面法 (Cutting Planes Approach)、網(wǎng)絡(luò)流算法 (Network Flow Approach)、動態(tài)規(guī)劃方法 (Dynamic Programming Approach)。 啟發(fā)式解法 (Heuristics) 由于上述三種方法的求解效率 較差，所以大部分的學(xué)者都致力于啟發(fā)式解法的發(fā)展。目前已提 6 出的啟發(fā)式算法很多，按 Cesar Rego 的分類法有以下四類： （ 1）算法 (Constructive Algorithm) 根據(jù)一些準(zhǔn)則，每一次將一個不在線路上的點(diǎn)增加進(jìn)線路，直到所有的點(diǎn)都被安排進(jìn)線路為止。 構(gòu)造算法是最早提出用來解決旅行商問題 (Traveling Salesman Problem,簡稱 TSP)及 VSP的，這些方法一般速度快，也很靈活，但這類方法有時找到的解離最優(yōu)解差的很遠(yuǎn)。一般第一階段常用構(gòu)造算法，在第二階段常用的改進(jìn)技術(shù)有 2opt(Lin，1965)、 3opt(Lin Kernighan， 1973)和 Oropt(Or， 1976)交換法，這是一種在解的鄰域中搜索，對初始解進(jìn)行某種程度優(yōu)化的算法，以改進(jìn)初始解。這樣做通常會增加模型最終實現(xiàn)并被采用的可能性。 （ 4）改進(jìn)算法 (Improvement Algorithm) 從一個初始解開始，通過對當(dāng)前的解進(jìn)行反復(fù)地局部擾亂 (Perturbations)以達(dá)到較好的解。 亞啟發(fā)式算法包括表搜索算法 (Table Search)、模擬退火算法 (Simulated Annealing)、遺傳算法 (Geic Algorithm)和神經(jīng)網(wǎng)絡(luò) (Neural Networks)方法。該類問題根據(jù)任務(wù)特征又分 為以下兩類： （ 1）集貨或送貨的車輛優(yōu)化調(diào)度 所有任務(wù)全是集貨點(diǎn)或全是送貨點(diǎn)，車輛空車從車場出發(fā)，去各貨主處裝滿貨后返回車場。 （ 2）集貨和送貨一體化的車輛優(yōu)化調(diào)度 每一項貨運(yùn)任務(wù)都有自己的集貨點(diǎn)和送貨點(diǎn)，車輛從車場出發(fā)，去某一任務(wù)的集貨地點(diǎn)裝貨后運(yùn)至其送貨地點(diǎn)卸貨（即裝卸混合），完成所有任務(wù)后返回車場。根據(jù)任務(wù)特征可分為以下兩類： （ 1）集貨或送貨的車輛優(yōu)化調(diào)度 載貨車輛由車場出發(fā)到幾個集貨點(diǎn)裝貨后返回車場（僅有裝貨），或是車輛出發(fā)到幾個送貨點(diǎn)卸貨（僅有卸貨）后返回車場。 研究的意義 目前有關(guān) VSP的研究，多致力于單一車種或多車種優(yōu)化調(diào)度問題，很少涉及結(jié)合時間窗口的 VSP問題。由于消費(fèi)者需求趨于多樣化，對送貨時間的要求日趨嚴(yán)格，尤其是運(yùn)送有時效性的商品，例如海鮮、花卉、蔬菜、水果等講究新鮮度的貨物，除了因缺貨造成的機(jī)會成本的損失外，由于配送不及時也會造成貨物價值的大大降低。 有時間窗的 VSP問題也稱為 VSPTW(Vehicle Scheduling Problem with Time Windows） ，根據(jù)時間約束的嚴(yán)格與否，分為軟時間窗和硬時間窗的 VSP。 研究的范圍 由于有時間窗約束的車輛優(yōu)化調(diào)度問題所牽涉的因素相當(dāng)多，本研究僅針對具有普遍性的物流中心予以探討，就研究范圍與假設(shè)界定如下： 僅考慮區(qū)位己知的單一物流配送中心和供應(yīng)商； 物流配送中心無缺貨的可能，而且商品種類單一； 物流配送中心已知顧客的基本配送資料 (需求量、地理位置、時間窗約束等 )； 8 物流配送中心擁有足夠數(shù)量的同類型配送車輛，即每輛車的載重量、時速相同。三者分述如下： 硬時間窗 (Hard Time Windows)：指配送車必須在特定時間區(qū)段 (如圖 21中的 ? ?le, )內(nèi)將貨品送達(dá)顧客手中，不論是遲到或早到都完全不予接受。 Desrochers (1988)曾指出硬時間窗寬度會影響尋優(yōu)程序，并提出時間窗寬度評價指標(biāo)，時間窗越寬則 VSPTW 問題越接近路線安排 (Routing)問題，越窄則越近似行程安排(Scheduling)問題。圖 22就是一種可能的懲罰函數(shù)。在實際的物流配送中，配送車輛如果能在最佳時段 (如圖 23 中的 ? ?le, 內(nèi)將貨物送到顧客處，則不處罰；若在圖 23 中的（ ? ?ea, 或 ? ?bl, ）時段內(nèi)才送達(dá)，則顧客的滿意度降低 (轉(zhuǎn)化為懲罰函數(shù) )，而且顧客不接受上述兩個時段以外的時間 （ ? ?a,?? 或 ? ??,b ）收貨。所以對每一部車輛來說，是一個旅行商問題 (TSP)。 行程安排 (Scheduling)問題 一般車輛優(yōu)化調(diào)度問題再加入時間窗約束，則必須考慮到達(dá)各顧客的先后順序，也就是行程安排問題。 遺傳算法的特點(diǎn) 同傳統(tǒng)的尋優(yōu)算法相比，遺傳算法具有以下特點(diǎn)： 算法對問題參數(shù)的代碼集起作用，而不是對參數(shù)本身起作用。 遺傳算法是從初始群體開始搜索的，而不是從單點(diǎn)開始搜索的。這種點(diǎn)到點(diǎn)的搜索方法在多峰值優(yōu)化問題中，容易誤入局部最優(yōu)解。 遺傳算法在求解時只使用適應(yīng)度函數(shù)的信息，而不使用導(dǎo)數(shù)及其他輔助信息。遺傳算法在優(yōu)化過程中，放棄使用這些輔助信息，具有廣泛適應(yīng)性。遺傳算法的初始種群本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息，通過選擇、交叉、變異操作能迅速 排除與最優(yōu)解相差極大的染色體。 Goldeberg對 GA的處理并行性進(jìn)行了合理的分析，指出了GA對模式的處理效率是 ? ?3no ， Holland稱之為 GA的“隱式并行性” ［５］ 。復(fù)制體現(xiàn)了向最優(yōu)解的逼近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。 遺傳算法的基本步驟和處理流程 遺傳算法的主要處理步驟是：首先構(gòu)造滿足約束條件的染色體。實際問題的染色體有多種編碼方式，染色體編碼方式的選取應(yīng)盡可能的符合問題約束，否則將影響計算效率。初始群體群體的染色體數(shù)量應(yīng)適當(dāng)選擇。適應(yīng)度函數(shù)基本上依據(jù)問題的目標(biāo)函數(shù)而定，是反映染色體優(yōu)劣的 唯一指標(biāo)，遺傳算法就是要尋得適應(yīng)度最大的染色體。第四是染色體的交叉。子代的產(chǎn)生是一個生殖過程，它產(chǎn)生了一個新解；最后是變異，新解產(chǎn)生過程中可能產(chǎn)生基因變異，變異使某些解的編碼發(fā)生變化，使解具有更大的遍歷性。 圖 31 遺傳算法的基本流程 遺傳算法的應(yīng)用 遺傳算法是 60年代由美國 J. Holland教授首先在《自然結(jié)合人工智能系統(tǒng)的適應(yīng)性》一書中提出的，是一種新興的自適應(yīng)隨機(jī)搜索方法，具有極強(qiáng)的魯棒性和內(nèi)在的并行計算機(jī)制，特別適合于非凸空間中復(fù)雜的多極值優(yōu)化和組合優(yōu)化，在機(jī)器學(xué)習(xí)、自動控制、機(jī)器人技術(shù)、電器自動化以及計算機(jī)和通信領(lǐng)域以取得了非凡的成就。對于復(fù)雜的函數(shù)優(yōu)化問題 (如非線性、不連續(xù)、多峰 值函數(shù)的優(yōu)化等 )和組合優(yōu)化問題 (如 VSP, TSP,01 背包問題、工作計劃問題 確定表示問題解答的染色體（編碼） 初始化染色體種群 計算每個染色體的適應(yīng)度 滿足終止條件？ 根據(jù)適應(yīng)度選擇串進(jìn)行復(fù)制 交叉 變異 輸出最優(yōu)解 否 是 14 制定等 )都有廣闊的發(fā)展前景。 機(jī)器學(xué)習(xí) 基于遺傳算法的機(jī)器學(xué)習(xí)也是遺傳算法應(yīng)用研究的一個重要方面。遺傳算法從其開始就與機(jī)器學(xué)習(xí)有著密切的聯(lián)系。 神經(jīng)網(wǎng)絡(luò) 遺傳算法的另一個 活躍的研究方向是在神經(jīng)網(wǎng)絡(luò)方面的應(yīng)用，這包括優(yōu)化神經(jīng)網(wǎng)絡(luò)的連接權(quán)系數(shù)、網(wǎng)絡(luò)的空間結(jié)構(gòu)等。 近些年來，人們在用遺傳算法解決現(xiàn)實中的各種組合優(yōu)化問題上進(jìn)行了探索，如在生產(chǎn)調(diào)度問題中的應(yīng)用、對一般 TSP (Traveling Salesman Problem,旅行商問題 )問題的求解都取得了一些成果 (Oliver和 Smith, 1989:Fogel, 1993 )。Malmb,1996。有專家斷言遺傳算法是用來解決NP完全問題和 NP難題的趨勢 ［８］ 。編碼方法決定了染色體的排列形式。設(shè)計優(yōu)良的編碼方案是遺傳算法的應(yīng)用難點(diǎn)之一。 二 進(jìn)制編碼 二進(jìn)制 編碼是最常用的編碼技術(shù)之一，許多數(shù)值與非數(shù)值優(yōu)化問題的解都可以用二進(jìn)制位串進(jìn)行編碼。二進(jìn)制編碼結(jié)構(gòu)簡單，易于進(jìn)行交叉、變異等遺傳操作。例如 7和 8的二進(jìn)制編碼分別為 0111和 Hamming懸崖（ Hamming cliffs） ,有可能降低遺傳算法的搜索效率。若在一開始就選取較高的精度，則串長很大，也會降低算法的效率。 15 Gray 編碼 Gray編碼的目的是為了克服二進(jìn)制編碼的 Hamming懸崖缺陷。 Gray 編碼的方法是首先對問題的解進(jìn)行二進(jìn)制編碼，再將二進(jìn)制編碼轉(zhuǎn)換為相應(yīng)的Gray編碼，然后進(jìn)行遺 傳操作，當(dāng)進(jìn)行適應(yīng)度計算時，再將 Gray編碼轉(zhuǎn)換為相應(yīng)的二進(jìn)制編碼。 實數(shù)向量編碼 在求解一些多維高精度優(yōu)化