胡修宇 王君悦 傅馨峤

摘 要：随着物流行业的快速发展，运输问题也受到广泛关注。针对运输问题的一般模型，本文对表上作业法、图与网络算法和遗传算法三种算法并进行了对比分析。同时通过结合某运输企业的实例，对模型添加了时间窗和转运站的约束，并利用MATLAB进行求解。在有时间窗约束下，通过引入惩罚函数使问题得到简化，从而实现多角度寻找最优解。

关键词：运输问题;图与网络;遗传算法;时间窗约束;惩罚函数

运输问题是社会经济生活和军事活动中经常出现的优化问题。随着物流行业的快速崛起，其中涉及的运输问题受到了广泛的关注。如何制定调运方案，将物资运往指定地点，而且实现运输成本最小，即为运输问题。运输问题是特殊的线性规划问题，它是早期的线性网络最优化的一个例子。本文通过对比表上作业法、图与网络算法和遗传算法三種算法并考虑转运站和时间窗约束从多角度分析物流过程中存在的运输问题。

一、运输问题模型及求解概述

1.运输问题基本模型

2.求解概述

本文只讨论线性运输问题，线性运输问题的含义是：从不同的供给起点或来源向不同的终点运送同一种物品，每个终点需要特定数量的物品。问题是：如何分配在每个起点的供给，以便在满足每个终点需求的条件下，优化某一个或几个目标，例如运输费用最小，运输时间最短等。

二、算法探索

算法分析：

对于最基本的运输问题模型，可以使用运筹学求解器GAMS、Lingo进行求解，求解器其本身调用的IP或MIP求解的算法，为了探究更高效的算法，本文总结比较了三种算法。

算法1 表上作业法

表上作业法是一种依赖于手工作业的方法，算法的流程图如下：

表上作业法通常情况下只适用于规模比较小的问题进行直观地演算，当规模较大时，表上作业法的效率很低，而且易于出错，对于实际问题而言不宜于实际操作，仅在教学中方便演示线性规划问题的细节。

算法2 图与网络方法

该算法抛弃了图上作业表格的想法，从图论的角度出发，将产地和销售地视为网络中的节点，节点之间的有向弧表示两地之间可以连接，并且弧上的权值代表两地之间的运输费用或者运输时间，同时，在产地和销地两侧分别加上虚拟节点s，t（如图2），虚拟节点与产销地节点之间权值为0。

下面根据图论中的最小费用流算法，通过在原图上建立增广链，并在增广链上进行调整，循环迭代，直到找不到增广链，即找到满足条件的最小费用流。

使用图论的方法，大大简化了问题的本身，易于编程实现，使用范围很广阔，理论上可以求出任何一个问题的最优解（在存在最优解的条件下），但往往会耗费大量的计算资源，但是在实际工程中有时不需要十分精确，在较少的计算资源条件下获得最大的效益是实际中追求的目标。

算法3 遗传算法

遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。遗传算法通常实现方式为一种计算机模拟。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。

在本问题的遗传算法中，染色体是基于矩阵的表达。

由于遗传算法本身依赖于一定的初始种群特征，如果初始种群的生成效果不好，有可能会导致收敛过快或过慢，为了减少这种影响，我们认为规定只迭代50次，如果在50次之内就收敛了，那么就以那个为准，如果没有，就在第50代中寻找最好的那个解。

算法分析：

对于以上三种算法，我们从准确性，算法效率两个角度来评价：

1.从准确性来说，表上作业法和图论中最小费用流的方法都是对于问题的精确求解，而遗传算法本身属于启发式的搜索算法，当迭代次数足够多的时候，其最优解和精确解差异不大;反之，迭代次数或者中间某些参数选取的不合适的时候，其准确性上有所欠缺。

2.从算法效率上来说，我们做了以下实验，对同一个问题，不同的规模下，程序消耗时间的多少（计算100次）

三、案例分析

某运输企业主要从南京仓库、北京仓库、成都仓库、广州仓库、沈阳仓库发货提供给全国各地区的主要58个门店，中途有3个中转站，运转货物到门店。

针对这个实际问题，本文考虑了三种情况：

（1）无时间窗约束下的转运

（2）有时间窗约束下的转运

（3）对转运站的合理利用条件下上述约束的转运

注：时间窗是指一定的时间约束。

1.必须过转运站无时间窗问题

该问题等价于运输基本模型问题套用两次，可以利用图与网络方法快速求解，在这里不再一一赘述。

2.不必过转运站且无时间窗问题

首先，将带有转运环节运输平衡问题转化为一般运输平衡问题，其步骤如下：

这样就化为无时间约束的运输问题，就可以进行求解。

对于新增加的时间窗约束，可以用一个新的函数来转化，本文称之为时间约束函数，每当找出一条最小费用增广链的时候，就利用该函数来进行判断，是否满足时间窗的条件，如果早到或者晚到，都需要进行惩罚即费用的增加，不断循环，直到找不到最小费用增广链为止。最后计算总的费用。

4.不必过转运站有时间窗问题

该问题可以由上述问题三经过变换求解，同样可以利用图论快速求解，这里就不再赘述。

四、总结

1.在处理无时间窗的运输问题时，无论是否带有转运站，都可以将其转化为一般运输问题进行求解，然后求解。

2.在处理有时间窗的运输问题时，通过增加惩罚函数，将其转化为单目标函数进行求解。

3.由问题案例出发，深入探讨运输问题，对于有无时间窗，有无转运站的情况分别进行了讨论研究，从特殊问题一般化等角度分别切入，分别应用遗传算法，转化问题等多种算法进行运算，得到最终结果，对比不同算法发现，在处理运输问题时更应该突破传统课本束缚，从更多角度进行求解，对比得到最接近最优解的可行解。

参考文献：

[1]邹宗峰，张保全.带混合时间窗的多目标危险化学品运输路径优化.中国安全科学学报，2012，22（04）：第83-89页.

[2]吕学伟，杨斌，黄振东.混合时间窗约束下多式联运最优路径选择研究.铁道运输与经济，2018，40（08）：第6-11页.

[3]王晓林.时间窗约束运输问题的一种算法，中国企业运筹学学术交流大会，2007.中国重庆：第4页.

[4]周婷，周爱莲.基于时间成本的地下物流配送路线优化模型.物流工程与管理，2016，38（08）：第60-62+87页.

[5]覃运梅，郝忠娜，王玲玲.零担货物的物流配送优化方法.柳州职业技术学院学报，2006（02）：第24-26页.

作者简介：胡修宇（1998.12- ），男，汉族，山东菏泽人，北京交通大学，本科在读，研究方向：交通运输（铁道运输方向）