# A 'capacitated' VRP model where the capacity constraint is the time

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?

• 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$. Commented Jan 31, 2023 at 12:44
• 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.$
– prubin
Commented Jan 31, 2023 at 16:37
• @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. Commented May 3, 2023 at 9:55