分布式OD運載網(wǎng)絡中物流綠色軌跡監(jiān)測系統(tǒng)的布局優(yōu)化＊

李淑琴，楊 斌，胡志華，2

（1.上海海事大學物流研究中心，上海201306；2.同濟大學經(jīng)濟與管理學院，上海200092）

1 引言

物流的環(huán)境效益和社會責任備受關(guān)注，綠色物流的研究對于經(jīng)濟、社會以及環(huán)境之間的協(xié)調(diào)發(fā)展具有重要的理論意義和實踐意義。Murpy等人［1］對綠色物流的重要性、發(fā)展水平、動機和障礙等問題展開研究。單麗輝［1］提出基于物流網(wǎng)絡的物流資源整合模式。肖丁丁和張文峰［2］運用圖論與矩陣工具從企業(yè)、政府和環(huán)境層面進行系統(tǒng)分析。Ubeda等人［3］考慮業(yè)務盈利能力對環(huán)境的影響，在案例研究中將最大限度減少CO2排放作為評價標準。Caniato等人［4］以服裝業(yè)為例來研究供應鏈的環(huán)境可持續(xù)發(fā)展問題。Harris等人［5］在選址模型中考慮提高車輛利用率減少物流成本與能耗。朱慶華和竇一杰［6］提出綠色供應鏈管理戰(zhàn)略中生產(chǎn)商間的三階段博弈模型。

物流綠色軌跡監(jiān)測系統(tǒng)通過在相應道路上設(shè)置監(jiān)測器，構(gòu)造監(jiān)測網(wǎng)絡識別和記錄物流網(wǎng)絡中物流車輛和路段運輸量，從而獲得物流網(wǎng)絡中的“綠色軌跡”信息，實現(xiàn)對區(qū)域“綠色度”的評價。OD（Origin Destination）流是交通研究的基本工具，在物流背景下拓展為具有起止位置的運輸需求。Guo和Huang［7］在研究如何監(jiān)測和評估網(wǎng)絡中交通流量時，建立01整數(shù)規(guī)劃模型，研究OD流路徑選擇的隨機性。Nie和Zhang［8］研究基于柱生成算法的動態(tài)OD流需求估算問題。國內(nèi)外很多學者將混合整數(shù)規(guī)劃、多目標規(guī)劃和啟發(fā)式算法等運用到物流網(wǎng)絡布局優(yōu)化的研究中。Thanh等人［9］建立混合整數(shù)規(guī)劃模型優(yōu)化物流網(wǎng)絡；Pishvaee等人［10］建立物流網(wǎng)絡規(guī)劃的確定性混合整數(shù)規(guī)劃模型和隨機規(guī)劃模型。Harris等人［5］通過建立多目標優(yōu)化模型，評價CO2排放對基礎(chǔ)設(shè)施成本的影響。馬祖軍和代穎［11］建立逆向物流網(wǎng)絡優(yōu)化的混合整數(shù)規(guī)劃模型。狄衛(wèi)民［12］為回收物流網(wǎng)絡建立隨機規(guī)劃模型。本文主要通過建立一個多目標混合整數(shù)規(guī)劃模型來研究物流綠色軌跡監(jiān)測系統(tǒng)的布局優(yōu)化問題。

2 問題定義與分析

物流綠色軌跡監(jiān)測系統(tǒng)的目的是對物流網(wǎng)絡中通過的物流車輛進行識別和監(jiān)控，實現(xiàn)對道路交通流量、能耗水平和污染程度等指標的監(jiān)測。為達到這個目的，需要回答以下問題：如何在已知節(jié)點、道路以及OD流分布狀況的運載網(wǎng)絡中建立物流綠色軌跡監(jiān)測系統(tǒng)？即在監(jiān)測器數(shù)量和能力有限的情況下，如何合理部署監(jiān)測系統(tǒng)的位置；監(jiān)測器的數(shù)量為多少時監(jiān)測系統(tǒng)的能力最優(yōu)？如圖1所示，在具有10個節(jié)點的物流網(wǎng)絡中，部署由6個監(jiān)測器構(gòu)成的綠色軌跡監(jiān)測網(wǎng)絡，對通過16個路段的車輛進行監(jiān)測。

采用圖2所示的步驟進行研究。首先，對已知的分布式OD運載網(wǎng)絡，考慮到節(jié)點間的線路分布，計算出任意兩節(jié)點的最短距離。對OD運載網(wǎng)絡中的線路以最短路徑進行估計：根據(jù)最短距離計算過程，得出每條OD流所經(jīng)過的最短距離，以及每條OD流經(jīng)過的路徑。然后，考慮監(jiān)測器的數(shù)量與總成本，根據(jù)流量大小和相關(guān)性來確定安裝監(jiān)測器的位置集合。

3 模型

下面對問題進行進一步界定：（1）分布式OD運載網(wǎng)絡是一個圖（Graph），包括物流網(wǎng)絡的所有節(jié)點及節(jié)點之間的路線；（2）運載需求由每條OD流的起始點及其流量確定；（3）由O和D確定的路徑在最短路徑基礎(chǔ)上具有一定隨機性，即該需求途經(jīng)的道路可能并不完全確定；（4）運輸本身的外包情況并不熟悉，管理機構(gòu)只能通過采樣的方式獲得“綠色”評價數(shù)據(jù)；（5）物流綠色軌跡監(jiān)測系統(tǒng)中監(jiān)測器選擇安裝在線路上，避免不同線路的起始點有交集，并且對每條線路不考慮流量限制。

3.1 參數(shù)和決策變量

根據(jù)以上研究問題的說明和假設(shè)條件，相關(guān)的模型參數(shù)說明如下。

（1）集合

①N＝ ｛1，2，…，NN ｝ ：物流網(wǎng)絡中所有節(jié)點的集合；

②E＝ ｛1，2，…，NE ｝ ：物流網(wǎng)絡中所有線路的集合；

③OD ＝ ｛1，2，…，NOD ｝ ：物流網(wǎng)絡中所有OD流的集合。

（2）參數(shù)

①Da：OD流a∈OD上起始點間的流量；

②Pa，r∈ ｛0，1｝：Pa，r＝1表示OD流a∈OD經(jīng)過線路r∈E；

③S：表示監(jiān)測系統(tǒng)中安置的監(jiān)測器數(shù)量；

④Vr：表示經(jīng)過線路r∈E的OD流的總數(shù)量；

⑤RELi，j：表示線路i∈E和線路j∈E的相關(guān)性，即同時經(jīng)過線路i∈E和線路j∈E的所有OD流的流量之和。

（3）決策變量

①xr∈ ｛0，1｝：xr＝1表示選擇在線路r∈E上安裝監(jiān)測器，否則xr＝0；

②yi，j∈ ｛0，1｝：yi，j＝1表示同時在線路i∈E和線路j∈E上安裝監(jiān)測器，否則yi，j＝0。

3.2 目標函數(shù)

為了達到監(jiān)測系統(tǒng)的效用與合理性，并兼顧經(jīng)濟效益，目標函數(shù)式（1）最小化分布式運載網(wǎng)絡中任意兩條線路之間的相關(guān)性。

其中，RELi，j表示第i條線路和第j條線路之間的相關(guān)性，即同時經(jīng)過這兩條線路的OD流的流量之和，通過式（2）計算。

RQ越小，表示監(jiān)測系統(tǒng)中部署的監(jiān)測器所監(jiān)測到的重復的OD流流量越少，從而監(jiān)測系統(tǒng)的監(jiān)測能力也就越強，所獲得的樣本數(shù)據(jù)越全面。目標函數(shù)式（3）最大化所有安裝監(jiān)測器的線路所能監(jiān)測到的OD流的總數(shù)量。

其中，Vr＝ ∑aPa，r，表示在既定的運載網(wǎng)絡中，當假定OD流都能以最短路徑運行時，第r條線路上經(jīng)過的所有的OD流的條數(shù)，即第r條線路所能監(jiān)測到的OD流條數(shù)。VQ越大，表明監(jiān)測系統(tǒng)所覆蓋的監(jiān)測范圍越大。目標式（1）和式（3）之間相互影響，綜合考慮這兩個目標函數(shù)，可以對綠色軌跡進行全面評價，得到合理的監(jiān)測網(wǎng)絡部署方案。

3.3 約束條件

約束函數(shù)式（4）通過x定義y，當xi和xj同時為1時yi，j＝1，否則為yi，j＝0。約束函數(shù)式（5）對監(jiān)測器數(shù)量進行約束。

綜合以上關(guān)于決策變量、目標函數(shù)和約束函數(shù)的定義，得到多目標01整數(shù)規(guī)劃模型（P1）。

3.4 OD流網(wǎng)絡的最短路徑算法

從模型（P1）可知，OD流網(wǎng)絡中的最短路徑問題是一個基本問題。算法1在Dijkstra算法的基礎(chǔ)上提出了分布式OD運載網(wǎng)絡中求OD流最短路徑的算法。

算法1 生成OD流的最短路徑算法

輸入：

N：節(jié)點的集合；

Xn：節(jié)點n∈N的橫坐標；

Yn：節(jié)點n∈N的縱坐標；

E：線路的集合；

Sr∈E：線路r∈E的起點；

Tr∈E：線路r∈E的終點；

OD：OD流的集合。

輸出：

W：Graph中任意節(jié)點之間的距離矩陣；

L：從始點O到終點D的最短距離；

Z：從OD流的始點O到終點D的最短路徑；

Pa，r：任意一條OD流a是否經(jīng)過線路r。

步驟：

Step 1 準備W ：將矩陣元素的默認值設(shè)置為無窮大，對角線元素設(shè)置為0：

?i，j∈N：W（i，j）＝INF ；

?i∈N：W（i，i）＝0。

Step 2 初始化W（i，j）：根據(jù)E 集合設(shè)置由線路直接連接的邊：

?r∈E：W（Sr，Tr）＝W（Er，Tr）＝

Step 3 根據(jù)Dijkstra算法求解任意節(jié)點間的最短距離：

其中，（）L i表示從始點Oa到節(jié)點i的最短距離；Z（）j表示從OD流的始點Oa到節(jié)點j的最短路徑上j點的前一個點，且Z（Oa）＝0；

／／L＝min｛L（Da），L（k）＋W（k，Da）｝，?k∈N

if L（Da）＞L（k）＋W（k，Da），then Z（Da）＝k，L即為OD流從始點Oa到終點Da的最短距離。

Step 6 根據(jù)Step 5生成的OD流的最短路徑Z，尋找其經(jīng)過的線路：

?a∈OD：將Z中所經(jīng)過的點兩兩依次組成線路Ei，j；在集合E中找到這些線路Ei，j所對應的線路標號r，令Pa，r＝1。

Step 4 準備矩陣P，即將矩陣元素的默認值設(shè)置為0：

Step 5 根據(jù)Dijkstra算法求解OD流的最短路徑：

4 仿真

下面通過仿真實驗驗證模型（P1）和算法1的有效性，并對模型結(jié)果進行分析。分布式OD運載網(wǎng)絡及其線路和節(jié)點網(wǎng)絡如圖3所示。

4.1 基本參數(shù)設(shè)置

如圖3所示，區(qū)域中共有10個路口節(jié)點和16條直接相連的線路，且在整個運載網(wǎng)絡中存在分布式OD流運載任務，直接連接的線路長度如圖中路段上的數(shù)值表示。在下面的實驗中，隨機生成90個OD流構(gòu)成集合OD，每個OD流的起點和終點在1～10中隨機選擇，而OD流的流量則通過均勻分布DEM ～U （10，50）隨機生成。90條OD流及其運載量的具體分布見圖4，可以發(fā)現(xiàn)該運載網(wǎng)絡中OD流的運載量大致在30集卡單元上下波動。

4.2 仿真結(jié)果與分析

用Matlab.R 2011a編寫了算法1的程序，模型采用Lingo 9.0進行求解，運行環(huán)境均為：Intel（R）Core（TM）i3－2310MCPU ＠2.10GHz，內(nèi)存2GB。

根據(jù)算法1采用Matlab求出圖3所示運載網(wǎng)絡中生成的所有OD流的最短路徑，以及Pa，r分布矩陣，即第a條OD流是否經(jīng)過第r條線路的分布矩陣；在此基礎(chǔ)上，對模型進行仿真。

模型（P1）是一個雙目標模型，兩個目標相互影響。利用帕累托最優(yōu)準則權(quán)衡兩個目標函數(shù)對于整個監(jiān)測系統(tǒng)布局的影響。通過不同的權(quán)重分配，來獲得不同的配置方案。首先，分別給兩個目標函數(shù)設(shè)權(quán)重，其中目標RQ的權(quán)重為W1，目標VQ的權(quán)重為W2，且有W1＋W2＝1，W1≥0，W2≥0。通過式（6）聚合轉(zhuǎn)化為單目標，通過調(diào)整W1和W2尋找Pareto解。

min f＝RQ·W1－VQ·W2（6）

設(shè)定W1從1～0以0.01的幅度遞減；在不同的監(jiān)測水平下，即在監(jiān)測器數(shù)量分別為S＝4、S＝5和S＝6的情況下，分別運行100次得到的結(jié)果如表1所示。由表1可見，隨著監(jiān)測器數(shù)量的增加，帕累托不可公度解的數(shù)量也在增加。

在圖5中，以目標函數(shù)RQ為橫坐標，目標函數(shù)VQ為縱坐標，結(jié)合表1的結(jié)果可以得到：在不同的監(jiān)測水平下，隨著監(jiān)測器數(shù)量的增加，監(jiān)測系統(tǒng)所能覆蓋的范圍增大；而在同一監(jiān)測水平下，隨著線路之間的相關(guān)性水平的增高，監(jiān)測系統(tǒng)所覆蓋的OD流條數(shù)也逐漸增加，并漸趨于平穩(wěn)。通過對比分析，相關(guān)性水平RQ的值在1 000～2 500比較合理，此時所得到的解具有比較好的收斂性。

Table 1 Pareto results of the monitoring system layout under different monitoring levels表1 不同監(jiān)測水平下的監(jiān)測系統(tǒng)布局的Pareto結(jié)果

5 結(jié)束語

在OD運載網(wǎng)絡布局優(yōu)化的基礎(chǔ)上，建立“綠色軌跡監(jiān)測系統(tǒng)”布局的多目標整數(shù)規(guī)劃模型，目的是為監(jiān)測設(shè)備有限的監(jiān)測網(wǎng)絡提供兼具經(jīng)濟效益和環(huán)境效益的配置方案，為此設(shè)計分布式OD運載網(wǎng)絡中計算OD流最短路徑的算法。采用漸變加權(quán)將多目標化為一系列單目標問題求解Pareto最優(yōu)解集，并提出綠色軌跡監(jiān)測的線路相關(guān)性衡量方法，對物流背景下一般監(jiān)控網(wǎng)絡布局與優(yōu)化問題的解決具有參考價值。進一步的研究將突破網(wǎng)絡規(guī)模限制，采用啟發(fā)式算法來解決大規(guī)模的監(jiān)測系統(tǒng)布局問題；考慮OD流路徑選擇時最短路徑本身的隨機性，同時考慮線路交通流量等限制因素，OD流路徑應當存在k－最短路的選擇；另外，通過融入客戶綠色偏好和污染量分析等因素進一步拓展模型與算法的研究。

［1］ Murphy P R，Poist R F，Braunschweig C D.Role and relevance of logistics to corporate environmentalism：An empirical assessment［J］.International Journal of Physical Distribution and Logistics Management，1995，25（2）：5－19.

［2］ Xiao Ding－ding，Zhang Wen－feng.Key element analysis for green logistics development by using decision making trial and evaluation laboratory method［J］.Industrial Engineering Journal，2010，13（1）：52－57.（in Chinese）

［3］ Ubeda S，Arcelus F J，F(xiàn)aulin J.Green logistics at Eroski：A case study［J］.International Journal of Production Economics，2011，131（1）：44－51.

［4］ Garcia F A，Marchetta M G，Camargo M，et al.A framework for measuring logistics performance in the wine industry［J］.International Journal of Production Economics，2012，135（1）：284－298.

［5］ Harris I，Naim M，Palmer A，et al.Assessing the impact of cost optimization based on infrastructure modeling on CO2emissions［J］.International Journal of Production Economics，2011，131（1）：313－321.

［6］ Zhu Qing－h(huán)ua，Dou Yi－jie.A game model for green supply chain management based on government subsidies［J］.Journal of Management Sciences in China，2011，14（6）：86－95.（in Chinese）

［7］ Guo R－Y，Huang H－J.Network traffic flow evolution model considering OD demand mutation［J］.Systems Engineering－Theory ＆Practice，2009，29（1）：118－123.

［8］ Nie Y，Zhang H M.A variational inequality formulation for inferring dynamic origin－destination travel demands［J］.Transportation Research Part B：Methodological，2008，42（7－8）：635－662.

［9］ Thanh P N，Bostel N，Péton O.A DC programming heuristic applied to the logistics network design problem［J］.International Journal of Production Economics，2012，135（1）：94－105.

［10］ Pishvaee S，Jolai F，Razmi J.A stochastic optimization model for integrated forward／reverse logistics network design［J］.Journal of Manufacturing Systems，2009，28（4）：107－114.

［11］ Ma Zu－jun，Dai Ying.Optimization model for reverse logistics network design for product recovery［J］.Journal of Industrial Engineering／Engineering Management，2005，19（4）：114－117.（in Chinese）

［12］ Di Wei－min，Hu Pei.Optimal design of returned logistics network with stochastic parameters of continuous distribution［J］.Chinese Journal of Management Science，2007，15（3）：40－46.（in Chinese）

附中文參考文獻：

［2］ 肖丁丁，張文峰.基于DEMATEL方法的綠色物流發(fā)展關(guān)鍵因素分析［J］.工業(yè)工程，2010，13（1）：52－57.

［6］ 朱慶華，竇一杰.基于政府補貼分析的綠色供應鏈管理博弈模型［J］.管科科學學報，2011，14（6）：86－95.

［11］ 馬祖軍，代穎.產(chǎn)品回收逆向物流網(wǎng)絡優(yōu)化設(shè)計模型［J］.管理工程學報，2005，19（4）：114－117.

［12］ 狄衛(wèi)民，胡培.含有連續(xù)型隨機參數(shù)的回收物流網(wǎng)絡優(yōu)化設(shè)計［J］.中國管理科學，2007，15（3）：40－46.