卷煙承運(yùn)標(biāo)段劃分模型研究

莊文杰，鄒翔宇，孫慶平，劉嘉

卷煙承運(yùn)標(biāo)段劃分模型研究

莊文杰，鄒翔宇，孫慶平，劉嘉*

江蘇中煙工業(yè)有限責(zé)任公司，南京 210011

面對(duì)卷煙需求頻次高、批量小，訂單碎片化的趨勢(shì)，合理的承運(yùn)標(biāo)段劃分方法不僅有利于平衡各承運(yùn)商的實(shí)際收益，也有利于提高拼車配載的可能性，從而降低運(yùn)輸成本。本文以最小化全部標(biāo)段內(nèi)部的需求點(diǎn)遍歷路程之和為優(yōu)化目標(biāo)建立模型。在此基礎(chǔ)上，本文提出了一種雙層算法對(duì)模型進(jìn)行求解，上層采用聚類方法獲取具有較高可行性的初始解；下層基于邊緣交換算法通過(guò)迭代對(duì)初始解進(jìn)行優(yōu)化，從而得到近似最優(yōu)解。最后，本文以A中煙公司為例，在其近兩年的訂單量歷史數(shù)據(jù)基礎(chǔ)上進(jìn)行了案例分析，驗(yàn)證了所提出模型與解決方法的有效性。

卷煙配送；標(biāo)段劃分；雙層優(yōu)化算法

隨著卷煙營(yíng)銷市場(chǎng)化取向改革的深入推進(jìn)，商業(yè)公司要貨頻次高、批量小，訂單碎片化趨勢(shì)越來(lái)越明顯，因此，迫切需要對(duì)承運(yùn)標(biāo)段劃分方法進(jìn)行深入研究[1]。充分考慮各標(biāo)段發(fā)貨訂單量均衡及拼車配載的可能性，不僅能夠降低供需雙方運(yùn)輸成本，調(diào)動(dòng)承運(yùn)商積極性，保證卷煙發(fā)貨高效完成，同時(shí)有利于提升承運(yùn)商整體運(yùn)作水平，實(shí)現(xiàn)資源的合理配置，進(jìn)而實(shí)現(xiàn)整個(gè)物流網(wǎng)絡(luò)的優(yōu)化。

目前A中煙公司向全國(guó)300多家商業(yè)公司供貨，省外地區(qū)銷售比例超過(guò)50%，物流運(yùn)輸存在點(diǎn)多、面廣、線長(zhǎng)的特點(diǎn)，運(yùn)輸費(fèi)用占物流總費(fèi)用比例較高[2]。A中煙公司現(xiàn)行卷煙承運(yùn)標(biāo)段主要依托于省域分界進(jìn)行劃分，運(yùn)輸網(wǎng)絡(luò)中的各個(gè)標(biāo)段訂單量不均衡、缺少科學(xué)合理的路線規(guī)劃，造成資源浪費(fèi)，存在運(yùn)輸成本偏高并且效率偏低的問(wèn)題。

國(guó)內(nèi)外學(xué)者對(duì)標(biāo)段劃分方面的研究，大多集中在物流配送區(qū)域劃分方面，通過(guò)對(duì)配送過(guò)程中車輛路徑的合理的規(guī)劃，以降低企業(yè)的運(yùn)輸成本，提高物料配送的效率和及時(shí)性。由于該問(wèn)題為一個(gè)多約束復(fù)雜決策的NP-hard組合優(yōu)化問(wèn)題，許多學(xué)者在構(gòu)建模型和提升算法精度方面做了一定工作。何夢(mèng)軍等[3]以最短配送時(shí)間為目標(biāo)，構(gòu)建了帶時(shí)間窗的非線性數(shù)學(xué)規(guī)劃模型，同步解決區(qū)域劃分與配送路徑優(yōu)化問(wèn)題。王勇等[4]將時(shí)滯成本納入研究范圍，以網(wǎng)絡(luò)總成本最小化為目標(biāo)函數(shù)構(gòu)建模型，并提出一種改進(jìn)粒子群-遺傳混合算法獲取最優(yōu)標(biāo)段劃分方案；袁慶達(dá)等[5]考慮了軟時(shí)間窗和混合車隊(duì)問(wèn)題，基于Tabu search算法設(shè)計(jì)了GENIUS兩階段啟發(fā)式算法。施國(guó)洪等[6]在研究區(qū)域網(wǎng)絡(luò)零售商物流配送問(wèn)題中提出了基于聚類改進(jìn)兩階段啟發(fā)式算法，第一階段采用聚類算法，并在第二階段運(yùn)用遺傳算法進(jìn)行求解。國(guó)外學(xué)者多采用基于聚類或啟發(fā)式方法對(duì)物料配送區(qū)域劃分進(jìn)行研究。Ganesh等[7]通過(guò)建立評(píng)價(jià)指標(biāo)體系，生成模糊關(guān)系矩陣，運(yùn)用模糊數(shù)學(xué)中的理論進(jìn)行物流配送點(diǎn)聚類研究。Wang等[8]對(duì)顧客進(jìn)行了聚類研究，通過(guò)模糊聚類算法劃分配送區(qū)域。通過(guò)對(duì)顧客進(jìn)行聚類分析，達(dá)到降低配送網(wǎng)絡(luò)復(fù)雜性的效果，便于進(jìn)行配送路徑優(yōu)化。Christofides[9]通過(guò)將配送區(qū)域網(wǎng)格化為大小不均等的正方形區(qū)域，區(qū)域內(nèi)需求視為單個(gè)需求點(diǎn)，其需求量為區(qū)域內(nèi)需求量總和，區(qū)域中心坐標(biāo)作為區(qū)域點(diǎn)坐標(biāo)，依據(jù)不同正方形區(qū)域的歷史路徑連接頻率將各正方形區(qū)域聚合為配送單元。Wang等[10]建立物流配送分區(qū)模型以最小化雙層級(jí)物流網(wǎng)絡(luò)總成本，并提出擴(kuò)展的混合粒子群遺傳算法進(jìn)行求解。本文研究思路將該問(wèn)題轉(zhuǎn)換為一種特殊的多旅行商問(wèn)題，每個(gè)區(qū)域配送的承運(yùn)商可視為一個(gè)旅行商，通過(guò)引入?yún)^(qū)域內(nèi)訂單均衡的特殊約束，來(lái)實(shí)現(xiàn)物流配送區(qū)域的最優(yōu)劃分。多旅行商問(wèn)題多采用元啟發(fā)式算法進(jìn)行求解，如Sacramento等[11]研究了無(wú)人機(jī)和卡車協(xié)作的多旅行商問(wèn)題，建立了以時(shí)間限制和成本最小化的數(shù)學(xué)模型，設(shè)計(jì)自適應(yīng)大型鄰域搜索元啟發(fā)式算法。Miranda等[12]研究了混合負(fù)載的校車路線問(wèn)題，通過(guò)將迭代局部搜索和特殊鄰域結(jié)構(gòu)結(jié)合的多負(fù)載優(yōu)化方法，降低該問(wèn)題的計(jì)算代價(jià)。Yuan等[13]針對(duì)多旅行商問(wèn)題提出了一種新的兩部分染色體交叉算子，并驗(yàn)證基于該算法求解多旅行商問(wèn)題的有效性。

卷煙承運(yùn)標(biāo)段劃分在煙草公司主要采用基于省域或者片區(qū)的經(jīng)驗(yàn)劃分方法，易于管理，標(biāo)段輪廓明確。有學(xué)者[14-15]研究了煙草配送中轉(zhuǎn)站的選址，在此基礎(chǔ)上考慮固定成本與變動(dòng)成本，建立物流配送區(qū)域劃分?jǐn)?shù)學(xué)規(guī)劃模型。但隨時(shí)需求碎片化和外部形勢(shì)的變化，傳統(tǒng)劃分方法存在的運(yùn)輸資源浪費(fèi)的劣勢(shì)不斷凸顯。本文考慮訂單量分配要求，承運(yùn)商收益平衡要求等現(xiàn)實(shí)約束，研究基于運(yùn)輸里程、訂單量分配來(lái)支撐更合理的量化標(biāo)段劃分方法。主要研究如何在訂單量均衡（承運(yùn)商利益基本均衡）約束下，盡可能地提高卷煙拼車配載運(yùn)輸?shù)目赡苄?。著重采用科學(xué)的數(shù)學(xué)建模與求解方法，進(jìn)行承運(yùn)標(biāo)段劃分。主要的研究目標(biāo)包括以下4個(gè)方面：一是研究探索合理的標(biāo)段劃分?jǐn)?shù)目，形成理論依據(jù)；二是實(shí)現(xiàn)各個(gè)標(biāo)段內(nèi)訂單量基本均衡，各承運(yùn)商的收益基本平衡；三是提高拼車發(fā)貨的可能性，有效降低運(yùn)輸成本，實(shí)現(xiàn)雙方共贏；四是同標(biāo)段內(nèi)的城市盡可能集中分布，降低物流網(wǎng)絡(luò)的復(fù)雜度，為智能運(yùn)輸調(diào)度奠定基礎(chǔ)。

1 模型構(gòu)建

本文以卷煙廠位置為起點(diǎn)，各標(biāo)段對(duì)其內(nèi)部商業(yè)公司所在城市進(jìn)行遍歷且最后回到卷煙廠所在位置，當(dāng)所經(jīng)過(guò)的總路程達(dá)到最小時(shí)，此時(shí)的標(biāo)段劃分達(dá)到最優(yōu)，拼車配載的可行性最高。

1.1 參數(shù)

廠商所服務(wù)的城市集合（單位：個(gè)）

廠商服務(wù)全部城市的訂單總量（單位：件）

廠商服務(wù)城市集合（單位：個(gè)）

m 城市的訂單量為m（單位：件）

標(biāo)段集合（單位：個(gè)）

標(biāo)段數(shù)量（單位：個(gè)）

C標(biāo)段包含的城市集合（單位：個(gè)）

N 標(biāo)段包含的城市數(shù)（單位：個(gè)）

[] 城市間鄰接矩陣（單位：無(wú)）

d鄰接矩陣中城市到城市的距離（單位：公里）

1.2 變量

θ若θ=1，則表示從城市出發(fā)前往城市；反之，若θ=0，表示未從城市出發(fā)前往城市

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

為了盡可能提高同一標(biāo)段內(nèi)城市運(yùn)輸任務(wù)的拼車可能性，優(yōu)化目標(biāo)設(shè)置為最小化全部標(biāo)段內(nèi)部的路程之和。

1.4 約束條件

其中，公式（2）確保標(biāo)段內(nèi)的城市之和等于需求點(diǎn)城市總數(shù)；公式（3）確保每個(gè)城市只屬于一個(gè)標(biāo)段；公式（2）和（3）共同構(gòu)成了城市的全覆蓋約束；公式（4）確保滿足全部訂單量運(yùn)輸任務(wù)；公式（5）確保節(jié)點(diǎn)訪問(wèn)的進(jìn)出流量平衡，即任意城市商業(yè)公司的訪問(wèn)次數(shù)等于該商業(yè)公司的駛出次數(shù)；公式（6）中a，b為系數(shù)，控制標(biāo)段訂單量閾值。該閾值設(shè)定目的為確保各個(gè)標(biāo)段訂單量相對(duì)均衡，且在招標(biāo)時(shí)對(duì)承運(yùn)商產(chǎn)生一定差異化競(jìng)爭(zhēng)，可結(jié)合各招標(biāo)單位自身情況設(shè)置。本文中通過(guò)對(duì)A中煙公司的專家調(diào)研，最終設(shè)置為a=0.85，b=1.1。

2 算法設(shè)計(jì)

由于本文研究的標(biāo)段劃分問(wèn)題是NP-hard問(wèn)題，研究表明該類問(wèn)題無(wú)法在有效時(shí)間內(nèi)獲取最優(yōu)解。因此，為客觀評(píng)價(jià)標(biāo)段劃分方案的優(yōu)劣程度，本文基于兩種方案進(jìn)行標(biāo)段劃分優(yōu)化設(shè)計(jì)。一是對(duì)照組方案，不考慮訂單量約束，計(jì)算得出理論最優(yōu)目標(biāo)函數(shù)值；二是模型優(yōu)化方案，加入訂單量約束條件，設(shè)計(jì)了雙層算法并進(jìn)行求解。由于對(duì)照組方案去除了訂單量約束，其取值實(shí)質(zhì)為帶訂單約束問(wèn)題的數(shù)值下界，可用以評(píng)估優(yōu)化方案解的優(yōu)劣程度。

2.1 對(duì)照組方案（無(wú)訂單量約束）

在不考慮訂單量約束的情況下，設(shè)置優(yōu)化目標(biāo)為：在遍歷全部商業(yè)公司城市的條件下，最小化全部承運(yùn)商的總行程距離[8]。求解具體步驟如下：

Step1：標(biāo)段數(shù)為k，則在N個(gè)城市的基礎(chǔ)上，增加（k-1）個(gè)與起點(diǎn)重疊的虛擬起點(diǎn)（虛擬起點(diǎn)之間的距離設(shè)為無(wú)窮）。

Step2：構(gòu)建含（N+k）個(gè)點(diǎn)的鄰接矩陣，基于Dijkstra算法得最短距離矩陣。

Step3：求解目標(biāo)函數(shù)值。

Step4：求解后，相鄰兩起點(diǎn)之間經(jīng)過(guò)的城市劃分為1個(gè)標(biāo)段，依此類推。

2.2 模型優(yōu)化方案（有訂單量約束）

采用雙層算法進(jìn)行有訂單量約束的標(biāo)段劃分：上層采用聚類方法獲取具有較高可行性的初始解；下層基于邊緣交換算法通過(guò)迭代對(duì)初始解進(jìn)行優(yōu)化，從而得到近似最優(yōu)解。

（1）上層算法?；诰頍煆S商到各商業(yè)公司所在城市的最短路徑矩陣對(duì)城市進(jìn)行聚類，以提升其拼車概率。步驟如下：

Step1：基于Dijkstra算法（最短路徑算法）獲取從卷煙廠商出發(fā)到全部發(fā)貨城市的最短路徑矩陣。

Step2：根據(jù)以城市為節(jié)點(diǎn)的最短路徑，將全部城市按照k個(gè)簇進(jìn)行聚類。

Step2.1：隨機(jī)選取k個(gè)城市作為初始聚類中心；

Step2.2：計(jì)算每個(gè)城市到k個(gè)中心的距離，并將該城市分配至與中心距離最小的簇中；

Step2.3：重新計(jì)算當(dāng)前每個(gè)簇的中心，如果中心位置不再移動(dòng)，則結(jié)束迭代，否則重復(fù)Step2.2和Step2.3。

（2）下層算法。邊緣交換算法屬于局部搜索算法，是解決組合優(yōu)化問(wèn)題的有效工具，如今已經(jīng)廣為人知并且在組合優(yōu)化領(lǐng)域中得到了廣泛的應(yīng)用[9-10]。下層算法對(duì)初始解進(jìn)行優(yōu)化，考慮到初始解可能存在的局限性，所以在交換操作基礎(chǔ)上，增加了移動(dòng)操作。步驟如下：

Step1：針對(duì)初始方案計(jì)算其目標(biāo)函數(shù)，記錄為當(dāng)前最優(yōu)解T0，當(dāng)前迭代次數(shù)t=0。

Step3：第t次迭代開(kāi)始，隨機(jī)執(zhí)行移動(dòng)操作或者交換操作的優(yōu)化算子，具體如下；

Step5：檢驗(yàn)當(dāng)前目標(biāo)函數(shù)值T，若T＜T0，則更新為當(dāng)前最優(yōu)解，T0=T，并重新進(jìn)入Step3；反之，拒絕該操作，直接重新進(jìn)入Step4。

Step6：依此類推，直到達(dá)到終止條件，輸出最終解即為模型優(yōu)化方案。

圖1 鄰接標(biāo)段間的移動(dòng)操作

圖2 鄰接標(biāo)段間的交換操作

2.3 最優(yōu)標(biāo)段數(shù)探索

在進(jìn)行標(biāo)段劃分方案計(jì)算時(shí)，首先需確定在可接受范圍內(nèi)的最優(yōu)標(biāo)段數(shù)。為探索標(biāo)段數(shù)的普適性規(guī)律，本文以A中煙公司B廠為例，根據(jù)其近兩年（2016年4月—2017年12月）的訂單量數(shù)據(jù)及產(chǎn)品需求終點(diǎn)的分布情況，對(duì)其最優(yōu)標(biāo)段數(shù)進(jìn)行探究。

圖3 目標(biāo)函數(shù)變化趨勢(shì)對(duì)比（橫坐標(biāo)代表標(biāo)段數(shù)單位，縱坐標(biāo)代表距離目標(biāo)函數(shù)）

經(jīng)過(guò)本文的探索，由圖3可以發(fā)現(xiàn)：對(duì)于對(duì)照組和模型最優(yōu)方案，當(dāng)標(biāo)段數(shù)從10增加到20過(guò)程中，目標(biāo)函數(shù)均隨之增大，而標(biāo)段數(shù)為1即不劃分標(biāo)段時(shí)，目標(biāo)函數(shù)取得最小值。從理論上而言，當(dāng)全部城市劃為一個(gè)標(biāo)段時(shí)，拼車可能性最大，該結(jié)論也與A中煙公司的歷史配送經(jīng)驗(yàn)相符合。

基于此，本文提出：為了促進(jìn)承運(yùn)商之間的良好競(jìng)爭(zhēng)，可以根據(jù)現(xiàn)有承運(yùn)商數(shù)量k，將標(biāo)段數(shù)設(shè)置為（k+1）的形式。如此，一方面可以符合實(shí)際需求，另一方面也在理論上可盡可能地提高卷煙運(yùn)輸拼車可能性。

3 案例分析

為了驗(yàn)證所提出的卷煙標(biāo)段劃分方法的有效性，本文以A中煙公司為例進(jìn)行標(biāo)段劃分模型驗(yàn)證。考慮其下轄的B，C，D 3個(gè)主要廠在承運(yùn)商數(shù)量、客戶訂單分布、生產(chǎn)品規(guī)類型等多種因素上的差異，為更全面體現(xiàn)本文模型有效性，分別對(duì)3廠的標(biāo)段劃分進(jìn)行分析。同時(shí)考慮新舊標(biāo)段劃分前后對(duì)數(shù)據(jù)的影響，采用3廠數(shù)最近1次標(biāo)段劃分前后的歷史數(shù)據(jù)進(jìn)行實(shí)際案例分析。根據(jù)上文標(biāo)段數(shù)的分析結(jié)論，本文以（k+1）的形式將3廠的省外承運(yùn)區(qū)域分別劃分為6，5，2個(gè)標(biāo)段，在此基礎(chǔ)上進(jìn)行模型優(yōu)化方案計(jì)算。此外，考慮到在模型優(yōu)化方案中，同一標(biāo)段內(nèi)的城市分布較為分散，難以進(jìn)行統(tǒng)一組織管理，因此本文進(jìn)一步將同一省份內(nèi)的城市集中劃分。具體而言，是指增加片狀約束，犧牲一定程度的訂單量均衡約束，對(duì)可行解進(jìn)行篩選，從而提高同一標(biāo)段內(nèi)城市的鄰接程度，最終獲得進(jìn)化方案。

最后，本文采用Matlab軟件，對(duì)論文提出的標(biāo)段劃分算法進(jìn)行編程實(shí)現(xiàn)，對(duì)A中煙公司3個(gè)卷煙廠承運(yùn)標(biāo)段現(xiàn)行方案、對(duì)照組方案和進(jìn)化方案的目標(biāo)函數(shù)進(jìn)行對(duì)比；同時(shí)，引入標(biāo)段間訂單量的方差、標(biāo)準(zhǔn)差值，以評(píng)估方案的均衡性，檢驗(yàn)?zāi)Ｐ团c算法的科學(xué)和有效性。

3.1 B廠

（1）現(xiàn)行方案。由圖4(a)可以發(fā)現(xiàn)，B廠現(xiàn)行方案共12個(gè)標(biāo)段，各標(biāo)段以省域劃分為主，部分省份被割裂到不同的標(biāo)段，但仍然集中于鄰接的2至3個(gè)標(biāo)段內(nèi)。

（2）對(duì)照組方案。B廠對(duì)照組方案中絕大多數(shù)城市被劃分到同一個(gè)標(biāo)段，只有個(gè)別城市被劃分到其余3個(gè)標(biāo)段，目標(biāo)函數(shù)值較為優(yōu)秀，但由于缺少了訂單均衡約束，該方案各標(biāo)段之間訂單量不均衡極為嚴(yán)重。

（3）進(jìn)化方案。由圖4(b)可以發(fā)現(xiàn)，B廠進(jìn)化方案將省外城市劃分為6個(gè)標(biāo)段，以片狀劃分為主。同一省內(nèi)城市被分到不同標(biāo)段的情況較少，各承運(yùn)商可基于其自身運(yùn)輸優(yōu)勢(shì)和熟悉程度進(jìn)行投標(biāo)，形成承運(yùn)商間的良性競(jìng)爭(zhēng)，也提升了通過(guò)拼車降低運(yùn)輸成本的可能性。

圖4 (a) B廠現(xiàn)行標(biāo)段劃分方案 (12個(gè)標(biāo)段)

Fig.4(a) Current scheme of B manufacturer (12 sections)

圖4 (b) B廠進(jìn)化后標(biāo)段劃分方案 (6個(gè)標(biāo)段)

Fig.4(b) B vendor evolution scheme (6 sections)

（4）方案對(duì)比。將B廠各方案目標(biāo)函數(shù)值、方差、標(biāo)準(zhǔn)差進(jìn)行比較，如表1所示。

表1 B廠三種標(biāo)段劃分方案結(jié)果對(duì)比

Tab.1 Comparison of the results of the three section division schemes of B vendor solutions

由表中數(shù)據(jù)可得，進(jìn)化方案與現(xiàn)行方案相比，在目標(biāo)函數(shù)上降低了21.90%，可見(jiàn)經(jīng)模型優(yōu)化的方案使運(yùn)輸?shù)目偩嚯x明顯減少，而方差，標(biāo)準(zhǔn)差有所增加，這是因?yàn)檫M(jìn)化方案在提高方案實(shí)用性時(shí)犧牲了部分訂單量均衡。另一方面，進(jìn)化方案與對(duì)照組方案相比，在目標(biāo)函數(shù)上增加了20.80%，但在方差和標(biāo)準(zhǔn)差方面明顯較少，相比之下分別降低了94.50%，76.54%?？傮w來(lái)說(shuō)，進(jìn)化方案遍歷全部城市的行程距離較對(duì)照組方案有一定差距，但相比現(xiàn)行方案得到了較好改善。

3.2 C廠

（1）現(xiàn)行方案。由圖5(a)可以發(fā)現(xiàn)，C廠現(xiàn)行方案分為7個(gè)標(biāo)段，也以省級(jí)行政單位的地理邊界作為主要的劃分依據(jù)，各標(biāo)段呈現(xiàn)片狀分布，有較為明顯的地域分界線，幾乎沒(méi)有出現(xiàn)標(biāo)段之間相互交叉的現(xiàn)象。

（2）對(duì)照組方案。C廠對(duì)照組方案將絕大多數(shù)城市劃分至同一標(biāo)段，余下的數(shù)個(gè)城市被劃分為3個(gè)標(biāo)段。

（3）進(jìn)化方案。由圖5(b)可以發(fā)現(xiàn)，C廠進(jìn)化方案片狀結(jié)構(gòu)明顯，主要圍繞C發(fā)散分布，同一省內(nèi)城市被拆出的情況較少，各標(biāo)段內(nèi)的城市鄰接性良好，提高了拼車可能性。同時(shí)目標(biāo)函數(shù)結(jié)果下降，進(jìn)一步降低了運(yùn)輸成本。

圖5 (a) C廠現(xiàn)行標(biāo)段劃分方案 (7個(gè)標(biāo)段)

Fig.5(a) Current scheme of C manufacturer (7 sections)

Fig.5(b) C vendor evolution scheme (5 sections)

（4）方案對(duì)比。將C廠各方案目標(biāo)函數(shù)值、方差、標(biāo)準(zhǔn)差進(jìn)行比較，如表2所示。

表2 C廠三種標(biāo)段劃分方案結(jié)果對(duì)比

Tab.2 Comparison of the results of the three section division schemes of C vendor solutions

由表中數(shù)據(jù)可得，進(jìn)化方案與現(xiàn)行方案相比，在目標(biāo)函數(shù)上降低了5.50%，在方差上降低了97.69%，在標(biāo)準(zhǔn)差上降低了84.79%，可見(jiàn)在訂單量均衡方面有明顯的改善。另外，進(jìn)化方案與對(duì)照組方案相比，目標(biāo)函數(shù)增加了8.77%，在方差上降低了99.99%，在標(biāo)準(zhǔn)差上降低了99.07%，但訂單量更加均衡。綜上所述，進(jìn)化方案相比現(xiàn)行方案不僅在目標(biāo)函數(shù)有一定提升，且其訂單量分布更為均衡。

3.3 D廠

（1）現(xiàn)行方案。D廠現(xiàn)行方案將全部城市劃分為2個(gè)標(biāo)段，從圖6(a)可以看出，南北兩標(biāo)段基本不交叉，以省域劃分為主，有明顯的地理分界線。

（2）對(duì)照組方案?？紤]到目前D廠實(shí)際只有1個(gè)承運(yùn)商，結(jié)合標(biāo)段數(shù)探究結(jié)論，故D廠對(duì)照組方案是將所有城市劃分為1個(gè)標(biāo)段，不需要再考慮訂單量的約束，此時(shí)拼車的可能性最大，目標(biāo)函數(shù)達(dá)到最小。

（3）進(jìn)化方案。由圖6(b)可知，D廠進(jìn)化方案將城市劃分成南北兩部分，2個(gè)標(biāo)段輪廓明顯，增加了方案的實(shí)用性。

圖6 (a) D廠現(xiàn)行標(biāo)段劃分方案 (2個(gè)標(biāo)段)

Fig.6(a) Current scheme of D manufacturer (2 sections)

圖6 (b) D廠進(jìn)化后標(biāo)段劃分方案 (2個(gè)標(biāo)段)

Fig.6(b) D vendor evolution scheme (2 sections)

（4）方案對(duì)比。將D廠各方案目標(biāo)函數(shù)值、方差、標(biāo)準(zhǔn)差進(jìn)行比較，如表3所示。

表3 D廠三種標(biāo)段劃分方案結(jié)果對(duì)比

Tab.3 Comparison of the results of the three section division schemes of D vendor solutions

經(jīng)過(guò)對(duì)比可以發(fā)現(xiàn)，現(xiàn)行方案和進(jìn)化方案在目標(biāo)函數(shù)方面相差不大，但進(jìn)化方案比現(xiàn)有方案的方差、標(biāo)準(zhǔn)差分別降低了71.78%和46.88%，訂單量更加均衡，并且各標(biāo)段的輪廓分割更加明顯。

值得注意的是，本文提出的模型求解方案采用了雙層優(yōu)化算法，平均計(jì)算耗時(shí)（20 min以內(nèi)）隨標(biāo)段數(shù)的增加而增加?？紤]標(biāo)段劃分為長(zhǎng)期戰(zhàn)略性決策，一般2年重新制定1次，該計(jì)算耗時(shí)在可接受范圍內(nèi)。同時(shí)考慮到國(guó)內(nèi)標(biāo)段劃分場(chǎng)景需求眾多，本文研究成果具有較高推廣應(yīng)用價(jià)值。

本文提出的卷煙承運(yùn)標(biāo)段劃分研究方法具有一定靈活性和普適性，不僅適用目前A中煙公司物流配送網(wǎng)絡(luò)，也可拓展應(yīng)用到其它中煙物流網(wǎng)絡(luò)。如目前中煙物流配送有在重要樞紐節(jié)點(diǎn)上建立區(qū)域集散中心，針對(duì)此類物流網(wǎng)絡(luò)可在應(yīng)用本文所提雙層算法時(shí)，將網(wǎng)絡(luò)中的區(qū)域中心倉(cāng)固定為聚類算法中的初始質(zhì)心，并使其在算法的演變過(guò)程中保持不變。

4 結(jié)論

經(jīng)過(guò)本文的研究，在卷煙承運(yùn)標(biāo)段劃分上取得了較為顯著的成果：

構(gòu)建了標(biāo)段劃分模型，基于實(shí)際情況對(duì)理論模型不斷優(yōu)化調(diào)整，實(shí)現(xiàn)了理論研究到實(shí)際應(yīng)用的有效轉(zhuǎn)化，并且為標(biāo)段劃分方案提供了評(píng)價(jià)標(biāo)準(zhǔn)。

（1）形成最終優(yōu)化方案，目前已直接應(yīng)用于A中煙公司2019年度的運(yùn)輸服務(wù)招標(biāo)文件當(dāng)中，相比現(xiàn)行方案，模型目標(biāo)函數(shù)改善明顯，訂單均衡也存在一定改善。

（2）標(biāo)段優(yōu)化后不僅給管理帶來(lái)便捷，同時(shí)也提高了拼車可能性，有利于供需雙方降低運(yùn)輸成本，創(chuàng)造了社會(huì)價(jià)值，具體經(jīng)濟(jì)效益將在下一運(yùn)輸服務(wù)年度得到驗(yàn)證，預(yù)計(jì)全年卷煙運(yùn)輸費(fèi)用下降1～2個(gè)百分點(diǎn)。

（3）標(biāo)段劃分在國(guó)內(nèi)外相關(guān)領(lǐng)域研究較少，本文具有較高的創(chuàng)新性，且具有一定的通用性，在行業(yè)范圍內(nèi)有較高的推廣價(jià)值。

[1] 劉璐峰. 淺談卷煙市場(chǎng)化取向改革中消費(fèi)者信息采集的重要性與方法[J]. 中國(guó)市場(chǎng)，2018(31): 135+142.

LIU Lufeng. On the importance and method of consumer information collection in the reform of cigarette marketization orientation[J]. China Market journal, 2018(31): 135+142

[2] 陳權(quán). XX中煙卷煙物流在途信息系統(tǒng)的規(guī)劃[D]. 南京理工大學(xué)，2014.

CHEN Quan. Planning of in-transit Information System for XX Chinese Cigarette Logistics[D]. Nan Jing University of Technology, 2014.

[3] 何夢(mèng)軍，吳懷崗，丁翔. 帶時(shí)間窗的同城物流配送區(qū)域劃分與路徑優(yōu)化[J]. 南京師范大學(xué)學(xué)報(bào)（工程技術(shù)版），2018, 18(02): 70-76.

HE Mengjun, WU Huaigang, DING Xiang. Division and Path Optimization of intra-city logistics distribution area with time window[J]. Journal of Ning Jing Normal University (Engineering & Technology Edition), 2016,18(02): 70-76.

[4] 王勇，毛海軍，劉靜. 帶時(shí)間窗的物流配送區(qū)域劃分模型及其算法[J]. 東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2010, 40(05): 1077-1083.

WANG Yong, MAO Haijun, LIU Jing. The model and algorithm of logistics distribution area division with time window[J]. Journal of southeast university (natural science edition), 2010, 40(05): 1077-1083.

[5] 袁慶達(dá)，杜文，周再玲. 帶軟時(shí)間窗的混合車隊(duì)車輛路線問(wèn)題的模型和算法研究[J]. 西南交通大學(xué)學(xué)報(bào)，2001, 36(4): 401-406.

YUAN Qingda, DU Wen, ZHOU Zailing. Research on Model and Algorithm for Vehicle Routing Problem of Hybrid Fleet with Soft Time Window[J]. Journal of Southwest Jiaotong University, 2001, 36 (4): 401-406.

[6] 施國(guó)洪，張慶汶，徐森. 區(qū)域網(wǎng)絡(luò)零售商物流配送網(wǎng)絡(luò)規(guī)劃研究[J]. 科技與管理，2011, 13(02): 82-85.

SHI Guohong, ZHANG Qingwen, XU Sen.Research on logistics distribution network planning of regional network retailers[J]. Science Technology and Management, 2011, 13 (02): 82-85.

[7] K Ganesh, T Narendran. Cloves:a cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up[J]. European Journal of Operational Research, 2007, 178(3): 699-717.

[8] WANG Y, MA X, LAO Y. A fuzzy-based customer clustering approach with hierarchical structure for logistics network optimization[J]. Expert Systems with Applications, 2014, 41(2): 521-534.

[9] N. Christofides. Fixed routes and areas for delivery operations[J]. International Journal of Physical Distribution and Logistics Management, 2013, 1(2): 87-92.

[10] WANG Y, MA X, XU M, et al. Two-echelon logistics distribution region partitioning problem based on a hybrid particle swarm optimization-genetic algorithm[J]. Expert Systems with Applications, 2015, 42(12): 5019-5031.

[11] D. Sacramento, D. Pisinger and S. Ropke. An adaptive large neighborhood search Metaheuristic for the vehicle routing problem with drones[J]. Transportation Research Part C: Emerging Technologies, 2019, 102(00): 289-315.

[12] D. M. Miranda, R. S. de Camargo, S. V. Concei?ao, M. F. Porto and N. T. R. Nunes. A multi-loading school bus routing problem[J]. Expert Systems with Applications, 2018, 101(00): 228-242.

[13] S. Yuan, B. Skinner, S. Huang and D. Liu. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms [J]. European Journal Of Operational Research, 2013, 228(1): 72-82.

[14] 謝繼超. 卷煙區(qū)域物流網(wǎng)絡(luò)布局優(yōu)化研究[D]. 山東大學(xué)，2013.

XIE Jichao. Study on Optimization of Cigarette regional Logistics Network Layout[D]. Shandong University, 2013.

[15] Helsgaun K . An effective implementation of the Lin–Kernighan traveling salesman heuristic[J]. European Journal of Operational Research, 2000, 126(1): 106-130.

Study on the Model of Cigarette Transportation Segment Division

ZHUANG Wenjie, ZOU Xiangyu, SUN Qingping, LIU Jia*

China Tobacco Jiangsu Industrial Co, LTD, Nanjing 210011, China

In the face of the trend of high-frequency cigarette demands, small batch sizes, and fragmented orders, a rational transportation segment division is not only conducive to balancing the actual income of each carrier, but also improves the possibility of carpooling and stowage, thus reducing the transportation cost. This paper establishes a model with the objective of minimizing the total traversing distance within all segments. On this basis, a two-tier algorithm is proposed to solve the model. The upper layer adopts clustering method to obtain the initial solution with high feasibility; the lower layer optimizes the initial solution iteratively based on edge-exchange algorithms to approach an optimal solution. Finally, taking Company A as an example and based on its order volume historical data from the recent two years, a case study is conducted to verify the effectiveness of the proposed model and solution method.

cigarette distribution; division of tender sections; two-tier optimization algorithm

Corresponding author. Email：liujia@jszygs.com

莊文杰（1985—），碩士研究生，主要研究方向：物流信息化、倉(cāng)儲(chǔ)信息化，Tel：13770636621，Email：zhuangwj@jszygs.com

劉嘉（1980—），碩士研究生，工程師，主要研究方向：供應(yīng)鏈物流管理、智能化、互聯(lián)網(wǎng)+技術(shù)，Tel：13770682996，Email：liujia@jszygs.com

2020-12-31；

2023-08-31

莊文杰，鄒翔宇，孫慶平，劉嘉. 卷煙承運(yùn)標(biāo)段劃分模型研究[J]. 中國(guó)煙草學(xué)報(bào)，2023，29（5）. ZHUANG Wenjie,ZOU Xiangyu,SUN Qingping,et al. Study on the partition model of cigarette carrier tender section[J]. Acta Tabacaria Sinica,2023,29(5). doi:10.16472/j.chinatobacco.2020.T0127