Vejleder: Niels Christian Petersen, institut for organisation og ledelse
                 Joan Boyar, institut for matematik og datalogi.

Aflevering: 31. December 2001.

Capacitated arc routing problemet (CARP) forekommer  i forbindelse med postomdeling, renovation og andet hvor der er efterspørgsel efter en service på nogle veje.

Vi har givet et netværk med efterspørgsel på kanterne samt et depot indeholdende et antal identiske køretøjer. Vi ønsker nu at minimere den samlede kørte distance under bibetingelse af at alle kanter med positiv efterspørgsel bliver serviceret af netop et køretøj, og intet køretøj servicerer flere kanter end det har kapacitet til.

Problemet er NP-hard og kan derfor ikke, i praksis, løses til optimalitet, endvidere kan det vises at selv det at finde en 0,5-approximation til problemet er NP-hard. Man søger derfor af finde en god løsning ved at benytte Heuristikker, dvs. metoder man tror på giver en god løsningt.

Første del af specialet vil være en matematisk tilgang til teorien bag CARP. Her vil jeg bl.a. se på hvad det er der gør CARP så svært at løse og på hvordan CARP kan transformeres om til et "almindeligt" rutelægningsproblem (VRP).

Anden del af specialet vil behandle heuristiske algoritmer til løsning af CARP. Denne del vil dels være en teoretisk datalogisk behandling af de enkelte heuristikker, og dels en praktisk tilgang med at implimentere -og teste kvaliteten af- algoritmerne.

Slutteligt vil jeg prøve at se på hvordan de eksisterende algoritmer teoretisk set kan forbedres, og gennem implimentering undersøge de praktiske effekter heraf.