Building a Rideshare Simulator in C++

Picking up and dropping off passengers on real map data from OpenStreetMap. The code and data mentioned here can be found in my Github repository.

An image from the Rideshare Simulator, using Downtown Kansas City as the map. Videos are included further below.

I recently built a rideshare simulator in C++, capable of taking in OpenStreetMap data and a related image, and showing vehicles driving around, picking up passengers, and taking them to their destinations.

I built this project as my Capstone project for the C++ Nanodegree (ND) program at Udacity. As a side note, I work at Udacity, although this was a personal project, so I won’t delve too deep into the ND itself except as it relates to a couple of earlier projects in the program that gave me the idea.

The first project in the ND is to build a route planner that uses A* Search on top of an OpenStreetMap data file, while allowing the user to input a starting and end point, to find a route between those points. The second-to-last project is a Concurrent Traffic Simulation, that while using a hard-coded map of “streets” and “intersections”, has vehicles drive around and stop at red lights (and proceed when they are green). You can see a quick example of these below.

On the left is the Route Planner project output (also using OpenStreetMap data); on the right is the Concurrent Traffic Simulator (using a hard-coded map).

While the traffic simulator didn’t use real map data, it seemed like a natural extension to try to apply similar principles onto OpenStreetMap data like the earlier project. I decided to try to generalize similar concepts from the traffic simulator first onto OSM data from downtown Kansas City, Missouri, where I currently live.

Checking that I could (mostly) accurately find all intersections from the KC map data

In the above image, I used the same “drawing” techniques that the traffic simulator had used to put a bunch of green dots where I found nodes shared by more than one road (or “way”, in OSM parlance), and saw they lined up pretty closely to the image. So, I felt confident my approach could work for building out a full rideshare simulation.

Examples

Before we get too far, let’s look at examples of the final output, so you can tell whether you actually want to read the whole article! I’ll note first that the typical settings for the simulator have a max of 10 “map objects” of each type at any given time — this means up to 10 vehicles, and up to 10 “passengers” waiting on a ride, although there can also be additional passengers already in vehicles. It is also set to randomly add a new waiting passenger every 3–5 seconds, up to the maximum. Vehicles or passengers that are “stuck” on the map (in an unreachable position) do eventually get removed — this can happen on the Downtown KC map as certain highway positions cannot be reached from the main downtown roads (because the ramps are not on the limited map). Lastly, the simulator does not currently pay attention to one-ways.

The rideshare simulator running on Downtown KC with a max of ten of each object type

The square-like objects are the vehicles here, with the diamonds passengers, and the X-marks their desired destinations. The passengers do currently sort of teleport into the vehicle when the vehicle reaches the closest road node to their position, and similarly they teleport out when at the nearest road node to their destination — one thing I hope to improve on in a future update.

To show that the simulator can generalize to other map data, I’m also including the below video, with otherwise similar settings, showing the area near the Arc de Triomphe in Paris, France (like the hard-coded Traffic Sim, but with real map data this time).

Showing the simulator can generalize to other map data — in this case near the Arc de Triomphe

Build Process

Here, I’ll describe the general process I took to build out the simulator functionality, with expansion on certain areas later on.

1. After seeing I could accurately find all intersections in the OpenStreetMap data, I next decided to build out the generation of waiting passengers. This was fairly straightforward, as a “passenger” is basically a current map position and a map destination, determined by asking the map model itself for two random positions that are within the map data’s outer coordinates. I also added some random colors for each so they are distinguished from each other on the map.
2. Next, I focused on adding vehicles to the map, and having them just randomly drive around. This directly uses the route planner from the earlier project along with a random “destination” for each vehicle. However, the routes that the route planner makes has “separated” nodes on the map — there is often a good amount of space between them. So, I also added a method to incrementally drive between road nodes each cycle, for the appearance of smooth driving. I discuss more on vehicle states further below.
3. From there, I added the ride matcher to actually tell vehicles when there are waiting passengers to pick up. I discuss more on how matches are made later on as well.
4. The last “main” step was to enable vehicles to actually pick up passengers from their starting positions, and drop them off at their destinations. In this case, the vehicle will pick up or drop off the passenger when they reach the closest road node to their starting position or destination position (which do not have to be on a road), respectively.

Project Architecture

The project architecture utilizes concurrency, so that the graphics can be drawn on the main thread, while updates to the vehicles and passengers are done in background threads. The traffic sim project had made each vehicle and traffic light its own thread, but I took a different approach, having one thread for a vehicle manager (with multiple vehicles), one thread for the ride matcher, and one thread for the passenger queue. While the route planner is called by the vehicle manager or passenger queue, it is not on its own thread right now.

The first implementation of this was rather naive, and not really appropriate from a concurrency standpoint. A given thread, such as the vehicle manager, would directly call to the ride matcher class (represented by a shared pointer), which would update the ride matcher while it might be doing something else. That could then create what is called a race condition, where depending on the sequence of events, the outcome might be different.

The original “naive” approach, creating race conditions between threads (in somewhat butchered UML)

The fix for this was to instead pass “messages” between the threads. Each cycle, a thread would read its new messages, and take action based on those messages. While reading, the messages get locked by a mutex, so new messages can’t be received (and other threads will wait to be able to send those messages). After reading, this is unlocked, so the other threads can now send further messages, but the current thread won’t read them until the next cycle.

The current architecture, reading new “messages” at the start of a cycle, and taking action based on those messages. Sent messages, like requesting a match, are stored (and mutex protected) until the next cycle.

This could potentially even be further improved by the use of something like a publisher-subscriber architecture. The vehicle manager and passenger queue both currently need to include the ride matcher and route planner interfaces to be able to communicate with them, and vice versa. In this potential architecture, each would instead just need to know relevant topics to publish or subscribe to on the overall service, and wouldn’t need to know any specifics of (or really, of the existence of) the other classes.

A potential further improved architecture, where the concurrent classes instead publish or subscribe and don’t need any coupling to the other classes.

Matching Vehicles to Passengers

To focus on the other functionality first, the original matching in the simulator was quite simple — the first passenger ID in the matcher, and the first vehicle ID, were matched together. Since match requests are put into ordered sets, one with passenger IDs, and the other with vehicle IDs, this just meant that the lowest passenger ID (also meaning the longest waiting passenger, since IDs increase for each new map object) always was the first attempted match. However, it also meant that the vehicle getting the match was going to be whichever the lowest ID asking to be matched was, regardless of if they were the furthest from the waiting passenger — Vehicle 0 would always have priority over Vehicle 4, for example.

Simple Matching — the first of each by ID is matched (assuming no prior un-matching). Vehicle #9 would be substantially less likely to be given a match at any point in time than an earlier ID.

This actually works quite fine, but wasn’t optimal, of course. I also eventually needed to add in a step to make sure to skip any potential matches that had failed previously (due to the vehicle not being able to reach the passenger), or else it would essentially guarantee at least the vehicle, and likely the passenger, were going to be removed from the map due to too many failures, even if one or the other wasn’t actually stuck.

The current type of matching is the more logical method — matching a given passenger (still the first one) to the nearest vehicle to it (using Euclidean distance). However, to slightly save time if a larger number of vehicles are on the map, it will also just match them to a “close enough” vehicle if any exist — currently set to roughly 15% of the size of the map. This way, if the simulator was set to instead use 100 vehicles (or even more), it doesn’t need to check for the closest out of all 100 vehicles — if any vehicle is within that “close enough” distance, the match gets made.

With the Closest (or “close enough”) Match, the earliest passenger is still matched first, but ID has no impact on which vehicle is matched to them — only how close they are on the map.

Note that there isn’t any un-matching done if a different passenger is later closer to a vehicle than the original match — if the matched passenger is reachable, the vehicle will always go get them.

Vehicle States and Handling Issues

One of the central ideas to how each vehicle acts each cycle is based on its “state”. I came up with five of these, each with different behavior:

1. No passenger requested — vehicle either just started driving or just dropped off a passenger, and has not yet asked the ride matcher to give them a new passenger assignment. This will drive around to random destinations on the map.
2. No passenger queued — similar to above, but it has now requested to be matched, without receiving a match yet.
3. Passenger queued — the ride matcher has notified it (or more so the Vehicle Manager, which tells the individual vehicle) of a match, and where that waiting passenger is. It drives to the nearest node to the passenger position.
4. Waiting — a very short state currently, where the vehicle has arrived at the passenger position and is waiting to receive them. In the future, this is probably where the passenger would be shown to “walk” to the vehicle on the visualization.
5. Driving Passenger — the vehicle has picked up the passenger, and is driving to the nearest road node to their destination. Once they arrive, they will “drop off” (i.e. remove) the passenger, and transition back to the first state.

Issues While Driving

With the above implemented, there were four main areas where a vehicle could run into an issue (and at the time, crash the program until these were handled).

1. A vehicle has not requested a match, but cannot get an initial path — this is pretty simple to handle actually, and probably means the vehicle is “stuck” in a position where they can’t reach most of the roads on the map. Handled by incrementing the vehicle’s failure counter, and trying a new random destination. It will be removed if it has 10 or more failures.
2. The vehicle has requested a match, but cannot get a path — this is handled almost the exact same as above, although if removal does occur, we have to notify the ride matcher, so it won’t try to match the vehicle still.
3. The vehicle matched with a passenger, but can’t reach them — this is mostly handled similarly to above, although the ride matcher must always be notified. The ride matcher will un-do the match, and also notify the passenger of the failure, in case the passenger may be “stuck” and need to be removed. This was reduced substantially by actually making passengers also check for a “path” from their position to their destination at the time of creation — if there is no viable path, they are immediately removed from the map, prior to ever requesting a match. There is a small chance, however, that both the passenger’s start position and destination are both on the highway in the KC map — so for them, a path exists, but the vehicle can’t reach them.
4. The vehicle can reach the passenger, but not the passenger’s destination — this was actually resolved entirely with the check in #3 above, although I originally tried to address this issue first. It is a potential issue, but not one that is reachable in the current code.

Output Information

The simulator also outputs some relevant information to the console, so you can better see what is going on. For example, here is a small snippet of output from early on in a run:

Vehicle #3 picked up Passenger #1.
Vehicle #1 dropped off Passenger #5.
Passenger #6 requesting ride from: 39.0991, -94.579.
Vehicle #6 matched to Passenger #6.
Vehicle #6 picked up Passenger #6.
Passenger #7 requesting ride from: 39.1008, -94.5877.
Vehicle #7 matched to Passenger #7.
Vehicle #8 picked up Passenger #0.
Vehicle #2 dropped off Passenger #4.
Vehicle #3 dropped off Passenger #1.

There are other outputs too, such as vehicles beginning to drive, stuck/unreachable vehicles or passengers being removed, or un-matching (usually because the vehicle can’t reach the assigned passenger, usually due to one or the other being stuck), but those are seen less often.

Scalability

I mentioned in the earlier examples that they were set to a max of 10 map objects and potential generation of new waiting passengers every 3–5 seconds. This was sort of arbitrarily determined as being easier to actually watch the driving and pickup/drop-off — it can actually handle a lot more! The below video shows it running just fine with a 100 object max, and new passenger generation time of 0–1 seconds.

A max of 10 is fairly arbitrary — here we have 100 vehicles and max of 100 waiting passengers, with 0–1 second generation time for new waiting passengers

One thing that is more difficult to scale with is a larger OpenStreetMap area — you may have noticed that both the Downtown KC map and Paris map (which is a little larger) aren’t necessarily huge areas. While I have not checked just how large of an area could be used, the loading of the map at the start does take longer as the area gets larger — the Paris map’s OSM data has nearly 163,000 rows of XML data.

Future Improvements

There are a number of ways the current simulator could be improved, but here are my top-of-mind areas:

1. Change the current “teleportation” of passengers into and out of vehicles to instead show a smooth “walking” movement in from their original position and out to their final destination point.
2. Vehicles currently ignore the directions of streets. “Fixing” this may cause more situations where a vehicle or passenger is “stuck”.
3. Certain routing is a bit finicky near intersections, causing a slight backtracking. The route planner likely needs some further improvement to guarantee nodes are always “forward” near an intersection.
4. Make vehicle/passenger generation more dynamic around potential supply/demand. This could result in a vehicle/passenger leaving the map if they have to wait too long for a match, or also where more vehicles would appear if passengers are waiting longer, or vice versa.
5. Allow for user input to switch matching types, or perhaps even to give a location and call the OpenStreetMap API to use new locations.

Conclusion

As noted at the start, you can also check out the related code for the simulator in my GitHub repository. Thank you for reading this article, and I hope you found it interesting!