# Transportation Assignment Problem

A common variant consists of finding a minimum-weight perfect matching.

It is a specialization of the maximum weight matching problem for bipartite graphs.

The formal definition of the assignment problem (or linear assignment problem) is The problem is "linear" because the cost function to be optimized as well as all the constraints contain only linear terms.

The assignment problem can be solved by presenting it as a linear program.

However, we can solve it without the integrality constraints (i.e., drop the last constraint), using standard methods for solving continuous linear programs.

While this formulation allows also fractional variable values, in this special case, the LP always has an optimal solution where the variables take integer values.

The assignment problem can then be solved in the usual way and still give the best solution to the problem.

Similar adjustments can be done in order to allow more tasks than agents, tasks to which multiple agents must be assigned (for instance, a group of more customers than will fit in one taxi), or maximizing profit rather than minimizing cost.

The solution to the assignment problem will be whichever combination of taxis and customers results in the least total cost.

However, the assignment problem can be made rather more flexible than it first appears.