1 緒論

1.1 研究背景和意義

大數(shù)據(jù)在物流企業(yè)中的應(yīng)用越來(lái)越受到人們關(guān)注，物流配送路線設(shè)計(jì)過(guò)程中會(huì)產(chǎn)生數(shù)以百萬(wàn)的數(shù)據(jù)信息，但大部分企業(yè)卻未能有效地利用這些數(shù)據(jù)來(lái)進(jìn)行線路優(yōu)化。而且傳統(tǒng)的路徑優(yōu)化算法無(wú)法應(yīng)對(duì)如今復(fù)雜的城市道路交通情況下，物流配送路線的有效快速生成。在現(xiàn)有的路徑優(yōu)化算法中加入道路交通信息已成為必然的趨勢(shì)。而配送客戶的急劇增加和考慮道路交通信息，使得不僅數(shù)據(jù)規(guī)模急劇增加，對(duì)數(shù)據(jù)處理的復(fù)雜程度也隨之增加。傳統(tǒng)的單個(gè)計(jì)算機(jī)計(jì)算速度越來(lái)越不能滿足大規(guī)模配送路線優(yōu)化所需的求解質(zhì)量和運(yùn)算速度要求。

本文通過(guò)在遺傳算法模型中加入車(chē)道數(shù)量、道路是否禁止掉頭、車(chē)輛速度三個(gè)道路交通狀況量化因子對(duì)配送路線進(jìn)行優(yōu)化，對(duì)于提高遺傳算法的精確性和實(shí)時(shí)性有一定意義。本文對(duì)貴陽(yáng)煙草物流配送中心的實(shí)證分析也為大數(shù)據(jù)時(shí)代到來(lái)企業(yè)面對(duì)大量數(shù)據(jù)，，如何進(jìn)行企業(yè)物流配送信息化建設(shè)提供一個(gè)參考的發(fā)展方向。對(duì)于配送路線優(yōu)化過(guò)程中的大量數(shù)據(jù)，本文使用 Hadoop 環(huán)境下的 Mapreduce對(duì)物流配送的動(dòng)態(tài)優(yōu)化算法進(jìn)行編程實(shí)現(xiàn)，對(duì)于大數(shù)據(jù)分析工具 Mapreduce 在物流配送路線優(yōu)化中的應(yīng)用處理有一定的研究參考價(jià)值。

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

1.2 國(guó)內(nèi)外研究現(xiàn)狀

1.2.1 路線優(yōu)化的國(guó)內(nèi)外研究現(xiàn)狀

1.國(guó)外研究現(xiàn)狀

路線優(yōu)化研究的核心問(wèn)題,即 VRP(Vehicle Routing Problem,車(chē)輛路徑問(wèn)題)。VRP 最早由 Dantzig 和 Ramser 于 1959 年提出。隨后 Clark 和 Wright 在對(duì)上述VRP 方法進(jìn)行改進(jìn)的基礎(chǔ)上提出了改進(jìn)啟發(fā)式 Saving 算法。至此以后各學(xué)科的研究人員以及物流運(yùn)輸行業(yè)的管理者很快便對(duì)車(chē)輛路徑問(wèn)題開(kāi)始重視，并對(duì)其從多個(gè)維度做了比較詳細(xì)深入的研究。  Bedin  于  1983  年通過(guò)發(fā)表總結(jié)性的論文將前人的各研究成果進(jìn)行了整理匯總，Daniele  和  Toth  也于 2002  年把各不同學(xué)科研究人員對(duì) VRP 問(wèn)題的研究進(jìn)展進(jìn)行匯總編制成書(shū)，并進(jìn)行出版。對(duì)車(chē)輛路徑優(yōu)化問(wèn)題的研究已經(jīng)取得了豐富的且具有代表性的成果,各算法從本質(zhì)上可分為精確算法和啟發(fā)式算法兩大類(lèi)。

（1）精確算法

精確算法通過(guò)采用數(shù)學(xué)手段和建立相應(yīng)的求解模型，表示并計(jì)算最優(yōu)路線。它是解決路徑優(yōu)化問(wèn)題比較早的一種算法。具體有包括分支定界法以及改進(jìn)后的結(jié)合了下界和分支定界后的改進(jìn)算法,將 m-TSP 轉(zhuǎn)化為 1-TSP.精確算法的主要特點(diǎn)是通過(guò)有嚴(yán)密邏輯且復(fù)雜的數(shù)學(xué)運(yùn)算，來(lái)計(jì)算出較高質(zhì)量的解。而當(dāng)物流配送規(guī)模急劇增加時(shí)，精確算法指數(shù)爆炸對(duì)缺陷就會(huì)暴露，這就限制了精確算法的應(yīng)用范圍，使其在實(shí)際應(yīng)中很少發(fā)揮實(shí)踐作用，而只能對(duì)規(guī)模有限的車(chē)輛路徑問(wèn)題進(jìn)行求解。

（2）啟發(fā)式算法

啟發(fā)式算法是通過(guò)對(duì)過(guò)去經(jīng)驗(yàn)的歸納推理和實(shí)驗(yàn)分析從而解決 VRP 問(wèn)題的方法，它與精確算法的不同也表現(xiàn)在這里。它通常能夠在計(jì)算的復(fù)雜性以及解的優(yōu)劣性中尋求到平衡，因此被學(xué)者廣泛的釆用和研究。啟發(fā)式算法分構(gòu)造啟發(fā)式算法、改進(jìn)啟發(fā)式算法和亞啟發(fā)式算法三大類(lèi)。

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

2 大量物流配送線路優(yōu)化思路

2.1  物流配送區(qū)域劃分概述

配送區(qū)域的劃分方法有成千上萬(wàn)種，而采用不同的方法會(huì)使區(qū)域劃分的最后結(jié)果千差萬(wàn)別，因此選擇一種合理的、符合本論文需要的區(qū)域劃分算法對(duì)各個(gè)配送小區(qū)域的產(chǎn)生乃至本文最后的優(yōu)化路線都是極為重要的。選擇一種配送區(qū)域劃分方法首先應(yīng)該做的是就是透徹理解所要解決的問(wèn)題，在對(duì)問(wèn)題根本理解的基礎(chǔ)上，滿足以下幾個(gè)基本條件：

1）初始劃分區(qū)域不能疊加，不能覆蓋； 

2）每個(gè)小區(qū)域內(nèi)的個(gè)體位置相距較近，這樣能節(jié)省車(chē)輛運(yùn)送貨物耗費(fèi)在路上的時(shí)間； 

3）為了使配送工作量保持均勻，避免出現(xiàn)配送路程相近卻配送量差距較大的不均衡現(xiàn)象，每個(gè)小區(qū)域的配送量要大概保持相等。

4）每一輛配送車(chē)量一次運(yùn)送所走的總路程應(yīng)大致保持相等。 

現(xiàn)有的常用區(qū)域劃分方法有：掃描法和聚類(lèi)算法。掃描法是 Gillett 和 Miller于 1974 年所提出的求解車(chē)輛路線問(wèn)題(Vehicle Routing Problem，VRP)的方法，此方法采用先分群再排路線的方式。一般分為兩階段性步驟：第一階段，把各配送戶的位置使用極坐標(biāo)表示，然后將任一配送戶作為起點(diǎn)，以配送車(chē)容量為客戶分群的限制條件，以該配送點(diǎn)為零點(diǎn)按時(shí)針的方向，進(jìn)行客戶分群。第二階段，使用旅行商問(wèn)題求解算法，解決客戶群的配送路線問(wèn)題。1983 年有專家將此方法應(yīng)用于求解時(shí)窗限制車(chē)輛路線問(wèn)題（vehicle routing problems with time windows，VRPTW），比原掃描法改進(jìn)的地方是在第二階段求解客戶配送路線問(wèn)題時(shí)，此算法不僅使用了插入法而且還對(duì)配送時(shí)間可行性進(jìn)行驗(yàn)證，只要不能滿足時(shí)間窗約束的配送點(diǎn)，就不能歸到一條配送線路中去。當(dāng)全部客戶都?xì)w入完成及所有客戶都已配送完，此時(shí)路線的建立完成；當(dāng)有顧客沒(méi)有被歸入，則對(duì)剩余的尚未被歸入的客戶重新進(jìn)行掃描與插入操作，直到所有的顧客點(diǎn)都配送完為止。如上所述，掃描法的每種考慮情況使得其要進(jìn)行復(fù)雜的計(jì)算，當(dāng)客戶數(shù)驟增時(shí)掃描法的計(jì)算量呈指數(shù)增長(zhǎng)，這使其求解的有效性大大的降低。

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

2.2 k-means 聚類(lèi)算法在物流配送區(qū)域劃分過(guò)程中的應(yīng)用

2.2.1 k-means 聚類(lèi)算法介紹

J.B.MacQueen 在 1967 年提出了 K-means 聚類(lèi)算法，其特點(diǎn)是同一聚類(lèi)內(nèi)各點(diǎn)之間盡量緊密，不同聚類(lèi)之間各點(diǎn)盡可能的分開(kāi)。算法的好處是能有效的處理大量數(shù)據(jù)中各不同信息之間雜亂的關(guān)系。K-means 聚類(lèi)算法進(jìn)行的基礎(chǔ)是要已知聚類(lèi)的具體個(gè)數(shù)，在此基礎(chǔ)上，再對(duì)大量數(shù)據(jù)信息采用聚類(lèi)計(jì)算，最后計(jì)算所得解是 k  個(gè)聚類(lèi)中心及其計(jì)算后得出的包含在各個(gè)聚類(lèi)中的的具體數(shù)據(jù)。K-means聚類(lèi)算法不可能只計(jì)算一次就得出最佳結(jié)果，而是需要通過(guò)不斷的迭代修正，其計(jì)算結(jié)果才會(huì)越來(lái)越接近于最優(yōu)解，才能有較好的聚類(lèi)結(jié)果。

k-means 聚類(lèi)算法在物流配送區(qū)域劃分過(guò)程中的應(yīng)用 配送區(qū)域劃分的具體過(guò)程：

1）首先收集整個(gè)物流配送區(qū)域內(nèi)各個(gè)配送點(diǎn)的地理位置（即經(jīng)緯度坐標(biāo)）；

2）根據(jù)配送點(diǎn)的密集程度把配送區(qū)域劃分為 k 個(gè)聚類(lèi)，并選取相應(yīng)的初始聚類(lèi)中心 K=1，2，3…k； 3）計(jì)算除聚類(lèi)中心外其他配送點(diǎn)到各個(gè)聚類(lèi)中心的歐式距離。按照與聚類(lèi)中心距離的遠(yuǎn)近及聚類(lèi)規(guī)模的大小完成對(duì)象的分配。

4）對(duì)各個(gè)聚類(lèi)內(nèi)點(diǎn)的經(jīng)緯坐標(biāo)求平均值，得出新的聚類(lèi)中心。

5）新計(jì)算出的聚類(lèi)中心與之前的聚類(lèi)中心進(jìn)行比較，如果聚類(lèi)中心發(fā)生明顯變化，重復(fù) 3）的操作，否則轉(zhuǎn)

6） 6）輸出聚類(lèi)結(jié)果。

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

3 大量物流配送路線的 Mapreduce 實(shí)現(xiàn) ................ 23

3.1Hadoop 技術(shù)構(gòu)架 ............... 23

3.2 分布式文件系統(tǒng)（HDFS） ................... 23

4 實(shí)證分析 ................... 30

4.1 貴陽(yáng)煙草物流配送中心配送活動(dòng)現(xiàn)狀 ............... 30

4.2 貴陽(yáng)煙草配送路線優(yōu)化思路 .................. 30

5 結(jié)束語(yǔ) ....................... 42

5.1 研究結(jié)論及本論文的創(chuàng)新點(diǎn) ...... 42

5.2 展望 ...................... 42

4 實(shí)證分析

4.1 貴陽(yáng)煙草物流配送中心配送活動(dòng)現(xiàn)狀

貴陽(yáng)市煙草物流配送中心負(fù)責(zé)貴陽(yáng)市七個(gè)市區(qū)及貴陽(yáng)市所轄三縣一市煙草的配送。配送終端既有大型超市、便利店等需求量大而集中的地方，也包括酒店、零售鋪等需求量小而散的地方。配送總用量有 2 萬(wàn)戶左右�，F(xiàn)有配送路線 160 余條，配送車(chē)輛 30 量。每日根據(jù)營(yíng)銷(xiāo)中心傳遞的訂單數(shù)據(jù)分多個(gè)波次進(jìn)行配送，配送量、配送范圍和配送復(fù)雜性均較大，卷煙送貨任務(wù)十分艱巨。貴陽(yáng)市卷煙現(xiàn)行送貨體系存在著以下一些問(wèn)題：

（1）路線重疊設(shè)置現(xiàn)象較為嚴(yán)重。現(xiàn)在使用的路線，主要是靠配送管理人員的實(shí)際經(jīng)驗(yàn)逐漸調(diào)整、增加形成的，線路間有一定的重復(fù)，實(shí)際配送中司機(jī)以及配貨員按照經(jīng)驗(yàn)挑選合適的路徑進(jìn)行配送，雖然有優(yōu)化作用，但是不具有理論依據(jù)，沒(méi)有使用信息化技術(shù)手段進(jìn)行精確計(jì)算，缺乏整體考慮，尚未實(shí)現(xiàn)最佳的配送路線設(shè)置。

（2）油耗大，成本較高。由于路線重復(fù)、空駛距離過(guò)長(zhǎng)，以及送貨波次間缺乏整體調(diào)度等原因，造成配送線路加長(zhǎng)，配送效率降低，因此必然導(dǎo)致有關(guān)的送貨成本包括汽車(chē)油耗，人員費(fèi)用等的增加，帶來(lái)總的配送成本的增加。同時(shí)，因?yàn)榫頍熶N(xiāo)售存在明  顯的季節(jié)波動(dòng)性，容易造成忙閑不均，平時(shí)冗余車(chē)輛和人工的閑置也會(huì)導(dǎo)致成本的增加，因此如何對(duì)配送路線進(jìn)行優(yōu)化，減少車(chē)輛和人員配置是提高效率同時(shí)降低成本的關(guān)鍵。

（3）不同線路人員配送量差距大，導(dǎo)致分工不平衡。由于現(xiàn)有線路劃分基本按照傳統(tǒng)經(jīng)驗(yàn)來(lái)劃分，造成有的車(chē)輛線路過(guò)長(zhǎng)，有的車(chē)輛線路卻過(guò)短。不同的配送路程量嚴(yán)重失衡。

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

5 結(jié)束語(yǔ)

5.1 研究結(jié)論及本論文的創(chuàng)新點(diǎn)

本論文通過(guò)：首先，定性的結(jié)合傳統(tǒng)的配送線路和定量的采用 k-means 聚類(lèi)算法對(duì)配送區(qū)域進(jìn)行分區(qū)；其次，構(gòu)建考慮了道路情況、交通情況的配送路線優(yōu)化模型，使用粗粒度并行遺傳算法實(shí)現(xiàn)大規(guī)模配送路線的計(jì)算實(shí)現(xiàn)；再次，采用大數(shù)據(jù)處理工具 mapreduce 對(duì) k-means 聚類(lèi)算法和粗粒度并行遺傳算法進(jìn)行編程實(shí)現(xiàn)。最后，以貴陽(yáng)煙草物流配送中心為實(shí)例，選取部分?jǐn)?shù)據(jù)對(duì)其物流配送線路進(jìn)行生成。在配送區(qū)域劃分方面，由原來(lái)的單純按行政區(qū)域劃分為七個(gè)，合并整理為五個(gè)。即將云巖區(qū)、南明區(qū)、小河區(qū)歸類(lèi)為一個(gè)，統(tǒng)稱為南明片區(qū)；烏當(dāng)區(qū)、白云區(qū)、金陽(yáng)新區(qū)和花溪區(qū)仍沿用行政區(qū)域的名稱，但是，有部分商戶在分區(qū)是被歸類(lèi)到了與行政區(qū)不一致的片區(qū)當(dāng)中。在配送線路優(yōu)化方面，本文采用的樣本數(shù)據(jù)為南明片區(qū)部分?jǐn)?shù)據(jù)，最后產(chǎn)生了 30 條配送線路。與以前貴陽(yáng)煙草的云巖、南明、小河三個(gè)區(qū) 33 條的線路相比，優(yōu)化了 3 條線路。說(shuō)明遺傳算法并結(jié)合Mapreduce 編程技術(shù)可以得出大量物流配送的具體線路，而且在總的配送工作量差不多的情況下，減少了配送線路數(shù)量，也就可以減少配送車(chē)輛的數(shù)量和配送人員的配置，說(shuō)明本論文對(duì)于優(yōu)化大量數(shù)據(jù)的物流配送路線有一定的促進(jìn)作用。

本論文的創(chuàng)新點(diǎn)為：1、在大量物流配送線路的優(yōu)化模型中考慮了交通情況和道路情況，使優(yōu)化模型更貼近現(xiàn)實(shí)也更準(zhǔn)確；2、將配送路線優(yōu)化方法運(yùn)用到貴陽(yáng)煙草物流配送中心的路線優(yōu)化中，有一定的實(shí)踐意義。

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