Integrating learning-based and TSP solvers for the cylinder replacement problem

Abstract In the liquefied petroleum gas industry, service providers must regularly visit customers to replace gas cylinders. Efficiently scheduling these visits gives rise to the Cylinder Replacement Problem (CRP), a variant of the classical capacitated vehicle routing problem that involves additional complexity due to strict, customer-specific time windows determined by remaining gas levels. Recently, neural combinatorial solvers have been actively studied as a means of quickly inferring heuristic solutions. However, existing solvers are unsuitable for directly solving CRPs because (i) they cannot adequately handle strict customer-specific delivery constraints, and (ii) obtaining optimal solutions for training is computationally expensive. To address these issues, we propose a hybrid optimization framework that combines a neural combinatorial solver with traveling salesperson problem (TSP) solvers. We observe that the delivery constraints in the bilevel approach can be reformulated as an optimal transport problem. For end-to-end training, we first train a surrogate network to estimate the optimal TSP cost and then freeze its parameters before training the cost-estimation network. The remaining route optimization consists of a collection of small traveling salesperson problems, which can be solved efficiently. Experimental results show that our framework significantly outperforms the Gurobi Optimizer in both feasibility and computational efficiency. In particular, it achieves more than a 2 $$\times $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>×</mml:mo> </mml:math> speedup and improves feasibility up to 31%. Moreover, solutions from our framework can serve as high-quality initializations for traditional solvers, further accelerating convergence-especially valuable in real-world scenarios that require flexible and rapid rescheduling due to fluctuating gas consumption.