A Memetic Algorithm for Computing Multicriteria Shortest Paths in Stochastic Multimodal Networks
Affiliation auteurs | !!!! Error affiliation !!!! |
Titre | A Memetic Algorithm for Computing Multicriteria Shortest Paths in Stochastic Multimodal Networks |
Type de publication | Conference Paper |
Year of Publication | 2017 |
Auteurs | Dib O., Caminada A., Manier M-A, Moalic L. |
Editor | Ochoa G |
Conference Name | PROCEEDINGS OF THE 2017 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE COMPANION (GECCO'17 COMPANION) |
Publisher | Assoc Comp Machinery; ACM SIGEVO; Sentient; Uber AI Labs; Springer; Beacon |
Conference Location | 1515 BROADWAY, NEW YORK, NY 10036-9998 USA |
ISBN Number | 978-1-4503-4939-0 |
Mots-clés | Genetic algorithms, hill climbing, memetic algorithms, Multicriteria optimization, stochastic multimodal networks |
Résumé | Modern transport systems are nowadays very complex. Building Advanced Travelers Information Systems (ATIS) has therefore become a certain need. Since passengers do not only seek a short-time travel, but they tend to optimize several criteria, an efficient routing system should incorporate a multi objective analysis into its search process. Besides, the transport system may behave in an uncertain manner. Therefore, integrating uncertainty into routing algorithms may provide better itineraries. The main objective of this work is to propose a Memetic Approach (MA) in which a Genetic Algorithm (GA) is combined with a Hill Climbing (HC) local search procedure in order to solve the multicriteria shortest path problem in stochastic multimodal transport networks. Experimental results have been assessed by solving real life itinerary problems defined on the transport network of the city of Paris and its suburbs. Results indicate that unlike classical deterministic algorithms and pure GA and hill climbing, the proposed MA provide better itineraries within a reasonable amount of time. |
DOI | 10.1145/3067695.3076064 |