Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

04.02.2017 | Ausgabe 1/2017 Open Access

Data Science and Engineering 1/2017

Investigating TSP Heuristics for Location-Based Services

Zeitschrift:
Data Science and Engineering > Ausgabe 1/2017
Autoren:
Weihuang Huang, Jeffrey Xu Yu

Abstract

Travel planning is one of the important issues in the location-based services (LBS). Traveling salesman problem (TSP) is to find the optimal tour that traverses points exactly once in the minimum total distance. Given the hardness of TSP (NP-hard), TSP query for a given set of points, \(Q\), is not widely studied for online LBS, and the nearest-neighbor heuristic is the only heuristic adapted to find TSP-like tours with additional constraints for LBS. The questions to ask are: Is the nearest-neighbor the best in terms of accuracy? Which heuristics among many should we use to process TSP queries online for LBS? In the literature, TSPLIB benchmarks are designed for special cases where the number of points used is large, and the existing synthetic datasets are based on uniform/normal distributions. Both do not reflect the real datasets used in real applications. Therefore, the best heuristics suggested by the TSPLIB and the existing benchmarks need to be reconsidered for LBS setting. In this work, we investigate 22 heuristics and show that the best heuristics in terms of accuracy for LBS are not the ones suggested by the existing work, and identify several heuristics by extensive performance studies over real datasets, TSPLIB benchmarks, the existing synthetic datasets and our new synthetic datasets. Among many issues, we also show that it is possible to get high-quality TSP by precomputing/indexing, even though it is hard to prove by theorem.
Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2017

Data Science and Engineering 1/2017 Zur Ausgabe

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise