徐小峰，孫玉萍

(中國(guó)石油大學(xué)(華東)經(jīng)濟(jì)管理學(xué)院，山東 青島 266580)

1 引言

近年來(lái)，我國(guó)物流業(yè)產(chǎn)業(yè)規(guī)模擴(kuò)展迅速，粗獷發(fā)展模式下的物流業(yè)暴露出網(wǎng)絡(luò)運(yùn)行成本高、效率低等問(wèn)題，網(wǎng)絡(luò)內(nèi)部協(xié)同運(yùn)作水平亟待提高[1]。作為一種科學(xué)有效的復(fù)雜系統(tǒng)網(wǎng)絡(luò)組織結(jié)構(gòu)，軸輻式網(wǎng)絡(luò)(Hub and Spoke Network)在物流業(yè)的應(yīng)用受到越來(lái)越廣泛的關(guān)注。與全聯(lián)通的網(wǎng)絡(luò)結(jié)構(gòu)相比，軸輻式網(wǎng)絡(luò)在服務(wù)空間分散的小批量物流需求、整合物流資源、產(chǎn)生規(guī)模效益等方面更具應(yīng)用潛力[2]，但也存在物理路徑延長(zhǎng)、繞道時(shí)效損失等弊端。同時(shí)，為靈活地應(yīng)對(duì)差異化物流需求，軸輻式物流網(wǎng)絡(luò)不再局限于單樞紐-單分配-純軸輻式結(jié)構(gòu)形式，而是更趨近于采用多樞紐-多分配-混合軸輻式網(wǎng)絡(luò)結(jié)構(gòu)形式[3]，即網(wǎng)絡(luò)中布局多個(gè)樞紐、允許單個(gè)輻點(diǎn)分配到多個(gè)樞紐且輻點(diǎn)間存在直達(dá)線路的情況，這也使得物流節(jié)點(diǎn)的協(xié)同運(yùn)作和物流網(wǎng)絡(luò)的運(yùn)營(yíng)管理更加復(fù)雜。因此，如何權(quán)衡多任務(wù)整體利益和單個(gè)任務(wù)滿意度，實(shí)現(xiàn)多個(gè)空間分散的物流任務(wù)-執(zhí)行路徑的有效匹配，成為提升物流集成服務(wù)商競(jìng)爭(zhēng)力的關(guān)鍵。

1987年，O’Kelly以航線網(wǎng)絡(luò)優(yōu)化為切入點(diǎn)，首次提出軸輻式網(wǎng)絡(luò)p-中位優(yōu)化設(shè)計(jì)模型[4]，引發(fā)學(xué)術(shù)界對(duì)軸輻式結(jié)構(gòu)的廣泛關(guān)注。按照規(guī)劃內(nèi)容適用周期的不同，將近年軸輻式網(wǎng)絡(luò)規(guī)劃相關(guān)研究分為長(zhǎng)期規(guī)劃研究(Hub and Spoke NetworkLong-term Planning，HSNLP)和短期規(guī)劃研究(Hub and Spoke Network Short-term Planning，HSNSP)。HSNLP是指以節(jié)點(diǎn)城市物流服務(wù)能力、城市間物流往來(lái)流量結(jié)構(gòu)數(shù)據(jù)為基礎(chǔ)，進(jìn)行軸輻式網(wǎng)絡(luò)樞紐選址和軸線分配等研究，大致有兩類研究方法：一類是通過(guò)建立指標(biāo)評(píng)價(jià)體系，利用主成分分析等方法對(duì)節(jié)點(diǎn)的服務(wù)能力進(jìn)行分級(jí)以此確定樞紐節(jié)點(diǎn)的數(shù)量和位置[5-8]，這類方法側(cè)重對(duì)物流節(jié)點(diǎn)服務(wù)能力的評(píng)價(jià)，對(duì)網(wǎng)絡(luò)本身的運(yùn)營(yíng)成本及效率考慮不足；另一類則更多地考慮節(jié)點(diǎn)間已知物流往來(lái)流量結(jié)構(gòu)，通過(guò)數(shù)學(xué)建模和智能算法求解來(lái)優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)[9-12]，不少研究還針對(duì)單分配[13-15]、多分配[16-17]、含直達(dá)線路[18]以及存在多式聯(lián)運(yùn)[19-20]的情況進(jìn)行改進(jìn)設(shè)計(jì)，大大提高了軸輻式網(wǎng)絡(luò)在實(shí)際運(yùn)營(yíng)中的適用性和靈活性。然而，上述HSNLP研究?jī)?nèi)容僅僅完成了網(wǎng)絡(luò)建設(shè)工作，在網(wǎng)絡(luò)實(shí)際運(yùn)行中，由于流量狀態(tài)存在不確定性，與HSNLP設(shè)定狀態(tài)存在差距，物流任務(wù)集的最佳走形線路將發(fā)生變化。為此，一些學(xué)者針對(duì)網(wǎng)絡(luò)運(yùn)營(yíng)過(guò)程中物流任務(wù)-路徑匹配等HSNSP問(wèn)題進(jìn)行了研究，如Karlaftis等[21]提出樞紐港口與眾多喂給港口間貨物往來(lái)存在季節(jié)性變化，因此對(duì)軸輻式子網(wǎng)絡(luò)集裝箱船舶線路重新規(guī)劃，建立了帶時(shí)間窗的整數(shù)規(guī)劃模型，但未考慮中轉(zhuǎn)時(shí)間和等待時(shí)間；楊立乾[22]考慮樞紐容量和貨物時(shí)間約束，對(duì)軸輻式支線集裝箱運(yùn)輸多船型船舶調(diào)度問(wèn)題進(jìn)行建模研究，并設(shè)計(jì)粒子群算法進(jìn)行模型求解；黃麗霞等[23]綜合考慮客戶送達(dá)時(shí)間、服務(wù)等級(jí)需求和運(yùn)輸能力限制等因素，對(duì)軸輻式網(wǎng)絡(luò)下的干線貨物運(yùn)輸路徑、服務(wù)班列及運(yùn)行數(shù)量進(jìn)行優(yōu)化設(shè)計(jì)。

綜上，盡管軸輻式網(wǎng)絡(luò)規(guī)劃已經(jīng)有較豐富的研究?jī)?nèi)容[24-27]，但多是集中于軸點(diǎn)選址等HSNLP方面[28]，而較少關(guān)注在軸輻式物流資源服務(wù)體系確定條件下的物流任務(wù)-路徑優(yōu)化匹配等HSNSP問(wèn)題，且已有HSNSP研究多是將軸輻式網(wǎng)絡(luò)作為問(wèn)題產(chǎn)生的背景，僅僅將單個(gè)層級(jí)(支線或干線)作為資源調(diào)度對(duì)象，未能從系統(tǒng)整體角度考慮調(diào)度過(guò)程，忽視了網(wǎng)絡(luò)層級(jí)間的相互影響。因此，本文將多任務(wù)集成調(diào)度問(wèn)題擴(kuò)展到HSNSP研究領(lǐng)域，以多樞紐-多分配-混合軸輻式多式聯(lián)運(yùn)協(xié)同物流網(wǎng)絡(luò)(雙層)為基礎(chǔ)，綜合考慮干線資源發(fā)車時(shí)刻限制和費(fèi)用折扣系數(shù)動(dòng)態(tài)變化條件，針對(duì)一特定時(shí)段內(nèi)網(wǎng)絡(luò)內(nèi)部多起始點(diǎn)-多目的地的物流任務(wù)集，構(gòu)建軸輻式協(xié)同物流網(wǎng)絡(luò)任務(wù)-路徑優(yōu)化匹配模型并采用遺傳算法進(jìn)行模型求解，以滿足客戶服務(wù)時(shí)間要求并使得總物流成本最小。

2 問(wèn)題描述

在軸輻式物流網(wǎng)絡(luò)資源服務(wù)體系確立的條件下，本文從物流集成服務(wù)商的角度出發(fā)，研究一個(gè)調(diào)度周期內(nèi)多起止點(diǎn)多個(gè)需求不同的物流任務(wù)的任務(wù)-路徑優(yōu)化匹配過(guò)程，通過(guò)物流任務(wù)的有效聚合，實(shí)現(xiàn)物流資源的整合，從而最大限度地發(fā)揮網(wǎng)絡(luò)系統(tǒng)協(xié)同規(guī)模效益。

圖1 多樞紐-多分配-混合軸輻式多式聯(lián)運(yùn)協(xié)同物流網(wǎng)絡(luò)形態(tài)示意圖

給定軸輻式協(xié)同物流網(wǎng)絡(luò)G=(N,E)(如圖1)，N=H∪S表示網(wǎng)絡(luò)中的兩層物流節(jié)點(diǎn)，上層為軸點(diǎn)H={h1,h2…h(huán)k,hm…h(huán)h}，具有貨物中轉(zhuǎn)功能，下層為輻點(diǎn)S={s1,s2,…si,sj…ss}，為軸點(diǎn)提供物流任務(wù)喂給服務(wù)；E為網(wǎng)絡(luò)中關(guān)聯(lián)邊集合，表示服務(wù)商在該路段可提供的物流資源，帶有運(yùn)輸時(shí)間、運(yùn)輸能力、可變費(fèi)用折扣等屬性。網(wǎng)絡(luò)中軸點(diǎn)間完全聯(lián)通，輻點(diǎn)間的聯(lián)絡(luò)主要借助軸點(diǎn)實(shí)現(xiàn)?？紤]到物流網(wǎng)絡(luò)的穩(wěn)定性和貨物運(yùn)輸選擇的靈活性，該網(wǎng)絡(luò)允許輻點(diǎn)與多個(gè)軸點(diǎn)存在指派關(guān)系，xik是表示si和hk之間是否存在指派關(guān)系的0-1變量；同時(shí)部分輻點(diǎn)間可選擇直達(dá)線路，yik是表示si,sj間是否有直達(dá)線路的0-1變量。軸點(diǎn)hk,hm間存在多種運(yùn)輸工具供選擇，運(yùn)輸能力及發(fā)車時(shí)刻存在一定要求。

圖2 多任務(wù)多起止點(diǎn)物流服務(wù)示意圖

1)匹配執(zhí)行模式：調(diào)度過(guò)程存在直達(dá)和轉(zhuǎn)運(yùn)兩類執(zhí)行模式，轉(zhuǎn)運(yùn)模式下的干線運(yùn)輸成本遠(yuǎn)低于直達(dá)模式，但前者由于存在繞道以及中轉(zhuǎn)耗時(shí)使得總體運(yùn)輸時(shí)間大于后者；

2)匹配轉(zhuǎn)運(yùn)樞紐：不同樞紐對(duì)應(yīng)干線不同，中轉(zhuǎn)成本、中轉(zhuǎn)耗時(shí)及等待時(shí)間也不同；

3)調(diào)度運(yùn)輸資源：干線間運(yùn)輸資源的開始服務(wù)時(shí)間取決于其待執(zhí)行物流任務(wù)集中最晚到達(dá)任務(wù)的最早開始時(shí)間。

3 模型構(gòu)建

3.1 條件假設(shè)

為方便模型構(gòu)建和計(jì)算分析，作如下假設(shè)：

(1)軸輻式網(wǎng)絡(luò)中物流資源均為系統(tǒng)原有資源，模型中不再考慮建設(shè)成本等固定成本；

(2)軸點(diǎn)中轉(zhuǎn)無(wú)容量限制，且針對(duì)不同運(yùn)輸資源的中轉(zhuǎn)時(shí)間和成本相同；

(3)干線存在多種運(yùn)輸資源，支線和直達(dá)線路只有公路運(yùn)輸一種；

(4)干線運(yùn)輸資源存在發(fā)出時(shí)刻限制；

(5)僅考慮干線規(guī)模效益，用費(fèi)用折扣系數(shù)表示，折扣大小隨調(diào)度周期內(nèi)該條干線承擔(dān)總物流量動(dòng)態(tài)變化；

(6)物流任務(wù)不可拆分，即單個(gè)物流任務(wù)只能匹配一條路徑；

(7)物流任務(wù)發(fā)出和接收地均為輻點(diǎn)，運(yùn)輸過(guò)程最多允許轉(zhuǎn)運(yùn)兩次；

(8)物流任務(wù)的執(zhí)行僅考慮從發(fā)出方到接收方的過(guò)程，即任務(wù)性質(zhì)為純送貨任務(wù)。

3.2 變量定義

表1 模型參數(shù)含義說(shuō)明

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

(1)

(2)

其中：式(1)為模型的服務(wù)成本目標(biāo)函數(shù)，由四個(gè)部分組成：第一部分是轉(zhuǎn)運(yùn)路徑成本，分別為軸點(diǎn)間規(guī)模運(yùn)輸成本、輻點(diǎn)與軸點(diǎn)間支線集散運(yùn)輸成本和軸點(diǎn)轉(zhuǎn)運(yùn)成本；第二部分為輻點(diǎn)間的直接運(yùn)輸成本；第三部分為超時(shí)懲罰成本；第四部分軸點(diǎn)等待成本。式(2)是模型的服務(wù)時(shí)間目標(biāo)函數(shù)，包括運(yùn)輸時(shí)間、轉(zhuǎn)運(yùn)時(shí)間和等待時(shí)間。

3.4 約束條件

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

式(3)表示每個(gè)物流任務(wù)只能匹配一種運(yùn)輸方式，即基于軸點(diǎn)轉(zhuǎn)運(yùn)運(yùn)輸或者直接運(yùn)輸；若選擇轉(zhuǎn)運(yùn)，干線運(yùn)輸只能匹配公路或者鐵路一種運(yùn)輸工具。式(4)表示軸點(diǎn)選擇條件，即只有當(dāng)任務(wù)發(fā)出點(diǎn)/接收點(diǎn)與軸點(diǎn)存在指派關(guān)系時(shí)，才能選擇相應(yīng)軸點(diǎn)作為轉(zhuǎn)運(yùn)點(diǎn)。式(5)表示選擇直線運(yùn)輸?shù)臈l件是任務(wù)起訖點(diǎn)間存在直達(dá)線路。式(6)表示運(yùn)輸路徑能力限制。式(7)表示干線資源發(fā)車時(shí)間，即作為緊后活動(dòng)，其開始時(shí)間取決于緊前子任務(wù)集的最晚完成時(shí)間。式(8)表示物流任務(wù)r的實(shí)際總服務(wù)時(shí)間。式(9)表示物流任務(wù)超時(shí)懲罰函數(shù)。式(10)表示費(fèi)用折扣系數(shù)變化依據(jù)，αmin為給定最低費(fèi)用折扣值。

4 模型求解

多樞紐軸輻式協(xié)同物流網(wǎng)絡(luò)任務(wù)-路徑優(yōu)化匹配問(wèn)題屬于NP問(wèn)題，其時(shí)間復(fù)雜度會(huì)隨著問(wèn)題規(guī)模增大而急劇上升，傳統(tǒng)的精確計(jì)算方法難以解決。遺傳算法是一類借鑒生物界自然選擇和遺傳機(jī)制的隨機(jī)搜索算法，非常適應(yīng)于處理復(fù)雜的非線性規(guī)劃問(wèn)題。本文利用遺傳算法對(duì)上述模型進(jìn)行求解，具體實(shí)現(xiàn)過(guò)程如下：

(1)編碼

根據(jù)軸輻式網(wǎng)絡(luò)任務(wù)-路徑優(yōu)化匹配過(guò)程的特點(diǎn)，在對(duì)所有物流節(jié)點(diǎn)及干線運(yùn)輸方式編號(hào)的基礎(chǔ)上，本文設(shè)計(jì)了三層整數(shù)編碼來(lái)表示任務(wù)執(zhí)行路徑，如圖3所示。每層編碼基因數(shù)目與任務(wù)數(shù)r相等，即染色體總長(zhǎng)度為3r。對(duì)于任務(wù)r，若一二層基因恰好等于其起止點(diǎn)，則表示該任務(wù)匹配直達(dá)線路。若兩個(gè)任務(wù)三層編碼完全一致，則表示兩個(gè)任務(wù)在相應(yīng)路段發(fā)生集并。

圖3 編碼示意圖

(2)種群初始化

設(shè)置種群規(guī)模為m，按照編碼規(guī)則隨機(jī)生成m個(gè)滿足路徑約束、資源能力約束的染色體，以此為初始種群進(jìn)行遺傳操作。

(3)適應(yīng)度函數(shù)

適應(yīng)度是評(píng)估染色體優(yōu)劣的標(biāo)準(zhǔn)。本文通過(guò)賦權(quán)的方式將模型中成本和時(shí)間兩個(gè)目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)形式，同時(shí)進(jìn)行歸一化處理，得到適應(yīng)度函數(shù)如下：

F=ηminC/Cmax+(1-η)minT/Tmax

(12)

其中，Cmax、Tmax取種群進(jìn)化過(guò)程遍歷的可行解中對(duì)應(yīng)的最大執(zhí)行成本和最大執(zhí)行時(shí)間。

(4)遺傳操作

1)選擇

依據(jù)適應(yīng)度值選擇優(yōu)良個(gè)體作為父代進(jìn)行繁殖，形成新的子代。本文采用輪盤賭選擇策略。

2)交叉

隨機(jī)選擇兩個(gè)染色體，以設(shè)定概率Pc進(jìn)行交叉操作。由于本文采用三層編碼表示任務(wù)執(zhí)行路徑，經(jīng)典的單點(diǎn)交叉算子極易破壞解的可行性，導(dǎo)致大量無(wú)效操作。因此，本文設(shè)計(jì)了多點(diǎn)位交叉方式，如圖4所示，若隨機(jī)選中第r+2個(gè)基因進(jìn)行交叉，則第2和第2r+2個(gè)基因也隨之進(jìn)行交叉，即任務(wù)r2的三層編碼同時(shí)交叉，保證了交叉的有效性。

圖4 交叉過(guò)程示意圖

3)變異

隨機(jī)選擇兩個(gè)染色體，以設(shè)定概率Pm進(jìn)行變異操作，同交叉方式類似，本文的變異方式遵循同一任務(wù)的三層編碼同時(shí)變異的原則。

4)終止

當(dāng)進(jìn)化次數(shù)達(dá)到預(yù)設(shè)的迭代次數(shù)時(shí)，終止遺傳操作，輸出結(jié)果。

5 算例仿真

5.1 算例設(shè)計(jì)

某物流集成服務(wù)商承接了我國(guó)中西部一制造業(yè)企業(yè)在全國(guó)范圍內(nèi)的物流任務(wù)，其可調(diào)配的物流資源組成圖5所示的軸輻式協(xié)同物流網(wǎng)絡(luò)，主要資源參數(shù)見表2。取兩點(diǎn)間直線距離作為兩物流節(jié)點(diǎn)間的運(yùn)輸距離，并假定干線和支線公路運(yùn)輸時(shí)速分別為80公里/時(shí)和70公里/時(shí)，干線鐵路運(yùn)輸時(shí)速為100公里/時(shí)，以此得到網(wǎng)絡(luò)運(yùn)輸時(shí)間矩陣。干線規(guī)模效益取決于該線路承擔(dān)的貨運(yùn)量(式(10))，貨運(yùn)量越大，規(guī)模效益越顯著，設(shè)定αmin=0.3，即當(dāng)該線路滿載時(shí)，成本折扣系數(shù)達(dá)到最小0.3。

根據(jù)全國(guó)各銷售商訂單需求和蘭州、西安及重慶三處分制造廠的供貨情況，物流集成服務(wù)商需要在一個(gè)調(diào)度周期內(nèi)完成表3所示的8個(gè)物流任務(wù)。為實(shí)現(xiàn)規(guī)模效益最大化，集成商會(huì)盡可能使任務(wù)集并運(yùn)輸，但如果任務(wù)對(duì)交貨期要求嚴(yán)，集并可能會(huì)大大降低單個(gè)任務(wù)滿意度。因此，集成商需根據(jù)各任務(wù)的具體需求及任務(wù)各執(zhí)行階段可匹配的資源情況(圖6)，綜合制定任務(wù)-路徑匹配方案。

圖5 軸輻式協(xié)同物流網(wǎng)絡(luò)形態(tài)示意圖

表2-a 軸輻式網(wǎng)絡(luò)物流資源條件——干線資源

hk?hm公路鐵路dijvcijukmvdijvcijukmv成都?北京19.03102015.223030成都?杭州19.38102015.53030杭州?北京14.13102011.33030

表2-b 軸輻式網(wǎng)絡(luò)物流資源條件——支線及樞紐資源

表3 物流任務(wù)表

圖6 多任務(wù)物流服務(wù)示意圖

5.2 結(jié)果分析

設(shè)置種群規(guī)模為30，迭代次數(shù)為250，交叉概率為0.8，變異概率為0.1，編寫遺傳算法利用Matlab2014a進(jìn)行求解。

為便于比較分析，令成本目標(biāo)函數(shù)權(quán)重系數(shù)η分別等于0.5和1，同時(shí)令后者懲罰成本為0，得到收斂曲線如圖7所示，對(duì)應(yīng)的路徑匹配方案如表4所示。

圖7 遺傳算法收斂曲線

可以發(fā)現(xiàn)，當(dāng)集成商只關(guān)注自身成本時(shí)，盡管實(shí)現(xiàn)了更低的成本支出，卻忽略了單個(gè)任務(wù)的滿意度，使得對(duì)服務(wù)時(shí)間要求高的任務(wù)發(fā)生延遲；而當(dāng)集成商兼顧整體與單個(gè)任務(wù)效益時(shí)，盡管成本有所上升(+1.4%)，卻大幅度節(jié)省了執(zhí)行時(shí)間(-14.9%)，從而大大提升了客戶滿意度。由圖8可以看到，優(yōu)化方案中，對(duì)于延遲成本高的任務(wù)2和任務(wù)7，集成商放棄使用轉(zhuǎn)運(yùn)路徑直接匹配直達(dá)線路，保證了其交貨時(shí)間；對(duì)于延遲成本低的任務(wù)，普遍采用轉(zhuǎn)運(yùn)運(yùn)輸，以達(dá)到更大的規(guī)模效益，且當(dāng)多個(gè)任務(wù)最優(yōu)路徑相同而路徑能力有限時(shí)，為保證整體利益，損失更小的任務(wù)將匹配次優(yōu)線路。

表4 軸輻式協(xié)同物流網(wǎng)絡(luò)任務(wù)-路徑匹配方案

注：①-分別代表成都、北京、杭州、蘭州、重慶、西安、石家莊、天津、濟(jì)南、鄭州、南京、武漢；I代表干線公路運(yùn)輸，II代表干線鐵路運(yùn)輸。

圖8 軸輻式協(xié)同物流網(wǎng)絡(luò)甘特圖

6 結(jié)語(yǔ)

本文研究HSNSP問(wèn)題，在多樞紐-多分配-混合軸輻式多式聯(lián)運(yùn)協(xié)同物流網(wǎng)絡(luò)建立的條件下，對(duì)一個(gè)調(diào)度周期內(nèi)多個(gè)多起點(diǎn)-多目的地的物流任務(wù)進(jìn)行路徑優(yōu)化匹配。從物流集成服務(wù)商角度出發(fā)，綜合考慮干線資源的發(fā)車時(shí)刻和能力約束，設(shè)計(jì)了隨物流量動(dòng)態(tài)變化的成本折扣系數(shù)來(lái)表示規(guī)模效益，建立了帶軟時(shí)間窗的任務(wù)-路徑優(yōu)化匹配模型，優(yōu)化目標(biāo)為集成商物流成本和服務(wù)時(shí)間最小。針對(duì)模型特點(diǎn)，在利用遺傳算法求解過(guò)程中，設(shè)計(jì)了三層編碼來(lái)表示任務(wù)路徑，并采用多點(diǎn)位交叉、變異機(jī)制來(lái)保證遺傳操作的有效性。最后利用具體算例驗(yàn)證了本文模型和算法的有效性。

研究結(jié)果表明，本文模型通過(guò)對(duì)單個(gè)任務(wù)設(shè)置延時(shí)懲罰，兼顧物流服務(wù)集成商的利潤(rùn)需求和客戶服務(wù)質(zhì)量，實(shí)現(xiàn)了整體效益最優(yōu)。帶資源回程的軸輻式協(xié)同物流網(wǎng)絡(luò)任務(wù)-路徑優(yōu)化匹配將是下一步研究工作的重點(diǎn)。