姚 薇，丁必榮，呂 堃

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

·交通運(yùn)輸·

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

姚 薇，丁必榮，呂 堃

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

約束條件：

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

2 算法思路

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

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

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

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

3 算 例

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

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

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

表1 迭代過程

（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)輸時間為13小時。

4 結(jié)束語

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

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

[2] 李仁安，袁際軍.基于改進(jìn)遺傳算法的物流配送路線優(yōu)化研究[J].武漢理工大學(xué)學(xué)報，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] 楊躍武.一種新的基于最小生成樹的物流配送優(yōu)化路線算法[J].計算技術(shù)與自動化，2008(3):24-28.

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

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

[7] 馮輝宗，陳勇，劉飛.基于遺傳算法的配送車輛優(yōu)化調(diào)度[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)

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

時間約束；物流調(diào)度；車輛路線問題；最短路問題

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

1002-3100(2011)03-0087-03