楊麗娟,　劉渤海

(1.安徽工商職業(yè)學院 工商管理系， 安徽 合肥　231131; 2.合肥工業(yè)大學 管理學院， 安徽 合肥　230009)

?

基于Dijkstra拓展算法路線優(yōu)化

楊麗娟1,劉渤海2*

(1.安徽工商職業(yè)學院 工商管理系， 安徽 合肥231131; 2.合肥工業(yè)大學 管理學院， 安徽 合肥230009)

摘要：利用Dijkstra算法，將配送中心的3個業(yè)務(wù)目標(距離、時間和費用)進行整合，建立可實現(xiàn)多目標的模型。對多目標Dijkstra算法進行了拓展，即一個配送中心對應(yīng)兩個客戶配送以及車輛調(diào)度。

關(guān)鍵詞：配送中心; 多目標; 車輛調(diào)度; 路線優(yōu)化

0引言

0.1　相關(guān)背景

物流配送是物流中一個重要的直接與消費者相連的環(huán)節(jié)，配送的速度及質(zhì)量直接關(guān)系到配送中心的工作質(zhì)量和效益。隨著經(jīng)濟的發(fā)展，物流配送中心的貨運量逐漸增大，貨物規(guī)格不斷增多，需求運輸車輛也逐漸增加，同時隨著油價不斷上漲，人工成本增加，使得配送中心的成本逐步增加。因此,對制定車輛配載計劃和配送路線的優(yōu)化就顯得十分重要[1]。如何高效地制定出一個合理的車輛調(diào)度和路線優(yōu)化方案,強化管理，降低成本，提高提潤率，成為物流配送研究中一個亟待解決的問題[2]。

0.2　國內(nèi)研究現(xiàn)狀

目前國內(nèi)配送中心在配送路線優(yōu)化中，往往只為了實現(xiàn)單一目標，即距離、時間或是總費用，這導致配送中心在實際的作業(yè)過程中只單純地追求最短路徑、配送的最短時間或是配送的總費用[3]。而現(xiàn)實是最短的路徑可能路況不好，或是最短的時間路況不好，過路費較高等，這都會造成配送成本不一定最低。與此同時，配送中心配送運輸過程中產(chǎn)生的一些費用，如過路過橋費、車輛折舊費、管理費用、財務(wù)費用、信息費、駕駛員工資等。

文中在對配送中心的車輛路線設(shè)計相關(guān)理論研究中發(fā)現(xiàn)，主要分為單一目標和多目標(兩個及以上)兩大類型[4]。單一目標主要分為最短路徑、最低費用和最短時間3種。具體方法如下：

1)單一目標----最短路徑法。用于解決最短路徑問題的算法被稱做“最短路徑算法”， 有時被簡稱作“路徑算法”。 最常用的路徑算法有：VSP規(guī)劃法、Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法和Johnson算法。

2)單一目標----最低費用。具體運用到的方法主要有：遺傳算法、分支切割算法、禁忌算法、模擬退火算法等，均屬于較專業(yè)、較復雜的數(shù)學方法。

3)單一目標----最短時間。目前國內(nèi)關(guān)于最短時間這一單一目標的研究較少，Dijkstra算法可以實現(xiàn)。

4)多目標----最短路徑、最短時間、最低費用。

文中在調(diào)研時發(fā)現(xiàn)配送中心在運用數(shù)學方法實現(xiàn)多目標的研究較少，更多的專家集中在構(gòu)建不同的數(shù)學模型實現(xiàn)單一的目標。

1關(guān)于配送中心車輛路線優(yōu)化的研究

1.1　多目標Dijkstra算法的原理

針對物流配送中心如何根據(jù)貨物運單來調(diào)度運輸車輛的問題,在研究了各種貨物配裝優(yōu)化模型的基礎(chǔ)上,建立了車輛安排的多目標優(yōu)化模型。然后，利用線性加權(quán)法和主要目標法將多目標優(yōu)化問題轉(zhuǎn)化為單目標優(yōu)化問題,采用精確算法思想進行模型求解[5]。文中的多目標Dijkstra算法的情境是：單車場單送貨車輛路徑，未考慮路況、天氣因素、發(fā)車時間限制、客戶時間窗約束等情況下的車輛路徑優(yōu)化方法。

1.2　多目標Dijkstra算法具體方法

1.2.1權(quán)值的賦予

在這里權(quán)值主要分為3種：兩點間距離、運行時間和費用。

距離權(quán)值比較容易確定，可以通過查閱《中國公路地圖》或者到中國公路網(wǎng)等國內(nèi)權(quán)威網(wǎng)站確定最短路徑。

運行時間權(quán)值文中按照百度地圖運行時間進行計算，也可以利用兩點之間的距離和限速的最大值比較得來，即運行時間=路徑/限速最大值。

費用主要包括：燃油費、過路過橋費、車輛折舊費、管理費用、財務(wù)費用、信息費、駕駛員工資等[6]。

1.2.2權(quán)重的賦值

對于距離、運行時間和費用3個指標權(quán)重的賦值是由配送中心根據(jù)自己的實際情況來確定。配送中心可以只考慮單一目標，也可以考慮2個目標，或者綜合考慮3個目標[7]。

1.2.3運用多目標Dijkstra算法對配送中心車輛路線優(yōu)化的研究

南京某配送中心有一批3.8 t的貨物將從南京配送中心運至淮南客戶(1.8 t)和蚌埠客戶(2 t)處。所涉及的城市信息如圖1所示。

圖1　城市網(wǎng)絡(luò)圖

圖中：線段上的數(shù)字為兩點之間的距離(km)，括號內(nèi)的數(shù)字為運行時間(min)，城市間的距離為兩點直達路徑距離，一部分是高速，另一部分是國道。

此配送中心可調(diào)度的車型有兩種：2 t車和4 t車。具體信息如下：

配送中心共有兩種車型可供選擇：A型車，車自重1 t，核定載重2 t，數(shù)量5輛，空車油耗為4 L/(100 km)，半載油耗7 L/(100 km),滿載油耗10 L/(100 km)；B型車，車自重2 t，核定載重4 t，數(shù)量4輛；空車油耗為6 L/(100 km)，半載油耗10 L/(100 km)，滿載油耗18 L/(100 km)[8]。

此次業(yè)務(wù)中車輛調(diào)度方案有兩輛2 t車分別配送和一輛4 t車共同配送，我們分別進行線路設(shè)計。

1.2.3.1方案1(調(diào)度兩輛A型車分別配送)

第一輛2 t車從南京出發(fā)到蚌埠；第二輛2 t車從南京出發(fā)到淮南。

步驟1：費用核算。2 t貨車油耗為10 L/(100 km)，柴油價按照7.3元/L計算；過路費按照實際收費標準計算，安徽省高速公路10 t及以下的貨車的計重收費標準為0.08元/(t·km)。車貨總質(zhì)量不足5 t按5 t計費；計重收費不足20元時，按20元計費。安徽省普通公路:根據(jù)實際車貨總質(zhì)量，小于10 t的車輛按2元/t車次計費[9]。各城市間的總費用見表1。

表1　城市間相關(guān)費用表

步驟2：城市間距離、時間、費用權(quán)值信息表。配送中心賦予距離、時間和費用的權(quán)重為0.3，0.3，0.4，根據(jù)權(quán)重和各指標的數(shù)值利用加權(quán)法計算得到3個指標的權(quán)值，具體信息見表2。

表2　城市間距離、時間、費用權(quán)值信息表

步驟3：第一輛2 t車“南京-蚌埠”線路權(quán)重計算。根據(jù)以上權(quán)值，利用多目標Dijkstra算法進行計算：

1)南京為已知解。與南京相連的有合肥、滁州、明光；南京-合肥權(quán)值為161.2,南京-滁州權(quán)值為84.3；南京-明光權(quán)值為115.2。所以取南京-滁州，滁州為已知解。

2)與南京和滁州相連的有合肥、淮南、明光。滁州-合肥總權(quán)值為213.1；滁州-淮南總權(quán)值為233.1；滁州-明光總權(quán)值為157.6；南京-合肥總權(quán)值為161.2；南京-明光權(quán)值為115.2。所以取最小值115.2，即路線南京-明光,明光為已知解。

3)與南京、滁州、明光相連的有合肥、淮南、蚌埠。南京-合肥總權(quán)值為161.2；滁州-淮南總權(quán)值為233.1；滁州-合肥總權(quán)值為213.1；明光-淮南總權(quán)值為232；明光-蚌埠總權(quán)值為192。所以取最小值161.2，即線路南京-合肥，合肥為已知解。

4)與南京、滁州、明光、合肥相連的有淮南、蚌埠。合肥-淮南總權(quán)值為264.5；合肥-蚌埠總權(quán)值為295；滁州-淮南總權(quán)值為233.1；明光-淮南總權(quán)值為232；明光-蚌埠總權(quán)值為192。所以取最小值192，即線路明光-蚌埠，蚌埠為已知解。

綜上所述，此次配送的線路最終為：南京-明光-蚌埠，總權(quán)值為192。

步驟4：第二輛2 t車權(quán)值“南京-淮南”線路權(quán)重計算。我們利用多目標Dijkstra算法進行計算：

1)南京為已知解。與南京相連的有合肥、滁州、明光；南京-合肥權(quán)值為161.2,南京-滁州權(quán)值為84.3；南京-明光權(quán)值為115.2。所以取南京-滁州，滁州為已知解。

2)與南京和滁州相連的有合肥、淮南、明光。滁州-合肥總權(quán)值為213.1；滁州-淮南總權(quán)值為233.1；滁州-明光總權(quán)值為157.6；南京-合肥總權(quán)值為161.2；南京-明光權(quán)值為115.2。所以取最小值115.2，即路線南京-明光,明光為已知解。

3)與南京、滁州、明光相連的有合肥、淮南。南京-合肥總權(quán)值為161.2；滁州-淮南總權(quán)值為233.1；滁州-合肥總權(quán)值為213.1；明光-淮南總權(quán)值為232。所以取最小值161.2，即線路南京-合肥，合肥為已知解。

4)與南京、滁州、明光、合肥相連的有淮南。合肥-淮南總權(quán)值為264.5；滁州-淮南總權(quán)值為233.1；明光-淮南總權(quán)值為232。所以取最小值232，即線路明光-淮南，淮南為已知解。

第二輛2 t車配送的線路為：南京-明光-淮南，權(quán)值為264.5。綜上所述，兩輛2 t車的總權(quán)值為192+264.5=456.5。

1.2.3.2方案2(調(diào)度1輛4 t車進行路線優(yōu)化設(shè)計)

步驟1：“南京-淮南段”總費用權(quán)值計算。因為車型不同，油耗不同，核定載重及自重不同，所以燃油費、過路費要重新計算。4 t車的前段路程滿載狀態(tài)油耗為18 L/(100 km)。

表3　城市間相關(guān)費用表

步驟2：南京-淮南段城市間距離、時間、費用權(quán)值信息表。配送中心賦予距離、時間和費用的權(quán)重為0.3,0.3,0.4，根據(jù)權(quán)重和各指標的數(shù)值利用加權(quán)法計算得到3個指標的權(quán)值，具體信息見表4。

表4　城市間距離、時間、費用權(quán)值信息表

步驟3：多目標Dijkstra算法路線選擇。根據(jù)以上的權(quán)值，我們利用多目標Dijkstra算法進行計算：

1)南京為已知解。與南京相連的有合肥、滁州、明光；南京-合肥權(quán)值為203.6；南京-滁州權(quán)值為105.9；南京-明光權(quán)值為148.9。所以取最小值105.9，即南京-滁州，滁州為已知解。

2)與南京和滁州相連的有合肥、淮南、明光。滁州-合肥總權(quán)值為267.9；滁州-淮南總權(quán)值為291.7；滁州-明光總權(quán)值為197.8；南京-合肥總權(quán)值為203.6；南京-明光權(quán)值為148.9。所以取最小值148.9，即路線南京-明光,明光為已知解。

3)與南京、滁州、明光相連的有合肥、淮南。南京-合肥總權(quán)值為203.6；滁州-淮南總權(quán)值為291.7；滁州-合肥總權(quán)值為267.9；明光-淮南總權(quán)值為296.4。所以取最小值203.6，即線路南京-合肥，合肥為已知解。

4)與南京、滁州、明光、合肥相連的有淮南。合肥-淮南總權(quán)值為334；滁州-淮南總權(quán)值為291.7；明光-淮南總權(quán)值為296.4。所以取最小值291.7，即線路滁州-淮南，淮南為已知解。

綜上所述，配送的線路為：南京-滁州-淮南，總權(quán)值為291.7。

步驟4：“淮南-蚌埠段”費用計算。4 t貨車拉貨1.8 t，自重2 t，半載油耗為10 L/(100 km)，由淮南開往蚌埠。

城市間相關(guān)費用表見表5。

表5　城市間相關(guān)費用表

步驟5：“淮南-蚌埠段”權(quán)值計算。城市間距離、時間、費用權(quán)值信息表見表6。

步驟6：多目標Dijkstra算法路線選擇。根據(jù)以上的權(quán)值，利用多目標Dijkstra算法進行計算：

淮南為已知解。與淮南相連的有明光、蚌埠；淮南-蚌埠權(quán)值為65，淮南-明光權(quán)值為112.4。所以取淮南-蚌埠，蚌埠為已知解，權(quán)值為65。兩段路線權(quán)值總計為291.7+65=356.7。

表6　城市間距離、時間、費用權(quán)值信息表

1.2.3.3方案1和方案2比較分析

方案1調(diào)度兩輛2 t車兩條線路總權(quán)值為456.5，方案2調(diào)度1輛4 t車的最優(yōu)線路總權(quán)值為356.7。兩個車輛調(diào)度方案比較得知，方案2調(diào)度1輛4 t車，總權(quán)值最小，為最佳車輛調(diào)度和最優(yōu)路線。

2結(jié)語

利用Dijkstra算法實現(xiàn)了距離、時間和費用3個綜合目標，并由此擴展到一個配送中心對應(yīng)兩個客戶的情況，不僅實現(xiàn)了3個綜合目標的線路設(shè)計，同時進行了合理的車輛調(diào)度[10]。配送中心或者貨運企業(yè)可以根據(jù)自身狀況對3個指標賦予不同的權(quán)重，針對具體業(yè)務(wù)情況進行合理的車輛調(diào)度和路線設(shè)計。

參考文獻：

[1]張念.用Dijkstra算法實現(xiàn)對整車配送線路的優(yōu)化[J].中國水運,2007,5(5)：15-16.

[2]胡鶴嚴.基于成本的配送路線優(yōu)化模型與算法研究[D]：[碩士學位論文].長春:吉林大學,2012.

[3]齊晗.對物流配送作業(yè)若干問題的優(yōu)化研究[J].安徽電子信息職業(yè)技術(shù)學院學報，2012(6):22-24.

[4]南超蘭.基于距離和時間的物流運輸路線優(yōu)化分析[J].物流科技,2012(12)：65-70.

[5]楊維,李歧強.粒子群優(yōu)化算法綜述[J].中國工程科學,2012(5)：25-26.

[6]王靜波.公路快運企業(yè)網(wǎng)絡(luò)優(yōu)化模型及算法研究[D]：[碩士學位論文].青島：山東大學,2013.

[7]曾嘉俊.基于種群多樣性的自適應(yīng)變異粒子群算法及應(yīng)用[D]：[碩士學位論文].成都:西南交通大學,2012.

[8]劉建美,馬壽峰,馬帥奇.基于改進的Dijkstra算法的動態(tài)最短路計算方法[J].系統(tǒng)工程理論與實踐, 2011(6)：78-82.

[9]張志遠.基于“云計算”的智能交通系統(tǒng)研究與構(gòu)建[D]：[碩士學位論文].蘭州：西北師范大學,2011.

[10]孫瑞超.網(wǎng)絡(luò)拓撲連通性恢復算法的研究與實現(xiàn)[D]：[碩士學位論文].哈爾濱：哈爾濱工業(yè)大學,2011.

Dijkstra based algorithm for

vehicle scheduling and route optimizatio

YANG Li-juan1,LIU Bo-hai2*

(1.Department of Business Administration, Anhui Business Vocational College, Hefei 231131, China;

2.School of management, Hefei University of Technology, Hefei 230009, China)

Abstract：With Dijkstra algorithm, the three business indexes in a distribution center such as distance, time and cost are integrated to build the multi-objective model. The multi-objective Dijkstra algorithm is extended with which one distribution center is responsible for two customer distribution business and vehicle scheduling.

Key words：distribution center； multi-objective； algorithm vehicle scheduling； route optimization.

作者簡介：楊麗娟(1981-)，女，漢族，安徽宿州人，安徽工商職業(yè)學院講師,碩士，主要從事物流管理方向研究,E-mail:yanglj2010@163.com. *通訊作者：劉渤海(1982-)，男，漢族，安徽淮北人，合肥工業(yè)大學副教授，博士，主要從事運營管理方向研究,E-mail:liubh2010@163.com.

基金項目：2013年高校省級優(yōu)秀青年人才基金重點項目(2013SQRW108ZD)

收稿日期：2014-06-13

中圖分類號：TP 301

文獻標志碼：A

文章編號：1674-1374(2015)01-0066-06

DOI:10.15923/j.cnki.cn22-1382/t.2015.1.14