CS Paper Radar

Adaptive Operator Selection in Bilevel Large Neighborhood Search for Electric Autonomous Dial-a-Ride Problem under Uncertainty

Ishara Hewa Pathiranange, Aneta Neumann

cs.NE cs.AI ·submitted 2026-10-03 02:18 UTC · v1

Abstract

The electric autonomous dial-a-ride problem (EADARP) extends the classical dial-a-ride problem by incorporating battery and charging constraints for electric vehicles. In practice, travel-time uncertainty can cause violations of time-window constraints. Large neighborhood search is effective for solving the EADARP, but its performance can depend on the choice of insertion operator during the repair phase. This paper investigates insertion-operator selection within a bilevel large neighborhood search framework for deterministic and chance-constrained variants of the EADARP. In the chance-constrained variant, arc travel times are modeled as independent normally distributed random variables, and upper time-window constraints are enforced probabilistically. We consider six selection methods, namely fixed greedy insertion, fixed regret-based insertion, random selection, a deterministic state-based rule, performance-adaptive ALNS selection, and LLM-based state-aware selection. Experimental results show comparable performance on smaller instances, while differences become more evident on larger and more constrained instances. There is no single strategy that performs best across all instances, and the relative performance of the LLM-based, rule-based, and ALNS strategies varies with the problem instance and experimental setting.

Closest papers

Nearest neighbours by meaning across the whole index.

L2R-EV: Learning What to Repair in Electric Ride-Pooling with Finite Charger Queues

cs.GT ·2026-09-30 ·Mai Pham, Vikrant S. Vaze, Peter Chin
similarity 0.62
Abstract

Electric ride-pooling must jointly manage passenger service, routes, batteries, and finite chargers; a locally useful relocation can reduce later service. We introduce a discrete-event ride-pooling simulator with ordered passenger stops, pickup and ride-time constraints, battery reserves, charger travel, and finite first-come, first-served (FCFS) charging queues. On top of a common dispatcher, we add a learned repair layer that moves uncollected passengers between vehicles, uses a supervised score to estimate later effects, and uses a two-stage proximal-policy-optimization (PPO) policy to focus computation on promising moves. Every executed move must satisfy route, battery, and time constraints and provide an immediate route-cost improvement. For larger instances, we limit the number of candidate moves and apply several non-conflicting repairs at once. On 12 held-out Manhattan episodes with 100 requests, 30 EVs, and one plug per station, supervised repair reduces operational cost by 6.57\% versus no repair (12/12 wins) and serves 74.92 rather than 72.75 requests. Two-stage PPO stays within 1.43\% of supervised repair with 95.4\% fewer exact trials, while our experiments scale to 8,000 requests and 2,400 EVs with cost reductions across all three larger development settings. Queue-aware charging reduces waiting by 41.0\%; under a declared 1.5-kW queue-idle load, operational electricity per served request falls 1.73\%.

0.19

Adaptive search with path-constrained mobile sensors using multi-arm bandits

cs.RO cs.LGmath.OC ·2026-10-29 ·Abraham P. Vinod, Parth K. Thaker, Gautam Dasarathy, Stefano Di Cairano
similarity 0.60
Abstract · 24 pages, 5 figures

We study a constrained sequential decision problem for detecting regions of interest from noisy online measurements collected by a team of energy-constrained mobile sensors. The sensor motion is restricted to a precomputed set of feasible paths that satisfy mobility constraints, limited available energy by requiring return to charging stations, and avoidance of known obstacles. We cast the resulting active path selection as a multi-armed bandit problem and propose an iterative search algorithm that adaptively assigns paths using confidence bounds computed from the collected data. We also propose a graph-based method to construct low-cardinality path covers under the team's constraints. We establish finite-time and anytime probabilistic correctness guarantees for the proposed algorithm, derive non-asymptotic upper bounds on the times required to detect all regions of interest and to label all nodes, and show that these bounds match algorithm-independent lower bounds up to constant factors for a broad class of problem instances. Using numerical simulations, we illustrate the behavior of the proposed approach and the effect of path redundancy and team size on search performance.

0.15

Distributionally Robust Chance-Constrained Reinforcement Learning for Home Energy Management under Electric Vehicle Uncertainty

eess.SY ·2026-10-18 ·Meng Yuan, Ye Wang, Yi Mei, Ramesh Rayudu, Alan Brent +2 more
similarity 0.59
Abstract

The electrification of residential energy systems and adoption of electric vehicles (EVs) create demand-side flexibility. However, random driving behaviour makes it difficult to ensure EV readiness at departure and maintain thermal comfort. To address this, we formulate residential scheduling as a distributionally robust (DR) chance-constrained Markov decision process, whose 2-Wasserstein ambiguity set guards against tail risk and distribution shift in EV behaviour. The intractable DR chance constraint is then replaced by a sufficient tightened expectation constraint under the nominal distribution. The resulting problem is solved by a Lagrangian soft actor--critic with distributional cost critics, and an online boundary guard enforces EV reachability and thermal comfort within the actuator limits at every step. Five controllers are compared over one year in Wellington, New Zealand, under a degraded forecast. The proposed controller is the cheapest controller that meets the EV target on every day and both chance constraints under forecast error and random driving behaviour. Compared with the rule-based baseline, the only other controller to do so, it lowers the annual cost by 8.6% and the comfort violation hours by 69%. The ablation study confirms that the boundary guard ensures pointwise feasibility within the actuator limits, and the DR chance constraint reduces tail risk.

0.16

A heuristic for optimal coordination of autonomous vehicles: dynamic problems

eess.SY ·2026-10-27 ·Saugat Shahi, Filippo Fabiani, Mario Zanon
similarity 0.57
Abstract

The coordination of autonomous vehicles at unsignalized intersections requires deciding both the trajectories of the vehicles and their crossing order, with the additional difficulty that the set of vehicles to be coordinated changes as traffic flows through the intersection. Since the resulting mixed-integer optimal control problem is hard to solve online, we propose an arrival-triggered receding-horizon scheme built around a schedule-refinement heuristic: for a fixed crossing order, a single nonlinear program (NLP) optimizes all trajectories and crossing times, and the first-order sensitivities of the cost with respect to the vehicle schedule are used to select adjacent swaps that are likely to reduce the overall cost. Replanning is triggered only when a new vehicle arrives, the new vehicle is appended at the tail of the current crossing order, and a memory of evaluated swaps that persists across replanning steps avoids redundant computations. Simulations of traffic scenarios involving streams of a few hundred heterogeneous vehicles show that the proposed scheme recovers most of the optimality gap incurred by first-in-first-out scheduling.

0.52

Bisect-Index-Choose: A Fast and Exact Algorithm for EV Charging under Minimum Charging Rates

eess.SY ·2026-11-07 ·Can Berk Saner
similarity 0.56
Abstract · 10 pages, 6 figures. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after w…

Electric vehicle (EV) charging stations are increasingly operated with an aggregate power limit below the sum of their port ratings, and require scheduling algorithms to divide the available power among the connected EVs. Charging standards permit a current that is either zero or at least a minimum rate, typically 6 A, which makes this allocation problem non-convex. Existing methods either solve a mixed-integer program with a commercial solver, which can be computationally expensive, adds software dependencies, and incurs licensing costs, or apply heuristics without optimality guarantees. This paper proposes Bisect-Index-Choose (BIC), a fast and solver-free scheduling algorithm that computes a globally optimal allocation among EVs under mild assumptions on their utilities. For $n$ EVs, BIC runs in $O(n \log n)$ time when all EVs share one maximum rate and in $O(n^2)$ time for two, times a logarithmic factor in the numerical precision. In tests with up to 1000 EVs, BIC attains global optimality and is up to three orders of magnitude faster than the solver. On real-world charging data, it needs less capacity and delivers more energy than existing heuristics. We implement BIC on a low-cost microcontroller and show that it solves instances with 1000 EVs in less than 90 ms.

0.30

A Hybrid Exact-Heuristic Solver for the Integrated Passenger and Parcel Transportation Problem

cs.AI ·2026-11-17 ·The Dung Bui, Ha Thu Nguyen
similarity 0.56
Abstract · 4 pages, 2 figures, 3 tables. Technical Report for the SOICT 2026 Student Contest

We describe the solver we submitted to the second round of the SOICT 2026 contest on the Integrated Passenger and Parcel Transportation problem, a selective pickup-and-delivery routing problem with time windows, open routes and heterogeneous taxis. The solver is a single-file, standard-library Python program that combines (i) a constant-time insertion test based on latest-arrival slack, (ii) greedy insertion, local search and an Adaptive Large Neighborhood Search (ALNS) with simulated-annealing acceptance, and (iii) an exact route-selection engine that enumerates, for every taxi, the best feasible route for each request set and then solves the resulting set-packing problem by branch-and-bound strengthened with route-based large neighborhood search, Lagrangian bounds and reduced-cost fixing. The engine is chosen automatically from the instance size, and an independent verifier and a watchdog guarantee that a valid answer is always printed. On the official evaluation (38 scored instances, 5-minute limit) the solver obtained a total benefit of 487,237, finished every run within 277 s and used at most 279 MB; 28 of the 38 instances terminated well before the limit.

0.25

Joint pricing and matching for dynamic high-capacity ride-sharing considering passengers' choice uncertainty

eess.SY ·2026-08-23 ·Wang Chen, Xinglu Liu, Kaihang Zhang, Hongzheng Shi, Jintao Ke
similarity 0.55
Abstract

This work investigates the uncertainty-aware joint pricing and matching problem for dynamic high-capacity ride-sharing services, where passengers are assumed to be price-elastic and decide whether to accept a ride-sharing offer based on the upfront prices provided by the platform. We formulate the studied problem as a two-stage stochastic program, where the first stage optimizes upfront price decisions for passengers, and the second-stage recourse problem captures passenger-vehicle assignment based on passengers' uncertain choices. To enhance computational efficiency, we introduce a novel relaxation-based gradient descent-guided search algorithm that leverages the problem's structural properties. Initially, the algorithm generates a feasible solution for the first-stage problem via relaxation. It then iteratively improves the solution via a search process guided by the derived gradient information. In particular, scenario reduction is applied to eliminate unnecessary scenarios when calculating the gradient, thereby reducing the overall computational burden. Numerical experiments demonstrate that, compared to solving the stochastic program directly, the proposed algorithm can accelerate computation speed by thousands of times while achieving optimality gaps of no more than 1.1%. Finally, we validate the benefits of considering passengers' choice uncertainty through large-scale simulation using real-world datasets and road networks over two large cities. The results demonstrate that, on average, the proposed method can increase the revenue by 5.2% and the service rate by 8.2% compared to the baseline approaches. This study provides a valuable reference for transportation network companies to design pricing strategies for ride-sharing to enhance service efficiency and improve revenue.

0.34

Tight Approximations for Fixed-Order Vehicle Routing with Stochastic Demands

cs.DS ·2026-10-12 ·Jingyang Zhao, Mingyu Xiao
similarity 0.55
Abstract

We study the vehicle routing problem (VRP) with stochastic demands, where each client has an independent demand with a known distribution, and its realized demand is observed only on the first visit. We consider a priori and restocking policies that fix the client order before observing demands and serve each client's entire demand before first visiting the next. Gupta, Nagarajan, and Ravi (Oper. Res., 2012) developed randomized a priori $(α+1)$-approximation and $(α+2)$-approximation algorithms for splittable and unsplittable deliveries, respectively, where $α$ is the approximation ratio of a metric traveling salesman problem (TSP) algorithm. We improve these approximation ratios to $2$ and $3$ by using their replenishment rules with a TSP tour constructed via matroid parity. We also obtain deterministic a priori $(2+\varepsilon)$-approximation and $(3+\varepsilon)$-approximation algorithms by compressing the distributions of cumulative demands to select an initial stock in polynomial time. All guarantees are relative to the general adaptive optimum. We then establish matching lower bounds of $2$ and $3$ that hold even for the more general class of randomized restocking policies. Finally, we apply our matroid-parity construction to improve approximation ratios for several VRP variants with deterministic demands.

0.35