This paper proposes a mathematical model and an exact algorithm for a novel problem, the k-Color Shortest Path Problem. This problem is defined on a edge-colored weighted graph, and its aim is to find a shortest path that uses at most k different edge-colors. The main support and motivation for this problem arise in the field of transmission networks design, where two crucial matters, reliability and cost, can be addressed using both colors and arc distances in the solution of a constrained shortest path problem. In this work, we describe a first mathematical formulation of the problem of interest and present an exact solution approach based on a branch and bound technique.

The k-Color Shortest Path Problem / Ferone, D.; Festa, P.; Pastore, T.. - 3:(2019), pp. 367-376. [10.1007/978-3-030-34960-8_32]

### The k-Color Shortest Path Problem

#### Abstract

This paper proposes a mathematical model and an exact algorithm for a novel problem, the k-Color Shortest Path Problem. This problem is defined on a edge-colored weighted graph, and its aim is to find a shortest path that uses at most k different edge-colors. The main support and motivation for this problem arise in the field of transmission networks design, where two crucial matters, reliability and cost, can be addressed using both colors and arc distances in the solution of a constrained shortest path problem. In this work, we describe a first mathematical formulation of the problem of interest and present an exact solution approach based on a branch and bound technique.
##### Scheda breve Scheda completa Scheda completa (DC)
2019
978-3-030-34959-2
978-3-030-34960-8
The k-Color Shortest Path Problem / Ferone, D.; Festa, P.; Pastore, T.. - 3:(2019), pp. 367-376. [10.1007/978-3-030-34960-8_32]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11588/866546`
• ND
• 8
• ND