侯一萌 劉士廣

南京農(nóng)業(yè)大學(xué)工學(xué)院，江蘇 南京 210031

基于路網(wǎng)的動態(tài)配送系統(tǒng)軟件開發(fā)與設(shè)計

侯一萌 劉士廣

南京農(nóng)業(yè)大學(xué)工學(xué)院，江蘇 南京 210031

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

路網(wǎng)；Floyd算法；節(jié)約算法；車輛優(yōu)化調(diào)度；動態(tài)配送

1.研究意義

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

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

2.軟件概述

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

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

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

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

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

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

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

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

3.配送車輛優(yōu)化調(diào)度問題算法分析與選擇

3.1 最短路徑問題

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

3.1.1 Floyd算法

Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題，時間復(fù)雜度為O(N^3)，空間復(fù)雜度為O(N^2)，用矩陣記錄圖，利用動態(tài)規(guī)劃思想，設(shè)Di,j,k為從i到j(luò)的只以(1...k)集合中的節(jié)點為中間節(jié)點的最短路徑的長度。若最短路徑經(jīng)過點k，則Di,j,k = Di,k,k-1 + Dk,j,k-1；若最短路徑不經(jīng)過點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算法是解單源最短路徑問題的一個貪心算法。設(shè)圖共有n個不同的結(jié)點，則從源點出發(fā)到達(dá)其他各點的最短路徑有n-1條，這n-1條最短路徑之間存在大小關(guān)系。Dijkstra算法的基本策略是，按長度不減次序構(gòu)造這n-1條最短路徑，即先求出長度最小的一條最短路徑，然后求出長度第二小的最短路徑，最后求出長度最大的最短路徑[4]。

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

3.2 配送車輛調(diào)度問題

3.2.1 節(jié)約算法解決初始配送路線問題

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

節(jié)約算法求解問題的步驟是：

第一步：求出最短距離矩陣。根據(jù)配送路網(wǎng)圖中配送中心與客戶之間以及客戶之間的距離，應(yīng)用Floyd算法計算出路網(wǎng)中各節(jié)點之間的最短距離，計入矩陣；

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

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

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

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

3.2.2 插入法進行路線的動態(tài)調(diào)整

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

當(dāng)有新客戶點產(chǎn)生時，配送調(diào)整路線應(yīng)從新客戶點出發(fā)返回至配送中心，此時從一點出發(fā)返回至該點的節(jié)約算法不再適用。受節(jié)約算法的啟發(fā)，我們采用插入法來解決這一問題。

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

4.軟件制作

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

4.1 Floyd算法程序

圖1

4.2 節(jié)約算法部分程序

圖2

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

圖3

5.結(jié)語

本文設(shè)計開發(fā)的軟件在物流企業(yè)進行貨物配送的問題上建立了車輛優(yōu)化調(diào)度的模型，提出最優(yōu)的配送路徑方案，并針對配送任務(wù)過程中可能出現(xiàn)新客戶點的情況，對配送方案進行動態(tài)調(diào)整，達(dá)到資源的優(yōu)化利用，提高物流配送效率。

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

[1]馬力強.關(guān)于我國現(xiàn)代物流發(fā)展的思考[J].交通運輸系統(tǒng)工程與信息,2000年第1期

[2]郎茂祥.配送車輛調(diào)度問題芻議.物流技術(shù)，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國際信息技術(shù)與應(yīng)用論壇論文集,2010年

[5]鄭英，孟志青.基于節(jié)約算法的煙草物流配送路線優(yōu)化.中國管理信息化, 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