SOP om Travelling Salesman-problemet

Side 1

1 af 27

Abstract

The shortest route have always been a goal for every transport or movement. Since the first humans started walking around gathering fruits and nuts the optimal route has been wanted.

The Travelling Salesman Problem is a way to find the optimal solution. However, the optimal solution is not so optimal anymore. My optimal solution could be the shortest one, while your optimal solution could be the cheapest or fastest one.

In this assignment, I will put focus on how to find the optimal or efficient solution, depending on whether you are using the expansion or not. Furthermore, I will discuss the purpose of finding an

optimal route, and put in a business context in relation to Netto A/S. I will later on try to predict

some future applications for the Travelling Salesman Problem.

This assignment have given me insight in a well-studied mathematic problem. I have discovered how a minimization problem can be formulated. I have shown in praxis how this “problem” can be used to optimize distribution of goods, and suggested how it can be used in the future. To conclude on all this, the Travelling Salesman Problem is still used and could still with advantage be

used in the future. Netto A/S could be an example of a company who uses it, whether it is on

purpose or not I cannot be curtain. The application of the Travelling Salesman Problem gives a company the possibility of utilizing its resources.

Side 2

2 af 27

Indholdsfortegnelse

Abstract ............................................................................................................................................................. 1 Indledning .......................................................................................................................................................... 3

1 Beskrivelse af Travelling Salesman Problemet ............................................................................................... 4

1.1 Travelling Salesman i netværk ................................................................................................................. 4

1.2 Travelling Salesman Problemet som minimerings problem .................................................................... 6

1.3 Udvidelse af Travelling Salesman Problemet .......................................................................................... 9

2 Beskrivelse af Virksomheden Netto ............................................................................................................. 11

2.1 Distribution ............................................................................................................................................ 12

3 Anvendelse af Travelling Salesman Problemet i Distributionsstyring .......................................................... 13

4 Beregning af konkret eksempel .................................................................................................................... 18

4.1 Upper and lower bound ........................................................................................................................ 18

4.2 Løsning vha. Microsoft Autoroute ......................................................................................................... 19

5 Fremtidig anvendelse af Travelling Salesman Problemet ............................................................................ 21

6 Konklusion .................................................................................................................................................... 23 Litteraturliste ................................................................................................................................................... 24 Bilag ................................................................................................................................................................. 25 Bilag 1 – Hamilton kæden ............................................................................................................................ 25 Bilag 2 – NNA ............................................................................................................................................... 25 Bilag 3 – MST ............................................................................................................................................... 26 Bilag 4 – Udvidelse af Travelling Salesman Problemet ................................................................................ 26 Bilag 5 – Netto Skagen fra Køge .................................................................................................................. 27 Bilag 6– Netto Skagen fra Årslev ................................................................................................................. 27 Bilag 7 – Tur oversigt fra Netto .................................................................................................................... 28 Bilag 8 – Tegning af Travelling Salesman Problemet med Netto ................................................................ 28 Bilag 9 – Microsoft Autoroute, den korteste rute ....................................................................................... 29 Bilag 10 – Microsoft Autoroute, den hurtigste rute .................................................................................... 29

Side 3

3 af 27

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.

Side 4

4 af 27

1 Beskrivelse af Travelling Salesman Problemet

Travelling Salesman problemet er egentligt noget vi alle har brugt eller i hvert fald tankegangen.

Den situation hvor man skal besøge for eksempel 3 steder inden man skal hjem igen, hvilket skal man så besøge først og hvilket skal være det sidste for man køre den korteste distance?

Travelling Salesman Problem betyder direkte oversat den kørende sælgers problem dvs. en sælger skal besøge n byer, han skal besøge hver by netop en gang og derved også forlade hver by en gang. Han starter og slutter i samme by. Hvilken rute skal han vælge hvis han ønsker den korteste rute? Dette er det verdenskendte Travelling Salesman Problem. Travelling Salesman problemet er et ofte studeret matematisk område.

For at man kan bruge Travelling Salesman går man ud fra at afstandene er symmetriske, altså at afstanden fra by a til by b er den samme som afstanden fra b til a. Samtidigt med dette er grafen komplet, dvs. at der er en kant der forbinder alle knuder med hinanden. Alle knuder er således naboer, dvs. forbundet med hinanden. Man tager endvidere forbehold for at der ikke findes parallelle kanter, eller såkaldte loops, hvor en kant forbinder en knude med sig selv. I forbindelse med Travelling Salesman Problemet skal man sikre sig at alle byer bliver besøgt. Med andre ord skal man på sin rute gennem alle knuder på grafen. Når der i en graf er tegnet en rute som går gennem alle knuder, men ikke nødvendigvist alle kanter, kaldes det en Hamilton cirkel eller en Hamilton kæde. [1] Figur a i bilag 1 er derfor en Hamilton kæde mens figur b ikke er.

1.1 Travelling Salesman i netværk

1

Bilag 1

Side 5

5 af 27

Figur 1.1 – netværk med omkostninger

For at regne den optimale i et tilfælde som i figur 1, som er et netværk, kan man bare prøve sig frem. Problemet er bare, at der hurtigt bliver mange muligheder. Hvis man som i ovenstående tilfælde har 5 punkter, er der 12 mulige løsninger. Måden hvorpå man udregner antallet af mulige

løsninger er^{(}^{𝑛−1}_{2}^{)}^{!}, n er antallet af knuder. Grunden til man trækker en fra er at det første punkt

er bestemt, f.eks. i figur 1 kan man have bestemt at man skal starte i punktet A, der er derfor til punkt nummer 2 (5-1) muligheder til punkt 3 er der derfor (5-2) osv. Til det sidste punkt vil der også kun være en mulighed derfor skal det ikke med da man blot ganger med 1. Man dividere med

2, da længden af turen ikke afhænger om man tager den forfra eller bagfra, altså hvis A B D C E A var en løsning er det det samme som A E C D B A. Man kan altså hurtigt se at der skal ikke være ret

mange knuder/byer før Travelling Salesman problemet hurtigt bliver u overskueligt. Hvis man blot

har 10 knuder inklusiv startknuden er der 181.440 mulige ruter.

Der findes dog nogle algoritmer som man kan bruge til at finde ud af om det er en mulig optimal løsning man har fundet. Jeg vil her gennemgå en fremgangsmåde hvor man finder den øvre grænse og den nedre grænse. Ved hjælp af Nearest Neighbor Algorithm (NNA) finder man den øvre grænse for den optimale rute, og ved hjælp af Kruskal’s Minimal Spanning Tree (MST) finder man den nedre grænse. Jeg vil i min gennemgang af disse 2 metoder bruge figur 1 som grundlag for dette.

Ved brug af NNA, skal man finde den nærmeste nabo hele tiden. To knuder er naboer hvis de er forbundet at en kant. Mit start og slutpunkt er i dette tilfælde A. Den nærmeste nabo til A er C da de har en afstand på 16.

NNA kommer til at se således ud [2]

A C E B D A

🡪

B

2

Se Bilag 2

Side 6

6 af 27

Når man har været gennem alle knuder skal man tilbage til A. Her vurderer man hvilken afstand der er kortest, i dette tilfælde var det B derfor ->B. Alle afstandene lægger man herefter blot sammen og derved får man at den øvre grænse er 75.

For at finde den nedre grænse bruger man MST, det fungerer på den måde at man sorterer afstandene og vælger herefter de laveste ud, men der må ikke dannes en kreds.

Man kan også lave MST ved at fjerne et punkt og gemme det til sidst. Det er denne metode jeg vil benytte mig af. Derfor ser jeg nu bort fra alle kanter der fører til knuden D. [3]

BE=5
EC=9
AC=16

Nu har jeg taget alle de kanter jeg kan uden at det bliver en lukket kantfølge. Så ser jeg på hvordan D bedst kan forbindes med det Minimal Spanning Tree jeg har lavet, den korteste måde er CD + DB. Lægger man alle kanternes omkostninger sammen får man derfor 66 som så er den nedre grænse.

Nu kan jeg altså sige om den optimale løsning til figur 1 følgende:

66 ≤ 𝑜𝑝𝑡𝑖𝑚𝑎𝑙 𝑟𝑢𝑡𝑒 ≤ 75

Når vi ved at den optimale rute er mellem disse to grænser kan man altså sige at hvis man finder frem til en rute der er længere en 75 kan man med sikkerhed sige at det ikke er den optimale løsning på dette Travelling Salesman problem, man kan også med sikkerhed sige at der ikke findes en kortere rute end 66. Man har altså her indsnævret det interval hvori den optimale løsning skal findes.

1.2 Travelling Salesman Problemet som minimerings problem

For at kunne finde den kortest mulige afstande mellem n byer, er vi selvfølgelig nødt til at kende afstande mellem de enkelte byer. Afstande mellem byerne kunne man f.eks. kalde C. Her er det ij altså afstanden mellem by i og by j. For at kunne finde frem til den kortest mulige længde skal man bruge følgende indikator variabel:

𝑋_{𝑖𝑗} = {

1, 𝐻𝑣𝑖𝑠 𝑏𝑦 𝑗 𝑏𝑒𝑠ø𝑔𝑒𝑠 𝑢𝑚𝑖𝑑𝑑𝑒𝑙𝑏𝑎𝑟𝑡 𝑒𝑓𝑡𝑒𝑟 𝑏𝑦 𝑖.

0 𝑒𝑙𝑙𝑒𝑟𝑠.

3

Se Bilag 3

Side 7

7 af 27

Figur 1.2 – 5 knuder , med indtegnet rute

Med udgangspunkt i ovenstående figur 1.2 vil det altså betyde følgende:

X =1

AB

X =0

AC

X =0

AE

X =0

AD

Og sådan fortsætter det bare med alle punkterne. Længden af en bestemt rute kan derfor udtrykkes på følgende måde:

∑∑𝐶 𝑋_{𝑖𝑗}

𝑖𝑗 𝑛 𝑛

𝑖=1 𝑗=1

Dette er summen af længden på en given rute. Det er altså denne sum, der skal være mindst mulig for at finde den optimale rute. Hvis vi tager det i samme eksempel som før bare med omkostninger [4] på kanterne vil det se sådan ud:

4 i dette tilfælde længder

Side 8

8 af 27

Figur 1.3 – 5 knuder med indtegnet rute og omkostninger ved de respektive kanter.

OBS. Det er muligvis ikke den optimale rute der er indtegnet det er blot et eksempel for at illustrere ovenstående udregning.

Igen tager jeg kun udregningen for knuden A, da princippet er det samme hele vejen igennem.

C X =5*1

AB AB

C X =6*0

AC AC

C X =5*0

AE AC

C X =1*0

AD AD

Det er derfor summen af hele ruten kun bliver summen af længderne på de kanter vi bruger til at komme frem til den næste kant.

Det der var succeskriteriet for Travelling Salesman Problemet, var at man besøgte alle byer en gang, og dermed også kun forlod hver by en gang. Dette kan skrives på følgende måde:

∑𝑋 = 1, 𝑓𝑜𝑟 𝑗 = 1,2,…..,𝑛

𝑖𝑗 𝑛

𝑖=1

Side 9

9 af 27

∑𝑋_{𝑖𝑗} = 1, 𝑓𝑜𝑟 𝑖 = 1,2,…….𝑛

𝑛

𝑗=1

Den sidste betingelse vi skal have med til minimeringsproblemet er betingelsen der sikre at man ikke køre delture og så springer i grafen. F.eks. at man i figur 1.3 tog en tur der hed ABD og en der hed CE. Denne betingelse ville være overflødig hvis n var 2 eller 3, da der ikke kan opstå delture i sådanne tilfælde. Betingelsen for ingen delture er derfor:

∑ 𝑋_{𝑖𝑗} ≤ | 𝑈 | − 1, 𝑓𝑜𝑟 2 ≤ | 𝑈 | ≤ 𝑛 − 2

𝑖,𝑗∈𝑈

Jeg vil nu lige kort gennemgå denne betingelse med udgangspunkt i figur 1.2, hvor der er 5 knuder,

n er altså lig 5. Det betyder at U som er en delmængde af n er 2 eller 5-2=3. Betingelsen er altså i

dette tilfælde gældende for delmængden 2 og 3. Jeg tager herefter udgangspunkt i 3. Her står altså at summen af X ij ij er mindre end eller lig |U|-1. X som jo var vores betegnelse for om en kant kom umiddelbart efter en anden. Det betyder altså at hvis vi har en delmængde af n som er 3, må summen af X maks være lig 2, det giver mening på den måde at hvis man skal kæde knuderne A, B ij og C sammen må man maksimalt bruge 2 kanter, derved sikre man sig at man ikke kommer tilbage

til start inden man har været rundt ved alle knuderne/byerne.

1.3 Udvidelse af Travelling Salesman Problemet

Udtrykket den optimale rute er ikke så præcist som det lyder, for hvad er den optimale rute rent faktisk? Indtil videre har jeg kun beskrevet den optimale rute som den korteste, men hvad hvis man ønsker den billigste eller den hurtigste? Der kan være flere årsager til at man ønsker en hurtigere rute frem for en rute der er lidt kortere. Det kan også være man ønsker at køre så billigt som muligt for at sænke omkostningerne forbundet med forbruget af brændstof etc eller så hurtigt som muligt for at undgå spild tid.

Dette kan være reelt hvis nu den korteste rute går lige gennem en by, mens en alternativ rute går uden om byen f.eks. på hovedvej eller motorvej hvor hastighedsbegrænsningen er højere. Dette er nogle af de ting der kunne tænkes at påvirke en optimal rute. Det betyder derfor at den enes optimale rute ikke altid vil være den andens. Det kommer altså an på om man lægger mest vægt på afstand, tid eller omkostningerne.

Side 10

10 af 27

I stedet for den generelle løsning som er skrevet ovenfor kan man nu lave en nu som tager højde for alle de nævnte forhold. Det bliver således et MOILP(Multiple Objective Integer Linear Program) [5] man formulerer. I dette tilfælde et der tager højde for distance, tid og omkostninger. I stedet for kun at bruge C ij ij ij som betegnede distancen, udvider vi nu med L og B

. Her betegner L

                                                      6
tiden fra i til j, mens B så betegner omkostningerne/prisen fra i til j. Som man ser i bilaget, kan det

godt tænkes at en mulig optimal rute vil ændres alt efter hvordan man vægter de forskellige forhold, det der skal minimeres hedder nu:

∑∑𝐶 𝑋_{𝑖𝑗}

𝑖𝑗 𝑛 𝑛

𝑖=1 𝑗=1

∑∑𝐿 𝑋_{𝑖𝑗}

𝑖𝑗 𝑛 𝑛

𝑖=1 𝑗=1

∑∑𝐵 𝑋_{𝑖𝑗}

𝑖𝑗 𝑛 𝑛

𝑖=1 𝑗=1

Til disse 3 er der selvfølgelig de samme underbetingelser som tidligere, der sikrede at alle knuder blev besøgt præcist 1 gang og forladt præcist 1 gang samtidigt med man den som sikrede man ikke fik delture. Det nye forhold der skal minimeres er et såkaldt multikriterie optimeringsproblem.

Løsningen ved et sådan multikriterie optimeringsproblem er ingen optimal løsning. Løsningen på det klassiske Travelling Salesman Problem er netop en entydig optimal løsning, men ved denne udvidelse finder man i stedet frem til en række efficiente løsninger. En efficient løsning, er en løsning, hvor der ikke findes en anden løsning, som forbedrer alle kriterier.

Hvis vi omsætter det til noget mere håndgribeligt vil det betyde at den korteste rute er en efficient løsning, den hurtigste er en efficient løsning og den billigste er en efficient løsning, det er de da f.eks. ved den korteste rute findes der ingen rute som er kortere, men der findes en der er enten hurtigere eller billigere.

Man skal altså ved denne model selv gå ind og beslutte hvilken løsning man søger, med andre ord skal man selv gå ind og vægte de forskellige forhold. Man kan for eksempel vægte det ved at man

5

http://www.sciencedirect.com/science/article/pii/

6

Se bilag 4

Side 11

11 af 27 vil dels gerne have en kort rute, og dels en hurtig rute. Man vægter således de to kriterier som man finder interessante med en halv, mens man vægter den billigste rute med 0.

I de mange brugervenlige computerprogrammer der findes til løsning af Travelling Salesman Problemet, findes der dog også en tilsvarende mulighed. F.eks. i programmet Microsoft Autoroute, kan man vælge at få oplyst enten den korteste eller den hurtigste. Man kan endog også vælge at finde en efficient løsning, hvor man tager højde for vejtype. Man kan med andre ord vælge hvilken vejtype man helst vil køre på. Måden hvorpå dette fungerer er at man tilskriver de uønskede vejtyper, som for eksempel kunne være motorvej, med en højere omkostning (ikke i kroner/øre, men den omkostning der er forbundet med at tage en given kant, det kunne være 5 som afstanden fra A til B jf. figur 1.3) for at det bliver mindre sandsynligt at det bliver en del af den

efficiente løsning. Det svarer altså man i stedet for C skriver C +K, her kan K være alle reelle

ij, ij positive tal.

2 Beskrivelse af Virksomheden Netto

Netto, som er en del af Dansk supermarked, er Danmarks største discountkæde. De åbnede i 1981 den første butik, som var placeret på Godthåbsvej i København. Netto har på dagligvaremarkedet en markedsandel på 19% [7]. Netto har haft succes med discountkonceptet, og har 454 butikker i Danmark [8], men har samtidigt i løbet af årene åbnet butikker i Tyskland, Polen, og senest er de gået ind i Storbritannien igen [9]. Netto er altså markedsleder på discountmarkedet i Danmark som ifølge tal fra business.dk i alt består af ca. 1600 butikker.

Netto reklamere som flere andre dagligvarebutikker med at de får leveret friske varer 7 dage om ugen, og det sætter selvfølgelig det krav at alle Netto butikkerne i Danmark skal have leveret frugt og grønt osv. 1 gang om dagen. Disse leveringer står Netto ikke selv for.

7

Artikel fra: business.dk, skrevet den 27/11-14

http://www.business.dk/detailhandel/netto-klar-med-doegnaabne-discountbutikker
8

http://www.netto.dk/OmNetto/Pages/Om-Netto.aspx

9

Artikel fra: finans.tv2.dk, skrevet den 5/11-14
http://finans.tv2.dk/nyheder/article.php/id-:netto-%C3%A5bner-f%C3%B8rste-butik-i-england.html

Side 12

12 af 27

Netto A/S indgik i 2011 en aftale med Frode Laursen A/S om leveringer til yderligere 155 butikker i

Jylland og på Fyn [10]. Aftalen opstod da Netto fik opført deres nye lager i Årslev ved Århus. Dermed har Netto nu to lagre som står for at håndtere de varer der skal ud i de 454 butikker.

2.1 Distribution

Med åbningen af det andet lager i Danmark i Årslev, kan man sige at Netto A/S anvender

decentrale lagre da man har et lager der dækker et mindre område f.eks. Sjælland og Fyn, og et andet der dækker Jylland men på samme tid kan man også sige det er et centrallager hvert lager alligevel skal levere til i omegnen af 200 butikker 1 gang om dagen. Før man byggede lagret i Årslev, havde man en centrallager i Køge, men med opførslen af lagret i Årslev har man altså splittet landet op, en af årsagerne til man valgte at splitte butikkerne op i øst og vest er nok at da lageret i Køge stod færdigt i 2003 kunne det levere til ca. 350 netto butikker, men da antallet af butikker har været stødt stigende har det altså ikke været muligt eller måske endog ikke engang lønsomt at holde sig til kun det ene lager [11]. Fordelen ved at dele landet op med to lagre, er at man kommer tættere på sine kunder, i dette tilfælde butikkerne. Derved sikre man kortere leveringstid, og lavere transportomkostninger da der skal transporteres over kortere distancer. Ulempen ved at have to lagre er jo så at man skal have to sikkerhedslagre, et hvert sted. Omkostninger opvejer således lidt hinanden. Man kan altså ikke sige at omkostningerne ved at have 2 lagre er dobbelt så store som de er ved at have 1. Netto har sparet lidt penge i forbindelse med transportomkostninger, men til gengæld binder de lidt flere penge i sikkerhedslager og bygninger.

De administrative omkostninger i forbindelse med lagerstyring samt medarbejder kan også forventes at vokse når man opretter et ekstra lager, omkostningerne til medarbejdere stiger dog heller ikke til det dobbelte da der alt andet lige bliver færre ordre for lagret i Køge at varetage.

Det virker logisk at etablere et lager til at varetager leveringerne til Jylland da der fra det tidligere centrallager i Køge til butikken i Skagen er hele 484 km, se bilag 1. Med det nye lager i Årslev er der således kun 227 km, se bilag 2.

10

Artikel fra Transport magasinet, skrevet den 7/2-11, hentet 08/12-14

http://infomedia.skoda.emu.dk/ms3/ShowArticle.aspx?outputFormat=Full&Duid=e2787c7b
11

Nyhedsmeddelse fra Langbaek logistik fra 16/04-09
http://www.langebaek.com/nettos-centrallager-i-k%C3%B8ge-forbereder-sig-til-fortsat-v%C3%A6kst-28-21.html

Side 13

13 af 27

Samtidigt med man har mere end halveret distancen har man også reduceret køretiden med mere end 50%. Dette er altså gevinsten ved at vælge 2 ”decentrale” lagre. Nettos lagre varetager de opgaver som en grossist ville have varetaget for en mindre kæde. De pakker således leverandørpaller om til butikspaller, således at de enkelte butikker ikke får leveret en hel palle med opvaskemiddel direkte fra producenten med kun modtager netop den mængde som de har brug for så de er i stand til at holde deres lagre så lave som muligt. Dette er nemlig også en del af tankegangen bag discount. Omkostninger holdes nede da der ikke er bundet store pengemængder i lagre samtidigt med at der bliver en hurtig omsætningshastighed, da de ikke har det brede og dybe sortiment som man for eksempel kender fra Føtex og Bilka.

Som tidligere nævnt har man i Netto A/S valgt at samarbejde med fragtmandsfirmaet Frode

Laursen omkring transport af varer. Den valgte transportform er derved lastbiler. Det er egentligt den eneste nuværende transportform som er mulig, da fly og skib er udelukket da det er korte afstande varerne skal transporteres over og det ikke er mulig f.eks. at sejle fra Årslev til Viborg.

Tog er heller ikke en mulighed da varerne på denne måde ikke ville kunne nå helt ud til butikkerne.

Fordelene ved lastbiler er at det er mere fleksibelt da Frode Laursen stiller varerne på dørtrinnet så at sige, samtidigt med det er hurtigere end hvis man f.eks. havde valgt at de skulle køres ud med tog og så hentes på nærmeste station. Derved er det altså lastbil, der er den eneste logiske form for transportmiddel for Netto i den nuværende situation. Man har ved indgåelse af aftalen med Frode Laursen valgt at man ikke selv vil stå for transporten og de opgaver der er i forbindelse med at levere varerne ud til butikkerne. Et af argumenterne mod selv at stå for transporten er at man ved at købe sig til transport får know-how tilført udefra. Frode Lauersen leverer varer til et sted mellem 1500 og 2000 butikker i Norden, de er dermed vant til at håndtere varerne og har bilerne og chaufførerne til at varetage denne opgave [12].

3 Anvendelse af Travelling Salesman Problemet i Distributionsstyring

I forbindelse med distributionsstyringen som jo går ud på lagring og transport af varer, kunne man måske anvende Travelling Salesman Problemet. Vi har fundet ud af at med Travelling Salesman problemet finder man frem til den korteste rute, der forbinder n byer. Det vil derfor være

12

http://www.frode-laursen.dk/da/Butiksdistribution.31.aspx

Side 14

14 af 27 nærliggende at anvende det i forbindelse med den fysiske distribution. Som vist tidligere er der store afstande fra lager og til butik, og med 454 butikker i Danmark kan der være nogle penge at hente ved at køre den optimale rute. Der er dog visse begrænsninger i forbindelse med distributionen. Man kan jo ikke blot plotte samtlige butikker i Jylland ind i en beregning og så finde den korteste rute, da lastbilen skal have plads til de varer som butikkerne skal have leveret. Man må derfor sorterer butikkerne således at de ligger nogenlunde tæt samtidigt med at lastbilen helst skal være fuld, da en spildt plads øger leveringsomkostningerne pr. palle. Alt andet lige er det mest lønsomt at køre med en fuld lastbil i stedet for en halv tom. Samtidigt med man skal sørge for lastbilen er så fuld som muligt, skal ruten være tilrettelagt således man overholder køre-hviletidsreglerne [13]. Når man har fundet frem til en gruppe af butikker som passer med en fuld lastbil, kan man bruge Travelling Salesman problemet til at finde frem til den korteste rute rundt til disse butikker. Man vil nok ikke direkte bruge Travelling Salesman Problemet til at finde den korteste rute, men nok snarere benytte sig af en af de computerløsninger, der findes som

udregner den korteste/hurtigste/billigste rute, et af de programmer som bruger Travelling

Salesman Problemet til at finde frem til den korteste rute er Microsoft Autoroute, som er en del mere brugervenligt end Travelling Salesman i sin rå form, men også nogle GPS’er, som man kender fra biler osv. har en indbygget Travelling Salesman problem-solver. Senere i opgaven vil jeg se på om Netto logistik måske også anvender Travelling Salesman Problemet i forbindelse af

tilrettelæggelse af ruterne som Frode Laursen A/S kører rundt i Danmark efter.

Umiddelbart vil det være en fordel at anvende Travelling Salesman Problemet til at finde frem til den korteste rute rundt mellem de udvalgte butikker. Den korteste rute vil betyde at der formegentligt ikke vil blive spildt ressourcer på at køre en længere rute.

Årsagen til jeg siger formegentligt er at man med sikkerhed ikke kan sige den korteste rute altid er

den bedste/billigst/hurtigste, da man ved valget af den korteste rute kan gå glip af stykker med

motorvej til fordel for f.eks. bykørsel som går en del langsommer, på den måde kan en omvej som er lidt længere godt være hurtigere. Når det kommer til den billigste rute, er det noget om hvor meget brændstof der skal bruges. Her er motorvejen ingen fordel, da man forbruger mere end

13

https://www.politi.dk/da/borgerservice/Fardsel/tunge_koeretoejer/koere_hviletid_reglerne/

Side 15

15 af 27

20% mere på at køre på motorvej frem for landevej [14]. Samlet set vil det nok være en fordel at anvende Travelling Salesman Problemet til at styre distributionen, da det er dyrt at køre langt, og for en kæde der konkurrerer på prisen, handler det om at minimere alle omkostninger der ikke giver værdi for kunderne. Det er noget i stil med Lean princippet, som godt nok bruges til produktionsstyrring, men sagtens kan overføres til hele virksomheden. Lean har til formål at reducere alle de aktiviteter der ikke skaber værdi for kunden.

Levering af frisk frugt hver dag skaber værdi for kunden, så man kan ikke blot fjerne nogle leveringer for at spare penge, det at køre en længere rute derimod skaber ingen værdi. Det vil derfor være hensigtsmæssigt at man benytter sig af Travelling Salesman Problemet for at styre distributionen, således man benytter sig af en optimal rute i forbindelse med levering af varer.

Man kan også vælge at bruge den udvidelse jeg tidligere har vist, således man finder frem til den hurtigste eller den billigste rute. Den hurtigste kunne have anvendelse hvis man nu er tæt på grænsen der er ved køre-hviletiden, eller at lastbilen simpelthen ikke kan nå rundt til butikkerne før de lukker medmindre man kører den hurtigste rute frem for den korteste. Den optimale rute i forbindelse med distributionsstyrring vil altså være forskellig alt efter hvilke byer der er på rute og efter hvad situationen er. Hensigtsmæssigheden i at benytte Travelling Salesman Problemet i forbindelse med planlægningen af ruter er klart tilstede, man skal blot overveje hvorledes man vil vægte omkostninger, distance og tid.

Travelling Salesman problemet kunne man dog anvende i forbindelse med andre situationer. I alle situationer hvor man skal flytte noget kan man i princippet bruge Travelling Salesman Problemet til at skulle flytte det den korteste distance muligt, f.eks. når pallerne til butikkerne skal pakkes med varer skal varerne hentes et sted på lagret, men hvilken rækkefølge er den korteste at hente dem i?

14

http://www.oekonomikoersel.dk/index.php/hoj-fart-koster.html

Side 16

16 af 27

Figur 3.1 – lager skitse, grøn=start, rød=varer der skal hentes, blå+kanten mellem= varer hylder.

Hvis vi tager udgangspunkt i figur 3.1 som kunne være en forsimplet skitse af et lager hvor de isolerede punkter med en kant mellem sig skal forestille hylder, mens det grønne punkt O er pakkepladsen hvor varerne skal samles. De røde punkter er derfor de ønskede varers placering.

Der hvor Travelling Salesman Problemet kunne komme ind, ville så være i hvilken rækkefølge man skal hente de forskellige varer for at køre den korteste distance. I dette tilfælde vil den korteste rute også være den hurtigste, da man må formode der ikke er forskel på hastighedsgrænsen inde på lagret. Man vil ved hjælp at Travelling Salesman Problemet derfor, kunne samle varerne på den hurtigst mulige måde. Det vil effektivisere processen frem for man bare indsamler dem tilfældigt, og igen i henhold til Lean princippet minimerer man omkostninger som ikke skaber værdi for kunden. Det vil være hensigtsmæssigt at anvende Travelling Salesman Problemet til indsamling af varer på lagret, hvis det kan gøres på en måde der ikke sænker processen. Man kunne gøre det sådan at man har en computer med indbygget Travelling Salesman Problem-solver, således at når destinationerne kommer op har den allerede regnet i hvilken rækkefølge disse skal hentes. Det kræver dog at Nettos lagre benytter fast location på deres lagre. Her kan man selvfølgelig anvende udvidelsen også, altså at man bruger den hurtigste, den billigste vil nok ikke have gang på jorden da der jo ikke er så stort et forbrug forbundet med transport på lagre, her vil det formegentligt være lønnen der er den store omkostning, derfor vil jeg mene at den hurtigste vil være den mest anvendelige, da man således vil kunne pakke flest muligt pr. time. Her kan dog det dog inddrages at der som tidligere nævnt nok ikke er forskel på hastigheden på lagret, derfor vil den hurtigste også være den korteste, med mindre der er andre forhold der spiller ind som f.eks. forhold der gør en vej er langsommere, det kunne f.eks. være at der var smalt det sted, men logisk set vil den korteste også være den hurtigste i dette tilfælde.

Side 17

17 af 27

Det vil altså være hensigtsmæssigt hvis det kan laves på en ”smart” måde, som f.eks. en computer der regner ruten så snart den får informationen om hvad der skal plukkes på lagret.

Side 18

18 af 27

4 Beregning af konkret eksempel

Til beregning af et konkret eksempel vil jeg bruge bilag 7 som rent faktisk er en rute som Frode Laursen kørte den 6. november. I den mail er ruten beskrevet altså hvilke butikker der skal besøges først og hvilke sidst, det kan ses nederst i bilaget hvor butikkerne står i rækkefølge. (De er nævnt med butiksnummer f.eks. 662. Hvilket butiksnummer der henviser til hvilken butik kan ses i mail adresserne, f.eks. så kan man se at (7)662 er Randersvej, Viborg.) Jeg vil derfor regne efter og se om det i dette tilfælde er den korteste rute som lastbilen kører.

4.1 Upper and lower bound

Til at finde den øvre og nedre grænse vil jeg bruge de algoritmer der er nævnt tidligere. I bilag 8 finder i en tegning hvorpå man kan se afstanden fra de forskellige butikker. [15]

NNA

Årslev - Randersvej, Viborg - Vesterbrogade, Viborg - Nykøbing Mors - Asylgade, Thisted - Havnen, Thisted – Årslev

Ved brug af ”Nearest Neighbor” Algoritmen finder man frem til ovenstående rækkefølge. Afstanden mellem de knuderne ved brug af den valgte rækkefølge bliver derfor:

61,9+3,1+62,7+29,4+0,65+144=301,75

Den øvre grænse for denne optimale løsning er altså 301,75 km

For at finde Minimal Spanning Tree udelukker jeg Nykøbing Mors. Det betyder at de korteste afstande er:

Havnen, Thisted til Asylgade, Thisted = 0,65
Vesterbrogade, Viborg til Randersvej, Viborg = 3,1
Randersvej, Viborg til Årslev = 61,9
Thisted, Havnen til Vesterbrogade = 88,5
Den korteste måde at forbinde Nykøbing Mors med mit Minimal Spanning Tree er 29,4+62,7 nemlig

Thisted, havnen og Viborg Vesterbrogade. Alt i alt bliver den nedre grænse altså 246,25 km.

Det betyder altså 246,25 𝑘𝑚 ≤ 𝑂𝑝𝑡𝑖𝑚𝑎𝑙 𝑟𝑢𝑡𝑒 ≤ 301,75 𝑘𝑚

Jeg kunne ikke finde ruter der var kortere end den jeg brugte i forbindelse med ”Nearest Neighbor” algoritmen.

Løsningen i Minimeringsproblemet kommer til at se således ud:

15

Udmålt vha. Google maps - https://www.google.dk/maps/@5,,11z

Side 19

19 af 27

(Årslev=Å,Randersvej viborg=R, Vesterbrogade viborg=V, Nykøbing Mors=N, Asylgade thisted=A,
Havnen Thisted=H)

X C =1*61,9

ÅR ÅR

X C =1*3,1

RV RV

X C =1*62,7

VN VN

X C =1*29,4

NA NA

X C =1*0,65

AH AH

X C =1*144

HÅ HÅ

=301,75

Jeg har her over valgt ikke at tage alle de kanter jeg ikke bruger med, men princippet er beskrevet hvor minimeringsproblemet er gennemgået.

4.2 Løsning vha. Microsoft Autoroute

For at tjekke efter om det er den optimal rute jeg har fundet, bruger jeg rute planlægningsprogrammet Microsoft Autoroute. Jeg bestemmer at det den skal finde den korteste rute mellem de definerede adresser hvorledes løsningen ser ud fremgår af bilag 9. Yderst til højre kan man se hvilken rækkefølge som programmet finder frem til. Den rute Microsoft Autoroute finder frem til er den samme, som jeg fandt frem til ovenfor, det kan altså konkluderes, at det er den korteste rute der findes på nuværende tidspunkt, samtidigt kan det også konkluderes at Netto og Frode Laursen i dette tilfælde har benyttet den korteste rækkefølge. Om de har optimeret ruten efter lige præcist den korteste rute kan jeg være i tvivle om, den hurtigste rute indeholder nemlig også den selv samme rækkefølge, der er retur ruten fra Havnen, Thisted blot anderledes. [16] Det kan her diskuteres hvilken vej lastbilen har taget hjem til Årslev og dermed hvilket kriterie Netto og Frode Lauresen har prioriteret. Der kan argumenteres for begge, på den ene side koster det meget pr. kørt kilometer da brændstofpriserne på daværende tidspunkt var høje, samtidigt med dette er foregår den hurtigste rute på motorvej, dvs. at alt andet lige vil brændstofforbruget være højere grundet den lidt højere fart i forhold til landevej. På den anden side er Lastbil

16

Jf. Bilag 9.

Side 20

20 af 27 chaufførens løn formegentligt afhængig af hvor lang tid han kører, derved omkostningerne fra det øgede forbrug ved at tage den længere men hurtigere rute blive lidt mindre. Samtidigt er der ingen stop på motorvejen som der kan være på landevejen.

Side 21

21 af 27

5 Fremtidig anvendelse af Travelling Salesman Problemet

Travelling Salesman problemet kan som vist anvendes til at finde en optimal eller efficient løsning, alt efter om man tager udvidelsen med. Det bliver stadigvæk brugt og er altså stadigvæk relevant selvom det dog nu for det meste foregår automatisk ved hjælp at et computerværktøj. Jeg vurderer at der må være flere fremtidige anvendelses muligheder for Travelling Salesman

Problemet, da det vil være relevant at finde den korteste/hurtigste/billigste rute så længe man

ikke har opfundet teleporteren. De steder jeg umiddelbart ser anvendelses muligheder er i forbindelse med: droner, selvkørende biler, levering til forbrugeren.

Først vil jeg tage fat i den mest nærliggende i forhold til Netto A/S. Der er poppet indtil flere

virksomheder der leverer dagligdagsvarer til døren så forbrugeren ikke længere skal møde op i den fysiske butik. Et af eksemplerne på dette er Nemlig.com [17]. Nemlig.com skriver bl.a. i deres manifest følgende ” nemlig.com giver dig ud over din handlefrihed: Samme priser og antal varer

                               18
som i Nettos faste discountsortiment”. De er altså konkurrent med Netto A/S og forsøger at

matche dem på prisen og sortimentet samtidigt med at de leverer til døren. Hvis netto skal matche dette kunne det være nærliggende at benytte Travelling Salesman Problemet til at finde

den korteste/hurtigste/billigste rute rundt mellem dem som har bestilt.

Man kan kæde denne mulighed sammen med de to andre. Droner og selvkørende er transportformer der er på kanten af take-off. Flyvende droner findes og bruges allerede af det amerikanske militær, samtidigt med dette findes der små flyvende droner som kan købes for et relativt beskedent beløb. [19] For lige at gøre det klart er de doner som her omtales førerløse flyvende farttøjer. [20] Droner kan med tiden måske anvendes til levering af disse varer som forbrugerne bestiller hjemmefra. Det kræver dog at dronerne har kraft nok til at løfte pakker, der vejer flere kilo, samtidigt med at de kan undvige eventuelle objekter der også befinder sig i luftrummet etc. Andre droner, fugle mm. Her vil en Travelling Salesman Problem-solver også kunne være relevant. Der kunne endvidere laves en udvidelse således at mængden af knuder, lad os sige 10, blev fordelt mellem 3-4 droner, på den måde laver udvidelsen den samlede pakke af

17

http://www.nemlig.com/forside.aspx

18

http://www.nemlig.com/om-nemligcom/manifestet.aspx

19

http://droner.dk/

20

http://da.wikipedia.org/wiki/Drone

Side 22

22 af 27 knuder om til mindre pakker, som dronerne har kapacitet til. Dronerne vil formegentligt i starten ikke kunne fragte varer til 10 kunder, det vil derfor være forholdsvist korte ture grundet deres begrænsede kapacitet og rækkevidde.

Et alternativ til droner kunne være selvkørende biler, der går dog lidt tid inden det forventes at være lovligt at slippe førerløse biler løs på de offentlige veje, men ideen vil være stort set den samme som med dronerne. Forskellen her vil være at droner kan flyve hen over forhindringer, mens bilerne skal benytte sig af det almindelige vejnet. Bilerne har på den anden side en større kapacitet i forhold til rækkevidde og plads. Samtidigt med dette er en bil mindre påvirket af vind

                       21
og vejr i forhold til en drone.

Der kan altså være muligheder i fremtiden for anvendelsen af Travelling Salesman Problemet, det der taler for er at den optimale rute altid vil være ønsket, der er stigende konkurrence og stigende fokus på omkostninger og spild, derfor vil der kunne findes nye anvendelses muligheder for netop Travelling Salesman Problemet. Travelling Salesman problemet er ofte studeret og der findes mange udvidelser og måder at finde frem til de efficiente løsninger på. Jeg tror at Travelling Salesman problemet vil have anvendelse langt ud i fremtiden.

Dette bygger jeg på en tro på at der altid vil være en stræben efter at finde den rute der har den mindste omkostning, om det er i tid, kilometer eller kroner, kan så være uvist, men i en verden hvor tid i stadig højere og højere grad er penge vil den optimale rute være målet med alt.

21

http://www.dr.dk/nyheder/viden/tech/californien-slipper-foerste-selvkoerende-bil-loes-i-dag

Side 23

23 af 27

6 Konklusion

Travelling Salesman Problemet er jagten på den optimale rute, altså den rute der har de laveste omkostninger (tid, distance eller pris). Som vist i afhandlingen findes der udvidelser der gør det muligt at finde den hurtigste eller den billigste rute og ikke blot den korteste, løsningen er derfor

ikke altid optimal men til tider ”bare” en efficient løsning på det beskrevne problem. Netto A/S har

etableret et lager mere i Danmark og har derved ændret deres lagerstruktur fra centrallager over

til decentrale lagre. Netto A/S har gode muligheder for at kunne anvende Travelling Salesman

Problemet til distributionsstyrring, da det vil optimere deres transport. Jeg har vist to måder hvorpå Travelling Salesman problemet kan anvendes i virksomheden, men der er med sikkerhed flere. Jeg har i opgaven med et konkret eksempel vist en rute fra Netto og Frode Laursen hvor den rute de kørte, også var den optimale rute jeg fandt frem til. Travelling Salesman problemet har anvendelse i dag, og kan med fordel anvendes til distributionsstyrring, hvor man ved brugen af Travelling Salesman problemet udnytter ressourcerne bedst muligt alt efter om det er tid, kr eller km man måler i. Mulighederne for fremtidig anvendelse af Travelling Salesman problemet ser jeg som lys, som bekrevet tidligere, vil den optimale rute altid være ja optimal. Den vil derfor altid være eftertragtet, for hvorfor f.eks. spilde tiden når tid er blevet til penge, og det derfor vil betyde man smider penge ud af vinduet.

Side 24

24 af 27

Litteraturliste

”Grafteori” skrevet af Jens Carstensen, udgivet af Systime A/S i 1992

Virksomhedsøkonomi A, bind 1&2, udgivet af Trojka i 2010

"Covering walks in graphs" af Futaba Fujie udgivet af Springer-verlag New York Inc i 2014

http://www.microsoft.com/en-gb/autoroute/home.aspx
http://travellingsalesmanproblem.com/
http://www.proff.dk/firma/netto-centrallager-%C3%A5rslev/brabrand/supermarkeder/1/
http://www.netto.dk/OmNetto/Pages/Om-Netto.aspx
https://www.youtube.com/watch?v=BmsC6AEbkrw
http://econ.au.dk/fileadmin/Economics_Business/Knowledge_Exchange/Gymnasielaererdag_2012/Jens_Ly

sgaard.pdf

http://www.math.uwaterloo.ca/tsp/methods/opt/opt.htm
http://travellingsalesmanproblem.com/
http://www.math.uwaterloo.ca/tsp/problem/index.html
http://www.georgmohr.dk/tr/tr10graf.pdf
http://en.wikipedia.org/wiki/Hamiltonian_path
https://www.youtube.com/watch?v=BmsC6AEbkrw&list=TLdqqRrNVHdBI
http://econ.au.dk/fileadmin/Economics_Business/Knowledge_Exchange/Gymnasielaererdag_2012/Jens_Ly

sgaard.pdf

http://www.math.uwaterloo.ca/tsp/methods/opt/opt.htm

Fra fodnoter:

http://www.sciencedirect.com/science/article/pii/
Artikel fra: business.dk, skrevet den 27/11-14
http://www.business.dk/detailhandel/netto-klar-med-doegnaabne-discountbutikker
http://www.netto.dk/OmNetto/Pages/Om-Netto.aspx
Artikel fra: finans.tv2.dk, skrevet den 5/11-14
http://finans.tv2.dk/nyheder/article.php/id-:netto-%C3%A5bner-f%C3%B8rste-butik-i-

england.html

Artikel fra Transport magasinet, skrevet den 7/2-11, hentet 08/12-14
http://infomedia.skoda.emu.dk/ms3/ShowArticle.aspx?outputFormat=Full&Duid=e2787c7b
http://www.langebaek.com/nettos-centrallager-i-k%C3%B8ge-forbereder-sig-til-fortsat-v%C3%A6kst-28-

21.html

http://www.frode-laursen.dk/da/Butiksdistribution.31.aspx
https://www.politi.dk/da/borgerservice/Fardsel/tunge_koeretoejer/koere_hviletid_reglerne/
http://www.oekonomikoersel.dk/index.php/hoj-fart-koster.html
https://www.google.dk/maps/@5,,11z
http://www.nemlig.com/forside.aspx
http://www.nemlig.com/om-nemligcom/manifestet.aspx
http://droner.dk/
http://da.wikipedia.org/wiki/Drone
http://www.dr.dk/nyheder/viden/tech/californien-slipper-foerste-selvkoerende-bil-loes-i-dag

Side 25

25 af 27

Bilag

Bilag 1 – Hamilton kæden

Bilag 2 – NNA

Side 26

Bilag 3 – MST
A B C D E
17; 5; 23; 16; 9
14 [overstreget i originalen]
[utydeligt og overstreget i originalen]
22 [overstreget i originalen]
Bilag 4 – Udvidelse af Travelling Salesman Problemet
A B C D E
5 km, 4 min, 10 kr
3 km, 1.5 min, 3 kr
4 km, 8 min, 16 kr
6 km, 3 min, 8 kr
1 km, 2 min, 3 kr
5 km, 7 min, 8 kr
4 km, 1 min, 2 kr
2 km, 6 min, 7 kr

Side 27

Bilag 5 – Netto Skagen fra Køge
Mimersvej 1, 4600 Køge
Sct. Laurentii Vej 105, 9990 Skagen
Ruteindstillinger
via E20 og E45: 4 t 46 min; 484 km
4 t 26 min uden trafik · Vis trafik
Denne rute indeholder vejafgifter.
Denne rute omfatter private veje eller veje med begrænset brug.
Se hele ruten; Se alle trin
via Rute 21: 5 t 10 min; 399 km
Sct. Laurentii Vej 105; Mimersvej 1
Jerup; Hjørring; Frederikshavn; Vendsyssel; Brønderslev; Aalborg; Klitmøller; Thisted; Aars; Hobro; Nykøbing; Skive; Struer; Viborg; Randers; Holstebro; Grenå; Herning; Silkeborg; Aarhus; Ebeltoft; Ringkøbing; Horsens; Grindsted; Vejle; Varde; Esbjerg; Haderslev; Aabenraa; Sylt; Flensburg; Næstved; Nakskov; Kalundborg; Frederikssund; Danmark; Denmark; Nationalpark Vadehavet; E45; Earth; Google
Kungälv; Alingsås; Kungsbacka; Varberg; Falkenberg
[Enkelte kortnavne er afskåret i originalen.]
Bilag 6– Netto Skagen fra Årslev
Rosbjergvej 37, 8220 Brabrand
Sct. Laurentii Vej 105, 9990 Skagen
Ruteindstillinger
via E45 og E39: 2 t 19 min; 227 km
2 t 11 min uden trafik · Vis trafik
Se hele ruten; Se alle trin
Sct. Laurentii Vej 105; Rosbjergvej 37
Hirtshals; Jerup; Hjørring; Frederikshavn; Vendsyssel; Brønderslev; Aalborg; Klitmøller; Thisted; Hanstholm; Nibe; Aars; Nykøbing Mors; Roslev; Hadsund; Hobro; Skive; Skals; Struer; Viborg; Bjerringbro; Randers; Grenå; Holstebro; Hadsten; Herning; Ikast; Ebeltoft; Skanderborg; Kattegat; E39; E45; Earth; Google
27 af 27

Side 28

28 af 27

Bilag 7 – Tur oversigt fra Netto

Bilag 8 – Tegning af Travelling Salesman Problemet med Netto

Side 29

29 af 27

Bilag 9 – Microsoft Autoroute, den korteste rute

Bilag 10 – Microsoft Autoroute, den hurtigste rute