Solving a VRP variant with time constraints

Question

I am trying to solve a VRP variant where I have a list of vehicles. If a vehicle is used/rented, a cost will be incurred. If not, there will be no cost.

And even if a vehicle is rented, it can only be used for a certain given time.

I am trying to formulate the problem like this.

\begin{align*} \text{Minimize:} \quad & \sum_{j=1}^{m} \text{vehicle_rent_cost}[j] * y[j] \\ \text{Subject to:} \quad & \\ & \sum_{i=1}^{n} x[i, j] = 1 \quad \forall j = 1 \text{ to } m \\ & x[i, j] \leq y[j] \quad \forall i = 1 \text{ to } n, \quad \forall j = 1 \text{ to } m \\ & \sum_{a=1}^{n} \sum_{b=1}^{n} \text{total_time_matrix}[a, b] * v[a, b] \leq \text{vehicle_rent_time} \quad \forall j = 1 \text{ to } n \\ & \sum_{i=1}^{n} \text{cell_demand_kg}[i] * x[i, j] \leq \text{vehicle_capacity_kg}[j] * y[j] \quad \forall i = 1 \text{ to } n, \quad \forall j = 1 \text{ to } m \\ & \sum_{i=1}^{n} \text{cell_demand_cft}[i] * x[i, j] \leq \text{vehicle_capacity_cft}[j] * y[j] \quad \forall i = 1 \text{ to } n, \quad \forall j = 1 \text{ to } m \\ \end{align*}

Where:

n be the number of cells.

m be the number of vehicles.

x[i, j] be a binary variable indicating whether cell i is assigned to vehicle j.

y[j] be a binary variable indicating whether vehicle j is used.

v[a, b] be a binary variable indicating whether cell b is served after cell a.

vehicle_rent_cost[j] be the cost of renting vehicle j.

total_time_matrix[a, b] be the time to travel from cell a to cell b, after serving cell a.

vehicle_rent_time be the total available time for a vehicle.

cell_demand_kg[i] be the demand in kilograms for cell i.

vehicle_capacity_kg[j] be the capacity in kilograms of vehicle j.

cell_demand_cft[i] be the demand in cubic feet for cell i.

vehicle_capacity_cft[j] be the capacity in cubic feet of vehicle j.

But this is clearly wrong. v[a,b] will always be 0.

How can I formulate the problem in a better way?

Answer 1

What is the incentive for using the vehicles? Nothing in your model requires that any demand be satisfied, so the cheapest solution clearly is to do nothing. If you are required to meet cell demands, you need a constraint to enforce that.

Answer 2

You'd need precedence constraints like

(1) $ x_{a,j} \le x_{b,j} \ \forall j \ \ \forall (a,b) \in$ Time matrix
Precedence constraint if travelling from $ b -> a$

(2) $\sum_b v_{a,b}^j \le x_{a,j} \ \ \forall a,j$

(3) $\sum_av_{a,b}^j \le x_{b,j} \ \ \forall j, b$

(4) $x_{a,j} + x_{b,j} \le v_{a,b}^j + 1 \ \ \forall a,b,j$

Then in the constraint for total vehicle rent time you may need to sum $v_{a,b}^j$ for vehicles $j$ if it's total rent time of all vehicles.

Alternatively instead of $v_{a,b}$ being binary you can make it nonnegative continuous if it's only to be used in constraint to compute time of travel for vehicle $j$ and update constraints (2)-(4) as $t_{a,b}(x_{a,j}+x_{b,j}-1) \le v_{a,b}^j \le t_{a,b}x_{b,j}$

$0 \le v_{a,b}^j $

Then in the total rent time constraint just use $ \sum_j v_{a,b}^j$ instead of time parameter