第 1 章  緒論

1.1  研究背景

近年來，國內(nèi)快遞行業(yè)發(fā)展勢頭強勁迅猛。根據(jù)國家郵政局最新統(tǒng)計數(shù)據(jù)顯示：2014 年，全國快遞服務企業(yè)累計完成業(yè)務量為 139.6 億件，同比增長 51.9%；全年度累計完成營業(yè)收入為 2045.4 億元，同比增長 41.9%，提前并超額完成了“十二五”制定的總目標�？爝f行業(yè)作為現(xiàn)代服務業(yè)的一部分，在改善人民生活和推動經(jīng)濟發(fā)展方面發(fā)揮著重要的作用，特別是近年來伴隨著電子商務的蓬勃發(fā)展。據(jù)統(tǒng)計，快遞行業(yè)的業(yè)務量將近有 70%來自于電子商務，行業(yè)相關(guān)從業(yè)人員超過 200 萬人。  然而，快遞行業(yè)在高速發(fā)展的同時，自身也暴露了不少問題。例如：快遞企業(yè)普遍存在小散弱等局面、綜合運營管理效率低下、服務水平不高等問題，總而言之，快遞行業(yè)整體水平還不能滿足當前國民經(jīng)濟發(fā)展的實際需要。因此，提升運營效率，改善服務水平，是當下快遞行業(yè)不得不面對和解決的重大課題。在此背景下，《快遞服務“十二五”規(guī)劃》報告則重點提出了“加強服務能力建設，提升服務水平和質(zhì)量”等要求。此外，《“十二五”綜合交通運輸體系規(guī)劃》報告則進一步提出了要實現(xiàn)“大力發(fā)展便捷、高效快遞服務”等目標。一方面，政府積極出臺相應政策，引導快遞企業(yè)轉(zhuǎn)換升級和改善服務。另一方面，政府又積極引入競爭機制加強市場管理，促使整個快遞行業(yè)提升服務水平。

城市快遞配送作為快遞服務的最后環(huán)節(jié)，是快遞物流的“最后一公里”，對提升企業(yè)服務水平起著關(guān)鍵的決定性作用。由于快遞配送直接面向于終端客戶，其服務水平的高低直接影響著客戶滿意度和企業(yè)形象，同時也反過來間接影響企業(yè)的競爭力和市場份額的占比。因此，提升城市快遞配送效率就成為了快遞企業(yè)改善服務水平以贏得市場的關(guān)鍵手段。在城市快遞系統(tǒng)配送中，車輛路徑規(guī)劃作為其中的一項日常工作，在降低運營成本、改善客戶服務以及提高效益方面扮演著舉足輕重的作用，因此，有必要對快遞車輛的路徑優(yōu)化展開研究。而在實際的路徑規(guī)劃中，往往需要考慮多方面因素，例如：車輛容量、行駛距離、客戶時間窗、不確定性限制等等，這些因素將直接決定著城市快遞配送最終優(yōu)化的結(jié)果。同時，快遞企業(yè)在城市配送過程中，除了考慮成本因素外，通常還會兼顧滿足客戶需求等其他目標�；诖�，本文對城市快遞配送條件下的多目標車輛路徑優(yōu)化問題展開了研究。

.....................

1.2 研究目的和意義

本文研究的是城市快遞配送條件下的多目標車輛路徑優(yōu)化問題，針對城市快遞配送特點構(gòu)建相應模型，通過調(diào)整和改進遺傳算法求出最優(yōu)解以實現(xiàn)快遞配送路徑的優(yōu)化，從而為城市快遞配送服務提供有力的理論支撐和決策支持。

本文研究的目的主要表現(xiàn)在三個方面：首先，根據(jù)快遞配送的實際情況，構(gòu)建更有效的多目標車輛路徑優(yōu)化模型；其次，針對該模型的求解，調(diào)整和改進遺傳算法。最后，通過應用以上構(gòu)建的模型的采用的算法，為決策者提供建議。

本文研究的意義主要表現(xiàn)兩個方面：其一，本文采用遺傳算法來求解多目標帶時間窗的快遞配送路徑優(yōu)化問題，其模型構(gòu)建、遺傳算法應用和改進以及相關(guān)參數(shù)設定等一套思維方法給其他研究者提供了一定的參考；其二， 快遞配送車輛路徑規(guī)劃作為城市快遞服務的一個重要的環(huán)節(jié)，車輛調(diào)度效率的改進既可以降低快遞企業(yè)的運營成本，也可提升企業(yè)的服務質(zhì)量，對改善企業(yè)經(jīng)營狀況和企業(yè)形象有著重要的意義。本文結(jié)合實例求證該模型，其研究結(jié)論能夠給快遞企業(yè)提供一定的實施依據(jù)和管理建議。

...........................

第 2 章  城市快遞配送路徑優(yōu)化的理論基礎(chǔ)

2.1 城市快遞配送相關(guān)理論

2.1.1 城市快遞配送的特點

城市快遞配送的主要特點包括以下幾個方面：

（1）經(jīng)濟性    快遞企業(yè)在開展城市快遞配送業(yè)務的首要目標是獲取一定的經(jīng)濟效益，由于快遞配送屬于“最后的一公里”環(huán)節(jié)，幾乎不產(chǎn)生直接的經(jīng)濟效益，從而快遞企業(yè)只能在降低成本開支方面苦下功夫，具體措施可以通過采取合理安排配送路徑、選擇適當容量的配送車輛、車輛保養(yǎng)以及加強信息管理等途徑予以實現(xiàn)其效益目標。

（2）時效性     時效性是指快遞企業(yè)要在規(guī)定的時間范圍內(nèi)將快遞送達至顧客手中，隨著電子商業(yè)的蓬勃發(fā)展以及消費者對時間的緊迫感越發(fā)強烈，很多企業(yè)在城市配送中積極開展了“即日達"、“次早達”業(yè)務，通過縮短客戶的等待時間以此來提高顧客滿意度。對于城市快遞配送，隨著行業(yè)競爭的加強以及消費者權(quán)益的強勢，快遞企業(yè)在除了考慮經(jīng)濟效益之外，更應重視快遞時效相應的服務質(zhì)量。

（3）不確定性    城市快遞配送由于受城市交通狀況、天氣氣候、車輛保養(yǎng)情況、快遞員對路況的熟悉程度、車輛調(diào)度安排、城市突發(fā)事件以及客戶接收響應等因素的影響，從而使快遞車輛在行駛過程中到達客戶點的時間存在不確定性，甚至到達客戶點之后等待客戶接收快遞，由于在該時間范圍內(nèi)客戶的響應速度受多方面因素影響，例如：到達接收點的路程、該時間段的繁忙程度、查看接收信息的時點等等，同樣導致客戶服務時間的不確定性。 

（4）多任務性     現(xiàn)代快遞企業(yè)在開展城市快遞配送業(yè)務時，不得不在運營成本和服務質(zhì)量之間保持權(quán)衡。傳統(tǒng)意義上的以純粹追求經(jīng)濟效益為目標的生產(chǎn)方式在如今日益發(fā)展和激烈競爭的現(xiàn)代城市越來越顯得不太可行，從而使現(xiàn)代快遞企業(yè)從傳統(tǒng)的成本控制經(jīng)營理念向現(xiàn)代客戶服務經(jīng)營理念轉(zhuǎn)變，從單目標任務向多目標任務轉(zhuǎn)變。例如：快遞企業(yè)針對快遞員的工作滿意度平衡快遞員的工作載荷，針對某些顧客群體安排同一快遞員服務以此加強客戶關(guān)系等。

.........................

2.2  車輛路徑問題相關(guān)理論

2.2.1 車輛路徑問題的概念和基本模型

Dantzig  & Rasmer（1959）首次提出車輛路徑問題（Vehicle  Routing Problem，VRP）。車輛路徑問題是運籌學領(lǐng)域中的一大類重要問題，它是物流配送中的一項重要研究內(nèi)容。一般定義為：制定合理的車隊行車線路，使車輛按照一定的秩序依次為若干客戶進行服務，在車隊滿足既定的約束條件（如車輛容量限制、時間窗約束、最大行駛距離約束等）的同時，還能夠?qū)崿F(xiàn)一定的任務和目標（如車輛使用數(shù)目最少、車隊總行駛路程最短、車隊總行程時間最短等）。車輛路徑問題自從被命名提出以來，深受國內(nèi)外學者的廣泛關(guān)注和研究。經(jīng)典VRP模型，可用如下數(shù)字語言描述：

目標函數(shù)（2-1）表示車隊總運輸成本最低；約束（2-2）表示為車輛的最大載重約束；約束（2-3）確保各個客戶點的運輸任務有且僅由一輛車服務，所以的任務總共由K輛車完成；約束（2-4）、（2-5）保證車輛都從配你送中心出發(fā)并最終返回到配送中心，且所有的客戶點都被服務到。

......................

第 3 章 多目標 VRPTW 模型構(gòu)建和遺傳算法求解 .................. 23

3.1  多目標 VRPTW 模型構(gòu)建 ................ 23

3.1.1  問題描述 .............. 23

3.1.2  模型假設 ................ 23

3.1.3  多目標 VRPTW 模型構(gòu)建.............. 24

3.2  基于遺傳算法的求解.................. 26

3.2.1  遺傳編碼和初始種群生成 ..............26

3.2.2  約束條件處理和適應度函數(shù)評價 ............... 27

第 4 章 實例分析 ................... 32

4.1  實例分析 ...................... 32

4.1.1  實例介紹 ................... 32

4.1.2  運算結(jié)果 ........... 33

4.1.3  結(jié)果分析 ................ 34

第 4 章  實例分析

4.1 實例分析

為了驗證本文設計的遺傳算法的有效性和可行性，本文將采用對比分析方法，即結(jié)合相關(guān)文獻中具體的多目標 VRPTW 實例，通過 Visual C++6.0 匯編軟件對本文算法予以運算實現(xiàn)，并將最終的運行結(jié)果和文獻進行對比，如果運行結(jié)果在結(jié)果優(yōu)化方面有所改善，即可說明本文算法在求解多目標VRPTW 問題方面具有一定的操作性和可行性。

4.1.1  實例介紹

本文的計算實例源于文獻，基本信息如下： 某公司擁有 1 個配送中心，服務于 80 個客戶點，各個客戶點的坐標、需求量如表 4-1 所示。該公司擁有 2 種配送車型，車輛數(shù)目分別為 11 和 2 輛，，配送最大允許容量分別為 500 和 400。所有客戶要求的時間窗口均為 11：00-12：00，軟時問窗口為 10：30-11：00 和 12：00-12：30，公司從上午 10：00 出發(fā)，依次展開配送行程安排計劃。

.......................

結(jié)論

本文基于近年來國內(nèi)快遞行業(yè)取得迅猛發(fā)展以及人們對快遞行業(yè)提出更高服務要求的背景，同時根據(jù)國內(nèi)外研究現(xiàn)狀，重點研究了快遞配送條件下的多目標車輛路徑優(yōu)化問題。首先根據(jù)城市快遞的相關(guān)特點，構(gòu)建了多目標VRPTW 模型，重點考慮了車型因素和不確定時間因素。其中，不確定時間因素假定車輛行駛時間和客戶服務時間呈正態(tài)分布規(guī)律。同時，針對該模型，采取改進遺傳算法對其進行求解。其中在適應度函數(shù)設計上，采用無量綱統(tǒng)一和權(quán)重配比，將多目標函數(shù)問題轉(zhuǎn)化為單目標函數(shù)問題。其次，在遺傳算子設計上，在選擇遺傳操作、交叉遺傳操作和變異遺傳操作環(huán)節(jié)保存最優(yōu)個體，從而提高了種群整體的進化程度。最后，結(jié)合文獻實例，對該算法進行了驗證。此外，還通過算例進一步分析了相關(guān)因素對實驗結(jié)果的影響。

根據(jù)實驗結(jié)果顯示，本文遺傳算法的最優(yōu)結(jié)果均優(yōu)于實驗組，從而驗證了該遺傳算法的有效性可行性。此外，還驗證了相關(guān)因素對實驗結(jié)果的影響。其中，時間窗因素對優(yōu)化結(jié)果有著重要的影響作用，以及多車型相對于單車型在路徑優(yōu)化方面具有更大的優(yōu)越性。因此，對快遞企業(yè)來說，適時減少時間窗懲罰可以改善服務，增加車型的多樣性可以降低配送成本。

由于快遞配送作為路徑優(yōu)化的一個重要課題，本文研究還存在不少局限。首先，在快遞配送過程中，沒有考慮快遞攬收情況。在實際的快遞服務中，通�？爝f的遞送和攬收工作是同時進行的，學者們可以就此展開深入研究；其次，在實際的快遞配送服務中，用戶需求和服務過程存在諸多不確定性因素，有必要對多配送中心、隨機需求、模糊時間窗和攬收一體化等條件下的動態(tài)規(guī)劃模型進行展開和分析；最后，在對模型的求解算法上，本文只討論了遺傳算法，今后的研究中可將遺傳算法與其它啟發(fā)式算法相結(jié)合起來，進一步來求解復雜的車輛路徑問題。

參考文獻（略）