EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4239. On finding dissimilar paths with different dissimilarity weights: a comparative approach

Invited abstract in session TD-52: Integer Programming and Combinatorial Optimization: Complexity Questions and Algorithms, stream Combinatorial Optimization.

Tuesday, 14:30-16:00
Room: 8003 (building: 202)

Authors (first author is the speaker)

1. Marta Pascoal
DEIB, Politecnico di Milano; University of Coimbra
2. Maria Teresa Godinho
Mathematics, ESTIG-IPBEJA &CmafCIO

Abstract

The resilience of the solution for routing problems may be affected if the solutions share many network resources.
The problem of finding sets of K paths between given origin and destination nodes in a network which minimize a total cost function and maximize the paths dissimilarity intends to promote the search for low cost solutions that simultaneously have little in common to one another.
That problem was addressed recently based on bi-objective single-commodity and discretized flow formulations which model the similarity based on two assumptions: the minimization of the number of arc reuses and the minimization of the number of pairwise arc overlaps.
In the present work we review the bi-objective linear integer formulations and compare this bi-objective approach with single-objective formulations where the similarity measure is weighted differently depending on the sensitivity of the area of the network where arcs may be shared.

Keywords

Status: accepted

Back to the list of papers