title: VRPTW: How to handle time windows and slacks for the special depot node?
body: <p>I find reading all values of an assignment, obtained from</p>
  
  <pre><code>assignment = routing.SolveWithParameters(search_params)
  </code></pre>
  
  <p>of routing problems with time windows quiet tricky. First of all, there are nodes and indices. I obtain the indices of a vehicle (route) via</p>
  
  <pre><code>index = routing.Start(vehicle)
  indices = [index]
  while not routing.IsEnd(index):
      index = assignment.Value(routing.NextVar(index))
      indices.append(index)
  </code></pre>
  
  <p>and the corresponding nodes are obtained by</p>
  
  <pre><code>nodes = [routing.IndexToNode(x) for x in indices]
  </code></pre>
  
  <p>For a particular routing problem with 5 stops and <code>depot=0</code> the solver finds an assignment with the following indices and nodes:</p>
  
  <pre><code>vehicle: 0
  indices: [0, 1, 6]
  nodes:   [0, 1, 0]
  
  vehicle: 1
  indices: [5, 4, 3, 2, 7]
  nodes:   [0, 4, 3, 2, 0]
  </code></pre>
  
  <p>So there are three more indices than nodes, because each vehicle starts and ends in the depot. I have defined a cost of 1 for every transit and reading the cost values via</p>
  
  <pre><code>cost_dimension = routing.GetDimensionOrDie("cost")
  cost_vars = [cost_dimension.CumulVar(x) for x in indices]
  costs = [assignment.Value(x) for x in cost_vars]
  </code></pre>
  
  <p>seems to work:</p>
  
  <pre><code>vehicle: 0
  indices: [0, 1, 6]
  nodes:   [0, 1, 0]
  costs:   [0, 1, 2]
  
  vehicle: 1
  indices: [5, 4, 3, 2, 7]
  nodes:   [0, 4, 3, 2, 0]
  costs:   [0, 1, 2, 3, 4]
  </code></pre>
  
  <p>But when I add time constraints I run into problems. Let's first look at the code that defines the problem. The time unit is minutes.</p>
  
  <pre><code>def time_function(x,y):
      return 30
  
  evaluator = time_function
  slack_max = 40
  capacity = 24*60
  fix_start_cumul_to_zero = False
  name = "time"
  routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)
  time_dimension = routing.GetDimensionOrDie("time")
  
  time_windows = [(7*60, 8*60),(9*60, 10*60),(9*60, 10*60),
                  (9*60, 10*60),(9*60, 10*60)]
  for node, time_window in enumerate(time_windows):
      time_dimension.CumulVar(node).SetRange(time_window[0], time_window[1])
      routing.AddToAssignment(time_dimension.SlackVar(node))
  </code></pre>
  
  <p>So each trip takes 30 minutes, vehicles may be idle at a stop for 40 minutes (<code>slack_max=40</code>) and each stop should be serviced between 9am and 10am. The range constraints that are enforced via <code>time_windows[0]</code> are intended to define the starting times of each trip in the morning. But since the depot is the first <em>and</em> last stop of each route they could also be interpreted as arriving times in the evening.</p>
  
  <p>So here is my first difficulty with time windows: the depot appears twice on each route but the range constraint is defined on nodes. I am assuming that the routing model is not designed to take two windows for the depot?</p>
  
  <p>Let me continue to get to the second part of my question. I set <code>fix_start_cumul_to_zero = False</code> so that routes may start at any time. Also note that <code>routing.AddToAssignment(time_dimension.SlackVar(node))</code> is supposed to give me access to the slack variables later. Now, when I inspect the time values per index, via</p>
  
  <pre><code>time_vars = [time_dimension.CumulVar(x) for x in indices]
  times.append([assignment.Value(x) for x in time_vars])
  </code></pre>
  
  <p>formated with datetime, I get reasonable results:</p>
  
  <pre><code>vehicle: 0
  indices: [0, 1, 6]
  nodes:   [0, 1, 0]
  costs:   [0, 1, 2]
  times:   ['7:50:00', '9:00:00', '9:30:00']
  
  vehicle: 1
  indices: [5, 4, 3, 2, 7]
  nodes:   [0, 4, 3, 2, 0]
  costs:   [0, 1, 2, 3, 4]
  times:   ['7:50:00', '9:00:00', '9:30:00', '10:00:00', '10:30:00']
  </code></pre>
  
  <p>The solver apparently favors early departure times. Given the max slack of 40min, each vehicle might also start a bit later, e.g. at 8am.</p>
  
  <p>The trouble begins when I try to read the slack variables via</p>
  
  <pre><code>slack_vars = [time_dimension.SlackVar(x) for x in indices]
  slacks = [assignment.Value(x) for x in slack_vars]
  </code></pre>
  
  <p>The program crashes with the message:</p>
  
  <blockquote>
    <p>SystemError:  returned NULL
    without setting an error</p>
  </blockquote>
  
  <p>which suggests that <code>time_dimension</code> does not have a slack variable for every index. Is that right? Why not?</p>
  
  <p>Thanks for reading this excessive post. Here are the two questions:</p>
  
  <ol>
  <li>Is it possible to define arrival and departure time windows for the depot?</li>
  <li>How to properly read the slacks for time windows for all nodes, including the depo?</li>
  </ol>