Exact decomposition algorithms for the student clustering problem
European Journal of Operational Research, 2026 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Basım Tarihi: 2026
- Doi Numarası: 10.1016/j.ejor.2026.10.036
- Dergi Adı: European Journal of Operational Research
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, ABI/INFORM, Applied Science & Technology Source, Compendex, EconLit, INSPEC, MathSciNet, Public Affairs Index, zbMATH, Business Source Ultimate (EBSCO), Engineering Source (EBSCO)
- Anahtar Kelimeler: Branch-and-benders-cut, Branch-and-check, Educational logistics, Student clustering problem, Total unimodularity
- İstanbul Üniversitesi Adresli: Evet
Özet
The Student Clustering Problem (SCP), a decision problem that precedes the School Bus Routing Problem, involves the assignment of students to schools under multi-grade capacity constraints. As a variant of the Capacitated Clustering Problem, the SCP is NP-hard, and large-scale instances are typically addressed using metaheuristics due to the computational limitations of standard Mixed-Integer Linear Programming (MILP) solvers. This study proposes, to the best of our knowledge, the first problem-specific exact decomposition algorithms for the SCP. Whereas earlier studies solved monolithic MILP formulations with general-purpose exact solvers, we develop dedicated algorithms that exploit the problem's decomposition structure, separating the combinatorial school selection (master problem) from the student assignment task (the Student–School Assignment Problem, SSAP). We show that the SSAP is solvable in polynomial time due to the total unimodularity of its bipartite constraint matrix, and we establish a partial-integrality property showing that the integrality gap arises solely from the selection variables. Building on these results, we present two exact methods that share a single-tree branch-and-check architecture and differ only in the cut returned by the subproblem: the first uses combinatorial (no-good) cuts to enumerate minimum-cardinality configurations, while the second is a branch-and-Benders-cut method that generates dual optimality cuts from the transportation subproblem. An attractiveness-based pricing phase guides the search in both. Both algorithms employ a lexicographic objective that prioritizes minimizing the number of selected schools, followed by total transportation distance. Computational experiments on 121 benchmark instances, including a real-world case study from Fortaleza, Brazil, show that both methods match or improve upon the standard MILP formulation and state-of-the-art metaheuristics such as GRASP, A-BRKGA, and Clustering Search, achieving better or equal objective values in all 484 pairwise comparisons. The two exact methods certify optimality on exactly the same 91 of the 121 instances, against 51 for the monolithic MILP, and return identical objective values on every instance they certify. This confirms what the structural analysis predicts: because the subproblem is totally unimodular, the dual Benders cut reproduces the bound the master relaxation already supplies and so adds no certification power. The two are complementary rather than interchangeable: the branch-and-Benders-cut method assumes nothing about the cost structure and so applies to the general formulation, whereas the combinatorial method exploits the lexicographic structure and, within that regime, returns the better incumbent where the time budget binds. The generality of the former is tested rather than asserted: with heterogeneous, non-dominating opening costs the branch-and-Benders-cut method certifies optima that open more schools than the minimum cardinality, and across three cost levels it is at no level significantly inferior in solution quality to the monolithic formulation. Overall, the proposed framework provides a robust and provably optimal approach for decision support in educational logistics and resource allocation.