理论教育 扩展情况下的最短时限运输问题数学规划模型

扩展情况下的最短时限运输问题数学规划模型

时间:2023-05-30 理论教育 版权反馈
【摘要】:在最短时限运输问题的基本模型中,从发点Ai到收点Bj的运输时间为一个给定常数tij,与这两点之间的运输量xij的大小无关。该模型可以看成基本的最短时限运输问题的推广,若令αij=0,则得到基本模型。参考文献[48、49]研究了运输时间的附加部分分别为运输量的线性函数和二次函数的情况,为研究最短时限运输问题的扩展情况提供了新的思路。

扩展情况下的最短时限运输问题数学规划模型

在最短时限运输问题的基本模型中,从发点Ai到收点Bj的运输时间为一个给定常数tij,与这两点之间的运输量xij的大小无关。在实际中,运输量经常会影响运输时间,例如运输量越多,装卸车的时间越长,车辆运输的速度越慢,从而运输时间就越长等,因此两点之间的运输时间应该是运输量xij的一个函数。参考文献[48]中考虑了运输量与运输时间的关系,把两点之间的实际运输时间表示成两部分时间之和,其中一部分可以看成是与运输量无关只与两点之间距离有关的空载运输时间,即模型(8-1~8-7)中的tij,另一部分是与运输量有关的附加时间,这部分时间中包括了货物装卸时间、车速对总时间的影响等。由于这部分附加时间与运输量有关,因此可以看成运输量的函数,参考文献[48]讨论了附加时间为xij线性函数,即附加时间等于αijxij时的最短时限运输问题(其中αij是常数,其值的大小取决于从发点i到收点j的运输车辆的状况、道路的状况等因素)。此时,总运输时间等于tij+αijxij。该模型可以看成基本的最短时限运输问题的推广,若令αij=0,则得到基本模型。基于同样的思想,参考文献[49]考虑了当附加时间为运输量xij非线性函数的情形,假设附加时间为xij二次函数,即附加时间等于αijxij2的情形(其中αij是常数),此时总运输时间可以表示为tij+αijxij2。对于这两种扩展情形的最短时限运输问题,参考文献[48]和参考文献[49]分别给出了一个基于网络图最大流算法的迭代求解方法,这种方法计算量大,在短时间内不一定能找到精确最优解,而且以上文献中并没有介绍算法的编程实现过程。

注意到最短时限运输问题扩展情况的特点,通过引入一组与模型(8-1~8-7)类似的0,1变量,可以建立起这类问题的非线性规划模型,以参考文献[49]中的运输时间是运输量的二次函数为例,其对应的非线性规划模型为

模型(8-8~8-14)的约束与模型(8-1~8-7)的含义类似。参考文献[48]中的情形可以写成类似模型(8-8~8-14)的线性规划模型。

参考文献[48、49]研究了运输时间的附加部分分别为运输量的线性函数和二次函数的情况,为研究最短时限运输问题的扩展情况提供了新的思路。在实际中,运输时间和运输量之间的函数关系可能比较复杂,而且对于不同的车型、不同的货物、不同的路况,运输时间与运输量之间的关系可能没有一个统一的表达式。因此,有必要进一步研究运输时间是运输量一般函数的情形,即最短时限运输问题更一般的推广情况。

假设从发点i到收点j的运输时间的附加部分是运输量xij的一般函数,即等于αijfxij),则总运输时间为:tij+αijfxij)。(www.daowen.com)

最短时限运输问题的一般扩展情形可以表示成下列数学规划模型

其中,变量和约束的含义类似于模型(8-1~8-7)及模型(8-8~8-14)。

模型(8-15~8-21)是最一般的模型,模型(8-1~8-7)和模型(8-8~8-14)分别可以看成模型(8-15~8-21)的特殊情况,当模型(8-15~8-21)中的fxij)=0时即得到模型(8-1~8-7),当fxij)=xij2时即得到模型(8-8~8-14)。实际中的其他情况的数学模型,可以通过改变fxij)的表达式形式由模型(8-15~8-21)直接导出。

由于以上模型均为规范的数学规划模型,因此,可以使用现成的数学软件编程直接进行求解。本节利用Lingo软件编写了求解这些模型的程序,并对文献中的实例用软件进行计算。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈