Skip to content
Snippets Groups Projects
README 2.07 KiB
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