@MASTERSTHESIS\{IMM2007-05228,
    author       = "C. R. Lessel",
    title        = "Ruteplanl{\ae}gning i hjemmeplejen",
    year         = "2007",
    keywords     = "Hjemmeplejen, f{\ae}llesbes{\o}g, heuristikker, ruteplanl{\ae}gning, v{\ae}gtet grupperet klike problem og to-fase probleminddeling.",
    school       = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}",
    address      = "Richard Petersens Plads, Building 321, {DK-}2800 Kgs. Lyngby",
    type         = "",
    note         = "Supervised by Assoc. Professor Jesper Larsen, {IMM,} {DTU}.",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/5228-full.html",
    abstract     = "Form{\aa}let med dette projekt er at unders{\o}ge muligheden for en to-fasedeling af ruteplanl{\ae}gningsproblemer i hjemmeplejen. Ideen bag to-fasedelingen er, at bes{\o}gene i f{\o}rste fase inddeles i en r{\ae}kke grupper ud fra geografisk placering, pr{\ae}ferencer, plejerens kompetencer, f{\ae}llesbes{\o}g, osv. Til hver gruppe er der tilknyttet Žen plejer.

I anden fase betragtes hver enkelt gruppe som et separat {TSPTW}. De seperate problemer er koblede igennem indbyrdes f{\ae}llesbes{\o}g. Koblingen best{\aa}r i, at et f{\ae}llesbes{\o}g betragtes som to enkelt bes{\o}g og placeres i to forskellige grupperinger.

Dette projekt tager udgangspunkt i anden fase, da denne fase kan beskrives udelukkende ved h{\aa}rde begr{\ae}nsninger.

Der er udviklet en rutegenerator som vha. af en inds{\ae}ttelsesheuristik hurtigt genererer en st{\o}rre m{\ae}ngde ruter for hver plejer. Udfra disse ruter opstilles et s{\aa}kaldt v{\ae}gtet grupperet klike problem (VGKP). Dette problem beskriver koblingen mellem de enkelte {TSPTW}. L{\o}sningen af problemet resulterer i, at der opn{\aa}s et s{\ae}t ruter, der opfylder, at to plejere kan v{\ae}re hos deres indbyrdes f{\ae}llesbes{\o}g samtidig. Der udviklet en gr{\aa}dig genstartsheuristik, som p{\aa} kort kan finde gode l{\o}sninger til {VGKP}.

Resultaterne viser, at der findes l{\o}sninger, der ligger maksimalt {0-}10 \% fra den optimale l{\o}sning, for problemer med op til ca. 455 bes{\o}g, ca. 55 f{\ae}llesbes{\o}g og 50 plejere. Instanserne brugt i dette projekt er konstruerede instanser med inspiration fra hjemmeplejen i S{\o}ller{\o}d kommune.

Ud fra resultaterne i dette projekt virker en to-fasedeling af ruteplanl{\ae}gningsproblemer i hjemmeplejen lovende og det kan v{\ae}re interessant at arbejde videre med samspillet mellem de to faser."
}