CS Paper Radar

The Train Unit Shunting Problem with Service Scheduling and Workforce Assignment: classical and quantum optimization approaches

Alessia Ciacco, Francesca Guerriero, Eneko Osaba

cs.ET math.OCquant-ph ·submitted 2026-11-13 10:18 UTC · v1

Abstract

Efficient railway rolling stock management requires the coordinated planning of train-unit assignment, shunting movements, track occupation, service operations, and workforce allocation. These interdependent decisions give rise to a challenging combinatorial optimization problem, particularly as the size of the fleet and the planning horizon increase. This paper introduces the Train Unit Shunting Problem with Service Scheduling and Workforce Assignment, a mixed-integer linear programming formulation that integrates these operational decisions within a unified optimization framework. To improve computational tractability, a preprocessing procedure is developed to reduce the size of the resulting model. The proposed approach is evaluated through computational experiments on instances of increasing size and under different objective-function weight and cost configurations. Classical optimization experiments using Gurobi show that filtering method reduces the number of decision variables and constraints, while its impact on computational time varies across instances. In addition, a constrained quadratic model representation is investigated using D-Wave's hybrid quantum-classical optimization solver.

Comment
Train Unit Shunting Problem, Railway Optimization, Mixed-Integer Linear Programming, Quantum Annealing, Hybrid Quantum-Classical Optimization

Closest papers

Nearest neighbours by meaning across the whole index.

Hybrid Classical-Quantum Optimization for CVRPTW: A Systems Framework with Provable Feasibility and Empirical Hardware Limits

cs.ET quant-ph ·2026-11-11 ·Syamasundar Gopasana, Swatantra Singh, Rohan Joydhar, Shubhashis Sengupta
similarity 0.63
Abstract · 11 pages, 3 figures, Poster version of this paper has been accepted to be presented at HiPC 2026 Bengaluru Conference

Solving large-scale Capacitated Vehicle Routing Problems with Time Windows (CVRPTW) remains challenging because strict operational constraints and scale limit both exact and heuristic methods. We present a hybrid classical-quantum architecture combining Mixed Integer Linear Programming (MILP) with vehicle-level Quadratic Unconstrained Binary Optimization (QUBO), solved using Toshiba SQBM+ and QAOA on Rigetti Ankaa-3 and IQM Emerald quantum processors. The decomposition avoids the variable growth and constraint-enforcement difficulties of monolithic CVRPTW QUBO formulations. We evaluate the framework on five realistic benchmarks derived from London traffic and location data, spanning 10--70 customers, using a validation pipeline enforcing feasibility and monotone improvement over classical baselines. SQBM+ achieves verified fleet-distance reductions of 2.80% (7,927 m) for the 25-customer instance and 0.22% (1,186 m) for the 55-customer instance. QAOA experiments establish a current hardware boundary for reliable constraint satisfaction at subproblems of up to 4 customers (16 qubits). Diagnostic results identify assignment-level time-window tightness, rather than local route optimization, as the dominant scalability bottleneck. The results demonstrate a practical near-term role for hybrid classical-quantum optimization while establishing empirical limits for current quantum hardware.

0.22

QUBO Formulations of the Downlink MIMO Scheduling Problem in 5G Base Stations

eess.SP ·2026-09-16 ·Olli Apilo, Jorma Kilpi
similarity 0.63
Abstract

Quantum computers can potentially solve large-scale combinatorial problems very efficiently when the problems are first converted into the quadratic unconstrained binary optimization (QUBO) format. Scheduling in fifth generation (5G) base stations is a practical combinatorial problem that cannot be solved optimally in real-time using classical computing. We formulate the downlink (DL) multiple-input multiple-output (MIMO) scheduling at 5G base stations as QUBO and analyze the QUBO formulation scalability with respect to the key system parameters. The single-user MIMO (SU-MIMO) QUBO formulation looks promising because the number of QUBO variables grows linearly while the problem search space grows exponentially with increasing number of users. Based on the simulation results, the suboptimal greedy algorithm for the SU-MIMO performs well with a high number of users and low bandwidth. A hybrid approach, where either a quantum solver or a suboptimal low-complexity classical algorithm is selected based on the system parameters, seems sensible in practice. This work paves the way for future quantum and quantum-inspired implementations of scheduling in cellular systems.

0.20

Quantum Approximate Multi-Objective Optimization in Routing Problems

cs.ET quant-ph ·2026-09-15 ·Eduardo Willwock Lussi, Alisson dos Passos Fumaco, Marcos Vinicius Reballo, José Carlos Libois Neto, Fernando Augusto Caletti de Barros +1 more
similarity 0.61
Abstract

Multi-objective optimization (MOO) problems are common in logistics, where routing decisions must balance conflicting objectives such as travel distance, delivery time, and operational risk. A recently proposed Quantum Approximate Optimization Algorithm (QAOA) parameter-transfer strategy solves multi-objective MAX-CUT problems by reusing parameters trained on smaller instances, avoiding costly reoptimization for each scalarized problem. However, its effectiveness has only been demonstrated on proof-of-concept instances tailored to quantum hardware connectivity. In this work, we evaluate the applicability of this strategy to realistic routing problems. We formulate the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) as Quadratic Unconstrained Binary Optimization (QUBO) models, reduce them to MAX-CUT, and assess the parameter-transfer framework under conditions matching the original study. Validation is performed through classical simulations and experiments on IBM quantum hardware. The resulting Pareto fronts are compared with those obtained using an adapted classical ε-constraint method, using hypervolume as the primary quality metric. Results indicate that parameter transfer remains effective, frequently achieving higher hypervolume and often finding competitive solutions earlier. However, performance depends on problem structure. The approach is consistently effective for TSP instances but less stable for the more constrained VRP, suggesting that QAOA parameter transferability decreases as the optimization landscape becomes more complex. These results provide the first comprehensive evaluation of QAOA parameter transfer on realistic multi-objective routing problems and demonstrate its potential beyond proof-of-concept MAX-CUT benchmarks.

0.23

QC-CCG: Quantum-Classical Algorithm for Two-stage Adaptive Robust Optimization

cs.ET eess.SY ·2026-08-28 ·Duong The Do, Jiaming Cheng, Duong Tung Nguyen
similarity 0.61
Abstract · 12 pages

Quantum optimization provides a promising approach for solving large-scale combinatorial problems through quadratic unconstrained binary optimization (QUBO) formulations. However, integrating QUBO-based solvers into structured optimization frameworks while preserving solution guarantees remains a fundamental challenge. This paper develops a hybrid quantum-classical column-and-constraint generation (QCCG) framework for solving two-stage adaptive robust optimization problems with binary first-stage decisions and linear recourse under polyhedral uncertainty. The proposed approach reformulates the restricted master problem as a QUBO and solves it approximately using a quantum optimizer, while retaining a classical adversarial subproblem to compute worst-case recourse and certify solution quality. We construct a constraint-preserving QUBO encoding for inequality-constrained master problems using slack variables and penalty terms, enabling general mixed-integer structures to be mapped to quantum-compatible representations. To address inexactness arising from discretization, penalty modeling, and quantum optimization, we introduce a bound-adjustment mechanism that yields valid lower and upper bounds and provides a certified stopping criterion. We show that the proposed framework generalizes classical column-and-constraint generation and retains its convergence properties when the master problem is solved exactly. Numerical experiments on two-stage robust location-transportation problems demonstrate that the proposed hybrid approach achieves solution quality comparable to classical methods while reducing the computational burden associated with solving mixed-integer master problems, highlighting the potential of hybrid quantum-classical optimization for scalable decision-making under uncertainty.

0.26

Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes

cs.ET quant-phmath.COmath.OC ·2026-10-30 ·Emanuele Casciaro, Mario De Simone, Stefano Martina, Fabio Mascherpa, Alfonso Amendola +1 more
similarity 0.58
Abstract · 12 pages, 6 figures, 1 table

With the expansion of complex transport infrastructure, new paths for linking different destinations have emerged, allowing the definition of multiple routes. The introduction of new roads may also lead to disruptions in traffic flow. This problem can be generalized into a special case of VRP, which aims to find the optimal route for a fleet of vehicles within a network of destinations. Finding solutions to this problem requires an exponential number of operations, hindering the ability of exact solvers to deal with large instances, which must therefore be tackled using heuristics, often leading to suboptimal results. Quantum-based algorithms may allow us to find exact solutions in polynomial time with high probability, offering a potential future alternative to classical solvers and in this work, we focus on the QAOA. Our novel contributions are a parameter-initialization strategy that improves the convergence probability and the integration of the subtour constraints directly into the optimization without using additional qubits by employing an approximation of exponential equality constraints. We believe that our results pave the way for effectively solving instances of VRP using quantum-based solutions, leveraging the space-efficient problem encoding and our initialization strategy, which limits the effect of barren-plateau under random parameter initialization.

0.08

On the Impact of Coordinate Descent for Multi-Angle QAOA in the Independent Set Graph Problem

eess.SP ·2026-10-01 ·Daeyeun Kim, Seungcheol Oh, Joongheon Kim
similarity 0.58
Abstract

Constrained combinatorial optimisation provides a mathematical framework for modelling a wide range of practical decision making problems, including energy network operation, financial portfolio optimisation, logistics, routing, and resource allocation. This paper studies parameter optimisation for the multi angle quantum approximate optimisation algorithm (maQAOA) applied to the maximum independent set problem, a canonical constrained graph based optimisation task. We propose a coordinate wise training framework for maQAOA that updates one variational parameter at a time by solving a sequence of one dimensional optimisation subproblems. For each selected coordinate, the method reconstructs the objective dependence on that parameter and moves directly to the parameter value that minimises the training objective, or equivalently maximises the corresponding expected solution quality. While demonstrated specifically on maQAOA, the underlying theoretical principle, that the expectation value with respect to a given parameter can be analytically expressed as a finite Fourier series, is broadly applicable to general tasks solved via parameterised quantum circuits. Empirical evaluations on connected ErdHos Renyi graph benchmarks demonstrate that this analytic approach significantly reduces the computational training cost required to reach target approximation ratios and yields superior convergence reliability compared to standard gradient based, stochastic, and derivative free baselines.

0.15

SPLIT-Q: A Scalable Sequential Quantum Computing Framework for Coherent Controlled Islanding

eess.SY quant-ph ·2026-08-13 ·Yuqi Jiang, Zhiding Liang, Qiang Guan, Yan Li, Ganesh Kumar Venayagamoorthy
similarity 0.57
Abstract

Growing integration of distributed energy resources increases power-system variability and uncertainty. During disturbances, these effects can intensify generation-load imbalances and cascading failures. Controlled islanding limits their propagation by partitioning a compromised grid into connected, electrically sustainable islands. However, classical methods face rapidly growing computational costs as network size and island count increase. Quantum optimization offers an alternative for exploring this combinatorial partition space. Yet monolithic quantum formulations encode all assignment decisions in one circuit, causing qubit demand and circuit complexity to scale with network size. In this study, a qubit-bounded sequential distributed quantum approximate optimization algorithm (QAOA) framework is proposed to tackle coherent controlled islanding under limited quantum resources. It formulates the optimization as boundary-conditioned regional quadratic unconstrained binary optimization (QUBO) subproblems that are solved sequentially within a fixed qubit budget. Thus, circuit width remains independent of network size, with aggregate quantum workload scaling linearly on bounded-degree networks. Evaluation covers eleven IEEE systems from 9 to 300 buses using IBM quantum computing resources, with Gurobi and monolithic QAOA as references. Across all systems, the framework recovers feasible Gurobi-optimal partitions under noise, confirming the resilience of its solution quality. The results further show that the proposed method substantially reduces quantum-resource demand and circuit complexity relative to monolithic QAOA, allowing large islanding problems to be addressed within current hardware limits. The proposed framework provides a feasible and scalable pathway for quantum optimization in large-scale power systems.

0.04

Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing

cs.ET quant-ph ·2026-10-14 ·Silvie Illésová, Vojtěch Novák, Martin Beseda
similarity 0.57
Abstract

Drone-delivery planning combines routing decisions with operational constraints such as payload capacity and limited onboard energy, resulting in combinatorial optimization problems that can become costly to encode directly in binary form. This work investigates a hybrid quantum--classical approach in which candidate drone missions are generated and evaluated classically before constructing a quadratic unconstrained binary optimization (QUBO) model for mission selection. Payload- and energy-infeasible missions are removed during preprocessing, while the reduced QUBO is solved using exact enumeration, simulated annealing (SA), and the Quantum Approximate Optimization Algorithm (QAOA), with mixed-integer linear programming (MILP) used as a classical reference. Experiments on controlled synthetic delivery instances evaluate solution quality, the effect of preprocessing, and computational scaling. Exact QUBO optimization reproduces the MILP optimum on the evaluated small instances, while SA achieves $100\%$ feasibility with a median optimality gap of $0\%$. Combined payload-and-energy preprocessing reduces the mean number of QUBO variables by $29.60\%$ and quadratic interactions by $49.20\%$, while reducing mean SA runtime by $31.26\%$. In contrast, the evaluated shallow statevector-based QAOA configuration achieves lower feasibility and is restricted to small QUBO instances. These results indicate that, in the considered setting, the main practical benefit of the hybrid architecture comes from classical feasibility preprocessing that reduces the binary search space before QUBO-based optimization.

0.09