基于路網的動態配送系統軟件開發與設計

侯一萌 劉士廣

南京農業大學工學院，江蘇 南京 210031

基于路網的動態配送系統軟件開發與設計

侯一萌 劉士廣

南京農業大學工學院，江蘇 南京 210031

配送車輛優化調度問題是物流系統中的一個重要環節，本軟件借助VB語言，在分析靜態配送的基礎上，針對不斷變化的市場需求，建立動態的物流配送模型，在生成路網的平臺上，通過研究物流配送貨物過程中路徑、車輛選擇的問題，提出對物流配送最優路徑的動態選擇方案，提高物流配送效率，滿足客戶需求，更符合實際。

路網；Floyd算法；節約算法；車輛優化調度；動態配送

1.研究意義

現代物流已被公認為是企業在降低物質消耗，提高勞動生產率以外創造利潤的第三個重要源泉，也是企業降低生產經營成本，提高產品市場競爭力的重要途徑[1]。所謂配送是指按客戶的訂貨需求，在物流中心進行分貨、配貨工作，并將配好的貨物及時送交收貨人的物流活動，是物流系統中的一個重要環節[2]。我國在20世紀80年代初就引進物流配送的概念，隨著經濟的發展，越來越多的人對物流配送有了全面的了解和認識，但在相當多的企業中，其觀念還停留在成本中心、利潤中心上，運輸、倉儲的現代化水平比較低，“只送不配”的現象造成物流配送無效作業環節的增多，車輛空駛嚴重，配送成本高，質量低，效率低下。

本軟件在配送中心與客戶之間進行物流活動前，得出最優配送方案，并對于車輛配送過程中可能隨機出現新客戶的情況進行配送路線和車輛的調整，使配送資源得到最大化的利用，減少配送時間和成本，避免車輛空駛現象，提高配送效率。

2.軟件概述

配送車輛優化調度問題可以描述為：在一個存在供求關系的系統中，有若干臺車輛，若干個配送中心，要求合理安排車輛的行車路線和出行時間，從而在給定的約束條件下，把客戶需求的貨物從配送中心送到客戶，把客戶供應的貨物從客戶取到配送中心，并使目標函數取得優化[3]。

由于現實生活中的配送車輛優化調度問題非常復雜，為了方便用Visual Basic語言進行編程，我們在以下約定條件下進行研究：

（1）從一個配送中心向多個客戶送貨；配送中心供應的貨物能夠滿足所有客戶的需求。

（2）每臺配送車輛的最大載重量一定，不允許超載；每臺配送車輛都從配送中心出發，向客戶提供配送服務以后，最終返回配送中心。

（3）對于客戶的要求將需求貨物送到的時間無限制，即不帶時間窗的配送調度問題。

（4）各個客戶需求的貨物可以裝在同一輛配送車輛上，每個客戶的貨物需求量不超過配送車輛的最大載重量；每個客戶的送貨要求必須滿足，且僅能有一輛車輛完成，不允許分批配送。

（5）配送中心與客戶之間以及客戶之間的距離已知；不考慮運輸網絡中的車輛流量的限制。

基于以上條件，在所開發的軟件中輸入節點數，可以生成具有相應節點數的隨機路網；輸入客戶數，在已生成的路網的基礎上相應地隨機生成一個配送中心和若干客戶點及每個客戶點要求的貨物量；計算機經過計算，得出具有一定載貨量的車輛由配送中心出發，將貨物配送至各個客戶點的最佳路徑。車輛在按此路徑方案進行配送的過程中可能出現新的客戶和客戶需求，軟件即可根據此信息調整車輛之后所走的路線，得到新的配送方案，從而達到動態配送，使配送資源利用最大化的目的，降低配送成本，提高配送效率。

3.配送車輛優化調度問題算法分析與選擇

3.1 最短路徑問題

最短路徑問題通常指的是在網絡中的每條邊都有一個權值，尋找圖（由結點和路徑組成的）中兩結點之間總權和最小的路徑。最短路徑問題可以分為單源最短路徑問題和全局最短路徑問題。單源最短路徑包括以下幾種問題：確定起點的最短路徑問題；確定終點的最短路問題；確定起點終點的最短路問題。全局最短路問題則要求出圖中所有的最短路徑。

3.1.1 Floyd算法

Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權的最短路徑問題，時間復雜度為O(N^3)，空間復雜度為O(N^2)，用矩陣記錄圖，利用動態規劃思想，設Di,j,k為從i到j的只以(1...k)集合中的節點為中間節點的最短路徑的長度。若最短路徑經過點k，則Di,j,k = Di,k,k-1 + Dk,j,k-1；若最短路徑不經過點k，則Di,j,k = Di,j,k-1。因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 ,Di,j,k-1)。

3.1.2 Dijkstra算法

Dijkstra算法是解單源最短路徑問題的一個貪心算法。設圖共有n個不同的結點，則從源點出發到達其他各點的最短路徑有n-1條，這n-1條最短路徑之間存在大小關系。Dijkstra算法的基本策略是，按長度不減次序構造這n-1條最短路徑，即先求出長度最小的一條最短路徑，然后求出長度第二小的最短路徑，最后求出長度最大的最短路徑[4]。

由于本軟件生成的路網及客戶點、客戶需求量都是隨機的，且生成的網絡圖沒有負權邊，在此情況下，為了使計算機更容易獲得最優配送路線方案以及進行之后的動態調整，我們選取用于解決全局最短路徑問題的Floyd算法來完成軟件最短路徑部分的編程。

3.2 配送車輛調度問題

3.2.1 節約算法解決初始配送路線問題

節約算法是由Clarke和Wright于1964年首次提出的，它的基本原理是首先把各點單獨與源點0相連，構成1條僅含一個點的線路。總費用為從原點到各點的距離的費用的兩倍。然后計算將點i和j連接在一條線路上費用的節約值，即：S(i,j)=c0i+ ci0+ c0j+cj0-(c0i+ cij + cj0)= c0i+ c0j -cij。S(i,j)越大，說明把i和i連接在一起時總路程減少越多。實際的路線優化就是根據節約值進行降序排列。

節約算法求解問題的步驟是：

第一步：求出最短距離矩陣。根據配送路網圖中配送中心與客戶之間以及客戶之間的距離，應用Floyd算法計算出路網中各節點之間的最短距離，計入矩陣；

第二步：計算節約值s(i,j)。根據第一步中求得的最短距離矩陣，利用節約值計算公式求出各客戶點的節約里程，令M={s(i,j)|s(i,j)>0}；

第三步：在M中對s(i,j)降序排列。

第四步：確定配送路線。根據節約值的大小順序和節約算法的約束條件，逐漸組成配送路徑圖[5]。

節約算法運算速度快，尤其在小規模的配送優化中，節約算法的優化精度很高，可以很快得出結果。將節約算法運用在所開發的軟件中，得出從配送中心出發最終回到配送中心的初始配送路線。

3.2.2 插入法進行路線的動態調整

由于軟件需要實現動態調整路線的功能，即當車輛按照原路線行駛至客戶點A時，出現新的客戶點B及相應的需貨量，可以調整車輛在A點之后的行駛路線，或者從配送中心重新調度，達到既能滿足客戶需求，又能有效利用資源、提高配送效率的最優化目的。

當有新客戶點產生時，配送調整路線應從新客戶點出發返回至配送中心，此時從一點出發返回至該點的節約算法不再適用。受節約算法的啟發，我們采用插入法來解決這一問題。

以生成一個新客戶點P為例。首先根據P點的需貨量，判斷目前貨物重量是否超過單車載重，若超過，則從配送中心選擇最佳路徑重新調度車輛；若沒有超過，則調用最短距離函數，依次求出初始路線在A點之后的所經過的各個節點1、2、3……n與新客戶點P之間的最短距離，用ss(i,P)表示節點i與P之間的最短距離，令d(1)=ss(2,P)-ss(1,P)；d(2)=ss(3,P)-ss(2,P)……d(i)=ss(i+1,P)-ss(i,P)，找出使d(i)取值最小的下標j，可以將新客戶P點插入節點j和節點j+1中間，完成配送路徑的調整。

4.軟件制作

軟件運用Visual Basic語言進行界面制作和程序編譯。在以上算法分析的基礎上，依次進行生成路網、最短路徑、隨機生成客戶及客戶需貨量、節約算法求解路徑、插入法調整路徑的編程工作，部分程序如下：

4.1 Floyd算法程序

圖1

4.2 節約算法部分程序

圖2

軟件制作完成后，可以得到如下圖效果：

圖3

5.結語

本文設計開發的軟件在物流企業進行貨物配送的問題上建立了車輛優化調度的模型，提出最優的配送路徑方案，并針對配送任務過程中可能出現新客戶點的情況，對配送方案進行動態調整，達到資源的優化利用，提高物流配送效率。

由于本軟件僅限于建立了動態配送優化調度的模型，且研究的約束條件不含帶時間窗，可用于教學軟件，但與復雜的現實情況相比仍有較大的差距。在此基礎上，可以將時間窗等約束條件添加到算法中，模擬更多約束條件的車輛配送路線問題。同時，可以考慮將GIS系統應用到軟件中，模擬與實際情況相符合的路網狀況，是軟件應用性更強。

[1]馬力強.關于我國現代物流發展的思考[J].交通運輸系統工程與信息,2000年第1期

[2]郎茂祥.配送車輛調度問題芻議.物流技術，2003年03期

[3]Golden B L,Assad A A , Ball M..Routing and Scheduling of Vehicles and Crews:The State of Art[J].Computers & Operations Research,1983,7(10):63～211

[4]吳華麗，吳進華，王玲玲，陳世童.2010國際信息技術與應用論壇論文集,2010年

[5]鄭英，孟志青.基于節約算法的煙草物流配送路線優化.中國管理信息化, 2010年12月第13卷第23期

Based on Network Dynamic Distribution System Software Development and Design Hou Yimeng，Liu Shiguang

College of Engineering,Nanjing Agricultural University,Nanjing 210031,China

Logistics distribution vehicle scheduling problem of logistics is a key link in the system, the software developed by VB language, in the analysis of static distribution basis, in response to the changing market demand, establishing the dynamic model of logistics distribution in generation, network platform,through the research of logistics distribution vehicle routing, goods in the course of selection problem, put forward to the logistics distribution path optimization dynamic selection scheme, improve the efficiency of logistics distribution, to meet customer needs, more practical.

road network;floyd algorithm;saving algorithm;optimization of vehicle dispatching;dynamic distribution

10.3969/j.issn.1001-8972.2012.15.038