A combined fast greedy heuristic for the capacitated multicommodity network design problem

Abstract

The capacitated multicommodity network design problem represents a network design system and has a wide range of real-life applications, such as the construction of logistics networks, transportation networks, communication networks, and production networks. In this article, we introduce a fast greedy algorithm for solving the capacitated multicommodity network design problem. The greedy algorithm is based on link-rerouting and partial link-rerouting heuristics for the uncapacitated multicommodity network design problem. This algorithm involves a capacity scaling for reducing the number of candidate arcs and a restricted branch-and-bound for improving solutions. The algorithm succeeds in finding good solutions within a short computation time. The average computation time for solving benchmark problem instances is only several tens of seconds.

Keywords:

• Network design
• greedy heuristic
• capacity scaling

Additional information

Funding

The present study was supported by the Japan Society for the Promotion of Science (JSPS) through KAKENHI Grant Number JP25350454.