Task Assignment Problem using MILP (tasks >> agents)

Question

I have a general assignment problem that assigns a set of payload tasks $T$ to a set of workers $A$, where $|T|$ >> $|A|$. Each task $T_i \in T$ consists of a tuple $(s_i, g_i)$, which represent the start and goal position of the task.

I would like a MILP formulation, similar to that which is used for the Hungarian Algorithm, for this problem that I can use something like Gurobi to solve. Here are some assumptions I am making:

• Agents start at the position of their first assigned task. Thus, there is no assigned cost for an agent starting their first task.
• All distances from any position can be efficiently calculated.
• Agents need not be assigned the same number of tasks and all agents need not be used to solve the set of tasks
• A task can only completed by a single agent once. Tasks are not repeated or split amongst agents.

My biggest problem is figuring out how to incorporate the cost of traveling from one task to another. For example, if agent $A_i$ is assigned tasks $T_j$ and $T_k$, then we need to consider the cost of traveling from the goal of $T_j$ to the start of $T_k$.

I am not well-versed with generating these types of MILPs, could I get some assistance with the formulation? This is what I have so far, but I know it is not complete and missing the ordering of tasks. How would you encode task ordering?

For the below formulation, assume we have a total of $n$ agents, $m$ tasks, $i$ is used to index agents, and $j$ is used to index tasks.

\begin{align*} min \sum_{i,j} c_{i,j} x_{i,j} \\ \sum_i x_{i,j} = 1 \ \ \forall j \\ 0 \leq x_{i,j} \leq 1 \\ \end{align*}

Answer 1

I recommend a network-based formulation in a directed network defined as follows. Each task is a node, and there is a directed arc from task $T_j$ to task $T_k$ if it is possible for a single agent to perform $T_j$ and then $T_k$. There is also a source node, with supply $n$, and an arc from the source to each task. Similarly, there is a sink node, with demand $n$, and an arc from each task node to the sink. Finally, introduce an arc from source to sink. You have a nonnegative integer flow variable for each arc and two linear constraints for each task node: the incoming flow equals 1, and the outgoing flow equals 1.