Carrierselectie in De Telecommarkt

Inhoudsopgave

1. INLEIDING EN PROBLEEMOMSCHRIJVING 2

2. VARIANTEN VAN HET PROBLEEM 5

3. MATHEMATISCHE FORMULERING VAN HET PROBLEEM 7

4. OPLOSSINGSMETHODE EN ALGORITME 10

4.1 Historisch overzicht 10

4.2 Onze oplossingsmethode 11

4.2.1 Optimaal of niet? 11

4.2.2 De "cheapest price" methode 13

4.2.3 De "midprice" methode 13

4.2.4 De "most hit" methode 14

4.2.5 Het "Carrier Evaluation with Total Affordable Demand-Algorithm" 14

5. COMPUTERSOFTWARE 17

5.1 Commerciлle software 17

5.1.1 AIMMS 3.5 17

5.1.2 PDSS 18

5.1.3 LINDO 19

5.1.4 CS2 19

5.2 Zelf ontworpen applicatie 19

6. OPLOSSING EN BESPREKING 21

BIJLAGEN 27

Bijlage 1: Carrier Selection Algoritme 27

Bijlage 2: Voorgestelde oplossing 29

Bijlage 3: Voorgestelde oplossing (schematisch) 32

Bijlage 4: Werkwijze Recursieve Backtracking 33

BIBLIOGRAFIE 34

1. Inleiding en probleemomschrijving

Omwille van de liberalisering en de daarmee gepaard gaande hevige concurrentie op de telecommunicatiemarkt gedurende de laatste jaren trachten vele operatoren hun kosten terug te dringen. Eйn van de punten waarop dit kan gebeuren is het verminderen van de connectiekosten voor internationale gesprekken.

Proxistar heeft als mobiele operator een draadloos netwerk ter beschikking, dat verbonden is met een aantal vaste telefoonnetwerken, zowel om nationale als internationale gesprekken tot bij de bestemmeling te leiden. Deze vaste netwerken zijn in het bezit van zogenaamde carriers, die aan Proxistar gespreksminuten verkopen voor elk van de door Proxistar gewenste bestemmingen. Proxistar kan op basis van vorige periodes een zeer exacte voorspelling maken wat betreft het aantal benodigde minuten voor elke bestemming. Proxistar heeft voor de 100 gewenste bestemmingen de keuze tussen 80 carriers, die gespreksminuten aanbieden tegen een bepaalde prijs. Bovendien zullen de carriers volumekortingen doorrekenen: dit betekent dat hoe meer minuten Proxistar koopt van een bepaalde carrier, des te lager de kost per gespreksminuut zal zijn. Deze volumekorting wordt bepaald door het interval, waarin het door Proxistar gewenste aantal minuten zich bevindt. Deze lagere prijs zal dan aangerekend worden voor alle minuten die Proxistar bij deze bepaalde carrier aankoopt. Daarom zal Proxistar indien gewenst meer minuten dan noodzakelijk aankopen, om zo in een hoger interval terecht te komen en dus een lagere prijs voor alle gespreksminuten te bekomen (dit wordt in de literatuur vermeld als de "meer-voor-minder"-paradox). Toch wenst Proxistar ook niet te afhankelijk te worden van ййn bepaalde carrier. Daarom is er beslist dat ййn bepaalde carrier niet meer dan 20% van de totale vraag aan gespreksminuten mag verzorgen. Aan de andere kant wenst Proxistar ook niet met meer dan 10 carriers samen te werken, om administratieve moeilijkheden te vermijden en om op langere termijn betere relaties met een beperkter aantal carriers op te bouwen.

Het probleem dat hierboven beschreven wordt is een variant van een min-cost flow probleem, algemeen beschouwd als de meest elementaire variant van netwerkproblemen. In een min-cost flow probleem moeten we de goedkoopst mogelijke manier zoeken om via een bepaald netwerk het aanbod van de aanbieders (knooppunten) naar de vragers (knooppunten) te leiden. In onze case moeten we dus zorgen dat voor elke bestemming aan de vraag van de klanten voldaan wordt, rekening houdend met de beperkingen van de carriers (gegeven door de intervals van elke carrier) en dit tegen een zo laag mogelijke totale prijs.

Algemeen is het min-cost flow probleem een optimalisatiemodel, dat als volgt geformuleerd kan worden:

Minimaliseer

onder de beperkingen voor alle i Є N.

voor alle (i,j) Є A

waarbij

In matrixvorm kunnen we het min-cost flow probleem als volgt formuleren:

Minimaliseer

onder de beperkingen

In deze formulering is N een nxm-matrix, de knoop-pijl incidentiematrix genaamd. Elke kolom Nij in de matrix correspondeert met een variabele xij . De kolom Nij heeft een +1 in de ide rij en een -1 in de jde rij; de rest van de matrix is gelijk aan 0.

Op het eerste gezicht zouden we al snel durven concluderen dat onze case een toewijzingsprobleem is (als variant van de min-cost flow problemen). Een toewijzingsprobleem vinden we bijvoorbeeld bij het toewijzen van mensen aan verschillende projecten of van taken aan verschillende machines. Indien onze case inderdaad een toewijzingsprobleem zou zijn, zou binnen de strikte definitie ervan moeten voldaan zijn aan drie voorwaarden: (1) het aantal carriers moet gelijk zijn aan het aantal bestemmingen (de twee datasets N1 en N2 dienen namelijk een gelijk aantal elementen te bevatten), (2) elke carrier (uit subset N1) verzorgt juist ййn bestemming (uit subset N2) en (3) elke bestemming (uit subset N2) wordt door juist ййn carrier (uit subset N1) verzorgd. Aan deze voorwaarden moet in onze case niet voldaan worden, dus spreken we beter van een transportprobleem, waarbij het aantal carriers (dit is de subset N1, waarin elke knoop een aanbodknoop is) niet gelijk hoeft te zijn aan