He used a custom clustering algorithm, not k-means.

We initially tried assigning clusters to couriers, and letting them complete the assigned orders in any ordering (usually according to deadline), however, we ran into issues when new orders came in (especially rushed delivery orders). We settled on a solution of ordering a courier's assignments in an optimized order to increase chance of finishing all assignments on-time, and then only showing the courier one assignment at a time: the top priority assignment. When we closed down, we had been experimenting with factoring in the number of gallons and of what octane each courier was currently carrying.

We had a special business license with Google Maps API, but still cached the driving time calculations to speed up the algorithm / save money. Anyways, the routing algorithm only have to run every time the orders/couriers state changes (https://github.com/Purple-Services/app-service/blob/e0a4f74c...).

When you are tracking every couriers' location you can playback GPS coords prior to an accident and determine if their average velocity was higher than acceptable. You can also tell if they aren't on-task after receiving an assignment, or if there are two on-duty couriers in the same car! We experimented with RFID tag + Bluetooth connection to courier's app, to track actual amount of gas delivered as seen by a flow meter. And, we had an algorithm for recommending gas stations for couriers to fill up at based up price / distance. In B2B sales, a VIN scanner in the courier app was useful for reporting.