This project designed a min matching algorithm to match riders requesting carpool in Manhattan in order to save total travel distance.
We formed an undirected graph with nodes represent passengers and edges represent their sharing plan. Using maximum matching with minimum weight algorithm, we can find the best sharing plan with the minimum total distance.
Based on Manhattan distance (π(π₯1, π₯2), π(π¦1, π¦2), π(π, π) = |π₯1 β π¦1| + |π₯2 β π¦2|), we defined the distance between each two passengers π(π, π)1 in five scenarios:
a. Pick up π then pick up π then drop off π then drop up π:
β’ π(ππ)=π(1)=π(π1π1)+π(π1π2)+π(π2π2)
b. Pick up π then pick up π then drop off π then drop up π:
β’ π(ππ)=π(2)=π(π1π1)+π(π1π2)+π(π2π2)
c. Pick up π then pick up π then drop off π then drop up π:
β’ π(ππ)=π(3)=π(π1π1)+π(π1π2)+π(π2π2)
d. Pick up π then pick up π then drop off π then drop up π:
β’ π(ππ)=π(4)=π(π1π1)+π(π1π2)+π(π2π2)
d.π and π travels on his/her own:
β’ π(ππ)=π(5)=π(π1π2)+π(π1π2)
Passengers are not pooling with someone if the total travel distance he spends on a shared vehicle will exceed 25% more then traveling on his/her own. We call it βlevel of serviceβ to guarantee the quality of vehicle sharing.
For passenger(π):
if π(π1π1)+ π(π1π2)>1.25π(π1π1):
set π(1) as +β
if π(π1π1)+ π(π1π2)+ π(π2π2)>1.25π(π1π1):
set π(2) as +β
if π(π1π2) + π(π2π2) > 1.25π(π1π1):
set π(4) as +β
Repeat it for all passengers and output all the distance. The weight of two passengers is defined as:
π(ππ) = min{π(1), π(2), π(3), π(4), π(5)}.
After defining all the weight of edges, we formed a complete graph to represent passengers and their best way of pooling with each other.
As shown in the figure below, there are four passengers π΄, π΅, πΆ and π· with weights and way of pooling marked on edges. The maximum matching of all passengers with a minimum total weight is pair π΄ with π· using scenario 1 and pair π΅ with πΆ using scenario a.