Find your way

English below

Inhaltsverzeichnis

• Inhaltsverzeichnis
• Einleitung
• Algorithmus
• Starten
• Funktionen
• Beispieldaten
• Lösung der Challenge
• Table of contents
• Intro
• Run
• Features
• Example data

Einleitung

Find your way ist eine Angular-Applikation, um ein TSP (Traveling Salesman Problem; Rundreise-Problem) zu lösen. Die Daten werden mittels einer CSV-Datei hochgeladen.

Die Web-Applikation wurde im Rahmen der get in IT Coding Challenge erstellt.

Algorithmus

Der gewählte Algorithmus basiert auf die Branch and Bound-Methode. Diese Methode wurde genommen, weil sie effekt ganzzahlige Optimierungsprobleme lösen kann. Zwar ist diese Methode relativ speicher aufwändig, jedoch sollte das für bis zu 40 Knoten kein Problem sein. Außerdem ist der Algorithmus relativ einfach zu verstehen und zu implementieren.

Starten

1. Um die Angular-Applikation zu starten, muss zuerst ein API-Key für google maps erstellt werden (siehe hier). Dieser Key muss in die Datei /src/API_KEY.txt gespeichert werden.
2. Danach kann der Docker-Container erstellt werden mit docker build -t find-your-way . und
3. gestartet werden mit docker run -it -p 80:80 find-your-way.
4. Anschließend startet die App unter localhost:80.

Funktionen

Find-your-way hat folgende Funktionen:

• CSV-Upload (siehe Beispieldaten)
• Visualisierung der Punkte auf einer Karte
• Visualisierung der kürzesten Strecke auf einer Karte
• Verlinkung der Route zwischen zwei Städten auf Google Maps (z.B. von Nürnberg nach Stuttgart).
• Verlinkung der kompletten Route mit Zwischenstopps auf Google Maps (Google Maps unterstützt nur Routen mit max. neun Zwischenstopps, deswegen wird die Route automatisch aufgeteilt)

Beispieldaten

So sollte die CSV-Datei aussehen (im Verzeichnis ist auch eine Datei example-data.csv):

Hinweis: Die Spalten Straße, Hausnummer, PLZ und Ort können leer sein.

Nummer	Standort	Straße	Hausnummer	PLZ	Ort	Breitengrad	Längengrad
1	Ismaning/München	Robert-Bürkle-Straße	1	85737	Ismaning	48.229035	11.686153
2	Berlin	Wittestraße	30	13509	Berlin	52.580911	13.293884
3	Braunschweig	Mittelweg	7	38106	Braunschweig	52.278748	10.524797
4	Bretten	Edisonstraße	2	75015	Bretten	49.032767	8.698372
5	Chemnitz	Zwickauer Straße	16a	09122	Chemnitz	50.829383	12.914737
6	Düsseldorf	Gladbecker Straße	3	40472	Düsseldorf	51.274774	6.794912
7	Essen	Am Thyssenhaus	1.3	45128	Essen	51.450577	7.008871
8	Frankfurt	Mergenthalerallee	73-75	65760	Eschborn	50.136479	8.570963
9	Görlitz	Melanchthonstraße	19	02826	Görlitz	51.145511	14.970028
10	Hamburg	Dammtorwall	7a	20354	Hamburg	53.557577	9.986065
11	Hannover	Hildesheimerstraße	265-267	30519	Hannover	52.337987	9.769706
12	Ingolstadt	Pascalstraße	4	85057	Ingolstadt	48.784417	11.399106
13	Köln/Hürth	Max-Planck-Straße	40	50354	Hürth	50.886726	6.913119
14	Lingen (Ems)	Kaiserstraße	10b	49809	Lingen	52.519154	7.322185
15	Münster	Schulstraße	22	48149	Münster	51.969304	7.61428
16	Nürnberg	Südwestpark	60	90449	Nürnberg	49.429596	11.017404
17	Passau	Dr. Hans-Kapfinger-Straße	30	94032	Passau	48.571989	13.453256
18	Schortens/Wilhelmshaven	Beethovenstraße	46	26419	Schortens	53.537779	7.936809
19	St. Georgen	Leopoldstraße	1	78112	St. Georgen	48.126258	8.325873
20	Stuttgart	Humboldtstraße	35	70771	Leinfelden-Echterdingen	48.694648	9.161239
21	Walldorf	Altrottstraße	31	69190	Walldorf	49.295011	8.649036

Lösung der Challenge

minimalster Weg (Luftlinie): 2,333.41 km

Tabelle mit Wegpunkten:

Nummer	Standort	Straße	Ort
1	Ismaning/München(Hauptsitz)	Robert-Bürkle-Straße 1	85737 Ismaning
12	Ingolstadt	Pascalstraße 4	85057 Ingolstadt
16	Nürnberg	Südwestpark 60	90449 Nürnberg
20	Stuttgart	Humboldtstraße 35	70771 Leinfelden-Echterdingen
19	St. Georgen	Leopoldstraße 1	78112 St. Georgen
4	Bretten	Edisonstraße 2	75015 Bretten
21	Walldorf	Altrottstraße 31	69190 Walldorf
8	Frankfurt	Mergenthalerallee 73-75	65760 Eschborn
13	Köln/Hürth	Max-Planck-Straße 40	50354 Hürth
6	Düsseldorf	Gladbecker Straße 3	40472 Düsseldorf
7	Essen	Am Thyssenhaus 1.3	45128 Essen
15	Münster	Schulstraße 22	48149 Münster
14	Lingen (Ems)	Kaiserstraße 10b	49809 Lingen
18	Schortens/Wilhelmshaven	Beethovenstraße 46	26419 Schortens
10	Hamburg	Dammtorwall 7a	20354 Hamburg
11	Hannover	Hildesheimerstraße 265-267	30519 Hannover
3	Braunschweig	Mittelweg 7	38106 Braunschweig
2	Berlin	Wittestraße 30	13509 Berlin
9	Görlitz	Melanchthonstraße 19	02826 Görlitz
5	Chemnitz	Zwickauer Straße 16a	09122 Chemnitz
17	Passau	Dr. Hans-Kapfinger-Straße 30	94032 Passau
1	Ismaning/München (Hauptsitz)	Robert-Bürkle-Straße 1	85737 Ismaning

Find your way (English)

Table of contents

1. Intro
2. Run
3. Features
4. Example data

Intro

Find your way is an angular app to solve a TSP (Traveling Salesman Problem) using the Branch and Bound-method.

Run

1. To run the application, you need an api key for google maps. Write this key in the file /src/API_KEY.txt .
2. Build the docker container with docker build -t find-your-way .
3. Start the docker container with docker run -it -p 80:80 find-your-way.
4. The app should be run at localhost:80.

Features

Find-your-way has the following features:

• CSV-Upload (see Example data)
• Visualization of the points on a map
• Visualization of the shortest route on a map
• Linking the route between two cities on Google Maps (e.g. from Nuremberg to Stuttgart).
• Linking of the complete route with waypoints on Google Maps (Google Maps only supports routes with a maximum of nine waypoints, therefore the route is split automatically)

Example data

This is how the CSV file should look like (there is also a file example-data.csv in the directory; this file is in German, but the language of the uploaded header is not important):

note: The columns street, house number, post code and city can be blank.

Id	location name	street	house number	post code	city	latitude	longitude
1	Ismaning/München	Robert-Bürkle-Straße	1	85737	Ismaning	48.229035	11.686153
2	Berlin	Wittestraße	30	13509	Berlin	52.580911	13.293884
3	Braunschweig	Mittelweg	7	38106	Braunschweig	52.278748	10.524797
4	Bretten	Edisonstraße	2	75015	Bretten	49.032767	8.698372
5	Chemnitz	Zwickauer Straße	16a	09122	Chemnitz	50.829383	12.914737