Novel approaches to container loading: from heuristics to hybrid tabu search

2.50
Hdl Handle:
http://hdl.handle.net/10547/295765
Title:
Novel approaches to container loading: from heuristics to hybrid tabu search
Authors:
Liu, Jiamin
Abstract:
This work investigates new approaches to the container loading problem which address the issue of how to load three-dimensional, rectangular items (e.g. boxes) into the container in such a way that maximum utilisation is made of the container space. This problem occurs in several industry sectors where the loading approach places cargo effectively into aeroplanes, ships, trailers or trucks in order to save considerable cost. In carrying out this work, the investigation starts by developing a new heuristic approach to the two-dimensional bin packing problem, which has lower complexity than container loading in the aspects of constraints and geometry. A novel approach, including the heuristic strategies and handling method for remaining areas, is developed that can produce good results when testing with benchmark and real world data. Based on the research for two-dimensional bin packing, a novel heuristic approach is developed to deal with the container loading problem with some practical constraints. The heuristic approach to container loading also includes heuristic strategies and the handling of remaining spaces. The heuristic strategies construct effective loading arrangements where combinations of identical or different box types are loaded in blocks. The handling method for remaining spaces further improves the loading arrangements through the representation, partitioning and merging of remaining spaces. The heuristic approach obtains better volume utilisation and the highest stability compared with other published heuristic approaches. However, it does not achieve as high a volume utilisation as metaheuristic approaches, e.g. genetic algorithms and tabu search.To improve volume utilisation, a new hybrid heuristic approach to the container loading problem is further developed based on the tabu search technique which covers the encoding, evaluation criterion and configuration of neighbourhood and candidate solutions. The heuristic strategies as well as the handling method for remaining spaces developed in the heuristic approach are used in this new hybrid tabu search approach. It is shown that the hybrid approach has better volume utilisation than the published approaches under the condition that all loaded boxes with one hundred per cent support from below. In addition, the experimental results show that both the heuristic and hybrid tabu search approaches can also be applied to the multiple container loading problem.
Citation:
Liu, J. (2008) 'Novel approaches to container loading: from heuristics to hybrid tabu search' PhD thesis. University of Bedfordshire.
Publisher:
University of Bedfordshire
Issue Date:
Apr-2008
URI:
http://hdl.handle.net/10547/295765
Type:
Thesis or dissertation
Language:
en
Description:
A thesis submitted for the degree of Doctor of Philosophy of the University ofBedford shire
Appears in Collections:
PhD e-theses

Full metadata record

DC FieldValue Language
dc.contributor.authorLiu, Jiaminen_GB
dc.date.accessioned2013-07-11T11:35:18Z-
dc.date.available2013-07-11T11:35:18Z-
dc.date.issued2008-04-
dc.identifier.citationLiu, J. (2008) 'Novel approaches to container loading: from heuristics to hybrid tabu search' PhD thesis. University of Bedfordshire.en_GB
dc.identifier.urihttp://hdl.handle.net/10547/295765-
dc.descriptionA thesis submitted for the degree of Doctor of Philosophy of the University ofBedford shireen_GB
dc.description.abstractThis work investigates new approaches to the container loading problem which address the issue of how to load three-dimensional, rectangular items (e.g. boxes) into the container in such a way that maximum utilisation is made of the container space. This problem occurs in several industry sectors where the loading approach places cargo effectively into aeroplanes, ships, trailers or trucks in order to save considerable cost. In carrying out this work, the investigation starts by developing a new heuristic approach to the two-dimensional bin packing problem, which has lower complexity than container loading in the aspects of constraints and geometry. A novel approach, including the heuristic strategies and handling method for remaining areas, is developed that can produce good results when testing with benchmark and real world data. Based on the research for two-dimensional bin packing, a novel heuristic approach is developed to deal with the container loading problem with some practical constraints. The heuristic approach to container loading also includes heuristic strategies and the handling of remaining spaces. The heuristic strategies construct effective loading arrangements where combinations of identical or different box types are loaded in blocks. The handling method for remaining spaces further improves the loading arrangements through the representation, partitioning and merging of remaining spaces. The heuristic approach obtains better volume utilisation and the highest stability compared with other published heuristic approaches. However, it does not achieve as high a volume utilisation as metaheuristic approaches, e.g. genetic algorithms and tabu search.To improve volume utilisation, a new hybrid heuristic approach to the container loading problem is further developed based on the tabu search technique which covers the encoding, evaluation criterion and configuration of neighbourhood and candidate solutions. The heuristic strategies as well as the handling method for remaining spaces developed in the heuristic approach are used in this new hybrid tabu search approach. It is shown that the hybrid approach has better volume utilisation than the published approaches under the condition that all loaded boxes with one hundred per cent support from below. In addition, the experimental results show that both the heuristic and hybrid tabu search approaches can also be applied to the multiple container loading problem.en_GB
dc.language.isoenen
dc.publisherUniversity of Bedfordshireen_GB
dc.subjectG160 Engineering/Industrial Mathematicsen_GB
dc.subjectcontainer loadingen_GB
dc.subjectvolume utilisationen_GB
dc.subjecttabu searchen_GB
dc.titleNovel approaches to container loading: from heuristics to hybrid tabu searchen
dc.typeThesis or dissertationen
dc.type.qualificationnamePhDen_GB
dc.type.qualificationlevelPhDen
dc.publisher.institutionUniversity of Bedfordshireen_GB
This item is licensed under a Creative Commons License
Creative Commons
All Items in UOBREP are protected by copyright, with all rights reserved, unless otherwise indicated.