陳文強(qiáng) 顧玉磊

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

0 引 言

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

1 問題分析

1.1 問題表述

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

1.2 問題的解決思路

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

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

2 模型構(gòu)建

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

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

2.1 運(yùn)輸過程費(fèi)用模型函數(shù)

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

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

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

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

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

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

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

3 模型求解

3.1 算 法

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

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

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

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

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

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

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

3.2 正確性檢驗(yàn)

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

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

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

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

那么進(jìn)入算法步驟（1）。

無論模型算法還是正確性檢驗(yàn)，均可以在計(jì)算機(jī)環(huán)境下自動(dòng)實(shí)現(xiàn)。

4 實(shí)例證明

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

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

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

5 結(jié)束語

本文根據(jù)物流配送網(wǎng)絡(luò)中影響物流配送的的諸多因素，構(gòu)建了基于貨物時(shí)間價(jià)值的物流網(wǎng)絡(luò)最小配送費(fèi)用路徑模型，依據(jù)物流配送的決定因素是實(shí)際配送費(fèi)用，從而將多目標(biāo)最優(yōu)路徑轉(zhuǎn)化為最小配送費(fèi)用路徑問題，給出模型的算法，驗(yàn)證了算法的正確性，論文最后利用Netlog 軟件檢驗(yàn)了模型的正確性，結(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]陳文強(qiáng)，吳群琪.時(shí)間相關(guān)的運(yùn)輸網(wǎng)絡(luò)最小費(fèi)用路徑模型及算法[J].鐵道運(yùn)輸與經(jīng)濟(jì).2009,5(31):11-14.