Container Relocation Problem

[Ermo1994]

Hallo,

Ik ben een 4e jaars student op de opleiding International Logistics & Economics,

Nu moet ik voor het vak Operations Research een Container stacking problem oplossen, met het gebruik van Excel.

De opdracht houdt het volgende in:

Er zijn 999 containers die in een bepaalde volgorde binnenkomen op de terminal en er ook weer uit gaan. Er zijn in totaal 20 locaties die 5 hoog gestapeld mogen worden, dus in totaal 100 locaties.

Elke keer als een container de terminal moet verlaten maar er staat een andere container op zorgt dit voor een extra handeling.

Het doel is om de containers zo te stapelen dat ze de terminal inkomen en verlaten met de minste handelingen.

Mijn vraag is , is dit een probleem dat op te lossen is met excel, zo ja hoe ? (evtl, excel solver)?

Elke tip of hulp is welkom, al is het maar om me op de goede weg te helpen.

In de bijlage de excel file en een uitgebreide uitleg van de opdracht !

 

[snb]

Dit trok mijn aandacht:

here are 999 containers for in- and outbound: this leads to 1898 consecutive moments in time for a container to
arrive or leave.

Zou in plaats van 1898 een aantal van 1998 bewegingen niet correcter zijn ?

 

[Ermo1994]

Ik heb het nagecheckt in de excel file, het zijn inderdaad 1998 bewegingen. Ik denk dat dit een type of reken-fout is geweest !

 

[snb]

Zouden de ingeleverde opdrachten net zo nauwkeurig worden nagekeken ?

 

[cow18]

zonder strategie (= gewoon stapelen op de kleinste stapel en dan volgens rangnummer) 176 en 3649 bewegingen
rekenmethode kan tig keer sneller, maar voorlopig is dat bijkomstig.
Stel anders eens een andere strategie voor ...
Hoe ver kan je in de toekomst kijken en hoe verwerk je die info ?

 

[cow18]

het was iets moeilijker dan de vorige insteek, maar met je opmerkingen en de ervaringen van de terminalmanager van de binnenhaven van Alveringem-Oost kwam ik tot volgende nieuwe oplossing.
Er werd gebruikt gemaakt van het IJB-algortime.
In totaal kwam ik nu op 999 inkom en 999 uitgaande zetten (die zijn vast) en nog 742 jinga's.
Dat is een verbetering van 909 zetten tov. vorige uitgangshypothese.
IK ben er van overtuigd, als we onze kaarten samen leggen, dat we nogmaals zo'n sprong kunnen maken.
PS. macro "containers"

 

[alphamax]

@cow18
Waar kan ik meer vinden van het IJB-algortime en zijn/haar "jinga's", want op google kan ik niets vinden.
Als ik google met "container stack problem algorithm" vind ik wel andere algorithmes en voorstellen.

 

[cow18]

Alphamax,
zoals je uit je zoekresultaten en andere info (PB) weet, jinga's, dat is "containerhandling voor gevorderden".
Er is dus een oplossing mogelijk in 2539 zetten (999 in's, 999 out's en 541 andere)
zie bijlage
update : 512 andere

 

[Ermo1994]

@cow18

Allereerst bedankt voor jou reactie ! heel erg fijn dat je me helpen kan


Ik heb zelf met de eerste data set, die van 62 containers gepuzzeld en kwam tot 140 handelingen, 124 verplichte en 16 re-shufflings.
Dit heeft alleen heel erg lang geduurd en als ik dit ook met 999 containers moet gaan doen ben ik nog wel even bezig !

Ik wil nu gaan beginnen aan de grotere dataset, en zou graag willen weten hoe je tot de oplossing bent gekomen! Ik wil het zelf ook op die manier gaan proberen, maar in jouw file zie ik geen formules of uitleg, dus ik snap niet zo goed hoe je het hebt gedaan.

Alvast bedankt

 

[cow18]

rekentijd voor 62 containers = 0.60 sec, rekentijd voor 999 containers = 7 sec.
62 containers = 62 in's, 62 out's en 27 "re-shufflings".
Dus je algoritme is beter.
Dus hoe deed je het ?

 

[Ermo1994]

Mijn oplossing

Ik heb het handmatig gedaan, dus niet met een algoritme. Dit is wel wat ik graag wil gaan doen, maar ik zou niet weten hoe dit in excel gaat, dus het zou super zijn als je mij kunt uitleggen hoe ik zo'n algoritme die jij hebt gebruikt kan toepassen met excel. De leraar heeft mij gezegd dat puzzelen mag, dus handmatig zoals ik het deed, maar dat een algoritme een hoger punt op zou leveren, daarom zou ik graag willen weten hoe.

In de bijlage is mij handmatige oplossing ( 2e tab in excel)
ook mijn rapport (nog niet af) heb ik in de bijlage gezet, in chapter 3 leg ik stap voor stap uit hoe ik tot mijn uitkomst ben gekomen.

 

[cow18]

ik kan je schema nog niet helemaal vatten.
Zit nu op 19 reshuffles, nog niet op je bedoelde 16, kan nog niet vinden waar die laatste 3 zitten.
Grappig, maar door de toegepaste veranderingen zit ik nu in het 999-verhaal plots aan 590 reshuffles.
Te gek voor woorden.

Aangezien de rekentijd te verwaarlozen is, 7 sec, zou er kunnen geopteerd worden om meerdere scenario's te testen en dan de beste te nemen.

Voorlopig ga ik er nog steeds van uit dat je vooraf het volledig overzicht van die momenten had. Ik dacht begrepen te hebben, dat je die info maar geleidelijk tijdens het proces kreeg.

 

[Ermo1994]

Algoritme

Ja. het is een planning, dus je weet van te voren wat er op welk moment in en uit gaat.


ik ben ondertussen de zelfde methode op de grote data-set aan het gebruiken, maar dit is kost zo veel tijd dat ik nooit aan alle containers toe kom Moet dit vannacht voor 12 inleveren.

Met een algoritme zou dit wel kunnen, al weet ik niet hoe dit mogenlijk is, zou je die van jou kunnen uitleggen en me vertellen hoe ik deze zelf kan toepassen?

Alvast bedankt

 

[cow18]

in bijlage het excel-bestand.
in tabblad result :
* cel E37: kiezen tss 0 en 1 = tussenresultaten tonen, levert alleen veel schermflikkering op, maar oogt wat spectaculairder. Verdubbelt de rekentijd zonder toegevoegde waarde.
* groene knop "run 999 containers" laat de macro lopen en schrijft per zet de tussenstanden bij iedere zet weg naar AA:AZ

nu kan je nog extra punten scoren voor je werk, want de opzet laat zo toe dat je stoeit met parameters.
Ga bv. naar tabblad "data1" en verander max stacks naar 19 of 18 (=loopt vast) in de éne richting of 21, 22, ..., 25 in de andere richting.
Geef het aantal reshuffles tov max stacks mooi weer in een grafiekje en concludeer dat extra stacks daarop een buitenproportionele invloed hebben, reken eventueel wat de investering in een extra stack als besparing heeft op operationele kosten of zo.

Zie ook PB, bij de meldingen, rechtsboven.

2e bestand = VBA gekopieerd naar een werkmap, zodat je die gemakkelijker kan afprinten eventueel.

Ik moet nu wel 3 uur gaan werken !!!

 

[cow18]

Op deze site staan een groepje fanatiekelingen klaar om de vragen van anderen belangeloos op te lossen, in ruil zou er op zijn minst een dankwoordje afkunnen.
Wat ik met deze vraagsteller tegen kwam stoot me enorm tegen de borst en doet me twijfelen om me nog verder in te zetten.
Even de situatie schetsen.
* vrijdag 1/2 om 15:00 opent TS een login en stelt zijn 1e vraag, op het eerste zicht een duidelijke schoolvraag, maar dan eerder van de universiteit of zo.
er zijn wat andere tussenkomsten, eerder opmerkingen.
* om 20:00 geef ik een 1e voorzet, met meegeleverde excelfile, met de duidelijke melding, dat dit een oplossing zonder strategie was. Gewoon zet de containers ergens neer en haal ze dan weer op. Er waren dus iets van een 1.700 extra bewegingen nodig.
Ik wacht op een reactie van TS, aangezien het een schoolvraag is, moet hij me maar een strategie voorstellen.
* zo 3/2 om 22:00, nog steeds geen reactie van TS, geef ik een 2e voorzet, opnieuw met excelfile, maar gebruik ik de jenga-techniek, een grapje, jenga is een spel voor kleine en iets minder kleine kinderen (zie onderaan video)
Alphamax is er snel bij om uitleg te vragen over het algoritme, daarvoor stuur ik hem een PB-tje.
* ma 4/2 7:00 zonder excelfile zeg ik dat ik op dat moment op 712 extra bewegingen zit.
* ma 4/2 om 11:00, 3 dagen na zijn vraag, komt er een eerste voorzichtige vraag van TS over de oplossing. Daar deelt hij mee dat hij, voor het kleine 66-model op 16 extras zit.
* ma 4/2 om 13:30, ik had eventjes het model aangepast naar de kleine versie, moet ik vaststellen dat ik het met 27 extras moet doen. Dus vraag ik zijn algoritme en via PB geef ik hem mijn emailadres om gemakkelijker te communiceren.
* ma 4/2 om 14:00 stuurt TS zijn voorlopige oplossing (excel & Wordfile).
* ma 4/2 om 16:00 zit ik op 19 extras, ik vind niet meer hoe ik daaraan kwam, maar tot daar. Er wordt me om het algoritme gevraagd.
* ma 4/2 om 17:30 stuur ik mijn excelfile met mijn oplossing en de gebruikte macros netjes op
* ma 4/2 om 20:00 krijg ik mijn eerste en enige mail van TS binnen, nogmaals met de vraag om het algoritme in enkele simpele excelformules te tonen. Daarin hoor ik ook dat de deadline op 24:00 staat.
Ik stuur nog 2 mails, maar vanaf dan is de lijn dood.
* di 5/2 om 7:00 stuur ik hem een mail dat in zijn versie duidelijk fouten zitten. Je kan die zo zien in het excelbestand laatste tabblad momenten 21,35 en 37. Dat zijn duidelijke jengas. Dus is zijn oplossing fout en zit ik toch nog goed op de rails.
Ik had ook een versie van zijn ingediend verslag gevraagd, tja ... .

Dus bij deze gooi ik even mijn frustratie en mijn finale versie hier neer.
Normaliter mag er op deze manier geen gal gespogen worden, maar tot daar, het moest er uit.

Nu nog even uitleg wat een jenga voor volwassenen is : https://www.youtube.com/watch?v=DWc8dUl7Xfo

 

[samabert]

@cow18

Er zijn op dit forum meer dankbare vraagstellers dan andere en die appreciëren heel erg wat jij en de andere hulpverleners voor ons uitwerken en bouwen.
Graag niet twijfelen om je verder in te zetten.

Ik weet niet of je de link met Worksheet.nl en het Belgisch leger nog weet? Jouw geboden hulp is na jaren nog altijd in gebruik waarvoor dank!

Mvg.
Marc

 

[HSV]

@cow18,

Gewoon doorgaan Bart.
Ik kan me indenken dat je gefrustreerd bent hoor, maar dit gaat het toch niet verzieken voor je?; weegt ook niet op tegen de lol om oplossingen bedenken voor anderen die wel netjes een bedankje achterlaten.


Ik wil je wel een advies meegeven.
Zodra er het woord 'haast, deadline' of iets dergelijks staat...., de vraag dood laten bloeden.
Er zit geen emotie bij; in de zin van, "het is niet voor eigen gebruik".

Ik ben daar al een aantal keren mee op de koffie gekomen.

 

[E v R]

@cow18,

Hoewel ik dit draadje (nog) niet gevolgd heb, worden normaliter draadjes niet alleen door de TS gevolgd maar ook door anderen die er wat van op willen en kunnen steken. Ik kan uit eigen ervaring zeggen dat dit in jouw geval zeer zeker het geval is! :thumb:

 

[Excelbat]

Inderdaad, ik lees altijd graag de bijdragen van Cow18. Glasheldere uitleg en een haast ongeëvenaard vermogen tot oplossen van rekenproblemen.

Greetz/Excelbat