提高物流车辆调度效率的数学模型与实际应用？

本文介绍了基于柔性作业车间问题模型的卡车调度方法，通过混合整数线性规划优化卡车在生产现场的任务执行顺序，旨在减少完工时间。研究表明，该方法相比先进先出原则可提升16%的效率。此外，文章还探讨了随机到达时间等不确定性因素对调度的影响，并提出鲁棒模型以应对实际挑战。

现实生活中，生产现场由于缺乏科学的管理，卡车的调度往往效率不高，容易出现拥堵现象。那么，是否可以通过数学模型对该问题建模，提高其运作效率呢？本文介绍了卡车调度问题的数学模型，通过算例分析验证：较先进先出的调度方法，数学模型调度法可提高16%的运作效率。

回答提纲：

本文旨在介绍一种解决现实场景中卡车调度问题的方法。该方法基于柔性作业车间问题(flexiblejobshop)模型，使用混合整数线性规划来解决此类问题。

现实场景简述如下：卡车到达生产现场，需要在现场完成一些必需的任务。在一个工作站上处理一个任务，一个任务对应一个工作站。在生产现场有多个工作站，每个工作站可由多个资源组成，下文将使用停靠站(dock)来表示这些资源。在某些工作站的前面，有可供卡车等待的缓冲区。某些缓冲区仅专用于一个站，而共享缓冲区可用于多个站。在某些没有缓冲区的工作站上，提供了无限的等待空间。

在这种情况下，这个生产现场有意优化卡车的运行。这项研究的目的是为每辆卡车找到一条最佳路径，以便在卡车到达现场后快速完成所有任务。该卡车调度问题被建模为柔性作业车间调度问题(flexiblejobshopscheduling:FJSS)，其目的是最大程度地减少完工时间(makespan)。作业车间调度问题(jobshopscheduling:JSS)是计算机科学和运筹学中的一个优化问题，方案是将作业在特定时间分配给资源。柔性作业车间调度问题是作业车间调度的扩展。在作业车间环境中，每个作业在所有机器上都有预定的处理顺序，因为每个机器只能执行某个操作。而在柔性作业车间环境中，则有一组有能力的机器可以执行这个操作。在上述环境中，整个生产现场可以看作是一个车间(JobShop)。卡车需要的各项操作可以看作是任务(Job)。工作站上的多个资源被认为是可以在工作站处理所需任务的一组有能力的机器。这样一来，卡车调度就可以看作卡车经过预定工作站完成任务次序的规划，目的是减少整体的完工时间。

问题中的要素是：大门，由停靠站(dock)和缓冲区(buffer)组成的工作站(station)。所有元素的简化图举例如下图。该现场上有四个工作站。在每个站，都有两个缓冲区和两个停靠站(dock)。所有这些元素均按顺序命名和编号。缓冲区和停靠站(dock)聚集在工作站上。例如，缓冲区1、2和停靠站1、2属于工作站1。它们只能用于在工作站1处理的卡车。进来的卡车需要被分配到相应的工作站，以完成所有必要的操作(operations)。这种调度问题的实质是为卡车分配在每个工作站的时间间隔，以完成相应的任务。由于每个工作站有多个停靠站(dock)，因此还需要分配停靠站(dock)。可能会有这样的情况，当卡车到达车站时，所有停靠站都被占用，因此，卡车必须等待在属于该工作站的缓冲区。

1.卡车在大门口登记的时间可以忽略，它可以在大门外面等待。大门外有无限的等候空间。

2.每辆卡车访问工作站的顺序是预先确定的。

3.在每一个工作站上有两个过程。首先是在缓冲区上等待，其次是在停靠站上进行操作。这并不意味着卡车必须在每个工作站等待。如果没有等待，缓冲区上的处理时间将为0。停靠站上的处理时间为实数。

4.每个工作站的停靠站和缓冲区数量是确定的。每个工作站的停靠站都是一样的，即，卡车的处理时间不依赖于停靠站。

5.在处理过程中，每个操作都不能中断，即不允许进行任何抢占。

6.假设所有参数：到达时间，处理时间等都是确定的，

7.停靠站之间，停靠站和缓冲区以及工作站和大门之间的行驶时间可以忽略。

以本文2.1中的场景为例，我们可以使用一些模拟数据利用以上模型，在GAMS(GeneralAlgebraicModelingSystem)软件中进行编码，并用CPLEX求解器求解得到一个卡车调度方案。在这个场景里有4个工作站，每个工作站上有两个停靠站和缓冲区，即m=16。如下表所示，有8辆卡车需要排程，即n=8。表格第二列给出了它们到达生产现场的时间。由于卡车的操作与工作站相关，所以可以用工作站的顺序来表示各项操作的顺序。比如，卡车i1的整个流程包含8项操作。第一个操作(j=1)和第二个操作(j=2)是在工作站1(s1)上进行的。第一个操作是在s1上等待，缓冲区1和缓冲区2都有能力执行，但这并不代表卡车i1必须在缓冲区等待。因为对于任何一辆卡车，在缓冲区的操作时间参数都被设置为0。只有在变量等待时间不为0的情况下，卡车需要在缓冲区等待。第二个操作是在s1上进行处理，停靠站1和停靠站2都有能力执行。第二个操作是由停靠站1或停靠站2执行取决于解出的变量Vijk的值。卡车的第三和第四个操作是在s2上进行的。缓冲区3和4有能力执行第三个操作，停靠站3和4有能力执行第四个操作。依此类推，剩下的操作依次在s3和s4上完成。

输入以上参数，GAMS给出的一个最优解如下面的甘氏图所示。

整个过程的最小完工时间是36个时间单位，相比下面的在先进先出原则下的规划可以节约7个时间单位，效率提高16%。

在此卡车调度问题中，某些参数可能不受控制。例如，卡车的到达时间和处理时间。由于交通条件的不同，卡车可能比预期的到达时间更早或更晚。处理时间可能会受到机器状况(例如机器停机时间，维护等)的影响。这些不确定性会干扰卡车的时间表。在现实中，随机到达时间一直是困扰该生产现场卡车管理的最具破坏性的因素。我们以随机到达时间为例，放松假设条件6，扩展文章第二部门的模型，引入情景(scenarios)索引可以将问题的随机性考虑到鲁棒模型中。此处的情景即多组卡车的到达时间，每组情景包含了所有卡车的到达时间。

[1]Zhang,G.,X.Shao,P.Li,andL.Gao(2009).Aneffectivehybridparticleswarmoptimizationalgorithmformulti-objectiveflexiblejob-shopschedulingproblem.Computers&IndustrialEngineering56(4),1309–1318.

更多关于机器学习，人工智能，运筹学的前沿信息可以关注『运筹OR帷幄』大数据时代的运筹学

以上内容由58汽车提供。如有任何买车、用车、养车、玩车相关问题，欢迎在下方表单填写您的信息，我们将第一时间与您联系，为您提供快捷、实用、全面的解决方案。