Geoptimaliseerde laadplanning aan boord van tankers en bulkschepen

Tim
Pintens

                                                                                        

Automatisatie en optimalisatie van               laadplanning     voor   tankers    en   bulkschepen:

toekomstperspectief met “OptiLoading”

Het vervoer van goederen over zee is wereldwijd in volle expansie door de verhoogde vraag naar

grondstoffen en energie. Een belangrijk deel van dit transport bestaat uit onverpakte goederen

(bulkproducten of stortgoed, zoals graan, erts, steenkool) en vloeibare stoffen (petroleum, gas,

scheikundige producten).

Vooraleer een schip voor een nieuwe reis geladen wordt stelt men een laadplan op. Hierbij wordt,

voor elk deel van de vervoerde lading, beslist in welke tank of in welk deel van het ruim deze lading

zal gestouwd worden. De manier waarop het schip geladen wordt, bepaalt in grote mate de

stabiliteit en het gedrag van het schip tijdens de reis. Het is dus van groot belang voor de veiligheid

van het schip, zijn bemanning en lading. Het laadplan beïnvloedt ook een aantal economische

factoren zoals de hoeveelheid lading die kan vervoerd worden.

Een goed laadplan zoekt daarom steeds een evenwicht tussen de vele technische eisen (rond

veiligheid, stabiliteit en belasting van het schip) en de economische belangen van de rederij en haar

klanten. Door de grote complexiteit van het probleem is het opstellen van een aanvaardbaar

laadplan een zeer tijdsintensieve taak. Voor het veilig en efficiënt uitvoeren ervan is bovendien veel

kennis en ervaring vereist. Het opstellen van het laadplan wordt daarom aan de eerste stuurman

toegewezen.

Bij tankers en bulkschepen hebben we te maken met onverpakte ladingen. Elk compartiment mag

daarom slechts één soort lading bevatten. Momenteel wordt het laadplan voor tankers en

bulkschepen manueel opgesteld en daarna gecontroleerd met een speciaal computerprogramma. De

huidige laadprogramma's voor tank- en bulkschepen kunnen, vertrekkend van het ingegeven

(manueel opgestelde) laadplan, de diepgangen, slagzij en trim (het verschil in diepgang van het

schip voor- en achteraan), de stabiliteit en de belasting van het schip berekenen. Zij kunnen nagaan

of aan alle technische eisen rond veiligheid voldaan is.

Aanvaardbare laadplannen zijn meestal niet uniek. Er bestaan steeds meerdere oplossingen die aan

de minimale criteria voldoen. Eén oplossing kan echter duidelijke voordelen bieden. Een laadplan

waarbij bijvoorbeeld 99 % van de maximaal toelaatbare belasting bereikt wordt, is perfect binnen

de vooropgestelde criteria, maar in vele gevallen zullen “betere” oplossingen bestaan, waarbij de

belasting op het schip een stuk lager ligt.

Op zoek gaan naar een beter laadplan, wanneer je al een aanvaardbaar laadplan in handen hebt, is in

de huidige situatie niet vanzelfsprekend. Het manueel opstellen en berekenen van een ander

laadplan is zeer tijdrovend en levert niet gegarandeerd de gewenste verbetering op. Het is ook

praktisch onmogelijk om alle mogelijke oplossingen met elkaar te vergelijken om zo het best

mogelijke laadplan te kiezen. In deze eindverhandeling zochten we daarom naar methodes om

automatisch, met behulp van een computer, een zo goed mogelijk (optimaal) laadplan op te stellen,

en de eerste officier dus te adviseren bij het uitvoeren van deze taak.

Automatische optimalisatie van het laadplan biedt een reeks duidelijke voordelen:

    • De veiligheid van het schip en zijn opvarenden wordt verhoogd door een verbeterde

         stabiliteit.

    •    De gemiddelde belasting over de levensduur van het schip zal lager liggen waardoor de

         levensduur mogelijk verlengd wordt.

    • Door optimaal gebruik te maken van de beschikbare compartimenten kan het aantal

         gebruikte compartimenten verlaagd worden. Hierdoor wordt de duur van een havenbezoek

         verkort en worden de kosten voor tankreiniging verlaagd.

    • De taak van de eerste officier wordt gevoelig verlicht. Het door de computer opgestelde

         laadplan wordt best als advies beschouwd en dient steeds door de eerste officier

         gecontroleerd te worden voor het effectief gebruikt wordt. Zijn kennis en ervaring blijven

         noodzakelijk. Het meest tijdrovende deel van deze taak wordt echter door de computer

         uitgevoerd.

In de eerste plaats hebben we onderzocht of dit vraagstuk kan behandeld worden als een probleem

van lineaire programmering. Hierbij wordt een laadplan, samen met alle randvoorwaarden rond

stabiliteit en veiligheid, vertaald in een stel eenvoudige wiskundige vergelijkingen. Om twee

laadplannen te vergelijken maken we gebruik van een “doelfunctie”. Dit is een wiskundige

uitdrukking die op een objectieve manier tracht de “kwaliteiten” en “minpunten” van het laadplan te

meten. Het opbouwen van deze functie vormt één van de grootste problemen bij het ontwikkelen

van deze techniek. Het is immers moeilijk om objectief vast te leggen waarom het ene laadplan

beter is dan het andere.

Eens het probleem van laadplanning in deze vorm beschreven is, reikt de wiskunde efficiënte

technieken aan (het “simplexalgoritme”) voor het bepalen van het best mogelijke laadplan.

Om de voorgestelde optimalisatietechnieken in de praktijk te testen, werd een softwarepakket

ontwikkeld: “Optiloading”. Dit programma gebruikt een eenvoudige beschrijving van de lading die

moet worden gestouwd (gewenste hoeveelheid van elk product) en berekent zelf het best mogelijke

laadplan. Praktische proeven met deze software wijzen uit dat met de lineaire programmering

inderdaad zeer goede laadplannen bekomen worden. Naarmate het aantal verschillende ladingen

toeneemt (wat vaak voorkomt bij chemicaliëntankers), neemt de rekentijd, nodig voor het bepalen

van deze oplossingen, echter zodanig snel toe dat de methode praktisch onbruikbaar wordt.

In een tweede deel van dit werk hebben we daarom onderzocht of dit probleem ook kan aangepakt

worden met andere optimalisatietechnieken. Hier hebben we ons gericht op “heuristische”

methodes, waarbij geprobeerd wordt steeds betere laadplannen te vinden door telkens opnieuw

kleine wijzigingen aan te brengen aan reeds gekende oplossingen. Vaak probeert men bij deze

technieken een verbeteringsproces uit de natuur na te bootsen. Dit is bijvoorbeeld het geval bij

“genetische algoritmes”, die hun inspiratie putten uit de evolutietheorie.

Voor het verbeteren van laadplannen hebben we een methode ontwikkeld die gebruik maakt van

“simulated annealing”, een optimalisatietechniek die inspiratie put uit een techniek voor het harden

van metaal door langzame afkoeling.

Ook deze optimalisatietechniek werd geïntegreerd in het softwarepakket “Optiloading”. Bij proeven

blijkt dat de heuristische methode sneller werkt, maar dat de oplossingen van een iets mindere

kwaliteit zijn dan bij lineaire programmering. In vergelijking met manueel opgestelde laadplannen

leiden beide optimalisatietechnieken echter tot een verbeterde laadconditie.

Rond dit onderzoeksproject werd tenslotte ook een website opgebouwd, www.optiloading.be.

Het programma “Optiloading” kan hier gedownload en uitgetest worden.

 

Bibliografie

Bibliografie

 [1] Chemical Hazards Response Information System. http://www.chrismanual.com.

 [2] GLPK. http://www.gnu.org/software/glpk/.

 [3] GNU GPL. http://www.gnu.org/licenses/.

 [4] IMO. http://www.imo.org.

 [5] LP Solve. http://lpsolve.sourceforge.net/5.5/.

 [6] Nonlinear programming frequently asked questions. http://www-unix.mcs.anl.

    gov/otc/Guide/faq/nonlinear-programming-faq.html.

 [7] Wikipedia. http://www.wikipedia.org.

 [8] Alves C. and Valrio de Carvalho J-M. Accelerating column generation for variable

    sized bin-packing problems. European Journal of Operational Research, 183:1333–1352, 2006.

 [9] Alves C. and Valrio de Carvalho J-M. A stabilized branch-and-price-and-cut algorithm for the

    multiple length cutting stock problem. Computers and Operations Research, 35:1315–1328,

    2006.

[10] J.W. Chinneck. Practical Optimization: a Gentle Introduction. Carleton University, 2000.

     Niet gepubliceerde cursus.

[11] Pisinger D. and M. Sigurd. The two-dimensional bin packing problem with variable bin sizes

    and costs. Discrete Optimization, 2:154–167, 2005.

[12] H. Dyckhoff and U. Finke. Cutting and packing in production and distribution.

    Heidelberg: Physica Verlag, 1992.

[13] D.K. Friesen and M.A. Langston. Variable sized bin packing. SIAM Journal on Computing,

    15:222–230, 1986.

[14] Belov G. and G. Scheithauer. A cutting plane algorithm for the one-dimensional

    cutting stock problem with multiple stock lengths. European Journal of Operational Research,

    141:274–294, 2002.

[15] W. Gelade. Benaderingsalgoritmen. bachelorthesis, Universiteit Limburg, 2005.

[16] P. Giemsch. Stowage planning and pile problems. 2004.

[17] R.L. Graham. Bounds on performance of scheduling algorithms. Computer and Job-Shop

    Scheduling Theory, 1976.

[18] P. Hoffman. The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for

    Mathematical Truth. New York: Hyperion, 1998.

[19] H. Hoogeveen. Optimalisering. Universiteit Utrecht, 2006. Niet gepubliceerde cursus.

[20] IMO. MARPOL 73/78, Consolidated edition 2002. IMO Publishing, 2002.

[21] IMO. Load Lines, Consolidated Edition 2005. IMO Publishing, 2005.

[22] E.I. Kaisar. A stowage planning model for multiport container transportation. PhD thesis,

   University of Maryland, 2006.

[23] L.C.M. Kallenberg. Besliskunde. Universiteit Leiden, 2005. Niet gepubliceerde cursus.

[24] J. Kang and S. Park. Algorithms for the variable sized bin packing problem.

   European Journal of Operational Research, 147:365–372, 2003.

[25] M. Monacci. Algorithms for packing and scheduling problems. PhD thesis, Universitá di

   Bologna, 2002.

[26] T. Pintens. Geoptimaliseerde laadsimulatie. bachelorthesis, Hogere Zeevaartschool Antwerpen,

   2007.

[27] K.J. Sijsling. Technieken van Operations Research. Academic Service, third edition, 1997.

[28] C. van Heule. Metaheuristieken. Sint-Lieven Hogeschool, 2006. Niet gepubliceerde cursus.

[29] D.C. van Leijenhorst. Complexiteitstheorie. North Star Publications, Radboud Universiteit

   Nijmegen, 2006. Een beknopte inleiding in 12 voordrachten.

[30] G. Vanden Berghe. Datastructuren en Algoritmen. KaHo Sint-Lieven, 2004. Niet

   gepubliceerde cursus.

                                 ̈

[31] G. Vanden Berghe. Artificiele Intelligentie. KaHo Sint-Lieven, 2006. Niet gepubliceerde

   cursus.

[32] V.V. Vazirani. Approximation algorithms. Springer, 2003.

[33] G. A. Vouros, T. Panayiotopoulos, and C.D. Spyropoulos. A framework for developing expert

   loading systems for product carriers. Expert Systems with Applications, 10:113–126, 1996.

 

Download scriptie (55.23 KB)
Universiteit of Hogeschool
Hogere Zeevaartschool Antwerpen
Thesis jaar
2008