CN100428247C - An Optimal Method for Reducing Container Overturning During Shipment - Google Patents

Abstract

Translated fromChinese

本发明公开了一种装船时减少集装箱翻箱量的优化方法，由航次和港口决定装船顺序时的步骤如下：(a)确定模糊目标状态；(b)搜索确定目标状态；(c)确定具体翻箱步骤。在上述基础上进一步考虑集装箱重量时先执行步骤(a)、(b)把得到的确定目标状态作为一个新的初始状态，对新的初始状态中集装箱数目进行分类统计，同航次、同港口、同重量的集装箱为同一类别，然后重复进行(b)、(c)步骤的操作。利用本发明轮胎吊司机在等待集卡的空闲时间进行有目的翻箱，可以将无序的集装箱堆放状态整理为有序，集卡不必经过等待可以直接从堆场运输集装箱装船，从而减少装船所用的时间，并在很大程度上提高了装船准确率。

The invention discloses an optimization method for reducing container overturning during shipment. The steps for determining the shipment order by voyage and port are as follows: (a) determine the fuzzy target state; (b) search to determine the target state; (c) Determine the specific rummaging steps. On the basis of the above, when further considering the weight of the container, first perform steps (a) and (b) to use the obtained determined target state as a new initial state, and classify and count the number of containers in the new initial state, the same voyage, the same port, Containers with the same weight belong to the same category, and then repeat steps (b) and (c). Utilizing the tire crane driver of the present invention to carry out purposeful overturning during the idle time of waiting for the collection truck, the disordered container stacking state can be sorted into order, and the collection truck can directly transport the container from the yard for loading without waiting, thereby reducing the loading and unloading time. The time used by the ship and greatly improve the accuracy of shipment.

Description

Translated fromChinese

一种装船时减少集装箱翻箱量的优化方法An Optimal Method for Reducing Container Overturning During Shipment

技术领域technical field

本发明涉及集装箱码头、堆场的自动化生产操作方法，更具体地说是涉及一种通过计算机安排生产操作减少装船时集装箱翻箱量的方法。The invention relates to an automatic production operation method for a container terminal and a storage yard, and more specifically relates to a method for reducing the amount of container overturning during shipment by arranging production operations through a computer.

背景技术Background technique

集装箱码头的效率是衡量一个码头生产能力的最重要的指标，能否高效率的装卸船对于减少运输成本，遵守船期有着重大的影响。由于出口箱由道口进入堆场时的顺序是随机性的，海关多采用的先进港再查验的流程，以及堆放出口箱时多采用集卡司机或轮胎吊司机个人经验，无法全面考虑出口箱装船顺序等因素，当出口箱进入箱区后，堆放状态较为无序。在进行装船时，需要边翻箱边装船，不仅翻箱次数较多，而且降低装船效率。所以设定集装箱翻箱的优化方法使轮胎吊司机在空闲时进行有目的翻箱，可以将无序的集装箱堆放状态整理为有序，从而来提高出口箱装船效率，减少装船所用的时间，并在一定程度上提高装船准确率。The efficiency of a container terminal is the most important indicator to measure the production capacity of a terminal. Whether it can load and unload ships efficiently has a major impact on reducing transportation costs and complying with shipping schedules. Since the order of export containers entering the yard from the crossing is random, the customs often adopt the advanced port re-inspection process, and use the personal experience of truck drivers or tire crane drivers when stacking export containers, so it is impossible to fully consider the export container loading. Ship order and other factors, when the export box enters the box area, the stacking state is relatively disorderly. When carrying out shipment, it is necessary to ship while turning over the box, which not only has more times of turning over the box, but also reduces the efficiency of shipping. Therefore, the optimization method of container overturning is set so that the tire crane driver can perform purposeful overturning of the container when he is free, and the disordered container stacking state can be sorted into order, thereby improving the efficiency of export container loading and reducing the time spent on loading , and improve the shipping accuracy to a certain extent.

发明内容Contents of the invention

针对现有集装箱装船操作方法中存在的不足，本发明所要解决的技术问题是提供一种装船时减少集装箱翻箱量的优化方法，集装箱进入相应堆场后在空闲时间对集装箱的排布进行有目的的翻箱整理，从而将无序的集装箱堆放状态整理为有序，提高出口箱装船效率。Aiming at the deficiencies existing in the existing container loading operation method, the technical problem to be solved by the present invention is to provide an optimization method for reducing the amount of container overturning during loading. Carry out purposeful rummaging and sorting, so as to organize the disordered container stacking state into an orderly state, and improve the efficiency of export container loading.

本发明采用的技术方案：根据轮胎吊只能在一个位上进行翻箱操作，不能提箱前后移动的实际情况，本发明考虑对一个物理箱区中的一个位上并排7个栈所构成的2维平面上进行最小翻箱量设计的优化步骤。一种装船时减少集装箱翻箱量的优化方法，由航次和港口决定装船顺序时的步骤如下：The technical scheme adopted in the present invention: according to the actual situation that the tire crane can only perform box turning operation at one position, and cannot move forward and backward when picking up the box, the present invention considers 2 stacks formed by arranging 7 stacks side by side on one position in a physical box area. The optimization steps of the design of the minimum turnover amount on the dimensional plane. An optimization method for reducing container overturning during shipment. The steps for determining the order of shipment by voyage and port are as follows:

(a)确定模糊目标状态：先对栈中的集装箱数目进行分类别统计，同航次同港口的集装箱为同一类别，然后计算各类别集装箱需要占用的列数，需要混合的类别则进行混合，接着根据初始栈状态尽量使最多数的集装箱不移动把相同类别的集装箱分配到相同的列；(a) Determine the state of the fuzzy target: First, count the number of containers in the stack by category, and the containers of the same voyage and port belong to the same category, then calculate the number of columns that each category of containers need to occupy, and mix the categories that need to be mixed, and then According to the initial stack state, try to make the most containers not move and assign the same type of containers to the same column;

(b)搜索确定目标状态：采用广度搜索的算法，数据结构为一队列，初始状态为队列的第一个元素，从队列的第一个未处理元素开始进行如下处理，取出第一个未处理元素作为当前栈状态，对当前栈状态移箱一次产生一个新的栈状态，然后以新的栈队列依次和步骤(a)所产生的“模糊目标队列”进行比对，通过遍列新的栈队列元素，在“模糊目标队列”中查找该元素，若新的栈队列中的每个元素在两个队列中位置相同，则判断此栈状态符合模糊目标状态，并把此栈状态记为确定目标状态，否则将其插入队列，然后再对当前栈状态移箱一次产生新状态，然后判断是否符合模糊目标状态，重复这种操作直至当前栈状态不能再产生新的栈状态为止，再然后到队列中取出最前一个栈状态作为当前栈状态进行上述操作直至搜索出确定目标状态或队列满为止；(b) Search to determine the target state: use the algorithm of breadth search, the data structure is a queue, the initial state is the first element of the queue, start from the first unprocessed element of the queue to perform the following processing, and take out the first unprocessed element The element is used as the current stack state, and the current stack state is shifted once to generate a new stack state, and then the new stack queue is compared with the "fuzzy target queue" generated in step (a), and the new stack is traversed Queue element, search for this element in the "fuzzy target queue", if each element in the new stack queue has the same position in the two queues, then judge that the stack state conforms to the fuzzy target state, and record this stack state as determined target state, otherwise insert it into the queue, then move the current stack state once to generate a new state, then judge whether it meets the fuzzy target state, repeat this operation until the current stack state can no longer generate a new stack state, and then to Take the first stack state from the queue as the current stack state and perform the above operations until the target state is found or the queue is full;

(c)确定具体翻箱步骤：用步骤(b)中算法确定目标状态，且在搜索过程中记录搜索顺序，在搜索到确定目标状态后进行回溯，把搜索的过程输出为一个具体的翻箱步骤。(c) Determine the specific steps of turning over boxes: use the algorithm in step (b) to determine the target state, and record the search sequence during the search process, and perform backtracking after searching to determine the target state, and output the search process as a specific box turning process step.

一种装船时减少集装箱翻箱量的优化方法，在考虑航次和港口的基础上进一步考虑集装箱重量决定装船顺序时的步骤如下：先执行上述步骤(a)、(b)把得到的确定目标状态作为一个新的初始状态，对新的初始状态中集装箱数目进行分类统计，同航次、同港口、同重量的集装箱为同一类别，然后计算各类别集装箱需要占用的列数，需要混合的类别则进行混合，接着根据初始栈状态尽量使最多数的集装箱不移动把相同类别的集装箱分配到相同的列；采用广度搜索的算法，数据结构为一队列，初始状态为队列的第一个元素，从队列的第一个未处理元素开始进行如下处理，取出第一个未处理元素作为当前栈状态，对当前栈状态移箱一次产生一个新的栈状态，然后判断此栈状态是否符合模糊目标状态，如果符合则把此栈状态记为确定目标状态，否则将其插入队列，然后再对当前栈状态移箱一次产生新状态，然后判断是否符合模糊目标状态，重复这种操作直至当前栈状态不能再产生新的栈状态为止，再然后到队列中取出最前一个栈状态作为当前栈状态进行上述操作直至搜索出确定目标状态或队列满为止；用步骤(b)中算法确定目标状态，且在搜索过程中记录搜索顺序，在搜索到确定目标状态后进行回溯，把搜索的过程输出为一个具体的翻箱步骤。An optimization method for reducing the amount of container overturning during shipment. The steps for determining the order of shipment by further considering the container weight on the basis of the voyage and port are as follows: first perform the above steps (a) and (b) to obtain the determined The target state is used as a new initial state, and the number of containers in the new initial state is classified and counted. The containers of the same voyage, port, and weight belong to the same category, and then calculate the number of columns that need to be occupied by each category of containers, and the categories that need to be mixed Then mix, and then try to make the most containers not move according to the initial stack state, and assign the containers of the same type to the same column; use the breadth search algorithm, the data structure is a queue, and the initial state is the first element of the queue. Starting from the first unprocessed element of the queue, perform the following processing, take the first unprocessed element as the current stack state, shift the current stack state once to generate a new stack state, and then judge whether the stack state conforms to the fuzzy target state , if it matches, record this stack state as the definite target state, otherwise insert it into the queue, then move the current stack state once to generate a new state, then judge whether it meets the fuzzy target state, repeat this operation until the current stack state cannot Until a new stack state is generated, then go to the queue to take out the most previous stack state as the current stack state and carry out the above operations until the target state is determined or the queue is full; use the algorithm in step (b) to determine the target state, and in the search The search sequence is recorded during the process, and the backtracking is performed after the target state is determined, and the search process is output as a specific step of rummaging.

本发明的有益效果：利用本发明轮胎吊司机在等待集卡的空闲时间进行有目的翻箱，可以将无序的集装箱堆放状态整理为有序，集卡不必经过等待可以直接从堆场运输集装箱装船，从而来提高出口箱装船效率，减少装船所用的时间，并在很大程度上提高了装船准确率。Beneficial effects of the present invention: By using the tire crane driver of the present invention to carry out purposeful overturning during the idle time of waiting for the collection truck, the unordered container stacking state can be sorted into order, and the collection truck can directly transport the container from the yard without waiting Shipment, so as to improve the efficiency of export box shipment, reduce the time spent on shipment, and improve the accuracy of shipment to a large extent.

附图说明Description of drawings

图1是原始无序状态下的集装箱排列示意图；Fig. 1 is a schematic diagram of container arrangement in the original disordered state;

图2是实际生产操作中集装箱排列示意图；Fig. 2 is a schematic diagram of container arrangement in actual production operation;

图3是先翻箱后作业的情况下集装箱排列示意图；Fig. 3 is a schematic diagram of container arrangement in the case of overturning first and then operation;

图4是本发明流程图。Fig. 4 is a flowchart of the present invention.

具体实施方式Detailed ways

结合附图对本发明进一步详细描述：一种装船时减少集装箱翻箱量的优化方法，由航次和港口决定装船顺序时的步骤如下：(a)确定模糊目标状态：先对栈中的集装箱数目进行分类别统计，同航次同港口的集装箱为同一类别，然后计算各类别集装箱需要占用的列数，需要混合的类别则进行混合，接着根据初始栈状态尽量使最多数的集装箱不移动把相同类别的集装箱分配到相同的列；(b)搜索确定目标状态：采用广度搜索的算法，数据结构为一队列，初始状态为队列的第一个元素，从队列的第一个未处理元素开始进行如下处理，取出第一个未处理元素作为当前栈状态，对当前栈状态移箱一次产生一个新的栈状态，然后判断此栈状态是否符合模糊目标状态，如果符合则把此栈状态记为确定目标状态，否则将其插入队列，然后再对当前栈状态移箱一次产生新状态，然后判断是否符合模糊目标状态，重复这种操作直至当前栈状态不能再产生新的栈状态为止，再然后到队列中取出最前一个栈状态作为当前栈状态进行上述操作直至搜索出确定目标状态或队列满为止；(c)确定具体翻箱步骤：用步骤(b)中算法确定目标状态，且在搜索过程中记录搜索顺序，在搜索到确定目标状态后进行回溯，把搜索的过程输出为一个具体的翻箱步骤。在考虑航次和港口的基础上进一步考虑集装箱重量决定装船顺序时的步骤如下：先执行步骤(a)、(b)把得到的确定目标状态作为一个新的初始状态，对新的初始状态中集装箱数目进行分类统计，同航次、同港口、同重量的集装箱为同一类别，然后计算各类别集装箱需要占用的列数，需要混合的类别则进行混合，接着根据初始栈状态尽量使最多数的集装箱不移动把相同类别的集装箱分配到相同的列；顺序按照步骤(b)、(c)得到一个具体的翻箱步骤。The present invention is further described in detail in conjunction with the accompanying drawings: a kind of optimization method for reducing the amount of container overturning during shipment, the steps when the order of shipment is determined by the voyage and the port are as follows: (a) determine the fuzzy target state: first check the container in the stack The number is counted by category, the containers of the same voyage and port are of the same category, and then the number of columns that need to be occupied by each category of containers is calculated, and the categories that need to be mixed are mixed, and then according to the initial stack state, try to keep the largest number of containers from moving. The containers of the category are assigned to the same column; (b) search to determine the target state: use the breadth search algorithm, the data structure is a queue, the initial state is the first element of the queue, and start from the first unprocessed element of the queue Process as follows, take out the first unprocessed element as the current stack state, shift the box of the current stack state once to generate a new stack state, and then judge whether the stack state meets the fuzzy target state, if so, record the stack state as determined target state, otherwise insert it into the queue, then move the current stack state once to generate a new state, then judge whether it meets the fuzzy target state, repeat this operation until the current stack state can no longer generate a new stack state, and then to Take out the first stack state in the queue as the current stack state and carry out the above operations until the search determines the target state or the queue is full; (c) determine the specific step of turning over the box: use the algorithm in step (b) to determine the target state, and in the search process Record the search sequence, backtrack after searching to determine the target state, and output the search process as a specific step of rummaging. On the basis of considering the voyage and port, the steps to further consider the weight of the container to determine the order of shipment are as follows: first perform steps (a) and (b) and use the determined target state as a new initial state, and for the new initial state The number of containers is classified and counted. Containers of the same voyage, port, and weight belong to the same category, and then calculate the number of columns that need to be occupied by containers of each category. Mix the categories that need to be mixed, and then try to make the most containers according to the initial stack status. Distribute the containers of the same category to the same column without moving; obtain a concrete rummaging step according to steps (b) and (c) in sequence.

根据轮胎吊只能在一个位上进行翻箱操作，不能提箱前后移动的实际情况，如图1所示，深色箱为中控指定需要发送的箱子，灰色为暂不发箱。本发明所涉及的范围是在一个物理箱区中的一个位上并排7个栈上所构成的2维平面上进行最小翻箱量的计算给出相应的操作步骤。针对图1给出的模型是由六个可以容纳五个箱以及一个可以容纳最多五个箱(即倒箱位)，共七个栈三十五个箱位构成二维空间物理模型。对于堆场上每个位上的栈，都只能先将最外面的箱移出，才能移出下面的箱，即他们满足后进先出原则。用计算机技术中的堆栈stack来描述这个物理模型，stack同样是后进先出，并且只有pop和push两种操作。由于在实际操作时，轮胎吊司机通常会首先将暴露在堆场表面的已发箱做掉，然后再考虑对埋在未发箱下的已发箱进行翻箱操作，所以在运行翻箱操作算法前我们首先进行装箱运算，即对当前堆场上可以直接装车的箱进行处理，将他们从各自的栈中pop出来，之后再在余下的箱构成的模型中进行翻箱操作，如图2所示，这样做更贴近实际操作并能够简化算法。在边翻箱边装车的算法中，当箱子被翻到表面后，无需继续留在堆场上，也就是无需继续留在堆栈里，这时应该将他们POP出来，并调整描述堆场状态的二维数组。在将一个栈里的未发箱移到别的栈时，我们会对当前堆场所剩余的空位置根据先底层后高层，在小于5层时优先考虑离当前要移动的箱最近的位置，当有两个位置都适合时，优先考虑已经翻过箱子的栈，即右边靠近倒箱位的栈；在第5层只考虑无需翻箱的栈，靠近1号位的优先，如果以上都不满足，就考虑倒箱位等原则来为当前移动的箱子挑选合适的位置。不同于边翻箱边作业，在进行先翻箱后作业的情况下，已发箱并不离开堆场，即他们将继续留在栈中只是换了别的栈，所以在计算时算法同前者不同，我们这时要求这个已发箱在转换了栈以后不会造成被PUSH的栈还要翻箱，经过上述操作得到图3。According to the actual situation that the tire crane can only turn over the box at one position, and cannot move the box back and forth, as shown in Figure 1, the dark box is the box designated by the central control to be sent, and the gray box is not delivered temporarily. The scope involved in the present invention is to calculate the minimum amount of box rummaging on a 2-dimensional plane formed by arranging 7 stacks side by side on a position in a physical box area, and provide corresponding operation steps. The model given in Fig. 1 is composed of six stacks that can accommodate five boxes and one that can accommodate up to five boxes (that is, inverted boxes), a total of seven stacks and thirty-five boxes constitute a two-dimensional space physical model. For each stack on the yard, the outermost box can only be removed first before the lower box can be removed, that is, they satisfy the last-in-first-out principle. Use the stack stack in computer technology to describe this physical model. The stack is also last-in-first-out, and there are only two operations: pop and push. In actual operation, the tire crane driver usually removes the delivered containers exposed on the surface of the yard first, and then considers the delivered containers buried under the undelivered containers. Therefore, when running the container dump operation Before the algorithm, we first perform box packing operations, that is, process the boxes that can be directly loaded on the current yard, pop them out from their respective stacks, and then perform box rummaging operations in the model composed of the remaining boxes, such as As shown in Figure 2, doing so is closer to actual operation and can simplify the algorithm. In the algorithm of turning over boxes and loading cars, when the boxes are turned over to the surface, there is no need to stay on the yard, that is, there is no need to stay in the stack. At this time, they should be popped out and adjusted to describe the status of the yard A two-dimensional array of . When moving an undelivered box in one stack to another stack, we will first consider the bottom level and then the high level for the remaining vacant positions in the current stack, and give priority to the position closest to the current box to be moved when it is less than 5 floors. When both positions are suitable, give priority to the stack that has already turned over the box, that is, the stack on the right that is close to the unloading position; on the fifth floor, only consider the stack that does not need to be turned over, and the stack near the No. 1 position is preferred, if none of the above is satisfied , consider the principle of reversing the position of the box to select a suitable position for the currently moving box. Different from working while rummaging through boxes, in the case of rummaging first and then working, the delivered boxes will not leave the yard, that is, they will remain in the stack and just change to another stack, so the calculation algorithm is the same as the former Different, we require that the sent box will not cause the PUSHed stack to be turned over after the stack is converted. After the above operations, Figure 3 is obtained.

发明的数学理论基础如下：The mathematical basis of the invention is as follows:

一.初始状态的假设条件：1. Assumptions of the initial state:

1.每一个stack共有六列，任一列集装箱数目不超过5个；1. Each stack has six rows, and the number of containers in any row does not exceed 5;

2.每一个stack的集装箱数目不超过21个；2. The number of containers in each stack shall not exceed 21;

3.集装箱依重量、装船先后次序等因素划分3～5个等级，用1～5表示。即：(1)-表示最优先级的集装箱；3. Containers are divided into 3 to 5 grades according to factors such as weight and shipment sequence, represented by 1 to 5. That is: (1) - indicates the container with the highest priority;

(2)-表示第二优先级的集装箱；(2) - indicates a container of the second priority;

(3)-表示第三优先级的集装箱；(3) - indicates a container of the third priority;

(4)-表示第四优先级的集装箱；(4) - indicates a container of the fourth priority;

(5)-表示第五优先级的集装箱；(5) - indicates a fifth priority container;

等级的划分根据具体情况事先已给定；The division of grades has been given in advance according to the specific circumstances;

4.假设同一个stack的集装箱为同一条船同一港口的货物；(如4不满足，我们不把栈定义为最小单位；而以同一条船同一港口的列为一个“stack”)；4. Assume that the containers of the same stack are the goods of the same ship and the same port; (if 4 is not satisfied, we do not define the stack as the smallest unit; but use the same ship and the same port as a "stack");

5.假设没有倒箱位。5. Assuming there is no unloading position.

某初始状态A见表1。An initial state A is shown in Table 1.

表1.某初始状态ATable 1. An initial state A

列：          1    2    3    4    5    6Columns: 1 2 3 3 4 5 6

复杂度σ(A_i)：0    2    3    0    1    2$\underset{i=1}{\overset{6}{\mathrm{\Σ}}}\mathrm{\σ}\left(A_i\right)=8$Complexity σ(A_i ): 0 2 3 0 1 2$\underset{i=1}{\overset{6}{\mathrm{\Σ}}}\mathrm{\σ}\left(A_i\right)=8$

共21个集装箱，分1，2，3，4级。A total of 21 containers, divided into 1, 2, 3, 4 levels.

每个stack表示法：(0111200221120332130011200043310034328)Each stack notation: (0111200221120332130011200043310034328)

二.数学变量的定义2. Definition of Mathematical Variables

1.stack的表示：1. Representation of stack:

假如没有倒箱位，用30维数组表示：If there is no unpacking position, it is represented by a 30-dimensional array:

(a₁a₂...a₃₀)＝(011120221103321001120043300343)(a₁ a₂ ...a₃₀ )＝(011120221103321001120043300343)

假如有倒箱位，用31维数组表示：If there is an inverted box, it is represented by a 31-dimensional array:

(a₁a₂...a₃₁)，其中a₃₁＝0 or 1，2，3，4。(a₁ a₂ ...a₃₁ ), where a₃₁ =0 or 1,2,3,4.

2.复杂度的定义及表示：σ(A_i)2. Definition and representation of complexity: σ(A_i )

$\mathrm{\σ}\left(A\right)=\underset{i=1}{\overset{6}{\mathrm{\Σ}}}\mathrm{\σ}\left(A_i\right)$(没有倒箱位)$\mathrm{\σ}\left(A\right)=\underset{i=1}{\overset{6}{\mathrm{\Σ}}}\mathrm{\σ}\left(A_i\right)$ (no unloading slot)

$\mathrm{\σ}\left(A\right)=\underset{i=1}{\overset{7}{\mathrm{\Σ}}}\mathrm{\σ}\left(A_i\right)$(有倒箱位)$\mathrm{\σ}\left(A\right)=\underset{i=1}{\overset{7}{\mathrm{\Σ}}}\mathrm{\σ}\left(A_i\right)$ (with unloading space)

σ(A_i)：表示stack A中的第i(1≤i≤6)列中使A_i成为一个复杂度为0且|A_i|≤4，至少需要移动的集装箱数目。σ(A_i ): Indicates at least the number of containers that need to be moved in the i-th (1≤i≤6) column of stack A to make A_i a complexity of 0 and |A_i |≤4.

如果a₃₁≠0，则σ(A₇)＝1If a₃₁ ≠0, then σ(A₇ )=1

如果a₃₁＝0，则σ(A₇)＝0If a₃₁ =0, then σ(A₇ )=0

三.目标状态的定义：复杂度为0，同时同一列尽可能同一等级3. Definition of the target state: the complexity is 0, and the same column should be at the same level as possible

四.通过研究翻箱规律得到的数学结论，具体而言：4. Mathematical conclusions obtained by studying the law of overturning boxes, specifically:

1.6步DFS搜索：4步后去掉复杂度增加2的，去掉4步后复杂度完全不动的(Th3)，5步后去掉复杂度增加的。1.6-step DFS search: After 4 steps, remove the ones whose complexity increases by 2, remove the ones whose complexity does not change after 4 steps (Th3), and remove the ones whose complexity increases after 5 steps.

2.每6步后找复杂度最少的那部分状态作为初始状态再用6步DFS搜索。2. After every 6 steps, find the part of the state with the least complexity as the initial state and then use 6-step DFS search.

3.在前3步减少搜索次数：3. Reduce the number of searches in the first 3 steps:

a)一次移动使中间某列高过4的，不用移动。a) If one move makes a column in the middle higher than 4, there is no need to move.

b)移动后与原来同构的，不用移动。b) After being moved, it is isomorphic to the original, no need to move.

c)若从A_i移走一个箱子放在A_j列，但σ(A_i)≠0，和σ(A_j)≠0，那么下一步不能从另外的列A_k移箱子放在A_i。c) If a box is removed from A_i and placed in column A_j , but σ(A_i )≠0, and σ(A_j )≠0, then the box cannot be moved from another column A_k to A_i in the next step .

d)若|A_i|＝4且σ(A_i)＝0，那么A_i锁定。d) If |A_i |=4 and σ(A_i )=0, then A_i is locked.

五.数学证明：5. Mathematical proof:

Th1定义最少翻箱次数为M(A)，则M(A)≥σ(A)。Th1 defines the minimum number of flips as M(A), then M(A)≥σ(A).

Th2A翻6次以后得到B，满足σ(B)＜σ(A)的B中一定有最优路径。After turningTh2A 6 times to get B, there must be an optimal path in B that satisfies σ(B)<σ(A).

推论：A翻5次到A₅，σ(A₅)＞σ(A)的可以去掉。Inference:Turn A 5 times to reach A₅ , and those with σ(A₅ )>σ(A) can be removed.

      A翻4次到A₄，σ(A₄)＞σ(A)+2的可以去掉。A turns over 4 times to A₄ , σ(A₄ )>σ(A)+2 can be removed.

Th3 A→A1→A2→A3→A4，如果σ(A)＝σ(A1)＝σ(A2)＝σ(A3)＝σ(A4)则A4可以去掉。Th3 A→A1→A2→A3→A4, if σ(A)=σ(A1)=σ(A2)=σ(A3)=σ(A4), then A4 can be removed.

Th4若最大的等级为k，又设在所有列最底下一层没有k的集装箱，则一定将某列清空！Th4 If the maximum level is k, and there is no k container in the bottom layer of all columns, then a certain column must be cleared!

六.在移箱过程中的优先目标：Six. Priority goals in the process of moving boxes:

1.出现空行优先。1. Empty lines appear first.

2.最底下等级大(即轻的)优先。2. The lowest level is big (ie light) first.

3.σ(A_i)≠0且min{σ(A_i)|σ(A_i)≠0}的列优先3. Column priority of σ(A_i )≠0 and min{σ(A_i )|σ(A_i )≠0}

4.A1与A6的列优先4. Column priority of A1 and A6

5.优先放箱在同等级的箱子上或比它小的箱子上(即2压1，而不5. Prioritize placing boxes on boxes of the same level or on boxes smaller than it (that is, 2presses 1 instead of

是2压3，如果3所在的列复杂度为0，则2压3可以)。It is 2 pressing 3, if the complexity of the column where 3 is located is 0, then 2 pressing 3 is fine).

以上所述内容仅为本发明构思下的基本说明，而依据本发明的技术方案所作的任何等效变换，均应属于本发明的保护范围。The above content is only a basic description of the concept of the present invention, and any equivalent transformation made according to the technical solution of the present invention shall fall within the scope of protection of the present invention.

Claims (2)

Translated fromChinese

1.一种装船时减少集装箱翻箱量的优化方法，由航次和港口决定装船顺序时的步骤如下：1. An optimization method for reducing container overturning during shipment, the steps of which are as follows when the order of shipment is determined by the voyage and port:(a)确定模糊目标状态：先对栈中的集装箱数目进行分类别统计，同航次同港口的集装箱为同一类别，然后计算各类别集装箱需要占用的列数，需要混合的类别则进行混合，接着根据初始栈状态尽量使最多数的集装箱不移动把相同类别的集装箱分配到相同的列；(a) Determine the state of the fuzzy target: First, count the number of containers in the stack by category, and the containers of the same voyage and port belong to the same category, then calculate the number of columns that each category of containers need to occupy, and mix the categories that need to be mixed, and then According to the initial stack state, try to make the most containers not move and assign the same type of containers to the same column;(b)搜索确定目标状态：采用广度搜索的算法，数据结构为一队列，初始状态为队列的第一个元素，从队列的第一个未处理元素开始进行如下处理，取出第一个未处理元素作为当前栈状态，对当前栈状态移箱一次产生一个新的栈状态，然后以新的栈队列依次和步骤(a)所产生的“模糊目标队列”进行比对，通过遍列新的栈队列元素，在“模糊目标队列”中查找该元素，若新的栈队列中的每个元素在两个队列中位置相同，则判断此栈状态符合模糊目标状态，并把此栈状态记为确定目标状态，否则将其插入队列，然后再对当前栈状态移箱一次产生新状态，然后判断是否符合模糊目标状态，重复这种操作直至当前栈状态不能再产生新的栈状态为止，再然后到队列中取出最前一个栈状态作为当前栈状态进行上述操作直至搜索出确定目标状态或队列满为止；(b) Search to determine the target state: use the algorithm of breadth search, the data structure is a queue, the initial state is the first element of the queue, start from the first unprocessed element of the queue to perform the following processing, and take out the first unprocessed element The element is used as the current stack state, and the current stack state is shifted once to generate a new stack state, and then the new stack queue is compared with the "fuzzy target queue" generated in step (a), and the new stack is traversed Queue element, search for this element in the "fuzzy target queue", if each element in the new stack queue has the same position in the two queues, then judge that the stack state conforms to the fuzzy target state, and record this stack state as determined target state, otherwise insert it into the queue, then move the current stack state once to generate a new state, then judge whether it meets the fuzzy target state, repeat this operation until the current stack state can no longer generate a new stack state, and then to Take the first stack state from the queue as the current stack state and perform the above operations until the target state is found or the queue is full;(c)确定具体翻箱步骤：用步骤(b)中算法确定目标状态，且在搜索过程中记录搜索顺序，在搜索到确定目标状态后进行回溯，把搜索的过程输出为一个具体的翻箱步骤。(c) Determine the specific steps of turning over boxes: use the algorithm in step (b) to determine the target state, and record the search sequence during the search process, and perform backtracking after searching to determine the target state, and output the search process as a specific box turning process step.2.根据权利要求1所述的一种装船时减少集装箱翻箱量的优化方法，在考虑航次和港口的基础上进一步考虑集装箱重量决定装船顺序时的步骤如下：先执行步骤(a)、(b)把得到的确定目标状态作为一个新的初始状态，对新的初始状态中集装箱数目进行分类统计，同航次、同港口、同重量的集装箱为同一类别，然后计算各类别集装箱需要占用的列数，需要混合的类别则进行混合，接着根据初始栈状态尽量使最多数的集装箱不移动把相同类别的集装箱分配到相同的列；顺序按照步骤(b)、(c)得到一个具体的翻箱步骤。2. according to claim 1, the optimal method for reducing the amount of container overturning during a kind of shipment, the steps when further considering the weight of the container to determine the order of shipment are as follows on the basis of considering the voyage and the port: first perform step (a) 、(b) Take the determined target state obtained as a new initial state, and classify and count the number of containers in the new initial state. Containers of the same voyage, port, and weight belong to the same category, and then calculate the required occupancy of each type of container. The number of columns that need to be mixed should be mixed, and then according to the initial stack state, the most containers should not be moved and the containers of the same category should be assigned to the same column; the sequence is obtained according to steps (b) and (c) Turn over steps.

Images