These are some instances for the Balanced Path problem arising from telecommunication and crew scheduling applications. For a detailed description of the problem and of the instances, please refer to: P. Cappanera, M. G. Scutellà “Color-Coding Algorithms to the Balanced Path Problem: Computational Issues” (with related Online Supplement), INFORMS Journal on Computing, 23 (3), 446 – 459, 2011.
The telecommunication suite of instances
Two data sets have been generated starting from 29 and 52 telecommunication instances respectively. Specifically:
(i) the 29 instances are available at ZIB;
(ii) the 52 instances are used in P. Belotti, L. Brunetta and F. Malucelli, “Multicommodity network design with discrete node costs”, Networks 49 (1), 90-99, 2007.
The first group of instances will be referred to as Sndlib instances, while the second one will be referred to as Belotti instances.
The crew scheduling suite of instances
A set of 20 acyclic instances has been generated starting from two crew scheduling instances proposed in J.E. Beasley and B. Cao, “A tree search algorithm for the crew scheduling problem”, European Journal of Operational Research 94, 517-526, 1996.
The instances are all contained in BP.tgz.
The text file format
The instances have the following format.
First row: number of nodes (n) number of arcs (m) number of commodities (k)
Second row: for each arc i (i=1,..,m) the start node of i is given
Third row: for each arc i (i=1,..,m) the end node of i is given
Fourth row: for each commodity h (h=1,..,k) the source node is given
Fifth row: for each commodity h (h=1,..,k) the destination node is given
A set of k rows follows, one for each commodity. Row relative to commodity h contains for each arc i (i=1,..,m) the cost of arc i for commodity h
Last row: contains the string “false” or “true” respectively for the single commodity case and the multicommodity case; in the case of single commodity, the fourth and the fifth rows contain the set of the sources and the set of the destinations, respectively.