卡车装运的最优效率模型.doc

数海-云嫣小屋 / 19-12-11卡车装运的最优效率模型（第五组：刘一贞 黄伟 陆星）指导老师：方老师摘要：本文在详细分析的基础上，通过合理的假设并引进装卸货原则，将问题转化为较简单的优化问题，运用了排队论与优化的数学思想和递推的计算方法，给出了数学模型平均等待时间随拖车到达的时间间隔的变化关系，再求最小值Min(w)；而第二小问，是在一问的基础上，规定了24小时的限制时间以及准时到达的定义，求得了两种情况下的时间界限Max(t1)与Max(t2)。一、问题重述联合集装箱运输（ACM）是一个卡车公司，它提供昼夜货物运输。公司有一个调度网，有许多集装箱处理中心（ICPC，以下简称中心）。在每个中心，进来的货物在卸载口卸载后，到这个中心的货物就认为是收到了。其他的货物被分到不同的接运门，以准备运到不同的地方。每个中心有许多卸载口，拖车可以在此卸载。当拖车数目大于卸载口数目时，进来的拖车将要排队等待，直到有一个门空出来。一辆拖车可能有几个中心的货物。对于进入卸载口的拖车来说，只装有当前中心货物的拖车比需要接运的拖车优先级要低。同样的，接运拖车中，后到的拖车比先到的拖车进入卸载口的优先级要低。如果需要卸载和装运，不考虑货物的大小和数量，卸载的时间和装运的时间都是2小时。当接运拖车装满货物后，或是这一天需要运到那个目的地的货物全部运上了拖车，拖车就立即开始向下一个目的地出发。货物的大小按照拖车容量的百分比计算。为了使拖车尽量装满，每辆车上的货物尺寸尽量选择一致。在拖车离开卸载口或接运口，队列中另一辆又进入，这之间不需要时间。在接运口，拖车永远不会短缺。为了帮助公司估计网络的效率，请你决定拖车在等待进入卸载口的平均等待时间以及确定哪些货物没有准时到达中间站或目的地。二、模型假设1. 各中心规模一样；且针对调度网络而言，各中心的地位相同。2. 各拖车的装载量与性能都相同。3. 货物种类不同决定了其尺寸也不同。4. 装卸货原则： 假设有两种装货方式：整装和混装。 整装是指同中心同尺寸的装货形式：混装是指不同中心的同一尺寸的装货形式。 为了使司机的工作程序变得较为简单,在装车时先整装后混装。 为了提高效率,同一中心不同卸载口等待的队长相同。 5. 准时到达：是指总公司当天发出的货物在当天（24小时）内完成卸载。网络效率：是指在当天内的等待时间，越短则效率越高。三、符号定义1. n中间集装箱处理中心的个数2. m不同尺寸的货物种类3. s各中心的装卸口数4. A(i,j) 第i中心所需的第j种货物的数量 (i=1n, j=1m)5. kj 第j种货物相对于拖车容量的百分比 (j=1m) 6. L(i,t) 第i中心的任一卸载口到t时刻等待车的长度 (i=1n)7. w(i,t) 第i中心的任一卸载口到t时刻拖车等待总时间 (i=1n)8. ai 在24小时内到达第i中心任一卸载口的拖车数目 (i=1n)9. t(i1,i2)第i1中心到第i2中心所需的最短时间 (i1,i2=1n)10.t(o,i) 总公司o到第i中心所需的最短时间 (i=1n)11. 拖车到达任一卸载口的时间间隔。四、问题分析（一）公司运作过程对于一中心而言，货物有直接从总公司来的和从其它中心转运来的；而拖车在整个运作过程可分为两种情况，即整装与混装。具体如下:整装: 总公司装货 卸载排队卸载混装: 总公司装货 卸载排队 卸载 装车等待 装货 卸货(附: 表示运输)（二）排队的优先级别混装拖车对整装拖车具有绝对的优先权，即混装拖车可以不经过等待直接卸货；相同类型的拖车之间的优先级别是相同的，符合先到先服务原则。（三） 假设某中心的某一卸载口在t时刻驶来一台拖车，现分析其对系统总等待时间的影响,如图（1、2）所示： 图（1） 图（2）（附： 新到的拖车； 排队的拖车； 卸载口）若为整装车，则系统等待时间增加的部分就是新到的那辆车的等待时间，即w(i,t+t)=w(i,t)+2L(i,t)(2)若为混装，根据绝对优先权原则，原来整装的拖车都要后退一个位置；其实也就是说，混装车插到第一辆整装车的位置，而原来排在第一位的整车就排到最后。则系统等待时间增加的部分就是新到的拖车的等待时间加上第一辆整装车后退所增加的时间，即w(i,t+t)=w(i,t)+2L(i,t)综上分析可知，对于一个卸载口，不管到达的是整装的还是混装的，对于系统的总等待时间的影响是一样的。但对于接运车来说，为了减少装货的等待时间，应使该接运口的货物尽快集够一车或这一天的货物全到达。而对于该公司来说，整装还是混装并不影响其效率。因而，可设混装车的到来是连续的。五、模型建立与求解(一).平均等待时间的优化模型根据上面的分析，该问题可转化为一种简单的情况：即让一天内到达卸载口的混装车先到达，接着才是整装车的到来，这样就转化为“先到先服务”的排队问题。现对第i个中心的任一卸载口进行分析：0时刻从总公司发来第一辆拖车，每间隔t时间又发来一辆车，一直到本中心的货物全部运到为止。假设 = ； u= ； w(i,0)=0 ；L(i,0)=0则：到该卸载口的总车辆数为：最后一辆拖车发出的时间为： 再过t时间该卸载口的等待卸载的队伍长：L(i,t+t)=L(i,t)+-u=L(i,t)+1-由上式的递推关系可得： L(i,t)=L(i,0)+ (1-)=(1-) （*）该卸载口到t+时刻总等待时间：w(i,t+t)=w(i,t)+2(L(i,t+t)-1)由上式的递推关系式可得,该卸载口的总等待时间为：w(i,ait)=w(i,0)+2(L(i,ait)+1-ai)=ai(1-)ai(1-)+1-2ai而整个网络系统的总等待时间即为所有卸载口的时间之和，而平均等待时间，即Min 在货物量、货源与各中心的距离确定的情况下，该联合集装箱运输（ACM）公司的网络效率只与该公司的发车时间有关。现用Matlab软件对最小值进行求解，得：当时，拖车在等待进入卸载口的最小平均等待时间为：Min由上式可知，平均等待时间还与、有关；当这些条件一定时，该公司可通过调度整个网络的发车时间，即调节拖车到达各卸载点的时间间隔来使网络的平均时间最短。（二）时间界限根据假设6可知，不准时到达中间站或目的地，就是指一拖车在第24时刻没有完成卸载：仍在等待或还没卸载完。现对第i个中心的任一卸载口进行分析，求出从哪一时刻起发出的货物不能准时到达。设从总公司发车的时间；从任一中心接运口的发车时间从总公司发出的车： （a）从任一中心接运口发出的车： (b)把上面L(I,t)的表达式（*）带入上式，得： (a) (b) 可见，时间界限与拖车到达的时间间隔有关。对应一确定的时间间隔，就可知道最大的时间界限 、。总公司0在Max()之后发车就不能准时到达；而接运口在Max()时刻之后发出的拖车也就不能准时到达. 当时， Max(Max所以，该ACM中心估计为了到达网络的最高效率，总公司的发车时间间隔为,最小的平均时间为Min()。而相应的不能准时到达中间站或目的地的时间界限分别为：从总公司发出的拖车的时间为Max()，从接运口发出的拖车的时间为Max().六、模型的评价、改进与推广本文先在假设的前提下，运用排队论与优化的数学思想和方法，将问题转化为求极值以及求时间界限的问题。整个模型较为简单，计算量也较小。对于由总部统一控制运作的服务系统，具有较大的指导作用。在建模过程中，提出了一个装货原则，对货物混装的情况作了较为简单的处理，这就简化了模型；但在本模型中，接运车的利用率较低，在具体使用中，该网络系统可通过调整接运车的比例来提高效率。对于一个开放的