英语论文

2012～2013 学年第一学期

考查课程 专业外语 专业班级 应数09 考核时间 2012、12

A model and its algorithm on container yard problem Xin Hu School of Science, Xi’an University of Architecture and Technology Xi’an, P.R. China,710055 Abstract: There is a problem in container yard, a series of containers is transformed to t he gate of yard waiting f or being assigned a location. T he containers are stacked in three with the lighter below and t he heavier above in order that the lighter container is above when loading t he ship. For the random of arrivals of the containers, it is inner it able to shift containers ( if a lighter container is above a heavier one, then we move the lighter aside to load the heavier, t hen load t he lighter) . How to as-sign a location to t he container to minimize the number of shifting containers maybe a NP problem. There is no precise solution. So we give a heuristic algorithm to the solution. Keywords :Yard; Number of container- shifting AMS: O1773 1 Introduction A ship depart s, t he containers of the ship are sent to t he container wharf which is called / collect ion0. All containers of the same ship are stacked up in the same yard. We are required to pile t he containers three in a stack and load the heavier, then load the lighter. This is called / shifting . The numbers of shifting can lower the loading speed, prolong the parking time, so influence the working efficiency. In order to reduce the rate of shifting, we find a method to assign the locations for a group of containers. 2 Constructing a model According to the yard problem, we construct a mat hermetical model. For a sequence of n containers with a weight number, we pile them up three in one stack one above another. T hen the number of stacks is k = n/3 n is integer times of 3 k = n/3+1 n is not integer times of 3 We let the lighter container above and the heavier below. T he container with the same number can be piled up in one stack . So the there weight numbers of one stack make a sequence from the bottom t o top. There is an inverse number for every stack. T he problem becomes that how to as-sign a location t o every container so that the sum of the inverse numbers of k stacks is minimum. The number in a container represents the weight of the container. Usually, the containers are divided In to several groups according to their weight. T he containers in the same group can be piled up in the same stack in which t he inverse number is zero. For ex ample, at the yard gate, the containers are divided in to three groups, one group wit h the weight 0~ 10 tons; another with 11~ 17 tons; else another wit h 17 tons or above. Considering the weight of a container is not an integer, it is difficult to make a computer program, and it. s impossible to arrange the containers strictly by their w eights. We divide the containers into nine groups by their weight. So every container has a number from 1 to 9. T he bigger the number is, the heavier the container is. T he containers with the same number have the same weight and the inverse number of three containers of t hem is zero. The minimum of t he inverse number is corresponding to that of the shifting number. another group of containers. In this way, we divide the containers roughly in to several groups. Secondly, Find the best set for the group including one or two points by the way used in the first step. Thirdly, according t he sequence of arrival, the containers in the same group are piled up in three one above one. Repeat t he second step until there is not t he combination which inverse number is 0. Lastly, stack the remaining containers in three one above one by their sequence. For example, twenty- three containers come in the sequence: 3, 5, 7, 1, 4, 2, 9, 9, 8, 6, 4, 2, 7, 9, 8, 3, 5, 8, 9, 7, 9, 8, 1. T he number represents the weight class of the container. Now we stack the containers in three and minimize the shifting number. Set up the rectangular coordinate system, we have 23 point s which x- coordinate is the sequence of arrival and they coordinate is the weight number representing the weight class. By the first step, from the point ( 1, 3) , we obtain t he first group A 1= { ( 1, 3) , ( 2 , 5) , ( 3 , 7 ) , ( 7, 9 ) , ( 8, 9 ) , ( 14, 9) , ( 19, 9 ) , ( 21 , 9) } From the point ( 4, 1) , we obtain t he second group: A 2= { ( 4 , 1) , ( 5, 4) , ( 9, 8) , ( 15, 8) , ( 18, 8 ) , ( 22,8) } Other groups are let the lighter below and the heavier above as much as possible so that the heavier is loaded firstly. Be- cause the containers arrive at the yards gate randomly, the workers assign a location number to the containers according to t he sequence. It is unavoidable to locate t he heavier below and t he lighter above. In t his case, we must put the lighter aside T he problem is complicated because ( 1) the method to pile n containers in k stacks wit h the minimizing shifting number is not unique.This problem maybe N- P difficult problem, that is, the optimal solution is not found by t he computer [ 3] . ( 2) a container arrives at the container yard randomly. We assign a posit ion to the container only by t he preceding containers positions. So t he shifting is not avoidable. This paper gives an approximate algorithm t o assign posit ions to a group of containers. Firstly it derives a rough solution, then improves it step by it. 3 The algorithm Set up at dimensional rectangular- coordinate system, let a point in t he plane represent a container. The x- coordinate represent s its order number, the y- coordinate represents it s weight number. We obtain many points in the coordinate systems . Firstly rough division: let the point with the smallest x- coordinate be the first point , scan t he area which is a infinite rectangle with the first point be the most left and lowest point , find t he nearest point according to t he x- coordinate in t he area, let it be t he second point, link the second point into t he first point by a line segment . Then repeat the steps above. Scan the area which is a in- finite rectangle wit h t he second point be t he most left and lowest point , find the nearest point according to the x- coordinate in the area, let it be the third point , link this point in to the second point by a line segment . T he process continues until t here is not any point in the right and above area. Then we obtain a group of point linked by line segments .This group of containers can be piled up in a stack in which t he inverse number is zero. Let the point wit h the smallest x- coordinate in the remaining points be the first point , scan its right- above area, find the point which is nearest to the first point ac- cording to x- coordinate, let it be t he second point, link the two point s. Repeat the above steps to get A 3= { ( 6, 2) , ( 10 , 6) , ( 13, 7 ) , ( 20, 7) } A 4= { ( 11, 4 ) , ( 17, 5) } A5={ a { ( 12, 2 ) , ( 16, 3) } A 6= { ( 24, 1 ) } F or the group A 6 wit h only one point, there is no point in its right- above and left- below area.Check the next group A 5 with two points. We find a point ( 17, 5) in it s right- above area and obtain a set S 1= { ( 12 , 2 ) , ( 16, 3 ) , ( 17 , 5 ) } . Cancel t he point ( 17, 5) from the group A 4, then A 4 has only one point ( 11, 4) . By the w ay in t he first step , we obtain another set S 2 = { ( 11, 4 ) , ( 13, 7 ) , ( 14,9) } . At last , w e obtain the other set s S 3= { ( 6 , 2) , ( 10, 6 ) , ( 20, 7) } S 4= { ( 4 , 1) , ( 5, 4) , ( 23 , 1) } S 5= { ( 15, 8) , ( 18, 8) , ( 21, 9 ) } S 6= { ( 1 , 3) , ( 2, 5) , ( 3, 7) } S 7= { ( 7 , 9) , ( 8, 9) , ( 19 , 9) } S 8= { ( 9 , 8) , ( 22, 8 ) } Therefore, the 23 containers are piled up 8stacks. 9( 2) 5( 17) 9( 14 )9( 19 )7( 20) 1( 23) 7( 3) 8( 18) 8( 15) 3( 16) 2( 12) 7( 13) 4( 11) 8( 22) 8( 9)9( 8) 9( 7) 6( 10) 2( 6) 4( 5) 1(4) 5( 2) 3( 1) 7( 13) 4( 11) T he number outside the parentheses represent s the w eight , the number inside t he parentheses rep- resent s t he sequence of t he container. T he shifting number is 1. T his is inevitable because t he lightest container arrives lastly. Reference: [1] BANK S B. Three results in the value-distribution theory of solutions of linear differential equations [J].Kodai Math. J., 1986, 9(2): 225{240. [2] BANK S B, LAINE I. Representations of solutions of periodic second order linear differential equations [J]. J. Reine Angew. Math., 1983, 344: 1{21. [ 3] L IU Ding- ming . Container Transform Technology Dictionary[ M ] . Beijing : People Publishing Company , 19911 [ 4] XIA O Zhong- x i. Harbour Business Management[ M ] . Dalian: Dalian Maritime University Press, 19921 [5] YA NG Hua- fei, WANG Chao- rui. Combination Mathmatics and Its Application[ M ] . Beijing: Beijing University of T ech.Press, 19921 E-mail: 578821555@qq.com 集装箱堆场问题的一个数学模型及算法 胡鑫 西安建筑科技大学 理学院数学系 中国 西安 710055 摘要: 讨论了集装箱堆场中一个常见的问题,即若干个不同重量的集装箱按一定顺序到达,要将这些箱子三个一垛码好,先到先码,后到后码,尽量轻箱在下,重箱在上,以保证装船时重箱在下,轻箱在上。因为在大多数情况下,无论怎样码放,都免不了捣箱。因此,如何码放才能使捣箱数最小是值得研究的问题,此问题可能是N- P难的问题,所以本文给出了这一问题的一个启发式算法。 关键词: 堆场; 集装箱移动数量 CMS：O177.3 1介绍： 集装箱的船舶离开，被送到了集装箱码头被称为/收集ion0。同一条船上的所有容器都堆叠在同一个院子里。我们需要堆积了三栈和容器装载较重的，然后加载了较轻的。这就是所谓的/移位。移位的数目可以降低加载速度，延长的停车时间，所以影响了工作效率。为了减少移位的速率，我们发现一组容器的分配的位置的方法。 2 构建模型： 据院子里的问题，我们构建了一个垫密闭模型。如果在n个容器的重数的序列，我们堆放了三个在一个堆栈一个在另一个之上。 Ţ当数栈 K = N /3 n是3的整数倍K= N/ 3 +1，n不是3的整数倍的整数倍 让较浅的容器上面，较重的下面。他具有相同数量的容器可以堆放在一个堆栈。因此，有重号的一个堆栈一个的序列从底部到顶部。有逆数堆栈。T他问题变成了如何为签名的位置，使每个容器k堆叠的倒数的总和为最小。 在一容器中的数字表示在容器的重量。通常情况下，容器被划分进行几组，根据他们的体重。他在同一个组可以堆容器在同一个堆叠，其中T倒数是零。例如，在院子里的门，容器被分成三组，一组用权重为0〜10吨，另一个有11〜17吨;用17吨或以上的。考虑的容器的重量是不是一个整数，它是难以使一个计算机程序，它不可能安排的容器严格按照其W八。把容器分为九个组，他们的体重。因此，每个容器都有一个从1到9的数字。T他数字越大，较重的容器。T他用同样数量的容器具有相同的重量和的倒数三个容器的t下摆为零。 吨数的逆数的最小值是对应换档号码。另一组的容器。在这种方式中，我们把容器大致在几组。 第二组包括一个或两个点的方式的第一步，寻找最好的一套。 第三，根据“序列的到来，在同一组中的容器堆放在3以上。重复了第二个步骤，直到没有了组合，逆数为0。 最后，三个高于它们的顺序栈的剩余的容器。

例如，容器23中的序列：3，5，7，1，4，2，9，9，8，6，4，2，7，9，83，5，8，9， 7，9，8，1。他数代表的权重类的容器。现在，我们在三个堆叠的容器，尽量减少转移的数量。

建立直角坐标系中，我们有23个点s，x坐标是到达的顺序和他们协调为代表的权重类的权数。

由所述第一步骤中，从点（1，3），我们得到了第一组，A 1= {（1，3），（2，5），（3，7），（7，9），（8 ，9），（14％，9），（19，9），（21，9）} 从点（4，1），我们得到T他第二组：A 2 ={（4，1），（5，4），（9,8），（15，8），（18，8）， （22,8）}其他组让较轻的下面和上面尽可能地较重，使较重的首先被加载。导致容器到达随机码门，工人分配一个位置编号的容器中，根据T他序列。这是不可避免的定位吨，他较重的下面和t他更轻以上。在他的情况下，我们必须把较轻的留出了问题很复杂，因为

（1）Ň容器堆在k堆叠用最小转移数量是不unique.This的问题也许N-P难题，那就是，没有找到最佳的解决方案是由T计算机[3]。

（2）的容器到达集装箱堆场随机。我们分配断定离子的容器，只能由他前面的容器。位置。所以T他转移是无法避免的。

这种近似算法，指定断定离子的一组容器。首先，它派生出一个粗糙的解决方案，进而提高一步。

3算法：在三维直角坐标系，让一个点，他在T飞机代表一个容器。x坐标代表它时

的订单号，y坐标表示其权数。我们可以获得很多点的坐标系中。

首先粗略的划分：让点最小的x坐标是第一点，扫描，这是一个无限的第一点是最左边的点与最低点的矩形，T他最近的点按t，X-协调，他在T区，让它成为他第二点，链接，第一点，第二点到线段。然后重复上面的步骤。这是一个在有限矩形机智HT的第二点是t他最左边的点与最低点，找到距离最近的点的x坐标在该地区的扫描区域，让它成为第三点，这点链接到第二点的线段。T他过程继续进行，直到t这里是没有任何点的右侧和上述区域。然后，我们得到一组点segments.T他的研究小组的容器堆放在一个堆栈，其中T倒数是零线相连的。让点用最小的x坐标剩下的点是第一点，它的右上面的区域中，找到的第一点，根据x坐标的点，这是最近的，让他第二点，连接这两个点s。重复了上述步骤，T O得到 A 3 = {（6，2），（10，6），（13，7），（20，7）} A 4 = {（11，4），（17，5）} A 5 = {（12，2），（16，3）} A 6 = {（1）}

F或A组6机智h只在一个点，有没有在它的右以上和左下面的area.Check A组5连得两分。我们发现权利上述区域中的一个点（17，5），和获得的集合S 1 = {（12，2），（16，3），（17，5）}。取消了点（17，5）从组A 4，A 4只有一个点（11，4）。他在T的第一步中，我们得到另一个集合S 2 = {（11，4），（13，7），（14,9）}。 最后，W E获得另一组 小号3 = {（6，2），（10，6），（20，7）} S 4 = {（4，1），（5，4），（23，1）} 小号5 = {（15，8），（18，8），（21，9）} 小号6 = {（1，3），（2，5），（3，7）} 小号7 = {（7,9），（8，9），（19，9）} S 8 = {（9,8），（22，8）}

因此，23个集装箱堆放8stacks。 9（2）5（17）9（14）9（19）7（20）1（23）7（3）8（18）8（15）3（16）2（12）7（13）4（ 11）8（22）8（9）9（8） 9（7）6（10）2（6）4（5）1（4）5（2）3（1）7（13）4（11） 他括号外的数代表S的w 8吨，他括号内的数字代表了ST序列，容器。 T他转移数为1。T他是不可避免的，因为他最轻的集装箱到达最后。 参考文献： [1] BANK S B. Three results in the value-distribution theory of solutions of linear differential equations [J].Kodai Math. J., 1986, 9(2): 225{240. [2] BANK S B, LAINE I. Representations of solutions of periodic second order linear differential equations [J]. J. Reine Angew. Math., 1983, 344: 1{21. [ 3] L IU Ding- ming . Container Transform Technology Dictionary[ M ] . Beijing : People Traffic Publishing Company , 19911 [ 4] XIA O Zhong- x i. Harbour Business Management[ M ] . Dalian: Dalian Maritime University Press, 19921 [5] YA NG Hua- fei, WA NG Chao- r ui. Combination Mathmatics and Its Application[ M ] . Beijing: Beijing University of T ech.Press, 19921 电子邮箱：578821555@qq.com