Recent growing interest in Artificial Intelligence (AI) and platform-based autonomous fleet management systems support the algorithmic research of new means for dynamic and large-scale fleet management. At the same time, recent advancements in deep and reinforcement learning confirm promising results by solving large-scale and complex decision problems and might provide new context sensitive benefits for optimization. In this paper, we solve a residing combinatorial optimization problem commonly known as graph-based pairwise assignment, maximum bipartite cardinality matching, min-cut, or max-sum problem by the application of reinforcement learning in comparison with traditional linear programming algorithms. We provide simulative quantitative and qualitative results regarding by solving symmetric and asymmetric bipartite graphs with multiple algorithms. Particularly, the comparison includes solutions of Cplex, Hungarian-Munkres-Kuhn, Jonker Volgenant and Nearest Neighbor algorithm to reinforcement learning-based algorithms such as Q-learning and Sarsa algorithms. Finally, we show that reinforcement learning can solve small symmetric bipartite maximum matching problems close to linear programming quality, depending on the available processing time and graph size, but on the other hand is outperformed for large-scale asymmetric problems by linear programming-based and nearest neighbor-based algorithms subject to the constraint of achieving conflict-free solutions.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Combinatorial Reinforcement Learning of Linear Assignment Problems


    Beteiligte:


    Erscheinungsdatum :

    01.10.2019


    Format / Umfang :

    1088471 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Flight Gate Assignment Problem with Reinforcement Learning

    Muhafız Yıldız, Müge / Avcı, Umut / Örnek, Mustafa Arslan et al. | Springer Verlag | 2023



    Reinforcement Learning Based Decentralized Weapon-Target Assignment and Guidance

    Merkulov, Gleb / Iceland, Eran / Michaeli, Shay et al. | AIAA | 2024


    Weapon–Target Assignment by Reinforcement Learning with Pointer Network

    Na, Hyungho / Ahn, Jaemyung / Moon, Il-Chul | AIAA | 2023