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

https://hal.archives-ouvertes.fr/hal-03595240
Contributor : CCSD Sciencesconf.org 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

File

ROADEF_2022_mod_le_de_document...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03595240, version 1

Citation

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⟩

Share

Metrics

Record views

23

Files downloads

15