Source-linked AI summary
RideSkill: A Hierarchical Algorithm for Generalized Ride Sharing with LLM-Driven Automatic Evolution
Zijian Zhao, Sen Li, Xialiang Tong, Mingxuan Yuan
TL;DR
Ride-sharing dispatch must bundle differing OD requests under changing scenarios, objectives, and large-scale constraints, while existing MARL and LLM-based approaches have limited adaptability or real-time practicality. RideSkill uses an LLM-evolved hierarchy of reusable skills, adaptive skill selection, and sequential repositioning, with offline-trained policies that require no deployment-time LLM calls. Across evaluated tasks and scenarios, it achieves the best reported performance and adapts correspondingly to different tasks.
Problem
Ride-sharing requires efficient OD-pair bundling under varying conditions, while existing MARL and LLM-based methods face generalization, scalability, or inference-time deployment limitations.
Method
RideSkill combines an LLM-evolved skill repository, a combiner that selects vehicle-specific dispatch skills, and a sequential repositioner trained offline through automatic evolution.
Results
RideSkill achieves the best performance across all evaluated tasks and adapts correspondingly to different tasks and scenarios.
Takeaways & Limitations
Offline-trained RideSkill policies support adaptive ride-sharing deployment without LLM calls during operation.
Takeaways & Limitations
The rescaling mechanism is heuristic, lacks theoretical guarantees, and is optional.
Abstract
from arXiv · showhide
Ride-sharing, which allows multiple passengers with different origin-destination (OD) pairs to share a single vehicle, is a challenging operational problem, as it requires orders with different OD pairs to be efficiently bundled and assigned to vehicles under uncertain and varying scenarios. Although multi-agent reinforcement learning (MARL) solutions have achieved promising performance, they suffer from limited generalization (adapting to different environmental scenarios), low transferability (adapting to different platform objectives), and training difficulties in large-scale systems, such as the curse of dimensionality. Recently, motivated by the scaling of large language models (LLMs), several works have incorporated LLMs into ride-hailing systems, either by employing LLMs directly as decision-making agents or using them for automatic algorithm design. However, none of these approaches support vehicle sharing, which complicates the problem by expanding both the state and action spaces exponentially. Moreover, most of them require frequent LLM calls at inference time, making them infeasible for real-time deployment. To address these issues, we propose RideSkill, a hierarchical method for ride-sharing that leverages LLM-assisted automatic algorithmic design. RideSkill consists of a combiner that assigns appropriate skills to each vehicle from a learned skill repository, enabling adaptive dispatch under varying scenarios and objectives, and a repositioner that sequentially relocates idle vehicles to emerging regions, avoiding conflicts among vehicles. Crucially, the skill repository, combiner, and repositioner are all trained by an LLM-based automatic evolutionary method, eliminating the need for LLM calls during deployment and thus ensuring high real-time performance.
1 INTRODUCTION
Ride-sharing can improve urban transportation efficiency and passenger access, but generalized dispatch remains difficult at scale and under changing conditions. RideSkill addresses these challenges with hierarchical, LLM-evolved components that operate without inference-time LLM calls.
- Ride-sharing increases vehicle occupancy, reduces trips, and can lower congestion and carbon emissions while improving passenger convenience.It can also help platforms serve more demand with limited fleets through lower fares and shorter waiting times.
- Classical and rule-based dispatch methods are efficient but myopic, whereas MARL faces dimensionality challenges as vehicles and orders scale.
- LLM-based ride-hailing approaches require frequent inference-time calls, making them unsuitable for real-time ride-sharing latency requirements.
- RideSkill combines a reusable skill repository, adaptive vehicle-level skill assignment, and sequential idle-vehicle repositioning for varying scenarios and objectives.Its components are trained offline through an LLM-assisted evolutionary procedure and run without LLM calls after training.
2 PROBLEM SETUP
The platform must dispatch shared-ride requests while accounting for vehicle, order, temporal, spatial, capacity, and future-demand relationships. Because fleet, demand, traffic, and objectives vary, the paper seeks adaptation across tasks without policy reconstruction or retraining.
- The centralized platform makes dispatch decisions every ∆t time units for requests arriving at arbitrary times.
- Dispatching must account for OD and temporal relationships, vehicle-order spatial relationships, remaining capacity, and potential future orders.
- The ride-sharing problem is formulated as a Multi-Agent Markov Decision Process with vehicles represented as agents.
- Fleet size, order volume, traffic conditions, and platform objectives can vary, requiring adaptation across tasks without policy reconstruction or retraining.
3 METHODOLOGY
RideSkill uses a hierarchy of reusable skills, adaptive per-vehicle combination, bipartite matching, and sequential repositioning to handle varying ride-sharing conditions and objectives. An LLM-based evolutionary process trains these components offline, including self-checking, task variation, and relative fitness evaluation.
- Skill Repository and Combiner: RideSkill combines a repository of reusable ride-sharing skills with a combiner that selects skill mixtures for each vehicle under current conditions and objectives.The repository includes skills such as nearest matching, detour minimization, and service-rate maximization.
- LLM-Assisted Evolutionary Training: An LLM-based (µ+λ)-ES authors, validates, evolves, and de-duplicates skills while training the combiner and repositioner across varied tasks, with self-check feedback and relative fitness.The pipeline uses task generation for generalization and transferability, and self-checking to detect mismatches between designed intent and measured behavior.
- Skill Repository and Combiner: Each skill scores vehicle-order pairs from vehicle observations, candidate orders, and episode-static and live step contexts, rather than directly outputting assignments.This score-based formulation addresses the large joint action space of ride-sharing dispatch.
- Skill Repository and Combiner: The resulting pair scores are converted into dispatch decisions through an integer-linear-program bipartite matching problem that limits each order and vehicle to one new assignment per step.A dummy order represents the option for a vehicle to wait, while capacity constraints exclude infeasible assignments.
- Skill Repository and Combiner: The combiner normalizes scores across each skill’s feasible candidate set before blending them, preventing skills with larger numerical ranges from overwhelming other signals.An optional income-based budget can boost below-average vehicles and damp above-average vehicles, but this heuristic has no theoretical guarantees.
- Repositioner: The repositioner sequentially assigns idle vehicles to demand regions, decrementing effective demand after each assignment to reduce conflicts and prevent vehicles from flocking to one hotspot.Its fitness is the same-task, same-seed return improvement over the reposition-off baseline, so positive values directly measure repositioning gains.
4 EXPERIMENTS
Experiments use Manhattan ride-hailing data and compare RideSkill with model-based, MARL-based, and LLM-based baselines across varied operating conditions. RideSkill achieves the best overall performance across scenarios and metrics, including conditions beyond MARL training ranges.
- Experimental setup: Experiments use real-world Manhattan ride-hailing data in the RideGym simulator, with separate training, validation, and testing periods.Training covers April 6–12, 2026; validation and testing use April 13–14, 2026.
- Baselines: The evaluation compares model-based, MARL-based, and LLM-based dispatch methods, including nearest matching, KM, GS, REDA, BMG-Q, MFRL, and LLM baselines.
- Main results: RideSkill achieves the best performance across varied hours, fleet sizes, speeds, capacities, and nearly all reported metrics.Its detour time is substantially lower than competing approaches, indicating efficient order bundling.
- Generalization: MARL baselines fail when vehicle capacity exceeds their training range, whereas RideSkill significantly outperforms rule-based and LLM-based baselines in those cases.
- Ablations: RideSkill outperforms its no-repositioner variant, while both variants substantially outperform the single-skill baseline.These ablations evaluate the repositioner and combiner modules separately.
5 CONCLUSION
RideSkill is presented as an LLM-evolved ride-sharing algorithm designed to adapt across operational scenarios and objectives. On a real-world Manhattan dataset, it achieves the best performance across evaluated tasks and adapts correspondingly to different tasks.
- RideSkill is presented as the first ride-sharing algorithm trained through LLM-based evolution and designed to adapt to varying objectives and operational scenarios.
- The framework combines a skill repository, an objective- and scenario-conditioned combiner, and a sequential repositioner balancing demand and idle vehicles.
- Experiments on a real-world Manhattan ride-hailing dataset show the best performance across all evaluated tasks, with corresponding task adaptation.
ETHICS STATEMENT
The paper states its adherence to the ICLR Code of Ethics. The supplied related-work passages describe ride-sharing dispatch as a bundling and matching problem addressed by optimization and learned methods.
- The paper states that it adheres to the principles outlined in the ICLR Code of Ethics.
- Ride-sharing dispatch requires bundling multiple overlapping orders onto shared-capacity vehicles.
- Learned dispatch methods commonly decompose large joint actions across vehicles under multi-agent formulations.
A.2 LLMS FOR RIDE HAILING
LLM-based ride-hailing methods use language models either for direct dispatch or automatic algorithm design, but their deployment scalability differs. RideSkill is positioned as a ride-sharing method that adapts across scenarios and objectives.
- LLM-based dispatch: LLM dispatch methods either make per-vehicle decisions, perform global matching, or generate overall dispatch plans.Per-vehicle and global-matching approaches require frequent inference calls, while overall-plan generation faces large input and output spaces.
- Automatic algorithm design: Offline LLM-assisted algorithm design eliminates runtime model calls but prior work targets ride-hailing without vehicle sharing.Zhang et al. combine LLM generation with evolutionary search and evaluate open-loop and close-loop variants.
- RideSkill: RideSkill is described as the first LLM-based ride-sharing solution and the first ride-sharing approach adapting to varying scenarios and objectives.
- Terminology: The notation distinguishes scenarios, objectives, tasks, and policies used to describe the paper’s problem and solutions.A scenario specifies environmental configuration; an objective is a reward function; a task pairs one scenario with one objective; and a policy is a complete dispatch solution.
C METHOD IMPLEMENTATION
RideSkill’s implementation evolves objective-specialist skills and an objective-reading combiner through constrained LLM-generated code and evolutionary search. Its design emphasizes distinct decision-rule mechanisms, self-authored skill fitness, and reward-aware skill selection.
- Phase 1: skill evolution: Phase 1 evolves one objective-specialist scoring function at a time using a fixed metric menu and diversity-oriented mechanism menu.The system supplies descriptions of existing skills and requires a genuinely different decision-rule shape to encourage repository diversity.
- Output contract: The implementation specifies exact output fields for skill proposals, including the objective, self-check, mechanism, differences, description, fitness code, rationale, and dispatch code.
- Fitness design: Each skill’s fitness is a cheap pure function of the fixed metrics dictionary and remains frozen throughout its evolutionary search.Fitness functions cannot use rollouts, environments, randomness, imports, or LLM calls.
- Skill design constraints: Skill proposals must declare one objective axis, explain coverage, and use a behaviorally distinct mechanism rather than merely new weights.Allowed shapes include gates, threshold switches, lexicographic rules, marginal scores, opportunity cost, patience, and nonlinear saturation.
- Phase 2: combiner evolution: Phase 2 evolves a combiner that scores frozen skills for each vehicle according to an unseen episode objective.The combiner uses synthetic probe events to infer coefficients of the objective’s per-step reward vector.
D.1 TRAINING CONFIGURATIONS
The training and comparison setup combines evolutionary search with task-diverse evaluation and benchmarks RideSkill against heuristic, MARL, and LLM-based alternatives. The closest prior automatic-design baseline removes runtime calls only in its open-loop form and does not support vehicle sharing.
- Training configuration: All three training phases share a (µ+λ)-ES with group-relative fitness, while phase-specific hyperparameters are summarized separately.
- Comparative baselines: The baselines span nearest matching, Kuhn-Munkres, Gale-Shapley, REDA, BMG-Q, MFRL, and LLM-based dispatch methods.The model-based methods use matching or proximity rules, while the MARL baselines use independent or neighborhood-based value estimation.
- Phase 1: Phase 1 initializes handwritten skills, generates LLM proposals, validates them in a sandbox, evolves variants, deduplicates champions, and self-checks intent alignment.
- Phase 2: Phase 2 evolves a frozen-skill combiner over sampled task distributions and retains reward-family elites for cross-task selection.The combiner is required to pass probe-coverage checks and is selected through group evaluation, fresh-batch rerolls, and a final runoff.
- LLM baseline: Zhang et al. is the closest prior work in spirit, combining LLM generation with evolutionary search for ride-hailing without vehicle sharing.Its open-loop variant runs without intermediate deployment calls, whereas the close-loop variant reinvokes the LLM during deployment.
D.3 EVALUATION METRICS
The evaluation records a common metric set from raw episode logs and reports scenario-level means with standard deviations unless otherwise stated. Runtime dispatch combines skill blending, matching, fairness budgets, and sequential repositioning, while repositioner evolution evaluates efficiency–fairness trade-offs.
- Reporting convention: Evaluation metrics are computed from raw episode logs and generally reported as mean ± standard deviation across evaluation scenarios.The scenarios vary by windows, fleets, or axis levels depending on the experiment.
- Dispatch metrics: The metric set includes reward, service rate, completion rate, wait time, ride time, detour time, utilization, and empty driving.Service rate counts assigned orders, completion rate counts delivered orders, and completion rate is no greater than service rate.
- Phase 3: repositioner evolution: Phase 3 evolves a repositioner using reposition-on versus reposition-off return deltas across task and fairness-strength cells.Selection reserves elites by objective family and fairness-strength band and reports objective- and fairness-blindness diagnostics.
- Runtime dispatch: Runtime dispatch selects and blends positive skills, solves vehicle-order matching with a no-op option, and sequentially repositions idle unmatched vehicles.A shared regional state is decremented after each relocation so later vehicles account for demand already claimed by earlier vehicles.
- Fairness metrics: Fairness evaluation reports fleet-level dispersion measures such as Orders Std, Served Std, Dist. Std, and W-Dist Std, with lower values indicating greater equity.
D.4 OBJECTIVE RESPONSE
RideSkill adapts its policy to changing platform objectives without retraining, using either mathematical reward functions or natural-language objectives. Sweeping reward coefficients and testing objective-conditioned policies shows targeted metric changes and comparable performance between natural-language and mathematical detour objectives.
- Objective adaptation: RideSkill adapts its policy to different objectives without retraining, unlike fixed policies from previous approaches.Evaluation points use five held-out test windows and the same metric set as Table 1.
- Coefficient sweeps: Increasing detour-time or pickup-time coefficients decreases the corresponding detour and wait-time metrics.Increasing the service-time coefficient also reduces detour and pickup times while increasing ride time, with little change in average ride time and a slight service-rate increase.
- Given objectives: Mathematical objectives reduce their corresponding pickup-time or detour-time metrics as expected.These evaluations compare objective-aware and objective-blind versions of the same stack on identical test windows.
- Natural-language objectives: Serving long-trip orders increases ride time by 1.74 minutes and detour time by 1.45 minutes under a natural-language objective.The remaining 0.19-minute difference is attributed to policy adjustments, while the detour increase reflects the prevalence of short-distance orders along routes.
- Natural-language objectives: A natural-language objective to minimize detour time achieves performance comparable to its mathematically specified counterpart.The result indicates that the policy interprets the natural-language objective without an equivalent mathematical reward supplied directly.
D.5 FAIRNESS
RideSkill evaluates the efficiency–fairness tradeoff by varying fairness strength across multiple scenarios. Its fairness-related skills and repositioner improve equity, while the explicit fairness budget is most effective when repositioning is unavailable.
- Fairness outcomes: RideSkill achieves overall better fairness than the compared baselines and MARL agents.The authors attribute this result to fairness-related skills included in the skill repository.
- Fairness budget: Increasing fairness strength ρ reduces per-vehicle metric deviations without significantly affecting overall performance when repositioning is disabled.The experiment sweeps ρ from 0, meaning disabled, to 1.0.
- Repositioning: The fairness budget is less effective with repositioning active because the repositioner already directly improves fairness metrics.It relocates idle vehicles, typically lower-income vehicles, toward high-demand regions to balance supply and demand.
- Evaluation protocol: Fairness is measured using per-vehicle standard deviations, with lower values indicating greater equity.Table 6 reports these statistics alongside performance metrics as mean±std across five scenarios.
D.6 EVALUATION ON OPEN-SOURCE LLM
The open-source-LLM evaluation replaces Claude Opus 4.8 with GLM-5.1 in the full evolutionary pipeline and reports lower performance for GLM-5.1 across scenarios. The examples illustrate objective-conditioned skills, combiner routing, and repositioning logic generated through the pipeline.
- Open-source LLM evaluation: GLM-5.1, with 67B parameters, underperforms Claude Opus 4.8, with 309B parameters, across all evaluated scenarios.The comparison uses the five-axis generalization sweep and three stacks: single-skill average, RideSkill without repositories, and RideSkill.
- Generated artifacts: The example artifacts include generated code and natural-language cards describing each artifact’s objective, mechanism, and expected behavior.These outputs are presented for all three training phases.
- Generated skills: The generated near-short-efficiency skill applies a hard completability gate before ranking feasible trips by productive-time efficiency.Its stated mechanism also uses OD-region re-demand and a region-aware no-op option.
- Combiner: The combiner routes vehicle states to specialists according to dominant objective coefficients while protecting deadline-pressed vehicles first.Idle vehicles can be routed toward completion, seating, length, volume, or broad-coverage specialists; loaded vehicles receive objective-specific weights.
- Vehicle-state handling: Deadline-pressed vehicles receive en-route and slack-budget skills regardless of the current objective.The implementation identifies this state when minimum onboard slack is at most 0.7 times mean solo time.
- Repositioner: The repositioner scores destinations using objective-weighted demand, supply, travel cost, and structural OD demand signals.Its target shifts toward drop-off or seat-rich regions for completion and pooling objectives and toward nearby raw demand for throughput.