Accelerated Benders Decomposition for the Two-Level Generalized Median Tour Problem

- 325457
Complete Articles (CA)
Favorite this paper
How to cite this paper?
Abstract

This paper proposes a Benders decomposition-based algorithm to solve the Two-Level Generalized Median Tour Problem (TLGMTP), which models hierarchical distribution systems partitioned into clusters. The algorithm incorporates modern acceleration techniques, such as the two-phase approach, the use of a single branch-and-bound tree, normalized subproblems, and the addition of valid inequalities. Computational experiments conducted on 32 instances with up to 417 nodes from the GTSP-Lib demonstrate the effectiveness of the proposed approach: all instances were solved to optimality, with an average solution time of only 395.69 seconds. This represents a significant improvement over the original work method, which presented average GAPS of 3.10%, and over the CPLEX automatic Benders decomposition, which presented average GAPS of 0.08%. The results confirm that the proposed method is robust, efficient, and promising for network design problems with hierarchical structure and fixed costs.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 PUC-Rio
  • 2 Pontifícia Universidade Católica do Rio de Janeiro
Track
  • 16. OD-Discrete Optimization
Keywords
Integer Programming
Benders decomposition
Network Design