VRP Variants

The Generalized Assignment Problem (GAP)

The GAP consists of optimally assigning a set $I = {1, …, m}$ of tasks to a set $J = {1, …, n}$ of agents. Each task must be performed by exactly one agent, and each agent has a limited resource capacity. Mathematically, the problem can be formulated as follows:

min $sum over i,j of c_ij x_ij$

s.t.: $resource capacity constraints$

$each task assigned to exactly one agent$

$x_ij binary$

Here $c_ij$ is the cost of assigning task i to agent j, $b_j$ is agent j's capacity, and $a_ij$ denotes the amount of resource required by agent j to perform task i. The binary variable $x_ij$ equals 1 if agent j performs task i and 0 otherwise. When processing the tasks requires more than one type of resource, the problem is known as the multi-resource GAP.

The GAP is NP-hard, and it appears naturally inside vehicle routing: assigning customers to vehicles (or to depots, or to days) is a generalized assignment problem, which is why GAP models arise as subproblems in many VRP construction heuristics, Lagrangian relaxation schemes, and route-first/cluster-second and cluster-first/route-second decompositions.

See also: Bin Packing Problem · VRP formulation · P and NP classes