配送線路劃分與電子排單系統(tǒng)建模與算法研究.pdf

1、目前物流配送中心的末端配送主要采取集中統(tǒng)一的送貨方式，這種配送模式必須綜合考慮配送網(wǎng)點(diǎn)訂貨情況、物流配送中心規(guī)模、道路擁擠度、道路整改等因素對(duì)配送效能的影響。本文從衡量配送線路實(shí)際工作量大小的“廣義工作量”指標(biāo)入手，在地理信息系統(tǒng)(GeographyInformationSystem，GIS)和企業(yè)網(wǎng)絡(luò)數(shù)據(jù)庫系統(tǒng)的支持下，以提高網(wǎng)點(diǎn)客戶滿意度和降低配送成本為主要目標(biāo)，進(jìn)行物流配送中心末端配送線路優(yōu)化課題的研究工作。 研究工作主要

2、包括配送線路廣義工作量和送貨經(jīng)濟(jì)距離概念的提出和應(yīng)用、配送線路的劃分、單車線路優(yōu)化和電子排單系統(tǒng)的可視化輸出等內(nèi)容。 首先，本文提出了衡量配送線路工作量大小的“廣義工作量”的概念。廣義工作量是配送中心進(jìn)行配送線路區(qū)域劃分的一項(xiàng)重要經(jīng)濟(jì)指標(biāo)，它與送貨經(jīng)濟(jì)距離S、送貨量D、零售網(wǎng)點(diǎn)數(shù)量N等因素相關(guān)，它要求不同配送線路之間廣義工作量大小基本均衡，以使所有線路車輛送貨員或駕駛員在其配送過程中更好地為客戶提供滿意的服務(wù)。在體現(xiàn)廣義工作量大

3、小的影響因素中，客戶訂貨量(即配送中心送貨量)、送貨經(jīng)濟(jì)距離、單車線路的網(wǎng)點(diǎn)客戶數(shù)量都是物流配送中心送貨線路劃分的重要因素。送貨經(jīng)濟(jì)距離是指在考慮路段長(zhǎng)短、擁擠程度、車道數(shù)量、路面類型等因素基礎(chǔ)上，實(shí)現(xiàn)兩點(diǎn)間配送時(shí)間最短的車輛行駛距離值。廣義工作量概念的提出是進(jìn)行配送線路劃分的先決條件，也是求解配送成本與網(wǎng)點(diǎn)客戶服務(wù)水平之間均衡點(diǎn)的前提。 其次，在企業(yè)配送網(wǎng)絡(luò)GIS支持下，以廣義工作量均衡和車輛容載量為目標(biāo)值，對(duì)所有配送網(wǎng)點(diǎn)進(jìn)行

4、配送線路的劃分，把一個(gè)包含幾千個(gè)配送網(wǎng)點(diǎn)的難點(diǎn)問題，轉(zhuǎn)化為有限個(gè)實(shí)際可控、可觀測(cè)的子系統(tǒng)進(jìn)行求解。本文采用最鄰近算法求得物流配送中心送貨線路劃分的初始解，然后采用插入算法對(duì)線路劃分初始解進(jìn)行改進(jìn)，在GIS平臺(tái)上的仿真結(jié)果表明了改進(jìn)后線路劃分方案的合理性。為了使劃分結(jié)果進(jìn)一步符合物流企業(yè)的實(shí)際應(yīng)用，本文在常規(guī)最鄰近算法的基礎(chǔ)上，提出了二階最鄰近算法的內(nèi)涵，證明了該算法每次選擇下一個(gè)新網(wǎng)點(diǎn)時(shí)，其與當(dāng)前線路上已有的兩個(gè)次新網(wǎng)點(diǎn)所組成的網(wǎng)點(diǎn)子集

5、都是聚集程度最高的，由此得到的配送線路中的客戶網(wǎng)點(diǎn)聚集程度，要高于常規(guī)一階最鄰近算法所得到的線路，這為下一階段的單車線路優(yōu)化提供了較好的基礎(chǔ)。 本文在配送線路劃分的基礎(chǔ)上，在GIS平臺(tái)上進(jìn)行了單車配送線路的優(yōu)化調(diào)度，即綜合考慮單車線路每次送貨的網(wǎng)點(diǎn)數(shù)量、訂貨數(shù)量、道路擁擠度等因素的變化，求解出每日每次每條送貨車輛的行駛路線安排，實(shí)現(xiàn)物流配送中心送貨車輛的每日每次動(dòng)態(tài)電子排單的可視化輸出。 論文在對(duì)國內(nèi)外單車線路優(yōu)化問題大

6、量調(diào)研的基礎(chǔ)上，提出了自己獨(dú)特的、適合國內(nèi)物流配送中心末端配送的單車線路求解方案：先用最節(jié)約插值法構(gòu)建問題的初始可行解，生成初始解路徑集合；然后采用混合遺傳算法的全局搜索策略優(yōu)化最節(jié)約插值法得到的初始解，進(jìn)而得到一個(gè)相對(duì)滿意的解。由于傳統(tǒng)遺傳算法全局搜索能力很強(qiáng)但局部搜索能力不足，爬山算法則具有很強(qiáng)的局部搜索能力，是一種常用的尋找局部最優(yōu)解的方法，本文將二者相結(jié)合，以期取長(zhǎng)補(bǔ)短，實(shí)踐應(yīng)用表明這種策略可大大提高配送線路的優(yōu)化性能。為了使每

7、日每次單車配送線路更加符合實(shí)際電子排單和道路交通狀況，本文以杭州市某段景區(qū)為例，從城市交通網(wǎng)絡(luò)中道路路段間的地理關(guān)聯(lián)關(guān)系入手，在最短路徑算法(Dijkstra)基礎(chǔ)上，考慮道路暢通度系數(shù)，探討不同配送時(shí)間段道路暢通度隨機(jī)因素對(duì)單車線路配送效能的影響，分析結(jié)果使送貨經(jīng)濟(jì)距離數(shù)據(jù)庫的建立和應(yīng)用更加符合配送線路的實(shí)際運(yùn)營(yíng)狀況。 上述研究以杭州市區(qū)卷煙配送網(wǎng)絡(luò)為數(shù)據(jù)獲取源和應(yīng)用案例，分別建立物流配送中心配送線路劃分和單車線路優(yōu)化兩個(gè)階段

8、的系統(tǒng)模型，采用多種算法(或其混合)進(jìn)行求解。由于大規(guī)模配送網(wǎng)絡(luò)車輛路線問題是一個(gè)典型的NP難點(diǎn)，隨著網(wǎng)點(diǎn)數(shù)量的增加，系統(tǒng)計(jì)算的復(fù)雜度無論在空間上還是在時(shí)間上都將成指數(shù)級(jí)增長(zhǎng)，這對(duì)于規(guī)模較大的即時(shí)配送調(diào)度問題的優(yōu)化計(jì)算是難以接受的。據(jù)我們調(diào)研，物流配送企業(yè)對(duì)網(wǎng)點(diǎn)客戶訂單的有效反應(yīng)要求很高，節(jié)拍很短，有時(shí)甚至不允許電腦計(jì)算時(shí)間過長(zhǎng)，因此有必要進(jìn)行本課題的系統(tǒng)建模與算法研究，解決物流配送中心末端配送的復(fù)雜配送網(wǎng)絡(luò)求解時(shí)間過長(zhǎng)、計(jì)算工作量過高

9、的現(xiàn)實(shí)問題。 本文采用MapInfo、VB、SOLServer2000等開發(fā)技術(shù)將上述模型與算法集成到企業(yè)配送網(wǎng)絡(luò)GIS環(huán)境下，完成物流配送中心末端配送系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)。通過與GIS系統(tǒng)的集成，將線路劃分結(jié)果與單車線路電子排單結(jié)果，直觀地輸出在電子地圖上，從而實(shí)現(xiàn)物流配送中心末端配送車輛路線問題的可視化輸出控制。研究成果在煙草、百貨、醫(yī)藥、油料等企業(yè)的物流配送中心末端集中配送領(lǐng)域，具有普適性和推廣應(yīng)用前景。 本文研究?jī)?nèi)容

10、的創(chuàng)新性主要體現(xiàn)在以下幾個(gè)方面： (1)在定義物流配送中心送貨線路“廣義工作量”和“送貨經(jīng)濟(jì)距離”概念的基礎(chǔ)上，根據(jù)不同配送線路工作量均衡和送貨經(jīng)濟(jì)距離最短的多目標(biāo)決策問題求解期望，采用改進(jìn)后的二階最鄰近算法和插入法進(jìn)行送貨線路劃分，從而兼顧了配送成本降低與客戶滿意度提高兩者之間的“二律背反”關(guān)系； (2)單車線路優(yōu)化應(yīng)用了標(biāo)準(zhǔn)遺傳算法與爬山算法相結(jié)合的混合遺傳算法，在其中的同化操作中，首次提出并應(yīng)用能綜合體現(xiàn)單車線路網(wǎng)