A novel reformulation for the single-sink fixed-charge transportation problem

• 成果类型: Article
• 署名作者: Legault, Robin; Cote, Jean-Francois; Gendron, Bernard
• 署名单位: Laval University; Universite de Montreal; Universite de Montreal
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01930-y
• 发表日期: 2023
• 页码: 169-198
• 关键词: minimal algorithm; bounds

摘要

The single-sink fixed-charge transportation problem is known to have many applications in the area of manufacturing and transportation as well as being an important subproblem of the fixed-charge transportation problem. However, even the best algorithms from the literature do not fully leverage the structure of this problem, to the point of being surpassed by modern general-purpose mixed-integer programming solvers for large instances. We introduce a novel reformulation of the problem and study its theoretical properties. This reformulation leads to a range of new upper and lower bounds, dominance relations, linear relaxations, and filtering procedures. The resulting algorithm includes a heuristic phase and an exact phase, the main step of which is to solve a very small number of knapsack subproblems. Computational experiments are presented for existing and new types of instances. These tests indicate that the new algorithm systematically reduces the resolution time of the state-of-the-art exact methods by several orders of magnitude.