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

中国烟草学报 Acta Tabacaria Sinica 2023 Vol.29 No.5 作者简介：庄文杰（1985），硕士研究生，主要研究方向：物流信息化、仓储信息化，Tel：[phone]，Email： 通讯作者：刘嘉（1980），硕士研究生，工程师，主要研究方向：供应链物流管理、智能化、互联网+技术，Tel：[phone]，Email： 收稿日期：2020-12-31；网络出版日期：2023-08-31 112 庄文杰，邹翔宇，孙庆平，刘嘉.卷烟承运标段划分模型研究J.中国烟草学报，2023，29（5）.ZHUANG Wenjie,ZOU Xiangyu,SUN Qingping,et al.Study on the partition model of cigarette carrier tender sectionJ.Acta Tabacaria Sinica,2023,29(5).doi:10.16472/j.chinatobacco.2020.T0127 卷烟承运标段划分模型研究 庄文杰，邹翔宇，孙庆平，刘嘉*江苏中烟工业有限责任公司，南京 210011 摘 要：面对卷烟需求频次高、批量小，订单碎片化的趋势，合理的承运标段划分方法不仅有利于平衡各承运商的实际收益，也有利于提高拼车配载的可能性，从而降低运输成本。本文以最小化全部标段内部的需求点遍历路程之和为优化目标建立模型。在此基础上，本文提出了一种双层算法对模型进行求解，上层采用聚类方法获取具有较高可行性的初始解；下层基于边缘交换算法通过迭代对初始解进行优化，从而得到近似最优解。最后，本文以 A 中烟公司为例，在其近两年的订单量历史数据基础上进行了案例分析，验证了所提出模型与解决方法的有效性。关键词：卷烟配送；标段划分；双层优化算法 随着卷烟营销市场化取向改革的深入推进，商业公司要货频次高、批量小，订单碎片化趋势越来越明显，因此，迫切需要对承运标段划分方法进行深入研究1。充分考虑各标段发货订单量均衡及拼车配载的可能性，不仅能够降低供需双方运输成本，调动承运商积极性，保证卷烟发货高效完成，同时有利于提升承运商整体运作水平，实现资源的合理配置，进而实现整个物流网络的优化。目前 A 中烟公司向全国 300 多家商业公司供货，省外地区销售比例超过 50%，物流运输存在点多、面广、线长的特点，运输费用占物流总费用比例较高2。A 中烟公司现行卷烟承运标段主要依托于省域分界进行划分，运输网络中的各个标段订单量不均衡、缺少科学合理的路线规划，造成资源浪费，存在运输成本偏高并且效率偏低的问题。国内外学者对标段划分方面的研究，大多集中在物流配送区域划分方面，通过对配送过程中车辆路径的合理的规划，以降低企业的运输成本，提高物料配送的效率和及时性。由于该问题为一个多约束复杂决策的 NP-hard 组合优化问题，许多学者在构建模型和提升算法精度方面做了一定工作。何梦军等3以最短配送时间为目标，构建了带时间窗的非线性数学规划模型，同步解决区域划分与配送路径优化问题。王勇等4将时滞成本纳入研究范围，以网络总成本最小化为目标函数构建模型，并提出一种改进粒子群-遗传混合算法获取最优标段划分方案；袁庆达等5考虑了软时间窗和混合车队问题，基于 Tabu search 算法设计了GENIUS 两阶段启发式算法。施国洪等6在研究区域网络零售商物流配送问题中提出了基于聚类改进两阶段启发式算法，第一阶段采用聚类算法，并在第二阶段运用遗传算法进行求解。国外学者多采用基于聚类或启发式方法对物料配送区域划分进行研究。Ganesh等7通过建立评价指标体系，生成模糊关系矩阵，运用模糊数学中的理论进行物流配送点聚类研究。Wang等8对顾客进行了聚类研究，通过模糊聚类算法划分配送区域。通过对顾客进行聚类分析，达到降低配送网络复杂性的效果，便于进行配送路径优化。Christofides9通过将配送区域网格化为大小不均等的正方形区域，区域内需求视为单个需求点，其需求量为区域内需求量总和，区域中心坐标作为区域点坐标，依据不同正方形区域的历史路径连接频率将各正方形区域聚合为配送单元。Wang 等10建立物流配送分区模庄文杰等 卷烟承运标段划分模型研究 113 型以最小化双层级物流网络总成本，并提出扩展的混合粒子群遗传算法进行求解。本文研究思路将该问题转换为一种特殊的多旅行商问题，每个区域配送的承运商可视为一个旅行商，通过引入区域内订单均衡的特殊约束，来实现物流配送区域的最优划分。多旅行商问题多采用元启发式算法进行求解，如 Sacramento等11研究了无人机和卡车协作的多旅行商问题，建立了以时间限制和成本最小化的数学模型，设计自适应大型邻域搜索元启发式算法。Miranda 等12研究了混合负载的校车路线问题，通过将迭代局部搜索和特殊邻域结构结合的多负载优化方法，降低该问题的计算代价。Yuan 等13针对多旅行商问题提出了一种新的两部分染色体交叉算子，并验证基于该算法求解多旅行商问题的有效性。卷烟承运标段划分在烟草公司主要采用基于省域或者片区的经验划分方法，易于管理，标段轮廓明确。有学者14-15研究了烟草配送中转站的选址，在此基础上考虑固定成本与变动成本，建立物流配送区域划分数学规划模型。但随时需求碎片化和外部形势的变化，传统划分方法存在的运输资源浪费的劣势不断凸显。本文考虑订单量分配要求，承运商收益平衡要求等现实约束，研究基于运输里程、订单量分配来支撑更合理的量化标段划分方法。主要研究如何在订单量均衡（承运商利益基本均衡）约束下，尽可能地提高卷烟拼车配载运输的可能性。着重采用科学的数学建模与求解方法，进行承运标段划分。主要的研究目标包括以下 4 个方面：一是研究探索合理的标段划分数目，形成理论依据；二是实现各个标段内订单量基本均衡，各承运商的收益基本平衡；三是提高拼车发货的可能性，有效降低运输成本，实现双方共赢；四是同标段内的城市尽可能集中分布，降低物流网络的复杂度，为智能运输调度奠定基础。1 模型构建 本文以卷烟厂位置为起点，各标段对其内部商业公司所在城市进行遍历且最后回到卷烟厂所在位置，当所经过的总路程达到最小时，此时的标段划分达到最优，拼车配载的可行性最高。1.1 参数 N 厂商所服务的城市集合（单位：个）M 厂商服务全部城市的订单总量（单位：件）J 厂商服务城市集合（单位：个）mj 城市 j 的订单量为 mj（单位：件）I 标段集合（单位：个）k 标段数量（单位：个）Ci 标段 i 包含的城市集合（单位：个）Ni 标段 i 包含的城市数（单位：个）d 城市间邻接矩阵（单位：无）dxy 邻接矩阵中城市 x 到城市 y 的距离（单位：公里）1.2 变量 ij 若1ij=，则表示城市 j 属于标段 i；反之，若0ij=，表示城市 j 不属于标段 i xy 若 xy=1，则表示从城市 x 出发前往城市 y；反之，若 xy=0，表示未从城市 x 出发前往城市 y 1.3 目标函数 为了尽可能提高同一标段内城市运输任务的拼车可能性，优化目标设置为最小化全部标段内部的路程之和。1.4 约束条件()()iixyxyi I x C y CMin TMind=（1）ijj J i IN=（2）1iji I=（3）ijii Ij JmM=（4）xyyzx Jz J=（5）,ixx CMMambabiIkk （6）其中，公式（2）确保标段内的城市之和等于需求点城市总数；公式（3）确保每个城市只属于一个标段；公式（2）和（3）共同构成了城市的全覆盖约束；公式（4）确保满足全部订单量运输任务；公式（5）确保节点访问的进出流量平衡，即任意城市商业公司的访问次数等于该商业公司的驶出次数；公式（6）中 a，b 为系数，控制标段订单量阈值。该阈值设定目的为确保各个标段订单量相对均衡，且在招标时对承运商产生一定差异化竞争，可结合各招标单位自身情况设置。本文中通过对 A 中烟公司的专家调研，最终设置为 a=0.85，b=1.1。中国烟草学报 Acta Tabacaria Sinica 2023 Vol.29 No.5 114 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。Step3：在聚类过程中，检验订单量均衡约束，确保每个簇的订单量之和均满足 0.85Mkixx Cm 1.1,MiIk。（2）下层算法。边缘交换算法属于局部搜索算法，是解决组合优化问题的有效工具，如今已经广为人知并且在组合优化领域中得到了广泛的应用9-10。下层算法对初始解进行优化，考虑到初始解可能存在的局限性，所以在交换操作基础上，增加了移动操作。步骤如下：Step1：针对初始方案计算其目标函数，记录为当前最优解 T0，当前迭代次数 t=0。Step2：初始化 Neighbor list 记录与每一个城市距离最近的 个城市。若该城市 Neighbor list 内存在属于外标段城市点，则此城市界定为边缘城市。Step3：第 t 次迭代开始，随机执行移动操作或者交换操作的优化算子，具体如下；Step3.1：移动优化：通过随机选取标段 内边缘城市集合中订单量小于(1.1-0.85)M 平均的城市，并将该边缘城市移动到其邻接标段中；若该边缘城市有两个及以上邻接标段，则通过外标段 内包含的邻接城市数 ，采用轮盘赌方式选取待移动的新标段，标段 被选中的概率为 =/()，移动优化示意如图 1 所示。Step3.2：交换优化：通过随机选取标段 内边缘城市集合中的城市，搜索该城市邻接标段中订单量相近的城市，进行交换；若该边缘城市有两个及以上邻接标段，同 Step4 移动优化采用轮盘赌的方式选取待交换的新标段，交换优化示意如图 2 所示。令 t=t+1。Step4：检验订单量，若满足 0.85Mkixx Cm1.1,MiIk，则进入 Step5；反之，重新进入 Step3。Step5：检验当前目标函数值 T，若 TT0，则更新为当前最优解，T0=T，并重新进入 Step3；反之，拒绝该操作，直接重新进入 Step4。Step6：依此类推，直到达到终止条件，输出最终解即为模型优化方案。庄文杰等 卷烟承运标段划分模型研究 115 图 1 邻接标段间的移动操作 Fig.1 Movement operation between adjacent sections 图 2 邻接标段间的交换操作 Fig.2 Swap operation between adjacent sections 2.3 最优标段数探索 在进行标段划分方案计算时，首先需确定在可接受范围内的最优标段数。为探索标段数的普适性规律，本文以 A 中烟公司 B 厂为例，根据其近两年（2016年 4 月2017 年 12 月）的订单量数据及产品需求终点的分布情况，对其最优标段数进行探究。图 3 目标函数变化趋势对比（横坐标代表标段数单位，纵坐标代表距离目标函数）Fig.3 Comparison of objective function trends(X-axis represents the number of sections,Y-axis represents the distance objective function)经过本文的探索，由图 3 可以发现：对于对照组和模型最优方案，当标段数从 10 增加到 20 过程中，目标函数均随之增大，而标段数为 1 即不划分标段时，目标函数取得最小值。从理论上而言，当全部城市划为一个标段时，拼车可能性最大，该结论也与 A 中烟公司的历史配送经验相符合。基于此，本文提出：为了促进承运商之间的良好竞争，可以根据现有承运商数量 k，将标段数设置为中国烟草学报 Acta Tabacaria Sinica 2023 Vol.29 No.5 116（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 方案 目标函数 订单量方差 标准差 现行方案（12 标段）76,460,547 678167E+10 260,416 对照组方案 49,435,397 4.02147E+12 2,005,360 进化方案（6 标段）59,718,519 2.21364E+11 470,493 庄文杰等 卷烟承运标段划分模型研究 117 由表中数据可得，进化方案与现行方案相比，在目标函数上降低了 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)图 5(b)C 厂进化后标段划分方案(5 个标段)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 方案 目标函数 订单量方差 标准差 现行方案（7 标段）57,604,547 1.43841E+10 119,934 对照组方案 50,048,964 3.88375E+12 1,970,724 进化方案（5 标段）54,438,229 3.32745E+08 18,241 由表中数据可得，进化方案与现行方案相比，在目标函数上降低了 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 个标段轮廓明显，增加了方案的实用性。中国烟草学报 Acta Tabacaria Sinica 2023 Vol.29 No.5 118 图 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 方案 目标函数 方差 标准差 现行方案（2 标段）49,441,174 1.00318E+9 31,673 对照组 45,618,491 1.45076E+13 3,808,886 进化方案（2 标段）48,143,168 2.83114E+8 16,826 经过对比可以发现，现行方案和进化方案在目标函数方面相差不大，但进化方案比现有方案的方差、标准差分别降低了 71.78%和 46.88%，订单量更加均衡，并且各标段的轮廓分割更加明显。值得注意的是，本文提出的模型求解方案采用了双层优化算法，平均计算耗时（20 min 以内）随标段数的增加而增加。考虑标段划分为长期战略性决策，一般 2 年重新制定 1 次，该计算耗时在可接受范围内。同时考虑到国内标段划分场景需求众多，本文研究成果具有较高推广应用价值。本文提出的卷烟承运标段划分研究方法具有一定灵活性和普适性，不仅适用目前 A 中烟公司物流配送网络，也可拓展应用到其它中烟物流网络。如目前中烟物流配送有在重要枢纽节点上建立区域集散中心，针对此类物流网络可在应用本文所提双层算法时，将网络中的区域中心仓固定为聚类算法中的初始质心，并使其在算法的演变过程中保持不变。4 结论 经过本文的研究，在卷烟承运标段划分上取得了较为显著的成果：构建了标段划分模型，基于实际情况对理论模型不断优化调整，实现了理论研究到实际应用的有效转化，并且为标段划分方案提供了评价标准。（1）形成最终优化方案，目前已直接应用于 A中烟公司 2019 年度的运输服务招标文件当中，相比现行方案，模型目标函数改善明显，订单均衡也存在一定改善。（2）标段优化后不仅给管理带来便捷，同时也提高了拼车可能性，有利于供需双方降低运输成本，创造了社会价值，具体经济效益将在下一运输服务年度得到验证，预计全年卷烟运输费用下降 12 个百分点。（3）标段划分在国内外相关领域研究较少，本文具有较高的创新性，且具有一定的通用性，在行业范围内有较高的推广价值。参考文献 1 刘璐峰.浅谈卷烟市场化取向改革中消费者信息采集的重要性与方法J.中国市场，2018(31):135+142.LIU Lufeng.On the importance and method of consumer information collection in the reform of cigarette marketization orientationJ.China Market journal,2018(31):135+142 2 陈权.XX 中烟卷烟物流在途信息系统的规划D.南京理工大学，2014.CHEN Quan.Planning of in-transit Information System for XX Chinese Cigarette LogisticsD.Nan Jing University of Technology,2014.3 何梦军，吴怀岗，丁翔.带时间窗的同城物流配送区域划分与庄文杰等 卷烟承运标段划分模型研究 119 路径优化J.南京师范大学学报（工程技术版），2018,18(02):70-76.HE Mengjun,WU Huaigang,DING Xiang.Division and Path Optimization of intra-city logistics distribution area with time windowJ.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 windowJ.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 WindowJ.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 retailersJ.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-upJ.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 optimizationJ.Expert Systems with Applications,2014,41(2):521-534.9 N.Christofides.Fixed routes and areas for delivery operationsJ.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 algorithmJ.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 dronesJ.Transportation Research Part C:Emerging Technologies,2019,102(00):289-315.12 D.M.Miranda,R.S.de Camargo,S.V.Conceiao,M.F.Porto and N.T.R.Nunes.A multi-loading school bus routing problemJ.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 LayoutD.Shandong University,2013.15 Helsgaun K.An effective implementation of the LinKernighan traveling salesman heuristicJ.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 Abstract: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.Keywords:cigarette distribution;division of tender sections;two-tier optimization algorithm *Corresponding author.Email：