前言

現代物流作為現代經濟的重要組成部分，在國民經濟和社會發(fā)展中發(fā)揮著重要作用。發(fā)展現代物流對于提高國民經濟運行的質量和效益、優(yōu)化資源配置、改善投資環(huán)境、促進企業(yè)結構調整、提高我國經濟實力等多方面都具有十分重要的意義。目前，國際上普遍把物流稱為“降低成本的最后邊界”，排在降低原材料消耗、提高勞動生產率之后的“第三利潤源泉”。隨著經濟全球化和信息化進程的不斷加快，物流業(yè)作為具有廣闊前景和增值功能的新興服務業(yè)，正在全球范圍內迅速發(fā)展，掀起“現代物流革命”。

配送是物流系統(tǒng)中的一個重要環(huán)節(jié)，它是指按客戶（包括零售商店、用戶等）的訂貨要求（包括在貨物種類、數量和時間等方面的要求），在配送中心進行分貨、配貨工作，并將配好的貨物及時送交收貨人的物流活動。配送是一種集集貨、分貨、配貨、配裝、送貨等多種功能為一體的物資流通方式。在配送業(yè)務中，配送車輛優(yōu)化調度問題的涉及面較廣，需要考慮的因素較多，對配送企業(yè)提高服務質量、降低物流成本、增加經濟效益的影響也較大。該問題是物流系統(tǒng)優(yōu)化的關鍵。

國外將配送車輛優(yōu)化調度問題歸結為VRP（Vehicle Routing Problem，車輛路徑問題）、VSP（Vehicle Scheduling Problem，車輛調度問題）和MTSP（Multiple Traveling Salesman Problem，多路旅行商問題）。該問題于1959年由Dantzig和Ramser提出后，很快便引起運籌學、應用數學、組合數學、圖論與網絡分析、物流科學、計算機應用等學科的專家以及運輸計劃制定者的極大重視，并一直是運籌學與組合優(yōu)化領域的前沿與熱點問題。在現實生產和生活中，郵政投遞問題、飛機、鐵路車輛、水運船舶及公共汽車的調度問題、電力調度問題、管道鋪設問題、計算機網絡拓撲設計問題等都可以抽象為配送車輛優(yōu)化調度問題。本書所研究的配送車輛優(yōu)化調度問題的求解算法對解決上述問題也是有效的。可見，本書研究配送車輛優(yōu)化調度問題的模型和算法，具有重要的理論和現實意義。

本書展示的是作者多年從事配送車輛優(yōu)化調度問題研究的成果，包括作者的博士學位論文，作者在學術期刊和學術會議上發(fā)表的學術論文以及作者指導研究生的碩士學位論文。本書主要展示了以下創(chuàng)新研究成果。

（1）在對配送車輛優(yōu)化調度問題的構成要素包括貨物、車輛、配送中心、客戶、運輸網絡、約束條件和目標函數等的屬性進行系統(tǒng)分析和描述的基礎上，分別建立了無時限單向、有時限單向、無時限雙向和有時限雙向單配送中心車輛優(yōu)化調度問題，無時限和有時限多配送中心車輛優(yōu)化調度問題以及動態(tài)車輛配送優(yōu)化調度問題和動態(tài)網絡配送車輛優(yōu)化調度問題的基于直觀描述的數學模型。上述模型均考慮了較為接近實際的約束條件和目標函數，并具有簡單、直觀、易于理解、易于設計算法求解及可擴充性強等特點。

（2）為構造配送車輛優(yōu)化調度問題的求解算法提出了兩種新的解的表示方法（即客戶直接排列的表示方法及車輛和客戶對應排列的表示方法）和兩種新的鄰域搜索策略（即逆轉法和插入法）。進而分別針對多種解的表示方法設計了相應的解的評價方法和具體的鄰域選點策略。

（3）分別設計和實現了無時限單向配送車輛優(yōu)化調度問題的爬山算法、禁忌搜索算法、模擬退火算法和遺傳算法，并通過實驗計算分析了解的表示方法、鄰域選點策略、迭代搜索策略、個體編碼方法、選擇策略、交叉算子、變異算子等算法策略及搜索次數、禁忌長度、初始溫度、降溫速度、交叉概率、變異概率、群體規(guī)模、進化代數等運行參數對算法性能的影響，結果表明，選擇合適的算法策略和運行參數，有利于提高算法性能。

（4）通過實驗計算比較了爬山算法、禁忌搜索算法、模擬退火算法和遺傳算法的尋優(yōu)性能：爬山算法具有很高的收斂速度，對于規(guī)模較小的問題尋優(yōu)效果較好，對于規(guī)模較大或很大的問題尋優(yōu)效果較差，且算法的穩(wěn)健性較差；禁忌搜索算法和模擬退火算法性能接近，它們具有比爬山算法更好的尋優(yōu)性能，可以得到質量很好的解，且具有較強的穩(wěn)健性；遺傳算法對于規(guī)模較小的問題尋優(yōu)結果較好，但對于規(guī)模較大的問題尋優(yōu)結果較差，在相同的搜索次數下，基本遺傳算法的尋優(yōu)結果遠不如禁忌搜索算法和模擬退火算法，甚至不如爬山算法，遺傳算法的計算效率遠不如爬山算法，也不如禁忌搜索算法和模擬退火算法。

（5）針對基本遺傳算法的不足，提出將局部搜索能力較強的爬山算法和模擬退火算法與基本遺傳算法結合，并構造了求解配送車輛優(yōu)化調度問題的兩種混合遺傳算法：爬山遺傳算法和模擬退火遺傳算法。實驗計算結果表明：兩種混合遺傳算法可以在一定程度上克服基本遺傳算法在局部搜索能力方面的不足，從而能得到比基本遺傳算法更好的計算結果；兩種混合遺傳算法的計算效率均高于基本遺傳算法；兩種混合遺傳算法的尋優(yōu)性能均不如禁忌搜索算法和模擬退火算法。

（6）提出了更具一般性的雙向配送車輛優(yōu)化調度問題。針對硬時間窗和軟時間窗雙向配送車輛優(yōu)化調度問題中因每個客戶有供應和需求兩個時間窗從而造成求解困難的情況，提出了一種通過拆分客戶的方法將雙時間窗問題轉化為單時間窗問題進行求解的思路。

（7）設計了多配送中心車輛優(yōu)化調度問題的求解策略，即利用距離最近分配法劃定每個配送中心服務的客戶，進而將一個多配送中心車輛優(yōu)化調度問題轉化成多個單配送中心車輛優(yōu)化調度問題進行求解。

（8）分別設計并實現了硬時間窗單向、軟時間窗單向、無時限雙向、硬時間窗雙向和軟時間窗雙向配送車輛優(yōu)化調度問題以及無時限和有時限多配送中心車輛優(yōu)化調度問題的禁忌搜索算法和模擬退火算法，實驗計算結果表明：用禁忌搜索算法和模擬退火算法求解上述配送車輛優(yōu)化調度問題均可以取得很好的計算結果，且算法的計算結果較穩(wěn)定，計算效率也較高。

（9）研究了考慮車輛故障、車輛多次巡回配送等實際因素的動態(tài)車輛配送優(yōu)化調度問題。為該問題設計了“制定整體優(yōu)化配送計劃+實時局部優(yōu)化調度”的兩階段求解策略。設計和實現了求解該問題的“禁忌搜索+局部搜索”算法，既充分利用了禁忌搜索算法的優(yōu)勢，又通過局部搜索算法實現了對多次巡回車輛動態(tài)信息的實時處理，完成了局部調整的優(yōu)化調度，從而使該問題得到滿意的解決。

（10）構造了動態(tài)網絡配送車輛優(yōu)化調度問題的遺傳算法。在制定配送計劃階段，可以得到在保證一定的顧客服務水平基礎上運距最短、成本最小的配送方案。在配送計劃的執(zhí)行階段，借助于GPS可隨時得到車輛的在途位置，從而可以對后續(xù)顧客的服務保證率進行核定。若出現按計劃不能滿足對后續(xù)顧客的服務保證時，可以在最早的時間內知道計劃可能違約的時間，從而可為采取適宜的補救措施贏得時間。

本書除突出強調內容的創(chuàng)新性外，還具有以下特點。

（1）循序漸進性。本書是按照先簡單、后復雜的順序循序漸進地研究各類配送車輛優(yōu)化調度問題的。即先研究無時限問題，后研究有時限問題；先研究單向問題，后研究雙向問題；先研究單配送中心問題，后研究多配送中心問題；先研究靜態(tài)問題，后研究動態(tài)問題。這既符合科學研究規(guī)律，也增加了本書的易讀性。

（2）技術路線的科學性。本書對每類配送車輛優(yōu)化調度問題基本都按照“問題描述→數學建模→算法設計→實例計算→算法分析”的思路開展研究，技術路線清晰、合理，也體現了理論與實踐的有機結合。

（3）實用性。本書在介紹各種配送車輛優(yōu)化調度問題的優(yōu)化算法時，均在設計各種算法要素的基礎上，給出了詳細的計算機編程思路，并在附錄中給出了禁忌搜索算法和模擬退火算法的C語言程序源代碼，而且都進行了實例計算。這有利于有關人員將這些優(yōu)化算法嵌入到實際的物流管理和優(yōu)化軟件中，用以解決實際問題。

（4）讀者的廣泛性。本書可作為物流管理、物流工程、交通運輸等相關專業(yè)師生的參考書，也可供物流行業(yè)的管理人員、專業(yè)技術人員及軟件設計、開發(fā)人員學習參考。

本書得到了北京交通大學學術專著出版基金的資助和北京交通大學交通運輸學院學術著作出版資助獎勵，在此表示衷心的感謝！

作者的博士生導師胡思繼教授、妻子張建琴工程師、碩士研究生石洪波工程師為本書的完成做出了很大貢獻，在此深表謝意！并對為本書的出版提供幫助的單位、個人及本書參考文獻的作者表示誠摯的感謝！

由于作者水平有限，書中難免有不當或錯誤之處，希望專家、學者和廣大讀者不吝指正。

郎茂祥

2008年12月于北京交通大學