We develop an incentive scheme for a hub-toshuttle campus transit system, encouraging riders to shift travel times to improve system efficiency. Riders are modeled as agents with loss functions in order to evaluate social welfare in the incentive scheme. Incentives are calculated based on a predictive wait-time model trained via Gaussian process regression. Experiments show that the system's total loss decreases, but the average wait time increases. This leads to the conclusion that there is room for improvement in the predictive wait time model.
In most public transportation systems, particularly bus
systems, uneven ridership leads to an inefficient use of resources.
There are geographic areas and times within a traffic system
that require different resources, but in a bus system the same
vehicles travel the same routes throughout the day. The goal
of the RITMO project [M
The RITMO project aims to improve the bus system at the University of Michigan, by using this hub-to-shuttle system to address uneven ridership. Figure 1 shows the uneven demand across the campus bus system map. The idea of the hub-to-shuttle system is to connect the populous green areas with buses, and to use shuttles to drive riders in the sparse blue areas. It would be inefficient to have a single shuttle service all blue areas on the map, therefore the serviceable area is broken into zones, which can be seen in Figure 2. A shuttle will not leave its assigned zone, but rather pickup and deliver riders from hubs whom wish to travel in multiple zones.
Along with some physical routes getting significantly more attention, some temporal routes getting greater traffic volume causes problems with inefficiency. While it is inevitable that there will be uneven ridership throughout the day in a transit system, this paper addresses the problems created by the same amount of resources being deployed throughout the day by developing a solution to spread out traffic. Wait times are assumed to be important to riders and thus a useful tool to convince them to move to spread traffic. In this paper we define a wait time to be the time difference between when a rider requests to be picked up and when she actually boards her first vehicle. However, in a stochastic transit system like RITMO, wait times cannot be computed directly at the time the system would offer an incentive. In this paper, an incentive is defined as an arbitrary point system that can easily be expanded to a real quantity. For example, on the Michigan campus meal points can be allocated to students that alter their requests times. We specifically use incentives, rather than tolls, because the RITMO system is for a free campus bus system. Our goal is to spread riders out over time to reduce the cost of the system and lower wait times to increase efficiency and social welfare. Social welfare is the aggregate loss of riders in the system, plus the cost of providing incentives to riders.
The main contribution of this paper is the creation of an agent-based incentive scheme which utilizes a learned predictive wait time model. The incentive schemes aims to incentivize riders entering the system to change their departure time by small intervals. This helps alleviate the number of riders at a time, while not reducing the satisfaction of riders, because they still reach their destination on time. The incentive scheme models the riders as agents, then uses loss functions for the system and agents, and the expected wait time to calculate an incentive for each agent to change her trip starting time, or board time. The incentive model then decides if an agent should be offered an incentive based on if the system deems it socially optimal for the agent to move her travel time. The incentive model is judged by its effects on the system’s cost and social welfare.
The creation of a learned predictive wait-time model partnered with an agent-based incentive model has previously not been used in transportation pricing. When we first created the incentive model and did not have a good wait time predictor, then agents changed their board times to time intervals that potentially increased their wait times, which decreased the satisfaction of riders and increased costs to the system. As the predicted wait time became more accurate the satisfaction and cost of system improved. Therefore, the design of the predictive wait time model became integral to the success of the incentive model. Developing a predictive wait time model is not straightforward in the RITMO problem space because the shuttles’ paths are volatile. Our predictive wait time model uses Gaussian Process Regression [Pedregosa et al., 2011, Rasmussen, 2004] to find expected wait times for agents before their trips are scheduled, based on current traffic information. We evaluate the wait-time model on the accuracy of its predictions, and whether it helps reduce the average wait times in the system. 2
This work is part of the RITMO project, a hub-and-shuttle
public transportation project initiated by Pascal V
Literature on dynamic transportation pricing mostly
involves finding optimal prices for lanes or roads to reach an
equilibrium for drivers [Sharon et al., 2017,
Literature on pricing ride sharing systems strongly
considers surge pricing, or pricing during peak travel time
Studies using machine learning to predict the wait time for
public transportation riders mainly focus on arrival of buses
on their predetermined route
To reduce the number of riders entering the system at high traffic times, an incentive model aims to incentivize some riders to change their requested board times by small time intervals. A rider enters the RITMO system by providing a request to the scheduler on an app interface. Without an incentive model, a scheduler immediately processes a riders requests by finding a trip for the rider, which is illustrated in Figure 3. Scheduling the requested trip is necessarily beneficial to other riders in the system, so we introduce an incentive model to attempt to increase the social welfare of the system by lowering the aggregate loss of the riders. Figure 4 illustrates the process of how a scheduler uses the incentive model to handle a rider’s request. This request contains a rider’s desired trip information, which inform the scheduler how much the rider values different aspects of the trip, for instance any aversion about early arrival at destination. After receiving a request, the scheduler decides whether or not to provide an incentive to convince the rider to change her board time. This decision is based on expected wait times for the rider and similar riders. If the scheduler decides not to offer an incentive, then the original request processes by scheduling the trip. If the scheduler offers an incentive, then the rider decides if she wants to take the incentive and change her board time, or reject the incentive and keep her original board time. Once the rider makes her decision, the scheduler respects the decision and continues with processing the request.
Given the information in a request, we model the riders as agents with loss functions. An agent’s loss increases as wait time increases, and decreases with the addition of an incentive. Though every time an agent takes an incentive, the system endures the cost of that incentive. The entire system is better off when the agents’ losses in aggregate are lower. Therefore, the total loss of this system is calculated by the sum of agent loss plus the incentive costs. This total loss can be thought of as the negative of social welfare, because the agents on average are better off with a lower system loss. An individual agent’s assumed goal is to minimize her own loss. The goal of the scheduler is to maximize social welfare by minimizing the total loss of the system. 3.1
An agent wishes to minimize her own loss and to reach her destination. The scheduler wants to minimize the net-loss of the system and get all agents to their desired destinations. The scheduler breaks a day into t-minute time intervals as a way to measure congestion at different points. Both the agents and scheduler are aware of traffic in the market.
An agent, xi, initiates an interaction by sending a request with public and private parameters. We assume the scheduler has full information from agent xi’s request, that is, the request the scheduler receives reflects all private information. Given the request, the scheduler decides if the agent should be offered an incentive i to move the agent’s board time by t. We calculate the incentive with agent xi’s private loss function, using values in xi’s request. Once the scheduler finds i, it looks at congestion and a threshold for incentives. Congestion is determined by the effects of an agent on the average wait time at different time intervals.
If the scheduler determines that i should be given to xi then it returns her proposal consisting of i and a new board time. If the scheduler does not think that an incentive should be offered to xi, then it continues on with scheduling xi’s ride. If the agent is offered an incentive, then she considers her potential loss with the proposed board time and her original requested board time. The agent chooses the board time that minimizes her loss. Since the scheduler knows the private parameters of the agent, it can choose an incentive that it knows will be sufficient to convince an agent to agree to a time-shift. The scheduler updates agent xi’s request and continues with scheduling her ride.
Agents’ requests consist of a set of public and private parameters that the scheduler uses to assign routes and incentives. The public parameters within an agent’s request are a trip ID (i.e., an identifier for agent xi 2 X where X is the set of all agents), the requested board time lower bound ri, the pickup stop, and the delivery stop. The private parameters are her willingness to leave early i, willingness to leave late i, and malleability to incentives i, which determines how much xi appraises an incentive in proportion to how the system values it. Her wait time is the difference between her requested board time lower bound and her actual pickup time.
Agents have a loss function to evaluate a ride. The elements of this loss function consist of the travel time, and the effects of changing the request time if the agent chooses to change her board time lower bound. The travel time is broken down into the wait time and the time an agent spends on the actual trip. We assume agents want lower wait times. Therefore the wait time is beneficial in calculating an incentive. We assume that loss increases if the agent does not leave at her intended time, but an incentive counteracts this by decreasing loss.
Agent xi’s loss function is formally defined as: La(xi) = (pi) + i(ri pi)Ie + i(pi ri)I` i i: (1) The parameters are revealed to the scheduler in xi’s request. pi is a board time lower bound proposed to agent xi by the scheduler, where pi 2 fri t; ri; ri + tg. (pi) is the trip time at pi, where trip time is calculated by the time from pi to when the agent completes her trip. Ie and I` are indicator functions where Ie = 1 when ri > pi and Ie = 0 otherwise, i.e. when the proposal time is earlier than the request time, and I` = 1 when ri < pi and I` = 0 otherwise.
The scheduler and agents cannot know exact travel times until all rides are assigned trips, so the estimated agent loss is found by: L^a(xi) = E[ (pi)]+ i(ri pi)Ie+ i(pi ri)I` i i: (2) The expected trip time, E[ (pi)] = E[w(pi)] + E[vi]. E[w(pi)] is the predictive wait time model’s estimate at pi, and E[vi] is an optimization of the minimum trip distance. The calculation of the estimated wait time is discussed in section 4.
The system also endures a loss from each agent and the incentive it pays her. Therefore, the system’s loss is defined as the aggregate agents loss, plus the cost of the incentives. Since the system appraises the incentive at the its true value, the system’s loss from a rider is defined as:
Ls(xi) = La(xi) + i: (3) The scheduler uses an estimate of (3) to assess the effect an agent will have on the system, because the agent’s trip is not scheduled when it uses the loss to calculate an incentive. Thus, it must use the predictive wait time model to calculate the expected travel time. The estimation the scheduler uses:
L^s(xi) = L^a(xi) + i;
After the termination of the simulation, we evaluate the system by summing agent loss (3),
L = X i=1
Ls(xi):
Assuming the scheduler knows each agent’s private parameters, it can find L^a(xi); 8i, and use this to minimize the system’s loss. We find the minimum incentive for xi by solving: E[ (ri)] is the estimate loss of at ri. We solve for i in (6): (7) If the scheduler offers i found in (7), then agent xi is guaranteed to do as well as her original request time. However, it is most likely suboptimal to move all agents, so the scheduler decides which agents to incentivize the impact on other agents with similar requests. If the scheduler determines moving xi to have a positive affect on other agents, then i is offered to xi, in exchange for xi to change her request time to pi.
Once the scheduler calculates an agent’s required incentive, it must decide whether to offer this incentive to the agent. The scheduler’s goal is to maximize social welfare, so it offers xi an incentive if moving xi positively affects the other agents in aggregate. We determine this using the wait-time estimator to find the wait time with and without the agent at the requested time and time intervals around it. We assume that an agent affects only those requesting trips at the same stop and time interval. Therefore, we calculate the average estimated wait time of the original time interval and the intervals around it. To find the socially optimal option, we find the average estimated wait when xi is in each time interval. Whichever provides the lowest average wait time is the interval the scheduler incentivizes agent xi to move her request time. This decision is illustrated in Figure 5. We assume lower average wait time leads to a socially better outcome, because more agents with requests similar to xi will be better off since a lower average wait time yields a lower average loss.
An agent’s goal is to minimize her own personal loss. Therefore, she will take an incentive if her overall loss lowers when she moves her request time to the proposed time. How she makes this decision is illustrated in Figure 6. An agent does not particularly care about if she enters at rush hour or not, but rather if she has a low wait time and reaches her destination on time. Choosing the board time lower bound with the lowest loss assures that she achieves these goals. (4) (5) (6) We also explore the impacts on the incentive model when agents try to manipulate the system. Agent manipulation defines an agent attempting to lower her own loss by giving the scheduler an untruthful board time lower bound. Before an agent submits her request, she is assumed to have full knowledge of the system and can determine if she would be incentivized to change an untruthful request time to her true desired time. This decision happens before a request is sent, and how it fits into the incentive model is shown in Figure 7, and details of her decision are illustrated in Figure 8. A manipulative agent is only untruthful about her requested board time, and the other parameters in her request are truthful. The scheduler is unaware that an agent is untruthful, and assumes that the distribution of traffic throughout the system remains the same as if all agents were truthful. The incentive model is evaluated on its impacts on social welfare. Our goal is to minimize the system loss (5). This equation is the sum of the agents’ loss and the incentives provided to them. Therefore, in minimizing this equation, we also minimize the agents’ loss, while not providing unaffordable incentives. Minimizing the agents’ loss should result in maximizing the social welfare. The baseline for total system cost is the value of (5) when no incentive scheme is used with the model. 4
The goal of the incentive scheme is to convince an agent to alter her request before the actual trip takes place. To determine an incentive to provide the agent, the scheduler uses (7). Thus at the creation time of the request, the scheduler needs to know the wait time at the requested board time.
Finding the wait time at a future time step is nontrivial because the state of the system can change. In the interim, other agents may enter and alter a shuttle’s path, potentially affecting the predicted route of an agent at her creation time. Shuttles may also leave and enter the system in a stochastic manner. 4.1
We estimate wait times using a model trained with Gaussian process regression (GPR). GPR generates a nonlinear and nonparametric model to predict output values. It works by measuring the distance between points using a kernel function, and constructing predictions based on a distance-based weighting of those points. The training is governed by a set of hyper-parameters [Rasmussen, 2004].
We chose GPR for its superior performance using the features available in the stochastic RITMO system. GPR training requires time cubic in samples, which limited the size of training sets we could employ in experiments. We use a radial basis kernel function, k(x; x0) = cexp( 21` (x x0)2), with white noise. We assume that small changes in features causes only small changes in a wait time, which makes the smoothing quality of the radial basis kernel ideal. All of the features are standardized during training, and data is split between testing and training sets. 4.2
All of the selected features are independent of an agent’s private variables and pertain to the current state of riders, vehicles, and stop network: number of agents expected to request board times in the same zone and time interval; distance of the predicted closest vehicle; whether requested board stop is a hub; whether the agent’s pickup and drop-off stops are in different zones; whether the agent is at a hub and changing zones (i.e., waiting for a bus rather than shuttle). 4.3
The training loop begins by running the incentive model once to generate features and wait times used to train the predictive wait time model. The training loop and final model selection is illustrated in Figure 9. Once data is collected from this initial simulation run, it is split into testing and training data. The training data is used to train the Gaussian process regression model. The trained model’s generated parameters are plugged into the simulation, and used to calculate the expected wait time on future runs. Next, the simulation runs again with a smaller proportion of agents offered incentives. This proportion is determined by offering incentives only to agents that the scheduler is sure with benefit the system. The scheduler determines which agents will benefit other agents more by altering their requests in Section 3.2. Then the same data extraction and training process are repeated. The data is extracted and trained until are desired proportions are tested. After this training loop completes, all wait time models are used on the incentive model when either the corresponding proportion of agents are offered incentives, or no agents are offered incentives. The chosen final model is the combination of the predictive wait time and incentive models that yields the lowest total system loss, L, found by (5). 4.4
The predictive wait time model is evaluated on the accuracy of its expected wait times and its effects on the actual wait time. The model is therefore evaluated by its success in lowering aggregate wait times. The baseline for this comparison is the system with no incentive scheme.
We use a RITMO dataset provided by the RITMO project in our experiments. This dataset represents bus traffic on the University of Michigan campus. University bus drivers manually recorded the number of riders that boarded a bus at each stop three different months, which then was turned into a representative distribution of agent requests. There are also sets of shuttles, buses, and stops to create the University of Michigan RITMO system.
To model loss, we added personal preference data randomly to each agent. These preferences are not meant to be a realistic model, but rather reasonable values for evaluation. Using uniform distributions, we generated preferences, i; i; U [0; 0:1] and i U [0:5; 1:5], which specify, respectively, willingness to travel early and late, and how the rider values an incentive proportionally to the system. We also perturbed the baseline request set to test the incentive and predictive wait time models on different traffic spreads on the Michigan campus. Specifically, we added noise U [ 20; 20] minutes to each rider’s request-creation time and requested board time. 5.2
We consider the RITMO and perturbed datasets, which contain 37,724 rider requests in the University of Michigan bus system. This dataset takes place over a 22 hour period. The system is split into three zones, with between 17 and 31 shuttles in each zone. There are four bus lines with a total of 17 buses.
For both the incentive and predictive wait time models, we vary the proportion of agents offered incentives to determine if this affects the total loss and average wait time. We do this by only offering agents whom the scheduler is more convinced will benefit the system by moving. This is determined by setting a limit on the change in predicted average wait time, and the scheduler will only offer incentives to agents that it is more convinced will benefit the other agents around them. We then evaluate the system by the total loss and average wait time at the different proportion of agents offered incentives.
In the incentive model we test all non-manipulative agents, and all manipulative agents. We train the predictive wait time model on a set of 1,000 requests. Each experiment is run with 10 different random seeds to produce 95% confidence intervals on the following graphs. Lastly, the baseline is defined as the total loss or wait time of the system when no incentives are offered. The incentive model is evaluated by the total system loss for non-manipulative and manipulative agents. The goal is to lower these from their initial baseline values. The results of the total system loss with the predictive wait time model on the RITMO and perturbed data are presented in Figures 10 and 11, respectively.
Figure 10 shows for non-manipulative and manipulative agents the total system loss initially decreases by an insignificant amount from the baseline value, depicted by the black line, then dramatically increases. The difference in proportion of agents offered incentives is determined by a threshold placed on the certainty of the scheduler that moving an agent will benefit the system. Therefore, when more agents are offered incentives, there is a lower threshold on the certainty of the scheduler, and the maximum proportion in Figure 10 occurs when any agent may potentially benefit the system by moving. The result that the loss increases as more agents are offered incentives demonstrates an inaccuracy in the system, because ideally the scheduler should not be offering that many agents, if any at all, incentives that would cause the total loss to increase. This is mainly an issue because the goal of the system is to lower the loss of the agents in aggregate, a goal which is clearly not being achieved. The loss slightly increases when agents are manipulative, but not by a significant amount compared to non-manipulative agents.
Figure 11 shows the total loss of the perturbed data set. The perturbed data yields a similar result to RITMO data, but when a lower proportion of agents are offered incentives the total loss lowers by a significant amount. One more thing to note is that the confidence intervals are tighter on the perturbed data compared to the RITMO data, and there is less variation between the cases with and without manipulation. This is most likely caused by the method of perturbation making the traffic spread more stable and have slightly lower peaks at high traffic times. The predictive wait time model is evaluated by the average wait time at the end of the simulation. The results of the average wait time for the RITMO and perturbed data are shown in Figures 12 and 13, respectively.
Figure 12 shows the average wait for the RITMO data and training sets of non-manipulative and manipulative agents. This shows the exact same pattern as Figure 10, demonstrating that the loss and average wait times are directly related. This allows us to conclude that the inaccuracies with the scheduler’s decision that an agent will benefit the system are from problems with the predictive wait time model. If the predictive wait time model accurately calculated expected wait times for agents, then the average wait time would lower when agents took incentives, and as a result the total loss would lower as well. It also shows that the incentive model is behaving how we would expect because there is a direct relationship between the average wait and total loss. Therefore, we can come to the conclusion that to improve the entire model, we need to improve the predictive wait time model.
The average wait time of the perturbed data is shown in Figure 13. Like the RITMO data, the average wait time shows a similar pattern as the total loss. While the increase in wait time as the proportion of agents that take an incentive increases is similar, the average wait time is always lower when agents take incentives. This shows that the predictive wait time model works better on the perturbed data, which is most likely a result of the stabilization of the perturbed data discussed in the previous section. Therefore there is potential in the incentive scheme and predictive wait time model, but we should proceed in attempting to improve the predicted wait time model for all datasets. 6
We developed an incentive scheme for the RITMO transit system with a predictive wait-time model. The incentive model aims to minimize system loss and improve social welfare, which is defined as the aggregate loss of agents in the system. In experiments with non-manipulative agents, the total system loss is successfully lowered compared to the loss in an unincentivized model. However, the average wait time is consistently higher for all incentive schemes. Therefore, the predictive wait time model can be improved.
The main contributions of this work are the creation of the agent-based incentive model and learned predictive wait model. Using learned wait times to calculate incentives for agents in a stochastic system is an innovative idea because riders in a transportation system value their time, and thus want lower wait times. This idea could expanded to a useful tool for dynamic pricing in any stochastic road network.
One potential way to improve the predictive wait time model is to look at traffic at an individual stop, rather than the entire zone. We could also switch from Gaussian process regression to a deep neural network, which could better estimate the unknown, underlying structure of the RITMO system. Given the relationship in experiments between the mean squared error and average wait times, improving the predictive wait time model will greatly improve the success of the incentive model. Other extensions are to not assume the scheduler knows private information, and to assume an estimated distribution of riders, rather than the exact number of riders. These extensions would make this model more deployable.