National Technical University of Athens (NTUA)
Αποτίμηση ερωτημάτων σε συλλογές διαδρομών
Abstract
dc:descriptionThe recent advances in the infrastructure of Geographic Information Systems (GIS), and the proliferation of the GPS technology, have resulted in the abundance of geodata in the form of sequences of spatial locations representing points of interest (POIs), landmarks, waypoints etc. We refer to a set of such sequences as route collection. In many applications, the route collections are frequently updated as new routes are continuously created and included, or existing ones are extended or even deleted. This thesis studies three problems where given a frequently updated route collection the goal is to find a path, i.e., a sequence of spatial locations, that satisfies a number of constraints. According to the first problem a large collection of touristic routes is available and the goal is find a path that connects two landmarks through locations contained in the routes. Second, we focus on the pickup and delivery problems that appear in various logistics and transportation scenarios. A company that offers pickup and delivery services has already scheduled its fleet of vehicles to follow a collection of routes for servicing a number of customer requests. However during the day, new ad-hoc requests arrive at arbitrary times, and the objective is to find sequences of locations from the vehicle routes, i.e., paths, for picking up and delivering the new objects, and minimizing at the same time the company's expenses. Finally, we consider the problem of providing driving directions from one location of a city to another. In this context a collection of vehicle routes is constructed using everyday driving data on the road network of the city. This collection provides a trusted and "familiar" way of driving through the city, in other words it defines a "known" part of the city's network. The drivers consult the collection whenever they want to travel from one location to another, seeking for a path such that they will drive as less time as possible outside the known part of the road network without significantly increasing, at the same time, the total duration of their journey compared to the fastest way, i.e., the shortest path.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2011
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Bouros, Panagiotis
- Μπούρος, Παναγιώτης
Subjects
dc:subject × 18- Συλλογές διαδρομών
- Αποτίμηση ερωτημάτων
- Συχνές ενημερώσεις
- Πρόβλημα παραλαβών και παραδόσεων
- Δυναμικό συντομότερο μονοπάτι
- Συντομότερο μονοπάτι πολλών κριτηρίων
- Σχεδόν συντομότερο μονοπάτι
- Route collections
- Query evaluation
- Frequent updates
- Pickup and delivery problem
- Dynamic shortest path
- Multi-critera shortest path
- Near shortest path
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/26813