吳國(guó)濤，戚銘堯，張 瑩，陳 吉

（清華大學(xué) 深圳研究生院物流與交通學(xué)部，廣東 深圳 518055）

0 引言

多商品流問(wèn)題出現(xiàn)在各個(gè)應(yīng)用領(lǐng)域，如貨物配送、信號(hào)傳輸、電力傳輸?shù)阮I(lǐng)域。傳統(tǒng)的多商品流問(wèn)題（Multi-Commodity Network Flow，MCNF）描述的是多個(gè)商品在服務(wù)網(wǎng)絡(luò)中共享一些弧段的同時(shí)也競(jìng)爭(zhēng)共享弧段的容量［1］，該問(wèn)題根據(jù)目標(biāo)函數(shù)的不同主要分為最小化成本和最大化利潤(rùn)兩類。在最大化利潤(rùn)的情況下，一般假設(shè)配送到終點(diǎn)的成本不變，但是在實(shí)際情況中商品的成本隨配送路徑的增加而增加，因此傳統(tǒng)的多商品流模型不適合一些實(shí)際應(yīng)用場(chǎng)景。通過(guò)運(yùn)輸，商品的成本價(jià)格都會(huì)有一定程度的上漲，上漲的比率稱為成本上漲比率。本文研究在傳統(tǒng)MCNF的基礎(chǔ)上加入成本上漲因素，目的是最大化分銷商的利潤(rùn)?？紤]成本上漲的MCNF在實(shí)際中應(yīng)用較多，例如在生鮮食品和農(nóng)產(chǎn)品等分銷過(guò)程中，分銷商需要選擇供應(yīng)地與需求地之間利潤(rùn)最大的運(yùn)輸方案等。

帶容量限制的MCNF已經(jīng)被證明為NP-hard，目前對(duì)該類問(wèn)題的求解算法主要分為啟發(fā)式算法和精確算法兩大類。啟發(fā)式算法主要有禁忌搜索、鄰域搜索等：文獻(xiàn)［2］針對(duì)帶容量限制的多商品流問(wèn)題提出一種多層次合作的禁忌搜索算法，通過(guò)算例測(cè)試發(fā)現(xiàn)該算法適合商品數(shù)量較大的大規(guī)模MCNF；文獻(xiàn)［3］針對(duì)考慮固定費(fèi)用的容量限制MCNF，提出一種基于環(huán)路的鄰域結(jié)構(gòu)，實(shí)驗(yàn)表明基于該鄰域結(jié)構(gòu)的禁忌搜索算法比其他啟發(fā)式算法有更好的效果；文獻(xiàn)［4］針對(duì)整車物流網(wǎng)絡(luò)規(guī)劃問(wèn)題，提出一種流預(yù)測(cè)與遺傳算法相結(jié)合的算法，實(shí)驗(yàn)表明該算法可以很好地解決整車網(wǎng)絡(luò)規(guī)劃問(wèn)題；文獻(xiàn)［5］針對(duì)企業(yè)分銷網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，提出0-1和優(yōu)先權(quán)混合編碼的遺傳算法，很好地解決了分銷網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題；文獻(xiàn)［6］用二階段優(yōu)化方法解決了B2C模式下城市配送物流的網(wǎng)絡(luò)選址問(wèn)題。一般的MCNP 規(guī)模都比較大，精確算法主要集中在分解或列生成算法等：文獻(xiàn)［7］針對(duì)通信領(lǐng)域的一些附加約束，建立了針對(duì)該領(lǐng)域的多商品流模型，并提出對(duì)應(yīng)的列生成算法，測(cè)試結(jié)果表明該算法可以很好地解決通信領(lǐng)域的多商品流問(wèn)題；文獻(xiàn)［8］針對(duì)MCNP提出一種內(nèi)點(diǎn)算法，以克服傳統(tǒng)內(nèi)點(diǎn)算法求解效率低的缺陷，得到了很好的效率；文獻(xiàn)［9］運(yùn)用三階段分解算法解決了大規(guī)模貨物運(yùn)輸問(wèn)題。列生成算法在大規(guī)模線性規(guī)劃或整數(shù)規(guī)劃方面都表現(xiàn)出很大的潛力，具體見(jiàn)文獻(xiàn)［10-11］。

1 模型建立

1.1 問(wèn)題描述

考慮成本上漲的MCNP 可描述為：假設(shè)G=（N，A）為一個(gè)運(yùn)輸服務(wù)網(wǎng)絡(luò)，N為節(jié)點(diǎn)集合，A為有向弧段集合，如圖1所示。對(duì)于所有的節(jié)點(diǎn)，按照運(yùn)輸目的劃分為供應(yīng)節(jié)點(diǎn)、需求節(jié)點(diǎn)和中轉(zhuǎn)節(jié)點(diǎn)三類，其中：①供應(yīng)節(jié)點(diǎn)提供貨物，如圖1中的節(jié)點(diǎn)1，2，4；②需求節(jié)點(diǎn)對(duì)貨物有一定的需求，如圖1中的節(jié)點(diǎn)5～9；③每一個(gè)節(jié)點(diǎn)都是一個(gè)中轉(zhuǎn)節(jié)點(diǎn)，所有貨物都可以在中轉(zhuǎn)節(jié)點(diǎn)中轉(zhuǎn)，因此供應(yīng)、需求節(jié)點(diǎn)也是中轉(zhuǎn)節(jié)點(diǎn)，除此之外還有一類中轉(zhuǎn)節(jié)點(diǎn)，只有中轉(zhuǎn)作用，既不提供貨量也沒(méi)有需求，如圖1 中的節(jié)點(diǎn)3。商品定義為從供應(yīng)節(jié)點(diǎn)到需求節(jié)點(diǎn)的供應(yīng)貨量，即每一個(gè)商品對(duì)應(yīng)一個(gè)供應(yīng)節(jié)點(diǎn)、需求節(jié)點(diǎn)和貨量。每個(gè)商品都需要從供應(yīng)節(jié)點(diǎn)開(kāi)始，經(jīng)過(guò)一定的中間節(jié)點(diǎn)最后達(dá)到需求節(jié)點(diǎn)，來(lái)滿足需求節(jié)點(diǎn)的需求貨量。每個(gè)商品的需求節(jié)點(diǎn)對(duì)應(yīng)零售價(jià)格，供應(yīng)節(jié)點(diǎn)對(duì)應(yīng)基礎(chǔ)成本價(jià)格。商品的成本價(jià)格沿配送路徑逐步增加，每通過(guò)一弧段，成本價(jià)格都按成本上漲比率增加。商品的零售價(jià)格與其到達(dá)需求節(jié)點(diǎn)的成本價(jià)格的差值即為該商品的利潤(rùn)。另外，有弧段連接的兩節(jié)點(diǎn)之間可以運(yùn)輸貨物，但是有一定的容量限制?；《渭螦有雙向弧段（如圖1中節(jié)點(diǎn)1到節(jié)點(diǎn)3的弧段），表示可以雙向運(yùn)輸，也有單向弧段（如圖1中節(jié)點(diǎn)6到節(jié)點(diǎn)9的弧段），表示只能單向運(yùn)輸，除此之外還有一些弧段事先已經(jīng)存在一定的運(yùn)輸量（如圖1節(jié)點(diǎn)4到節(jié)點(diǎn)6的弧段），表示該弧段安排的運(yùn)輸量至少比已經(jīng)安排的貨量大，但是不超過(guò)該弧段的容量限制。在給定運(yùn)輸網(wǎng)絡(luò)結(jié)構(gòu)和商品需求的情況下，需要設(shè)計(jì)相應(yīng)的配送路徑，使分銷商的利潤(rùn)最大。

1.2 非線性數(shù)學(xué)模型

為方便討論，引入以下符號(hào)：K表示所有的商品集合；Rk表示第k個(gè)商品的所有路徑集合；o（k）表示第k個(gè)商品的起點(diǎn)；d（k）表示第k個(gè)商品的終點(diǎn)；uij表示弧段（i，j）上的最大運(yùn)輸量；pij表示弧段（i，j）的成本上漲率；表示第k個(gè)商品第r條路徑在弧段（i，j）上的運(yùn)輸量；如果第k個(gè)商品第r條路徑在弧段（i，j）上有運(yùn)輸量，則，否則；dj表示第j個(gè)需求節(jié)點(diǎn)的需求量；si表示 第i個(gè)供應(yīng)節(jié)點(diǎn)的供應(yīng)量；aij表示弧段（i，j）的預(yù)分配量；demand表示需求節(jié)點(diǎn)集合；supply表示供應(yīng)節(jié)點(diǎn)集合；assign表示預(yù)分配弧段集合。

考慮成本上漲MCNP的非線性模型如下：

2 列生成算法的設(shè)計(jì)

高次非線性規(guī)劃的問(wèn)題一直沒(méi)有通用的求解算法。一般來(lái)說(shuō)，小規(guī)模問(wèn)題可以用LocalSolver等非線性求解器求解，大規(guī)模問(wèn)題則采用線性化手段將其轉(zhuǎn)化成線性規(guī)劃問(wèn)題或者直接用啟發(fā)式算法求解。對(duì)于考慮成本上漲的多商品流問(wèn)題，一般都希望得到最優(yōu)解，一方面最大化其利潤(rùn)，另一方面根據(jù)市場(chǎng)實(shí)時(shí)調(diào)整自己的零售價(jià)格。因此，本文未用啟發(fā)式算法而采用降低次數(shù)的手段，首先將高次非線性問(wèn)題分解為主問(wèn)題和二次非線性子問(wèn)題，然后設(shè)計(jì)列生成算法迭代求解從而得到最優(yōu)解。其中具體線性規(guī)劃問(wèn)題用Gurobi優(yōu)化求解器計(jì)算。

列生成算法的基本流程：

步驟1 對(duì)于每個(gè)商品，求解從其供應(yīng)節(jié)點(diǎn)到需求節(jié)點(diǎn)的考慮成本上漲的最短路問(wèn)題，得到各自的最短路，從而形成初始運(yùn)輸方案，該方案有可能不是可行解，因?yàn)榭赡懿粷M足預(yù)分配約束。

步驟2 求解主問(wèn)題模型，得到當(dāng)前的最優(yōu)解及相應(yīng)的對(duì)偶變量。

步驟3 每個(gè)商品根據(jù)主問(wèn)題得到的對(duì)偶變量，求解對(duì)應(yīng)的最大化檢驗(yàn)數(shù)模型。如果有商品的最大檢驗(yàn)數(shù)大于0，則添加相應(yīng)的新路徑和新變量，返回步驟2。

步驟4 輸出主問(wèn)題，得到最優(yōu)解。

除此之外，由于一般列生成算法的效率比較低，還需要設(shè)計(jì)加速策略來(lái)提高列生成的效率，例如在初始解求解時(shí)剔除那些不可能的配送情況，用Gurobi的動(dòng)態(tài)生成新變量功能來(lái)提高求解效率等。

2.1 初始解階段

為了提高列生成的求解效率、使算法盡快得到最優(yōu)解，在初始解階段不采用人工變量的方法，而是設(shè)計(jì)相應(yīng)的優(yōu)化模型以獲得最有可能存在于最優(yōu)方案中的路徑。對(duì)于第k個(gè)商品，存在一條路徑，使得從供應(yīng)節(jié)點(diǎn)到需求節(jié)點(diǎn)的成本價(jià)格最小，從而使貨物運(yùn)輸商獲得的利潤(rùn)最大，因此該路徑最有可能存在于整體最優(yōu)方案中，用它來(lái)產(chǎn)生初始解。

獲得每個(gè)商品最短路徑的具體步驟如下：

1）構(gòu)建每個(gè)商品的考慮成本上漲的最短路模型；

2）消除存在的冗余圈。

對(duì)于非線性模型中的高次函數(shù)表達(dá)式，通過(guò)引入節(jié)點(diǎn)價(jià)格變量將其降低為二次函數(shù)表達(dá)式。對(duì)于第k個(gè)商品，只有一條成本價(jià)格最小的路徑。假設(shè)弧段（i，j）在該路徑上，則節(jié)點(diǎn)j的價(jià)格變量

式（9）表明，節(jié)點(diǎn)j的成本價(jià)格為節(jié)點(diǎn)i的成本價(jià)格與成本上漲率之乘積。通過(guò)引入節(jié)點(diǎn)價(jià)格變量，可以將高次函數(shù)表達(dá)式轉(zhuǎn)化為二次函數(shù)表達(dá)式，從而降低求解難度。

第k個(gè)商品的考慮成本上漲的最短路模型如下：

其中：目標(biāo)函數(shù)（10）為最小化到達(dá)需求節(jié)點(diǎn)的成本價(jià)格；約束（11）為起始節(jié)點(diǎn)的網(wǎng)絡(luò)約束；約束（12）為中間節(jié)點(diǎn)的網(wǎng)絡(luò)約束；約束（13）為終止節(jié)點(diǎn)的網(wǎng)絡(luò)約束；約束（14）為中間節(jié)點(diǎn)的成本價(jià)格約束；約束（15）為起點(diǎn)成本的價(jià)格需求；約束（16）是為了防止出現(xiàn)自循環(huán)約束，加上該約束可以提高算法的效率；約束（17）為變量取值約束。

上述模型會(huì)出現(xiàn)冗余圈的情況（如圖2）。假設(shè)節(jié)點(diǎn)1為供應(yīng)節(jié)點(diǎn)、節(jié)點(diǎn)4為需求節(jié)點(diǎn)，則生成的路徑中可能會(huì)出現(xiàn)與路徑完全沒(méi)有交集的冗余圈（如節(jié)點(diǎn)5～7），該冗余圈不會(huì)影響傳入需求節(jié)點(diǎn)的成本價(jià)格，但是會(huì)對(duì)主問(wèn)題的求解造成很大的影響。為了消除冗余圈，在目標(biāo)函數(shù)中引入對(duì)弧段數(shù)量的統(tǒng)計(jì)，使結(jié)果中的弧段越少越好；同時(shí)為了減少該統(tǒng)計(jì)量對(duì)目標(biāo)函數(shù)的影響，應(yīng)該引入一個(gè)微小的統(tǒng)計(jì)量。因此將目標(biāo)函數(shù)替換為式（18），其中ε為無(wú)窮小量，可取值0.01。

2.2 主問(wèn)題階段

根據(jù)初始解階段得到的可行解設(shè)計(jì)相應(yīng)的主問(wèn)題，來(lái)獲得當(dāng)前最優(yōu)解和對(duì)偶變量。由于得到的初始解不一定滿足預(yù)分配約束，即對(duì)某一預(yù)分配的弧段來(lái)說(shuō)，通過(guò)的貨量不能保證都大于預(yù)分配值。為了保證問(wèn)題的可行性，對(duì)每一個(gè)預(yù)分配約束引入一個(gè)人工變量yij，同時(shí)在目標(biāo)函數(shù)中引入人工變量的懲罰成本，當(dāng)所有人工變量都為0時(shí)，得到的解才是原問(wèn)題的可行解。

其中：目標(biāo)函數(shù)（19）是最大化分銷商的利潤(rùn)和違反預(yù)分配約束的懲罰成本之和；約束（20）限制所有經(jīng)過(guò)某弧段的貨量不超過(guò)其容量；約束（21）限定所有到達(dá)某需求節(jié)點(diǎn)的貨量不超過(guò)其需求量；約束（22）限定某供應(yīng)節(jié)點(diǎn)的供應(yīng)貨量不能超過(guò)其供應(yīng)量；約束（23）限制通過(guò)某弧段的貨量和人工變量之和要超過(guò)其預(yù)分配量；約束（24）為變量取值約束。

2.3 子問(wèn)題階段

子問(wèn)題主要有兩方面作用：①判斷主問(wèn)題得到的解是否為原問(wèn)題的最優(yōu)解；②如果沒(méi)有得到最優(yōu)解，則向主問(wèn)題中添加新變量和新路徑，使主問(wèn)題的目標(biāo)函數(shù)值增加。根據(jù)主問(wèn)題得到的對(duì)偶變量，對(duì)每個(gè)商品構(gòu)建一個(gè)優(yōu)化模型，判斷該商品的所有可行路徑中是否存在一條路徑，使得主問(wèn)題中加入該路徑后其總目標(biāo)值可以增加，如果存在則將該路徑作為新的變量加入主問(wèn)題中?？梢钥闯鰡?wèn)題是一個(gè)最大化回路問(wèn)題，對(duì)比初始階段的模型，唯一不同的就是目標(biāo)函數(shù)：初始階段的模型是最小化需求節(jié)點(diǎn)的成本價(jià)格，子問(wèn)題的目標(biāo)函數(shù)是最大化每個(gè)商品對(duì)應(yīng)的檢驗(yàn)數(shù)。如果對(duì)偶變量π=（π1，π2，π3，π4）分別對(duì) 應(yīng)主問(wèn)題中的四個(gè)約束集，則該檢驗(yàn)數(shù)的表達(dá)式為

以式（25）為目標(biāo)函數(shù)、以式（11）～式（17）為約束條件和變量取值約束，即為子問(wèn)題的優(yōu)化模型。然而該模型得到的最優(yōu)解同樣存在冗余圈問(wèn)題（如圖2），對(duì)主問(wèn)題的求解造成很大的影響。由于子問(wèn)題的目標(biāo)函數(shù)中包含對(duì)弧段的統(tǒng)計(jì)，不能用類似初始解階段的方法。為了消除冗余圈，根據(jù)切平面的思想設(shè)計(jì)相應(yīng)的破圈約束。這種破圈約束有很多個(gè)，為了提高算法的求解效率，采用動(dòng)態(tài)添加破圈約束的方式，具體方法為：當(dāng)在子問(wèn)題求解過(guò)程中回調(diào)函數(shù)發(fā)現(xiàn)存在冗余圈時(shí)，動(dòng)態(tài)添加相應(yīng)的破圈約束。假設(shè)X=｛x1，x2，…，xn｝為路徑中存在的冗余圈，對(duì)應(yīng)的冗余圈消除約束為

2.4 加速策略

對(duì)于大規(guī)模的MCNF，傳統(tǒng)的列生成算法存在求解效率低下的問(wèn)題，因此設(shè)計(jì)相應(yīng)的加速策略來(lái)提高列生成算法的求解效率。加速策略如下：

（1）盡早剔除不可能的商品

由于列生成算法求解效率與商品數(shù)量存在正相關(guān)的關(guān)系，商品數(shù)量越大，求解時(shí)間就越多，如果能盡早識(shí)別那些不可能存在于最優(yōu)方案中的商品，就可以加快算法的求解。因此可根據(jù)初始階段得到的成本價(jià)格最小路徑來(lái)剔除那些不可能的方案，即如果到達(dá)需求節(jié)點(diǎn)的成本價(jià)格大于需求節(jié)點(diǎn)的售價(jià)，則該商品絕對(duì)不會(huì)存在于最優(yōu)方案中，因?yàn)檫@種商品對(duì)貨物運(yùn)輸商來(lái)說(shuō)是不盈利的，應(yīng)該盡早剔除。

（2）利用Gurobi動(dòng)態(tài)添加新變量的功能

列生成算法需要根據(jù)子問(wèn)題的求解結(jié)果向主問(wèn)題添加新的變量。在求解過(guò)程中，子問(wèn)題需要求解很多次，如果重復(fù)新建子問(wèn)題模型，則時(shí)間成本太大。采用Gurobi求解器提供的動(dòng)態(tài)添加變量的功能可以消除重復(fù)新建模型的消耗，還可以保存之前模型的最優(yōu)解結(jié)構(gòu)，加速Gurobi求解器的再次求解。

3 算例結(jié)果

因?yàn)樵搯?wèn)題缺少基準(zhǔn)數(shù)據(jù)，所以在算法性能的分析上采用隨機(jī)生成的測(cè)試算例。在實(shí)際算例（算例8）的基礎(chǔ)上隨機(jī)增加或減少弧段，通過(guò)弧段容量隨機(jī)生成當(dāng)前最大最小容量之間的數(shù)值并獲取10組不同的測(cè)試算例，分別對(duì)應(yīng)小、中、大規(guī)模算例。算例之間的主要區(qū)別為網(wǎng)絡(luò)規(guī)模和商品數(shù)量。列生成算法采用C＃語(yǔ)言在VS 2010平臺(tái)上編程實(shí)現(xiàn)，線性模型采用Gurobi 6.0求解器進(jìn)行求解。算法在處理器為雙核Pentium T4300（主頻為2.1 GHz）、內(nèi)存為4GB 的PC 機(jī)上運(yùn)行。表1所示為不同算例的測(cè)試結(jié)果。

表1 不同算例的結(jié)果

表1表明，列生成算法可以很好地解決考慮成本上漲的多商品流問(wèn)題，而且求解效率比較高。對(duì)于小規(guī)模問(wèn)題，算法可以在1s內(nèi)得到最優(yōu)解；對(duì)于中等規(guī)模問(wèn)題，算法可以在30s內(nèi)得到最優(yōu)解；對(duì)于大規(guī)模問(wèn)題（算例10），網(wǎng)絡(luò)規(guī)模和商品數(shù)都遠(yuǎn)遠(yuǎn)大于其他算例，算法可在幾分鐘內(nèi)得到最優(yōu)解。算例表明所設(shè)計(jì)的列生成算法可以高效地求解該問(wèn)題。

另外，算例1～3和算例4～9對(duì)應(yīng)著相同網(wǎng)絡(luò)規(guī)模、不同商品數(shù)的算例，從運(yùn)行時(shí)間可以看出，在同等網(wǎng)絡(luò)規(guī)模下，商品數(shù)越多，算法的求解時(shí)間就越長(zhǎng)；算例1和算例4（2和5，3和6）對(duì)應(yīng)不同網(wǎng)絡(luò)規(guī)模、相同商品數(shù)的算例，結(jié)果表明：在相同商品數(shù)的情況下，網(wǎng)絡(luò)規(guī)模越大，算法的運(yùn)行時(shí)間就越長(zhǎng)。通過(guò)對(duì)比算例1和算例3（4和6）后發(fā)現(xiàn)，在相同網(wǎng)絡(luò)規(guī)模下，商品數(shù)增加1倍，算法的求解時(shí)間增加3～5倍；通過(guò)對(duì)比算例1和算例4（2和5，3和6）后發(fā)現(xiàn)，在相同的商品數(shù)下，網(wǎng)絡(luò)規(guī)模增加1倍，算法的求解時(shí)間增加6～13倍。因此，相對(duì)于商品數(shù)，網(wǎng)絡(luò)規(guī)模對(duì)算法的性能影響更大。

表2所示為算例8 的計(jì)算結(jié)果。算例8 有23個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)、56個(gè)弧段、4個(gè)預(yù)分配弧段和104個(gè)商品，通過(guò)列生成算法得到問(wèn)題最優(yōu)解，即17條商品的配送路徑和相對(duì)應(yīng)的配送量。

表2 算例5的計(jì)算結(jié)果

續(xù)表2

4 結(jié)束語(yǔ)

本文在傳統(tǒng)的多商品流問(wèn)題中引入成本上漲因素，建立了基于弧段的非線性模型，并提出列生成算法，為求解大規(guī)模的此類問(wèn)題提供了一種新的方法。為了加快算法的求解效率，采用了成本價(jià)格最小化模型及盡早刪除無(wú)意義商品的策略；為了消除冗余圈，對(duì)初始化模型和子問(wèn)題模型設(shè)計(jì)了不同的消除冗余圈方法。測(cè)試結(jié)果表明，所設(shè)計(jì)的列生成算法在解決考慮成本上漲的多商品流問(wèn)題時(shí)具有很大的潛力。后續(xù)研究可以在多商品流問(wèn)題中考慮更多的約束，如時(shí)效要求等。

［1］JONES K，LUSTIG I，F(xiàn)ARVOLDEN J，et al.Multi-commodity network flows：the impact of formulation on decomposition［J］.Mathematical Programming，1993，62（1-3）：95-117.

［2］CRAINIC T G，LI Y，TOULOUSE M.A first multilevel co-operative algorithm for capacitated multi-commodity network design［J］.Computers &Operations Research，2006，33（9）：2602-2622.

［3］GHAMLOUCHE I，CRAINIC T G，GENDREAU M.Cyclebased neighborhoods for fixed-charge capacitated Multi-commodity network design［J］.Operations Research，2003，51（4）：655-667.

［4］QIN Xuwei，F(xiàn)AN Yushun，YIN Chaowan.Research on integrated optimization for automobile logistics network design［J］.Computer Integrated Manufacturing Systems，2006，12（3）：364-370（in Chinese）.［秦緒偉，范玉順，尹朝萬(wàn).整車物流網(wǎng)絡(luò)規(guī)劃集成優(yōu)化模型研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2006，12（3）：364-370.］

［5］LI Yu，ZHAO Jun，WU Gang.Model and algorithm for location-distribution problem in two-stage distribution network［J］.Computer Integrated Manufacturing Systems，2012，18（11）：2546-2553（in Chinese）.［李 愈，趙 軍，吳 剛.兩級(jí)分銷網(wǎng)絡(luò)選址—配送問(wèn)題的模型及算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2012，18（11）：2546-2553.］

［6］ZHOU Xiang，XU Maozeng，LYU Qiguang.Two-stage layout optimization model for distribution center and terminal node under B2Cmode［J］.Computer Integrated Manufacturing Systems，2014，20（12）：3140-3149（in Chinese）.［周 翔，許茂增，呂奇光.B2C模式下配送中心與末端節(jié)點(diǎn)的兩節(jié)點(diǎn)布局優(yōu)化模型［J］.計(jì)算機(jī)集成制造系統(tǒng)，2014，20（12）：3140-3149.］

［7］HOLMBERG K，YUAN D.A multi-commodity network-flow problem with side constraints on paths solved by column generation［J］.Informs Journal on Computing，2003，15（1）：42-57.

［8］CASTRO J.A specialized interior-point algorithm for multicommodity network flows［J］.SIAM Journal on Optimization，2000，10（3）：852-877.

［9］TEYPAZ N，SCHRENK S，CUNG V.A decomposition scheme for large-scale service network design with asset management［J］.Transportation Research Part E，2010，46（1）：156-170.

［10］LUBBECKE M E，DESROSIERS J.Selected topics in column generation［J］.Operations Research，2005，53（6）：1007-1023.

［11］WILHELM W.A technical review of column generation in integer programming［J］.Optimization and Engineering，2001，2（2）：159-200.