1
$\begingroup$

I am looking for an algorithm to find the optimal matching/allocation of n individuals in m identical vehicles. The aim is to create groups of individuals who will share these vehicles. Groups' size is bounded.

An individual i has incomplete preferences over the other individuals (some are not included into i's preference list when i can't share a vehicle with them).

I am looking for an algorithm returning a stable matching and minimizing the global cost for all individuals (cost for individual i being defined as the sum of the index of the individuals sharing i's vehicle in i's preference list).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Have you tried the standard algorithm for solving the stable marriage problem? It's documented in many places. Is there some reason that doesn't work? Can you define what conditions an allocation must satisfy to count as valid? $\endgroup$ – D.W.♦ Apr 23 '19 at 0:52
  • 1
    $\begingroup$ @D.W. Stable marriage does not seem quite right, because the cars do not have preferences. The stable roommates problem can be seen as a special case of this problem if all vehicles have exactly 2 spots. Still, what stability you would want is unclear, and this should indeed be specified. In general, there may not exist a stable matching that also minimizes the cost. Perhaps it is better to try to minimize cost over all stable matchings. $\endgroup$ – Discrete lizard♦ Apr 23 '19 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.