Rozwinięty "problem marszrutyzacji"

Cześć!

Mam zadanie, które jest rozwiniętym problem marszrutyzacji. Ogólnie mówiąc:

1. Mamy jeden punkt, z którego wozimy towary do miast (oczywiście miasta są ze sobą połączone) - znamy odległości pomiędzy punktami
2. Mamy różne pojazdy (które różnią się pojemnością, ceną za kilometr, ile mogą punktów odwiedzić oraz jaki maksymalnie mogą pokonać dystans, wszystkie poruszają się z taką samą prędkością)
3. Dostawy, czyli ile i komu mamy dostarczyć (w wersji rozszerzonej również mamy okna czasowe, w których trzeba wykonać dostawę)

Wynik (koszt całkowity dostarczenia wszystkich towarów) nie musi być idealny, ważne by całe obliczenia uruchomione na przeciętny komputerze nie wykonywały się godzinami.

Ogólnie nie bardzo wiem jak ugryźć cały problem. Oczywiście nie oczekuję rozwiązania problemu, a proszę o wskazówki jak ogólnie podejść do problemu i jakie algorytmy zastosować. Ewentualnie warte uwagi rozwiązania podobnych zadań.

Z góry dziękuje.

jeżeli robisz to komercyjnie, to neo4j może ci pomóc, ma już zaimplementowane tego typu algo, wystarczy skorzystać.

Nie robię tego komercyjnie, wiec tego typu rozwiązania nie wchodzą w grę. Ma ktoś jakiś pomysł?

Nie chodzi tutaj o najlepsze rozwiązanie a w miarę optymalne (sporo przybliżone)

Algorytmy genetyczne - wydajne, ale nie znajdują optymalnych rozwiązań chociaż w realnym czasie powinny znaleźć jakieś lokalne ekstremum funkcji celu) . Główny problem to zamodelowanie genomu.