姚 薇，丁必榮，呂 堃

（合肥工業(yè)大學(xué) 機(jī)械與汽車(chē)工程學(xué)院，安徽 合肥 230009）

·交通運(yùn)輸·

基于時(shí)間約束的物流運(yùn)輸路線優(yōu)化

姚 薇，丁必榮，呂 堃

（合肥工業(yè)大學(xué) 機(jī)械與汽車(chē)工程學(xué)院，安徽 合肥 230009）

0 引 言

在物流調(diào)度中經(jīng)常涉及到車(chē)輛路線問(wèn)題 （VRP），即如何使運(yùn)輸?shù)穆肪€最短、運(yùn)輸費(fèi)用最少等，這些都需要對(duì)路線進(jìn)行優(yōu)化設(shè)計(jì)。VRP是一個(gè)典型的NP難題，其路線優(yōu)化算法很多，但主要分為兩大類(lèi)：精確算法和近似算法[1-2]。精確算法包括分枝定界法、動(dòng)態(tài)規(guī)劃法等[3-4]；近似算法則包括禁忌搜索法、遺傳算法等[5]。

在分析VRP中運(yùn)輸成本和時(shí)間基礎(chǔ)上，本文采用一種新的方法解決車(chē)輛調(diào)度路線優(yōu)化問(wèn)題，即在Dijkstra方法基礎(chǔ)上，添加時(shí)間約束，構(gòu)造出兩個(gè)權(quán) （費(fèi)用權(quán)和時(shí)間權(quán)），進(jìn)行迭代。

1 數(shù)學(xué)模型的建立

研究車(chē)輛物流調(diào)度的路線問(wèn)題，就是研究車(chē)輛行走的最短路問(wèn)題。最短路問(wèn)題，簡(jiǎn)單地說(shuō)就是尋求某網(wǎng)絡(luò)中，從起點(diǎn)到終點(diǎn)的最短路徑[6]。為此，首先應(yīng)建立數(shù)學(xué)模型，而數(shù)學(xué)模型主要由變量、目標(biāo)函數(shù)和約束條件等三部分組成。下面針對(duì)運(yùn)輸行業(yè)的具體情況，討論一下運(yùn)輸成本的組成和具體計(jì)算公式，進(jìn)而給出物流調(diào)度路線優(yōu)化問(wèn)題的數(shù)學(xué)模型。

車(chē)輛運(yùn)輸成本包括固定成本和可變成本兩部分。固定成本包括車(chē)輛購(gòu)買(mǎi)費(fèi)用、稅費(fèi)和管理費(fèi)用等，可變成本包括駕駛員的工作量、車(chē)輛消耗油量和過(guò)路費(fèi)用等。參照公路運(yùn)輸部門(mén)計(jì)算運(yùn)輸成本的方法，可以制定出相鄰兩點(diǎn)之間的運(yùn)費(fèi)計(jì)算方法[7]：

其中，路況費(fèi)用系數(shù)為不同路況對(duì)各種型號(hào)車(chē)輛造成的燃料油消耗、機(jī)械磨損 （反映在維修維護(hù)費(fèi)用上）等形成的費(fèi)用。

其中，車(chē)型修正系數(shù)為某車(chē)型 （車(chē)輛型號(hào)、新舊程度等）每單位噸公里的費(fèi)用修正系數(shù)。

車(chē)輛到達(dá)某一個(gè)地點(diǎn)的時(shí)刻主要取決于發(fā)車(chē)時(shí)間、行駛時(shí)間和沿途?？咳齻€(gè)方面，其中影響沿途行駛時(shí)間的因素較為復(fù)雜，通過(guò)對(duì)相鄰兩地點(diǎn)之間的標(biāo)準(zhǔn)行駛進(jìn)行定額，可以判斷物流調(diào)度方案是否能在規(guī)定的時(shí)間內(nèi)將貨物送到目的地。根據(jù)下述方法來(lái)估算并根據(jù)實(shí)際情況加以修正，即相鄰兩點(diǎn)之間的運(yùn)輸時(shí)間T為：

其中，裝載修正系數(shù)是對(duì)于不同的裝載量 （重載和輕載）具有不同的速度限額，其他參數(shù)同上。這樣就可以計(jì)算出每一條線路所需的時(shí)間。

以在規(guī)定的時(shí)間內(nèi)，運(yùn)輸費(fèi)用最低為目標(biāo)函數(shù)，可建立以下的數(shù)學(xué)模型：

目標(biāo)函數(shù)：

式中：Xij表示車(chē)輛從點(diǎn)i到點(diǎn)j行駛，有則為1，沒(méi)有則為0；Cij表示從點(diǎn)i到點(diǎn)j的運(yùn)輸費(fèi)用成本，可按照公式 （1）進(jìn)行計(jì)算；n為途中的節(jié)點(diǎn)數(shù)。

約束條件：

式中：Tij表示車(chē)輛從點(diǎn)i到點(diǎn)j行駛的時(shí)間，可按照公式 （3）進(jìn)行計(jì)算；Tm表示累計(jì)等待的時(shí)間；T表示規(guī)定到達(dá)的時(shí)間；其他符號(hào)的含義同上。

2 算法思路

上述問(wèn)題可以構(gòu)成一個(gè)賦權(quán)有向圖D=（V,A ）， 對(duì)每一個(gè)弧aij=（vi,vj）， 相應(yīng)地有費(fèi)用權(quán) ω（ aij）=ωij和時(shí)間權(quán) θ（ aij）=θij。 目前，公認(rèn)Dijkstra方法是解決具有正權(quán)的最短路問(wèn)題的最佳方法[7]。其算法基本思想是：假設(shè)已經(jīng)求出從vs到vt的最短路μ*如下： vs,…,vj,…,vk,…,vt。

根據(jù)最短路的性質(zhì)，從vs沿μ*到vj或vk的路，就是vs到vj或vk的最短路。這就是說(shuō)μ*不僅是起點(diǎn)vs到終點(diǎn)vt的最短路，而且，由vs到μ*上任意中間點(diǎn)的最短路也在μ*上。為了求得vs到vt的最短路，可先求vs到某中間點(diǎn)的最短路，然后再逐步擴(kuò)展到終點(diǎn)vt。

Dijkstra方法只討論解決具有一個(gè)權(quán)的最短路問(wèn)題，本文在其基本思想基礎(chǔ)上，引入時(shí)間約束作為判斷條件，對(duì)費(fèi)用權(quán)和時(shí)間權(quán)同時(shí)進(jìn)行迭代。

在計(jì)算過(guò)程中，需要將已經(jīng)求出到起點(diǎn)最短路的點(diǎn)與尚未求出到起點(diǎn)最短路的點(diǎn)區(qū)分開(kāi)來(lái)，以正確執(zhí)行迭代。為此，用標(biāo)號(hào)法求解，即從vs開(kāi)始，對(duì)每個(gè)節(jié)點(diǎn)給以標(biāo)號(hào)。標(biāo)號(hào)分為兩類(lèi)：臨時(shí)標(biāo)號(hào)Lj和永久標(biāo)號(hào)dj。Lj表示從vs開(kāi)始到被標(biāo)號(hào)點(diǎn)vj的最短路權(quán)的一個(gè)上界，dj表示從vs開(kāi)始到被標(biāo)號(hào)點(diǎn)vj的真正最短路權(quán)。另外，引進(jìn)集合N表示永久性標(biāo)號(hào)集合。開(kāi)始時(shí)，對(duì)vs有ds=0，其余各節(jié)點(diǎn)vj（j≠s ）則有Lj=ωij。算法的每一輪迭代都得到一個(gè)永久性標(biāo)號(hào)，直到所有點(diǎn)都得到永久性標(biāo)號(hào)為止。具體的算法流程圖如圖1所示。

3 算 例

在實(shí)際運(yùn)用中，由于兩個(gè)城市間的道路連接形式可能多種多樣，如高速公路、普通公路、國(guó)道、鐵路、水路等，每一種形式的運(yùn)費(fèi)、距離以及所需要的運(yùn)輸時(shí)間都不相同，如果每個(gè)城市當(dāng)作一個(gè)節(jié)點(diǎn)，則無(wú)法反映上述情況，為了解決這個(gè)問(wèn)題，本文采用增加節(jié)點(diǎn)的方法，即一個(gè)城市多個(gè)節(jié)點(diǎn)。但這樣又會(huì)出現(xiàn)終點(diǎn)不唯一的情況，可用虛擬點(diǎn)加以解決，即將幾個(gè)終點(diǎn)匯總成一個(gè)終點(diǎn)，其間的運(yùn)費(fèi)、運(yùn)輸時(shí)間、距離都為零。下面以某汽車(chē)股份公司的物流調(diào)度為例，首先根據(jù)實(shí)際運(yùn)輸情況，得出運(yùn)輸線路有向圖如圖2所示。

圖中V4、V11為虛擬點(diǎn)，虛線表示0費(fèi)用，0時(shí)間，第一個(gè)權(quán)為費(fèi)用權(quán) （單位：元），第二個(gè)權(quán)為時(shí)間權(quán) （單位：小時(shí)），并根據(jù)銷(xiāo)售情況得到時(shí)間約束T=13小時(shí)。其求解過(guò)程如下：

（1）迭代過(guò)程見(jiàn)表1所示，表的左邊表示迭代次數(shù)，中部為迭代過(guò)程中累計(jì)成本和累計(jì)運(yùn)輸時(shí)間，每一次得到的永久性標(biāo)號(hào)的先行節(jié)點(diǎn)，表示在表的右邊。

表1 迭代過(guò)程

（2）反向跟蹤得滿足約束的最小費(fèi)用路徑。根據(jù)表1迭代結(jié)果，由終點(diǎn)V11反向跟蹤先行節(jié)點(diǎn)V10，依次跟蹤到起始點(diǎn)V1，得到滿足約束的最小費(fèi)用路徑為：V1—V3—V4—V6—V7—V10—V11。該路徑所需要的成本費(fèi)用為840元，運(yùn)輸時(shí)間為13小時(shí)。

4 結(jié)束語(yǔ)

本文通過(guò)分析車(chē)輛運(yùn)輸?shù)馁M(fèi)用和時(shí)間情況，以最小運(yùn)輸費(fèi)用為目標(biāo)，規(guī)定時(shí)間為約束條件，建立車(chē)輛調(diào)度路線優(yōu)化的數(shù)學(xué)模型，并在Dijkstra算法基本思想的基礎(chǔ)上，提出解決多權(quán)約束的最短路問(wèn)題的方法，給出了該方法的算法流程，同時(shí)利用增加節(jié)點(diǎn)和虛擬節(jié)點(diǎn)的方法，解決了實(shí)際中可能遇到的問(wèn)題，為降低車(chē)輛調(diào)度的運(yùn)輸費(fèi)用提供理論依據(jù)和實(shí)現(xiàn)方法，最后通過(guò)實(shí)例加以驗(yàn)證，表明該算法能夠得到優(yōu)化的結(jié)果。

[1] 肖建輝.車(chē)輛路徑優(yōu)化文獻(xiàn)綜述[J].廣東技術(shù)師范學(xué)院學(xué)報(bào)，2010(12):31-37.

[2] 李仁安，袁際軍.基于改進(jìn)遺傳算法的物流配送路線優(yōu)化研究[J].武漢理工大學(xué)學(xué)報(bào)，2004(12):99-101.

[3] Lee C.G.,Marina A.,Cheslsea C.,et al.A shortest path approach to the multiple-vehicle routing problem with split pickups[J].Transportation Research,2006(40):265-284.

[4] 楊躍武.一種新的基于最小生成樹(shù)的物流配送優(yōu)化路線算法[J].計(jì)算技術(shù)與自動(dòng)化，2008(3):24-28.

[5] 郭淑紅，楊曉慧.遺傳算法在物流配送路徑優(yōu)化問(wèn)題中的應(yīng)用[J].硅谷，2009(1):46-47.

[6] 程理民，吳江.運(yùn)籌學(xué)模型與方法教程[M].北京：清華大學(xué)出版社，2003:45-50.

[7] 馮輝宗，陳勇，劉飛.基于遺傳算法的配送車(chē)輛優(yōu)化調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng)，2004(12):81-84.

The Optimization of Logistics Transportation Routing Based on Time Restriction

YAO Wei,DING Bi-rong,LV Kun
(School of Machinery and Automobile Engineering,Hefei University of Technology,Hefei 230009,China)

在分析車(chē)輛運(yùn)輸費(fèi)用和運(yùn)輸時(shí)間的基礎(chǔ)之上，建立一個(gè)以規(guī)定時(shí)間內(nèi)最小費(fèi)用為目標(biāo)的物流調(diào)度路線優(yōu)化數(shù)學(xué)模型。同時(shí)給出車(chē)輛路線問(wèn)題的求解算法思路和計(jì)算流程，并結(jié)合實(shí)例，采用Dijkstra迭代方法，討論該算法的應(yīng)用。從而為在物流調(diào)度的車(chē)輛運(yùn)輸路線優(yōu)化中實(shí)現(xiàn)在滿足時(shí)間約束條件下達(dá)到運(yùn)輸費(fèi)用最低提供依據(jù)和方法。

時(shí)間約束；物流調(diào)度；車(chē)輛路線問(wèn)題；最短路問(wèn)題

Through analyzing cost and time of automobiles transportation,practical mathematic model of route optimize in logistics distribution was established,which object was lowest costs in stated time.The algorithmic method and flow of vehicle route problem was presented,and based on example,adopted Dijkstra relaxation,discussed application of the algorithmic method.So it can offer gist and means for carrying out lowest transport costs during the optimization of logistics distribution routing in vehicle transportation,and satisfying time restriction.

time restriction;logistics distribution;vehicle route problem;shortest path theory

U116.2

A

2010-12-13

姚 薇（1975-），女，安徽桐城人，合肥工業(yè)大學(xué)機(jī)械與汽車(chē)工程學(xué)院碩士研究生，研究方向：物流工程；丁必榮（1978-），男，安徽合肥人，合肥工業(yè)大學(xué)機(jī)械與汽車(chē)工程學(xué)院，講師，主要從事企業(yè)信息化工程和物流管理信息系統(tǒng)等方面的研究。

1002-3100(2011)03-0087-03