Scholarlink

<p>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<InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\times \)</EquationSource> <EquationSource Format="MATHML"><math> <mo>×</mo> </math></EquationSource> </InlineEquation> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月23日

查看全文
  • Akihiro Yoshida,
  • Nozomi Hata,
  • Keiichiro Yamamura,
  • Hiroki Ishikura,
  • Katsuki Fujisawa

摘要

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 \) × 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.