Cabs n Commuters Solution

Problem Description

Write a program that takes an input file containing the location of m commuters and n cabs and a destination location, and outputs optimised cab routes for picking up all commuters (on a shared basis) and dropping them off at the destination.

Optimisation should be on the basis of total distance travelled by the cabs i.e. the optimal set of cab routes will be the one in which the total of the distances travelled by all the cabs is the least.

Pickups will be on a shared basis i.e. commuters will need to be grouped into different routes based on their locations. It's okay to assume a common pick up point for all commuters sharing a cab. Thus, total distance travelled by a cab will be the distance from the location of the cab to the pick up point + distance from the pick up point to the destination.

Locations can be represented using cartesian co-ordinates i.e. (x, y) notation. Distance calculation can be simplified by using straight-line distance between the points.

Input

Commuters location, m = [(x1, y1), (x2, y2), …..]
Cabs location, n = [(x1, y1), (x2, y2), …..]
Destination location, d = (x1, y1)

Assumptions

1. Common pickup point for all the commuters sharing a cab.
2. A cab is allowed only one trip.

Solution

Now the first task in hand is to group the commuters. This is required to ensure that each commuter is picked up from its location. I am using k-means clustering algorithm in which cab locations will be used as centroid, thus ensuring number of cluster(groups) formed is less than equal to number of cabs. Mathematically,

g = [g1, g2, ... gn] where gi = [mi, mi+1 …..]

len(g) <= len(n)

Note: A cab picking up a commuters group will go to the mean location of all the commuters of that group to ensure a common pick up point. So,

x(gi) = x(mi) + x(mi+1) + …. / n
y(gi) = y(mi) + y(mi+1) + …. / n

Our aim is to optimise the total distance travelled by the cabs

T(min) = t1 + t2 + …. + tn where ti is the distance travelled by each cab.
T(min) = ∑t(i)

In order to do that, we need to find the total distance travelled by a single cab(t(i)).

t(i) = p(i) + c(i)
where t(i) is total distance travelled by a cab; p(i) is distance between cab and pickup point; c(i) is distance between pickup point and destination

T(min) = ∑(p(i) + c(i))
T(min) = ∑p(i) + ∑c(i)

One thing to note here is, ∑c(i) is constant because distance between pickup point and destination remains same irrespective of the cab which picks the commuter.

So, we can reduce this problem to optimising only the total distance travelled between cab location and pickup point. Thus,

T(min) = ∑p(i)

Next step is to find distance between each commuter group and cab, and store it in a two dimensional array.

d[i][j] = pow(pow([x(g(i)) - x(n(j))], 2) + pow([y(g(i)) - y(n(j))], 2))1/2

where i denotes ith commuter group; j denotes jth cab;
0 <= i < len(g) and 0 <= j < len(j)

Now our job is to find cab for each commuter group such that the total distance travelled by all the cabs is minimum.

We can solve this problem by bit-masking approach.

Say, we denote a commuter group(g(i)) taking a cab(n(i)) by g(i)n(i) where,

g(i)n(i) = 0 or 1
where 1 represents commuter group is assigned cab; 0 represents commuter group is not assigned cab

So, there are two possibilities to assign a cab to a commuter group at the same location. Thus, total number of ways to assign/not assign all the commuters a cab.

T(gn) = pow(2, len(g) * len(n))

Now we will loop through all the possible ways of assigning cabs to commuter groups using binary representation. Psuedo code,

_From i=0 to (T(gn)-1);_<br>
   _bin_i = binary(i)_ // represents one way of assigning cabs to all commuter groups<br>

Lets take an example,

len(g) = 2, len(n) = 2, Tgn = 16

Loop will run from 0 to 15; all binary representations: 0000, 0001, 0010, 0011…., 1111

What does this binary number represents?

• 0001 tells that 0th commuter group will be assigned 0th cab; total distance travelled = d[0][0]
• 0010 tells that 0th commuter group will be assigned 1st cab; total distance travelled = d[0][1]
• 0110 tells that 0th commuter group will be assigned 1st cab; 1st group will be assigned 0th cab;
  Total distance travelled = d[0][1] + d[1][0]

Some of the ways assigning cabs is incorrect, for example

• 0000 does not assign any cab to a commuter group
• 1111 assign multiple cabs to a single commuter group

We have to filter out the correct binary representations by checking the following things:

• Number of 1’s in binary number must be equal to len(g)
• A commuter group is not assigned multiple cabs or a cab is not assigned to multiple commuter groups.

Final Answer: Binary representation which gives the minimum total distance travelled by all the cabs + distance between all the pickup locations and destination.