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?

CodePudding user response：

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

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

CodePudding user response：

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.