How can we handle periodic discounts from suppliers and vendors in ASR and AWR?

We have several options:

• We can do it manually through forward buy analysis from the client.
• We can interface this information from our ERP. This option requires that it is registered in the ERP and that is not always true.
• If we are using brackets we can have an ekstra set of brackets that contain the discount. Then we are able to do mass maintenance on Current Bracket in Source Properties -> Source Control Factors -> Bracket Controls when the discount period begins and when it ends,

Any other ideas?

In E3 there is no simple solution to an optimal buying pattern, if you only achieve discounts if you buy in eaches of for exampel 10.

There is a way solving this problem.

Here is an example:

You can set the quantity discount on the SKU or Item at 10 pieces. When the SOQ is below 10 it will buy 10 SKUs if affordable. When the SOQ is above 10 the problem occurs. The system will not round to the nearest ten pieces.

Normally when buying in large quantites it is almost always affordable to round up to the nearest 10. In that case you could have the described quantity discount and then set the convenience pack to 10. The tricky part is setting the convenience pack break point. You can set this to 99 % and E3 will surely not round SOQ values below ten, but when the SOQ is above ten it will always round to the convenience pack. This means that if in theory SOQ should be 11 it will be rounded to 20 because of the convenience pack setting. Remark, it will never round down.

Settings

Convenience pack = 10
Convenience pack break point = 99 %

Navigation
 
Change tabs: Ctrl + Tab or Ctrl + Shift + Tab
 
Change sub tabs: Ctrl + page down or Ctrl + page up
 
Database Selector: F2
 
Filter: Ctrl + F
 
OK - when confirming action: alt + O
 
Menus

Utility Master Menu: Ctrl + U
 
Show/Hide Columns in lists
Arrow up and down
Select or unselect column: Space (needs to be initialized by a mouse click or "left arrow")

Hi Young test user.

Actually JDA has a product for this. This is called JDA Demand.

There is a PDF doc on the topic and the JDA website.

If you want to solve your problem with E3 only, you must do some programming work in your ERP. You could interface uplift values from former promotion periods.

Heuristikken er baseret på simulated annealing, hvilket stammer fra metalindustrien, hvor metal opvarmes til en bestemt temperatur og nedkøles ifølge et bestemt køleskema. Ved nedkøling ændres strukturen i metallet, og afhængig af kølingsraten kan forskellige egenskaber opnås (se Winston et al., 2003, s. 805). I Modellen antages at der er en initial valid løsning til rådighed. Rutenetværket opvarmes derefter til en initial temperatur, hvorefter kunder udskiftes ved hjælp af systematisk tilfældighed i forskellige etablerede ruter. Den systematiske tilfældighed styres ved hjælp af den pågældende temperatur, som pejler løsningsprocessen i en bestemt kontrolleret retning. I hver gentagelse findes en ny løsning som accepteres med sandsynligheden

 , hvor ΔC er ændringen i omkostningerne for løsningen fra sidste gentagelse, og t er den nuværende temperatur. Ved accept af løsninger som ikke er bedre end den foregående løsning, forsøger heuristikken at undgå lokale optimumspunkter. Heuristikken gentages indtil løsningsprocessen fryses fast ved sluttemperaturen, idet temperaturen falder gradvist efter et bestemt antal gentagelser.

DARP er et kompliceret problem, fordi der både skal tages højde for tildeling af kunder til hver rute, og bestemmelse af i hvilken rækkefølge kunderne skal besøges. For at mindske kompleksiteten i denne proces, er der udviklet forskellige velfungerende metoder, til løsning af problemstillingen. Den klassiske metode er opdeling af  løsningsprocessen i to faser. Den første fase er gruppering af kunderne i bundter, hvorefter anden fase sørger for kunderækkefølgen i ruten (se Bergvinsdottir, 2004, s. 39, Chan, 2004, s. 16, Baugh et al. s. 102). Hver kunde kan kun være en del af et bundt, og der kan ikke være mere end en vogn om hvert kundebundt. Simulated annealing kan derefter anvendes til den første fase i løsningsprocessen, da det afgørende for løsningskvaliteten er en fordeling af kunderne i så gode bundter som muligt (se Baugh, et al., 1998, s. 103). Fase to, hvor rutelægningen udføres, kan heuristikken "The modified space-time heuristic algorithm" anvendes (se Bergvinsdottir et al., 2004, s. 10). Denne heuristik er forholdsvis hurtig og kan generere meget gode løsninger, fordi kundebundternes størrelse sandsynligvis er begrænsede i størrelsesordenen 10-20 kunder (se Baugh et al., 1998, s. 103). En variation af denne fremgangsmåde er dannelse af kundebundter, som allerede bestemmer ruterækkefølgen, hvorefter et forskydningsprincip kan anvendes til minimering af ventetid i ruten (se Cordeau et al., 2003, s. 587 og Mauri et al. 2006 s. 6). Ifølge Bergvinsdottir (2004, s. 100), er "The modified space-time heuristic algorithm" for langsom i forhold til metoden anvendt af Cordeau et al. (2003), da relativt færre gentagelser kan udføres på tilsvarende hardware på samme tid. Forskellen er så stor, at skylden sandsynligvis ikke kan lægges på hverken programmeringssprog eller rutiner.

Kvaliteten af løsningerne afhænger i høj grad af antallet af gentagelser en metaheuristik foretager under en modelkørsel, hvorfor forskydningsprincippet vælges til løsning af problemstillingen i fase to.

Kilder

Tidsvinduer

Der er to forskellige måder en kunde kan bestille befordring, enten udgående eller indgående bestilling. Udgående bestilling er hvor kunden skal være på et bestemt sted på et bestemt tidspunkt, eksempelvis være hos lægen klokken 14:00. Tidsparameteren der skal angives af kunden er ønsket afleveringstidspunkt. En indgående bestilling betyder hjemrejsetransport, hvor en kunde skal transporteres hjem efter eksempelvis endt konsultation hos lægen klokken 14:30. Kunden angiver en tidsparameter for afhentningstidspunktet i modsætning til afleveringstidspunktet. Tidsvinduerne udarbejdes derefter ud fra enten ønsket afhentnings- eller afleveringstidspunkt. Det anvendte datasæt indeholder lovet starttid, som er tidspunktet, som kunden er blevet lovet afhentning på. Endvidere er sluttiden angivet, som i slutningen af dagen er tilgængeligt i systemet, og består af den samlede anvendte tid til transport af kunden fra afhentnings- til afleveringspunktet. Den statiske model er deterministisk, hvorfor der ikke tages højde for andre ukendte forhold, som snevejr og uheld, der kan forårsage længere transporttid. Tidsvinduerne beregnes derfor kun ud fra forskellige begrænsninger, der skal sørge for et acceptabelt serviceniveau. Den maksimale køretid for en kunde er defineret af parameteren MRT = (1,5 · "den direkte køretid"), der vil være en af de bestemmende faktorer for, hvor brede tidsvinduer må være. Et eksempel med to kunder i en rute vil blive anvendt til illustration af tidsvindueopbygningen. Kunde 0 afhentes i punkt 0 og afleveres i punkt 2, mens kunde 1 afhentes i punkt 1 og afleveres i punkt 3.



Figur 11.2 viser de to kunders afhentnings- og afleveringspunkter, afstanden mellem hvert punkt over hver vandrette pil og tidsvinduerne for hvert punkt under rutepunkterne. Tidsvinduerne angiver tidsintervallet for, hvornår servicering af kunden må påbegyndes i et bestemt punkt.

Kunde 0 skal til tandlæge på tidspunkt 1301 men må afleveres 30 minutter før det ønskede afleveringstidspunkt. Tidsvinduet i punkt 2 vil derfor kræve aflevering mellem tidspunkt 100 og 130. Afstanden mellem punkterne 0 og 2 er 20 minutter, som er basis for beregning af tidsvinduet i afhentningspunktet. Tidsvinduet i punkt 0 starter på tidspunkt 80, hvilket er 20 minutter før starten af tidsvinduet i punkt 2. Tidsvinduet for afhentning må i dette eksempel have en bredde på 20 minutter (-5 til +15 minutter), hvorved tidsvinduet i punkt 0 er mellem tidspunkt 80 og 100. I det tilfælde vil kunde 0 få tidspunkt 85 at vide som lovet afhentningstidspunkt. En mere hensigtsmæssig beregning af tidsvinduer fra det økonomiske synspunkt, vil være på basis af MRT. Ulempen ved MRT-metoden er upræcis information til kunden, som får et tidsvindue i afhentningspunktet, hvis bredde afhænger af den direkte transporttid (se Cordeau et al. 2003, s. 580). Tidsvinduet i punkt 0 ved anvendelse af MRT er mellem tidspunkt 70 og 100 (100 – (20 · 1,5) og 130 – (20 · 1,5)). Dette resulterer i et tidsvindue med en bredde på 30 minutter, og det lovede afhentningstidspunkt er 85 (70 + 30/2) med en margen på (± 15 minutter). Afhængig af fremgangsmåde, vil tidsvinduerne have forskellig bredde, som skal specificeres i forhold til det ønskede serviceniveau kontra økonomisk gevinst.

Kunde 1 får fri fra et møde på tidspunkt 200, hvorefter tidsvinduet får en bredde på +15 minutter, da kunden ikke kan afhentes før mødet er færdigt. Tidsvinduet i punkt 1 er derfor mellem tidspunkt 200 og 215. Kunden vil gerne hjem, som er i punkt 3, og afstanden er 15 minutter. Tidsvinduet i punkt 3 er derfor mellem tidspunkt 215 og 238 (200 + 15 og 215 + (1,5 · 15)).  Sluttiden på tidsvinduet i punkt 3 er defineret ud fra MRT, fordi der ikke findes andre begrænsninger for afleveringspunktet ved indgående ordrer. Selvom tidsvinduerne er forholdsvist brede, vil kunderne aldrig være i en vogn længere tid end MRT, som er en begrænsning der altid gælder.
Tidsvinduerne bliver genereret på baggrund af sluttid (skal være hos lægen på tidspunkt x) og lovet starttid (fri fra skole på tidspunkt y) på baggrund af forgående eksempler.

Kilder

Darp litteraturen

DARP er blevet behandlet i litteraturen siden 1970'erne, hvor de første heuristikker blev udviklet til løsning af DARP, og interessen steg yderligere i starten 1980'erne (se Psaraftis,  1983, s. 133). Årsagen til den stigende interesse var sandsynligvis udviklingen og tilgængeligheden af IT, der kunne anvendes til løsning af DARP.  I begyndelsen fik det statiske DARP mest opmærksomhed på grund af de lempede krav til løsningstiden i forhold til det dynamiske DARP. Litteraturen præsenterer robuste løsningsmodeller til både den statiske og dynamiske del. Der er ikke klar enighed om, hvilken metode der er bedst i forskellige praktiske tilfælde. En af grundene til uenigheden er sandsynligvis, at vægtningen af optimeringsfunktionen er unik og situationsbestemt i forskellige praktiske tilfælde.

Dynamisk DARP
Brandvæsenet i København fik hjælp af Madsen et al. (1995, s. 193) til løsning af deres   DARP, som indeholdte 50.000 kundeordrer om året. Kundeordrerne bestod mest af transport af ældre og handicappede. Den anvendte heuristik er en indsættelsesalgoritme kaldet REBUS, som er baseret på en multikriterie objektfunktion, der tager højde for kundeservice og transportomkostninger. Indsættelsesalgoritmen er af typisk karakter for grådige heuristikker, hvor alle ordrer som ikke er rutelagt bliver indsat i det eksisterende rutenetværk en af gangen. Alle mulige indsættelseskombinationer for ordren i alle ruter bliver undersøgt, og ændringen i objektfunktionen beregnes hver gang. Ordren indsættes i den ruteposition, som er billigst i forhold til objektfunktionen. En ordre kan ikke altid serviceres af de eksisterende vogne, hvorfor den lægges i listen med ordrer, der ikke kan opfyldes. Alle ikke opfyldte ordrer kan derefter blive serviceret af tredjepart eller afvises helt. Hele proceduren er en sekventiel proces, som stopper, når aller kundeordrerne er tildelt en vogn eller er i listen over ordrer, der ikke kan opfyldes. Fordelen ved REBUS i forhold til en traditionel indsættelsesheuristik er, at kundeordrer som endnu ikke er rutelagt, sorteres i forhold til, hvor svære de er at indsætte. Endvidere præsenterer REBUS nye muligheder indenfor objektfunktionsopbygningen, og optimeringen tager højde for flere vognkapacitetsbegrænsninger. Ovenstående egenskaber viser indsættelsesheuristikkens fordele i forhold til en simpel indsættelsesmetode.

Jørgensen (2002) implementerer systemet Inforoute, der kan løse DARP hos Jensen Turisttrafik, som er en busoperatør. Systemet anvender en indsættelsesheuristik, der minder om den anvendte i REBUS. Det specielle ved implementeringen af Inforoute er metoden til lægning af den initiale løsning. Den initiale løsning kan lægges før dagens start, fordi nogle af kundeordrerne er kendt dagen før. Den anvendte algoritme til den initiale løsning er baseret på klyngedannelse (se Jørgensen, 2002, s. 154). Ved hver kundeindsættelse, undersøges om der er en eksisterende klynge, som kunden kan være en del af. En ny klynge dannes, hvis kunden ikke kan placeres i en eksisterende klynge. Klyngedannelsen er kun baseret på den første kunde i klyngen, hvorfor klyngestørrelserne begrænses. Tanken bag metoden til klyngedannelse er, at en god initial løsning kan være fordelagtig, så den grådige indsættelsesheuristik har et godt udgangspunkt. Klyngedannelsen er mere tidskrævende end den grådige indsættelsesheuristik, men tidsfaktoren er ikke et problem, fordi den initiale løsning kan lægges om aftenen dagen før.

I landområdet omkring Los Angeles har Diana et al. (2004) undersøgt en ny indsættelsesheuristik til løsning af DARP. Indsættelsesrækkefølgen af kundeordrer er sorteret efter et nyt princip, der forsøger at indsætte kundeordrer, som ved senere indsættelse sandsynligvis vil kræve højere omkostninger. Sorteringsprincippet er baseret på den geografiske tæthed af kundernes afhentnings- og afleveringspunkter. En kunde i et område med lav efterspørgsel er derfor sværere at indsætte. Derefter anvendes en parallel indsættelsesalgoritme baseret på fortrydelse. Omkostningerne for alle kunders indsættelsesmuligheder beregnes, hvorefter den kunde indsættes, som er dyrest ikke at indsætte. Systemet vælger derfor en kunde der minimerer sandsynligheden for høje omkostninger, så systemets handlinger ikke fortrydes senere i forløbet. Indsættelsen er baseret på omkostningsberegninger, der på tidspunktet er tilgængelige. Informationerne ændrer sig fra gentagelse til gentagelse, hvorfor en indsættelse på et bestemt tidspunkt ikke sikrer global optimalitet.

En heuristik der tager højde for to tidshorisonter, den korte – og lange tidshorisont er blevet udviklet af Mitrovic-Minic et al. (2004). Disse tidshorisonter er implementeret i objektfunktionen, hvorved indsættelsesheuristikken kan tage højde for kunder, der skal transporteres på forskellige tidspunkter af dagen. Under kundeindsættelsen i starten af dagen kan der tages højde for efterspørgslen senere på dagen. Denne strategi kan muliggøre generering af bedre løsninger. Opnåede besparrelser ved hjælp af denne fremgangsmåde er faldende, når problemstørrelsen stiger. Den største undersøgte problemstørrelse er på 1000 kunder.

Statisk DARP
En accepteret metodegruppe til løsning af det moderne statiske DARP med realistiske begrænsninger er metaheuristikker. Disse heuristikker er tidskrævende  og løsningernes kvalitet er stærkt afhængig af heuristikkens kørselstid (se Mitrovic-Minic et al., 2004, s. 672). Fordelen ved disse heuristikker er, at de ikke er afhængige af hverken sekventiel eller parallel indsættelsesrækkefølge, hvorfor sandsynligheden for optimale eller nær optimale løsninger stiger.

Baugh et al. (1998) anvender en fremgangsmåde der starter med klyngedannelse og rutelægger til sidst. Klyngedannelsen er baseret på en simulated annealing heuristik, hvor simple tilfældige ændringer i løsningen foretages. Et køleskema anvendes, som sørger for kontrolleret søgning i løsningsmængden og afslutning af heuristikken i løbet af rimelig tid. Ændring af løsningen foretages på baggrund af to forskellige ændringsoperationer. Den første ændringsoperation bytter to kunder fra to forskellige ruter ud med hinanden. Den anden ændringsoperation flytter en tilfældig kunde fra sin rute til en anden tilfældig rute, som kan være en helt ny rute. Problemet relakseres ved søgning i løsningsmængder der er værre end den hidtil bedste løsning. Dette opnås ved accept af omkostningsforværrende ændringsoperationer med en hvis sandsynlighed. Risiko for søgning i løsningsmængden der går i ring og derved fanges i et lokalt minimum mindskes ved anvendelse af en simpel tabuliste. Ændringer i løsningen forbydes, hvis de anvender kunder fra tabulisten.

Figur 10.1 viser hvordan en metaheuristik forsøger at søge væk fra et lokalt minimum. Heuristikken starter i løsning Lstart, som er fanget i et lokalt minimum. En søgning i løsningsmængden med højere omkostninger medfører en ny løsning Lslut. Denne løsning er bedre end Lstart, men er også fanget i et lokalt minimum. Det globale optimum Lbedste findes ikke, hvilket ikke er atypisk, da heuristikker ikke kan garantere globalt optimale resultater.




En metaheuristik baseret på tabusøgning er udviklet af Cordeau et al. (2003), og har vist sig at være en stabil og intelligent løsningsmetode. Grundlæggende minder metoden om simulated annealing udviklet af Baugh et al. (1998). Fremgangsmåden er anderledes, da en tabuliste anvendes i stedet for et køleskema som det primære konvergeringsværktøj. Metoden udvides med en tredje ændringsoperation til ændring af løsningen, der bytter to kunder i samme rute ud med hinanden. Tabusøgningsmetoden anvender den bedste indsættelse af en kunde, når en kunde flyttes fra en rute til en anden i stedet for tilfældige ryk som i simulated annealing. Beregning af kundens bedste indsættelsesposition er en tidskrævende procedure, men kan resultere i bedre resultater, selvom indsættelsesmetoden er grådig. Anvendelsen af tabusøgning til løsning af DARP har vist sig at være fordelagtig, fordi gode løsninger kan findes selv efter få gentagelser (se Chan, 2004, s. 63). Grunden til de gode resultater er sandsynligvis minimeringen af tilfældighed og anvendelse af tabulistens hukommelse.

Bergvinsdottir (2004) og Bergvinsdottir et al. (2004) arbejder på en relativ ny metode til løsning af DARP baseret på genetiske algoritmer. I stedet for klyngedannelsen ved hjælp af simple tilfældige ændringsoperationer, baseres løsningsændringer på parringer mellem løsningssæt. Det bedste afkom fra disse parringer erstatter løsninger med høje omkostninger. En anden metode til ændring af løsningerne er ved hjælp af krydsning af to tilfældige ruter fra to forskellige løsninger. Dette danner en skabelon til en ny rute, som ifølge et regelsæt, tager de nødvendige informationer fra de to ruter og laver en ny rute. I tilfælde af at den nye løsning ikke er valid, allokeres eller frasorteres kunder fra tilfældige ruter. Mutation kan også anvendes til ændring af løsningen, hvor en tilfældig kunde flyttes fra sin rute til en anden tilfældig rute. De endelige løsninger, som genetiske algoritmer kan generere, kan sammenlignes med heuristikken baseret på tabu søgning udviklet af Cordeau et al. (2003). Ulempen ved den genetiske algoritme er den forholdsvist store mængde beregninger med basis i tilfældighed, som gør anvendelsen langsom. Ekstraordinære lange løsningstider kan også opstå, når problemer med mange kunder skal løses (se Bergvinsdottir et al., 2004, s. 10).

En kombination af rutelægningsprincipperne fra Cordeau et al. (2003) og en diversifikationsstrategi baseret på simulated annealing (se Baugh et al., 1998) er udviklet af Mauri et al. (2006). Den nye heuristikopbygning er forholdsvis hurtig på baggrund af den simple struktur, der blandt andet ikke indeholder en tabuliste og minimerer beregningsmængden. Ifølge Mauri et al. (2006, s. 10-11) er deres simulated annealing heuristik bedre end den genetiske algoritme præsenteret af Bergvinsdottir et al. (2004) på alle målte kriterier: samlet rutetid, ventetid, køretid og CPU tid til generering af løsningen. Cordeau et al. (2003) heuristikken er signifikant bedre med hensyn til den totale køreafstand. Den nye simulated annealing heuristik præsenterer bedre resultater med hensyn til ventetid, kundekøretid og høj reduktion i CPU tid i forhold til Cordeau et al. (2003). Det største problem der anvendes til sammenligning af heuristikkernes kvalitet er en problemstørrelse på (n = 144, m = 10) (kunder, vogne), hvilket resulterer i et fald i CPU tiden fra 92,4 til 2,8 minutter til fordel for teknikken i Mauri et al. (2006) i forhold til Cordea et al. (2003).

Valg af heuristik
Valgmulighederne består af tre forskellige metaheuristikker: genetiske algoritmer, tabusøgning eller simulated annealing. En kombination af ovenstående heuristikker kan også anvendes. På baggrund af litteraturgennemgangen udvælges den bedste heuristik til problemstillingen ved hjælp af udelukkelsesmetoden.

Heuristikker baseret på genetiske algoritmer, er stadig under udviklingsfasen, hvorfor  uventede problemer kan forekomme. Estimering af gode parameterværdier kan endvidere være svære på baggrund af de mange indstillingsmuligheder i den genetiske algoritme (se Bergvinsdottir, 2004, s. 76). Det er derfor sandsynligvis nødvendigt med præliminære undersøgelser for de enkelte parameterværdier hver gang et nyt problem skal løses.

Tabusøgning og den nye simulated annealing metode er de to heuristikker, der vælges imellem. Det endelige valg af heuristik, skal baseres på parametre, der er vigtige i en given problemstilling. Tidsfaktoren er vigtig, fordi problemets statiske størrelse (n = 1000+, m = 500+) ikke er behandlet i litteraturen, hvorfor en bestemt teknik ikke er åbenlys. Tabusøgning kan være et risikabelt valg, på baggrund af en løsningstid på 92,41 minutter for en problemstørrelse på (n, m) = (144, 10) (se Cordeau et al., 2003, s. 589). For at maksimere sandsynligheden for et systemet, der kan generere gode brugbare løsninger, vælges den hurtigste heuristik baseret på simulated annealing. En acceptabel løsningstid kan medføre implementering af en tabuliste til forbedring af resultaterne som i Baugh et al. (1998).

Anvendelse af simulated annealing til løsning af DARP er blevet kritiseret, fordi den velkendte løsningsstruktur gør udvikling af intelligente søgningsheuristikker fordelagtig (se Jørgensen, 2002, s. 52). Tabusøgningsheuristikken udviklet af Cordeau et al. (2003) anvender grådige heuristikker til ruteprogrammeringen, hvilket medfører en stigning i tidsforbruget, når disse beregningstunge teknikker implementeres. Det høje tidsforbrug er ufordelagtigt i forhold til den positive korrelation mellem metaheuristikkernes løsningskvalitet og afviklingstiden. Metaheuristikker med simple og beregningslette operationer, der tillader mange ændringer i løsningen i løbet af kort tid, kan derfor være fordelagtige. Simulated annealing viser hvordan mange simple ændringer i løsningen kan genere gode resultater på kort tid (se Mauri et al., 2006, s. 10).

Udover tidsfaktoren er fordelen ved simulated annealing, at heuristikken ifølge Mauri et al. (2006, s. 11) reducerer vognenes ventetid. Reduktion af ventetid med kunder er fordelagtig, hvis en øget kundeservice ønskes. Resultaterne præsenteret i Mauri et al. (2006, s. 10-11) skal tolkes varsomt, fordi der ikke tages højde for forskellen i objektfunktionerne anvendt i artiklerne. Resultattabellerne for de forskellige heuristikmetoder, har derfor en begrænset sammenlignelighed. En ændring af vægtningen af forskellige parametre i objektfunktionen kan resultere i, at nogle omkostninger minimeres mere end andre. En højere vægtningskoefficient ud for ventetiden, kan derfor resultere i bedre ventetidsresultater, mens resultatet af de andre parametre kan på forhånd være uklar. Disse observationer forklarer endvidere, hvorfor kun nogle parametre er forbedret i Mauri et al. (2006) kontra Cordeau et al. (2003).

Det endelige valg af fremgangsmåde er anvendelse af samme princip som i Jørgensen (2002). En god initial løsning skal genereres aftenen i forvejen. Denne løsning bliver derefter grundlag for det nuværende dynamiske system Planet. I modsætning til Jørgensen (2002), vil en metaheuristik baseret på simulated annealing anvendes, der sandsynligvis kan generere bedre løsninger end relativt hurtige heuristikker til klyngedannelse. Ifølge Baugh et al. (1998, s. 102) kan simulated annealing generere tæt på globalt optimale løsninger i løbet af rimelig tid. En anden grund til denne fremgangsmåde er, at metaheuristikken vil være enkel at implementere, så den kører sideløbende med den dynamiske system. Implementeringen er enkel fordi heuristikken er baseret på simple ændringer, der kan foretages hurtigt fra løsning til løsning.

Den initiale model vil være en simpel udgave i forhold til avancerede modeller set i litteraturen. Grunden til denne fremgangsmåde er, at modellen forsøges løst til optimalitet, selvom problemet er formuleret som et MILP problem. Problemet indeholder også variabler, der begrænses til heltalsværdier. Heltalsbegrænsningen vil sandsynligvis øge sværhedsgraden og derved løsningstiden for problemet (se Winston et al., 2003, s. 475).

I litteraturen bruges generelt samme notation til modelformuleringen med få afvigelser til opbygning af objektfunktion. I denne opgave er den matematiske modelformulering hovedsageligt baseret på følgende kilder: Baugh et al. (1998, s. 93), Bergvinsdottir (2004, s. 21) og Jørgensen (2002, s. 69).

Valg af modelformat
Baugh et al. (1998, s. 99) gennemgår forskellige fremgangsmåder til opbygning af den matematiske MILP model. Den største forskel mellem modellerne er antallet af binære variabler i forhold til antallet af begrænsninger. Disse to parametre kan bruges til estimering af problemstillingens sværhedsgrad og herved løsningstiden. Ingen af ovenstående modelbeskrivelser er signifikant bedre end andre, hvorfor den generelle modelformulering fra de førnævnte kilder anvendes til den matematiske modelopstilling.

Modelbeskrivelse
Modellens notation og formulering er udarbejdet, så modellens dynamik sikres, hvorved ændringer i antal vogne og kunder kan foretages uden problemer. Funktionalitet af modellen bliver undersøgt på en enkelt kunde og en enkelt vogn. Derefter bliver modellen afprøvet med flere kunder og vogne for at undersøge, om løsningstiderne er acceptable på tilgængeligt hardware og software.
Modellen optimeres efter en objektfunktion, som definerer problemstillingens omkostninger, der skal minimeres. Det svære ved DARP er problemets objektfunktion, der består af modstridende mål. Optimeringen foregår generelt på baggrund af omkostninger baseret på kvaliteten af kundeservice, transportomkostningerne og antallet af vogne anvendt i løsningen. I testversionen af modellen skal objektfunktionen være så simpel som muligt, hvorfor en minimering af antallet af kanter anvendt i løsningen udføres.

Ruterne skal lægges korrekt, og forskellige tidsfaktorer skal overholdes, hvorfor en række begrænsninger opstilles. Disse begrænsninger sørger for, at alle vogne, som forlader deres depot, kommer hjem igen. Alle kunderne skal afhentes på deres afhentningspunkter og afleveres på deres afleveringspunkter indenfor bestemte tidsperioder. En kunde skal kun besøges af en vogn og skal afhentes, før aflevering kan finde sted. Modellen understøtter ikke, at en kunde bliver afhentet af en vogn og afleveret af en anden, hvilket også ville medføre en udvidelse af problemets kompleksitet på grund af flere mulige løsningspar. Begrænsninger, der sørger for, at tidsfaktoren bliver overholdt, er vigtige parametre for kundeservicen. Kunderne skal afhentes og afleveres indenfor specificerede tidsvinduer, hvis bredde kan have betydning for opnåelse af besparelser i transportomkostningerne. Sandsynligheden for besparelser er positivt afhængig af tidsvinduernes bredde. Ulempen ved brede tidsvinduer er, at det går ud over kundernes serviceniveau. Kundernes servicenedsættelse skyldes, at en kunde risikerer afhentning lang tid før eller efter det aftalte afhentningstidspunkt og aflevering på et tidligere tidspunkt end krævet. For at sikre kundens serviceniveau er acceptabelt, anvendes maksimal turlængde MRT (Maksimum Ride Time). Det er en faktor, som har indflydelse på, hvordan tidsvinduerne kan opbygges. En MRT, der svarer til halvanden gange den direkte transporttid, anvendes. En længere MRT giver mulighed for transport af flere kunder i samme rute med risiko for lang transporttid.

Modelnotation
Modellen afspejler en problemstilling med n antal kunder og v antal vogne. Disse kunder og vogne tildeles ID-numre ved hjælp af prædefinerede sæt. Depoterne er oplistede først, hvorefter kundernes afhentnings- og afleveringspunkter defineres. Startdepoterne defineres fra 1,...,v, slutdepoterne v+1,...,2v, afhentningspunkterne 2v+1,...,2v+n og endeligt afleveringspunkterne 2v+n+1,...,2v+2n. Følgende sæt bliver anvendt i modelopbygningen.

V = {1,...,v}   Vogne, som svarer til til startdepoterne.
Do = {1,...,v}   Startdepoter.
Dd = { v+1,...,2v}   Slutdepoter.
P = {2v+1,...,2v+n}   Afhentningspunkter.
D = {2v+n+1,...,2v+2n}   Afleveringspunkter.
N = P U D   Afhentnings- og afleveringspunkter.
A = N U Do U Dd   Alle knudepunkter.

Udover ovenstående sæt defineres parametre, som er konstante værdier, der anvendes af problemløseren som rå data. Parametrene indeholder information om servicetid, lastændring, kapacitet i vognene, start- og sluttid på tidsvinduer. Endvidere defineres M, som er en stor positiv værdi, der anvendes i forbindelse med linearisering af begrænsninger. Det kritiske punkt for M-værdien findes ved beregning af antallet af minutter i planlægningsperioden, som er et døgn (24 · 60 = 1440 minutter). Det antages, at et knudepunkt ikke forlades af en vogn senere end planlægningsperiodens sluttidspunkt.  En liste over anvendte parametre er vist herunder.

v   antal tilgængelige vogne.
n   antal kunder.
si   servicetid i punkt i.
li   lastændring ved knudepunkt i.
Ci   kapacitet i vogn i.
ai   tidsvindue starttid i knudepunkt i.
bi   tidsvindue sluttid i knudepunkt i.
M    M stor positiv værdi.

Beslutningsvariabler er de værdier, som kan ændres af problemløseren i løbet af optimeringsprocessen. De anvendes til bestemmelse af, hvorvidt en vogn skal køre på en bestemt strækning, hvornår vognen forlader et bestemt knudepunkt, og hvad lasten i vognen er, når knudepunktet forlades. De tre beslutningsvariabelsæt er vist herunder.



Ti,k =   tidspunkt når knudepunktet i forlades af vogn k, heltallig variabel, ≥ 0.
Li,k =   last når knudepunkt i forlades af vogn k, heltallig variabel, ≥ 0.
Notationen er defineret, og modellen kan opbygges med objektfunktion og begrænsninger.

Modelformulering
I et optimeringsproblem skal en objektfunktion opstilles, som problemløseren skal  minimere eller maksimere. I DARP udtrykkes objektfunktionen som en omkostningsfunktion, der skal minimeres. Til testmodellen opstilles den simple objektfunktion (9.1), der summerer alle strækninger, alle vogne kan køre. Ud fra den opstillede objektfunktion vil en vogn i den optimale løsning starte i sit depot, afhente og aflevere alle kunderne og returnere til sit depot. Vognens transportomkostninger i forhold til afstanden mellem knudepunkterne er ikke medtaget her.



Begrænsning (9.2) sørger for, at alle tilgængelige vogne kører ud til et afhentningspunkt. Der summeres over alle afhentningspunkter samt slutdepoter, hvorved vogne, som ikke anvendes, kan køre direkte fra start- til slutdepot. Denne begrænsning er nødvendig, så hver vogn ikke forlader depotet mere end én gang.
 


Den næste begrænsning (9.3) sørger for, at alle vogne, der har forladt deres depot, returnerer til deres slutdepot.
 


Begrænsning (9.4) er nødvendig, fordi den sikrer, at hver kunde kun bliver afhentet en gang, hvorefter vognen kører til et afleveringspunkt.
 


Begrænsningen (9.5) sørger for, at den vogn, som afhenter en bestemt kunde, også afleverer kunden i afleveringspunktet.
 


Besøges punkt j efter punkt i skal punkt i besøges tidsmæssigt før punkt j, som begrænsning (9.6) sørger for. Tiden, når vognen besøger punkt i plus servicetiden i punkt i, skal være mindre end eller lig tiden, når vognen er i punkt j. Begrænsningens ulighed er altid opfyldt, hvis en vogn ikke kører mellem knudepunkt i og j, da parameteren M i tilfældet sørger for en negativ venstreside.

 


I tilfælde hvor punkt i besøges af en vogn, skal vognen være i punktet indenfor tidsperioden defineret af punktets tidsvindue. Tidsvinduet angives med et start- og sluttidspunkt defineret af henholdsvis parametrene ai og bi. Begrænsning (9.7) sørger for overholdelse af tidsvinduerne for alle knudepunkter. Tidsvinduer for start- og slutdepoterne kan også defineres og anvendes til begrænsning af en vogns anvendelsesperiode i en given planlægningsperiode.
 


Afhentning af en kunde skal ske tidsmæssigt før kunden afleveres, hvorfor begrænsning ( 9.8 ) er anvendt.
 


Begrænsning (9.9) sørger for, at kapaciteten, der bruges af en kunde i et afhentningspunkt, er lig kapaciteten, der frigøres ved afleveringspunktet. Det antages her, at hvis en kørestolsbruger og kørestol afhentes, vil både kunden og kørestolen afleveres i afleveringspunktet. Begrænsning (9.9) er ikke lineær, men lineariseres efter samme princip som begrænsning (9.6), hvilket resulterer i de to lineære begrænsninger (9.10) og (9.11).
 


Vognkapaciteten skal overholdes, hvorfor lasten undersøges i alle punkter, en vogn besøger. Når punkt i forlades, skal lasten altid være større eller lig lastændringen i punktet og være mindre end eller lig vognkapaciteten. Alle vognkapaciteterne i alle punkter overholdes på grund af begrænsning (9.12).
 


Alle vogne skal starte og slutte tomme, hvilket er udtrykt i nedenstående begrænsningssæt (9.13).
 


Ovenstående begrænsningssæt fra 9.2 til 9.13 definerer den endelige testmodel. Modellen er vist i sammenhæng herunder og afprøves med forskellige antal kunder og vogne.


Modelafprøvning

Til modelafprøvningen er anvendt forskellige løsningsværktøjer for at udelukke fejl, der kan være forskyldt af løsningsværktøjet. Værktøjerne GLPSOL (GNU Linear programming solver)1,  LP løseren SoPlex (The Sequential object-oriented simPlex)2 der anvendes af MILP løseren SCIP (Solving Constraint Integer Programs)3, og endeligt er NEOS serveren anvendt i forbindelse med SCIP og CPLEX4. GLPSOL er frit software, som kan anvendes frit af alle. SoPlex og SCIP må kun anvendes frit i forbindelse med forskning, mens CPLEX er en state of the art kommerciel LP løser.

Til selve modelleringen anvendes GNU mathprog modeling language, som er frit matematisk modelleringssprog, der svarer til AMPL (A Modeling Language for Mathematical Programming)5, som er en kommerciel ækvivalent. GNU mathprog følger med i samme softwarepakke som GLPSOL, hvorfor GNU mathprog kan aflæses direkte af GLPSOL. Modelfilerne kan derefter konverteres til MPS format, der kan læses af SCIP og NEOS. I tilfælde hvor GLPSOL ikke er i stand til at finde en løsning, kan SCIP og NEOS afprøves.

Det første forsøg er baseret på en vogn og en kunde, der består af fire knudepunkter 1-4, som er henholdsvis vognens startdepot, vognens slutdepot, kundens afhentnings- og afleveringspunkt. Den forventede løsning har derfor følgende rutesekvens 1-3-4-2 (startdepot-afhentningspunkt-afleveringspunkt-slutdepot se figur 9.1). En kørsel af modellen test00.mod genererer en optimal løsning med to ruter i stedet for den forventede ene rute. I den første rute i løsningen kører vognen fra sit startdepot til slutdepot (1-2), og i den anden rute kører vognen fra kundens afhentningspunkt til kundens afleveringspunkt (3-4). Denne løsning medfører en objektfunktionsværdi, som er minimeret til 2 (x variabler med værdien 1: x121 og x341). Dette er ikke en valid løsning, da vognen i rute nummer to hverken starter eller slutter i sit depot. Denne testmodel er baseret på en basismodel (se Jørgensen, 2002, s. 73), som sandsynligvis er mangelfuld. Der mangler en begrænsning, der sørger for, at alle afhentnings- og afleveringspunkter forlades igen, hvis de besøges af en vogn. Begrænsningen skal tvinge vognen til at forlade afleveringspunktet i knudepunkt 4 i ruten 3-4. Vognen tvinges derfor til kørsel på strækningen j,i, når der køres på strækningen i,j. Dette gælder for alle punkter i problemet j og alle afhentnings- og afleveringspunkter i. Begrænsningen kan udtrykkes ved hjælp af følgende matematiske udtryk (9.14) (se Baugh et al., 1998, s. 94 og Bergvinsdottir, 2004, s. 22).
 


Denne begrænsning sørger for aktivering af strækningen (j, i) = (én af alle knudepunkter, 3), når en vogn færdes på strækningen (i, j) = (3, 4). Vognen skal derfor køre på en strækning, der lander i knudepunkt 3. Endvidere tvinges vognen tilbage til sit depot af begrænsning (9.3), hvorfor knudepunkt 2 også besøges. Ved tilføjelse af ovenstående begrænsningssæt til modelformuleringen dannes model test01.mod, som kan løses til optimalitet og giver følgende forventede og valide rute 1-3-4-2 med en objektfunktionsværdi på 3. Følgende x variabler er aktiveret (x131 , x341 og x421). Løsningerne kan findes i output.txt filerne på DVD'en i samme sti som modelfilerne (DVD/MILP/).

Målet er, at få modellen til at løse problemer med 1000+ kunder og 500+ vogne. Testdata er nødvendige til opstilling af et testscenarie, som skal afspejle problemstillingens parametre med forskellige antal kunder og vogne. Til formålet er en en parametergenerator7 opbygget, der generer tilfældige data. Modellerne test02.mod ogtest03.mod er kørt med henholdsvis (kunder, vogne) = (n, v) = (5,5); (10, 10); (100, 100). Den mindste model på (n, v) = (5, 5) løses med alle værktøjerne på under et minut. GLPSOL kan ikke løse en modelstørrelse på (n, v) = (10, 10) indenfor to timer, mens SCIP/SOPLEX finder den optimale løsning i løbet af 59 minutter og SCIP/CPLEX i løbet af 13 minutter. Modellen med (n, v) = (100, 100) medfører hukommelsesmangel, selvom den tilgængelige hukommelse er på to GB RAM. Flere testforsøg udføres ikke, da det antages, at forbedringer i modellen ikke kan mindske hukommelsesforbruget betydeligt.

Med det tilgængelige hardware har det vist sig, at optimal matematisk løsning af problemet i nødvendig størrelsesorden ikke er mulig. Mere hukommelse vil ikke løse problemet, da løsningstiden stiger betydeligt, når flere kunder og vogne tilføres problemet. En afgørende faktor er derfor også processor kraften, som ikke er tilstrækkelig i nutidens computerhardware. På baggrund af forgående forsøg, vil det videre arbejde til løsning af problemstillingen koncentreres om andre  løsningsmetoder.

Kilder

DARP er NP-hard (se Mauri et al., 2006, s. 1 og Baugh et al., 1998, s. 96), som betyder at den optimale løsning ikke kan findes i polynomisk tid, selvom det i nogle tilfælde er muligt. Eksakte matematiske metoder er derfor ikke anvendelige i praksis med problemer større end 10-20 kunder (se Baugh et al., 1998, s. 100), da løsningstiden herved bliver uacceptabel. En matematisk model opstilles alligevel, så en bedre forståelse for problemstillingen kan opnås. Den matematiske model forsøges løst ved hjælp af lineær programmering, hvorefter løsningen kan anvendes som optimal reference.

På baggrund af problemstillingens sværhedsgrad retfærdiggøres anvendelse af heuristiske metoder i løsningsprocessen. I litteraturen findes mange forslag til, hvordan det statiske og dynamisk DARP kan løses. Den statiske del er domineret af metaheuristikker, som er baseret på kunstig intelligens (se Winston et al. s. 805). Hovedgrupperne for metaheuristikker er genetiske algoritmer (biologi, genmanipulation), simulated annealing (fysik, termodynamik anvendt i blandt andet metalindustrien) og tabu søgning (hukommelse). Der er både fordele og ulemper ved anvendelse af disse heuristikker, og en analyse af det teoretiske materiale udføres senere i opgaven.

Kilder