Two-phase algorithm for solving the preference-based multicriteria optimal path problem with reference points

Luigi Di Puglia Pugliese , Janusz Granat , Francesca Guerriero

Abstract

The shortest path problem arises in several contexts like transportation, telecommunication or data analysis. New requirements in solving practical problems (e.g., efficient content delivery for information-centric networks, urban passenger transport system or social network) impose that more than one criterion should be considered. Since the objectives are in conflict, the solution is not unique, rather a set of (efficient) paths is defined as optimal. The most satisfactory path should be selected considering additional preference information. Generally, computing the entire set of efficient solutions is time consuming. In this paper, we apply the reference point method for finding the best path. In a reference point-based approach, non-additive scalarizing function is applied. In this case, the classical optimality principle for the shortest path problem is not valid. To overcome this issue, we propose an equivalent formulation dealing with the constrained shortest path (CSP) problem. The idea is to define a set of constraints guaranteeing that an optimal solution to the problem at hand lies in the feasible region of the defined CSP problem. We propose a two-phase method where, in the first phase, a bound on the optimal solution is computed and used to define the constraints, whereas, in the second phase a labelling algorithm is applied to search for an optimal solution to the defined CSP problem. The method is tested on instances generated from random and grid networks, considering several scenarios. The computational results show that, on average, the proposed solution strategy is competitive with the state-of-the-art approaches and behaves the best on grid networks.

Author Luigi Di Puglia Pugliese - [Universita della Calabria]
Luigi Di Puglia Pugliese,,
-
-
, Janusz Granat (FEIT / AK)
Janusz Granat,,
- The Institute of Control and Computation Engineering
, Francesca Guerriero
Francesca Guerriero,,
-
Journal seriesComputers & Operations Research, [Computers and Operations Research], ISSN 0305-0548, e-ISSN 1873-765X
Issue year2020
Vol121
Pages1-32
Publication size in sheets1.55
Article number104977
ASJC Classification1803 Management Science and Operations Research; 1700 General Computer Science; 2611 Modelling and Simulation
DOIDOI:10.1016/j.cor.2020.104977
URL https://www.sciencedirect.com/science/article/pii/S0305054820300940?via%3Dihub#!
Languageen angielski
File
Pugliese Granat i in 2020.pdf 1.28 MB
Score (nominal)140
Score sourcejournalList
ScoreMinisterial score = 140.0, 28-08-2020, ArticleFromJournal
Publication indicators Scopus Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 2.275; WoS Impact Factor: 2018 = 3.002 (2) - 2018=3.433 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?