A Graph-Induced Neighborhood Search Heuristic for the Capacitated Multicommodity Network Design Problem

Houshan Zhang ()
Additional contact information
Houshan Zhang: School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China

Mathematics, 2025, vol. 13, issue 4, 1-23

Abstract: In this work, an efficient graph-induced neighborhood search heuristic is proposed to address the capacitated multicommodity network design problem. This problem, which commonly arises in transportation and telecommunication, is well known for its inherent complexity and is often classified as NP -hard. Our approach commences with an arbitrary feasible solution and iteratively improves it by solving a series of small-scale auxiliary mixed-integer programming problems. These small-scale problems are closely tied to the cycles inherent in the network topology, enabling us to reroute the flow more effectively. Furthermore, we have developed a novel resource-efficient facility assignment technique that departs from standard variable neighborhood search algorithms. By solving a series of small knapsack problems, this technique not only enhances the quality of solutions further but also can serve as a primary heuristic to generate initial feasible solutions. Furthermore, we theoretically guarantee that our algorithm will always produce an integer-feasible solution within polynomial time. The experimental results highlight the superior performance of our method compared to other existing approaches. Our heuristic algorithm efficiently discovers high-quality feasible solutions, substantially reducing the computation time and number of nodes in the branch-and-bound tree.

Keywords: capacitated multicommodity network design; large neighborhood search; mixed-integer programming (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/4/588/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/4/588/ (text/html)

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:gam:jmathe:v:13:y:2025:i:4:p:588-:d:1588300

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().