Seminario online - The k-Color Shortest Path Problem
Venerdì 19 Febbraio alle ore 15:30 la prof.ssa Paola Festa, Ordinario presso l'Università di Napoli "Federico II", terrà un seminario onlinetramite la piattaforma Teams per la durata orientativa di 1h.
Il seminario è aperto a tutti utilizzando il link sotto riportato.
Title: "The k-Color Shortest Path Problem"
Several variants of the classical Constrained Shortest Path Problem have been presented in the literature so far. One of the most recent is the k-Color Shortest Path Problem (k-CSPP), that arises in the field of transmission networks design. The problem is formulated on a weighted edge-colored graph and the use of the colors as edge labels allows to take into account the matter of path reliability while optimizing its cost.
In this talk, a first mathematical formulation of the problem of interest will described, the complexity class will be demostrated to which the problem belongs, and two exact solution approaches will be presented based on a branch and bound technique and a dynamic programming framework. Extensive computational experiments have been carried out to compare the performances of the designed solution methods and the results gathered in the numerical validation will be discussed.