## Abstrakt

Container vessel stowage is a combinatorial optimization problem with

both high economic and environmental impact. The most successful

approaches to tackle this problem use hierarchical decompositions in

which the sub-problems of these decompositions assign containers to

slots in individual vessel bays. Due to the large number of

sub-problems, they must each be solved fast to generate complete

stowage plans within the time requirements and computational resource

limits of the shipping industry. In this paper we present the first

independent study of these sub-problems. We introduce an accurate

representative model of them developed with our industrial partner and

a constraint programming (CP) and integer programming approach to

solve them optimally. Our experimental evaluation of 236 instances

extracted from real stowage plans shows that, even though these

sub-problems are theoretically hard, they are often easy to solve in

practice. Using state-of-the-art CP software on our CP model, we were

able to solve 92% of the instances to optimality within one

second. Thus, somewhat to our surprise, it is possible to define an

optimal model that can be solved fast enough to be used directly in a

stowage planning tool.

both high economic and environmental impact. The most successful

approaches to tackle this problem use hierarchical decompositions in

which the sub-problems of these decompositions assign containers to

slots in individual vessel bays. Due to the large number of

sub-problems, they must each be solved fast to generate complete

stowage plans within the time requirements and computational resource

limits of the shipping industry. In this paper we present the first

independent study of these sub-problems. We introduce an accurate

representative model of them developed with our industrial partner and

a constraint programming (CP) and integer programming approach to

solve them optimally. Our experimental evaluation of 236 instances

extracted from real stowage plans shows that, even though these

sub-problems are theoretically hard, they are often easy to solve in

practice. Using state-of-the-art CP software on our CP model, we were

able to solve 92% of the instances to optimality within one

second. Thus, somewhat to our surprise, it is possible to define an

optimal model that can be solved fast enough to be used directly in a

stowage planning tool.

Originalsprog | Engelsk |
---|

Forlag | IT-Universitetet i København |
---|---|

Antal sider | 21 |

ISBN (Elektronisk) | 9788779492264 |

Status | Udgivet - okt. 2010 |