%======================问题介绍==================================== \section{Introduction} Christmas is coming, Santa needs an optimal loading mode, makes the present as compact as possible and orderly arranged in the sledge. The title gives an evaluation on the best standards, we think it is effective, our objective is based as much as possible to determine an optimal loading method.\par This is a space layout optimization problems\cite{a,b,c}, and is similar to the classic container loading problem . Container loading problem aims to determine the loading strategy as far as possible to make maximum utilization of the container space, solution method often used to have a constructive heuristic algorithm, using genetic algorithm, ant colony algorithm, tabu search algorithm and other intelligent algorithm. But in the Santa Claus present loading, we not only need to make a present the placement space utilization rate of the highest possible, should also be possible to make the place as far as possible the orderly, the existing methods are not applicable, we need to have characteristics determine a suitable method.\par Now,we will show our work in the paper:\par \begin{itemize} \item We first establish three present placement strategy. \item According to the strategy to establish the corresponding present display model. \item We carried out experiments on each parameter in the model, to find the best parameter value. \item We use the modified model to calculate the number of presents on the subject are given, to obtain the result. \item We use the results of analysis to discuss the basic placement strategy, and to discuss the rationality of definition of the optimal index analysis of the given topic. \end{itemize} \section{Assumptions and interpretation} %\renewcommand{\labelitemi}{\ding{43}} \begin{description} \item In this paper, the main purpose is to give the best present loading method, considering the close degree and order. The mathematical description that presents produce extrusion deformation is very complex. To establish the mathematical model to facilitate the solution, we think that the mutual extrusion will not generate deformation. \item In fact, the center of gravity when the top present below on the outside surface of the present, the whole structure will collapse because of the unstable. Establish the process to simplify the model to reduce the computational complexity, we assume that an arbitrary state display process is stable. \item Because of gravity, articles must be from the bottom up, not hanging put presents, which is more consistent with the real situation. \end{description} Under the above and basic assumptions, we can set out to construct our model. %=============================问题分析========================================== \section{Establish strategy and build models } %==================================模型建立============================================== \subsection{How to put presents} Loading of a certain number of objects to the sleigh, we make it as compact as possible, and try to make it orderly.A straightforward idea is to put some big size of the presents first, and then put the small size into the gap.For each of the presents ,we can adjust their attitude to find the most appropriate way. Each gift put can start from the lowest place, this can make the sleigh more smooth and more compact. To this end, we put forward the following strategies.\par \begin{itemize} \item \textbf{Group a certain number of presents, and each group by size within into two kinds of size, large size in a first, put the small sizes after.} \end{itemize}\par If the ideal sequence to put can produce many small gap, not only reduce the space utilization, and increased a lot of judgment, make the algorithm complexity has greatly increased. We can group first, classify after , and then put according to the strategy of the large size class first, small size class after .This not only can effectively makes use of gaps, but also greatly reduces the complexity of the algorithm.\par We divide each of T presents into a group. When we put n presents, the next group can be showed as the available set $G\{g_{n+1},g_{n+2},...,g_{n+T}\}$.\par Through the statistical analysis for the given presents size ,we can see the analysis results as shown in Fig\ref{fig:a}.\par \begin{figure} \graphicspath{{pic/}{png/}} \begin{center} \includegraphics {1}\\ \caption{presents size chart}\label{fig:a} \end{center} \end{figure} From the chart , the each side length of the majority presents is less than $10$ ,which can be a boundary to divided them into large size and small size.\par Large size and small size can be respected by the set $B$ and $S$.The classification diagram as shown in Fig\ref{fig:b}.\par \begin{figure} \graphicspath{{pic/}{png/}} \begin{center} \includegraphics {2}\\ \caption{Classification diagram}\label{fig:b} \end{center} \end{figure} Set the $n+k$ presents of length, width and height, respectively, and can be expressed as $u_{n+k}$,$v_{n+k}$,$w_{n+k}$.Thus the classification method can be described as \begin{align} S =\sum\limits_{k=1}^{k=T} g_{n+k}\bigcup S, min\{u_{n+k},v_{n+k},w_{n+k}\}\leq K\\ B =\sum\limits_{k=1}^{k=T} u_{n+k}\bigcup S, min\{u_{n+k},v_{n+k},w_{n+k}\} K \end{align} \par In the equation,let the parameter of classification $K=10$,and $n+kN$,$N$ is the number of the presents.\par \begin{itemize} \item \textbf{For each presents, use the highest degree in areas relevant to put.} \end{itemize}\par Presents put to is parallel or orthogonal with the sleigh.In this way,it can be put there with 6 kinds of gestures.The placement attitude as shown in Fig\ref{fig:c}.\par \begin{figure} \graphicspath{{pic/}{png/}} \begin{center} \includegraphics {3}\\ \caption{Placement attitude}\label{fig:c} \end{center} \end{figure} We select a way,in which,the present is the most revelent to the space , such as the way(1). Such is helpful to reduce the gap,and improve space utilization. Define the first k kinds of $n+1$ present placed for relevant degrees: \begin{center} $$ r_{n_1(k)}=\left\{ \begin{array}{ccl} \dfrac{P_{n+1(k)}Q_{n+1(k)}}{M_x N_y} {PM_x \quad and \quad QN_y \qquad (1\leq k\leq 6)}\\ 0 {PM_x \quad or \quad QN_y \qquad (1\leq k\leq 6)} \end{array}\right.$$ \end{center}\par Let the k kinds of $n+1$ presents of the length and width be , $P_{n+1_{k}}$,$Q_{n+1_{k}}$ ,and respectively for the current put coordinates $(x, y)$ identified put area's long and wide. \begin{itemize} \item \textbf{All regions can be put in the lowest prior.} \end{itemize}\par First determines the lowest place whether there is a space to satisfy the next present put, if meet in here, if not satisfied, in the area of the penultimate lower judgment, until find one can be placed. Generally, at the lowest space,we may find different kinds of spaces to choose .For this we take from left to right, from top to bottom of the order and search one by one. Put this method can be realized by matlab in ‘min’ function: \begin{equation} h_{min}=min(min(H_n)) \end{equation}\par Through the operation after $h_{min}$ said ,its returns coordinates ($x,y$).\par At the lowest priority put can avoid the bad situation of local high produce, which is beneficial to make full use of the remaining space, can effectively improve the tightness that puts.\par \subsection{ Record and update the space state} When we put presents in the process of the sleigh, records of space state is necessary, so that we can choose which space to the next present according to a certain strategy. We supposed that the display is always from the bottom up, but in fact, we just need to be concerned with the state on the surface of the space. Because the sleigh is for 1000 units of the square and the size of the presents is an integer, after put n present ,the state of space may be defined as: \begin{equation*} Z_n= \begin{pmatrix} z_{n_{0,0}} \cdots z_{n_{0,1000}}\\ \vdots \ddots \vdots \\ z_{n_{1000,0}} \cdots z_{n_{1000,1000}} \end{pmatrix} \end{equation*} $z_{n_{i,j}}$,($0\leq i \leq 1000,0\leq j \leq 1000$)is said the point ($i,j$) corresponding to the highest surface on the height of the object after putting the n presents.\par Set the $n+1$ present of length, width and height as $u_{n+1}$,$v_{n+1}$,$w_{n+1}$ respectively.when we put it in space on the surface, at a certain point ($x,y,z_{n_{x,y}}$),the height of the space will be updated to \begin{equation} z_{n+1_{x,y}}=z_{n{x,y}}+w_{n+1} \end{equation}\par After the n+1 present,we can get the state space description matrix $H_{n+1}$.\par The n+1 space status update operation is defined as $\beth_{n+1}$, after putting the $n+1$ present, status updates can be described as\par \begin{equation} Z_{n+1}=\beth_{n+1}Z_{n+1} \end{equation}\par Thus when the M update to the following value after putting the $n+1$ present. \begin{equation} M_{n+1}=M_{n}+2(Z_{n+1_{max}}-Z_{n_{max}})+\mid n+1=i_{n+1_{actual}} \mid \end{equation}\par $i_{n+1{actual}}$is the $n+1$ present’s actual order in the ideal order.Space state transition diagram is shown in Fig\ref{fig:d}.\par \begin{figure} \graphicspath{{pic/}{png/}} \begin{center} \includegraphics {4}\\ \caption{ Space state transition diagram }\label{fig:d} \end{center} \end{figure} \subsection{The improvement of model } Such problems have been shown is NP - hard problem ,and because our model is relatively ideal, computational complexity is too big that it is hard to solve. Here we will analyze a few of the main causes of computational complexity and improve our model for reducing the complexity of the calculation.\par \subsubsection{Give up small space } After the present put on the available space,it will be set apart as gap\_1 and gap\_2 space, as shown in Fig\ref{fig:e}.Too much gap will produce a large number of search points, that will increases searching complexity seriously .\par \begin{figure} \graphicspath{{pic/}{png/}} \begin{center} \includegraphics {5}\\ \caption{ Space is separated }\label{fig:e} \end{center} \end{figure} To solve this problem, we can give up some small space to reduce the searching complexity. So if for any rectangular space,the shortest edge is less than the given close degree $d_{min}$,it is considered to be not used. Judge expression as follows: \begin{center} $$ \left\{ \begin{array}{ccl} \Delta l_1(or \quad \Delta l_2)d_{min} \text{ gap\_1(or gap\_2) is unavailable}\\ \Delta l_1(or \quad \Delta l_2)d_{min} \text{ gap\_1(or gap\_2) is available} \end{array}\right.$$ \end{center}\par \subsubsection{How to deal with the unavailable space } Unavailable space:If present $g_n$ is unable to put into the available space and need to choose the next available space, the space becomes unavailable space at this time.when we put into the present $g_{n+1}$, we will restore the unavailable space .\par Due to $Min$ function is to search the global minimum altitude, you need to tag searched space not used to avoid repetition. Fuzzy problems exist in the change with unavailable space, so we will make a strategy.\par \begin{figure} \graphicspath{{pic/}{png/}} \begin{center} \includegraphics {6}\\ \caption{unavailable space }\label{fig:f} \end{center} \end{figure} The fuzzy problems is shown in the Fig\ref{fig:f} .The direction of searching is down and to the right , that can make the search point spread out and produce two spaces \{S1, S2\}. If we changed the space of S1, the quantity of state will ba tagged and S1 is unable to use at next searching.To avoid this situation ,we take the shortest length of the space as the boundary of the unavailable space. Because the upper length a is less than the lower length b,we define S2 as unavailable space.\par \section{Testing the Model} We take 1000 presents as the research object,and count up the 3d length of 1000 presents.We find that the statistic of 1000 presents is same of the 30000,100000 and 1000000 ,so we can say this testing is meaningful.\par The calculation flow chart is shown in Fig\ref{fig:g}:\par \pagebreak \begin{figure} \graphicspath{{pic/}{png/}} \begin{center} \includegraphics {7}\\ \caption{The calculation flow chart}\label{fig:g} \end{center} \end{figure} For the best answer,we should test some parameters of the model. \subsection{Parameter analysis} \subsubsection{Classification K } When we research category boundaries $K$ influencing on the result, we need to consider the indicators of different scales. In order to highlight the change trend of each indicators , the results after normalization is analyzed.The result is shown in Fig\ref{fig:h} :\par \pagebreak \begin{figure} \graphicspath{{pic/}{png/}} \begin{center} \includegraphics {8}\\ \caption{Analysis of parameter K}\label{fig:h} \end{center} \end{figure} We can see from the figure that ,the minimum value of $M$ is obtained at $K=10$, at the same time, the change of $K$ on the impact of the various indicators:\par \begin{enumerate} \item With the increase of $K$, the order of evaluation indicators $\sigma(p)$, rapid growth and then slow growth ,and in $K=10$, there is the rate of change; \item A maximum height of $Max_z$ in a trough at $K = 10$ ,after that height changes little; \item $M$ there was a minimum value $M=2582$ in the $K=10$, later along with the change of $K$, $M$ value is basically the same. \end{enumerate} \subsubsection{ Packet length T } Parameters $T$ (branch length) in the model influence the order , to test the results of $T$ with different values ,the result is shown in Fig\ref{fig:i} :\par \begin{figure} \graphicspath{{pic/}{png/}} \begin{center} \includegraphics {9}\\ \caption{Analysis of parameter $T$}\label{fig:i} \end{center} \end{figure} We can see from the figure that ,the minimum value of $M$ is obtained at $T=2$, at the same time, the change of $T$ on the impact of the various indicators:\par \begin{enumerate} \item With the increasing of $T$ , the order of evaluation indicators $\sigma (p)$ into linear growth, increase the slope is 176.5; \item A maximum height of $Max_z$ in a trough when $T=2$, after $T4$, with the increase of $T$ changed little; \item $M$ value throughout the change is mainly influenced by \ sigma (p), there is the minimum when $T=2$, $M=2582$, after $T5$, with the increase of $T$, $M$ value linear growth, growth slope was 163, slightly less than $\sigma(p)$ the growth of the slope. \end{enumerate} \subsubsection{Compact degree of d} In order to avoid in the process of solving the search for unavailable space,we give up small space, and compact degree of d in the strategy's influence on the results here are analyzing. Let $T=2$ and $K=10$, the results of the analysis is shown in Fig\ref{fig:j}:\par \begin{figure} \graphicspath{{pic/}{png/}} \begin{center} \includegraphics {10}\\ \caption{Analysis of parameter d}\label{fig:j} \end{center} \end{figure} We can see from the figure that ,the minimum value of $M$ is obtained at $d=9$, at the same time, the change of $d$ on the impact of the various indicators : \begin{enumerate} \item $d$ has no effect on the size of $\sigma(p)$; \item A maximum height of $Max_z$ in a trough when $d=9$, after the height changes gradually increase; \item $M$ there was a minimum value in the $d=9$, $M=2262$, later along with the change of $d$, $M$ value increases gradually, and change rate and $Max_z$ tend to be the same. \end{enumerate} \subsection{Test results and analysis} \subsubsection{Best parameter result} \begin{enumerate} \item Classification boundary $K=10$; \item Length of group $T=2$; \item Compactness $d=9$; \end{enumerate} \subsubsection{The analysis of the results} \begin{itemize} \item With the increase of packet length $T$, the $M$ value will increase quickly, which shows that the length of the packet has a great influence on the order; \item With the increase of classification boundaries $K$, in the initial time sequence index $\sigma(P)$ increased rapidly, because the present size mostly located within 10; \item The change of compactness $d$ almost has no influence on the order. It is mainly to change the space utilization rate. There is a minimum $d$ which satisfies the optimal space utilization rate, and that may decided by the distribution characteristics of presents’ own size. \end{itemize} \section{Model application} Because1000,30000,100000 and1000000 presents size have the same statistical distribution,we can set the parameters as the best parameters in testing.Solution of the specific steps are as follows:\par \textbf{Step1:}Set up parameters and input size and number of gifts，$T$(block length)$=2$, $K$(boundary)$=10$,$d$(compactness)$=9$,$N=30000$；\par \textbf{Step2:}According to the classification boundary to the gift of classification, get gift placed number;\par \textbf{Step3:}Search space and place the gift according to the model of the algorithm;\par \textbf{Step4:}calculate $M$, output the result.\par Calculated results table at Tab\ref{tab:1}\par \begin{table} \caption{Result} \label{tab:1} \begin{center} \begin{tabular}{cccc} \hline $N$ 30000 100000 1000000\\ $\sigma(p)$ 4968 16553 165503\\ $Max_{z}$ 25647 85090 848464\\ $M$ 56261 186734 1862431\\ \hline \end{tabular} \end{center} \end{table} As can be seen from the table, with the growth in the number of gifts, target showed a basic linear growth, this finding is helpful for large-scale gift space layout of the index forecast.\par \section{Strength and Weakness} \subsection{Strength} \begin{itemize} \item The model has a certain generality and expansibility, and can add the required constraints or change the display target, thus obtains the corresponding display method. \item The strategy is reasonable, and the utilization rate of the space is high according to the display mode. \end{itemize} \subsection{Weakness} \begin{itemize} \item The stability problem in the process of model does not consider,so the results are different from the actual value. \item Computational complexity is larger,the data processing time is long. \end{itemize} \begin{thebibliography}{99} \addcontentsline{toc}{section}{References} \bibitem{a} Yuan Qu, Xuelian Wang. \textsl{An efficient algorithm for three dimensional bin packig problem under complex condition.} Hoisting and Conveying Machinery,2007(8):48-51. \bibitem{b} Zeshuang Chen, Jianming He. \textsl{More hybrid genetic algorithm for unconstrained three-dimensional container.} Modern Computer,2001(1):14-18. \bibitem{c} Martello S, Pisinger D, Vigo D. \textsl{The three packing pmblem. Operations Research, } 2000(48):256-267. \bibitem{d} David Pisinger. \textsl{Heuristics for the Container Loading Problem. } European Journal of Operational Research 141 (2002): 382-392. \bibitem{e} Michael Eley. \textsl{Solving Container Loading Problems by BlockArrangement.} European Journal of Operational Research,141(2002):393-409. \bibitem{f} Kovalyov M Y, Ng C T,Cheng T C, et al. \textsl{Single machine scheduling with a variable common due date and resource-dependent processing times} . Computer and Operations Research, 2003, 30:1173-1185. \end{thebibliography} %====================附录导入程序代码========================================== \begin{appendices} %\renewcommand{\thesection}{\Alph{chapter}.} % \section{First appendix} \textbf{\textcolor {0.98,0.00,0.00}{matlab source:}} \lstinputlisting {./code/Santa_presents.m} % \section{Second appendix} % some more text\textcolor {0.98,0.00,0.00}{\textbf{Input C++ source:}} %\lstinputlisting {./code/sudoku.cpp} \end{appendices}
标签: 论文LATEX格式
