Premium
Container loading with multi‐drop constraints
Author(s) -
Christensen Søren Gram,
Rousøe David Magid
Publication year - 2009
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00714.x
Subject(s) - computer science , mathematical optimization , benchmark (surveying) , greedy algorithm , heuristic , drop (telecommunication) , container (type theory) , point (geometry) , grasp , tree (set theory) , algorithm , mathematics , engineering , mechanical engineering , telecommunications , geometry , geodesy , geography , mathematical analysis , programming language
In this paper, an algorithm for the container‐loading problem (CLP) with multi‐drop constraints is presented. When adding multi‐drop constraints, we demand that the relevant boxes must be available, without rearranging others, when each drop‐off point is reached. To make the solutions feasible in the real world, it is further demanded that all boxes are placed in a feasible manner with respect to load‐bearing strength and with proper support from below. This makes it possible to load consignments originating from builder merchants. A heuristic based on a tree search framework is proposed. It uses greedy solutions to evaluate each choice taken. 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 profitably. The algorithm is tested on new real‐world data from a Danish company distributing construction products. For the solutions to these problems to be feasible in a real‐world setting, both multi‐drop and load‐bearing strength constraints are essential. The obtained results show that the proposed model and algorithm are able to solve the new real‐world problems in fractions of a second. Furthermore, results obtained on benchmark problems indicate that the algorithm performs comparably with other more specialised methods.