Autonomous Vehicle Public Transportation System: Scheduling and Admission Control

I. INTRODUCTION

• The system jointly addresses economical AV scheduling for admissible requests and admission control to maximize revenue across point-to-point ridesharing services.A control center coordinates vehicles and service requests so vehicles follow assigned travel plans.Source: §I · p. 1
• The paper proposes an AV public transportation system and improves prior scheduling formulation to support both directed and undirected graphs.It also develops distributed scheduling and introduces admissibility with related analytical results.Source: §I · p. 1
• The paper formulates admission control and develops a genetic-algorithm-based method to solve it.The introduction also identifies real-world transportation service data as the validation basis.Source: §I · p. 1

II. RELATED WORK

• Prior AV research mainly addressed control and communication, whereas this paper focuses on coordinating AVs for public transportation services.Vehicular communications can connect AVs with a control center.Source: §I · p. 1, §II · p. 2
• Prior taxi ridesharing studies reported benefits, including 25% more taxi users served with 13% less total travel distance in Beijing, while this paper emphasizes AVs’ direct controllability.The cited comparison is from T-Share; the authors note that human-driven taxis may not fully follow control-center instructions.Source: §II · p. 2
• Unlike the cited Dial-A-Ride Problem formulation, this scheduling model can revise assigned but unserved requests as vehicles move through the system.The paper also proposes distributed scheduling for its fleet.Source: §II · p. 3
• The paper adapts admission control to transportation requests, seeking maximum total profit, and adopts a genetic algorithm for its problem formulation.Earlier examples cited for genetic-algorithm admission control are in communication systems and.Source: §II · p. 3

1) Network Structure:

• A directed road graph models locations and road connections, with edge costs and travel times that may be asymmetric.Costs typically represent distance; refuel locations can represent charging stations for electric vehicles.Source: 1) Network Structure · p. 3

2) Transportation Requests:

• Each request specifies pickup and dropoff locations, a maximum ride time, a service-start window, and the number of seats needed.The maximum ride time marks the threshold beyond which the customer would be dissatisfied.Source: 2) Transportation Requests · p. 3

3) Vehicles:

• Each AV is described by its next location, time to reach it, remaining operating time, passenger capacity, and previously assigned requests.Previously assigned requests distinguish those already being served from those assigned but not yet implemented.Source: 3) Vehicles · p. 3

B. Operations

• The control center collects requests and vehicle status, then admits outstanding requests and schedules the admitted ones during each duty-assignment interval.Unadmitted requests are reserved for reconsideration in the next interval; invalid requests are permanently excluded.Source: B. Operations · p. 4

1) Complete route specification:

• AVs must follow specified routes, have enough fuel to complete them, and end at a refuel station after serving their assigned requests.At pickup, the vehicle must have enough free seats; pickup time and actual ride time must also meet each request’s limits.Source: 1) Complete route specification · p. 4, 2) Time constraints · p. 4

IV. SCHEDULING

• Scheduling determines AV-request assignments, routes, and arrival times, assuming all scheduled requests are admissible and will be served.Admission control determines which requests are admissible.Source: §IV · p. 4

A. Preprocessing

• Preprocessing replaces the full road graph with shortest-path links among schedule-relevant locations, reducing variables and allowing greater route flexibility.With intermediate vertices omitted, an AV can adjust its path between specified locations to respond to traffic incidents without changing the original schedule.Source: A. Preprocessing · p. 5
• Preprocessing can be skipped when the scheduling problem on the full graph is solved efficiently; otherwise, shortest-path results can be precomputed and looked up.The paper describes the resulting preprocessing time cost as negligible.Source: A. Preprocessing · p. 5

B. Problem Formulation

• The objective minimizes total operational cost, measured by total distance traveled.The formulation uses assignment, route, arrival-time, and passenger-occupancy variables.Source: B. Problem Formulation · p. 5
• Flow constraints define each AV’s path from its start location to a refuel station and require assigned vehicles to pass through request pickup and dropoff locations.A served request must meet its ride-time limit and pickup time window, while passenger occupancy must satisfy vehicle capacity.Source: B. Problem Formulation · p. 6
• The model can revise previously assigned requests: in-service requests restart at the AV’s current location, while unserved requests may be reallocated to lower-cost vehicles.In-service requests retain their seat requirements, while their remaining ride-time limit is shortened by elapsed time.Source: B. Problem Formulation · p. 6
• The scheduling problem is a mixed-integer linear program (MILP), and positive edge costs ensure that a schedule serving no requests is not a solution.Because admission control removes invalid requests, the MILP is feasible and all requests passed to it must be served.Source: B. Problem Formulation · p. 7

C. Complete Schedule Construction

• The selected assignment variables identify which AV serves each request, while the route variables define its path through the reduced graph.The reduced-graph path is expanded into a complete route using the precomputed shortest paths between adjacent locations.Source: C. Complete Schedule Construction · p. 7
• Arrival times are assigned along each selected path by adding edge travel times, while pickup locations must meet request time windows.When several arrival times are feasible, choosing the earliest one preserves flexibility for later scheduling intervals.Source: C. Complete Schedule Construction · p. 7
• Passenger occupancy is reconstructed at pickup and dropoff locations by adding or subtracting the request’s required seats.The resulting vehicle paths and schedules provide instructions for completing assigned services.Source: C. Complete Schedule Construction · p. 7

• The section studies how traffic congestion and passenger no-shows affect admission control and scheduling.Source: §V · p. 7

A. Problem Formulation

• Admission control must screen requests for both feasibility and positive net profit because scheduling determines their induced costs.A single inappropriate request can make scheduling infeasible; the system therefore seeks a feasible admitted set that maximizes profit.Source: A. Problem Formulation · p. 7
• The bilevel formulation has an upper level choose requests to maximize total profit and a lower level schedule them at minimum cost.The levels depend on each other: request selection requires the scheduling result, while scheduling requires the selected requests.Source: A. Problem Formulation · p. 8
• Because the discrete bilevel problem is difficult for classical methods, the authors choose a genetic-algorithm-based approach.Source: A. Problem Formulation · p. 8
• Any subset of an admissible request set remains admissible; a non-admissible singleton makes every superset non-admissible, while disjoint vehicle fleets can serve the union of admissible sets.Source: A. Problem Formulation · p. 8
• The admission problem always has a feasible solution with non-negative profit because it can reject all newly received requests.Previously admitted requests were selected with non-negative profit.Source: A. Problem Formulation · p. 8
• An admissible superset of requests cannot be less profitable than its admissible subset.The paper derives this from the non-negative profit available for the additional requests.Source: A. Problem Formulation · p. 8

B. Variations

• The proposed admission-control and scheduling mechanisms remain applicable under congestion and passenger no-shows, with minor arrangements for handling them.Source: B. Variations · pp. 8–9

1) Traffic Congestion:

• Travel times are assumed nearly constant within each operating interval; intervals should shorten as travel times change faster and lengthen when changes are slower.For updated travel times, unused edges need no action, unserved requests can be rescheduled, and active trips may be handled by avoiding the edge or compensating passengers.Source: 1) Traffic Congestion · p. 9

2) No-show of Passengers:

• When some passengers do not show, the AV schedule stays unchanged and freed seats can serve later requests; when all are absent, allocated resources are released after pickup time.The paper also notes that penalty policies may discourage no-shows.Source: 2) No-show of Passengers · p. 9

VI. GENETIC-ALGORITHM-BASED SOLUTION METHOD

• The solution method adopts a genetic-algorithm framework whose components draw on the paper’s analytical results for the admission-control problem.Source: §VI · p. 9

A. Working Principle of Evolutionary Algorithms

• Evolutionary algorithms iteratively generate and evaluate candidate-solution populations, and can be used without requiring convexity or differentiability.The paper adopts the established genetic-algorithm framework to seek good practical solutions to the bilevel problem.Source: A. Working Principle of Evolutionary… · p. 9

B. Distributed Scheduling

• With request assignments fixed, solving each vehicle’s scheduling subproblem is equivalent to solving the original scheduling problem.Source: B. Distributed Scheduling · p. 10
• The distributed subproblems can run on separate computing units, including the AVs, while avoiding repeated solves of the exponentially growing joint scheduling model.If an AV loses communication with the control center, its subproblem can be delegated to an available control-center or cloud computing unit.Source: B. Distributed Scheduling · pp. 9–10

C. Algorithmic Components

• A GA generates candidate admission-control solutions through operations inspired by natural evolution, including selection, crossover, and mutation.The lower-level scheduling optimization is handled by a standard MILP method; the GA handles the upper-level optimization.Source: C. Algorithmic Components · p. 10, 1) Chromosome · p. 10

1) Chromosome:

• Each chromosome encodes request acceptance in a binary vector and vehicle assignments in a companion vector.The vehicle assignment κ_r applies when request r is accepted (z_r = 1).Source: 1) Chromosome · p. 10
• Including vehicle assignments in the chromosome enables distributed scheduling and is intended to save computation time.The paper notes that assignments could instead be determined in the original scheduling formulation.Source: 1) Chromosome · p. 10

2) Fitness Evaluation:

• Each vehicle solves its assigned scheduling subproblem, and the control center sums the returned costs to compute chromosome fitness.The process groups requests by assigned vehicle, sends each group to its vehicle, and returns scheduling costs to the control center.Source: 2) Fitness Evaluation · p. 11
• Distributed scheduling can reduce computation time because vehicles solve their scheduling subproblems simultaneously.Scheduling is identified as the algorithm’s most computationally demanding component.Source: 2) Fitness Evaluation · p. 11
• Only assigned requests and computed scheduling costs need to pass between the control center and vehicles during each evaluation.The passage says the system does not require a sophisticated communication system for these requirements.Source: 2) Fitness Evaluation · p. 11

3) Tabu List:

• A request-specific tabu list excludes vehicles that cannot serve that request, since adding requests cannot make an inadmissible assignment admissible.The lists are constructed during initialization and used in initial population generation and mutation.Source: 3) Tabu List · p. 11
• A fraction of the population survives each generation, and weighted random pairing selects survivors for crossover.The surviving fraction is Xrate of Npop; the remaining chromosomes are replaced by crossover offspring.Source: 4) Selection · p. 11

5) Crossover:

• Crossover combines parent request and vehicle assignments so offspring may admit more requests and achieve higher fitness.The design uses inherited parent assignments for requests not admitted by an offspring’s parent.Source: 5) Crossover · p. 11

6) Mutation:

• Mutation diversifies the search while preserving the highest-fitness chromosome from mutation.A 0-to-1 request change assigns a vehicle outside that request’s tabu list; a 1-to-0 change clears its assignment.Source: 6) Mutation · pp. 11–12

D. Algorithmic Design

• The algorithm has initialization, iterative search, and a final stage that outputs the best solution found.Feasible candidate solutions are maintained throughout the search.Source: D. Algorithmic Design · p. 12, 3) Final Stage · p. 12

1) Initialization:

• Initialization constructs request-specific tabu lists and creates feasible chromosomes by pairing a random request with a vehicle outside its tabu list.The initial chromosomes’ fitness is evaluated before iterations begin.Source: 1) Initialization · p. 12

2) Iterations:

• Each iteration backs up feasible solutions, applies selection, crossover, and mutation, then restores a backup if a modified chromosome is infeasible.One stated stopping criterion is reaching a specified number of generations.Source: 2) Iterations · p. 12

3) Final Stage:

• The final stage outputs the best solution found during the search.Source: 3) Final Stage · p. 12

VII. PERFORMANCE EVALUATION

• Simulations use 100 sampled Boston taxi trips and test scheduling time, admission-control performance, and profit during continuous operation.The trips come from City of Boston service data; the setup adapts their times, ride durations, seat occupancy, and fares for the proposed system.Source: §VII · p. 12

A. Computation Time for Scheduling

• Distributed scheduling time remained approximately steady as vehicle count changed, while centralized time grew exponentially with request count and cumulative time increased more slowly.Centralized scheduling took 8.30 s, 69.25 s, and 6.72 × 10^3 s for 3–5 requests, respectively; the authors recommend distributed scheduling when vehicles have sufficient communication and computation capabilities, and cumulative scheduling otherwise.Source: A. Computation Time for Scheduling · pp. 12–14, Figure 6 · p. 13, Figure 5 · p. 13

B. Admission Control in an Operating Interval

• Across Cases I–IX, the genetic algorithm rapidly converged to the global optimum in a few generations, with slightly more generations needed as problem size increased.The results average 20 runs per case and report diminishing error-bar gaps over 40 generations.Source: B. Admission Control in an Operating… · p. 14, Figure 7 · p. 15
• Profit increased with vehicle availability, but 20 AVs yielded only a 1–2% increase over 5 AVs in the tested cases.Cases I, IV, and VII are shown; profits across different cases are not directly comparable because they depend on request and vehicle parameters.Source: B. Admission Control in an Operating… · p. 14, Figure 8 · p. 14

C. Admission Control in Consecutive Operating Intervals

• Case 2 produced more cumulative profit by admitting more requests; the authors recommend shorter operating intervals, which also limit submitted requests and computation time.Fig. 9 compares cumulative profit over intervals with Case 1 intervals twice as long as Case 2 intervals; Fig. 10 tracks admitted requests.Source: Figure 9 · p. 14, Figure 10 · p. 14, C. Admission Control in Consecutive… · p. 15

VIII. CONCLUSION

• The paper formulates scheduling as an MILP, admission control as bilevel optimization, and reports validating its solution method with real-world transportation-service data.Its listed contributions also include distributed scheduling, admissibility analysis, and a genetic-algorithm-based admission-control method.Source: §VIII · pp. 15–16