Ride-Sharing Optimization Algorithm
MATLAB, Linear Integer Programming, Graphing Methods, Simulation
In this project, I worked in a group of two to create a ride-share algorithm that analyzes the benefits of carpooling in ride-sharing, as current ride-sharing services and models don't fully address the potential benefits of ride-sharing, due to limiting the amount of rider requests per vehicle. Therefore, we created a real-time redistributive carpooling ride-sharing model that works to match a driver with as many ride requests as possible, while working to minimize traffic congestion, energy consumption, and fulfilling each request's time constraints. We also analyzed the trade-off between constraints such as vehicle capacity, rider waiting time, rider travel delay, and operational costs to further analyze the potential upside of carpooling in ride-sharing.
The algorithm we designed, in MATLAB, was inspired by the research article, “On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment.”[1] This algorithm can be broken into five steps: Data Collection, Individual Requests Satisfaction, Request Set Satisfaction, Vehicle to Set of Request Assignment, and Vehicle Execution.
I will give a general overview and background of the algorithm before going through step A to step E.
Our ride-sharing model has two design variables,ei,j and xk, both representing binary variables. The variable ei,j represents a trip set, i, containing a combination of ride requests that can be carried out by a vehicle, j. If the trip set, i, will be carried out by vehicle j, ei,j = 1, and if the trip set isn't carried out by vehicle j, then ei,j = 0. The variable xk represents if an indivdual or group's ride request can be met. For example, if a ride wasn't found for ride request 1, r1, then the request isn't satisfied and x1 = 1, however if r1 can be satisfied then x1 = 0. Constraints that can prevent a ride from full-filling a rider's request include the vehicle's maximum capacity, the longest amount of time a request is willing to wait to be picked up, and the longest a request is willing to wait until it is dropped off at its destination.
Understanding this can be confusing, so now I will walk through an example. Say at an instance of zero minutes, t=0, there are two vehicles and one request, r1. Assuming that all constraints are satisfied, then there are two possible trips, e1 and e2, as both vehicles can complete r1. There is only one x variable, x1, as there is only one request, making the design variables [e1, e2, x1]. Now at t = 1, if another request, r2, is made and assuming that each vehicle can only satisfy each request individually, then the design variables are [e1, e2, e3, e4, x1, x2], thus increasing the number of feasible trips.
Step A, focuses on data collection. In this step, the current location of each active vehicle, each vehicle's maximum capacity, the ride requests currently within the vehicle, and the drop-off destinations of all ride-requests within a vehicle are made known. Additionally, the maximum wait time and maximum total delay time that each request is willing to wait is also made known. The maximum wait time, wmax, is defined as the longest amount of time a request is willing to wait for a vehicle to arrive for pickup after the ride-request was made.
w = trp - trr
trr is the time that the rider requested a ride and trp is the time that the rider(s) of a request are picked up. The total delay time of a request is the wait time of a request plus the additional in-vehicle delay that a ride request experiences before being dropped off. In-vehicle delay refers to the additional time added to a request’s trip if the vehicle picks up or drops off another rider in-between picking up and dropping off a ride-request . For example, If a vehicle picks up a request and drops the requests off immediately then the in-vehicle delay is 0, however if a vehicle picks up a request then picks up a second request up, before dropping off the first request, then in-vehicle delay will occur. Total delay time, (δr), is mathematically defined as:
(δr) = trd - tr*
where trd is the drop-off time and tr* is the theoretical drop-off time of the request rider if no delay in drop-off time occurs. tr* can also be described as the drop-off time of a request if the shortest path from the pickup location of a request to the destination of a request was taken. Positions in our model are identified using an x-y coordinate position, where a change of Δx = 1 or Δy = 1 takes one minute. This means a vehicle traveling from point {0,1} to {1,1}, in our x-y coordinate system, or vice versa takes one minute. Therefore tr* is calculated as:
tr* = tr + (|xend - xstart|+ |yend - ystart|)
Step B, shows a pairwise shareability RV-graph to identify potential connections between requests and vehicles. The graph is created by representing the request and vehicles as nodes
and their pairwise shareability as edges. The links between a car and person denotes that the car can satisfy that person's request and a link between two people
means that those two requests can be satisfied in the same trip if one of the riders were picked up with zero wait time.
During this step we test if it is feasible for each vehicle to pick up and drop off each individual request with no additional
requests being added to the trip given a vehicles current location. We also check if the trip satisfies each request's maximum wait time and maximum total delay time.
If it is feasible for a vehicle to drop a request off, while satisfying the constraints, then a node is created linking the vehicle with the request, indicating
the vehicle as a potential candidate to fulfill the request. This was done in MatLab, using a (v x r) matrix called v2rlinks, where j, represents the number of vehicles,
and r represents the number of requests. If vehicle, i, can drop off request, j, then v2rlinks(i, j) is set to 1 representing a node between the vehicle and request.
If vehicle, i, can’t drop off request, j, then v2rlinks(i, j) is set to 0 representing that there is no node connection between the vehicle and request. Once all
potential links were created we proceeded to step C.
Links between requests were not created and tested in our model. This was because we were focused on creating a
smaller, proof of concept model, and didn't anticipate a linkage between requests to have a significant impact on decreasing time complexity in future steps.
In creation of a larger model, linkages between requests would be necessary.
Step C shows a RTV-graph to visualize the potential trips and the vehicles that are capable of executing them.
The RTV-graph uses nodes to represent the requests, vehicles, and potential trips, with edges connecting between them based on their compatibility. In
the case where a case cannot be satisfied, a yellow triangle node is added to represent this unsatisfied request in the graph.
In our algorithm, this step is done by finding all combinations of potential requests that each vehicle can fulfill given linkages found in step B,
but only constrained to the vehicle's capacity. For example, If vehicle 1 is linked to request 1, r1, request 2, r2, and request 4, r4, with a maximum capacity
of two then the potential trips for vehicle 1 are {r1}, {r2}, {r4}, {r1, r2}, {r1, r4}, and {r2, r4}. Once all possible trip sets are found, we test
if these trips are feasible given the max wait time and max total delay time requested by each request. This is done by testing each request's constraints on
every permutable pick up, drop off order in which a trip set can be carried out, until we find if the trip is feasible. For example, two permutations of the set
{r1, r4} are {r1start, r4start, r1end, r4end} and {r4start, r1start, r1end, r4end}. If a trip is feasible and can be carried out by vehicle j then the algorithm
creates a link between the trip set and vehicle j.
Once all permuted feasible trip sets are found we look to minimize the cost of the trip.
The cost of the trip is defined as the sum of the total delay times of each request in a set. Changing the order of pickup and drop off of requests in a trip set
can lead to either an increase or decrease in the total cost of the trip, due to requests experiencing a longer or short wait time and/or in-vehicle delay.
For example, if vehicle 1, v1, starts at {1,0}, r1's pick-up location is at {2,0} and r2's
pickup location is at {3,0} and both requests would like to be dropped of at {5,0}, to minimize total delay, v1 would pick up r1, then pick up r2,
and would then drop both requests off at {5,0}, thus minimizing the total delay time. This would be the ideal route, as opposed to picked up r2 then turning
around to pick up r1, and then finally dropping both requests off, causing both requests to have a larger total delay time.
Once the minimum cost of a feasible trip was found, a (e x 3) matrix was created where e is total number of combinations of feasible trips that
can be carried out by all the vehicles. The first column shares the vehicle that can carry out the trip, the second column stores the optimized
order that the trip should be carried out in for each vehicle, and the third column stores the minimum cost of the trip. Once the minimum cost of each feasible trip is calculated then we move along to Step D.
In future and large models, this step would be modified to decrease time complexity, but due to a trade-off between time constraints of developing the algorithm and time
complexity of processes, this method was suitable.
Step D, illustrates an optimal assignment obtained by the LIP solution where vehicles are assigned to requests and asked to carry out their assigned requests. In this step we look to minimize our objective function by using Linear Integer Programming. This step assigns vehicles to trips by looking for the most optimal solution of our objective function.
Min f(x) = ∑ci,jei,j + ∑ckoxk
The final objective function value, seen above, represents the amount of street congestion and energy consumption that will occur in a given vehicle to request assignment scenario. A large objective function value means that the senerio would lead to a large traffic and energy consumption,
occur while a lower value means less potential congestion and energy consumption. In this formula, ci,j is the minimum cost of a trip, ei when carried out
by a vehicle j. The variable, cko, is a large constant set to 50 for unassigned requests used to deter the model from leaving a request unassigned if possible.
The purpose of a large cko constant is for the model to favor a ride request being part of a trip instead of having the request left unsatisfied.
If a request is satisfied this would ideally lead to carpooling and a more environment friendly outcome, thus a lower objective function value.
However, if a request is not satisfied this could result in a rider using another ride-share service, most likely not a carpooling serivce, or leading to a rider driving to their destination,
thus increasing the objective function value as this would lead to more total energy consumption and traffic. Thus, a method is needed to deter the model from leaving a request unsatisfied.
Using LIP on MatLab we limited all variables to integers. LIP doesn’t limit variables to binary, so the upper bound for each design variable was set to 1 and the lower bound
of each design variable was set to 0. Our initial conditions for our optimization were that where all trips don’t occur(ei equal to 0) and all requests are not satisfied(all xk variables equal to 1).
This was done for simplicity as the number of design variables can change throughout time. Lastly our objective function had two constraints. The first constraint, shown below in the formula below, ensures that each
vehicle is assigned to one trip, a set of ride requests, or zero trips.
(∑ei,j) ≤ 1 for all vehicles j
The formula above states that the sum of the binary values of every trip, ei, that can be carried out by j must be less or equal to one. Since all values are binary this ensures that each vehicle receives a maximum of one trip. This constraint is created for each vehicle. Our second constraint, shown below, assures that no more than one trip, containing request k, can occur and if no trip containing request k occurs, then request k is unsatisfied and xk = 1.
(∑ei,j) + xk = 1 for all requests k
Furthermore, this formula enforces that either the sum of all trips containing request k must be equal to one and xk = 0, meaning a trip containing request k occurs and request k is satisfied, or the sum of all trips containing request k equal to zero and xk = 1, a meaning a trip containing doesn’t occur and request k isn’t satisfied. An overall mathematical representation of our objective function and its constraints to follow can be shown below in Figure 2.
Figure 2: Optimization function and constraints on the optimization
Lastly, Step E, depicts the planned route for the two vehicles. In this step we look for each vehicle to carry out their assigned trip until a new ride request is made. During this step the following data is recorded and is updated at each time step: the position of each vehicle, the trip set a vehicle is responsible for, the ride requests the vehicle has as passengers, requests that have been dropped off, thr requests that still need to be picked up, and records of the travel history of each vehicle. If a new request is made or a new vehicle is added, as time increases, steps A, B, C, and D are repeated for a new optimal solution, while prioritizing the drop-off of passengers currently in the car, by adding the new requests to a vehicle's trip set. Requests not in a vehicle, can then be reassigned to a trip of a different vehicle in order for continous optimization.
Results of our experiment are too extensive to be included into my project portfolio however the results can still be found, beginning at page 12 of the following link.
This project gave us technical insight into the inner workings of ride-sharing services systems like Uber and Lyft. With regards to our own algorithm, we found the capacity constraint to be the most impactful in how the objective function is minimized. The larger the capacity of the vehicle, the more requests a single vehicle can serve. As a result, the number of cars needed to satisfy a set of requests decreases, given all other variables are constant. However, reducing the number of cars still can increase a ride request's wait and total delay time. Additionally, if ride-sharing carpooling was widely adapted, less cars would need to on the road, resulting in less travel delays en route to a passenger’s destination. Therefore, the extra time required when traveling in a high capacity vehicle may balance itself out in the long run.
For scalability, this model would need to see several improvements. Most importantly, more vehicles and ride-share requests would be needed to be added to the model, to
analyze the effects of carpool ride-sharing more accurately. Our algorithm also needs to be improved to limit the number of times a request's ride is redistributed to a new vehicle. When a high flux of
ride requests occurred in a set time frame, the optimizer would continuously reassign requests to different vehicles. In this constant shuffling, it would lead to
some vehicles, who could fulfil multiple trips, to end up not fulfilling any ride requests and some ride requests that could be full-filled to not be full-filled
by the end of the run. For example, say there were two actives vehicles and two new ride requests were added every second, causing the trips to be reassigned every second.
This would sometimes kick another request, that hasn't been picked up, out of being assigned a vehicle,thus leaving the request without a ride.his makes our current algorithm very unreliable for customers and would ultimately deter users from using the carpooling service.
Another recommended improvement would be to include vehicles or the size of the trip a vehicle is assigned to into the objective function as well.
If a vehicle is only assigned to one rider, this wouldn't improve the environmental energy consumption or street congestion, as the goal of the model is to enable carpooling.
Also, as it is possible for a vehicle in our model to never complete a request, that also vehicle wouldn't help
minimize traffic congestion. This, instead, would impact the environment negatively and should be represented in the objective function.
Additionally, more freedom needs to be given to the potential passengers and drivers. Currently, customers are not able to
cancel requests in our algorithm and drivers do not have the option to deny requests, both of which happen frequently in the real-world. Overall, our model
performed well for the small scope, however improvements to our model would still be needed for our algorithm to be implemented in the real world.