Menu

Praktiske anvendelser af kombinatorisk optimering og effektive algoritmer

Gruppen, som overlapper med algoritmikgruppen, arbejder med praktiske anvendelser af kombinatorisk optimering og effektive algoritmer. Det primære formål er at finde effektive måder til at opnå gode løsninger til meget komplekse praktiske diskrete optimeringsproblemer, som enten er direkte affødt af et konkret virksomhedsproblem, eller er nært beslægtet med real-life problemer. Eksempler er skedulering af produktionsanlæg, mandskabsplanlægning, ruteplanlægning, skemalægningsproblemer.

Gruppen arbejder med både eksakte algoritmer og (meta)-heuristikker. Alle de ovennævnte problemer er NP-hårde, selv i stærkt simplificeret form. Desuden gælder det, for mange praktiske anvendelser, at problemet skal løses meget hurtigt. Så det er et vigtigt fokus at finde hurtige algoritmer som løser problemerne til optimalitet. Hvor dette vises sig umuligt i praksis angriber vi problemet heuristisk for at finde nær-optimale løsninger.

Der forskes blandt andet i algoritmer til varianter af vechicle routing problemet, (job-shop) scheduling problemer og varianter af skemalægningsproblemer. Der arbejdes både med enkelt og flerobjektiv problemstillinger. Der anvendes blandt andet statistiske værktøjer til vurderingen af hvilke algoritmekonfigurationer der er bedst til at løse det givne praktiske problem.

På det mere teoretiske plan arbejder gruppen med diverse grafteoretiske problemer der har stor relevans for praktiske anvendelser. Eksempler er udvidelse af sammenhængen i netværk, problemer vedrørende disjunkte udspændende træer og problemet med at finde et træ hvis fjernelse ødelægger sammenhængen mest muligt.

Gruppen har samarbejdet med en række danske firmaer og offentlige institutioner, herunder B&O, DSB S-tog, FKI Logistex, Odense kommune, OUH, Rambøll Informatik, Cabinplant, Simcon A/S, Air Support og OE3i.

Videnskabelige medarbejdere
Jørgen Bang-Jensen
Daniel Merkle
Marco Chiarandini

Vi samler statistik ved hjælp af cookies for at forbedre brugeroplevelsen.  Læs mere om cookies

Acceptér cookies