Design and implementation of carpooling matching algorithms
Σχεδίαση και υλοποίηση αλγορίθμων διαμοιρασμού μετακινήσεων
View/
Keywords
Transportation domain ; Carpooling problem ; Genetic algorithms ; Crossover operator ; Mutation operator ; Local-search method ; Privacy ; Authentication schemeAbstract
In the current work, we design and implement two new algorithms applicable to problems in the transport domain. More specifically, we investigate a special case of a transportation domain problem, the carpooling problem. In that defined problem, multiple passengers and drivers commute in order to travel together and reduce their costs, environmental impact, have flexibility and decrease time of travel instead of with traditional means of transport. This thesis, proposes two new al-
gorithms based on the popular genetic algorithm NSGA-II that solve the carpooling problem when the participants have the same destination. We examine two variants of the problem: (a) with one driver and multiple passengers and (b) with multiple drivers and multiple passengers. Our proposed modifications include a new initialization procedure based on a clustering heuristic for better selecting the initial population when NSGA-II is applied, a new crossover operator based on the spatial position of passengers, named spatial crossover operator, and a local search method for applying a newly designed mutation operator. The structure of the proposed algorithms is presented along with implementation details and tools used for their development. Also, extensive evaluation and experiments were conducted to measure the effectiveness of the proposed methods and assess the quality of the generated solutions. The results show that the two proposed algorithms and the techniques utilized in the modified NSGA-II algorithm affect the quality of the best solutions in a positive way. Finally, a brief overview of the most popular privacy and authentication schemes in such carpooling services that exist in the literature, is presented.
Postgraduate Studies Programme
Κυβερνοασφάλεια και Επιστήμη ΔεδομένωνDepartment
Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα ΠληροφορικήςNumber of pages
92Language
EnglishCollections
Except where otherwise noted, this item's license is described as
Αναφορά Δημιουργού-Όχι Παράγωγα Έργα 3.0 Ελλάδα
Αναφορά Δημιουργού-Όχι Παράγωγα Έργα 3.0 Ελλάδα