Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadata
Contributor : CCSD Connect in order to contact the contributor
Submitted on : Thursday, March 3, 2022 - 10:47:17 AM
Last modification on : Sunday, July 24, 2022 - 3:43:21 AM
Long-term archiving on: : Saturday, June 4, 2022 - 6:29:12 PM


Files produced by the author(s)


  • HAL Id : hal-03595240, version 1


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⟩



Record views


Files downloads