杨璞光 陈安 吕永贵 罗艳辉

摘 要：本文研究了烟草物流配送时间的优化问题。该问题具有组合复杂性和计算困难性。本文首先根据卷烟工业物流实际情况建立相应的数学模型，采用了基于启发式策略和散射搜索算法的优化方法来缩短烟草物流配送的时间。该方法通过放宽问题的限制条件，构造优化配送的位置顺序，寻找最优配送周期来减少配送时间。最后通过数值实验对该算法进行了评价，并与现有强约束下的启发式算法进行了比较。结果表明，该算法具有较好的优化效果，能够有效缩短工烟物流配送的时间。

关键词：烟草物流配送;优化方法;散射搜索算法;启发式算法

引言：烟草物流是指烟草及其制品和原辅料从生产、收购、储存、运输、加工到销售服务整个过程中物质实体运动以及流通环节的所有附加增值活动，进一步可以狭义地认为是指烟草行业基于社会职能分工的不同，工烟企业、商烟企业及相互之间发生的烟草制品和相关物资实物的移动活动。烟草行业是一个垄断经营的高利润行业，因此高利润有时候掩盖了现代物流对企业竞争力的价值。物流成本是烟草企业成本中的重要组成部分，物流成本的降低就是企业的“第三利润源”。因此要以强大的物流体系来支撑烟草行业的持续发展，应对市场环境带来的风险。

当今，很多行业相关的优化问题被提出，有一些在相关文献中得到了解决，并提出了多种求解算法。例如漳州烟草配送区域及线路优化借助柔性线路截取算法以及GIS线路优化辅助系统，依据零售户的地理位置、历史销量对全区所有零售客户进行线路调整，改变传统既定计划、线路、车辆、人员“以线定车”的固定配送模式，建立了“以量定车，以户定线，户量均衡，动态优化”的弹性送货新模式。又例如宜春市烟草公司针对物流配送线路建立VRP模型，通过节约算法优化问题，提高卷烟配送运输效率，降低配送成本。安阳市烟草公司利用GIS系统，添加适当的约束条件，达到“送货线路到最优，车辆配载经济”的目标。

卷烟工业物流配送中心负责给烟草商业公司点至点的分发，配送中心发出配送车辆，完成配送任务后返回物流配送中心。各地商烟公司比较分散，导致物流末端配送呈现多批次、少批量的特点，对配送中心的物流配送路线优化提出了严峻挑战。本文将着重围绕物流配送路线优化问题展开探讨，提出相应的优化解决方法。

一、问题描述

卷烟工业物流配送指的是各个送货车辆从物流配送中心配货到向各个烟草商业公司送货的过程。送货路径选择的合理性对于整个配送过程的成本和效率都有很大的影响。所以如何采用科学合理的方式规划配送过程，是烟草物流管理过程中需要研究的一个重要问题。

本文假设问题里的送货车辆在一个运送周期里可运送多种货物到多个地点，每个配送点坐标都各不相同，送货车辆载重量一定。送货车辆先到配货仓库一次性装配多种货物，然后分别移动到对应的烟草商业公司卸下所需货物，这个过程中送货车辆不会再返回物流中心装配货物，除非它已经放置完之前取的所有货物。理论上是一次装配后，依次去多个烟草商业公司卸货，在规划的路径终点刚好完全卸完货物。之后再次返回物流中心配货，循环往复的过程。

二、问题分析和建模

卷烟工业物流配送的总时间可以分为以下几个部分：（1）送货车辆在送货路途行驶的时间;（2）送货车辆在仓库装配货物的时间;（3）送货车辆在各个烟草商业公司卸货的时间。

假设配送完所有货物需要K个配送周期（以下简称周期），用Ti表示一个周期所需要的时间（1

Tipick：在第i个周期中送货车辆从配送中心的仓库装配货物的时间。包括了在配送中心中行驶的时间和货物装配所需的时间。

Tidownload：在第i个周期中送货车辆从货物装配完成后到第一个烟草商业公司的时间。

Tiplace：在第i个周期中送货车辆卸货的时间。包括在不同烟草商业公司间移动的时间和卸货所需要的时间。

Tiupload：在第i个周期中送货车辆从最后一个烟草商业公司卸完货后离开到新的配送中心的时间。

因此，卷烟工业物流配送的总时间可以由以下数学公式表示：

■（1）

假设第i周期送货车辆装配的货物份数为■（1

■（2）

其中，■表示一次装货的时间。

同时，第i周期送货车辆需要到达的烟草商业公司卸货次数为■（1

■（3）

其中，■表示在烟草商业公司卸货所需要的时间，■表示在不同烟草商业公司间移动的时间，（j，j+1）表示从第j个烟草商业公司到第j+1个烟草商业公司。可近似认为是个常数，因此，由公式（2）可知，主要影响送货时间的是在烟草商业公司之间移动的时间。

通过以上分析，影响卷烟工业物流配送时间的主要因素为送货车辆去各个烟草商业公司送货的顺序。这个因素在整体优化问题中高度耦合，使得问题变得复杂。因此，本文尝试用一种分解相关问题的方法，然后设计相应的方法来求解问题。

通过合并等式（1），（2），（3），能得到：

■（4）

在等式（4）中，第三项和第四项主要取决于循环次数K和送货车辆最大装载量;其余项主要取决于行驶的时间和循环次数K。因此，为了缩短配送时间，应当缩短配送周期内行驶的时间和减少总的周期数。

三、优化方法

1.可行解的编码和评价函数

优化方法中的可行解不仅要包含问题中的决策信息，而且要适合所使用的算法。因此，为可行解设计一个合适的编码表示形式是必要的。

假设每个送货目的地都用一个连续的整数进行连续编号。使用不同目的地的编号构造编码序列来表示不同的可行解。编码序列可以通过以下方法进行解码：首先，从序列开始通过分组G区分送货组，也对应于送货周期。每组G表示一辆车一个周期所要到达的目的地集合。然后，对于每个送货组G，根据整数编号在序列中出现的顺序，依次将H1到HN（N是送货组中整数编号数量）分配给编号的目的地。

举例说明，一辆送货车辆要到达4个目的地，用H1表示一个周期内计划送的第1个目的地。而一共有14个目的地需要它送货，那么送货顺序问题的可行解可以用下图所示的编码序列表示。

图中，编码序列{3，14，1，12，5，13，8，6，9，4，11，10，2，7}可被解码为下面两个内容：（1）目的地被分成了四组{3，14，1，12}，{5，13，8，6}，{9，4，11，10}和{2，7}，对应了四个送货周期：G1、G2、G3、G4。（2）每货物组中的目的地编号按其在组中的出现顺序对应了依次送货到烟草商业公司的顺序：如G1中先送编号3的目的地，到14号目的地，再到1号目的地，最后到12号目的地。

从一个可行解的编码中可以得出两个决策信息：运送货物的周期数和一个周期内向目的地送货的顺序。可行解的编码实现了包含必要的决策信息，并使得可行解能够适用于算法。所以把问题的可行解经过编码后输入算法，把算法得到的结果解码便能得到所期望的决策信息。

在烟草物流配送的过程中，装货和卸货过程的时间可以近似为常数，主要的时间为在不同的烟草商业公司间移动所用的时间。因此，烟草物流配送的时间基本可以由送货车辆行驶的时间来衡量，而已知不同烟草商业公司的距离，可以通过计算距离的方式得到近似的行驶所需时间。本文通过建立数学函数的方式来计算各个物流配送方案所耗费的时间，来评估下文提出算法的不同可行解。

2.基于散射搜索的优化算法

由第2章的问题建模可知这个问题很难通过局部搜索方法找到最优解或次最优解。所以本文采用了一种基于散射搜索（SS）的优化算法，该算法是由Glover提出的一种全局搜索方法，其很少依赖搜索过程的随机性，而是采用其框架中一系列系统性方法来实现对优化问题的求解。基于SS方法的算法流程图如图5所示。

算法的具体操作步骤如下：

（1）生成初始解集

对于散射搜索法，要求初始集的解尽可能分散在整个解空间中。为了满足这一需求，按照以下步骤生成初始解集：

第一步：利用货物的编码集M，随机地生成初始可行解L0={m1，m2...mi...mM}，mi表示第i份货物的编码，|M|是货物的总数量。L（i）=mi。

第二步：定义一个序列P（h：s）=（L0（s），L0（s+h），L0（s+2h），...，L0（s+rh）），其中1

第三步：通过改变[1，|M|]中的h，能从初始解中得到|M|个不同的可行解。从而构造出初始解集S。

为了保证初始解集的多样性，本文对第三步做一点小的改动。对于可行解L（h），引入它的翻转序列，表示为L*（h），那么它同样也是可行解。例如，对于可行解L（4）=（4，9，6，3，7，2，5，1，8），它的翻转序列为L*（4）=4）=（8，1，5，2，7，3，6，4，9）。如果改变[1，|M|/2]中的h，生成|M|/2组初始解，还可以得到|M|/2组翻转解，进而能通过这些可行解构造初始解集。如果需要产生更多的解来扩展初始解集，能够使用这种方法随机地生成另一组可行集。

（2）初始解的改进

改进初始解的操作的目的是将初始集合中的每个原始解转换为一个或多个更好的解。可以用简单或复杂的方法来改进解。考虑算法的时间复杂度，本文采用两元素优化局部搜索方法对初始解集S的解进行改进。

解改进的基本操作描述如下。利用两元素优化方法对S中的一个解进行改进时，将解序列中的两个分量按其位置进行交换，从而产生一个新的解。如果找到一个更好的解，用它来替代S中的原始解;否则，保留原始解。应该注意的是，改进解的操作应该应用于S中的每个初始解。解的改进操作可以根据实际需要灵活设置终止条件。例如，可以为解引入持续改进或持续不改进的时间计数器，以确定何时可以终止改进。

通过改进初始解集，可以得到Simp（改进解集）。

（3）构造初始参考解集

设初始参考解集RefSet，是配送时间少的较好解和配送时间多的较差解的集合。设RefSet1为较优解子集，RefSet2为较差解子集。它们的大小都是b/2（b是一个整数，依赖于问题的规模，但不大于初始解集的大小）。RefSet是RefSet1和RefSet2的并集。初始RefSet的构造包括以下步骤：

第一步：从改进解集Simp中选择配送时间更短的b/2最佳解来构造子集RefSet1，将它们添加到参考解集RefSet并从Simp中删除它们。

第二步：对于Simp中其余的每个解，计算它与RefSet中每个解之间的最小“距离”。在这些最小距离上取最大值的解被添加到RefSet中，然后从Simp中移除。这个解也称为多样解，保留它是为了保持解的多样性。同样的过程重复b/2次，得到b/2不同的解，构造RefSet2。将这些解添加到RefSet。这样便得到了完整的参考解集RefSet。

上述两个解之间的“距离”的概念定义为两个解序列中相同位置的分量彼此所相差的次数。例如，有两个解序列s1=（1，5，2，4，3）和s2=（2，5，3，4，1），那它们的距离是3，因为有两对位置相同的分量是相同的。两个解之间的距离表示两个解之间的差异程度。

（4）组合解集

通过解的组合，生成新的解，扩大解空间的搜索范围。这个操作有两个步骤。第一步是生成解子集，第二步是每个子集的解的组合。

为了使子集覆盖尽可能分散的不同区域，子集应该同时包含优解和劣解。由于参考解集包含较好的解和较差的解，因此可以用它来生成子集。在这里，对参考解集RefSet应用成对组合方法，生成一种称为双解的子集。每個双解子集由两个解组成，这两个解分别从两个母解中选择。例如，如果得到一对集合为S1=（x1，x2，x3）和S2=（y1，y2），它最多有6个双解子集，（x1，y1），（x1， y2），（x2，y1），（x2，y2），（x3，y1）和（x3，y2）。所以，参考解集RefSet中任何两个解都能用来产生了两个一个双解子集。然而，由于两个不同的解可以构造一个有效的双解子集。因为RefSet中有b个解，结果最多可以得到b（b-1）/2个子集。

在生成双解子集之后，可以使用简单方法或复杂方法将两个解合并到子集中生成新的解。这里采用部分匹配交叉的方法。它起源于遗传算法。一个子集中两个解的每个组合都可以通过部分匹配交叉方法生成两个“新”解。通过这种方法，得到了一个具有b（b-1）/2“新”解的集合，记作TemSet。然后，再次使用两元素优化方法对TemSet中的所有解进行改进。

（5）参考解集更新

更新参考解集需要从RefSet和TemSet两个解集中选择b个“最佳”解，并在RefSet中替换原始解。更新方法与初始参考解集的构造相同，唯一的区别是源解集是这里的RefSet和TemSet的结合。然而，TemSet中的一些解决可能存在于RefSet中。为了判断TemSet中是否生成了真正的新解，算法计算差分集TemSet-RefSet，并将其设置为新的解集NewSet。然后，该算法决定是否结束当前的搜索循环判断如果NewSet是空集，如果NewSet不是一个空集，这意味解搜索过程中至少有一个新的解生成。当前循环的散射搜索将继续进行解的组合、改进和更新操作，如前面给出的算法框架所示。否则，当前搜索周期（不是整个算法）将终止。

3.算法运行效果与收敛性分析

为了检验算法的运行效果，通过MATLAB实现上述算法并进行检验。第一种检验方法为一次输入31个城市坐标数据，通过算法找出经过所有城市的最短路径以及相应的配送顺序。运行效果如图6所示。从图中可以看出，在复杂的情况下，人工已经难以计算出最短的连续路径的顺序，此时算法仍能够很好地计算出最短路径的顺序结果。第二种检验方法是同时输入15个城市数据，模拟3辆送货车辆的情况，运行效果如图7所示。从图中可以看出，在多路径多种分配的情况下，算法仍能够合理的分配送货车辆得到最短的配送路径顺序。

收敛性方面，由算法本身的原理特性，算法在迭代的过程中会保留原始的解集中一半的较优解集，在另一半较差解集的基础上进行改进，构造新的解集，利用匹配交叉变异等方法探索更多的解空间。上述的原理保证了算法的收敛性，在迭代的过程中能够不断的保存优质解，丢弃较差解，从而向期望的解空间收敛。第一种检验方法在迭代过程中算法的收敛性分析如图8所示，可以看出，随着算法的迭代，其求得的最短距离也在不断减小，最终达到了较稳定的水平。

四、实际应用

为了验证该算法的可行性和有效性，利用红塔集团的在广东省近年卷烟工业物流配送中某个月的实际数据进行实际应用。其中一辆送货车辆的装载量为150箱，即750件。实物包装一箱烟草，烟草行业一般称之为“件”，是50条。而在烟草报表中的统计概念，是以实物五件为一箱，是250条。

红塔集团广东省烟草某个月需求情况如下表所示。

以广东省烟草实际需求数据作为仿真实验的对象，为了下一步运用到物流配送系统内，在Microsoft Visual Basic 6.0中实现了该算法。根据实际，一辆送货车辆能装150箱烟，送货车辆的数量能够灵活调整，保证车辆满载。各地市之间的相对位置和距离按照实际地理位置设定，均为确定和已知的不变量。为了评估本文所运用的算法的性能，将其与文献中提出的强约束下的启发式算法进行了比较，该算法将整体问题分解为子问题的层次结构，并基于动态规划和最近邻旅行商问题的求解。另外，由于有些地市烟草需求量大，一部分烟草需要选择整车装载其所需烟草然后直达的运送方式。在烟草物流配送优化过程中无需对这部分直达运送方式进行优化，故在结果显示中将这部分运用直达运送方式的结果剔除。只讨论地市需求量不足整车装载量的情况下，如何分配送货车辆的配送路径以达到最短路程。

实际应用的比较结果如下表：

优化结果表明，该算法的性能优于HA算法，提高了近10%。不仅在总送货周期的基础上减少了一个送货周期，而且总路程上也有所缩短，相当于节省了一辆车的运载量和路程中的成本费用。究其原因主要有两个方面：一是SS算法放松了一些强约束，使得解空间扩大，这意味着获得更好解的可能性更高;二是具有全局搜索机制的SS算法比HA算法有更多的机会找到更好的解，HA算法对货物的配送排序采用局部搜索的方法。将该套方法运用到实际工作后，实现了配送货物数量相同的情况下，送货车辆和配送人员减少、装载量及送货户数增加的效果，达到了提高卷烟配送效率、降低配送成本的目的。

五、结论

本文研究了卷烟工业物流配送时间最小化的优化问题。对该问题进行了分析，指出了现有优化算法存在的一些强约束，导致了实际应用性能不理想的情况。由于问题具有组合性和计算难解性，本文提出了一种基于启发式策略和分散搜索方法的优化算法，优化卷烟工业物流配送的时间。通过红塔集团在广东省烟草物流配送数据实际应用结果表明，该算法能取得较好的效果，明显缩短了烟草物流配送过程中的时间，证明该套优化方法能够在实际卷烟工业物流配送中起到指导作用，达到提升配送效率、降低配送成本的目的。需要指出的是，本文的方法将整个问题分解为单独的子问题，并独立研究求解，得到最优解。在今后的工作中，将深入建立整体优化问题的集成模型，设计协同优化算法，同时解决相关子问题，进一步提高算法性能。

参考文献：

[1]李朵.地级市煙草现代物流配送系统优化[D].西安建筑科技大学，2016.

[2]章惠民.烟草商业系统物流线路优化研究与应用[J].中国烟草学报，2018，24（03）：100-105.

[3]陈小丽，曲媛，肖鸿.宜春市烟草公司物流配送线路优化[J].佳木斯大学学报（自然科学版），2012，30（01）：49-52.

[4]潘国鹏.安阳烟草公司物流配送路线优化问题研究[D].郑州大学，2017.

[5]陈影，孙虎.基于Flexsim的烟草物流配送中心规划仿真[J].物流技术，2018，37（07）：105-110.

[6]陈成.基于改进遗传算法的物流车辆路径问题优化[J].信息技术与信息化，2018（09）：41-43.

[7]李阳，范厚明，张晓楠，杨翔.随机需求车辆路径问题及混合变邻域分散搜索算法求解[J].控制理论与应用，2017，34（12）：1594-1604.

[8]张晓楠，范厚明.混合分散搜索算法求解带容量约束车辆路径问题[J].控制与决策，2015，30（11）：1937-1944.

[9]F.Glover， Heuristics for Integer programming using Surrogate constraints，Decision Sciences，8（7）：156-166，1977.

[10]陈萍.启发式算法及其在车辆路径问题中的应用[D].北京交通大学，2009.

作者简介：杨璞光（1994- ），男，华南理工大学在读硕士生，研究方向：自动驾驶