Reduce-then-Optimize for the Fixed-Charge Transportation Problem

Caroline Spieckermann (), Stefan Minner and Maximilian Schiffer ()
Additional contact information
Caroline Spieckermann: Logistics and Supply Chain Management, TUM School of Management, Technical University of Munich, 80333 Munich, Germany; and Advanced Optimization in a Networked Economy (GRK 2201), Technical University of Munich, 80333 Munich, Germany
Maximilian Schiffer: Munich Data Science Institute, Technical University of Munich, 85748 Garching, Germany; and Business Analytics and Intelligent Systems, TUM School of Management, Technical University of Munich, 80333 Munich, Germany

Transportation Science, 2025, vol. 59, issue 3, 540-564

Abstract: Research on addressing combinatorial optimization (CO) problems with machine learning (ML) is thriving with a strong focus on replacing exact but slow solvers with faster ML oracles. However, developing accurate and generalizable predictors remains challenging. We investigate a different paradigm, called reduce-then-optimize, that uses ML to reduce the problem complexity for a subsequent CO solver by predicting a relevant subset of variables. We apply this paradigm to the fixed-charge transportation problem (FCTP), an important problem class in logistics and transportation. To obtain a high-quality and problem size-agnostic predictor, we employ a tailored bipartite graph neural network (GNN). We evaluate the performance of our reduce-then-optimize pipeline on various FCTP benchmark data sets to analyze the impact of different instance characteristics, such as the supply-demand ratio or the predominance of the fixed costs, on the problem difficulty and predictability. This includes FCTP variants with edge capacities, fixed-step costs, and blending constraints. The GNN shows good prediction and generalization capabilities that translate into high-quality solutions across all data sets with optimality gaps below 1%, decreasing runtimes of a state-of-the-art mixed-integer linear programming by 80%–95%. When runtimes are limited, the problem reduction provides an effective reduction of the search space, which leads to better solutions in comparison with solving the full problem. Similarly, we systematically improve the solution quality and convergence of two established meta-heuristics by applying our reduce-then-optimize pipeline. As the GNN-based reduce-then-optimize pipeline can be easily adapted to support additional constraints and objectives, it constitutes a flexible and robust solution approach for FCTP solving in practice.

Keywords: fixed-charge transportation problem; problem reduction; machine learning; graph neural networks (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0407 (application/pdf)

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:inm:ortrsc:v:59:y:2025:i:3:p:540-564

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().