Abstract
This work presents solutions to the Traveling Salesperson Problem with precedence constraints (TSPPC) using Deep Reinforcement Learning (DRL) by adapting recent approaches that work well for regular TSPs. Common to these approaches is the use of graph models based on multi-head attention layers. One idea for solving the pickup and delivery problem (PDP) is using heterogeneous attentions to embed the different possible roles each node can take. In this work, we generalize this concept of heterogeneous attentions to the TSPPC. Furthermore, we adapt recent ideas to sparsify attentions for better scalability. Overall, we contribute to the research community through the application and evaluation of recent DRL methods in solving the TSPPC. Our code is available at https://github.com/christianll9/tsppc-drl.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ascheuer, N., Jünger, M., Reinelt, G.: A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Comput. Optim. Appl. 17(1), 61–84 (2000)
Bdeir, A., Boeder, S, Dernedde, T., Tkachuk, K., Falkner, J. K., Schmidt-Thieme, L. RP-DQN: an application of q-learning to vehicle routing problems. KI 2021, 3–16 (2021)
Bello, I., Pham, H., Le, Q.V., Norouzi, M., Bengio, S.: Neural combinatorial optimization with reinforcement learning. In: ICLR Workshop (2017)
Dumitrescu, I., Ropke, S., Cordeau, J.-F., Laporte, G.: The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm. Math. Program. 121(2), 269–305 (2010)
Escudero, L.F.: An inexact algorithm for the sequential ordering problem. Eur. J. Oper. Res. 37(2), 236–249 (1988)
Falkner, J. K., Schmidt-Thieme, L. Learning to solve vehicle routing problems with time windows through joint attention. CoRR abs/2006.09100 (2020)
Google Inc. OR-Tools (2016)
Helsgaun, K. An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, pp. 24–50 (2017)
Jamal, J., Shobaki, G., Papapanagiotou, V., Gambardella, L.M., Montemanni, R.: Solving the sequential ordering problem using branch and bound. In: 2017 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1–9 (2017)
Karan, M., Skorin-Kapov, N.: A branch and bound algorithm for the sequential ordering problem. In: 2011 Proceedings of the 34th International Convention MIPRO, pp. 452–457. IEEE (2011)
Kool, W., Hoof, H., Welling, M.: Attention, learn to solve routing problems!. In: International Conference On Learning Representations (2019). https://openreview.net/forum?id=ByxBFsRqYm
Li, J., Xin, L., Cao, Z., Lim, A., Song, W., Zhang, J.: Heterogeneous attentions for solving pickup and delivery problem via deep reinforcement learning. IEEE Trans. Intell. Transp. Syst. 23(3), 2306–2315 (2022)
Lu, H., Zhang, X., Yang, S.: A learning-based iterative method for solving vehicle routing problems. In: International Conference on Learning Representations (2020)
Ma, Q., Ge, S., He, D., Thaker, D., Drori, I.: Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning (2019)
Mojana, M., Montemanni, R., Di Caro, G., Gambardella, L.M., Luangpaiboon, P.: A branch and bound approach for the sequential ordering problem. Lecture Notes Manag. Sci. 4(1), 266–273 (2012)
Thyssens, D., Falkner, J. K., Schmidt-Thieme, L.: Supervised permutation invariant networks for solving the CVRP with bounded fleet size. CoRR. abs/2201.01529 (2022)
Shobaki, G., Jamal, J.: An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers. Comput. Optim. Appl. 61(2), 343–372 (2015). https://doi.org/10.1007/s10589-015-9725-9
Vaswani, A., et al.: Attention is all you need. In: Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R., (eds.), Advances in Neural Information Processing Systems, vol. 30, pp. 5998–6008 (2017)
Vinyals, O., Fortunato, M., Jaitly, N.: Pointer networks. In: Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., Garnett, R., (eds.), Advances in Neural Information Processing Systems, vol. 28, pp. 2692–2700 (2015)
Williams, R.J.: Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8(3–4), 229–256 (1992)
Xin, L., Song, W., Cao, Z., Zhang, J.: Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. Proc. AAAI Conf. Artif. Intell. 35(13), 12042–12049 (2021)
Acknowledgment
This work was supported by the German Federal Ministry of Education and Research (BMBF) via the project “Learning to Optimize” (L2O) under grant no. 01IS20013A.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendix
Appendix
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Löwens, C., Ashraf, I., Gembus, A., Cuizon, G., Falkner, J.K., Schmidt-Thieme, L. (2022). Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning. In: Bergmann, R., Malburg, L., Rodermund, S.C., Timm, I.J. (eds) KI 2022: Advances in Artificial Intelligence. KI 2022. Lecture Notes in Computer Science(), vol 13404. Springer, Cham. https://doi.org/10.1007/978-3-031-15791-2_14
Download citation
DOI: https://doi.org/10.1007/978-3-031-15791-2_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-15790-5
Online ISBN: 978-3-031-15791-2
eBook Packages: Computer ScienceComputer Science (R0)