What approach would be suitable for clustering customers based on pickup and drop locations

Question

There are some people who want to travel from some pickup location to some drop location. All pickup locations are in city A and all drop locations are in city B. Where A != B. How to cluster people such that total distance travelled by car to pickup and drop all customers is minimised. Since most cars have capacity to carry 4 people, its desired to use full capacity of each car. Each cluster would be assigned to driver of car who can choose to reject trip in which case it would be passed to next driver.

Answer 1

See the answer to this question: K-means algorithm variation with equal cluster size for an algorithm for clustering into clusters of equal size (in your case 4).

To handle the "different cities" constraint, define each customer as a point-tuple made up of their pickup point in city A and drop off point in city B, and define the distance between 2 customers as the sum of the distance between their pickup locations and the distance between their drop off locations. The average of a list of tuples would be the tuple made up of the average of the pickup locations and the average of the drop off locations. Defining these two functions should be enough to implement K-means.

You might want to weight distances in the two cities differently if travelling a given distance takes longer in one city than another on average because traffic is worse there or you will be in one city at rush hour or whatever.