带有时间窗的随机机会约束运输问题模型与算法

庞尔国

（兰州交通大学 交通运输学院，甘肃 兰州730070）

运输是实际生活不可或缺的重要组成部分，随着经济的飞速发展，在运输过程中如何选择路径使得所花费的费用尽可能达到最小，是人们亟待解决的问题。当前，企业之间的竞争日益激烈，为提高运输市场的竞争力，在产地与销地之间寻求最优的调配方案，降低运输成本，提高运输效率，能够及时安全地将产品提供给消费者，满足消费者需求，获得更大效益。

传统的运输问题可以转化为一个标准的线性规划，通过表上作业法、单纯形法或lingo软件等求解。在实际的运输过程中，常受到许多因素的限制，如运输时间、选择的路径、费用、运输的安全可靠性等。在传统运输问题的基础上发展形成了多目标运输问题，对于确定性的多目标运输问题有了较成熟的解决方案。虽然多目标运输问题对解决现实问题提供了有效的解决手段，但在一些具有随机性的现实问题中还是不能精确地描述。李珍萍等对带时间窗约束的运输问题进行探讨，但只是限于经典模式下的运输问题，没有涉及到随机条件下的此类问题。

已有许多文章对运输问题进行研究和探索，但在实际运输问题过程中，是一个复杂的受多种不确定因素影响的优化问题，为此，在传统经典运输问题的基础上，增加了运输过程中运输线路能力的约束，运输过程中的时间约束由于一些意外原因，如可供应量、需求量、线路能力、时间等都具有随机性，提出一种基于时间约束的随机机会规划运输问题模型，并利用混合遗传算法求解，进行算例验证。

1 运输问题模型

1.1 传统运输问题

设某物资有m个产地Ai（i＝1，2，…，m），其产量分别为ai（i＝1，2，…，m）；有n个销地Bj（j＝1，2，…，n）；从Ai到Bj运输物资的单位运价为cij（i＝1，2，…，m；j＝1，2，…，n）；

但在一般情况下，产销并不能总保持平衡，当产销不平衡时，问题可转化为产销平衡的运输问题模型。

1.2 带有时间约束的随机机会约束规划运输问题模型

在实际中通常要考虑其可靠性（或风险），即利于（或不利于）事件发生的概率，为此决策者可根据自己的喜好或一定的目的选择建立运输问题的随机机会约束规划模型。机会约束规划理论最早是Charnes和Cooper提出的，其特征是随机约束条件参数至少以一定的置信水平收敛。

Liu在机会约束规划提出之后，给出在随机环境条件下，若决策者希望极大化目标值函数的乐观值，建立如下的机会约束规划模型

其中约束条件中第一个是目标约束，第二个是联合机会约束，a和β是决策预先给定的置信水平。

在现实生活的运输过程中，产地、销地、选择的线路能力、运输时间都存在随机性，但这些约束条件在一定的置信水平成立，虽然已经有一些人对此做了研究，如在需求随机条件下运输问题的机会约束规划模型研究，对运输问题进行了综合实际考虑，但仍缺少时间约束，因此可建立目标函数为最小费用的带有时间窗约束的机会约束规划模型，则有

式中:ulr，vlr为权系数；σl为目标函数的置信水平；αi，βj，ηk为给定的供应量、销量以及线路能力的约束置信水平；tijk为运输过程中需要的时间；Tk为运输过程中最晚到达时间；Tk为软约束；γk为时间约束的置信水平。

2 模型求解并验证

在处理机会约束规划模型时，传统的方法是将他们转化为各自的等价形式，但这种情况只在极少数条件下才能成立，而对于一些较复杂的问题难以处理。因此将神经元网络与遗传算法结合起来，设计了混合遗传算法来求解一般的随机机会约束规划模型。

算法步骤

1）用随机模拟技术为上述不确定性模型函数生成培训输入输出的数据；

2）根据得到的输入输出数据进行训练，训练一个神经网络近似不确定函数生成的训练数据；

3）初始化pop＿size个染色体，其可行性可由经过训练的神经元网络检查；

4）通过交叉变异操作得到新的染色体，子代染色体的可行性可由经过训练的神经元网络检验；

5）利用事先训练好的神经元网络计算所有染色体的目标值；

6）根据每个染色体目标值计算其适应度；

7）通过旋转赌轮选择染色体；

8）重复第4～第7步骤，直到完成给定的循环次数；

9）找出其中最好的染色体作为最优解。

将随机模拟技术作为不确定函数，则有U∶x→（U1（x），U2（x），U3（x），U4（x），U5（x）），产生输入输出数据，其中

训练一个神经元网络（3个输入神经元，15个隐层神经元，3个输出神经元），不断地逼近不确定性模型函数U。然后将已训练好的神经元网络与遗传算法相结合，得到混合遗传算法。

史峰在MATLAB智能算法的30个案例分析中，对遗传算法与神经网络相结合的混合智能算法给出了分析案例，结合书中的分析，通过MATLAB实现设计的混合智能算法。

为验证混合遗传算法对在求解随机机会约束规划模型时的有效性，给出具体的实例，利用MATLAB编制混合遗传算法程序求解，下面给出在求解随机运输问题时的参数:

1）种群规模为50；

2）交叉概率为0.7；

3）变异概率为0.1；

4）评价函数参数为0.05；

5）迭代次数为200；

6）训练次数为3 000；

7）模拟次数为5 000。

实例:给出有两个供应店，两个销售点，两种运输方式的示例。假定目标费用最小，费用、时间、线路能力等约束条件服从某种分布的随机变量，相关参数数据如表1～表3所示。

表1 随机运输问题的单位费用

表2 随机运输问题的时间约束

表3 随机运输问题的约束

在表1中:u（a，b）表示该参数服从区间为［a，b］均匀分布的随机变量；N（μ，σ2）表示该参数服从期望为μ，方差为σ2的正态分布的随机变量；T（a，b，m）为参数服从三角分布的随机变量。

利用MATLAB软件，通过混合遗传算法进行求解，得出最优解为

从以上结果可以看出带有时间窗的随机机会约束规划模型的求解结果比较理想。

3 结束语

从不确定角度对随机参数建立运输问题模型，并在经典的运输问题基础上增加了时间窗约束和线路能力约束，因此模型从经典的运输问题线性规划转变为非线性规划，增加了求解的难度，很难找到最优解，但是本文利用混合遗传算法求解此类非线性规划模型案例，并对解进行优化，可以找到最优解。

［1］ Aneja Y P，Nair K P K.Bicriteria transportation problems［J］.Management Science，1979，25（1）:73～88.

［2］ Moore S M L L J.Optimizing Transportation Problems with Multiple Objectives［J］.Iie Transactions，2007，5（4）:333－338.

［3］ Ringuest J L，Rinks D B.Interactive solutions for the linear multiobjective transportation problem［J］.European Journal of Operational Research，1987，32（1）:96－106.

［4］ 李珍萍，徐清云，栗娜，等.带时间限制的最小费用运输问题的求解方法［J］.运筹与管理，2011（6）:9－14.

［5］ Hitchcock F L.The distribution of a product from several sources to numerous localities［J］.Journal of Mathematics ＆ Physics，1941:224－230.

［6］ 刘宝啶，赵瑞清，王纲.不确定规划及应用［M ］.北京:清华大学出版社，2003.

［7］ 王瑜.随机环境下资源分配与运输问题的机会约束规划模型研究［J］.梧州学院学报，2007，17（3）:16－18.

［8］ 朱萧篥，夏倩.需求随机条件下运输问题的机会约束规划模型研究［J］.交通科技与经济，2015，17（2）:66－68.

［9］ 张先君.不确定运输问题的模型与算法［D］.重庆:重庆大学，2006.