A heuristic for optimal coordination of autonomous vehicles: static problems

I. INTRODUCTION

• Mixed-integer formulations optimize order and trajectories jointly, but their binary-variable count grows combinatorially; fixed-order approaches leave part of achievable performance unexplored.Rule-based and reservation-based heuristics can overlook vehicle dynamics and heterogeneous costs.Source: §I · p. 1
• The proposed coordination scheme uses motion-planning sensitivity information to refine crossing order, retaining candidate swaps only when they reduce cost.For a fixed order, one NLP optimizes vehicle trajectories and entry and exit times; the higher-level heuristic uses precedence-constraint multipliers.Source: §I · p. 1

Notation:

• A schedule S is a permutation of the vehicle indices, and M and N denote the number of vehicles and time steps, respectively.The notation also distinguishes entry and exit quantities with the placeholder †.Source: Notation · p. 1

II. PROBLEM FORMULATION

• The problem seeks an optimal crossing schedule and corresponding vehicle trajectories, assuming predefined paths and no lane changes.The formulation separates a fixed-schedule NLP from schedule selection; optimizing over schedules makes the overall problem a MINLP that is typically prohibitive in real time unless M is very small.Source: §II · p. 2

III. SCHEDULE-REFINING HEURISTIC

• FIFO orders vehicles by arrival time absent the others, while a quadratic mixed-integer approximation offers another schedule-selection baseline but remains combinatorial.FIFO is computationally inexpensive but can perform poorly when vehicle costs differ.Source: §III · pp. 2–3
• Precedence-constraint multipliers estimate the first-order sensitivity of optimal cost, so the heuristic tries the adjacent swap associated with the largest multiplier and checks whether cost actually falls.Because the sensitivity is local, each proposed swap must be evaluated rather than assumed to improve the solution.Source: §III · p. 3
• The heuristic starts from an initial schedule, solves the NLP, selects an admissible adjacent pair, and retains its swap only when the updated cost is lower.The algorithm bounds swap attempts with Kmax; the variants greedily target pairs with the largest expected cost impact, reducing computational burden at the risk of suboptimal solutions.Source: §III · p. 3
• Heuristic 1 freezes attempted swaps, whereas Heuristic 2 allows rejected adjacent pairs to be revisited after a swap is accepted.Heuristic 1 is motivated by the expectation that repeating an accepted or rejected pair is unlikely to improve the result; the variants differ in how they update the admissible swap set.Source: §III · pp. 3–4

IV. BASELINES FOR COMPARISON

• For the simulations, the authors propose two alternative problem formulations as comparison baselines to evaluate both the efficiency and effectiveness of Algorithm 1.Source: §IV · p. 4
• In its simulations, the study proposes two alternative problem formulations as baselines for comparison, with the stated aim of evaluating Algorithm 1’s efficiency and effectiveness.Source: §IV · p. 4
• The heuristic's NLP formulation is assessed alongside MINLP and MIQP baselines.The passage identifies the comparison setup, without reporting comparative results.Source: §IV · p. 4

• For each entry or exit time, k† is defined as the largest sample index whose sampling time does not exceed that event time.Source: A. MINLP formulation (5) · p. 4
• The event position is obtained by integrating vehicle dynamics from the state at the sampled index and applying the input at that index.Source: A. MINLP formulation (5) · p. 4
• The formulation introduces a one-hot binary variable to express the position constraint explicitly.Source: A. MINLP formulation (5) · p. 4
• MINLP (14) minimizes J(x, u) over vehicle states, inputs, event times, schedule S, and binary variables b.Source: A. MINLP formulation (5) · p. 4

• Discretizing the event times in (14c) is proposed as a simplification that turns the MINLP into an MIQP.Source: B. MIQP formulation · p. 4
• The formulation assumes linear vehicle dynamics, making equality and path constraints affine while position constraints remain nonconvex.Source: B. MIQP formulation · p. 4
• One-hot binary variables select the sampling time immediately following each entry or exit event, and the preceding sample is recovered by shifting the index.Source: B. MIQP formulation · p. 4
• The resulting formulation is a relaxation of the original problem and can produce infeasible solutions.Source: B. MIQP formulation · p. 4

• The evaluation compares the proposed coordination framework based on NLP (6) with MINLP (14) and MIQP (21) for solution performance and computational efficiency.Source: §V · p. 5

• The NLP formulations and reordering strategy are implemented in CasADi, using IPOPT and WORHP for NLP and Gurobi for MIQP and MINLP.Source: A. Simulation setup · p. 5
• Vehicle classes use different weights for acceleration and braking effort and for velocity-tracking error.Larger r_i discourages aggressive control, while larger q_i enforces tighter tracking of reference speed.Source: A. Simulation setup · p. 5
• Scenarios use 3, 6, 9, or 12 vehicles, with initial positions and velocities varied to represent heterogeneous traffic conditions.Source: A. Simulation setup · p. 5
• The compared scheduling strategies include FIFO ordering by unobstructed entry time and the swapping-based order-refinement heuristic.Source: A. Simulation setup · p. 5
• NLP solvers IPOPT and WORHP are fastest with a fixed schedule; MIQP is orders of magnitude slower than NLP, while MINLP is extremely slow.All solvers except MIQP produce the same cost, with deviations below 0.001% of the MINLP solution in the 9- and 12-vehicle scenarios.Source: A. Simulation setup · p. 5

B. Swapping-based heuristic

• For six vehicles, both heuristics’ swap attempts and corresponding cost progression are illustrated, with successful and failed attempts distinguished.The sequence and cost progression are shown for Heuristic 1 and Heuristic 2; the 9-vehicle case is also illustrated.Source: B. Swapping-based heuristic · p. 5
• Both NLP solvers return the same final reordering and cost across five 6-vehicle instances, but IPOPT is faster computationally.The same solver trend is reported for the 9-vehicle case.Source: B. Swapping-based heuristic · p. 5

C. Comparing swapping heuristics, brute force, and FIFO

• Both heuristics return the same final crossing order and cost across the scenarios, but Heuristic 1 requires fewer swap evaluations and NLP solves.Heuristic 1’s restricted search space, controlled by α, prevents revisiting evaluated pairs and yields fewer evaluations across all scenarios.Source: C. Comparing swapping heuristics,… · p. 6, Figure 6 · p. 7
• Brute-force search evaluates all admissible vehicle orders to provide a global optimum, but its M! schedules make exhaustive enumeration intractable at moderate problem sizes.The evaluation compares the proposed reordering strategy with brute force and FIFO across 100 six-vehicle scenarios.Source: C. Comparing swapping heuristics,… · pp. 5–6
• The heuristic consistently reduces cost versus FIFO and follows the brute-force optimal trend in most six-vehicle scenarios.Figure 7 compares costs normalized by the brute-force optimum.Source: C. Comparing swapping heuristics,… · p. 7
• 77.4% is the average optimality-gap reduction relative to FIFO, while the heuristic’s average optimality gap against brute force is 41.8%.Figure 8 reports both metrics; the 41.8% average gap indicates a tradeoff between solution quality and computational efficiency.Source: C. Comparing swapping heuristics,… · p. 7

D. 12-Vehicle scenario: Scalability analysis

• Brute-force comparison is unavailable at 12 vehicles because 12! = 479,001,600 admissible schedules make enumeration computationally infeasible.FIFO is the sole reference baseline at this problem size.Source: D. 12-Vehicle scenario: Scalability… · p. 7
• 53.5% is the average cost reduction relative to FIFO across 100 randomized 12-vehicle scenarios, with individual reductions from roughly 9% to nearly 88%.The cost reductions are broadly spread across the scenarios rather than confined to favorable instances.Source: Figure 9 · p. 8, D. 12-Vehicle scenario: Scalability… · p. 8
• Heuristic 1 uses approximately 20 to 25 swap evaluations per scenario, compared with 55 to 105 for Heuristic 2.Heuristic 1 avoids revisiting previously evaluated pairs, producing a non-redundant search.Source: D. 12-Vehicle scenario: Scalability… · p. 8, Figure 10 · p. 8
• Without a global-optimum reference, the 12-vehicle evidence supports reductions over FIFO and fast search, not quantified optimality gaps.The authors characterize the framework as scaling favorably as scheduling complexity grows.Source: D. 12-Vehicle scenario: Scalability… · pp. 8–9

E. Comparison against rule-based and reservation-based heuristics

• 51.2% average cost reduction versus FIFO; the heuristic had the lowest cost in all 100 scenarios, while right-of-way and reservation baselines cost approximately 2.7× and 6× FIFO, respectively.The baselines target throughput and collision avoidance rather than the heterogeneous objective used for comparison.Source: E. Comparison against rule-based and… · p. 9

VI. CONCLUSION

• The framework formulates coordination as an NLP and refines crossing orders through targeted swaps using KKT sensitivity information, avoiding exhaustive enumeration or combinatorial optimization.The conclusion identifies Lagrange multipliers as the source of the sensitivity information.Source: §VI · p. 9
• Simulations report lower computational time than mixed-integer formulations and brute-force search, comparable cost minimization, and improved crossing order over FIFO; runtime is not yet real-time compatible.The current schedule is recomputed from scratch for a fixed vehicle set, and every candidate swap requires a full NLP solve.Source: §VI · p. 9, E. Comparison against rule-based and… · p. 9
• Future work proposes incremental schedule updates as vehicles arrive and reducing swap-evaluation cost to execute reordering within the sampling time.Other directions include robustness to model uncertainty, multi-intersection coordination, and learning-based components.Source: §VI · p. 9