An effective evolutionary algorithm for the multiple container packing problem

Abstract

This paper focuses on a new optimization problem, which is called "The Multiple Container Packing Problem (MCPP)" and proposes a new evolutionary approach for it. The proposed evolutionary approach uses "Adaptive Link Adjustment Evolutionary Algorithm (ALA-EA)" as a basic framework and it incorporates a heuristic local improvement approach into ALA-EA. The first step of the local search algorithm is to raise empty space through the exchange among the packed items and then to improve the fitness value through packing unpacked items into the raised empty space. The second step is to exchange the packed items and the unpacked items one another toward improving the fitness value. The proposed algorithm is compared to the previous evolutionary approaches at the benchmark instances (with the same container capacity) and the modified benchmark instances (with different container capacity) and that the algorithm is proved to be superior to the previous evolutionary approaches in the solution quality. (c) 2007 National Natural Science Foundation of China and Chinese Academy of Sciences. Published by Elsevier Limited and Science in China Press. All rights reserved.