Auto Clustering Service

This service enables MOOVE to create pools of geo-similar riders.

It is written in Google’s GO Language.

The goal of the auto clustering algorithm is to maximize utilization of vehicles based on multiple constraints such as on-time arrival, maximum capacity of a vehicle, maximum time and distance that is acceptable for a ride (and each individual rider), deviation from the route / axis, etc.

The service looks at the queue of scheduled riders and computes geo-hashes for their locations. The queue is then sorted on the basis of distance from the Enterprise’s office location for rides picking-up riders from Home to Office journeys.

The algorithm clusters locations that have similar geo-hashes in the first pass. It starts by taking the farthest employee (Employee E in the diagram below) and checks compliances – can this employee be picked up using a vehicle such that the employee will arrive on-time to work (location A in teh diagram below), and the total time and distance is within acceptable limits. It then tries to add another employee from the same geo-hash cluster or a close by cluster and verifies the constraints of time, distance, On-time arrival are still met. This process continues until the vehicle reaches max capacity or another constraint crosses permissible limit. The minimal set of employees that meet all the constraints are then considered a plausible cluster.

Once all the employees from the pick-up queue are assigned to these plausible clusters, the algorithm makes a third pass at optimizing. It does trade-offs between clusters to reach overall minima and then starts to convert the optimized clusters into manifests that can be assigned to Drivers.

Members: please use the Link(s) below to access the GODOC generated documentation of the MOOVE’s Auto Clustering Service developed in Go Lang.

Don’t see the Link(s) above? Please Sign-in / Register as a Member.