安裕强，徐跃明，欧阳世波，李圣毅

1.红云红河烟草（集团）有限责任公司物流中心，昆明市红锦路367号 650000

2.昆明理工大学管理与经济学院，昆明市景明南路727号 650000

3.马来西亚博特拉大学经济学院，马来西亚雪兰峩州沙垱 434000

成品卷烟销售订单的配送调度是卷烟工业企业物流管理的重要环节，也是物流管理优化决策的核心问题。针对该问题国内学者已有较多研究，任晓智等［1］基于智能化策略辅助启发式算法优化了配送中心选址，并设计了求解大规模原问题的方法。李存兵等［2-3］通过引入工作量均衡指标，提出了改进的双层遗传算法，并通过实验验证了该算法相比单层遗传算法性能更优；基于加权糅合构建了综合目标模型，并设计了精英自适应遗传聚类算法进行求解。张丹羽［4］按照分级调度的思路，采用聚类方法获得配送节点中心区域，再利用改进的C-W法求解每个区域中的最短路径。邹霞［5］在分级优化的基础上，引入时间窗设计了改进里程节约法，用于求解动态同城配送优化模型。刘昕雨［6］、方伟华［7］采用类似于图计算方法求解调度优化问题。禹旺明［8］基于蚁群算法提出了多回路车辆调度问题模型，并在卷烟企业进行了验证。徐明元［9］提出了改进型染色体编码方法以及不同蚁群分工的遗传算法和多态蚁群算法，提高了求解效率。潘国鹏［10］针对单调度中心，非满载，具有最大配送里程约束、载重约束、软时间窗约束的大规模纯卸货的路线优化问题，设计了改进信息素计算机制的蚁群算法。李蒙龙等［11］提出了基于任务分层模型的优化调度方法，可减小问题求解过程中的解搜索空间。冯子炎等［12］通过构造合适的遗传算子，设计了用于解决带时间窗的车辆路径规划问题（Vehicle Routing Problem，VRP）的遗传算法。肖正中等［13］采用边界分配法将多起点转化为单起点车辆调度问题，并结合遗传算法与蚁群算法求解跨区域配送寻优问题。章惠民［14］提出了一种改进的柔性线路截取优化算法，实现了车辆利用率最大化以及配送里程最小化目标。

而国外的研究主要集中在卷烟等快消品配送调度优化方面。Desrochers等［15］研究了带有时间要求的配送服务问题，通过将原问题分解成受限主问题和子问题，利用列生法逐步迭代求解主、子问题，能够获得在客户节点规模（约100个）较大情况下的可靠解法。Gendreau等［16］、Bullnheimer等［17］、Baker等［18］针对装载量限制、行驶路程限制的单配送中心的VRP问题，分别利用禁忌搜索算法、蚁群算法和遗传算法进行求解，并对不同启发式算法的求解效率进行对比。Thangiah［19］研究了多配送中心下的配送优化问题，提出了一种利用遗传算法对客户聚类，再通过嵌入式启发算法求解的方法。Dethloff［20］将配送优化从纯卸货问题扩展到沿途混合装卸，并设计了启发式算法进行求解。Bräysy等［21］探讨了启发式算法的特性和评价准则，针对时间窗VRP问题，分析比较了路径构造和路径优化两种启发式算法的求解效率。Novoa等［22］研究了随机需求下的VRP问题，通过将优化目标设定为期望路径最短，并利用Rollout回溯算法进行求解，解决了车辆动态执行临时配送任务的调度问题。Fleszar等［23］研究了开放式VRP问题，提出了一种变邻域搜索算法求解该问题。Baldacci等［24］对比了求解装载量限制VRP和时间窗VRP两种问题的精确算法，提出了一种整数规划的割平面方法。Rahmawan等［25］针对快消品公司PT X TBK存在的配送问题，通过引入容量限制、路径冲突限制，以及采用基于活动扫描的离散时间仿真方法，提高了资源使用效率，增加了客户满意度。

虽然目前关于配送车辆调度、配送路径优化的研究较多，但针对卷烟工业企业成品卷烟销售订单配送调度问题的研究则鲜有报道，在实践中配送调度主要依靠人工经验决策，存在着工作效率低、管理不科学、人工作业量大等问题。针对此，王保中［26］基于求解VRP数学模型是典型NP-hard问题，通过改进蚁群算法解决了烟草物流线路优化问题；杨燕霞等［27］对模拟场景抽象处理，通过减少约束条件降低求解难度，也获得了可行解。上述研究结果表明启发式算法具有可行性，但存在对模型参数依赖度高［8］、问题模型简化后过于理想等问题，导致求解结果难以应用于生产实践。此外，若求解规模过大，启发式算法还容易出现收敛速度慢或者全局搜索能力下降等问题［28］。为此，首先将待调度的成品卷烟销售订单进行凝聚聚类，然后利用专家策略函数和机器策略函数构建搜索树，再根据业务规则构造调度优化评价函数进行配送调度决策［29］，进而设计了一种基于机器学习的智能配送调度算法并对其进行模拟仿真，以期提高卷烟成品销售订单配送调度效率，实现调度决策支持。

1 模型建立

1.1 问题描述

卷烟工业企业的客户一般是按照地级市行政区设置商业企业，每个地级市有且只有一个烟草商业企业，因此工业企业配送主要为干线运输。考虑到调度后实际运输业务并不会立即发生，且中间还存在一个仓储发货作业时间，故在调度时将路网简化为时序静态的、点与点之间有且仅有一条路径的有向图，不考虑多路径选择及拥堵、过路费高低等因素。工业企业通常拥有若干个发货仓库，且发货仓库间的库存结构存在差异。由于卷烟运输实行法定准运证制度，即每个订单必须对应一个由行政管理部门签发的有时效的准运证，且订单必须在时效内完成交付。该制度还要求同一个订单不能分别在两个或两个以上仓库拆分出库，当发货仓库库存结构与订单需求不匹配时，可以采用将各发货仓库的库存移库至中心库集中配货方式。此外，订单及订单对应的准运证和承运车辆只能是“多对一”关系，即一辆货车可以承运总和不超过其装载量上限、不低于其装载量下限的多个订单，每个订单只能由一辆车承运，不能同一订单分车装运。

因此，成品卷烟销售订单配送调度优化问题可以归纳为：某一配送调度周期内，工业企业根据客户下达的订单，综合考虑运输路线、库存结构、承运车辆，以及由订单要求到货日期、准运证时效组成的时间窗口，通过合理组拼订单完成车货匹配，确定发货仓库和发货日期，进而实现时间窗条件下运输配送成本最低。

1.2 数学模型

在决策时点上，工业企业会接收到一个由M个客户在时间周期P内下达的R个订单组成的订单池，订购在销的K批次的T个规格的成品卷烟。定义O表示订单，设第m个客户下达的第r个订单为且∈Om∈O。定义artk表示订单包含的批次为k∈K且规格为t∈T的卷烟数量。定义时间区间表示订单的要求到货时间窗，即时间窗范围为要求到货日期当天上午9点至下午3点之间。设定车辆运输标准速度v为650 km/d，从货物启运至送达的在途时间为，其等于发货仓库和客户仓库之间距离与标准速度v的比值，故订单最晚出发时间为此外，准运证时效为要求到货日期下限时间后的48 h内，即为

用NS表示发货仓库，i∈NS，第i个发货仓库出库能力上限为Hi；用NC表示客户仓库，客户仓库集合定义为NC=｛uj｜j∈M｝；定义一个由发货仓库和客户仓库以及仓库之间基于地理路网组成的权值有向图G=（N，A），其中N=NS∪NC，A=N×N。以辽宁省为例，采用基于地理路网的权值有向图表示客户仓库网络空间关系权值有向图。用arc（i，j）表示有向图中第i个仓库到第j个仓库的路径，以两仓库间的运输距离作为路径权重wij，见表1。τij表示两仓库间的运输在途时间，τij=wij/v。如果i∈NS，则表示装货时间；如果i∈NC，则表示卸货时间。

定义sitk表示发货仓库i∈NS包含的批次为k∈K且规格为t∈T的成品卷烟库存数量，第i个发货仓库的库存总数如果车辆在时间窗下限之前到达客户仓库，将产生因等待卸货而带来的承运机会损失成本；如果车辆在时间窗上限之后、准运证到期之前到达，将产生因延迟到货而带来的客户满意度损失成本；如果车辆在准运证到期之后到达，将产生违规经营成本。B表示可调配车辆的集合，对于任意发货仓库i∈NS，Bi表示发货仓库i可调配车辆的集合，Gbll表示车辆b∈B的装载量下限，Gbsl表示装载量上限。

（1）定义决策变量：

dbi=车辆b从i点出发的时间，dbi∈R+，∀b∈B，∀i∈N

（2）设定优化调度模型目标函数为总成本最小：

f=min（c），令c=C1+C2+C3

总运输成本C1=u1cT

车辆使用成本C2=u2cV

时间成本C3=

式中：u1表示运输里程，表示运输成本，元/km；u2表示执行任务的车辆数量，辆；cV表示每辆车的使用成本，元/辆；cX表示每辆车因提前到达产生的承运机会损失成本，每等待1 h记1个单位成本；cM表示因延迟到货产生的客户满意度损失成本，每延迟1 h记1个单位成本；cL表示因准运证过期产生的违规经营成本，元。

2 算法设计原理及实现

由图1可见，本研究中设计的算法流程主要分为3步：一是对待调度成品卷烟销售订单构成的原问题集聚类，将业务规则和车货匹配历史数据作为聚类中心，使用凝聚聚类（Agglomerative Clustering，AC）进行订单合并并重复此步骤，从而缩小原问题规模；二是将历史销售订单组拼记录作为算法的数据样本，构建一个基于历史数据的专家策略函数作为优先策略，并采用蒙特卡洛搜索建立搜索树，再构建一个基于地理空间有向图的机器策略函数作为次级策略，采用与优先策略相同的方法建立搜索树；三是建立一个由业务规则组成的调度优化评价函数，对搜索树评价剪枝，确定搜索树结果。由此实现订单组拼和车货匹配结果的智能决策。在下一次调度优化中利用包含最近一次调度结果在内的历史数据样本对部分聚类规则及专家策略函数进行迭代，进而实现算法迭代。

2.1 订单聚类

任何时点待调度成品卷烟销售订单构成的原问题集，都会存在具有相同关键特征的订单，这些关键特征包括客户、客户仓库、订单号、需求结构（规格、批次和数量）、要求到货日期、发货仓库，共6个。如果订单的全部或部分关键特征相同，那么就可以将其合并为一类，即凝聚聚类，将小订单组合成大订单。当大订单达到经济运输规模，且要求到货时间窗和发货仓库库存结构均满足约束的情况下，可以直接获得大订单的调度结果，无需作为原问题集输入模型求解。

由于原问题集中订单的关键特征均为字符串数据，为了量化关键特征进而通过度量实现凝聚聚类，需要将关键特征数据转变为多维的0-1稀疏矩阵，即将订单数据进行欧式空间化。首先，以订单号为主键值，将客户、客户仓库两个关键特征的字符串数据分别转化为各自维度上的0-1变量，构成聚类空间中的两个维度。其次，根据订单需求结构和库存结构，构造两个维度的0-1矩阵，再进行矩阵运算，获得每个发货仓库维度上的0-1变量。例如，发货仓库现有A、B、C、D、E共5个批次为1的卷烟规格，订单ID.1需求结构为A规格1批次50万支，B规格1批次120万支，各发货仓库的库存结构见表2。当发货仓库库存满足订单需求结构时，发货仓库维度上相应的向量值取1，否则取0。最后，要求到货日期哑变量化，根据作业准备期和在途运输时间，能够推算出每个订单的要求发货日期，进而获得发货日期维度上的0-1哑变量。

表2 发货仓库WH 1～WH 4库存情况Tab.2 Inventories of warehouse WH 1-WH 4（万支）

对完成关键特征欧式空间化的订单数据，使用凝聚聚类将其归入不同的类并添加类标签，然后类标签为同一发货仓库、同一客户仓库、同一发货日期的订单直接输出调度结果，并将达到经济运输规模，且要求到货时间窗和发货仓库库存结构均满足约束的订单从原问题集中剔除，从而将订单分为已调度和待调度两类，待调度订单形成新的原问题子集，由此缩小调度问题规模。

2.2 基于策略函数的待决策子集优化

待调度子集是由聚类后关键特征离散的订单组成，基于机器学习的智能配送调度算法的核心是在路线优化的基础上对这些订单进行车货匹配决策，以实现总成本最小目标。分析可见，遍历所有可能的组合并评估目标函数是获得最优解的最佳方式，但遍历所需的深度和广度显然是不可接受的。为此，算法模拟人工在调度中采用的“按图索骥”搜索方式，基于蒙特卡洛搜索设计了具备优先级差异的两个策略函数，用于控制决策空间搜索的深度和广度，从而实现对待决策子集的优化。

将待调度子集R0original作为初始状态s0，在子集中选择距离发货仓库最远，即max（wi）j的一个订单r0，r0∈R0original，作为初始节点并创建搜索树。搜索树的分支首先由数据样本中的专家策略确定，只有当初始状态s0不具备专家经验时，才以次级的基于客户网络空间关系权值有向图的机器策略替代专家策略。在专家策略下，订单r0会存在若干历史组拼方式，定义p（a｜s0，R0resul）t表示初始状态s0下，专家经验中R0result订单与初始节点订单r0历史上已有的各种组拼方式出现的概率。由于决策当期内的成本、里程、车辆、库存结构相比各历史决策期不会发生突变，因此可以将pr≠0的组合组成策略空间Aexpe（rts，R），并认为其是近似最优策略空间。

首先，根据初始节点订单r0的客户、客户仓库、订单号、需求结构（规格和批次）、要求到货日期、发货仓库6个关键特征，从历史销售订单组拼记录中抽取客户、客户仓库两个关键特征与初始节点有过组拼的订单，组成历史订单集R0history，求解待调度子集R0original与历史订单集R0history的交集R0result=R0history∩R0original，订单r0与订单集R0result就组成一棵二级搜索树；如果不具备专家经验，以基于客户网络空间关系权值有向图获得的距离矩阵作为关键特征，在R0original中抽取距离wij满足阈值的订单组成订单集R0result，并与订单r0组成二级搜索树。其次，利用需求结构、要求到货日期、发货仓库3个关键特征，对初始状态s0下的二级搜索树进行剪枝，即在搜索中调用组合评价函数，进而找到初始状态下s0与r0的最优组合。组合评价函数是一个规则引擎，评价和判断当前状态下哪种组合较优的核心规则是按顺序将时间窗、发货仓库、装载量三者相互协调。

2.2.1 时间窗规则

成品卷烟物流是具备时间窗的约束问题。因此，首先评价二级搜索树中订单组拼时间窗的协调程度。初始节点订单r0的时间窗为，可以与r0进行组拼配送的订单是需要满足时间窗协调的订单ri∈且其最晚到货时间必须满足dr（iorder_3pm）≥dr（0order_3pm）+wr0ri/v。

2.2.2 发货仓库规则

由于经过凝聚聚类后原问题子集中的订单需求结构已欧式空间化处理，因此可以直接与同样经过欧式空间化处理的发货仓库库存结构进行矩阵运算，获得每个发货仓库数据维度上的0-1变量，并使用“订单是同一个发货仓库”的规则，对已经过时间窗规则剪枝的二级搜索树再次剪枝。

2.2.3 装载量规则

由于成品卷烟物流是规模效益显著的经济活动。因此，装载量规则的核心是车辆满载率尽可能不低于下限并趋于100%，故满足发货仓库规则的订单r0的订单数量可以建立关系：

其中，车辆上限Gbsl由历史上服务过订单r0客户频次最高的车型决定。对于ri∈，取GapR为最小值的订单ri与r0组合。以沈阳市烟草公司为例，相应装载量数据见表3。

表3 装载量数据（以沈阳市烟草公司为例）Tab.3 Loading capacity data，e.g.Shenyang Tobacco Company

如果多个组合同时均满足3个规则，则根据p(a|s0，）的大小决定组合的取舍。经过基于策略函数构建的搜索树决策后，将订单r0和ri从待决策的订单池中剔除，将待决策订单池从初始态s0更新为下一个状态s1，并继续迭代搜索决策，直至状态sn中剩余订单均无法满足评价函数。利用线性规划模型对剩余订单求解，其中目标函数中的运输成本cT取与承运商签订合同中约定的单价，单车使用成本cV按照车型进行经验赋值，提前到达产生的承运机会损失成本cX取每等待1 h记1个单位成本，延迟到货产生的客户满意度损失成本cM取每延迟1 h记1个单位成本。

随着配送调度决策结果的不断积累，每期调度决策可使用的历史数据也不断增加，专家策略空间的规模逐步增大。当时间足够长时，专家策略空间将会取代基于客户网络空间关系权值有向图的机器策略网络，并趋近于当前状态下的全部策 略 空 间 ，即由 此 可 以 减少算法时间载荷和硬件载荷，提高求解效率，并通过历史数据不断积累实现算法训练，使策略函数越来越符合实际调度业务场景，进而使输出的待决策子集逐步符合模型约束。

3 应用分析

3.1 数据采集

采集红云红河集团2020年4月28日至30日需调度的100个客户下达的584个成品卷烟销售订单，订单合计配送卷烟191 574.68万支。输入的基础数据包括决策期内红云红河集团的生产入库计划及库存、各发货仓库可用车辆、2016—2019年历史销售订单组拼记录、准运证有效期、距离矩阵、运输里程和时间等。

3.2 系统搭建及测试方法

本研究中算法采用PYTHON（3.6.2版）进行编程，主要调用机器学习库（Scikit-learn，0.21.3版）、数据分析和处理工具库（Pandas，0.25.3版；Numpy 1.16.2版），运行在配置主频2.3 GHz的酷睿i5-6200计算机上。为进一步验证机器学习算法的性能，基于同一计算平台使用相同的样本订单和基础数据，分别采用数学规划模型GUROBI求解器精确求解方法、时间窗VRP问题的遗传算法求解方法［12］，综合比较3类算法求解的使用车辆数量及结构、运输里程、时间成本以及多点组合车次数占比（单一车辆服务多个客户）。

3.3 结果与分析

由表4可见，对基于机器学习算法、精确算法、遗传算法求解出的结果进行数据分析。相较于精确算法和遗传算法，机器学习算法求解的使用车辆数分别减少19辆和14辆，运输里程分别减少2 595和3 682 km，时间成本分别减少195个单位成本和75个单位成本，多点组合车次数分别增加11.75和8.0百分点。表明机器学习算法对于订单调度具有更好的决策性能，多点组合车次数占比明显提高，时间成本得到有效控制，使用车辆数和运输里程在3种算法中均为最低。

表4 机器学习算法与其他两种算法调度结果对比Tab.4 Comparison of schedule decisions made by machine learning-based algorithm，accurate algorithm and genetic algorithm

4 结论

为提高卷烟工业企业成品卷烟销售订单配送调度效率，降低配送成本，设计了一种基于机器学习的智能配送调度算法。采用红云红河集团2020年4月部分成品卷烟销售订单作为样本数据，对机器学习算法、精确算法、遗传算法3种算法进行对比测试，结果表明：在相同样本数据和基础数据前提下，机器学习算法相较于精确算法和遗传算法，使用车辆数分别降低13.28%和10.14%，运输里程减少5%和7.2%，时间成本减少68%和45%，多点组合车次数分别增加11.75和8.07百分点。表明机器学习算法具有更好的收敛速度和收敛精度，可以快速求得配送调度问题的最优解，提高卷烟成品配送调度效率。由于机器学习算法存在训练集规模大、训练速度慢等问题，未来研究中将基于真实卷烟销售订单数据构建智能机器学习数据库，从而为成品卷烟销售订单预测以及根据学习经验数据库自动生成智能调度方案提供支持。