We focus on a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. We represent this problem on a directed graph where the capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete subgraph. Our contribution in this work is a set-partitioning formulation from a Dantzig-Wolfe decomposition of an existing mixed linear programming model, leading to a column generation algorithm. An extensive computational experience based on existing benchmark instances has compared this column generation algorithm against a previous exact algorithm based on the branch-and-cut technique. This computational experience shows a clear dominance of the column generation algorithm as far as the computational time is concerned. Furthermore, our proposal is able to solve to optimality some larger instances not solved by the previous exact algorithm.
| Subject : | : | Abstracts |
| Topics | : | Column generation/branch-and-price |
| PDF version | : |  PDF version |
