Quadratic and Higher-Order Unconstrained Binary Optimizationof Railway Dispatching Problem for Quantum Computing

TytułQuadratic and Higher-Order Unconstrained Binary Optimizationof Railway Dispatching Problem for Quantum Computing
Publication TypeJournal Article
Rok publikacjiSubmitted
AutorzyDomino K, Kundu A, Krawiec K
JournalArXiv:2107.03234
Słowa kluczowehigher-order binary optimization, hybrid algorithm, quadratic unconstrained binary optimization, Quantum annealing, railways dis-patching
Abstract

The consequences of disruptions in railway traffic are the primary cause of passengers' dissatisfaction. Hence, appropriate dispatching decisions are necessary (e.g., by assigning the order of trains), given the numerous restrictions of traffic nature. The latter is perceived as an NP-hard problem. This paper outlines QUBO (quadratic unconstrained binary optimization) and HOBO (higher-order binary optimization) representations for dispatching problems of railway traffic management. Specifically, we consider minimal span between trains, minimal stay on stations, station/track occupation, and rolling stock circulation. The main result is the hybrid algorithm to deal with disturbances in rail traffic on single-, double- and multi-track lines; the demonstrative model illustrates the issue briefly. This algorithm can solve railway dispatching problems using the quantum annealer or any other QUBO-based optimization device.

URLhttps://arxiv.org/abs/2107.03234

Projekt: