侯一萌 劉士廣

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

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

侯一萌 劉士廣

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

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

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

1.研究意義

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

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

2.軟件概述

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

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

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

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

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

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

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

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

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

3.1 最短路徑問題

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

3.1.1 Floyd算法

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

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

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

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

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

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

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

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

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

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

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

3.2.2 插入法進(jìn)行路線的動(dòng)態(tài)調(diào)整

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

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

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

4.軟件制作

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

4.1 Floyd算法程序

圖1

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

圖2

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

圖3

5.結(jié)語

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

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

[1]馬力強(qiáng).關(guān)于我國現(xiàn)代物流發(fā)展的思考[J].交通運(yùn)輸系統(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]吳華麗，吳進(jìn)華，王玲玲，陳世童.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