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

Naoto Katayama

Journal of the Operational Research Society, 2019, vol. 70, issue 11, 1983-1996

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.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2018.1500977 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:70:y:2019:i:11:p:1983-1996

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2018.1500977

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().