第 1 章  緒論

1.1  研究背景

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

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

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

1.2 研究目的和意義

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

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

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

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

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

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

2.1.1 城市快遞配送的特點(diǎn)

城市快遞配送的主要特點(diǎn)包括以下幾個(gè)方面：

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1.2  模型假設(shè) ................ 23

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

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

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

3.2.2  約束條件處理和適應(yīng)度函數(shù)評(píng)價(jià) ............... 27

第 4 章 實(shí)例分析 ................... 32

4.1  實(shí)例分析 ...................... 32

4.1.1  實(shí)例介紹 ................... 32

4.1.2  運(yùn)算結(jié)果 ........... 33

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

第 4 章  實(shí)例分析

4.1 實(shí)例分析

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

4.1.1  實(shí)例介紹

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

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

結(jié)論

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

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

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

參考文獻(xiàn)（略）