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

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

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

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

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

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

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

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

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

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

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