Assignment Problems With More than One Class of Resource

Question

I am working on a dispatch optimization problem in the trucking industry.

I have a first algorithm - a vehicle routing algorithm - that produces a series of tours.

I will need a second algorithm that assigns the tours resulting from the first algorithm to individual drivers, tractors and trailers (i.e. three different kinds of resources). I believe that the second algorithm would need to be (essentially) an assignment problem algorithm.

Here are my questions

1. What is the name for the kind of assignment problem where more than one different kind or class of resource needs to be assigned to tasks?
2. I believe that one approach to the design of the assignment problem would be to have a binary decision variable for each task / resource / hour-of-the-day combination. I'm thinking this approach is going to be computationally expensive. Are there alternative approaches to this part of the design that might be less computationally expensive?

Answer 1

I don't know a particular name for this type of problem. Depending on the specifics of the problem, the following approach might work. Use binary variables $x_{dr}$ indicating whether driver $d$ is assigned to route $r$, $y_{tr}$ indicating whether tractor $t$ is assigned to route $r$, and $z_{tr}$ indicating whether trailer $t$ is assigned to route $r$. If you need to know whether a route was assigned, add binary variables $w_r$ for each route $r$.

• Constraints to limit how many times a driver, tractor or trailer is used are obvious.
• If a driver, tractor or trailer cannot be used on a given route, just eliminate the corresponding variable, or set it to zero.
• It probably will be unnecessary to prevent the model from assigning drivers or equipment to unused routes, but if it is needed, you can just add constraints $\sum_d x_{dr} = w_r$ for each route $r$ and similarly for trailers and tractors. (I'm assuming each route is driven at most once.)
• If you need to weed out certain combinations (e.g., driver 7 and tractor 3 can both be used on route 5, but driver 7 cannot drive tractor 3 on route 5), those are easily handled. For my example, the constraint might be $$x_{75} + y_{35} \le 1.$$If a particular combination cannot be used on any route, just iterate the constraint over all routes.

Not knowing full details of the problem, I'll stop there.