EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Akihiro Yoshida, Nozomi Hata, Keiichiro Yamamura, Hiroki Ishikura, Katsuki Fujisawa

Japan Journal of Industrial and Applied Mathematics · 2026-06 · 43 (2)

DOI: 10.1007/s13160-026-00796-9 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Japan Journal of Industrial and Applied Mathematics, online erschienen am 23.05.2026. Verfasst von Akihiro Yoshida und 4 weiteren Autor:innen. Die Arbeit nennt 17 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Japan Science and Technology Agency, Core Research of Evolutionary Science and Technology.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Japan Science and Technology Agency
  • Core Research of Evolutionary Science and Technology

Zitieren

APA

Yoshida, A., Hata, N., Yamamura, K., Ishikura, H., & Fujisawa, K. (2026). Integrating learning-based and TSP solvers for the cylinder replacement problem. Japan Journal of Industrial and Applied Mathematics, 43(2). https://doi.org/10.1007/s13160-026-00796-9

Vancouver

Yoshida A, Hata N, Yamamura K, Ishikura H, Fujisawa K. Integrating learning-based and TSP solvers for the cylinder replacement problem. Japan Journal of Industrial and Applied Mathematics. 2026;43(2). doi:10.1007/s13160-026-00796-9

BibTeX
@article{Yoshida2026,
  author = {Yoshida, Akihiro and Hata, Nozomi and Yamamura, Keiichiro and Ishikura, Hiroki and Fujisawa, Katsuki},
  title = {Integrating learning-based and TSP solvers for the cylinder replacement problem},
  journal = {Japan Journal of Industrial and Applied Mathematics},
  year = {2026},
  volume = {43},
  number = {2},
  doi = {10.1007/s13160-026-00796-9}
}
Kostenlos starten →