Contents
Case: #onDroneDemand
Naar een idee van Jelle van Assema.
Drone delivery! De concurrentie is bij webwinkels en warenhuizen om te snijden, en om je als winkel een beetje te onderscheiden willen we razendsnelle bezorging. Dus laten we drones inzetten zoals Amazon dat hoopt te doen.De vraag is dan, hoe krijgen we zo snel mogelijk de bestellingen bij klanten d.m.v. onze drones?
Het idee voor de case is als volgt. Klanten plaatsten bestellingen. Alle bestellingen zijn dus bekend voor het roosteren begint. Een bestelling is een verzameling van één of meer pakketten die allemaal geleverd moeten worden voordat de bestelling voltooid is. Pakketten bevinden zich in warenhuizen. Warenhuizen zijn daarmee verzamelingen van pakketten, maar let op de voorraad kan ook opraken of niet aanwezig zijn. Drones kunnen één pakket tegelijk ophalen in een warenhuis en dit pakket vervolgens afleveren bij de klant. Dit alles vindt plaats op een grid van x bij y, met w warenhuizen, k klanten en o orders. Op elk plekje van het grid kan zich een klant bevinden of een warenhuis. Maarja, drones kunnen vliegen dus die doen niet aan Manhattan distance. Drones vliegen met de snelheid van één vakje per tijdseenheid, en dan is de tijd van x1,y1 naar x2,y2 gelijk aan ceil(((x1 - x2)**2 + (y1 - y2)**2)**(1/2)). Ofwel, Pythagoras naar boven afgerond. Het laden en ontladen van een drone kost geen tijd. Als de batterij op is, vervangen we deze door een reserve. Een drone kan altijd vliegen.
Nu is de taak, hoe krijgen we bestellingen zo snel mogelijk afgerond. Wat dit precies betekent is nog open. Zijn we geïnteresseerd in de laatste bestelling (zwakste schakel bepaalt score), of is elke afgeronde bestelling punten waard t.o.v. de tijd dat deze is afgerond?
Dan zijn alle parameters nog te bepalen: Hoeveel klanten met hoeveel bestellingen en waar? Hoeveel drones hebben we? Hoeveel warenhuizen met hoeveel pakketten en waar?
Hoe kunnen we het in deze case nou lastig, makkelijk of onmogelijk maken om een goede score te scoren? Terwijl we het toch toegankelijk houden voor de studenten.
ps. Dit naar aanleiding van Google HashCode 2015
Case: Air Cargo
Je hebt n items met een waarde w1 ... wn en een gewicht g1 ... gn. Stop zoveel mogelijk waarde in drie vliegtuigen met draagcapaciteit d1,d2,d3.
1) Pak vliegtuig 1 in met zoveel mogelijk waarde. Pak vliegtuig 1 en 2 in met zoveel mogelijk waarde.
2) Pak vliegtuigen 1, 2en 3 in met zo veel mogelijk waarde. Is vliegtuig 1 veranderd tijdens het proces?
3)
4)
5)
Case: staalplaats
Naar een suggestie van Misha Paauw.
Onze huidige tegelzetcase is de enige zuivere 'constraint satisfaction'-case. Daardoor is hij minder geschikt voor simulated annealing, genetic algorithms and so forth. We willen er eigenlijk een 'cutting stock' van maken.
Er is een staalfabriek die platen staal heeft/maakt/walst van een zeker dimensie x en y. Liefst identiek aan Tata staal of een andere echte staalfabriek. Ze hebben dus een stock van platen, en krijgen orders binnen voor rechthoekige stukken staal, zoals voor de autoindustrie, de scheepsbouw etcetera.
1) Een order O1 met n rectangles van dimensies whatever (zie lijst) komt binnen. Hoeveel platen heb je minimaal nodig?
2)
3)
4)
5)
Case: smart grid
Dit is in een idee van Alex Wittebrood. Er is een kaart waarop twee soorten knooppunten liggen: produktieknooppunten en afnamepunten ( huishouden / mkb ). Huishoudens, zonneparken en windmolens zijn produktiepunten.
Afnamepunten hebben bepaalde momenten een hoeveelheid stroomvraag. Produktieknooppunten hebben op bepaalde momenten een stroomoverschot. Het smart grid moet zo werken dat er zo geen tekorten zijn, en de kosten om het grid aan te leggen minimaal
1) Leg kabels tussen produktiepunten p1 ... pn en consumptiepunten c1...cn. Hoe korter de kabels hoe beter, alle consumptiepunten moet verbonden zijn aan (tenminste?) een productiepunt.
2) Kabels die een stuk delen zijn goedkoper (vertakkingen mogelijk maken)
3) Van tien momenten op de dag zijn de produktie en de consumptie van alle punten bekend. De kabels hebben een zekere capaciteit (? help me). Vind nu een goeie kabelwiring (dit doe ik om die continuiteit te omzeilen).
4) .... nog iets ... ?
pathfinding in adventure games (pittig!)
Gegeven kaarten 20x20, 30x30 (je kunt 3 watertjes wegtoveren), 40x40 (je kunt 5 tiles modifyen, er zijn teleports op de map.
1) Maak een algoritme dat een pad vindt tussen een ingegeven x en y op kaart 1
2) Maak een algoritme dat een pad vindt tussen een ingegeven x en y op kaart 2
3) Maak een algoritme dat een pad vindt tussen een ingegeven x en y op kaart 3
4) Iets met kosten? Ruiters gaan snel, maar niet in de bergen of zo?
RadioIostopen
Nog heel prematuur.