CS Paper Radar

Optimal Seat Movement Strategies Among Modular Bus Units

Shiyue Wang, Yuhao Liu, Zhibin Chen, Mingyang Pei, Changhong Lu

cs.CE math.OC ·submitted 2026-11-12 06:15 UTC · v1

Abstract

Movable seats enable passengers to transfer between coupled modular bus units while remaining seated, but require physical reconfiguration that existing modular transit models largely abstract away. We model seat reconfiguration as a colored generalized sliding-tile puzzle on the physical track graph, capturing simultaneous movements, seat indistinguishability within destination groups, and vertex, edge, and corner-following conflicts. A lexicographic objective minimizes makespan first and then the sum of costs (SoC), which penalizes movements and waiting at non-target positions. We develop an exact time-expanded mixed-integer linear programming formulation and a Boundary-Sequence Dynamic Programming (BSDP) algorithm. BSDP decomposes the problem at single-edge module interfaces and coordinates local schedules through compressed boundary-crossing sequences, provably preserving feasibility and optimal costs. On two- and three-module benchmarks, BSDP achieves mean per-instance speedups of 3.24x and 6.30x over Gurobi, respectively. In fixed-horizon tests with four to seven modules, both methods start from identical greedy schedules and receive a 300 s budget. BSDP obtains lower final SoC than Gurobi on 197 of 200 instances and ties on three, reducing mean final SoC by 17.93%-69.07% across the four size classes. Geometry sensitivity and ablation studies further clarify the contribution of boundary compression to computational performance. The framework links seat reconfiguration to the timing and operational cost of modular bus decoupling.

Closest papers

Nearest neighbours by meaning across the whole index.

MeshSIPP: Efficient Lattice Planning in Dynamic Environment

cs.AI cs.RO ·2026-10-07 ·Marat Agranovskiy, Konstantin Yakovlev
benchmarktheory similarity 0.60
Abstract

Autonomous navigation in dynamic environments requires computing spatiotemporal trajectories that satisfy non-holonomic motion constraints. When the trajectories of the moving obstacles are predictable or known, a promising approach is to rely on the combination of state lattices constructed from precomputed feasible motion primitives and Safe Interval Path Planning -- a search-based algorithm with strong theoretical guarantees. While this approach yields feasible paths, the rich primitive sets needed for smooth navigation induce a large branching factor, which becomes costly when coupled with time-dependent obstacle intervals. To this end, we present MeshSIPP, an efficient planner that removes the computational bottleneck by exploiting the fact that many primitives sweep the same regions and can therefore be validated together. MeshSIPP propagates primitives as spatial bundles, screens them with lightweight bounding-interval checks, and defers the expensive exact departure-time search until a primitive reaches its terminal state. A time-aware pruning rule additionally discards redundant space-time branches early in the search. We prove that the resulting search is complete and optimal. Extensive experiments over more than 6,000 benchmark instances and real-time ROS~2 simulations show that MeshSIPP achieves up to a 3$\times$ speedup over state-of-the-art spatiotemporal planners.

0.18

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

cs.AI ·2026-11-17 ·The Dung Bui, Ha Thu Nguyen
code/data similarity 0.60
Abstract · 5 pages, 1 figure, 2 tables. Technical Report for the SOICT 2026 Student Contest. Code: https://github.com/25023189-bit/Integrated-Passenger…

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.34

Class-Based Heuristic Selection for Solving the Flying Block Puzzle

cs.AI ·2026-08-20 ·Sanyar Ahmadi, Pedram Asadzadeh, Amanj Khorramian
benchmark similarity 0.58
Abstract · 27 pages, 15 figures, 2 tables

Heuristic search underlies planning in autonomous systems ranging from warehouse logistics to robotic navigation, yet generic heuristics fail to exploit the structural constraints that govern constrained spatial domains, causing search performance to degrade catastrophically on harder instances. We study this problem through the two-column Flying Block Puzzle, a rigorously NP-complete spatial planning microworld whose bottleneck geometry mirrors clearance-to-size constraints encountered in multi-agent path finding, autonomous vehicle navigation, and block relocation systems. We introduce the Class-Based Heuristic A* (CBHA*) algorithm, which integrates a General Move Constraint to capture minimum displacement costs when vacant units are scarce, a formal kinematic taxonomy partitioning the state space into seven mutually exclusive classes with provably admissible heuristics based on vacancy ratio and goal-piece geometry, and a class-conditional tie-breaking mechanism that dynamically switches between depth-priority and vertical-distance ordering to overcome f-value plateaus. Over 146 benchmark instances, CBHA* achieves a 93.4% success rate against 64% for Depth-Prioritized A*, 39% for Standard A*, and 17% for BFS, while reducing node expansions by 87.98% relative to Standard A* and sustaining an average effective branching factor of approximately 3, demonstrating that class-triggered adaptive heuristics constitute a principled mechanism for efficient spatial planning that generalizes structurally to physical constraint systems.

0.40

Energy- and Time-Efficient Multi-Vehicle Trajectory Planning Using Augmented DAG Search in Configuration Space

eess.SY ·2026-11-10 ·Amirreza Akbari, Galina Sidorenko, Johan Thunberg
similarity 0.57
Abstract · This manuscript is currently under review at IEEE Transactions on Intelligent Transportation Systems

Multi-vehicle trajectory planning for CAV requires balancing energy consumption and travel time while ensuring safety and scalability. While travel-time-optimal methods based on Integer Programming exhibit poor scalability in large-scale multi-vehicle scenarios, existing energy-oriented approaches fail to balance energy consumption and travel time. We extend a configuration-space framework for multi-vehicle trajectory planning to jointly locally optimize travel time and energy consumption. A weighted energy-travel time objective is combined with an efficient augmented DAG search on two-dimensional decompositions of a high-dimensional configuration space, enabling scalable and collision-free coordination of large numbers of vehicles. Although the proposed framework is applicable to other traffic scenarios, such as roundabouts and vehicle-following, we focus on intersections as a representative and challenging planning problem. To further improve performance for our methodology, we also extend the method with an insertion-ordering heuristic that exploits reduced-space geometric information. Combined with nonlinear model predictive control, the proposed framework is shown to scale to 40 vehicles, outperform MILP-based and convex optimization baselines in dense intersections, and reduce energy consumption at equalized travel times relative to time-optimal planning.

0.23

Multi-Agent Path Planning via Compatible Encounter-Space Allocation in Crowded Spaces Dynamically Occupied by Work Activities

cs.CE ·2026-10-13 ·Boda Liu, Xuezhi Yang, Bin Yang, Shu Li
published similarity 0.57
Abstract · 81 pages; full English and Chinese versions are included, with the English version first. Planning to submit to IEEE Transactions on Robotic…

Lifelong multiagent path planning on construction floors must accommodate continually changing goals and work occupancy. Existing planners can update paths and timing online, but work motion space coupling changes the spatial basis of unfinished encounters, while rerouting affects later encounters. Planning must therefore construct and maintain local encounter possibility. We propose Width based Planning with Compatible Encounter Space Allocation (WP), which constructs shared passage relationships from actual encounter demands and real time widths. Shared channels, ordered anchors, and urgency based updates coordinate successive encounters while retaining individual greedy motion between them. A necessary and sufficient width condition for fixed-point position exchange and a necessary directional condition for composite exchange provide geometric grounds for channel construction and encounter relocation. In crowded floor computational experiments, WP maintained route continuation after occupancy changes and enabled multi agent clearing, with infrequent, brief near stops. Complete run comparisons with four methods showed 25.2% to 52.2% more mean goal arrivals than the best baseline at each configuration of 5 to 10 agents, with lower mean computation time than the rolling horizon K_CBS adaptation. The contribution is a planning principle that constructs and continuously maintains local passage relationships from real time space, unifying shared spatial allocation and conditional local clearing to extend lifelong planning to work motion space coupling.

0.37

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

A Two-Echelon Covering Tour Vehicle Routing Problem with Drones for Post-Disaster Relief

cs.RO ·2026-09-28 ·Dang Viet Anh Nguyen, Rajesh Piplani, Aldy Gunawan
benchmark similarity 0.57
Abstract

We introduce the two-echelon covering tour vehicle routing problem (2E-CTVRP) for the distribution of relief supplies after a disaster. In the first echelon, a fleet of trucks transports supplies and drones from a central depot to satellites at the periphery of the affected area. In the second echelon, drones launched in parallel from the satellites deliver the supplies to the centroids of victim clusters, which are obtained by clustering the victim locations, and each truck waits at a satellite until its drones have returned. The problem combines the assignment of satellites to trucks, the sequencing of the truck routes, and the assignment of clusters to satellites, and minimizes the sum of the arrival times of the trucks at the satellites and at the depot. We formulate the 2E-CTVRP as a mixed integer linear program and propose a hybrid metaheuristic, GRASP-ILS-PR, which combines greedy randomized construction, a single-trajectory search, and periodic path relinking on the assignment of clusters to satellites. On a new benchmark set of 110 instances, GRASP-ILS-PR finds all known optimal solutions within 30 seconds, matches or improves on the one-hour solutions of a commercial solver on most larger instances, and improves on them by up to 11% for instances with 50 satellites. It clearly outperforms a conventional GRASP with evolutionary path relinking and yields more consistent results than a simulated annealing algorithm that uses the same search components. An analysis of two fleet configurations shows that few large trucks minimize the cumulative arrival time in most instances, whereas many small trucks deliver supplies to the victims earlier and more equitably in every instance.

0.24

A polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in fixed dimension

cs.DS math.CO ·2026-11-11 ·Daniel Skachkov, Yuriy Dorn
similarity 0.56
Abstract

In the Traveling Salesman Problem, a route must visit all customers and return to its starting point while minimizing its total length. The Minimum Latency Problem, also known as the Traveling Repairman Problem, instead minimizes the sum of the times at which customers are first visited. We give a deterministic polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in every fixed dimension, with arbitrary nonnegative customer weights. Our proof restricts the form of a solution in three steps, each with a controlled increase in cost. First, a decomposition based on Sitters' method assigns customers to phases that start and end at the root. Second, within each phase, we divide the route into a constant number of blocks and charge each customer at the end of its assigned block. The resulting objective is a nonnegative linear combination of block lengths. Third, we add an auxiliary dimension and use a fixed Minkowski norm to close each block path into a tour. Arora's closed-tour estimate then gives paths that cross the boundaries of a common dissection only at designated portals and a bounded number of times per face. A dynamic program optimizes the restricted objective, and projecting its paths back to the original space gives the final route. Rounding weights and coordinates keeps the state space polynomial.

0.30