Indexes seem to be off when comparing cumulvars

[bcoghe]

So, i'm trying to add pickup and delivery constraints (which works) with the following function:

def add_pickup_delivery(routing, p_idx, d_idx, data, distance_evaluator):
    pickup = routing.NodeToIndex(p_idx)
    delivery = routing.NoteToIndex(d_idx)
    routing.AddPickupAndDelivery(pickup, delivery)
    routing.solver().Add(routing.CumulVar(pickup, "Distance") < routing.CumulVar(delivery, "Distance"))
    routing.solver().Add(routing.VehicleVar(pickup) ==  routing.VehicleVar(delivery))
    return routing

This works fine. Now I have an additional constraint that the delivery time is max a certain time later than the pickup (in this case a certain distance, because my speed = 1).

What i thought would be working is:

routing.solver().Add(routing.CumulVar(delivery_idx, "Distance") <= routing.CumulVar(pickup_idx, "Distance") + 25)

This works fine with 2 vehicles, the depot at (10,10) and locations (5,5) for pickup and delivery at (15,10)

Now, when adding an extra pickup at (7,8) and delivery at (17,17). No solution is found anymore. But there are 2 vehicles, so the second route shouldn't even influence the first one. When increasing 25 to 33 it starts working (32 does not work). The solution then is:

Route for vehicle 0: 0 distance:0-> 1 distance:10-> 2 distance:25-> 0 distance:30Distance of the route 0: 30

Route for vehicle 1: 0 distance:0-> 3 distance:5-> 4 distance:24-> 0 distance:38Distance of the route 1: 38

Total Distance of all routes: 68

Also when I change (17,17) from the second delivery to (13,13) it starts working with a lower number than 33.. So I am guessing that the wrong index is used to add a constraint or something. Any help?

[bcoghe]

update: it looks like the constraint is being set on both vehicles. In the first vehicle on the distance between node 1 and node 2. In the second vehicle between node 3 and the end depot..

even when disabling the pickup and delivery i get a solution like this:

Route for vehicle 0:
0  distance:0-> 4  distance:14-> 0 distance:28
Distance of the route 0: 28

Route for vehicle 1:
0  distance:0-> 3  distance:5-> 1  distance:10-> 2  distance:25-> 0 distance:30
Distance of the route 1: 30

Total Distance of all routes: 58

but when i use 32 for the one contraint it gives no solution. With 33 or higher it does. No node even goes above 30..

[Mizux]

Can you share the full code to reproduce the error thanks.

[bcoghe]

"""Vehicle Routing Problem"""
from __future__ import print_function
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline

###########################
# Problem Data Definition #
###########################
class CityBlock():
    """City block definition"""
    @property
    def width(self):
        """Gets Block size West to East"""
        return 1

    @property
    def height(self):
        """Gets Block size North to South"""
        return 1
    

def create_city():
    return (np.random.randint(20),np.random.randint(20))

def create_locations(nr_cities):
    locations = []
    for i in range(nr_cities):
        locations.append(create_city())
    return locations

def plot_cities(cities, sign):
    plt.plot([cities[i][0] for i in range(len(cities))],[cities[i][1] for i in range(len(cities))],sign) 

locations = [(10, 10)] + [(5,5), (15,10)
                       ,(7,8), (17,17)
                         ]
plot_cities(locations[1:], 'o')
plot_cities(locations[:1], 'x')

class DataProblem():
    """Stores the data for the problem"""
    def __init__(self, locations):
        """Initializes the data for the problem"""
        self._num_vehicles = 2
        self.start_locations = [0,0]
        self.end_locations = [0,0]

        # locations in meters using the city block dimension
        city_block = CityBlock()
        self._locations = [(
            loc[0]*city_block.width,
            loc[1]*city_block.height) for loc in locations]

        self._depot = 0
    
    

    @property
    def num_vehicles(self):
        """Gets number of vehicles"""
        return self._num_vehicles

    @property
    def locations(self):
        """Gets locations"""
        return self._locations

    @property
    def num_locations(self):
        """Gets number of locations"""
        return len(self.locations)

    @property
    def depot(self):
        """Gets depot location index"""
        return self._depot

#######################
# Problem Constraints #
#######################
def manhattan_distance(position_1, position_2):
    """Computes the Manhattan distance between two points"""
    return (abs(position_1[0] - position_2[0]) +
            abs(position_1[1] - position_2[1]))

class CreateDistanceEvaluator(object): # pylint: disable=too-few-public-methods
    """Creates callback to return distance between points."""
    def __init__(self, data):
        """Initializes the distance matrix."""
        self._distances = {}

        # precompute distance between location to have distance callback in O(1)
        for from_node in xrange(data.num_locations):
            self._distances[from_node] = {}
            for to_node in xrange(data.num_locations):
                if from_node == to_node:
                    self._distances[from_node][to_node] = 0
                else:
                    self._distances[from_node][to_node] = (
                        manhattan_distance(
                            data.locations[from_node],
                            data.locations[to_node]))

    def distance_evaluator(self, from_node, to_node):
        """Returns the manhattan distance between the two nodes"""
        return self._distances[from_node][to_node]

def add_distance_dimension(routing, distance_evaluator):
    """Add Global Span constraint"""
    distance = "Distance"
    maximum_distance = 3000
    routing.AddDimension(
        distance_evaluator,
        0, # null slack
        maximum_distance, # maximum distance per vehicle
        True, # start cumul to zero
        distance)
    distance_dimension = routing.GetDimensionOrDie(distance)
    distance_dimension.SetGlobalSpanCostCoefficient(100)
    
def add_pickup_delivery(routing, p_idx, d_idx, data, distance_evaluator):
    routing.AddPickupAndDelivery(routing.NodeToIndex(p_idx), routing.NodeToIndex(d_idx))
    routing.solver().Add(routing.CumulVar(routing.NodeToIndex(p_idx), "Distance") < routing.CumulVar(routing.NodeToIndex(d_idx), "Distance"))
    routing.solver().Add(routing.VehicleVar(routing.NodeToIndex(p_idx)) == routing.VehicleVar(routing.NodeToIndex(d_idx)))
    return routing
    

###########
# Printer #
###########
class ConsolePrinter():
    """Print solution to console"""
    def __init__(self, data, routing, assignment):
        """Initializes the printer"""
        self._data = data
        self._routing = routing
        self._assignment = assignment

    @property
    def data(self):
        """Gets problem data"""
        return self._data

    @property
    def routing(self):
        """Gets routing model"""
        return self._routing

    @property
    def assignment(self):
        """Gets routing model"""
        return self._assignment
    
    def draw_solution(self, solution):
        solution_cities = []
        for i in solution:
            solution_cities.append(self.data.locations[int(i)])
        plt.plot([solution_cities[i][0] for i in range(len(solution_cities))],
                 [solution_cities[i][1] for i in range(len(solution_cities))],'-o') 

    def print(self):
        """Prints assignment on console"""
        # Inspect solution.
        total_dist = 0
        for vehicle_id in xrange(self.data.num_vehicles):
            index = self.routing.Start(vehicle_id)
            plan_output = 'Route for vehicle {0}:\n'.format(vehicle_id)
            route_dist = 0
            solution = []
            distance_dimension = self.routing.GetDimensionOrDie("Distance")
            while not self.routing.IsEnd(index):
                node_index = self.routing.IndexToNode(index)
                next_node_index = self.routing.IndexToNode(
                    self.assignment.Value(self.routing.NextVar(index)))
                route_dist += manhattan_distance(
                    self.data.locations[node_index],
                    self.data.locations[next_node_index])
                plan_output += ' {node_index}  '.format(
                    node_index=node_index)
                plan_output += "distance:" + str(self.assignment.Value(distance_dimension.CumulVar(index))) + '->'
                solution.append(int(node_index))            
                index = self.assignment.Value(self.routing.NextVar(index))

            node_index = self.routing.IndexToNode(index)
            total_dist += route_dist
            plan_output += ' {node_index}\n'.format(
                node_index=node_index)
            plan_output += "distance:" + str(self.assignment.Value(distance_dimension.CumulVar(index)))
            solution.append(int(node_index))
            plan_output += 'Distance of the route {0}: {dist}\n'.format(
                vehicle_id,
                dist=route_dist)
            print(plan_output)
            self.draw_solution(solution)
        print('Total Distance of all routes: {dist}'.format(dist=total_dist))
        
def plot_cities(cities, sign):    
    plt.plot([cities[i][0] for i in range(len(cities))],[cities[i][1] for i in range(len(cities))],sign)   

########
# Main #
########
def main():    
    """Entry point of the program"""
    # Instantiate the data problem.
    data = DataProblem(locations)
    cities = data.locations[1:]
    plot_cities(cities, 'o')
    depots = data.locations[:1]
    plot_cities(depots, 'x')

    # Create Routing Model    
    routing = pywrapcp.RoutingModel(data.num_locations, data.num_vehicles, data.start_locations, data.end_locations)
    # Define weight of each edge
    distance_evaluator = CreateDistanceEvaluator(data).distance_evaluator
    routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
    add_distance_dimension(routing, distance_evaluator)
    routing = add_pickup_delivery(routing, 1, 2, data, distance_evaluator)
    routing = add_pickup_delivery(routing, 3, 4, data, distance_evaluator)
    dist = routing.GetDimensionOrDie("Distance")
    routing.solver().Add(dist.CumulVar(2) - dist.CumulVar(1) <=33)
    # Setting first solution heuristic (cheapest addition).
    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC)
    search_parameters.local_search_metaheuristic= routing_enums_pb2.LocalSearchMetaheuristic.AUTOMATIC
    # Solve the problem.
    assignment = routing.SolveWithParameters(search_parameters)
    printer = ConsolePrinter(data, routing, assignment)
    printer.print()

if __name__ == '__main__':
  main()

[bcoghe]

Trying to attach the jupyter notebook, but that does not work. And accidentally closed the issue :/

[Mizux]

At the end in the main function, you must replace

routing.solver().Add(dist.CumulVar(2) - dist.CumulVar(1) <=33)

by

routing.solver().Add(dist.CumulVar(routing.NodeToIndex(2)) - dist.CumulVar(routing.NoteToIndex(1)) <=33)

CumulVar takes an Index not NodeIndex...
src: https://github.com/google/or-tools/blob/master/ortools/constraint_solver/routing.h#L1381

[bcoghe]

Doesn't change anything. Tried it.. the same problem stays. When changing the value to 32 it stops working, no solution is found

[bcoghe]

[bcoghe]

One more example without pickup and delivery on node 3 and 4:

Problem is again from 33 to 32 while both routes are not even that long..

[Mizux]

Using
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
works. It seems the AUTOMATIC FirstSolutionStrategy can't find a first solution...

#!/usr/bin/env python

"""Vehicle Routing Problem"""
from __future__ import print_function
from collections import namedtuple
from six.moves import xrange
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
#import matplotlib.pyplot as plt

###########################
#Problem Data Definition #
###########################
# City block declaration
CityBlock = namedtuple('CityBlock', ['width', 'height'])

#def plot_cities(cities, sign):
#  """Display Depot and Cities in a plot"""
#  plt.plot([cities[i][0] for i in range(len(cities))],
#           [cities[i][1] for i in range(len(cities))],
#           sign)

LOCATIONS = [
    (10, 10), # depot
    (5, 5), # loc1
    (15, 10), # loc2
    (7, 8), # loc3
    (17, 17) # loc4
    ]

class DataProblem():
  """Stores the data for the problem"""
  def __init__(self, locations):
    """Initializes the data for the problem"""
    self._num_vehicles = 2
    self._depots = [0,0]
    #Compute locations in meters using the block dimension defined as follow
    #Manhattan average block : 750ft x 264ft->228m x 80m
    #here we use : 114m x 80m city block
    #src : https:  // nyti.ms/2GDoRIe "NY Times: Know Your distance"
    city_block = CityBlock(width=1, height=1)
    self._locations = [(
        loc[0] * city_block.width,
        loc[1] * city_block.height) for loc in locations]

  @property
  def num_vehicles(self):
    """Gets number of vehicles"""
    return self._num_vehicles

  @property
  def locations(self):
    """Gets locations"""
    return self._locations

  @property
  def num_locations(self):
    """Gets number of locations"""
    return len(self.locations)

  @property
  def depots(self):
    """Gets depot location index"""
    return self._depots

#######################
#Problem Constraints #
#######################
def manhattan_distance(position_1, position_2):
  """Computes the Manhattan distance between two points"""
  return (abs(position_1[0] - position_2[0]) +
          abs(position_1[1] - position_2[1]))

class CreateDistanceEvaluator(object): # pylint: disable=too-few-public-methods
  """Creates callback to return distance between points."""
  def __init__(self, data):
    """Initializes the distance matrix."""
    self._distances = {}

#precompute distance between location to have distance callback in O(1)
    for from_node in xrange(data.num_locations):
      self._distances[from_node] = {}
      for to_node in xrange(data.num_locations):
        if from_node == to_node:
          self._distances[from_node][to_node] = 0
        else:
          self._distances[from_node][to_node] = (
              manhattan_distance(
                  data.locations[from_node],
                  data.locations[to_node]))

  def distance_evaluator(self, from_node, to_node):
    """Returns the manhattan distance between the two nodes"""
    return self._distances[from_node][to_node]

def add_distance_dimension(routing, distance_evaluator):
  """Add Global Span constraint"""
  distance = "Distance"
  maximum_distance = 3000
  routing.AddDimension(
          distance_evaluator,
          0, # null slack
          maximum_distance, # maximum distance per vehicle
          True, # start cumul to zero
          distance)
  distance_dimension = routing.GetDimensionOrDie(distance)
  distance_dimension.SetGlobalSpanCostCoefficient(100)

def add_pickup_delivery(routing, p_idx, d_idx, data, distance_evaluator):
  routing.AddPickupAndDelivery(routing.NodeToIndex(p_idx), routing.NodeToIndex(d_idx))
  routing.solver().Add(routing.CumulVar(routing.NodeToIndex(p_idx), "Distance") < routing.CumulVar(routing.NodeToIndex(d_idx), "Distance"))
  routing.solver().Add(routing.VehicleVar(routing.NodeToIndex(p_idx)) == routing.VehicleVar(routing.NodeToIndex(d_idx)))

###########
# Printer #
###########
def print_solution(data, routing, assignment):
  """Prints assignment on console"""
  print('Objective: {}'.format(assignment.ObjectiveValue()))
  total_distance = 0
  distance_dimension = routing.GetDimensionOrDie('Distance')
  for vehicle_id in xrange(data.num_vehicles):
    index = routing.Start(vehicle_id)
    plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
    distance = 0
    while not routing.IsEnd(index):
      previous_index = index
      index = assignment.Value(routing.NextVar(index))
      dst = routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
      distance += dst
      plan_output += ' {} --({}m)--> '.format(routing.IndexToNode(previous_index), dst)
    plan_output += ' {}\n'.format(routing.IndexToNode(index))
    plan_output += 'Distance of the route: {}m\n'.format(distance)
    print(plan_output)
    total_distance += distance

  print('Total Distance of all routes: {}m'.format(total_distance))

########
# Main #
########
def main():
  """Entry point of the program"""
#Instantiate the data problem.
  data = DataProblem(LOCATIONS)
  #cities = data.locations[1:]
  #plot_cities(cities, 'o')
  #depots = data.locations[:1]
  #plot_cities(depots, 'x')

#Create Routing Model
  routing = pywrapcp.RoutingModel(
      data.num_locations,
      data.num_vehicles,
      data.depots,
      data.depots)
#Define weight of each edge
  distance_evaluator = CreateDistanceEvaluator(data).distance_evaluator
  routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
#Add Pickup & Delivery constraint
  add_distance_dimension(routing, distance_evaluator)
  add_pickup_delivery(routing, 1, 2, data, distance_evaluator)
  add_pickup_delivery(routing, 3, 4, data, distance_evaluator)
  distance_dimension = routing.GetDimensionOrDie("Distance")
  routing.solver().Add(
      distance_dimension.CumulVar(routing.NodeToIndex(2)) -
      distance_dimension.CumulVar(routing.NodeToIndex(1)) <= 15)
  # 14 not working which is expected
#Setting first solution heuristic(cheapest addition).
  search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
  search_parameters.first_solution_strategy = (
      routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
#  search_parameters.first_solution_strategy = (
#      routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC)
  search_parameters.local_search_metaheuristic= routing_enums_pb2.LocalSearchMetaheuristic.AUTOMATIC
#Solve the problem.
  assignment = routing.SolveWithParameters(search_parameters)
  print_solution(data, routing, assignment)

if __name__ == '__main__':
  main()

and got:

[0]─[/tmp/plop]
[^v^]─mizux@mizux %./plop.py
Objective: 3868
Route for vehicle 0:
 0 --(5m)-->  3 --(19m)-->  4 --(14m)-->  0
Distance of the route: 38m

Route for vehicle 1:
 0 --(10m)-->  1 --(15m)-->  2 --(5m)-->  0
Distance of the route: 30m

Total Distance of all routes: 68m

ps: I have to tweak a little your program to make it run on my side. (I can't install python3-tk which is a dependency of matplotlib)

[Mizux]

Currently, you need to test several first solution strategies to help the solver if it can't find a solution in some cases. You can also make some nodes optional so FST (Fisrt Solution Strategy) will found a solution easily then use the LNS (Local Neighborhood Search) to optimize it...

If i remember well (cf #658 (comment)) AUTOMATIC will use PARALLEL_CHEAPEST_INSERTION so each time you add a new node (or move one) this can influence the FST search path.

I'm closing this issue since there is no more issue concerning "Indexes seem to be off when comparing cumulvars" please use my last code as reference for correctly using NodeToIndex() and IndexToNode().
TLDR: Nearly all methods use Index as input (CumulVar(), SlackVar(), NextVar(), GetArcCostForVehicle()) or return Index (Start(), End()) the noteworthy exception being the NodeEvaluator2 callback (taking two NodeIndex) which is understandable since your data model must use NodeIndex

You can create a new issue concerning the "bad" performance of the FST when using AUTOMATIC (i.e. no solution found).
note: There have been some improvements internally on the FST implementation, hope to backport it on GitHub by the end of 2018.