VRP solution not fulfilling all added constraints

[oriolcosp]

Hi,

I've been trying to implement a VRP with breaks and I am having a hard time getting the solution to meet my constraints.
I have implemented breaks by adding a dimension and some constraints between that dimension and the time dimension. The constraints are the following:

1. Either there is a break (time slack >= BREAK_TIME and break slack == 10, this 10 is an arbitrary number but I need > 0 to track the breaks) or there isn't one (break slack == 0)
2. Breaks need to happen before a certain time (max_time_to_break)

My issue is that for some values of "max_time_to_break", the system seems to violate the constraints.

I am using Python 3.6.5 and ortools 7.4.7247.
Here is my code:

from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import pandas as pd

pd.set_option('display.max_rows', 500)
pd.set_option('display.max_columns', 500)
pd.set_option('display.width', 1000)

data = {}
data['time_matrix'] = [
  [0, 6, 9, 8, 7],
  [6, 0, 8, 3, 2],
  [9, 8, 0, 11, 10],
  [8, 3, 11, 0, 1],
  [7, 2, 10, 1, 0],
  ]
data['num_vehicles'] = 1
data['depot'] = 0
data['break_time']= 6
data['max_time_to_break'] = 9


manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']), data['num_vehicles'], data['depot'])
routing = pywrapcp.RoutingModel(manager)

def time_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['time_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(time_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
time = 'Time'
routing.AddDimension(
  transit_callback_index,
  1000,
  1000,
  False,
  time)

time_dimension = routing.GetDimensionOrDie(time)

solver = routing.solver()

#### Breaks
def breaks_callback(from_index, to_index):
    return 0

breaks_callback_index = routing.RegisterTransitCallback(breaks_callback)

routing.AddDimension(
  breaks_callback_index,
  1000,
  1000,
  True,
  'Breaks')

breaks_dimension = routing.GetDimensionOrDie('Breaks')

for i in range(data['num_vehicles']):
  start_index = routing.Start(i)
  solver.Add(breaks_dimension.SlackVar(start_index) == 0) # initialize breaks to 0
  
  end_index = routing.End(i)
  solver.Add(breaks_dimension.CumulVar(end_index) > 0) # force breaks > 0 at the end

# define breaks logic
for i in range(len(data['time_matrix'])):
    index = manager.NodeToIndex(i)
    solver.Add(
                (
                  (
                    (time_dimension.SlackVar(i)>=data['break_time']) *
                    (breaks_dimension.SlackVar(i)==10)
                  ) +
                  (breaks_dimension.SlackVar(i)==0)
                ) > 0
              ) # either (time slack >= data['break_time'] and breaks slack=10) or (breaks slack=0)
    solver.Add(((time_dimension.CumulVar(index)<data['max_time_to_break'])+(breaks_dimension.SlackVar(index)==0))>0) # time cumul < max or breaks slack=0

# adding slack and transit vars to assignment
for i in range(len(data['time_matrix'])):
    index = manager.NodeToIndex(i)
    routing.AddToAssignment(breaks_dimension.SlackVar(index))
    routing.AddToAssignment(breaks_dimension.TransitVar(index))
    routing.AddToAssignment(time_dimension.SlackVar(index))
    routing.AddToAssignment(time_dimension.TransitVar(index))
   

def print_all():
    def route_vehicle(vehicle_id):
        route = []
        index = routing.Start(vehicle_id)
        prev_index = -1
        route.append({'index': index})
        
        while not routing.IsEnd(index):
            prev_index = index
            index = assignment.Value(routing.NextVar(index))
            route.append({'index': index})
        
        for d in route:
            d['node'] = manager.IndexToNode(d['index'])
        
        time_dimension = routing.GetDimensionOrDie('Time')
        breaks_dimension = routing.GetDimensionOrDie('Breaks')
        for d in route:
            d['breaks_cumulvar'] = assignment.Value(breaks_dimension.CumulVar(d['index']))
            d['time_cumulvar'] = assignment.Value(time_dimension.CumulVar(d['index']))
            if (d['index'] < 5):
                d['time_slack'] = assignment.Value(time_dimension.SlackVar(d['index']))
                d['time_transit'] = assignment.Value(time_dimension.TransitVar(d['index']))
                d['breaks_slack'] = assignment.Min(breaks_dimension.SlackVar(d['index']))
                d['breaks_transit'] = assignment.Min(breaks_dimension.TransitVar(d['index']))
        return route
    
    all_routes = []
    for i in range(data['num_vehicles']):
        all_routes = all_routes + route_vehicle(i)
    all_routes_pd = pd.DataFrame.from_records(all_routes)
    all_routes_pd = all_routes_pd[['node', 'time_cumulvar', 'time_slack', 'time_transit', 'breaks_cumulvar', 'breaks_slack', 'breaks_transit']]
    print(all_routes_pd)

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.log_search = True
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_MOST_CONSTRAINED_ARC)
assignment = routing.SolveWithParameters(search_parameters)

print_all()

For data['max_time_to_break'] = 9, everything works fine and I get the following solution:

However, for data['max_time_to_break'] = 10 (or any value higher than 9):

Which doesn't make sense because the breaks_cumulvar increases wile breaks_slack and breaks_transit are both 0. This breaks the main relationship between dimensions of:
if j == NextVar(i), CumulVar(j) = CumulVar(i) + TransitVar(i) + SlackVar(i)

How can I fix the code so that for any value of max_time_to_break, it works as in the max_time_to_break=9 example?

Thanks in advance!

[mteixido]

I have checked the example and as oriolcosp says setting data['max_time_to_break'] = 10 generates an assignment that seems to violate the PathConstraint on Breaks dimension. Checking with assignment.Value() it reports that all the values of TransitVar, FixedTransitVar, SlackVar are 0 but CumSum is not always zero. Maybe I'm missing something very obvious but I don't find it.