zaplanowanie odśnieżania dróg w gminie w qgis.

[robert]

Witaj kabanoska.

Przedstawiłaś bardzo ciekawy i jednocześnie praktyczny problem do rozwiązania - problem komiwojażera z teorii grafów [1]. Zadanie świetnie nadaje się dla studentów z kół naukowych
Zadanie podzieliłbym na dwie części.

1. Przygotowanie danych.
Nie będzie takie proste, bo musicie do każdego odcinka drogi przypisać odpowiednią wagę. Może to być tylko liczba mieszkańców, ale można też uwzględnić inne czynniki.

2. Rozwiązanie problemu.

2a. Przy niewielkiej liczbie dróg można próbować rozwiązać to "siłowo", testując wszystkie kolejne kombinacje. Ale podejrzewam, że dróg jest na taką metodę za dużo.

2b. Można spróbować rozwiązać to metodą "wujka Zenka".
Pługopiaskarka wyjeżdża z bazy i na każdym skrzyżowaniu wybiera drogę o większej wadze, przez którą jeszcze nie jechała. Niestety na końcu zostaną prawdopodobnie drogi z małymi wagami porozrzucane po mapie. Poza tym po niektórych drogach będziemy jeździć po kilka razy.

2c. Poszukać algorytmu dostosowanego do tego problemu i zakodować go.
Nie słyszałem o takiej gotowej wtyczce do QGIS, więc raczej nie ucieknie się od napisania jakiegoś skryptu. Jest wtyczka 'optymalna droga', ale w niej zadaje się tylko dwa punkty na grafie.

Zacząłbym od metody wujka Zenka. Jeśli dobrze zwizualizujesz trasę pojazdu, będzie ją można ręcznie poprawić w momentach gdzie ludzki zdrowy rozsądek lepiej działa niż algorytmy. Czyli taka kombinowana metoda kolejnych przybliżeń. Oczywiście dobrze byłoby zliczać jaką sumaryczną odległość przejedzie pojazd dla każdej z wersji.


[1] http://www.mini.pw.edu.pl/MiNIwyklady/gr...komiw.html