I am trying to model a capacitated VRP model where the capacity is defined by the time the vehicle is available.

What I have:

  1. List of vehicles available and the time for which they are available
  2. List of points that need to be served and each point with a specific serving time

My approach:

I am trying to formulate a MIP assuming a centroid for each vehicle and then minimising the distance of these dropping points from that centroid. I have added the constraint that the total serving time shouldn't exceed the capacity of a vehicle. But here the problem is only serving time is being taken care of. I am unable to code the travel time which is kind of the TSP time for a vehicle.

How can this problem be encoded?

  • 2
    $\begingroup$ If vehicle $k$ is available for $T_k$ units of time, you need to add a resource constraint, for example $\sum_{i,j}t_{ij}x_{ij}\le T_k$, where $t_{ij}$ is the travel time between $i$ and $j$, and $x_{ij}$ is a binary variable that takes value $1$ iff vehicle serves $j$ right after $i$. $\endgroup$
    – Kuifje
    Commented Jan 31, 2023 at 12:44
  • 2
    $\begingroup$ I would tweak the constraint @Kuifje posed by making $t_{ij}$ the sum of the travel time from $i$ to $j$ plus the service time at $j.$ $\endgroup$
    – prubin
    Commented Jan 31, 2023 at 16:37
  • $\begingroup$ @Kuifje Thanks for the idea. But how to tie that to the objective function? As it is a minimization problem, only using this constraint will give xij==0 for all the cases. $\endgroup$ Commented May 3, 2023 at 9:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.