允許直達(dá)的混合軸輻式快遞網(wǎng)絡(luò)規(guī)劃模型與算法研究

趙 晉，張建軍，嚴(yán)蔡華

(1.同濟(jì)大學(xué)職業(yè)技術(shù)教育學(xué)院，上海 201804；2.同濟(jì)大學(xué)中德工程學(xué)院，上海 201804；3.同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200092)

允許直達(dá)的混合軸輻式快遞網(wǎng)絡(luò)規(guī)劃模型與算法研究

趙 晉1,2，張建軍3，嚴(yán)蔡華3

(1.同濟(jì)大學(xué)職業(yè)技術(shù)教育學(xué)院，上海 201804；2.同濟(jì)大學(xué)中德工程學(xué)院，上海 201804；3.同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200092)

在快遞企業(yè)的日常運(yùn)營(yíng)中，當(dāng)兩個(gè)城市之間的快遞業(yè)務(wù)量達(dá)到一定規(guī)模之后會(huì)允許該城市對(duì)之間開(kāi)展直達(dá)遞送。但是這一規(guī)則通常僅在快遞網(wǎng)絡(luò)規(guī)劃完成之后由相關(guān)子公司提請(qǐng)實(shí)施。為彌補(bǔ)這一實(shí)際規(guī)則的局部最優(yōu)性缺陷，本論文將直達(dá)問(wèn)題納入網(wǎng)絡(luò)規(guī)劃決策，基于全局優(yōu)化的視角構(gòu)建了允許直達(dá)的混合軸幅式快遞網(wǎng)絡(luò)規(guī)劃決策模型，設(shè)計(jì)了相應(yīng)的求解流程，并對(duì)其中的指派關(guān)系決策構(gòu)建了遺傳算法?；趪?guó)內(nèi)標(biāo)桿企業(yè)的數(shù)值案例計(jì)算證明了該決策模型與求解方法的有效性，研究結(jié)果還說(shuō)明，相對(duì)于純軸輻式結(jié)構(gòu)，允許直達(dá)的混合軸幅式網(wǎng)絡(luò)結(jié)構(gòu)有助于降低網(wǎng)絡(luò)總成本，同時(shí)在直達(dá)線路上能夠有效的降低迂回、提高服務(wù)時(shí)效性和服務(wù)水平。

快遞網(wǎng)絡(luò)；網(wǎng)絡(luò)規(guī)劃；直達(dá)線路；混合軸幅式網(wǎng)絡(luò)；遺傳算法

1 引言

當(dāng)前，伴隨電子商務(wù)、網(wǎng)絡(luò)購(gòu)物發(fā)展迅猛，我國(guó)快遞服務(wù)業(yè)已進(jìn)入高速發(fā)展期，2014年我國(guó)快遞行業(yè)的日均處理量已超過(guò)3500萬(wàn)件，市場(chǎng)規(guī)模位居世界第一[1]。在企業(yè)界，2012年9月，F(xiàn)edEx和UPS兩大國(guó)際快遞巨頭獲得了經(jīng)營(yíng)中國(guó)國(guó)內(nèi)快遞業(yè)務(wù)的牌照；2013年5月，阿里巴巴集團(tuán)宣布建立中國(guó)智能骨干物流網(wǎng)；2014年12月，國(guó)家郵政局批準(zhǔn)雅瑪多、歐西愛(ài)司、嘉里大通等物流經(jīng)營(yíng)國(guó)內(nèi)包裹快遞業(yè)務(wù)……從這些事件可以看到，當(dāng)前，快遞業(yè)的機(jī)遇與挑戰(zhàn)共存，快遞網(wǎng)絡(luò)規(guī)劃成為企業(yè)關(guān)注的焦點(diǎn)。

人們對(duì)網(wǎng)絡(luò)規(guī)劃問(wèn)題研究的主要熱點(diǎn)有[2-4]：(1)具有混合網(wǎng)絡(luò)結(jié)構(gòu)的網(wǎng)絡(luò)規(guī)劃問(wèn)題；(2)具有網(wǎng)絡(luò)建設(shè)固定成本的網(wǎng)絡(luò)規(guī)劃問(wèn)題；(3)運(yùn)輸費(fèi)用有折扣率的網(wǎng)絡(luò)規(guī)劃問(wèn)題；(4)hub處理能力有限的網(wǎng)絡(luò)規(guī)劃問(wèn)題；(5)大規(guī)模網(wǎng)絡(luò)規(guī)劃問(wèn)題的求解算法設(shè)計(jì)。代表性的研究有：Rodriguez-Martin等[5]研究了包括hub邊緣聯(lián)接網(wǎng)絡(luò)與環(huán)形網(wǎng)絡(luò)在兩層網(wǎng)絡(luò)的規(guī)劃中的作用，并設(shè)計(jì)了分支切割算法求解；Campbell[6]首次將服務(wù)時(shí)間作為約束條件納入了與成本最小化為目標(biāo)的網(wǎng)絡(luò)規(guī)劃模型，其中服務(wù)時(shí)間被轉(zhuǎn)化為以距離的形式表達(dá)；作為一個(gè)發(fā)展，Alumura等[7]針對(duì)有時(shí)限約束的兩層多式聯(lián)運(yùn)網(wǎng)絡(luò)規(guī)劃問(wèn)題構(gòu)建了一個(gè)混合整數(shù)規(guī)劃模型，其中目標(biāo)函數(shù)為線性函數(shù)、決策變量數(shù)量為O(n3)。趙宇哲[8]針對(duì)航運(yùn)企業(yè)的重組與全球擴(kuò)張引起的競(jìng)爭(zhēng)問(wèn)題,提出了競(jìng)爭(zhēng)環(huán)境下的軸-輻式集裝箱海運(yùn)網(wǎng)絡(luò)設(shè)計(jì)模型。張建軍等[9]研究中國(guó)郵政速遞物流公司的陸路網(wǎng)絡(luò)規(guī)劃問(wèn)題，在多時(shí)限約束下提出了一個(gè)基于個(gè)體理性的啟發(fā)式算法并構(gòu)建了相應(yīng)的決策支持系統(tǒng)等。傅少川等[10]設(shè)計(jì)了改進(jìn)的禁忌搜索智能算法來(lái)求解無(wú)容量限制的單分配多樞紐中位問(wèn)題模型。倪玲霖和史峰[12]分析了多分配快遞軸輻網(wǎng)絡(luò)的節(jié)點(diǎn)及連接關(guān)系、徑路特征與形式等網(wǎng)絡(luò)設(shè)計(jì)要素，在運(yùn)輸時(shí)間預(yù)算約束下以分揀費(fèi)用、運(yùn)輸費(fèi)用、中轉(zhuǎn)費(fèi)用之和為目標(biāo)函數(shù)建立了多分配軸輻式快遞網(wǎng)絡(luò)樞紐選址與分配優(yōu)化模型[11]。類似的對(duì)多分配結(jié)構(gòu)[12]、逆向物流網(wǎng)絡(luò)[13]等的研究。

與前述研究不同的是，我們的研究視角聚焦快遞企業(yè)網(wǎng)絡(luò)規(guī)劃實(shí)踐中的一類直達(dá)問(wèn)題：在企業(yè)調(diào)研中，我們發(fā)現(xiàn)，企業(yè)管理者通常會(huì)有一條判斷規(guī)則，即任何兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)之間的快遞流量如果達(dá)到了一定規(guī)模，則在其間開(kāi)通一條直達(dá)運(yùn)輸線路。這一規(guī)則的價(jià)值是顯著的，具有易于操作的優(yōu)點(diǎn)，但是不足之處同樣明顯：它沒(méi)有在全局優(yōu)化的視角下分析其可行性。為此，本論文將允許直達(dá)納入到快遞網(wǎng)絡(luò)規(guī)劃問(wèn)題中，探討相應(yīng)的決策模型和求解算法設(shè)計(jì)問(wèn)題，為這一類具有重要實(shí)踐價(jià)值的決策規(guī)則提供科學(xué)的方法指導(dǎo)。

2 問(wèn)題描述

本文研究單一指派混合軸輻式網(wǎng)絡(luò)結(jié)構(gòu)，每個(gè)非樞紐節(jié)點(diǎn)指派給特定的樞紐中轉(zhuǎn)站，同一子網(wǎng)或者不同子網(wǎng)之間的非樞紐節(jié)點(diǎn)可以有直達(dá)線路，各中轉(zhuǎn)站之間兩兩直達(dá)運(yùn)輸。網(wǎng)絡(luò)的結(jié)構(gòu)圖如圖1。

如一批快件配送需求的發(fā)生地為貨運(yùn)站Si，目的地為貨運(yùn)站Sj，那么存在三種情況：

(1)直達(dá)線路(如果有的話)：貨運(yùn)站Si→貨運(yùn)站Sj；

(2)同一區(qū)域內(nèi)：貨運(yùn)站Si→樞紐中心Hk→貨運(yùn)站Sj；

換言之，貨運(yùn)站Si→樞紐中心Hk→樞紐中心Hk→貨運(yùn)站Sj；

(3)不同區(qū)域內(nèi)：貨運(yùn)站Si→樞紐中心Hk→樞紐中心Hm→貨運(yùn)站Sj；

具體問(wèn)題可以描述為：

(1)非樞紐節(jié)點(diǎn)都必須且只能與一個(gè)樞紐中心相連接；

(2)每個(gè)貨運(yùn)站只能單一指派給特定的樞紐中心，每個(gè)樞紐中心的覆蓋區(qū)域內(nèi)可以有多個(gè)貨運(yùn)站；

(3)網(wǎng)絡(luò)中樞紐中心的數(shù)量為P；

(4)非樞紐節(jié)點(diǎn)之間可以直接相連；

(5)兩個(gè)節(jié)點(diǎn)之間的流量運(yùn)輸只能有唯一的路徑，不能將流量分成兩個(gè)部分；

(6)樞紐節(jié)點(diǎn)之間全連通。

圖1 允許直達(dá)的混合軸輻式網(wǎng)絡(luò)結(jié)構(gòu)

針對(duì)上述情況，需要解決如下幾個(gè)決策問(wèn)題：

(1)選取哪些節(jié)點(diǎn)作為樞紐中心點(diǎn)？

(2)每個(gè)樞紐節(jié)點(diǎn)的覆蓋區(qū)域？各不同覆蓋區(qū)域中非樞紐節(jié)點(diǎn)的貨物運(yùn)輸路徑？

(3)哪些非樞紐節(jié)點(diǎn)之間建立起直達(dá)運(yùn)輸路徑？

3 決策模型構(gòu)建

考慮一個(gè)混合軸輻式網(wǎng)絡(luò)的完整集合G=(V,E)，V表示節(jié)點(diǎn)(軸或者輻)的集合V={1,2,…,N}，節(jié)點(diǎn)V表示的是網(wǎng)絡(luò)中的起點(diǎn)和終點(diǎn)(如城市終端)以及可能的樞紐節(jié)點(diǎn)。E表示連接弧(軸輻中間的連接路徑)的集合，E(i,j)的屬性包括兩點(diǎn)距離dij和從i運(yùn)輸?shù)絡(luò)的貨物流量(體積或者重量)Wij，兩點(diǎn)距離符合三角不等式規(guī)律。之前的文獻(xiàn)中提到，任意兩個(gè)節(jié)點(diǎn)對(duì)之間的物流運(yùn)輸包括通過(guò)E(i,k)從起點(diǎn)到hub的集貨，經(jīng)過(guò)hub點(diǎn)之間的轉(zhuǎn)運(yùn)E(k,m)，經(jīng)由E(m,j)配送到終點(diǎn)。本文規(guī)定，網(wǎng)絡(luò)中任意一個(gè)起始終點(diǎn)對(duì)之間的正逆物流流量總和超過(guò)某一上限，那么就表明這兩個(gè)城市節(jié)點(diǎn)之間的快遞需求交互頻繁，根據(jù)兩點(diǎn)距離符合三角不等式規(guī)律，建立直達(dá)網(wǎng)絡(luò)，而不是通過(guò)經(jīng)過(guò)中轉(zhuǎn)站運(yùn)輸，從而能夠很好的滿足城市對(duì)之間的物流需求的時(shí)效性要求。

傳統(tǒng)的模型都是假設(shè)hub點(diǎn)之間是全連通的，每對(duì)hub點(diǎn)之間的流量運(yùn)輸都有成本折扣α，這是規(guī)模效益的具體體現(xiàn)。但是隨之也帶來(lái)一個(gè)問(wèn)題，有時(shí)候hub點(diǎn)之間的運(yùn)輸流量并不比非hub弧上的流量要大，甚至更小。因此本文假設(shè)，當(dāng)非樞紐節(jié)點(diǎn)之間滿足建立起直達(dá)線路的條件時(shí)，規(guī)定該節(jié)點(diǎn)對(duì)之間的流量運(yùn)輸具有規(guī)模效應(yīng)，折扣因子為β。

由于每個(gè)配送路徑中通常包括三個(gè)環(huán)節(jié)：集貨、轉(zhuǎn)運(yùn)和配送。本文將成本核算成如下表達(dá)形式：

Cij=χdik+αdkm+σdmj當(dāng)貨物通過(guò)轉(zhuǎn)運(yùn)中心轉(zhuǎn)運(yùn)時(shí)；

Cij=βdij當(dāng)存在非樞紐節(jié)點(diǎn)之間的貨物直達(dá)運(yùn)輸時(shí)。

通常規(guī)定χ=σ=1,0≤α<1,0≤β<1。

以網(wǎng)絡(luò)運(yùn)營(yíng)成本最小化為目標(biāo)，建立如下帶有直達(dá)線路的混合軸輻式網(wǎng)絡(luò)問(wèn)題的模型：

(1)

約束條件：

(2)

(3)

Xi+δij≤1對(duì)于任意的i,j

(4)

δij=δji對(duì)于任意的i,j

(5)

Xk∈{0,1}對(duì)于任意的k

(6)

Xij∈{0,1}對(duì)于任意的i,j

(7)

δij∈{0,1}對(duì)于任意的i,j

(8)

參數(shù)說(shuō)明：

α表示樞紐中心之間轉(zhuǎn)運(yùn)費(fèi)用的折扣因子；

β表示直達(dá)路徑上運(yùn)輸費(fèi)用的折扣因子；

p表示需要建立的樞紐中心數(shù)量；

Cij表示節(jié)點(diǎn)對(duì)之間的單位運(yùn)輸費(fèi)用；

Wij表示從起始點(diǎn)i到終點(diǎn)j的貨物流量；

決策變量說(shuō)明：

Xk為二進(jìn)制決策變量，用于判斷節(jié)點(diǎn)k是否為樞紐中心點(diǎn)；當(dāng)Xk=1時(shí)，表示選擇節(jié)點(diǎn)k作為樞紐中心；否則，Xk=0。

Xij為二進(jìn)制決策變量，用于判斷節(jié)點(diǎn)i是否與節(jié)點(diǎn)j相連通；當(dāng)Xij=1時(shí)，表示節(jié)點(diǎn)i與j相連；否則，Xij=0。

目標(biāo)函數(shù)說(shuō)明:

約束條件說(shuō)明：

式(2)限制了最終需要建立的樞紐中心點(diǎn)的個(gè)數(shù)；

式(3)、(7)保證了非樞紐節(jié)點(diǎn)只能與一個(gè)樞紐中心點(diǎn)相連；

式(4)、(5)是為了明確非樞紐節(jié)點(diǎn)間的直接通路與樞紐節(jié)點(diǎn)和非樞紐節(jié)點(diǎn)連接路徑的區(qū)別；

式(6)、(7)、(8)是對(duì)決策變量取值的限制。

4 模型求解算法設(shè)計(jì)

上述所構(gòu)建的混合軸輻式網(wǎng)絡(luò)規(guī)劃模型，在實(shí)踐中由于網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量較大，屬于大規(guī)模的混合整數(shù)規(guī)劃問(wèn)題，如果采用精確求解的辦法，通常很難或者根本不可能在可以接受的時(shí)間內(nèi)得到問(wèn)題的有效解。為此我們?cè)O(shè)計(jì)了一個(gè)分步啟發(fā)式算法進(jìn)行求解，首先將模型求解問(wèn)題分成三個(gè)部分：樞紐選址問(wèn)題，非樞紐點(diǎn)的直達(dá)路徑構(gòu)建問(wèn)題，和非樞紐點(diǎn)的指派問(wèn)題。我們?cè)O(shè)計(jì)的求解流程如圖2。

4.1 樞紐中心選址

設(shè)計(jì)用于確定候選樞紐中心節(jié)點(diǎn)的求解過(guò)程如下：

第一步：計(jì)算節(jié)點(diǎn)i到其他與其有流量需求發(fā)生的節(jié)點(diǎn)的總運(yùn)輸距離和TCi；

第二步：計(jì)算節(jié)點(diǎn)i到其他各節(jié)點(diǎn)間的總流量之和TWi；

第三步：計(jì)算各節(jié)點(diǎn)的TWi/TCi值；

第四步：對(duì)所有節(jié)點(diǎn)的TWi/TCi值按從大到小排序，排位越靠前的節(jié)點(diǎn)被選中的幾率越大，因?yàn)門(mén)Wi/TCi值越大表明其運(yùn)輸流量大但運(yùn)輸總距離較小，體現(xiàn)了配送網(wǎng)絡(luò)運(yùn)營(yíng)價(jià)值的最大化；

圖2 決策模型的求解流程

4.2 非樞紐點(diǎn)的直達(dá)路徑構(gòu)建

設(shè)候選樞紐中心點(diǎn)得集合為H，非樞紐中心點(diǎn)的集合為U，則H+U=V，V是所有節(jié)點(diǎn)的集合。

最終可以得到，在不同的樞紐中心點(diǎn)選址的情況下，非樞紐點(diǎn)中需要建立直接通路的節(jié)點(diǎn)對(duì)集合。

4.3 非樞紐點(diǎn)的指派

在前面兩個(gè)部分完成之后，接下來(lái)就是要對(duì)非樞紐節(jié)點(diǎn)與相應(yīng)的候選中心集合中的各個(gè)節(jié)點(diǎn)進(jìn)行指派關(guān)系的確定。這是決策模型求解的核心部分。我們?cè)O(shè)計(jì)以下遺傳算法，根據(jù)前面兩個(gè)階段確定的樞紐中心集合H和非樞紐中心集合U，通過(guò)算法的遺傳搜索確定集合U中每個(gè)節(jié)點(diǎn)與集合H中的節(jié)點(diǎn)之間的指派關(guān)系，最終得到?jīng)Q策模型的解決方案。

(1)初始染色群體的設(shè)計(jì)

首先，將集合V(元素個(gè)數(shù)設(shè)為v)中的節(jié)點(diǎn)指派給距離最近的集合H(元素個(gè)數(shù)設(shè)為h，v+h=n)中的樞紐中心點(diǎn)，每個(gè)非樞紐節(jié)點(diǎn)只能指派給唯一特定的樞紐中心，若出現(xiàn)貨運(yùn)站節(jié)點(diǎn)到達(dá)兩個(gè)樞紐中心點(diǎn)的距離相等的情況，則隨機(jī)選取其中一個(gè)即可。如果將集合V中的v個(gè)非樞紐節(jié)點(diǎn)到集合H的h個(gè)樞紐中心的指派關(guān)系作為染色體的一個(gè)基因，那么整條染色體的基因個(gè)數(shù)將是v*h個(gè)，即一條染色體中有v段，每一段染色體有h個(gè)基因，h個(gè)基因的表示方式為二進(jìn)制，1表示貨運(yùn)站指派給所在的染色體基因段的樞紐中心，0表示貨運(yùn)站不指派給所在的染色體基因段的樞紐中心。

例如：v=4，h=8，V=(1,2,3,4)，H=(5,6,7,8,9,10,11,12)

染色體第一段，非樞紐節(jié)點(diǎn)到樞紐中心1的指派方式：

56789101112111000000

染色體第二段，非樞紐節(jié)點(diǎn)到樞紐中心2的指派方式：

56789101112200110000

染色體第三段，非樞紐節(jié)點(diǎn)到樞紐中心3的指派方式：

56789101112300001100

染色體第四段，非樞紐節(jié)點(diǎn)到樞紐中心4的指派方式：

56789101112400000011

通過(guò)設(shè)定染色體中的基因片段的不同的基因值，可以得到不同的染色體，組成初始染色體群。不同的染色體中基因片段和基因值各不相同，即相對(duì)應(yīng)的非樞紐節(jié)點(diǎn)與樞紐節(jié)點(diǎn)之間的指派方案和整個(gè)運(yùn)營(yíng)網(wǎng)絡(luò)不同，最終得出的運(yùn)營(yíng)網(wǎng)絡(luò)總成本也不同，總成本最小的方案最優(yōu)，總成本最大的方案最差。

(2)適應(yīng)度函數(shù)設(shè)計(jì)

遺傳算法在進(jìn)化搜索過(guò)程中基本不利用外部信息，僅以適應(yīng)度函數(shù)(Fitness Function)作為進(jìn)化的依據(jù)，利用中群眾每個(gè)個(gè)體的適應(yīng)度來(lái)進(jìn)行判斷和搜索。適應(yīng)度函數(shù)的選取至關(guān)重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而來(lái)的。定義目標(biāo)函數(shù)的方法，對(duì)于同一個(gè)問(wèn)題而言，可能不止一種，選擇時(shí)要盡量反應(yīng)問(wèn)題本身的整體特性，而不是只追求片面的目標(biāo)。一般來(lái)說(shuō)，適應(yīng)度函數(shù)設(shè)計(jì)主要滿足以下條件：

1)單值、非負(fù)、最大化；

2)合理、一致性。要求適應(yīng)度函數(shù)值反應(yīng)對(duì)應(yīng)解的優(yōu)劣程度。

3)計(jì)算量小。適應(yīng)度函數(shù)設(shè)計(jì)要簡(jiǎn)單，減少計(jì)算時(shí)間和復(fù)雜性。

4)通用性強(qiáng)。適應(yīng)度函數(shù)對(duì)某類問(wèn)題，應(yīng)盡可能通用。

運(yùn)營(yíng)網(wǎng)絡(luò)的總成本可以通過(guò)染色體適應(yīng)度的設(shè)定準(zhǔn)確的反映出來(lái)，可以將染色體的適應(yīng)度設(shè)為與運(yùn)營(yíng)網(wǎng)絡(luò)總成本成反比例關(guān)系的值，即總成本越小，該染色體的適應(yīng)度越高，反之則相反。為了達(dá)到在遺傳選擇過(guò)程中選取適應(yīng)度較大的染色體概率較大和成本最小化的目的，因此適應(yīng)度函數(shù)設(shè)定如下：

表1 20個(gè)戰(zhàn)略重點(diǎn)城市

Fit(f(x))=M-f(x)

其中M為較大的常量，使得函數(shù)值非負(fù)。適應(yīng)度函數(shù)將目標(biāo)函數(shù)值轉(zhuǎn)化成適應(yīng)度，可以看出適應(yīng)度越大，表明總成本越小，優(yōu)化方案越好。

(3)選擇操作設(shè)計(jì)

我們選用賭盤(pán)選擇法進(jìn)行選擇運(yùn)算，具體操作如下：

1)計(jì)算出群體中每個(gè)個(gè)體的適應(yīng)度Fiti；

3)計(jì)算出每個(gè)個(gè)體被遺傳到下一代群體中的概率pi，pi=Fiti/Fitzong

5)在[0,1]內(nèi)產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)r；

6)若r≤q1，則選擇個(gè)體1；否則，選擇個(gè)體k，使得qk-1

7)重復(fù)5、6步驟共pop_size次，每次選出一個(gè)染色體，最終構(gòu)成新的種群。

(4)交叉操作設(shè)計(jì)

我們采用多點(diǎn)交叉的方法來(lái)解混合軸輻式網(wǎng)絡(luò)規(guī)劃問(wèn)題，主要有以下步驟：

1)設(shè)定交叉概率pc，循環(huán)次數(shù)Nc為：Nc=Chr_gene_size*pop_size*pc/2

其中：Chr_gene_size為每條染色體中基因個(gè)數(shù)；

2)在每一次的循環(huán)過(guò)程中，選取隨機(jī)配對(duì)的染色體對(duì)進(jìn)行基因交叉運(yùn)算，從而產(chǎn)生新的個(gè)體，進(jìn)而組成新的染色體群體。

(5)變異操作設(shè)計(jì)

變異過(guò)程主要有以下步驟：

1)設(shè)定變異概率pm，變異循環(huán)次數(shù)為Nd：Nd=Chr_gene_size*pop_size*pm

2)在每一次的變異過(guò)程中，隨機(jī)選取一個(gè)染色體，隨機(jī)選取該染色體中的任意基因點(diǎn)位進(jìn)行變異，產(chǎn)生新的個(gè)體。

5 求解算法設(shè)計(jì)與案例計(jì)算

我們以國(guó)內(nèi)某標(biāo)桿快遞公司的長(zhǎng)三角區(qū)域陸路快遞網(wǎng)絡(luò)設(shè)計(jì)為例對(duì)上述決策過(guò)程的可適用性進(jìn)行驗(yàn)證。

5.1 數(shù)據(jù)準(zhǔn)備

本實(shí)例需要準(zhǔn)備的基礎(chǔ)數(shù)據(jù)如下：

1)城市節(jié)點(diǎn)數(shù)據(jù)：節(jié)點(diǎn)集合包括樞紐節(jié)點(diǎn)和非樞紐節(jié)點(diǎn)，如表1；

2)距離和流量數(shù)據(jù)：距離數(shù)據(jù)為每個(gè)節(jié)點(diǎn)對(duì)之間的距離，該距離矩陣為對(duì)稱矩陣，由百度地圖測(cè)得；流量數(shù)據(jù)為起始站到終點(diǎn)站在統(tǒng)計(jì)周期內(nèi)的平均貨流量，節(jié)點(diǎn)對(duì)之間的正逆向流量是不一樣的，因企業(yè)保密問(wèn)題，略去展示。

3)遺傳算法基本參數(shù)數(shù)據(jù)：包括染色體種群大小、染色體基因數(shù)目、種群的最大進(jìn)化代數(shù)、交叉概率、變異概率、適應(yīng)度函數(shù)中的常量M、迭代次數(shù)，如表2。

表2 遺傳算法參數(shù)設(shè)定

5.2 樞紐中心的確定

表3 確定的樞紐中心

表4 城市節(jié)點(diǎn)對(duì)的流量

至此，可以將案例中的城市節(jié)點(diǎn)分為兩大類：

第一類，樞紐中心點(diǎn)集合：上海、蘇州、杭州、南京；

第二類，非樞紐節(jié)點(diǎn)集合：常州、合肥、淮安、嘉興、金華、連云港、南京、南通、寧波、紹興、臺(tái)州、溫州、無(wú)錫、徐州、鹽城、揚(yáng)州、鎮(zhèn)江。

5.3 非樞紐節(jié)點(diǎn)之間直達(dá)路徑的確定

通過(guò)數(shù)據(jù)整理，得到表4。

由表4，根據(jù)流量閾值判斷，可以得出7對(duì)直達(dá)線路：常州——南通、南通——寧波、南通——無(wú)錫、鹽城——寧波、鹽城——臺(tái)州、鹽城——無(wú)錫、揚(yáng)州——溫州。

5.4 非樞紐節(jié)點(diǎn)指派路徑的確定

基于節(jié)4.3所設(shè)計(jì)的遺傳算法，采用Matlab 7.0對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的指派問(wèn)題進(jìn)行了編程，針對(duì)本案例的20個(gè)節(jié)點(diǎn)的問(wèn)題規(guī)模進(jìn)行求解，最終得出全局近似最優(yōu)解如表5、6所示。

表5 求解所得的各項(xiàng)成本

表6 各樞紐中心的覆蓋情況

5.5 結(jié)果分析

我們同樣計(jì)算了不允許直達(dá)線路存在的網(wǎng)絡(luò)結(jié)果，如表7所示。通過(guò)表6和表7的對(duì)比我們可以發(fā)現(xiàn)，在允許直達(dá)線路存在時(shí)，網(wǎng)絡(luò)總成本比不允許情形減少了約0.79%。另一方面，由于減少了迂回，7對(duì)直達(dá)線路的存在能夠顯著提高它們的服務(wù)效率和服務(wù)水平。

表7 不允許直達(dá)時(shí)的成本

6 結(jié)語(yǔ)

本文在允許直達(dá)的情形下建立了相應(yīng)的混合軸輻式快遞網(wǎng)絡(luò)規(guī)劃決策模型和決策流程，在保證時(shí)效性要求的前提下，以網(wǎng)絡(luò)成本最小化為目標(biāo)，對(duì)帶有直達(dá)線路的軸輻式網(wǎng)絡(luò)的規(guī)劃問(wèn)題進(jìn)行了分析和數(shù)學(xué)描述，并設(shè)計(jì)了遺傳算法對(duì)關(guān)鍵問(wèn)題進(jìn)行求解。進(jìn)而，基于實(shí)際的企業(yè)運(yùn)營(yíng)數(shù)據(jù)的實(shí)證研究證明了該決策模型和方法的有效性，并且發(fā)現(xiàn)：允許直達(dá)時(shí)，網(wǎng)絡(luò)成本能得到控制，并提高服務(wù)效率。

另一方面，本文研究存在以下不足之處尚需后續(xù)做進(jìn)一步研究：

(1)只考慮兩個(gè)層級(jí)的混合軸輻式網(wǎng)絡(luò)設(shè)計(jì)，如果能夠綜合考慮3個(gè)層次甚至更多軸輻式網(wǎng)絡(luò)，將更加貼近實(shí)際，能夠更好地指導(dǎo)實(shí)際應(yīng)用；

(2)本文初步考慮了以成本為目標(biāo)的優(yōu)化模型，并進(jìn)行了模型求解，可以嘗試采用多目標(biāo)優(yōu)化模型，加入相應(yīng)的時(shí)間約束，這方面的研究將是今后進(jìn)一步探討的重點(diǎn)；

(3)在算法設(shè)計(jì)中，本文首先確定了樞紐中心的個(gè)數(shù)和選址，這對(duì)成本最小化目標(biāo)有一定的影響；根據(jù)相關(guān)文獻(xiàn)，可以從全局最優(yōu)的角度出發(fā)，以成本最小化為目標(biāo)，讓算法自動(dòng)求解出相應(yīng)的樞紐中心個(gè)數(shù)和選址，從而給出全局最優(yōu)解，等。

[1] 國(guó)家郵政局.國(guó)家郵政局公布2014年郵政行業(yè)運(yùn)行情況[EB/OL].[2015-01-15].http://www.spb.gov.cn/dtxx_15079/201501/t20150115_410741.html，2014.

[2] Campbell J F, O'Kelly M E. Twenty-five years of hub location research[J]. Transportation Science, 2012，46(2): 153-169.

[3] Contreras I, Fernández E. General network design: A unified view of combined location and network design problems[J]. European Journal of Operational Research, 2012, 219(3): 680-697.

[4] Alumur S, Kara B Y. Network hub location problems: The state of the art[J]. European Journal of Operational Research, 2008, 190 (1): 1-21.

[5] Rodriguez-Martin I, Salazar-Gonzalez J, Yaman H.A branch-and-cut algorithm for two-level survivable network design problems[J]. Computers & Operations Research, 2016, 67(c):102-112.

[6] Campbell J F. Hub location for time definite transportation[J]. Computers & Operations Research, 2009, 36(12): 3107-3116.

[7] Alumura S A,Yamanb H, Kara B Y. Hierarchical multimodal hub location problem with time-definite deliveries[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(6): 1107-1120.

[8] 趙宇哲.競(jìng)爭(zhēng)環(huán)境下的軸-輻式集裝箱海運(yùn)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題[J].中國(guó)管理科學(xué)，2015，23(7)：103-112.

[9] Zhang Jianjun, Tang Ou, Zhao Jin, et al.CPEL redesigns its land express network[J]. Interfaces,2013,43(3):221-231.

[10] 傅少川，胡夢(mèng)飛，唐方成.禁忌搜索算法在單分配多樞紐軸輻式物流網(wǎng)絡(luò)中的應(yīng)用[J].中國(guó)管理科學(xué)，2012，20(3)：145-151.

[11] 何明珂，程紅晶.快遞企業(yè)航空貨運(yùn)網(wǎng)絡(luò)的構(gòu)建[J].運(yùn)籌與管理，2013，22(6)：232-242.

[12] 倪玲霖，史峰.多分配快遞軸輻網(wǎng)絡(luò)的樞紐選址與分配優(yōu)化方法[J].系統(tǒng)工程理論與實(shí)踐，2012，32(2)：441-448.

[13] 熊中楷，方衍，張聰譽(yù).以舊換新收購(gòu)方式下的逆向物流網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)[J].中國(guó)管理科學(xué)，2011，19(6)：65-72.

Research on Hybrid Hub-spoke Express Network Decision with Point-to-point Direct Shipment

ZHAO Jin1,2, ZHANG Jian-jun3, YAN Cai-hua3

(1.Institute of vocational education, Tongji University, Shanghai 201804, China;2.China-German School of Engineering,Tongji University, Shanghai 201804, China;3.School of Economics and Management, Tongji University, Shanghai 200092, China)

express network; network design; point-to-point direct shipment; hybrid hub-spoke network; genetic algorithm

1003-207(2016)11-0058-08

10.16381/j.cnki.issn1003-207x.2016.11.007

2015-06-06；

2016-02-25

國(guó)家自然科學(xué)基金資助項(xiàng)目(71102071, 71373180);上海市社科規(guī)劃課題(2014BGL025)

張建軍(1978-)，男(漢族)，江西人，同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院副教授，博士生導(dǎo)師，研究方向：物流與供應(yīng)鏈管理，E-mail：zhangjianjun@#edu.cn.

F272

A