動態(tài)閉環(huán)復雜配送網(wǎng)絡路徑優(yōu)化算法研究

張 旭 鳳， 張 永 安， 楊 麗

（1.北京物資學院物流學院，北京市 101149；2.北京工業(yè)大學經(jīng)濟與管理學院，北京市 100124；3.南京航空航天大學經(jīng)濟與管理學院，江蘇 南京 210016）

一、引言

隨著物流業(yè)的全球化、信息化與一體化發(fā)展，物流配送在整個物流系統(tǒng)中的作用變得越來越重要。物流配送本質上是運輸，因此創(chuàng)造空間效用自然成為它的主要功能。但物流配送又不同于運輸，它是運輸在功能上的延伸。物流運輸系統(tǒng)是物流配送系統(tǒng)中最重要的一個子系統(tǒng)，運輸費用超過企業(yè)物流總消耗的40%，[1]降低物流成本首先要從降低物流配送的運輸成本開始。其中，運輸路徑的合理性直接影響物流配送速度、成本和效益，特別是多用戶物流配送路徑的確定是一項復雜的系統(tǒng)工程。車輛路徑的恰當選取，有利于加快對客戶需求的響應速度，提高服務質量，增強客戶對物流環(huán)節(jié)的滿意度，降低服務商運作成本。

基于發(fā)展循環(huán)經(jīng)濟、綠色物流的理念，本文將逆向物流配送與正向物流配送相結合，并在此基礎上提出閉環(huán)物流配送。所謂閉環(huán)物流配送即充分考慮傳統(tǒng)物流配送過程中出現(xiàn)的逆向物流，并將正向物流配送與逆向物流配送結合起來進行系統(tǒng)分析和處理，使整個物流配送系統(tǒng)變得更加合理。因此，閉環(huán)物流配送網(wǎng)絡不僅包括傳統(tǒng)的正向物流配送網(wǎng)絡，同時還包括退貨和廢舊品回收再利用的逆向物流配送網(wǎng)絡，而且最為重要的是兩條配送網(wǎng)絡上的物流并非相互獨立，而是呈現(xiàn)出“從源到匯，再由匯到源”的閉環(huán)特征。因此，從物流角度講，閉環(huán)物流配送實質上是通過產(chǎn)品的正向交付與逆向回收再利用，使“資源—生產(chǎn)—消費—廢棄”的開環(huán)過程變成“資源—消費—再生資源”的閉環(huán)反饋循環(huán)過程。[2]逆向物流配送網(wǎng)絡是閉環(huán)物流配送網(wǎng)絡上的一個特殊環(huán)節(jié)。然而，閉環(huán)物流配送網(wǎng)絡不是簡單地將正向物流配送網(wǎng)絡與逆向物流配送網(wǎng)絡相加，而是涉及從戰(zhàn)略層到運作層的每一個層面，比傳統(tǒng)物流配送要復雜得多。它不僅具有傳統(tǒng)物流配送所有的特點，而且增加了許多新的特性。閉環(huán)物流配送的存在不僅是環(huán)境與可持續(xù)發(fā)展的要求，而且也是企業(yè)自身發(fā)展和獲取競爭優(yōu)勢的需要。環(huán)境與非環(huán)境因素共同造就了閉環(huán)物流配送的產(chǎn)生和發(fā)展。

閉環(huán)物流配送網(wǎng)絡是配送過程中相互聯(lián)系的組織與設施的集合，是由物流配送節(jié)點與運輸線路連接而成的一個網(wǎng)絡，根據(jù)逆向物流方式的不同，可分為制造商自己負責逆向物流配送、委托零售商負責逆向物流配送和委托第三方負責逆向物流配送三種。本文重點研究制造商自己負責逆向物流配送的閉環(huán)物流配送網(wǎng)絡，如圖1所示。網(wǎng)絡中的運輸線路代表不同庫存或儲存點之間貨物的移動路線，而物流配送節(jié)點就是商品的儲存點或需求點，如倉庫、配送中心、物流中心、工廠、供貨商或零售店等。任意一對物流節(jié)點之間都可能有多條運輸線路相連接，這些線路代表了不同的運輸方式、不同的運輸路線或不同的商品。物流節(jié)點也代表那些貨物流動過程中的臨時經(jīng)停點，如貨物在運達零售店或最終消費者之前進行短暫停留的倉庫。

圖1 制造商自己負責逆向物流的閉環(huán)物流配送網(wǎng)絡

二、相關研究綜述

對于物流的復雜性特點，學者們從不同角度出發(fā)進行了研究。張貝[3]對逆向物流網(wǎng)絡設計的復雜性進行了研究，并對逆向物流網(wǎng)絡設計模型與方法進行了分析與總結。王玉琳等[4]對物流管理系統(tǒng)組成的多元化和復雜性、功能的整體性、運作機制的隨機動態(tài)性和開放性等特征進行了分析。張公讓等[5]認為，物流管理具有結構、環(huán)境、行為等方面的動態(tài)、開放、凸顯等特點，屬于復雜系統(tǒng)的范疇。趙國智等[6]分析了煤炭物流網(wǎng)絡的復雜網(wǎng)絡特征，并運用復雜網(wǎng)絡的相關理論與方法分析煤炭物流網(wǎng)絡，對基于復雜網(wǎng)絡的煤炭物流網(wǎng)絡優(yōu)化方法進行了研究。

對于車輛路徑優(yōu)化問題，學者們從不同方面利用不同方法進行了大量研究，主要可分為精確算法和近似算法兩大類。求解車輛路徑優(yōu)化的精確算法主要包括分支定界算法、[7]列生成算法、[8]動態(tài)規(guī)劃算法、[9]分支切割算法；[10]求解車輛路徑優(yōu)化的近似算法包括人工神經(jīng)網(wǎng)絡算法、遺傳算法、模擬退火算法、禁忌算法等。

目前，有關逆向物流定量模型的研究大多集中于網(wǎng)絡結構。1989年，梅恩（Min）首先提出了同時收發(fā)送的混合車輛路徑優(yōu)化問題（簡稱VRPSDP）。[11]2001年，戴德羅夫（Dethloff）又重新提出該問題。[12]車輛路線問題還包括一類有回載的車輛路線問題（簡稱VRPB），[13]主要考慮收集和配送為各自獨立的兩個部分的情形，車輛從某些客戶點收集產(chǎn)品后再配送到另外的某些客戶點，沒有考慮正向物流與逆向物流的整合。戴德羅夫指出，VRPB的求解方法不能用于解決VRPSDP問題。[14]上述文獻本質上屬于車輛路線優(yōu)化問題，其目標是行駛路線最短，但多數(shù)研究并沒有考慮逆向物流的復雜性特點以及逆向物流與正向物流的有機整合。

針對上述逆向物流與正向物流整合中的物流配送路徑優(yōu)化問題，本文采用一類動態(tài)規(guī)劃模型來對閉環(huán)復雜物流配送網(wǎng)絡路徑優(yōu)化問題進行研究。

三、物流配送網(wǎng)絡的復雜性分析

物流配送網(wǎng)絡具有時空復雜性的重要特點，是一個與我們的生活、工作、社會經(jīng)濟環(huán)境密切相關的復雜大系統(tǒng)。應用復雜網(wǎng)絡理論從理論上分析物流配送網(wǎng)絡拓撲結構復雜性，是研究復雜物流配送網(wǎng)絡的關鍵所在，也是物流配送網(wǎng)絡研究的基礎理論問題之一。物流配送系統(tǒng)的運行效率受多方面因素的影響，要從整體、宏觀的角度去了解物流配送網(wǎng)絡，就要對系統(tǒng)各個部分之間的相互作用有一個清晰的認識。物流配送網(wǎng)絡不僅具有與其他復雜網(wǎng)絡相似的一些拓撲特性，而且具有不同于其他復雜網(wǎng)絡的顯著特點，比如自主性和選擇性。而通過融合物流配送網(wǎng)絡自身的特點，深入分析拓撲結構對物流配送網(wǎng)絡承載力的影響以及緩解物流瓶頸問題的策略是物流配送網(wǎng)絡復雜性研究中非常重要的方面。同時，還必須從系統(tǒng)的角度出發(fā)，對物流節(jié)點以及節(jié)點的物流特征進行分析與合理的規(guī)劃和管理，以達到有效緩解物流配送瓶頸的目的。此外，對本身是動態(tài)實體的物流配送網(wǎng)絡來說，適應性和動態(tài)性也是其基本特性。這意味著物流配送網(wǎng)絡拓撲結構不是固定的、成熟的，也不是一成不變的。相反，由于外部作用的驅動或者內(nèi)部元素的作用，允許它隨時間進行演化和調(diào)節(jié)。因此，有關這方面的研究可以從宏觀角度幫助我們理解物流配送網(wǎng)絡演化的內(nèi)在機理和運行規(guī)律，進而為提出解決物流問題的有效方法提供理論依據(jù)，為切實提高整個物流配送網(wǎng)絡承載能力，充分利用現(xiàn)有交通資源降低我國物流配送網(wǎng)絡建設設計、管理和控制的盲目性，科學制定我國物流發(fā)展戰(zhàn)略規(guī)劃，發(fā)展先進的物流管理與控制技術打下堅實的理論基礎。

物流配送網(wǎng)絡是一個復雜的網(wǎng)絡結合體，單就物流配送網(wǎng)絡所要實現(xiàn)的某一特定功能而言，可以比較容易地將其歸類于某一種網(wǎng)絡。比如，僅考察物流配送工具（如車輛）在物流配送網(wǎng)絡上的活動，可將之歸類于社會網(wǎng)絡；而僅考察物流配送網(wǎng)絡承擔的物流量的分配，可將之歸類于技術的分配網(wǎng)絡；僅考察物理層面的物流配送網(wǎng)絡，其物流配送網(wǎng)絡的形成可歸類于技術網(wǎng)絡的構建。而物流配送網(wǎng)絡恰恰是這些功能的承載體，是混合型的復雜網(wǎng)絡。

此外，對于物流配送網(wǎng)絡拓撲結構的復雜性完全可以用復雜網(wǎng)絡的理論進行研究，主要包括三個方面：（1）就簡單的拓撲統(tǒng)計規(guī)律而言，物流配送網(wǎng)絡的整體集合可能具有規(guī)則網(wǎng)絡的某些特性，但根據(jù)我們研究的對象及目的，完全可以根據(jù)不同的拓撲表示方式對其進行抽象，從而展示出非常復雜的重要拓撲特征。（2）就其動力學行為或特征而言，它具有明顯的復雜性特征。如物流節(jié)點不停地進行物流庫存產(chǎn)生和轉移，這些節(jié)點之間已經(jīng)不再是簡單的起點與終點的關系。另外，物流配送網(wǎng)絡節(jié)點上物流阻塞的形成、傳播及消散等規(guī)律也具有非常復雜的動態(tài)特性。因此，它在簡單的貌似規(guī)則網(wǎng)絡的平面格子上不得不背負著復雜網(wǎng)絡相關統(tǒng)計動力學特性，如物流流量的分配、阻塞的傳播與消散等。（3）就物流配送網(wǎng)絡的演化特征而言，網(wǎng)絡拓撲對物流配送網(wǎng)絡上物流流量分布及其他動力學過程具有潛在的巨大影響。

復雜網(wǎng)絡上的物流配送動力學研究所依賴的底層拓撲基于兩個基本思想：（1）通過一般的網(wǎng)絡產(chǎn)生機制給定一個底層的拓撲，在這樣的拓撲上進行各種動力學演化；（2）網(wǎng)絡上的動力學行為反過來影響網(wǎng)絡拓撲演化。

目前，復雜網(wǎng)絡在物流配送網(wǎng)絡系統(tǒng)中所對應的是物流配送網(wǎng)絡系統(tǒng)的拓撲結構、物流配送網(wǎng)絡系統(tǒng)的形成和演化以及物流配送網(wǎng)絡系統(tǒng)的動力學機制和穩(wěn)定性等問題。

四、任務模型與系統(tǒng)模型

由于閉環(huán)物流配送系統(tǒng)中雙向的物流配送增加了閉環(huán)物流配送網(wǎng)絡規(guī)劃的困難，因此設施的有效共用能有效降低物流成本，也就是說，物流配送網(wǎng)絡中制造商、配送中心及零售商等的設施也可以進行廢舊品處理或缺陷品回收等。最終客戶在地域上的分散性以及擁有廢舊品的少量性，使得正向物流和逆向物流配送線路與運輸能力的整合，常常導致高昂的廢舊品回收成本。由于回收與配送差異巨大，合理安排產(chǎn)品與廢舊品之間的運輸線路與運輸能力變得至關重要。因此，本文考慮由制造商退還貨物和廢舊品。

閉環(huán)物流配送系統(tǒng)涉及物流配送節(jié)點的地理位置、交通運輸條件、配送物資的供求關系以及回收物資等客觀因素，我們可根據(jù)這些將物流配送網(wǎng)絡劃分為若干物流配送子系統(tǒng)。

我們將之劃分為 n 個子系統(tǒng)，t=1，2，…，n。

假定在一個時間周期內(nèi)，從系統(tǒng)內(nèi)的一個物流配送中心（假定為節(jié)點1）發(fā)出一輛物流配送車向該系統(tǒng)內(nèi)的各個節(jié)點配送物資，配送完成后再把各個節(jié)點的物資（包括退貨與回收物資）送回節(jié)點1。試研究物流配送車行駛的最短路徑及行駛路線。

五、算法設計

依據(jù)問題的特點，建立閉環(huán)物流配送路徑優(yōu)化動態(tài)規(guī)劃模型如下：

根據(jù)問題的要求，從節(jié)點1出發(fā)到最后回到節(jié)點1，中間需要經(jīng)過n個節(jié)點，將子系統(tǒng)物流配送問題劃分為n個階段，階段變量 k=1，2，…，n。

假定物流配送車從節(jié)點1出發(fā)行駛到節(jié)點i，記Ni={2，3，…，i-1，i+1，…，n}，用以表示由節(jié)點 1 到節(jié)點 i可能經(jīng)過的中間節(jié)點的集合，Q表示由節(jié)點1到節(jié)點i經(jīng)過的中間節(jié)點的集合，則Q∈Ni。

狀態(tài)變量用（i，Q）表示，即物流配送車從節(jié)點1出發(fā)行駛到節(jié)點i，中間所經(jīng)過節(jié)點的集合為Q。（i，θ）表示物流配送車從節(jié)點1出發(fā)，直接行駛到節(jié)點i，中間不經(jīng)過其他節(jié)點，其中θ表示空集。

決策變量pk（ik+1，Qk）=ik表示決定配送車從節(jié)點ik-1行駛到節(jié)點ik。

最優(yōu)值函數(shù)fk（i，Q）表示配送車從節(jié)點1經(jīng)過k個中間節(jié)點（Q表示k個中間節(jié)點的集合）到達節(jié)點i的最短路線距離。

建立遞推公式如下：

其中，k=1，2，…，n-1；i=2，3，…，n。

其中，邊界條件f0（i，θ）表示配送車從節(jié)點1出發(fā)不經(jīng)過中間節(jié)點（Q=θ）直接到達節(jié)點i的距離dji。

最優(yōu)值函數(shù)fn-1（1，Nn，1），Nn，1={2，3，…，n}，即為所求第n個子系統(tǒng)的配送車從節(jié)點1出發(fā)到達其他n-1個中間節(jié)點一次且僅一次，再回到節(jié)點1的最短路線距離。配送車行配送車從節(jié)點1出發(fā)經(jīng)過k個中間節(jié)點一次且僅一次（Qk的前一個節(jié)點ik。

在每個子配送系統(tǒng)優(yōu)化的基礎上，可最終實現(xiàn)整個物流配送網(wǎng)絡系統(tǒng)路徑的最優(yōu)化：

其中，Z表示n個子配送系統(tǒng)中物流配送車行駛距離的總和。

六、算法應用

某閉環(huán)復雜物流配送網(wǎng)絡如圖2所示。其中，某子物流配送網(wǎng)絡中的配送中心A下屬五個商品超市，配送中心A每天從配送中心發(fā)出配送車，將商品配送到每個超市，卸貨后再將退貨和回收品裝車，依次到達下一個目的地，最后將退貨和回收品帶回配送中心。表1給出了配送中心與五個超市之間的距離（單位：公里），要求配送車從配送中心出發(fā)經(jīng)過每個超市一次且僅一次，最后回到配送中心，求配送車行駛的最優(yōu)路線與最短距離。

我們把配送中心、超市1、…、超市5依次進行編號，分別設為節(jié)點 1、節(jié)點 2、…、節(jié)點 6。由題設條件 dij≠dji，i≠j，i，j=1，2，…，6可知，此配送系統(tǒng)的交通圖是一個有向多重連通圖。根據(jù)上述討論，我們采用順推法求解物流配送車行駛的最優(yōu)路線和最短距離。

最后得到物流配送車最優(yōu)行駛路線為節(jié)點1→節(jié)點2→節(jié)點6→節(jié)點5→節(jié)點4→節(jié)點3→節(jié)點1，最短距離為114公里。

七、結論與展望

圖2 某物流配送網(wǎng)絡圖

表1 各節(jié)點物流配送距離

1.研究結論。本文通過對物流配送網(wǎng)絡復雜性的分析，利用動態(tài)規(guī)劃算法對目前閉環(huán)復雜物流配送網(wǎng)絡中的最優(yōu)路徑精確計算問題進行了研究。經(jīng)驗證，計算結果與實際情況相符合。本文雖然只對閉環(huán)復雜物流網(wǎng)絡中某一子系統(tǒng)的物流配送路徑優(yōu)化進行了研究，但對于整個閉環(huán)復雜物流配送網(wǎng)絡來說，可利用這種方法，將各子系統(tǒng)中的物流配送中心作為配送目標節(jié)點，將物流網(wǎng)絡中總的配送中心作為配送中心，依此類推，從而能夠對整個物流配送網(wǎng)絡以及某個子物流配送網(wǎng)絡的配送路徑進行優(yōu)化研究。

使用本文方法，可將子物流配送網(wǎng)絡的路徑優(yōu)化研究擴展到整個復雜物流配送網(wǎng)絡的路徑優(yōu)化研究，為研究整體閉環(huán)復雜物流配送網(wǎng)絡路徑優(yōu)化問題提供新的思路。

2.研究的局限性。本文僅對具有6個節(jié)點的子物流配送系統(tǒng)進行了計算，最優(yōu)解的求解較為容易。如果子系統(tǒng)節(jié)點很多，手工計算的工作量很大，就需要借助計算機及相應軟件來進行計算。另外，本文只對退貨及回收物資與所送物品可同用一車載送的問題進行了分析，而未考慮正向物流物品與逆向物流物品不可同載的問題。

在以后更進一步的研究中，需要在考慮上述問題的同時，繼續(xù)研究制造商處理回收品時如何解決某些客戶具有的優(yōu)先權問題以及回收品數(shù)量為隨機變量情況下的閉環(huán)物流回載策略問題等。

[1]劉志強，丁鵬，盛華燁.物流配送系統(tǒng)設計[M].北京：清華大學出版社，2004：22-37.

[2]馮之浚，張偉，郭強等.循環(huán)經(jīng)濟與末端治理的范式比較研究[N].光明日報，2003-09-22（3）.

[3]張貝.逆向物流網(wǎng)絡設計復雜性分析及研究現(xiàn)狀[J].物流技術，2005（12）：41-43.

[4]王玉琳，王諍諍.現(xiàn)代物流管理系統(tǒng)的復雜性分析[J].系統(tǒng)辯證學學報，2003，11（4）：88-91.

[5]張公讓，代軍旗，楊波.物流管理系統(tǒng)中的復雜性特征研究[J].價值工程，2009（4）：70-73.

[6]趙國智，王喜富等.煤炭物流網(wǎng)絡的復雜性分析及優(yōu)化方法研究[J].物流技術，2008，27（8）：117-119.

[7]N.Christofides，A.Mingozzi，P.Toth.Exact Algorithms for the Vehicle Routing Problem,Based on Spanning Tree and Shortest Path Relaxations[J].Mathematical Programming，1981（20）：255-282.

[8]M.Balinski，R.Quandt.On an Integer Program for a Delivery Problem[J].Operations Research，1964（12）：300-304.

[9]S.Eilon，C.D.T.Watson-Gandy，N.Christofides.Distribution Management：Mathematical Modeling and Practical Analysis[M].London：Griffin，1971：79-86.

[10]A.Letchford，R.Eglese，J.Lysgaard.Multistars，Partial Multistars and the Capacitated Vehicle Routing Problem[J].Mathematical Programming，2002（94）：21-40.

[11]H.Min.The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pickup Points[J].Transportation Research Part A，1989，23A（3）：377-386.

[12]、[14]Jan Dethloff.Vehicle Routing and Reverse Logistics：the Vehicle Routing Problem with Simultaneous Delivery and Pick-up[J].Operations Research Spektrum，2001，23（1）：79-96.

[13]J.Dethloff.Relation between Vehicle Routing Problems"An Insertion Heuristic for the Vehicle Routing Problem with Simultaneous Delivery and Pick-up Applied to the Vehicle Routing Problem with Backhauls[J].Journal of the Operational Research Society，2002，53（1）：115-118.