1
$\begingroup$

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?
$\endgroup$
3
  • $\begingroup$ We could use more detail. Is it correct that all tours must be used? Do tours have time constraints (e.g., delivery windows), and do drivers and/or equipment have availability time windows? Are all driver - tractor - trailer combinations feasible? Lastly, what is your objective function? $\endgroup$
    – prubin
    Jan 19 at 17:27
  • $\begingroup$ Not all tours have to be used - just the "best" ones. Yes, the tours will have time constraints - which is making me a little nervous about whether my proposed 2-model solution is going to be appropriate. No - there are going to be significant constraints on driver - tractor - trailer combinations depending on the load. For the assignment model I am thinking about, the objective function could be something like # of resource hours accommodated. $\endgroup$
    – dkent
    Jan 19 at 17:47
  • $\begingroup$ @dkent, do you try solving the problem with an exact method or (meta) heuristics algorithm? In the first part, you described two heuristic methods, whereas in the second part it seems you are looking for an exact method? $\endgroup$
    – A.Omidi
    Jan 25 at 6:25

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.