Darp løsningsmetoder

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