卷烟承运标段划分模型研究

庄文杰，邹翔宇，孙庆平，刘嘉

卷烟承运标段划分模型研究

庄文杰，邹翔宇，孙庆平，刘嘉*

江苏中烟工业有限责任公司，南京 210011

面对卷烟需求频次高、批量小，订单碎片化的趋势，合理的承运标段划分方法不仅有利于平衡各承运商的实际收益，也有利于提高拼车配载的可能性，从而降低运输成本。本文以最小化全部标段内部的需求点遍历路程之和为优化目标建立模型。在此基础上，本文提出了一种双层算法对模型进行求解，上层采用聚类方法获取具有较高可行性的初始解；下层基于边缘交换算法通过迭代对初始解进行优化，从而得到近似最优解。最后，本文以A中烟公司为例，在其近两年的订单量历史数据基础上进行了案例分析，验证了所提出模型与解决方法的有效性。

卷烟配送；标段划分；双层优化算法

随着卷烟营销市场化取向改革的深入推进，商业公司要货频次高、批量小，订单碎片化趋势越来越明显，因此，迫切需要对承运标段划分方法进行深入研究[1]。充分考虑各标段发货订单量均衡及拼车配载的可能性，不仅能够降低供需双方运输成本，调动承运商积极性，保证卷烟发货高效完成，同时有利于提升承运商整体运作水平，实现资源的合理配置，进而实现整个物流网络的优化。

目前A中烟公司向全国300多家商业公司供货，省外地区销售比例超过50%，物流运输存在点多、面广、线长的特点，运输费用占物流总费用比例较高[2]。A中烟公司现行卷烟承运标段主要依托于省域分界进行划分，运输网络中的各个标段订单量不均衡、缺少科学合理的路线规划，造成资源浪费，存在运输成本偏高并且效率偏低的问题。

国内外学者对标段划分方面的研究，大多集中在物流配送区域划分方面，通过对配送过程中车辆路径的合理的规划，以降低企业的运输成本，提高物料配送的效率和及时性。由于该问题为一个多约束复杂决策的NP-hard组合优化问题，许多学者在构建模型和提升算法精度方面做了一定工作。何梦军等[3]以最短配送时间为目标，构建了带时间窗的非线性数学规划模型，同步解决区域划分与配送路径优化问题。王勇等[4]将时滞成本纳入研究范围，以网络总成本最小化为目标函数构建模型，并提出一种改进粒子群-遗传混合算法获取最优标段划分方案；袁庆达等[5]考虑了软时间窗和混合车队问题，基于Tabu search算法设计了GENIUS两阶段启发式算法。施国洪等[6]在研究区域网络零售商物流配送问题中提出了基于聚类改进两阶段启发式算法，第一阶段采用聚类算法，并在第二阶段运用遗传算法进行求解。国外学者多采用基于聚类或启发式方法对物料配送区域划分进行研究。Ganesh等[7]通过建立评价指标体系，生成模糊关系矩阵，运用模糊数学中的理论进行物流配送点聚类研究。Wang等[8]对顾客进行了聚类研究，通过模糊聚类算法划分配送区域。通过对顾客进行聚类分析，达到降低配送网络复杂性的效果，便于进行配送路径优化。Christofides[9]通过将配送区域网格化为大小不均等的正方形区域，区域内需求视为单个需求点，其需求量为区域内需求量总和，区域中心坐标作为区域点坐标，依据不同正方形区域的历史路径连接频率将各正方形区域聚合为配送单元。Wang等[10]建立物流配送分区模型以最小化双层级物流网络总成本，并提出扩展的混合粒子群遗传算法进行求解。本文研究思路将该问题转换为一种特殊的多旅行商问题，每个区域配送的承运商可视为一个旅行商，通过引入区域内订单均衡的特殊约束，来实现物流配送区域的最优划分。多旅行商问题多采用元启发式算法进行求解，如Sacramento等[11]研究了无人机和卡车协作的多旅行商问题，建立了以时间限制和成本最小化的数学模型，设计自适应大型邻域搜索元启发式算法。Miranda等[12]研究了混合负载的校车路线问题，通过将迭代局部搜索和特殊邻域结构结合的多负载优化方法，降低该问题的计算代价。Yuan等[13]针对多旅行商问题提出了一种新的两部分染色体交叉算子，并验证基于该算法求解多旅行商问题的有效性。

卷烟承运标段划分在烟草公司主要采用基于省域或者片区的经验划分方法，易于管理，标段轮廓明确。有学者[14-15]研究了烟草配送中转站的选址，在此基础上考虑固定成本与变动成本，建立物流配送区域划分数学规划模型。但随时需求碎片化和外部形势的变化，传统划分方法存在的运输资源浪费的劣势不断凸显。本文考虑订单量分配要求，承运商收益平衡要求等现实约束，研究基于运输里程、订单量分配来支撑更合理的量化标段划分方法。主要研究如何在订单量均衡（承运商利益基本均衡）约束下，尽可能地提高卷烟拼车配载运输的可能性。着重采用科学的数学建模与求解方法，进行承运标段划分。主要的研究目标包括以下4个方面：一是研究探索合理的标段划分数目，形成理论依据；二是实现各个标段内订单量基本均衡，各承运商的收益基本平衡；三是提高拼车发货的可能性，有效降低运输成本，实现双方共赢；四是同标段内的城市尽可能集中分布，降低物流网络的复杂度，为智能运输调度奠定基础。

1 模型构建

本文以卷烟厂位置为起点，各标段对其内部商业公司所在城市进行遍历且最后回到卷烟厂所在位置，当所经过的总路程达到最小时，此时的标段划分达到最优，拼车配载的可行性最高。

1.1 参数

厂商所服务的城市集合（单位：个）

厂商服务全部城市的订单总量（单位：件）

厂商服务城市集合（单位：个）

m 城市的订单量为m（单位：件）

标段集合（单位：个）

标段数量（单位：个）

C标段包含的城市集合（单位：个）

N 标段包含的城市数（单位：个）

[] 城市间邻接矩阵（单位：无）

d邻接矩阵中城市到城市的距离（单位：公里）

1.2 变量

θ若θ=1，则表示从城市出发前往城市；反之，若θ=0，表示未从城市出发前往城市

1.3 目标函数

为了尽可能提高同一标段内城市运输任务的拼车可能性，优化目标设置为最小化全部标段内部的路程之和。

1.4 约束条件

其中，公式（2）确保标段内的城市之和等于需求点城市总数；公式（3）确保每个城市只属于一个标段；公式（2）和（3）共同构成了城市的全覆盖约束；公式（4）确保满足全部订单量运输任务；公式（5）确保节点访问的进出流量平衡，即任意城市商业公司的访问次数等于该商业公司的驶出次数；公式（6）中a，b为系数，控制标段订单量阈值。该阈值设定目的为确保各个标段订单量相对均衡，且在招标时对承运商产生一定差异化竞争，可结合各招标单位自身情况设置。本文中通过对A中烟公司的专家调研，最终设置为a=0.85，b=1.1。

2 算法设计

由于本文研究的标段划分问题是NP-hard问题，研究表明该类问题无法在有效时间内获取最优解。因此，为客观评价标段划分方案的优劣程度，本文基于两种方案进行标段划分优化设计。一是对照组方案，不考虑订单量约束，计算得出理论最优目标函数值；二是模型优化方案，加入订单量约束条件，设计了双层算法并进行求解。由于对照组方案去除了订单量约束，其取值实质为带订单约束问题的数值下界，可用以评估优化方案解的优劣程度。

2.1 对照组方案（无订单量约束）

在不考虑订单量约束的情况下，设置优化目标为：在遍历全部商业公司城市的条件下，最小化全部承运商的总行程距离[8]。求解具体步骤如下：

Step1：标段数为k，则在N个城市的基础上，增加（k-1）个与起点重叠的虚拟起点（虚拟起点之间的距离设为无穷）。

Step2：构建含（N+k）个点的邻接矩阵，基于Dijkstra算法得最短距离矩阵。

Step3：求解目标函数值。

Step4：求解后，相邻两起点之间经过的城市划分为1个标段，依此类推。

2.2 模型优化方案（有订单量约束）

采用双层算法进行有订单量约束的标段划分：上层采用聚类方法获取具有较高可行性的初始解；下层基于边缘交换算法通过迭代对初始解进行优化，从而得到近似最优解。

（1）上层算法。基于卷烟厂商到各商业公司所在城市的最短路径矩阵对城市进行聚类，以提升其拼车概率。步骤如下：

Step1：基于Dijkstra算法（最短路径算法）获取从卷烟厂商出发到全部发货城市的最短路径矩阵。

Step2：根据以城市为节点的最短路径，将全部城市按照k个簇进行聚类。

Step2.1：随机选取k个城市作为初始聚类中心；

Step2.2：计算每个城市到k个中心的距离，并将该城市分配至与中心距离最小的簇中；

Step2.3：重新计算当前每个簇的中心，如果中心位置不再移动，则结束迭代，否则重复Step2.2和Step2.3。

（2）下层算法。边缘交换算法属于局部搜索算法，是解决组合优化问题的有效工具，如今已经广为人知并且在组合优化领域中得到了广泛的应用[9-10]。下层算法对初始解进行优化，考虑到初始解可能存在的局限性，所以在交换操作基础上，增加了移动操作。步骤如下：

Step1：针对初始方案计算其目标函数，记录为当前最优解T0，当前迭代次数t=0。

Step3：第t次迭代开始，随机执行移动操作或者交换操作的优化算子，具体如下；

Step5：检验当前目标函数值T，若T＜T0，则更新为当前最优解，T0=T，并重新进入Step3；反之，拒绝该操作，直接重新进入Step4。

Step6：依此类推，直到达到终止条件，输出最终解即为模型优化方案。

图1 邻接标段间的移动操作

图2 邻接标段间的交换操作

2.3 最优标段数探索

在进行标段划分方案计算时，首先需确定在可接受范围内的最优标段数。为探索标段数的普适性规律，本文以A中烟公司B厂为例，根据其近两年（2016年4月—2017年12月）的订单量数据及产品需求终点的分布情况，对其最优标段数进行探究。

图3 目标函数变化趋势对比（横坐标代表标段数单位，纵坐标代表距离目标函数）

经过本文的探索，由图3可以发现：对于对照组和模型最优方案，当标段数从10增加到20过程中，目标函数均随之增大，而标段数为1即不划分标段时，目标函数取得最小值。从理论上而言，当全部城市划为一个标段时，拼车可能性最大，该结论也与A中烟公司的历史配送经验相符合。

基于此，本文提出：为了促进承运商之间的良好竞争，可以根据现有承运商数量k，将标段数设置为（k+1）的形式。如此，一方面可以符合实际需求，另一方面也在理论上可尽可能地提高卷烟运输拼车可能性。

3 案例分析

为了验证所提出的卷烟标段划分方法的有效性，本文以A中烟公司为例进行标段划分模型验证。考虑其下辖的B，C，D 3个主要厂在承运商数量、客户订单分布、生产品规类型等多种因素上的差异，为更全面体现本文模型有效性，分别对3厂的标段划分进行分析。同时考虑新旧标段划分前后对数据的影响，采用3厂数最近1次标段划分前后的历史数据进行实际案例分析。根据上文标段数的分析结论，本文以（k+1）的形式将3厂的省外承运区域分别划分为6，5，2个标段，在此基础上进行模型优化方案计算。此外，考虑到在模型优化方案中，同一标段内的城市分布较为分散，难以进行统一组织管理，因此本文进一步将同一省份内的城市集中划分。具体而言，是指增加片状约束，牺牲一定程度的订单量均衡约束，对可行解进行筛选，从而提高同一标段内城市的邻接程度，最终获得进化方案。

最后，本文采用Matlab软件，对论文提出的标段划分算法进行编程实现，对A中烟公司3个卷烟厂承运标段现行方案、对照组方案和进化方案的目标函数进行对比；同时，引入标段间订单量的方差、标准差值，以评估方案的均衡性，检验模型与算法的科学和有效性。

3.1 B厂

（1）现行方案。由图4(a)可以发现，B厂现行方案共12个标段，各标段以省域划分为主，部分省份被割裂到不同的标段，但仍然集中于邻接的2至3个标段内。

（2）对照组方案。B厂对照组方案中绝大多数城市被划分到同一个标段，只有个别城市被划分到其余3个标段，目标函数值较为优秀，但由于缺少了订单均衡约束，该方案各标段之间订单量不均衡极为严重。

（3）进化方案。由图4(b)可以发现，B厂进化方案将省外城市划分为6个标段，以片状划分为主。同一省内城市被分到不同标段的情况较少，各承运商可基于其自身运输优势和熟悉程度进行投标，形成承运商间的良性竞争，也提升了通过拼车降低运输成本的可能性。

图4 (a) B厂现行标段划分方案 (12个标段)

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

图4 (b) B厂进化后标段划分方案 (6个标段)

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

（4）方案对比。将B厂各方案目标函数值、方差、标准差进行比较，如表1所示。

表1 B厂三种标段划分方案结果对比

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

由表中数据可得，进化方案与现行方案相比，在目标函数上降低了21.90%，可见经模型优化的方案使运输的总距离明显减少，而方差，标准差有所增加，这是因为进化方案在提高方案实用性时牺牲了部分订单量均衡。另一方面，进化方案与对照组方案相比，在目标函数上增加了20.80%，但在方差和标准差方面明显较少，相比之下分别降低了94.50%，76.54%。总体来说，进化方案遍历全部城市的行程距离较对照组方案有一定差距，但相比现行方案得到了较好改善。

3.2 C厂

（1）现行方案。由图5(a)可以发现，C厂现行方案分为7个标段，也以省级行政单位的地理边界作为主要的划分依据，各标段呈现片状分布，有较为明显的地域分界线，几乎没有出现标段之间相互交叉的现象。

（2）对照组方案。C厂对照组方案将绝大多数城市划分至同一标段，余下的数个城市被划分为3个标段。

（3）进化方案。由图5(b)可以发现，C厂进化方案片状结构明显，主要围绕C发散分布，同一省内城市被拆出的情况较少，各标段内的城市邻接性良好，提高了拼车可能性。同时目标函数结果下降，进一步降低了运输成本。

图5 (a) C厂现行标段划分方案 (7个标段)

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

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

（4）方案对比。将C厂各方案目标函数值、方差、标准差进行比较，如表2所示。

表2 C厂三种标段划分方案结果对比

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

由表中数据可得，进化方案与现行方案相比，在目标函数上降低了5.50%，在方差上降低了97.69%，在标准差上降低了84.79%，可见在订单量均衡方面有明显的改善。另外，进化方案与对照组方案相比，目标函数增加了8.77%，在方差上降低了99.99%，在标准差上降低了99.07%，但订单量更加均衡。综上所述，进化方案相比现行方案不仅在目标函数有一定提升，且其订单量分布更为均衡。

3.3 D厂

（1）现行方案。D厂现行方案将全部城市划分为2个标段，从图6(a)可以看出，南北两标段基本不交叉，以省域划分为主，有明显的地理分界线。

（2）对照组方案。考虑到目前D厂实际只有1个承运商，结合标段数探究结论，故D厂对照组方案是将所有城市划分为1个标段，不需要再考虑订单量的约束，此时拼车的可能性最大，目标函数达到最小。

（3）进化方案。由图6(b)可知，D厂进化方案将城市划分成南北两部分，2个标段轮廓明显，增加了方案的实用性。

图6 (a) D厂现行标段划分方案 (2个标段)

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

图6 (b) D厂进化后标段划分方案 (2个标段)

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

（4）方案对比。将D厂各方案目标函数值、方差、标准差进行比较，如表3所示。

表3 D厂三种标段划分方案结果对比

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

经过对比可以发现，现行方案和进化方案在目标函数方面相差不大，但进化方案比现有方案的方差、标准差分别降低了71.78%和46.88%，订单量更加均衡，并且各标段的轮廓分割更加明显。

值得注意的是，本文提出的模型求解方案采用了双层优化算法，平均计算耗时（20 min以内）随标段数的增加而增加。考虑标段划分为长期战略性决策，一般2年重新制定1次，该计算耗时在可接受范围内。同时考虑到国内标段划分场景需求众多，本文研究成果具有较高推广应用价值。

本文提出的卷烟承运标段划分研究方法具有一定灵活性和普适性，不仅适用目前A中烟公司物流配送网络，也可拓展应用到其它中烟物流网络。如目前中烟物流配送有在重要枢纽节点上建立区域集散中心，针对此类物流网络可在应用本文所提双层算法时，将网络中的区域中心仓固定为聚类算法中的初始质心，并使其在算法的演变过程中保持不变。

4 结论

经过本文的研究，在卷烟承运标段划分上取得了较为显著的成果：

构建了标段划分模型，基于实际情况对理论模型不断优化调整，实现了理论研究到实际应用的有效转化，并且为标段划分方案提供了评价标准。

（1）形成最终优化方案，目前已直接应用于A中烟公司2019年度的运输服务招标文件当中，相比现行方案，模型目标函数改善明显，订单均衡也存在一定改善。

（2）标段优化后不仅给管理带来便捷，同时也提高了拼车可能性，有利于供需双方降低运输成本，创造了社会价值，具体经济效益将在下一运输服务年度得到验证，预计全年卷烟运输费用下降1～2个百分点。

（3）标段划分在国内外相关领域研究较少，本文具有较高的创新性，且具有一定的通用性，在行业范围内有较高的推广价值。

[1] 刘璐峰. 浅谈卷烟市场化取向改革中消费者信息采集的重要性与方法[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] 陈权. XX中烟卷烟物流在途信息系统的规划[D]. 南京理工大学，2014.

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

[3] 何梦军，吴怀岗，丁翔. 带时间窗的同城物流配送区域划分与路径优化[J]. 南京师范大学学报（工程技术版），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] 王勇，毛海军，刘静. 带时间窗的物流配送区域划分模型及其算法[J]. 东南大学学报（自然科学版），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] 袁庆达，杜文，周再玲. 带软时间窗的混合车队车辆路线问题的模型和算法研究[J]. 西南交通大学学报，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] 施国洪，张庆汶，徐森. 区域网络零售商物流配送网络规划研究[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] 谢继超. 卷烟区域物流网络布局优化研究[D]. 山东大学，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—），硕士研究生，工程师，主要研究方向：供应链物流管理、智能化、互联网+技术，Tel：13770682996，Email：liujia@jszygs.com

2020-12-31；

2023-08-31

庄文杰，邹翔宇，孙庆平，刘嘉. 卷烟承运标段划分模型研究[J]. 中国烟草学报，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