Het gebruik van memetische algoritmen bij operationele beslissingen. Een toepassing op het vestigingsprobleem

Abstract

Veel bedrijven worden al eens geconfronteerd met het bepalen van nieuwe vestigingsplaatsen. Het is een belangrijke lange-termijn beslissing aangezien met het bouwen of openen van vestigingen hoge kosten gepaard gaan. Daarom is het belangrijk om te proberen deze hoge kosten te minimaliseren. Nadat aan de hand van kwalitatieve determinanten een reeks potentiële vestigingen geselecteerd zijn, dienen de vestigingen geopend te worden die over voldoende capaciteit beschikken om aan de totale vraag van de klanten te voldoen én die de totale kosten proberen te minimaliseren. In deze eindverhandeling wordt gekozen voor het capacitated fixed charge location model. Dit model sluit aan bij de vereisten. Naast een aantal bestaande oplossingsmethoden voor dit model worden de memetische algoritmen ingeleid. Het memetisch algoritme dat in het onderzoek gebruikt wordt, wordt weergegeven en duidelijk toegelicht. De drie parameters in het algoritme, namelijk de populatiegrootte, het aantal generaties en de kans op local search kunnen in het onderzoek elk twee waarden aannemen. Zo bekomt men acht verschillende parametercombinaties voor het memetisch algoritme. Om verschillende invalshoeken te hebben, zijn datasets opgesteld voor een kleine, middelgrote en grote onderneming. Voor elk van die drie ondernemingen liggen de klanten telkens ofwel verspreid, ofwel geclusterd. Ook wordt gespeeld met de capaciteiten van de potentiële vestigingen. Bij de eerste reeks hebben de potentiële vestigingen elke keer een variërende capaciteit. Bij een tweede reeks beschikken de potentiële vestigingen iedere keer over identieke capaciteiten. Hoofd- en interactie-effecten worden berekend. Hiervan wordt een betrouwbaarheidsinterval opgesteld om te zien of het hoofd- of interactie-effect effectief significant is. Alle kleine en grote datasets geven iedere keer dezelfde optimale oplossing weer. De hoofden interactie-effecten bedragen hier nul. Een wijziging in de parameterwaarden heeft alzo geen invloed op de totale kost. Dit geldt ook voor de middelgrote ondernemingen waar de klanten geclusterd liggen. Indien de klanten van de middelgrote onderneming willekeurig verspreid liggen, geven de acht parametercombinaties verschillende uitkomsten aan. Slechts weinig effecten zijn significant verschillend van nul wanneer we een betrouwbaarheidsinterval van 95% of 99% selecteren. Zowel bij de dataset waar de potentiële vestigingen variërende capaciteiten hebben als waar de potentiële vestigingen over identieke capaciteiten beschikken heeft het hoofdeffect van de kans op local search een significante invloed op het 95%-niveau. Wanneer de kans stijgt tot 80%, leidt dit tot een vermindering in de totale kosten van beide datasets. Bij de dataset waar de potentiële vestigingen variërende capaciteiten hebben is het hoofdeffect horende bij een stijging van de populatiegrootte ook significant verschillend van nul. Door een stijging van 20 naar 40 individuen, daalt gemiddeld de totale kost. De overige effecten zijn allemaal niet significant verschillend van nul. Verschillende verklaringen kunnen gegeven worden voor de behaalde resultaten. De verhouding van de totale vraag tot de totale beschikbare capaciteit van een dataset kan van invloed zijn. Een lage verhouding geeft het algoritme meer toelaatbare oplossingen wat leidt tot meer rekenwerk. Een tweede verklaring voor de resultaten wordt gezocht bij de ligging van de klanten. Wanneer de klanten in clusters liggen, worden de vestigingen geopend die het dichtst bij de clustercentra gelegen zijn. Indien een verder gelegen vestiging zou geopend worden, lopen de transportkosten ineens hoog op. Bij de willekeurig verspreide klanten kan de transportkost geminimaliseerd worden door meer vestigingen te openen.