马翠鑫 曲晓艺 胡慧斌 陈宇 孙雪

摘 要：作为国民经济的基础产业，钢铁企业对国民经濟的发展十分重要。生产物流在钢铁企业中是提高企业利润，降低钢铁物流成本的关键环节。对某钢铁企业物流配送路径优化进行研究，通过建立模型和求解。可以减少了配送人员的绕行，减少货物的等待时间，有效地提高提货效率。

关键词：物流配送;路径优化;TSP

中图分类号：F25 文献标识码：A doi：10.19311/j.cnki.1672-3198.2019.36.014

0 引言

钢铁行业对国家的发展至关重要，也是我国国民经济的重要支柱产业之一。目前，我国钢铁生产物流存在的一个很大问题就是物流成本过高，其中运输的费用达到了物流总费用的一半，因此，有效地减少运输成本也是我国钢铁生产物流亟待解决的重要问题。基于这样的物流发展现状，要减少运输费用，进而减少配送成本，以达到降低物流成本的目的，就必须实现配送车辆运输路线优化。

本文以某大型钢铁企业M作为研究对象，通过分析园区内货物的堆放情况和运输车辆的运行情况，提出了一种基于TSP的物流配送优化模型，通过运用动态规划的方法对实例进行了求解，建立了配送路径的优化方案，为钢铁企业节省物流成本，提高物流效率提供了良好的决策。

1 国内外的研究现状

物流配送路径优化一直都是国内外研究的重点，许多的学者都对此进行了研究，很多倾向于用智能算法来对配送路径进行优化。旅行商问题（Traveling Salesman Problem，简称TSP，亦称郎担问题）就是典型的组合优化问题。它可以描述为：对于N个城市，它们之间的距离已知，有一旅行商要从某一城市出发走遍所有的城市，且每一个城市只能经过一次，最后回到出发城市，问如何选择路线可使他所走过的路程最短。国内外主要研究为：

J.F.Cordeau，M.Gendreau，G.Laporte等提出了改进的启发式算法进行路径优化，冯国莉、杨晓冬对用Hopfield神经网络车辆路径的优化进行了研究，刘芳华等对基于改进遗传算法的物流配送路径优化的研究等许多的学者对此进行了研究。对于TSP问题许多学者也进行了大量的研究，李萍等旺针对Hopfield神经网络解旅行商问题（TSP）经常出现无效解和局部优化解，将模拟退火智能算法与Hopfield神经网络相结合，提出了一种混合优化算法， Grefenstette J研究了遗传算法在TSP问题中的应用。孙雪等提出了一种改进的遗传算法来求解TSP问题。虽然很多学者对TSP问题及配送路径优化问题进行了大量的研究，但对于用TSP模型来实现钢铁行业物流配送路径优化的研究则很少，为此我们提出了用TSP模型来为钢铁行业的物流配送路线的进行优化研究。

2 模型的建立、求解及分析

M钢铁企业是国内规模比较大的钢铁企业，随着钢铁仓储品种、现货交易品种的扩大，钢铁电子交易量的增加，必须建立高效的钢铁仓储优化模型，使得堆码布局最佳，物流通道最简，推进钢铁物流智慧仓库建设。为了客户自行提货，尽可能的节省时间，该钢铁企业的物流园需要客户将订单上的货物分别到指定货仓一一提货，并在及时离开物流园的情况下实现路径最短。在建模过程中主要考虑如下因素：

（1）忽略因自然原因及人为等因素造成的交通堵塞的可能。

（2）两点之间的距离是两点之间的最短路径。

（3）司机在送货途中没出现意外情况。

（4）每一条通路的好坏都一样。

（5）车辆往返的路线相同。

该物流园区露天仓库一共有五个堆场，车辆从大门口进入仓库后，需要分别进行拣选。在建模过程中，模型中所应用的符号说明如表1所示。

五个堆场的距离矩阵如表2所示。

对于最短路径的问题，求解步骤如下：

（注：堆场1、堆场2、堆场3、堆场4、堆场5分别对应下面的各步骤）

（1）边界条件f0（i，F）的值列如表3。

根据上面的结果由状态k4=（1，{2，3，4，5}）开始回溯，得到一条回路为：1→2→5→4→3→1，且最短路径=30+16+34+32=112米。即车辆按照“堆场1→堆场2→堆场5→堆场4→堆场3→堆场1”走路径最短，并能最节省成本。

3 结论

本文针对某钢铁企业的实际需求，对其物流园内仓库配送路径优化问题建立基于TSP的模型，并利用通过动态规划方法来进行求解，最后通过实例计算得出了比较优的结果。通过本方法不但考虑了提货路径，还将回程考虑在内，这样做的好处是可以实现整个物流配送的闭合回路，减少了配送人员的迂回绕行，使他在完成了各个点提货任务后能及时离开物流园区，减少了等待时间，同时还能有效地提高提货效率。

因为该实例中地点数目不多，所以得出了最优解，但随着提货地点数目的增加，用此方法得到的则不一定是最优解，同时计算量也相当大。而且由于提货是一个比较复杂的问题涉及众多的变量，在我们的模型中尚有许多因素没有考虑在内。比如有的路况比较好，有的路比较很不好走，可以绕道等问题没有考虑在内等。未来可以对模型进行进一步优化，提高物流效率。

参考文献

[1]J.F.Cordeau，M.Gendreau，G.Laporte，J.-Y.Potvin and F.Semet.A Guide to Vehicle Routing Heuristics[J].Journal of the Operational Research Society，Vol.53，2002，pp.512-522.

[2]冯国莉，杨晓冬.基于Hopfield神经网络车辆路径的优化研究[J].信息技术，2006，（7）.

[3]刘芳华，赵建民，朱信忠.基于改进遗传算法的物流配送路径优化的研究[J].计算机技术与发展，2009，（7）.

[4]李萍，高雷阜，刘旭旺.一种基于模拟退火和Hopfield神经网络求解TSP算法[J].科学技术与工程，2008，8（14）：3937-3939.

[5]Grefenstette，John J.Genetic Algorithms for Machine Learning[Z].1994.

[6]Sun，X.，Yang，C.K.，wei，K.，Wu，C-C.，& Chen，L-R.Research on an improved genetic algorithm for logistics distribution path optimization[C]. ACM International Conference Proceeding Series（pp.282-286）. （ACM International Conference Proceeding Series; vol. Part F148260）. Association for Computing Machinery，2018.