hooolius/p1_pakkelevering

Projekt P1 - Levering af pakker

P1: Pakkelevering

p1_pakkelevering is a program written in C that can find the shortest route inbetween a series of addresses within the city of Aalborg. As this program uses the Held-Karp algorithm, the RAM usages will grow exponentially as more addresses are used, with 27 addresses taking around 15 GB of RAM, therefore, use at own risk. We recommend using at most 25 addresses on most computers.

The program was written as part of our 1. semester project at Aalborg University.

Prerequisites

Windows

• MinGW with CMake installed
• Git

Linux

• CMake
• Git

Installation

Linux

Clone the repository:

git clone https://github.com/hooolius/p1_pakkelevering.git

Navigate to the build directory:

cd p1_pakkelevering/src/build

Generate makefiles:

cmake -G "Unix Makefiles" ..

Install to a location:

sudo make DESTDIR=/path/to/location install 

Or to your bin directory:

sudo make install

Windows:

Clone the repository:

git clone https://github.com/hooolius/p1_pakkelevering.git

Navigate to the build directory:

cd p1_pakkelevering/src/build

Open MinGW as administrator in src/build

Generate makefiles:

cmake ..

Install to Program Files (x86):

make install 

Usage

Linux and Windows:

To use a specific input file:

p1_pakkelevering <input file>

Or simply

p1_pakkelevering

Then input addresses at the prompt.

Example:

p1_pakkelevering test_file.txt

This will make p1_pakkelevering calculate the optimal tour from the addresses within test_file.txt

License

MIT

p1_pakkelevering's Issues

Print the full optimal route to csv file

Distance formel skrives om til at bruge gruppens standard

2

Heuistik (egen fil)

Skal nok ikke have sig egen fil men bare være en del af a star

jSon_Parser: search in address.txt output

IO conveter fra A* til kombinatorisk.

Test: With pairing heap/sorted array

map_gen: accept æøå

Få "Jorden er ikke flad" til at snakke sammen med funktioner der bruger denne funktion

Test: Held-Karp + Dijkstra/A*

Time, operations, quality of solution

Test: Brute Force + A*/Dijkstra

Time, operations, quality of solution

Kombinatorisk pathfinding

Dyn memory

Der er lavet sådan en bandit

Update map parser to consider one-way roads

jSon_Parser Parse address.txt

5

Addresse input parser (read from text file)

Input prompt

2

Test: Greedy B&B + Dijkstra/A*

Time, operations, quality of solution

A star by sejbas

Venter på at dyn array og parings hob bliver lavet

pairing heap implementation

12

Test: Med/Uden jorden_er_ikke_flad

Hvor præcis er euklidsk distance i vores limited space?

Optimisation

jSon_Parser. Output coordinates for addresses