SOP om Travelling Salesman-problemet

SOP om Travelling Salesman-problemet

Dette SOP handler om Travelling Salesman problemet i relation til logistik i Netto A/S. SOP'et er skrevet i fagene Virksomhedsøkonomi A og Matematik A.

Opgaven er bygget op således, at der først kommer teori og beskrivelse af Travelling Salesman problemet sammen med lidt om Netto A/S. Herefter kædes de to dele sammen, der laves en konkret beregning og fremtidsmulighederne for Travelling Salesman Problemet vurderes.

Studienets kommentar

Fin kombination af matematik og virksomhedsøkonomi.

Studieområdeprojekter på hhx hed tidligere studieretningsprojekter (SRP). Eksemplet her er skrevet som et SRP. Der er enkelte forskelle mellem de to opgavetyper. I dag skal du fx ikke skrive et engelsk abstract, men et resumé på dansk. De fleste krav er dog ens, så du kan sagtens bruge eksemplet til at få gode idéer til dit SOP.

Den bedste måde at bruge eksemplet er ved at bruge SOP-bogen sideløbende. SOP-bogen er opdateret på alle de nye regler, så du er sikker på at leve op til alle krav.

Indhold

Abstract
Indledning
1 Beskrivelse af Travelling Salesman Problemet
1.1 Travelling Salesman i netværk
1.2 Travelling Salesman Problemet som minimerings problem
1.3 Udvidelse af Travelling Salesman Problemet
2 Beskrivelse af Virksomheden Netto
2.1 Distribution
3 Anvendelse af Travelling Salesman Problemet i Distributionsstyring
4 Beregning af konkret eksempel
4.1 Upper and lower bound
4.2 Løsning vha. Microsoft Autoroute
5 Fremtidig anvendelse af Travelling Salesman Problemet
6 Konklusion
Litteraturliste
Bilag
Bilag 1 – Hamilton kæden
Bilag 2 – NNA
Bilag 3 – MST
Bilag 4 – Udvidelse af Travelling Salesman Problemet
Bilag 5 – Netto Skagen fra Køge
Bilag 6– Netto Skagen fra Årslev
Bilag 7 – Tur oversigt fra Netto
Bilag 8 – Tegning af Travelling Salesman Problemet med Netto
Bilag 9 – Microsoft Autoroute, den korteste rute
Bilag 10 – Microsoft Autoroute, den hurtigste rute

Uddrag

Indledning
Travelling Salesman problemet er et problem der længe har været undersøgt. Der findes utallige udvidelser og algoritmer til det. Det går i bund og grund ud på at finde den korteste rute mellem et antal knuder/byer, hvor man skal besøge alle knuder, det hedder Travelling Salesman problemet fordi en sælgere, der skal ud til et antal kunder/byer, alle kunder skal have besøg en gang, men hvilken vej er den optimale? Travelling Salesman problemet minder lidt om det kinesiske postbuds problem, hvor man modsat Travelling Salesman Problemet, skal besøge alle kanter som i det tilfælde symboliserer gader.

Jeg har valgt Matematik A og Virksomhedsøkonomi A, og derunder Travelling Salesman problemet som indeholder begge fag. Jeg har valgt netop dette da jeg syntes det er interessant og spændende, at lære hvorledes nogle af GPS'erne vi alle bruger i biler osv. finder frem til den korteste/hurtigste/billigst rute.

Min opgaveformulering og selve opgaven er bygget op således, at der først kommer teori og beskrivelse af Travelling Salesman problemet sammen med lidt om Netto A/S. Herefter skal de to dele kædes sammen og der laves en konkret beregning inden fremtidsmulighederne for Travelling Salesman Problemet vurderes.

Jeg har valgt at afgrænse Travelling Salesman problemet på den måde at jeg kun gennemgår 2 algoritmer til at indsnævre den optimale løsning samtidigt med jeg viser hvorledes Travelling Salesman Problemet kan laves til et minimeringsproblem. Jeg forklarer hvordan udvidelsen fungerer så det ikke kun er distancen, der er omkostningen ved at tage en kant. I forbindelse med min analyse af Netto A/S har jeg valgt kun at inddrage noget distribution og lager sammen med en kort beskrivelse af virksomheden, da det ikke er relevant for opgaven at lave en komplet virksomhedsanalyse... Køb adgang for at læse mere

SOP om Travelling Salesman-problemet

[0]
Der er endnu ingen bedømmelser af dette materiale.