Given a weighted directed network G, we consider the problem of computing k balanced paths from given source nodes to given destination nodes of G, i.e., k paths such that the difference in cost between the longest path and the shortest path is minimized. Although not yet investigated by the OR scientific community, except for some preliminary theoretical results concerning the special case of acyclic networks, balanced path problems arise in several interesting applications, such as in transportation and in telecommunication settings. In this work, the focus is on the computation of node-disjoint balanced paths in the general case, where the input graph G could have any structure. Starting from some algorithmic ideas proposed for acyclic networks, a general framework based on the color-coding method for computing simple paths is first described. Then the general framework is specialized, and a pool of algorithms is designed that includes both an exact approach as well as alternative heuristics. The algorithms have been tested on a large suite of instances generated from some benchmark telecommunication instances. An additional set of instances, generated from some benchmark crew scheduling instances, has been used to get an idea of the behavior of the algorithms in the context of transportation applications. The obtained computational results are very interesting. For the telecommunication instances, in some cases the exact algorithm produced the optimal solution very rapidly; in the remaining cases, some of the proposed heuristics were able to generate high-quality solutions in a very quick time. As for the crew scheduling instances, which are larger and sometimes appear more difficult than the telecommunication ones, a suitable combination of the proposed color-coding issues allowed us to compute the optimal solutions in very short times.

Color-coding algorithms to the balanced path problem: computational issues / P. Cappanera; M.G. Scutella'. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1526-5528. - ELETTRONICO. - 23:(2011), pp. 446-459. [10.1287/ijoc.1100.0410]

Color-coding algorithms to the balanced path problem: computational issues

CAPPANERA, PAOLA;
2011

Abstract

Given a weighted directed network G, we consider the problem of computing k balanced paths from given source nodes to given destination nodes of G, i.e., k paths such that the difference in cost between the longest path and the shortest path is minimized. Although not yet investigated by the OR scientific community, except for some preliminary theoretical results concerning the special case of acyclic networks, balanced path problems arise in several interesting applications, such as in transportation and in telecommunication settings. In this work, the focus is on the computation of node-disjoint balanced paths in the general case, where the input graph G could have any structure. Starting from some algorithmic ideas proposed for acyclic networks, a general framework based on the color-coding method for computing simple paths is first described. Then the general framework is specialized, and a pool of algorithms is designed that includes both an exact approach as well as alternative heuristics. The algorithms have been tested on a large suite of instances generated from some benchmark telecommunication instances. An additional set of instances, generated from some benchmark crew scheduling instances, has been used to get an idea of the behavior of the algorithms in the context of transportation applications. The obtained computational results are very interesting. For the telecommunication instances, in some cases the exact algorithm produced the optimal solution very rapidly; in the remaining cases, some of the proposed heuristics were able to generate high-quality solutions in a very quick time. As for the crew scheduling instances, which are larger and sometimes appear more difficult than the telecommunication ones, a suitable combination of the proposed color-coding issues allowed us to compute the optimal solutions in very short times.
2011
23
446
459
P. Cappanera; M.G. Scutella'
File in questo prodotto:
File Dimensione Formato  
IJOC-BPP.pdf

Accesso chiuso

Descrizione: Articolo principale
Tipologia: Pdf editoriale (Version of record)
Licenza: Tutti i diritti riservati
Dimensione 327.21 kB
Formato Adobe PDF
327.21 kB Adobe PDF   Richiedi una copia

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

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/387973
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact