Finding optimal swapping paths in employees moving to different cities

Question

We have a problem where we want to find the optimal path for swapping employees' locations across the country.

Hypothetically, a company allows for employees to request to move to another city only if a vacancy is available in that city, and also if someone is willing to take their soon-to-be vacant position. Examine the example:

• Employee A who currently works in Los Angeles wants to move to Boston.
• Employee B who currently works in Boston wants to move to New York.
• Employee C who currently works in New York wants to move to Los Angeles.

In the above triangle, we can grant all three employees the permission to do the move, since there won't be any vacancies once they move. But the situation gets more complex when:

• Multiple employees are competing for the same location. We can solve this with a hypothetical score of some sort, like more years working for the company gets the priority.
• We have more cities to consider. (in the hundreds)
• We have more employees to consider. (in the hundreds of thousands)

Ultimately the goal is to grant the highest number of move permissions without leading to any vacancies in the system.

We're currently exploring the idea of simulating all the swapping paths, and then selecting the one that generates the highest number of moves.

But I feel that this problem existed in the wild before, I just don't know what keywords to look for in order to get more insights. Any ideas? What algorithms should we look into?

Answer 1

I was about to post this in a comment but it was more than the the actually allowed characters.

I'm not sure about existing advanced algorithms that could potentially solve this problem, but you can custom fit some fundamental ones:

1. An employee wanting to move from city1 to some city2 is a directed edge from city1 to city2. Make sure that if 2 employees want to move from A to B, you add 2 directed edges for that or somehow keep count of the quantity.
2. Find disjoint components of the graph.
3. In each disjoint component, find the largest possible circle. A circle means A -> B -> C -> A.
4. Remove those edges and keep count of the number of successful swaps.
5. Rpeat until there are no circles in any of the disjoint components.

This is a greedy algorithm. At the moment I'm still not quite sure if it would produce the optimal solution in each and every situation. Any input is appreciated.

Answer 2

Remove the impossible move requests, like this

A,B are specific cities.  n is amy city
RAB is a request to move from A to B
RAn is a request to move from A
RnA is a reuest to move to A
CAn is the number of requests to move from A
CnA is the number of requests to move to A

set flag TRUE
WHILE ( flag == TRUE )
    set flag = FALSE
    LOOP A over all cities
       IF CAn > CnA then not all RAn can be permitted.
            Remove lower scoring requests until CAn == CnA.  
            set flag TRUE

Once these "impossible" moves are removed, all of the remaining move requests are "in-balance". That is, all of the move requests to a city are equal all of those from a city. From that point on it no longer matters which cycles you choose to implement: once you implement them, the remainings requests are still all in-balance. And no matter which move-cycle and which order they are implemented in, it stays in-balance until all remaining requests are zero, and the total number of moves will be exactly the same no matter how they are implemented. ( This explanation is due to https://stackoverflow.com/users/109122/rbarryyoung )

Here is C++ code implementing this

void removeForbidden()
{
    bool flag = true;
    while (flag)
    {
        flag = false;
        for (auto &city : sCity)
        {
            auto vFrom = RequestCountFrom(city);
            auto vTo = RequestCountTo(city);
            if (vFrom.size() > vTo.size())
            {
                for (int k = vTo.size(); k < vFrom.size(); k++)
                {
                    vFrom[k]->allowed = false;
                }
                flag = true;
            }
        }
    }

    std::cout << "Permitted moves:\n";
    for (auto &R : vRequest)
    {
        if (R.allowed)
            std::cout << R.text();
    }
}

The complete application code is at https://gist.github.com/JamesBremner/5f49beaca59a7a7043e356fbb35f0d09

The input is a space delimited text file with 4 columns: employee name, employee score, from city, to city

Here is sample input based on your example but adding another request that cannot be permitted

e1 1 a b
e2 1 b c
e3 1 c a
e4 0 a c

The output from this is

Permitted moves:
e1 1 a b
e2 1 b c
e3 1 c a

Note: I have not implemented the scoring. For simplicity I assume that move requests are entered in order of descending score. So, the requests that are dropped when necessary, change according to the order you enter them. I assume you will be able to implement whatever scoring system you require. Also note that, unless you calculate a unique score for every request from a city, then which requests are denied may vary with the order of input.