I am starting a project which involves an allocation problem, and having explored a bit by myself, it is pretty challenging for me to solve it efficiently.

What I call here allocation problem is the following:

• There is a set of available slots in 3D space, randomly sampled ([xspot_0, yspot_0, zspot_0], [xspot_1, yspot_1, zspot_1], etc.). These slots are identified with an ID and a position, and are fixed, so they will not change with time.
• There are then mobile elements (same number as the number of available slots, on the order of 250,000) which can go from spot to spot. They are identified with an ID, and at a given time step, the spot in which they are.
• Each spot must have one and only one element at a given step.
• At first, elements are ordered in the same way as spots: the first element (element_id=0) is in the first spot (spot_id=0), etc.
• But then, these elements need to move, based on a motion vector that is defined for each spot, which is also fixed. For example, ideally at the first step, the first element should move from [xspot_0, yspot_0, zspot_0] to [xspot_0 + dxspot_0, yspot_0 + dyspot_0, zspot_0 + dzspot_0], etc.
• Since spots were randomly sampled, the new target position might not exist among the spots. The goal is therefore to find a candidate slot for the next step that is as close as possible to the "ideal" position the element should be in.
• On top of that first challenge, since this will probably be done through a loop, it is possible that the best candidate was already assigned to another element.
• Once all new slots are defined for each element (or each element is assigned to a new slot, depending on how you see it), we do it again, applying the same motion with the new order. This is repeated as many times as I need.

Now that I defined the problem, the first thing I tried was a simple allocation based on this information. However, if I pick the best candidate every time based on the distance to the target position, as I said some elements have their best candidate already taken, so they pick the 2nd, 3rd, ... 20th, ... 100th candidate slot, which becomes highly wrong compared to the ideal position.

Another technique I was trying, without being entirely sure about what I was doing, was to assign a probability distribution calculated by doing the inverse exponential of the distance between the slots and the target position. Then I normalized this distribution to obtain probabilities (which seem arbitrary). I still do not get very good results for a single step.

Therefore, I was wondering if someone knows how to solve this type of problem in a more accurate/more efficient way. For your information, I mainly use Python 3 for development.

Thank you!