Label Setting algorithm with Dynamic update of Pareto Front
| Autor: | Antoine Giret, Yannick Kergosien, Emmanuel Neron, Gaël Sauvanet |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Giret, Antoine |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: | |
| Zdroj: | VeRoLog VeRoLog, Jun 2016, Nantes, France HAL |
| Popis: | International audience; To compute short paths on road networks in a cycling context, several criteria can be used like the distance, the security or the attractiveness of a route. Thus, a Multi Objective Shortest Path problem should be solved. We propose a new exact method, called Label Setting algorithm with Dynamic update of Pareto Front, in order to enumerate all solutions of Pareto front solution. The proposed algorithm is based on a two-phase method. In the first phase an approximation of the Pareto front is obtained with feasible solutions and some lower and upper bounds of each criterion is determined. The second phase performs a label setting algorithm with some improvement techniques that uses the previous lower and upper bounds to dynamically update the Pareto Front. Numerical experiments are performed on real data sets - with conflicting criteria - and on instances of the literature that allow to show the efficiency of the proposed method. In a second time, we propose and test a heuristic to obtain an approximation of the Pareto front on big networks and in a much lower computation time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|