Cab Scheduling Algo

Link

1. Pure greedy

Dispatch every idle car to pick up the closest passenger that is waiting for a ride.
This is probably the most straight-forward approach, nonetheless quite effective. I’d venture to say that this is probably the most common approach for taxi companies because of its simplicity and ease of execution.

2. Greedy car pool

This approach is very similar to the previous approach in that the closest available vehicle is dispatched. The only difference is that each vehicle will pick up multiple packages at the pickup location, and deliver them one-by-one, in order of proximity.

3. Along the way

This approach considers not only idle cars that are closest to the passenger, but also vehicles that already have passengers on board. Cars are dispatched to pick up new passengers that are along the way, as long as there are enough seats and the driver can still drop all their passengers off on time.

This may resemble a rudimentary approach to something like UberPool or Lyft Line, where drivers can pick up more passengers that are heading in roughly the same direction.

4. Easy wins

This method might sound familiar, because it’s what happens when old-school cab drivers deny you a ride if you request one that’s too far for their liking. It is more lucrative for a cabbie to make a bunch of quick trips, because of the minimum fixed fee they earn each time.

This algorithm will look for quick and easy wins, i.e. short trips in close proximity. While driving towards a pickup location, the car can be rerouted to a pick up new package if it is an easier win. It will also pick up multiple packages at the same location.
In order to maximize the chances of finding these short trips, 1 car is assigned to roam exclusively the dense area of buildings in the centre.

5. Chinese cab drivers

This algorithm reminds me of a time when my wife and I tried to take a cab from the Wenzhou train station. The usual frenzy of fighting for a cab wasn’t that bad, if it weren’t for the fact that once we finally got seated, the cab driver decided to wait and look for more passengers heading the same way.

Obviously, this isn’t the best strategy if you care about your customers.
After 20 minutes of waiting and arguing with the driver, we decided to ditch the cab and take another one that was ready to hit the road.

The essence of this approach is to defer departure and and pick up as many passengers as possible, while ensuring that passengers will not be dropped off late. Our chinese cab driver didn’t understand that last part.

6. Route optimization

Route optimization is about finding the shortest total driving time, given a fleet of vehicles and a host of orders with their constraints. This is also known as the Vehicle Routing Problem. In this particular case, we need to solve a same-day Pickup and Delivery problem with time-windows and car capacities. Each snapshot in time can be considered a routing problem that we solve for, the results of which become the updated driving instructions for the fleet.

To this end, we hooked up Routific’s same-day pickup and delivery API to the Local Motion challenge, and called the API every 5 turns. You can find the code here [3]. As new information becomes available throughout the simulation, the entire fleet is re-optimized so they are always taking the most optimal routes.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s