陳文強 顧玉磊

長安大學(xué)，經(jīng)濟管理學(xué)院，西安 710064

0 引 言

在物流配送網(wǎng)絡(luò)中，物流配送商如何按照一定的規(guī)則選擇最優(yōu)路徑，完成物流需求配送工作，一直是研究者的重要課題，研究成果豐富。例如，H.C.Joksch[1]提出一類帶有時間約束的最短配送路徑問題，并給出了靜態(tài)的規(guī)劃方法；G.Handier[2]提出了邊帶成本約束的最短配送路徑問題，并證明其屬于NP 完備問題，并給出了一個對偶算法；J.More等[3]提出了一個雙目標(biāo)最短配送路徑問題，并給出了算法。上述模型一般為定常需求模型或為靜態(tài)路徑模型，其對中長期物流配送網(wǎng)絡(luò)的規(guī)劃是有效的。但是，在現(xiàn)代物流網(wǎng)絡(luò)中，由于交通事故、道路擁擠、天氣變化等偶發(fā)因素常引起物流配送網(wǎng)絡(luò)的動態(tài)變化性（OD 對之間的最優(yōu)路徑是時變的），因此，利用傳統(tǒng)靜態(tài)最優(yōu)配送路徑模型研究實際問題時，容易導(dǎo)致決策錯誤[4]?；诖?，本文充分考慮了動態(tài)出發(fā)時間和運輸過程延遲對配送路徑選擇的影響，提出了基于時間、費用的雙目標(biāo)決策的動態(tài)物流網(wǎng)路配送最優(yōu)路徑模型。

1 問題分析

1.1 問題表述

本文所述物流配送網(wǎng)絡(luò)是基于城市道路網(wǎng)組成的物流網(wǎng)絡(luò)，由運輸路徑，物流配送節(jié)點組成?；谖锪髋渌托枨筇攸c，將物流運輸網(wǎng)絡(luò)進行抽象。物流配送網(wǎng)絡(luò)被抽象為矢量圖，物流配送節(jié)點是圖中的節(jié)點，運輸路徑是圖中的線，配送方向與物流方向一致。圖1 是一個典型的物流配送網(wǎng)絡(luò)幾何抽象圖g，由配送網(wǎng)絡(luò)節(jié)點N、運輸路徑A 和時間T 構(gòu)成，此圖也可以用函數(shù)G=f(N,A,T)表示。如何在物流配送網(wǎng)絡(luò)g 中，符合實際地選取基于動態(tài)時間和費用的最優(yōu)配送路徑O-D（從O 點到達D點）是本文的基本問題。

1.2 問題的解決思路

圖1 典型物流配送網(wǎng)絡(luò)抽象Fig.1 A typical distribution network

多目標(biāo)最優(yōu)配送路徑問題的一般處理方式是把多目標(biāo)轉(zhuǎn)化為單目標(biāo)去求解[5]，從而使時間、費用相關(guān)的最優(yōu)路徑轉(zhuǎn)化為單目標(biāo)最優(yōu)路徑問題。物流配送需求實現(xiàn)過程由運輸過程和裝卸過程兩部分組成，所以，本文采用兩階段分析法，把最優(yōu)路徑問題分為兩個部分，建立各自模型，最后聯(lián)合分析求解總目標(biāo)（費用最小路徑）。

2 模型構(gòu)建

配送過程中，最優(yōu)配送路徑選擇往往是由多種因素決定的。但時間和費用一般是決定最優(yōu)配送路徑的主要影響因素，并且，影響效果一般通過實際配送費用來計量[6]。由于物流需求的異質(zhì)性，同一種服務(wù)反映的實際費用會有所不同。為清晰反映實際費用構(gòu)成，本文把實際費用分為客觀費用和貨物時間價值損失。所謂貨物時間價值的損失，是指物流需求沒有在規(guī)定時間內(nèi)到達目的地，使貨物失去一定時間價值。它可用兩個參數(shù)乘積（前提假設(shè)，時間價值是在途時間和時間價值損失系數(shù)的線性函數(shù)）來表示，即貨物在途時間與貨物（出行時間和配送延遲）時間價值損失系數(shù)乘積。

物流配送需求實現(xiàn)全程由運輸過程和裝卸過程兩部分組成，實際費用也可以分為運輸過程費用和裝卸過程費用。

2.1 運輸過程費用模型函數(shù)

運輸過程費用由運輸客觀費用和運輸時間價值損失組成，運輸客觀費用也可稱為運輸過程的固定費用（燃料、人工、損耗等），它是由運輸技術(shù)經(jīng)濟特性決定的；運輸時間價值損失是貨物對運輸時間延遲的價值缺失表現(xiàn)，用運輸過程時間*貨物運輸時間價值損失系數(shù)來表示。那么，運輸過程費用可用函數(shù)（1）表示。

αm(t)——出發(fā)時間為t 的m 類物流需求運輸時間價值損失系數(shù)（運輸造成的時間價值損失系數(shù)定義如下：在規(guī)定的時間內(nèi)將貨物運到目的地，運輸時間價值損失系數(shù)為零。距離貨物失去時間價值的時間越遠，由于運輸造成的時間價值損失系數(shù)越大）。

2.2 裝卸過程費用模型函數(shù)

如運輸過程費用一樣，裝卸過程費用也分為裝卸過程固定費用（客觀費用）和裝卸過程時間價值損失。裝卸過程固定費用由像裝卸費、人工等相關(guān)固定費用組成；裝卸過程時間價值損失是由于裝卸時間延遲等而造成貨物價值的損失，用裝卸過程時間乘以裝卸時間價值損失系數(shù)表示。裝卸過程相關(guān)費用函數(shù)如（2）所示。

2.3 最小費用路徑模型函數(shù)

在物流配送網(wǎng)絡(luò)中要想找出最小費用路徑，物流配送需求實現(xiàn)費用模型必須計算經(jīng)由每一個節(jié)點的運輸相關(guān)費用和裝卸相關(guān)費用。根據(jù)這一原則，整個運輸過程費用模型函數(shù)設(shè)計如式（3）所示。

此模型最明顯特征就是把整個配送過程的固定配送費用和時間價值損失很直觀的聯(lián)系起來，并且可以清楚的表明整個配送過程實際費用的明細。

3 模型求解

3.1 算 法

最小配送費用路徑求解采用倒推法由終節(jié)點D向前推進[7]，具體步驟如下。

則節(jié)點k 為最優(yōu)路徑的一個節(jié)點。

（2）重復(fù)步驟（1），找出k 節(jié)點的上一個最優(yōu)路徑節(jié)點τ-1(k)；

（3）重復(fù)步驟（2），直到找出最優(yōu)路徑的所有的節(jié)點；

（4）結(jié)束算法。

此算法從終節(jié)點向前推進，算法過程其實就是檢查一個節(jié)點k 前一個節(jié)點τ-1(k)是否存在一條路徑使節(jié)點k 到τ-1(k)的費用最小，如果條件滿足，τ-1(k)是條件點之一。依此類推，直到找出所有符合條件的節(jié)點，這些點組成的路徑就是基于時間相關(guān)的物流網(wǎng)絡(luò)最小配送費用路徑。

為保證算法的合理性，必須對參數(shù)進行合理設(shè)置。

3.2 正確性檢驗

如果目標(biāo)函數(shù)值為有限數(shù)，則目標(biāo)函數(shù)形式為

且必滿足下幾種情形之一。

如果是情形①或②或③發(fā)生，則進入算法步驟（2）；

如果發(fā)生情形④且j≠D，則目標(biāo)函數(shù)為

那么進入算法步驟（1）。

無論模型算法還是正確性檢驗，均可以在計算機環(huán)境下自動實現(xiàn)。

4 實例證明

假設(shè)物流配送網(wǎng)絡(luò)如圖2 所示，從O 點出發(fā)進行物流配送，D 點集結(jié)補養(yǎng)，綜合考慮運輸相關(guān)費用和裝卸相關(guān)費用，求解最佳配送路徑。利用Netlog軟件，編寫程序，模擬運算，結(jié)果如下圖（黑粗線）所示。

圖2 最優(yōu)物流配送路徑Fig.2 The optimal logistics path

圖例中黑色區(qū)域是備選路徑和節(jié)點組成的三角網(wǎng)絡(luò)，黑粗連接線表示算法選擇路線，即最優(yōu)配送路徑。

5 結(jié)束語

本文根據(jù)物流配送網(wǎng)絡(luò)中影響物流配送的的諸多因素，構(gòu)建了基于貨物時間價值的物流網(wǎng)絡(luò)最小配送費用路徑模型，依據(jù)物流配送的決定因素是實際配送費用，從而將多目標(biāo)最優(yōu)路徑轉(zhuǎn)化為最小配送費用路徑問題，給出模型的算法，驗證了算法的正確性，論文最后利用Netlog 軟件檢驗了模型的正確性，結(jié)果顯示，模型及算法是可行的。

[1]Jokson H.C.The shortest riute problem with constraints[J].Journal of Mathematical Analysis and Applicatilon.1996,(14):191-197.

[2]Handier G.A dual algorithm for the constrain shortest path[J].networks.1980,10(20):293-310.

[3]MORE J.,Murthy I.A parametric approach to solve constrain shortest path problem[J].European Journal of Operation Research.1991,53:81-92.

[4]Newall G.F.Flow on transportation network[M].MIT Press.1980.

[5]Ziliaskopoulos A.K.and Wardell W.An intermodal optimum path algorithm formultion modal networkswith dynamic arc travel times and switching delays[J].European Journal of Operational Research.2000,125:486-502.

[6]Jourquine B.and Beuthe M.Transportation policy analysis with a geographic information system[J].The Virtual Network of Freight Transportation in Europe,Transportation Research.1996,4C:359-371.

[7]陳文強，吳群琪.時間相關(guān)的運輸網(wǎng)絡(luò)最小費用路徑模型及算法[J].鐵道運輸與經(jīng)濟.2009,5(31):11-14.