README

Nasze podejście do problemu pozostawiliśmy sferze czysto(?) algorytmicznej.

Naszą pracę rozpoczęliśmy od dodania lokalizacji, które wedłg nas nadawałyby się do postawienia stacji ładowania. Rozszerzyło to początkowy zbiór danych z 7 tysięcy do ok 60 tysięcy w całej Polsce w tym 20 tysięcy w aglomeracjach miejskich.
Następnie postanowiliśmy znaleźć optymalne drogi pomiędzy parami aglomeracji. W tym celu wykorzystaliśmy algorytm A* łącząc centra miasta linią dróg. Otrzymany wynik był zbliżony do odległości w linii prostej a drogi prowadziły często przez małe miejscowości. Sumaryczny wynik tras wynosi ok 100 tysięcy kilometrów.
Z lokalizacji odpowiednich do postawienia stacji ładowania w każdym mieście stworzyliśmy spatial index, który pozwala wydajnie znajdować punkty najbliższe do wybranych tras. Niestety nie starczyło nam czasu na dokończenie ostatniego kroku, a co za tym idzie zminimalizowania ogólnej funkcji błędu do zadania pierwszego.

Jednocześnie przygotowywaliśmy rozwiązanie części drugiej. Z wybranych najkrótszych dróg pomiędzy parami miast, stworzyliśmy graf, w którym przy pomocy algorytmu Prima utworzyliśmy minimalne drzewo rozpinające o łącznej długości ścieżek ok 2600km. Pozwalałoby to na dojechanie do dowolnego miasta. Przy założeniu, że mamy dostępne 3000 stacji do rozstawienia poza miastami, pozwoliłoby to na ustawienie stacji w odległościach co 860m. Niestety ostatnia faza tego algorytmu również opiera się na tym samym rozwiązaniu co pierwszej części, której nie udało nam się dokończyć(wybranie odpowiednich punktów z potencjalnych kandydatów), co za tym idzie, nie wygenerowaliśmy plików wyjściowych, jedynie estymacje.

Jeśli chodzi o rozmieszczenie stacji ładowania w Warszawie i we Wrocławiu, naszym planem było wykorzystanie algorytmu k-środków na optymalne rozmieszczenie k stacji pomiędzy budynkami.

Zaimplementowaliśmy program obliczający najmniejsze odległości wzdłuż dróg przy użyciu Intel MPI oraz OpenMP. Wymyślony algorytm dobrze się skaluje.

fin