Color-coding heuristic approaches for the balanced path problem

Given a weighted directed network G, we consider the problem of computing k balanced paths from a node s to a node t of G, i.e., k paths such that the difference between the longest and theshortest path is minimized. In this work, we generalize some of the results proposed in the literature for special cases, to the case in which the input graph G may have any structure. We propose a family of heuristic approaches to solve the balanced path problem, which are based on the color-coding method for computing simple paths proposed by Alon et al. The heuristic approach has been tested both on benchmark telecommunication instances of the library SNDlib and also on some real instances related to a crew scheduling problem of an Italian Airline Company.