Container loading with multi-drop constraints |
| | Abstract | In this thesis, we develop an algorithm for the container loading problem (CLP) with multi-drop constraints. The CLP is the problem of loading the maximal value of a set of boxes into a container, while ensuring that the boxes neither overlap each other nor the container walls. By adding multi-drop constraints it is further demanded, that the relevant boxes must be available, without rearranging others, when each drop-off point is reached.
The algorithm is made with a setup in mind, where the CLP will be solved as a feasibility check on a route suggested by a vehicle routing application. Therefore solutions must be obtained fast. Furthermore it is demanded, that packings must be feasible in a real world scenario. The latter is accomplished by a detailed model, which makes sure that all boxes are placed multi-drop feasible, properly supported and only rotated in feasible directions. It is also assured, that boxes that are stacked, are not damaged. Based on the model, a tree search framework has been developed. The tree search utilises different greedy methods to evaluate the potential of each node considered. To make the framework more generic, a dynamic breadth is proposed. Based on problem characteristics and the time limit imposed, it will choose the breadth of the tree, making sure that the time is utilised most profitable.
The algorithm is tested on data from the two Danish companies Aarstiderne and Johannes Fog. The obtained results show, that the proposed model and algorithm is able to solve these problems within a reasonable time, giving solutions that respect all the constraints imposed and are feasible in a real world scenario. | | Keywords | Container Loading, Vehicle Routing, Multi-drop, Heuristics, Tree search | | Type | Master's thesis [Industrial collaboration] | | Year | 2007 | | Publisher | Informatics and Mathematical Modelling, Technical University of Denmark, DTU | | Address | Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby | | Series | IMM-Thesis-2007-37 | | Note | Supervised by Associate Professor Jesper Larsen, IMM, DTU. From Transvision A/S Jakob Birkedal Nielsen supervised the project. | | Electronic version(s) | [pdf] | | BibTeX data | [bibtex] | | IMM Group(s) | Operations Research |
|