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

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

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

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

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

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

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

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

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

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

1 模型構(gòu)建

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

1.1 參數(shù)

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

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

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

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

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

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

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

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

[] 城市間鄰接矩陣（單位：無）

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

2 算法設(shè)計

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

2.1 對照組方案（無訂單量約束）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step5：檢驗當(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)段間的移動操作

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

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

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

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

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

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

3 案例分析

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

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

3.1 B廠

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

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

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

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

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

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

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

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

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

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

3.2 C廠

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

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

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

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

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

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

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

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

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%，可見在訂單量均衡方面有明顯的改善。另外，進(jìn)化方案與對照組方案相比，目標(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個標(biāo)段，從圖6(a)可以看出，南北兩標(biāo)段基本不交叉，以省域劃分為主，有明顯的地理分界線。

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

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

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

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

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

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

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

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

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

經(jīng)過對比可以發(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)化算法，平均計算耗時（20 min以內(nèi)）隨標(biāo)段數(shù)的增加而增加?？紤]標(biāo)段劃分為長期戰(zhàn)略性決策，一般2年重新制定1次，該計算耗時在可接受范圍內(nèi)。同時考慮到國內(nèi)標(biāo)段劃分場景需求眾多，本文研究成果具有較高推廣應(yīng)用價值。

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

4 結(jié)論

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

構(gòu)建了標(biāo)段劃分模型，基于實際情況對理論模型不斷優(yōu)化調(diào)整，實現(xiàn)了理論研究到實際應(yīng)用的有效轉(zhuǎn)化，并且為標(biāo)段劃分方案提供了評價標(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)化后不僅給管理帶來便捷，同時也提高了拼車可能性，有利于供需雙方降低運(yùn)輸成本，創(chuàng)造了社會價值，具體經(jīng)濟(jì)效益將在下一運(yùn)輸服務(wù)年度得到驗證，預(yù)計全年卷煙運(yùn)輸費(fèi)用下降1～2個百分點。

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

[1] 劉璐峰. 淺談卷煙市場化取向改革中消費(fèi)者信息采集的重要性與方法[J]. 中國市場，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] 何夢軍，吳懷崗，丁翔. 帶時間窗的同城物流配送區(qū)域劃分與路徑優(yōu)化[J]. 南京師范大學(xué)學(xué)報（工程技術(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] 王勇，毛海軍，劉靜. 帶時間窗的物流配送區(qū)域劃分模型及其算法[J]. 東南大學(xué)學(xué)報（自然科學(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á)，杜文，周再玲. 帶軟時間窗的混合車隊車輛路線問題的模型和算法研究[J]. 西南交通大學(xué)學(xué)報，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] 施國洪，張慶汶，徐森. 區(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—），碩士研究生，主要研究方向：物流信息化、倉儲信息化，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]. 中國煙草學(xué)報，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