An efficient bi-objective personalized route planning over two-fold time-dependent road networks - Archive ouverte HAL Access content directly
Conference Papers Year :

An efficient bi-objective personalized route planning over two-fold time-dependent road networks

(1) , (1)
1
Liping Gao
  • Function : Author
  • PersonId : 1128908
Feng Chu
  • Function : Author
  • PersonId : 1128909

Abstract

Planning routes between two points over road networks is a common yet time-consuming task. Although both travel time and utility (e.g., beauty, safety/risky or happiness) on arcs are time-dependent concurrently in real cases, they are overlooked in most prior work. In this work, targeting a personalized route planning, we allow both travel time and utility on the arc to vary from time to time. Over such two-fold time dependent road network, we aim to discover the routes with the objectives of maximizing the utility and minimizing the travel time. Due to its strong NP-hard nature, a fast new ε-constraint-based heuristic algorithm is proposed. The main idea is to transform the bi-objective problem into a series of single-objective problems which can be solved to obtain an approximate Pareto front. We evaluate the proposed algorithm based on two real-world road networks. The results show that the proposed algorithm is able to find high-quality Pareto solutions for large-scale problem efficiently.
Fichier principal
Vignette du fichier
ROADEF_2022_mod_le_de_document_LaTeX_1_.pdf (166.28 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03595240 , version 1 (03-03-2022)

Identifiers

  • HAL Id : hal-03595240 , version 1

Cite

Liping Gao, Feng Chu. An efficient bi-objective personalized route planning over two-fold time-dependent road networks. 23ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, INSA Lyon, Feb 2022, Villeurbanne - Lyon, France. ⟨hal-03595240⟩
24 View
17 Download

Share

Gmail Facebook Twitter LinkedIn More