Aplikacja wyszukiwania i wizualizacji trasy dla przewoźników samochodowych

• Autorzy: Ratuszniak P. , Gątnicki Ł.
• Języki publikacji: PL

Abstrakty

PL

W artykule zaprezentowano praktyczną implementację algorytmu genetycznego do rozwiązywania problemu optymalizacji trasy analogicznego do problemu komiwojażera. Algorytm został zaimplementowany w autorskiej aplikacji do wyznaczania trasy przejazdu dla rzeczywistych danych geograficznych polskich miejscowości pobieranych z serwisu Google Maps. Prezentowana aplikacja generuje wskazówki dojazdu i umozliwia export wyznaczonej trasy do programu Automapa, co stanowi jego doskonałe uzupełnienie.

EN

The paper presents a practical implementation of a genetic algorithm to solve the problem of route optimization analogous to the traveling salesman problem. The algorithm has been implemented in the author's application for route calculation for the real Polish geographic data retrieved from Google Maps service. Presented application generates travel directions in the text and graphic form and allows to export the computed route to the Automapa program, which is his perfect complement.

Słowa kluczowe

PL

nawigacja; GPS; optymalizacja trasy; problem komiwojażera; algorytmy genetyczne

EN

vehicle navigation system; GPS; route optimization; travelling salesman problem; genetic algorithms

• Wydawca: Wydawnictwo Uczelniane Politechniki Koszalińskiej
• Czasopismo: Zeszyty Naukowe Wydziału Elektroniki i Informatyki Politechniki Koszalińskiej
• Rocznik: 2013
• Tom: Nr 5
• Strony: 115--125
• Opis fizyczny: Bibliogr. 11 poz., rys., map.

Twórcy

autor

Ratuszniak P.

• Wydział Elektroniki i Informatyki Politechnika Koszalińska

autor

Gątnicki Ł.

• Wydział Elektroniki i Informatyki Politechnika Koszalińska

Bibliografia

• 1. http://www.gps.gov/applications/
• 2. http://www.automapa.pl/?PEI=35489&lng=PL
• 3. Papadimitriou, Christos H. (1977), "The Euclidean traveling salesman problem is NP-complete", Theoretical Computer Science 4 (3): 237–244,
• 4. Applegate, D. L.; Bixby, R. M.; Chvátal, V.; Cook, W. J. , The Traveling Salesman Problem, 2006, ISBN 0-691-12993-2
• 5. Gutin, G.; Punnen, A. P. (2006), The Traveling Salesman Problem and Its Variations, Springer, ISBN 0-387-44459-9
• 6. F. H. Khan, N. Khan, S. Inayatulla, S. Nizami: Solving ISP Problem by Using Genetic Algorithm, International Journal of Basic & Applied Sciences IJBASIJENS Vol:09 No:10 ,2009
• 7. M.Karova, V.Smarkov, S. Penev: Genetic operators crossover and mutation in solving the TSP problem, International Conference on Computer Systems and Technologies, 2005
• 8. Marco Dorigo, Luca Maria Gambardella: Ant colonies for the travelling salesman problem, Biosystems, Volume 43, Issue 2, Elsvier, July 1997, Pages 73–81
• 9. Peter Merz, Bernd Freisleben: Memetic Algorithms for the Traveling Salesman Problem, Complex Systems, 13 (2001) 297–345; 2001
• 10. Z. Michalewicz, „Algorytmy genetyczne + struktury danych = programy ewolucyjne”, Wydawnictwo Naukowo-Techniczne, 1996
• 11. David E. Goldberg, Kalyanmoy DebA comparative analysis of selection schemes used in genetic algorithms, Foundations of Genetic Algorithms, 1991