Minimizing the cost of vehicles in CVRP problem using cp_model

[Nazanin Moarref]

Hi,

I have implemented a CVPR problem using OR-Tools' CP-SAT solver, and while the solver status is optimal, the results are not as expected. Ideally, the output should be 1 vehicle with a capacity of 20 (serving 17 demands) and a cost of 3. However, the solver assigns two vehicles: one with a capacity of 10 (serving 2 demands, cost 4) and another with a capacity of 20 (serving 15 demands, cost 3), resulting in a total cost of 7.

Could you please help me understand why this happens? Any insights into why the solver is not producing the expected optimal result would be greatly appreciated. Thank you!

Here is the code:

from ortools.sat.python import cp_model

import matplotlib.pyplot as plt # Data visualization

import random

import numpy as np

import pandas as pd

# parameters

data = {}

data['distance_matrix'] = [

[0, 2, 9, 10, 11],

[2, 0, 6, 4, 8],

[9, 6, 0, 7, 5],

[10, 4, 7, 0, 3],

[11, 8, 5, 3, 0]

]

data['demands'] = [0, 2, 4, 5, 6] # Demand at each location (including depot)

data['vehicle_capacities'] = [10,20,20] # Capacity of each vehicle

data['num_vehicles'] = len(data['vehicle_capacities'])

data['depot'] = 0

data['vehicle_costs'] = [4,3,7]

num_locations = len(data['distance_matrix'])

num_vehicles = data['num_vehicles']

depot = data['depot']

model = cp_model.CpModel()

# Variables

x = {}

for i in range(num_locations):

for j in range(num_locations):

for k in range(num_vehicles):

x[(i, j, k)] = model.NewBoolVar(f'x[{i},{j},{k}]')

u = {}

for i in range(num_locations):

u[i] = model.NewIntVar(0, sum(data['demands']), f'u[{i}]')

# Vehicle usage variable

vehicle_used = [model.NewBoolVar(f'vehicle_used[{k}]') for k in range(num_vehicles)]

# Constraints

# Each customer is visited exactly once by exactly one vehicle:

for i in range(1, num_locations):

model.Add(sum(x[(i, j, k)] for j in range(num_locations) for k in range(num_vehicles) if i != j) == 1)

for k in range(num_vehicles):

model.Add(sum(x[(depot, j, k)] for j in range(1, num_locations)) <= 1) # Each vehicle can leave the depot at most once:

model.Add(sum(x[(i, depot, k)] for i in range(1, num_locations)) <= 1) # Each vehicle can return to the depot at most once:

# If a vehicle is used, it must leave the start location

for k in range(num_vehicles):

expressions = sum(x[(depot, j, k)] for j in range(1, num_locations) )

model.Add(vehicle_used[k] == expressions )

# Flow conservation (each vehicle that enters a node must leave it):

for k in range(num_vehicles):

for h in range(num_locations):

model.Add(sum(x[(i, h, k)] for i in range(num_locations) if i != h) == sum(x[(h, j, k)] for j in range(num_locations) if h != j))

# Subtour elimination (MTZ constraints):

for k in range(num_vehicles):

for i in range(1, num_locations):

for j in range(1, num_locations):

if i != j:

model.Add(u[i] - u[j] + sum(data['demands']) * x[(i, j, k)] <= sum(data['demands']) - data['demands'][j])

# Vehicle capacity constraints:

for k in range(num_vehicles):

for i in range(1, num_locations):

model.Add(u[i] <= data['vehicle_capacities'][k])

#Load of the vehicle after visiting a node cannot exceed vehicle capacity:

for k in range(num_vehicles):

model.Add(sum(data['demands'][i] * sum(x[(i, j, k)] for j in range(num_locations) if i != j) for i in range(num_locations)) <= data['vehicle_capacities'][k])

# Objective: minimize the total distance traveled by all vehicles and minimize the total cost of vehicles used

objective_terms = []

for k in range(num_vehicles):

for i in range(num_locations):

for j in range(num_locations):

if i != j:

objective_terms.append(data['distance_matrix'][i][j] * x[(i, j, k)])

objective_terms.append(data['vehicle_costs'][k] * vehicle_used[k]) # Add the vehicle cost to the objective

model.Minimize(sum(objective_terms))

solver = cp_model.CpSolver()

status = solver.Solve(model)

all_routes = []

route_dic = {}

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:

print('Total distance = ', solver.ObjectiveValue())

for k in range(num_vehicles):

if solver.BooleanValue(vehicle_used[k]):

index = depot

route = [index]

while True:

next_index = -1

for j in range(num_locations):

if index != j and solver.BooleanValue(x[(index, j, k)]):

next_index = j

break

if next_index == depot or next_index == -1:

break

route.append(next_index)

index = next_index

route.append(depot)

d = []

print(f'Route for vehicle {k}: ' + ' -> '.join(map(str, route)))

all_routes.append(route)

route_dic[k] = route

cap = data['vehicle_capacities'][k]

print(f' cap: {cap} ')

for i in route:

d.append(data['demands'][i])

print(data['demands'][i])

cost = data['vehicle_costs'][k]

print(f'cost: {cost}')

print( f'total demand {sum(d)}' )

print('ends')

else:

print('No solution found!')

[Laurent Perron]

why not use the routing constraints ?

https://github.com/google/or-tools/blob/stable/examples/python/prize_collecting_vrp_sat.py for instance.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/d5bf9b57-04d5-4b17-b4e2-7d46f672811en%40googlegroups.com.

[Kyle Booth]

Your "Vehicle capacity constraints" is actually constraining the load at a location to be less than the minimum capacity across all of your vehicles. If you remove this constraint it finds the single vehicle solution.

So I think you need to modify this constraint so it is not so restrictive.