A HYBRID SIMULATED ANNEALING ALGORITHM FOR SOLVING MULTI-OBJECTIVE CONTAINER-LOADING PROBLEMS

Figures & data

FIGURE 1 Empty space in front and above of the LDB.

FIGURE 2 Empty space beside a packed box in the layer.

FIGURE 3 The proposed heuristic filling procedure.

FIGURE 4 Neighborhood solution generation using the flip operator (only for base-rotated boxes).

FIGURE 5 Neighborhood solution generation using the flip operator (rotation in any orientation is possible).

TABLE 1 A Pseudo-code of the Proposed SA

Step 1. Generate an initial solution and calculate the sum of the weighted goal deviations to form the fitness value fitness0 using the heuristic filling algorithm:

Step 2. Parameter initialization:2.1. Set the annealing parameters: T in., T f , il max , and α.2.2. Read the number of box types N.

Step 3. Annealing schedule:3.1. Inner loop initialization; il = 0.3.2. At every temperature achieve equilibrium. Execute inner loop until the condition in 3.2.4 is met.3.2.1. il = il + 1;3.2.2. Generate a neighborhood solution and calculate the sum of the weighted goal deviations to form the fitness value fitness il using the heuristic filling algorithm;3.2.3. Accept or reject the solution as described by the weighted GP approach;3.2.4. IF (il ≥ il max ) THEN terminate inner loop and GOTO step 3.3 ELSE continue inner loop and GOTO step 3.2.1 3.3. T iter+1 = α*T iter ;3.4. IF (T iter+1 < T f ) THEN terminate inner loop and GOTO step 4 ELSE continue inner loop and GOTO step 3.1

Step 4. Terminate the best solution and stop.

TABLE 2 Comparative Results with the Test Cases of Loh and Nee (1992)—Heuristic Approaches

	Packing density (%)	Volume utilization (%)
Problem	(Loh and Nee 1992)	(Ngoi, Tay, and Chua 1994)	(Bischoff, Janetz, and Ratcliff 1995)	(Bischoff and Marriott 1990)	(Eley 2002)	(Bischoff 2003)	(Lim, Rodrigues, and Yang 2005)
LN01	78.1	62.5	62.5	62.5	62.5	NC*	62.5
LN02	76.8	80.7	89.7	90.0	90.8	NC*	80.4
LN03	69.5	53.4	53.4	53.4	53.4	NC*	53.4
LN04	59.2	55.0	55.0	55.0	55.0	NC*	55.0
LN05	85.8	77.2	77.2	77.2	77.2	NC*	76.7
LN06	88.6	88.7	89.5	83.1	87.9	NC*	84.8
LN07	78.2	81.8	83.9	78.7	84.7	NC*	77.0
LN08	67.6	59.4	59.4	59.4	59.4	NC*	59.4
LN09	84.2	61.9	61.9	61.9	61.9	NC*	61.9
LN10	70.1	67.3	67.3	67.3	67.3	NC*	67.3
LN11	63.8	62.2	62.2	62.2	62.2	NC*	62.2
LN12	79.3	78.5	76.5	78.5	78.5	NC*	69.5
LN13	77.0	84.1	82.3	78.1	85.6	NC*	73.3
LN14	69.1	62.8	62.8	62.8	62.8	NC*	62.8
LN15	65.6	59.5	59.5	59.5	59.5	NC*	59.5
Mean	74.19	69.00	69.54	68.64	69.91	—	67.05

TABLE 3 Comparative Results with the Test Cases of Loh and Nee (1992)—Metaheuristic Approaches

	Volume utilization (%)
Problem	(Gehring and Bortfeldt 1997)	(Bortfeldt and Gehring 1998)	(Bortfeldt and Gehring 2001)	(Gehring and Bortfeldt 2002)	(Bortfeldt, Gehring, and Mack 2002)	(Moura and Oliveira 2005)	This work
LN01	62.5	65.5	62.5	NC*	NA**	NA**	62.5
LN02	90.7	96.7	89.8	NC*	NA**	NA**	90.1
LN03	53.4	53.4	53.4	NC*	NA**	NA**	53.4
LN04	55.0	55.0	55.0	NC*	NA**	NA**	55.0
LN05	77.2	77.2	77.2	NC*	NA**	NA**	77.2
LN06	91.1	96.3	92.4	NC*	NA**	NA**	85.8
LN07	82.7	84.7	84.7	NC*	NA**	NA**	84.2
LN08	59.4	59.4	59.4	NC*	NA**	NA**	59.4
LN09	61.9	61.9	61.9	NC*	NA**	NA**	61.9
LN10	67.3	67.3	67.3	NC*	NA**	NA**	67.3
LN11	62.2	62.2	62.2	NC*	NA**	NA**	62.2
LN12	78.5	78.5	78.5	NC*	NA**	NA**	78.1
LN13	85.6	85.6	85.6	NC*	NA**	NA**	83.9
LN14	62.8	62.8	62.8	NC*	NA**	NA**	62.8
LN15	59.5	59.5	59.5	NC*	NA**	NA**	59.5
Mean	69.99	71.07	70.15	—	70.90	70.30	69.55

TABLE 4 Comparative Results with the Test Cases of Bischoff and Ratcliff (1995) (BR1 to BR7)—Heuristic Approaches

	Volume utilization (%)
Problem	(Bischoff, Janetz, and Ratcliff 1995)	(Bischoff and Ratcliff 1995)	(Eley 2002)	(Bischoff 2003)	(Lim, Rodrigues, and Yang 2005)
BR1	81.76	83.79	NA**	89.39	87.40
BR2	81.70	84.44	NA**	90.26	88.70
BR3	82.98	83.94	NA**	91.08	89.30
BR4	82.60	83.71	NA**	90.90	89.70
BR5	82.76	83.80	NA**	91.05	89.70
BR6	81.50	82.44	NA**	90.70	89.70
BR7	80.51	82.01	NA**	90.44	89.40
Mean	81.97	83.45	88.75	90.55	89.13

TABLE 5 Comparative Results with the Test Cases of Bischoff and Ratcliff (1995) (BR1 to BR7) —Metaheuristic Approaches

	Volume utilization (%)
Problem	(Gehring and Bortfeldt 1997)	(Bortfeldt and Gehring 1998)	(Bortfeldt and Gehring 2001)	(Gehring and Bortfeldt 2002)	(Bortfeldt, Gehring, and Mack 2002)	(Moura and Oliveira 2005)	This work
BR1	85.80	92.63	87.81	88.10	93.52	89.07	86.38
BR2	87.26	92.70	89.40	89.56	93.77	90.43	87.70
BR3	88.10	92.31	90.48	90.77	93.58	90.86	87.06
BR4	88.04	91.62	90.63	91.03	93.05	90.42	86.61
BR5	87.86	90.86	90.73	91.23	92.34	89.57	86.10
BR6	87.85	90.04	90.72	91.28	91.72	89.71	85.47
BR7	87.68	88.63	90.65	91.04	90.55	88.05	84.49
Mean	87.51	91.26	90.06	90.43	92.65	89.73	86.26

TABLE 6 An Order List Including All of the Required Data for Multi-Objective CLP

Product ID	Product description	Dimensions (cm) width/ depth/height	Number of boxes	Weight of boxes (kg)	Total volume (cm^3)
1	Detergent	40/36/28	325	20	13,104,000
2	Bleaching liquid	54/28/30	25	22	1,134,000
3	Personal care	54/28/30	75	2.35	3,402,000
4	Detergent	39/29/32	75	20	2,714,400
5	Shaving product	15/10/20	10	1.47	30,000
6	Baby care	42/37/25	150	2.8	5,827,500
7	Toothpaste	36/18/18	3	3.72	34,992
8	Shampoo	18/17/22	25	4.97	168,300
9	Shampoo	22/17/22	50	5	411,400
10	Shampoo	12/11/16	5	1.33	10,560
11	Bleaching liquid	30/27/40	20	17.6	648,000
12	Shaving product	19/7/21	3	0.12	8379
Total			766	9905.37	27,493,531

TABLE 7 Results Obtained for the Multi-Objective Container-Loading Problem

Weights (Goal 1, Goal 2)	(0.1, 0.9)	(0.2, 0.8)	(0.3, 0.7)	(0.4, 0.6)	(0.5, 0.5)	(0.6, 0.4)	(0.7, 0.3)	(0.8, 0.2)	(0.9, 0.1)
	6713.37	6713.37	7157.06	7157.06	7150.41	7150.41	7150.41	7151.37	7151.37
Goal 2— volume util.	87.51	87.51	86.13	86.13	86.09	86.09	86.09	85.96	85.96
Dev. from Goal 1 (kg)	486.63	486.63	42.94	42.94	49.59	49.59	49.59	48.63	48.63
Dev. from Goal 2 (%)	12.49	12.49	13.87	13.87	13.91	13.91	13.91	14.04	14.04
Weighted sum of deviations	0.119169	0.113438	0.098879	0.085606	0.072994	0.059773	0.046551	0.033483	0.020119

FIGURE 6 Convergence graph for the first goal.

FIGURE 7 Convergence graph for the second goal.

FIGURE 8 Filled container. (A) Side view; (B) top view.

Loh , H. T. , and A. Y. C. Nee . 1992 . A packing algorithm for hexahedral boxes. In Proceedings of the Industrial Automation Conference, 115–126. Singapore.

 Google Scholar

Bischoff , E. E. , and M. S. W. Ratcliff . 1995 . Loading multiple pallets . Journal of Operational Research Society , 46 : 1322 – 1336 .

 Web of Science ®Google Scholar