Vehicles coming back for the next route feature

I am using VRP problem example with time window constraints. The only thing I changed there was the number of vehicles, I set it to 2 (it was equal to 4 before). It stopped giving me solution, instead I have an error:
File "test.py", line 278, in print
self.assignment.Value(self.routing.NextVar(index))
AttributeError: 'NoneType' object has no attribute 'Value'.

Similar issue was described in #721
But his solution is not OK for me. I need for a vehicle to go for a first route, then come back and go for the next one and so on, trying to meet all constraints including time constraints.
How can I do that?

test.txt
Here is the code I'm using. I changed the number of vehicles to 2.
If all locations can be covered using only two vehicles at once, my aim is to do it iteratively, come back, then go to next route etc until all of them covered.

did you use  https://github.com/google/or-tools/blob/master/examples/python/cvrptw.py ?
If yes then this problem can't be solved by two vehicles and still meet all TW constraints which are mandatory.
Actually if you check the assignent object it's a None object since no solution can be found....

I was using that yes,
I have two questions then

If two vehicles are capable to solve the problem with TW constraints but it requires them to make 2 routes each (make first route, come back, make the second one) - will it give such solution? I might try to make such an example.
Is it possible to show at least some solution, leaving some work undone? For example 2 vehicles are not capable to make the all jobs but they can do 75% and leave the rest undone?

I have made a test and it seems to be not possible (multiple routes by one vehicle)...
1 vehicle, 2 locations (both are the same locations).
demands in both locations are equal to 8, capacity of vehicles = 9
time windows separated into to different regions. There is one solution: the only available vehicle goes to first route and after a while to the second route. Capable by capacity and time windows but seems like there is "one vehicle - one route" restriction.

No solver visit only one time each node, there is no "come back" to depot unload then continue.
In this case you need to "duplicate" the depot node and also set a negative "cumulvar" and a "slackvar"  to simulate the refill

no, solver return a solution or nothing, you need to use disjunctive constraint to have "partial" solution

Thank you, got it,
Any such example for python (found only for c++)?

Not yet unfortunately, maybe soon...

A small working example:
I add three virtual node to be able return to depot to unload.
So this node have a demand of -15 (i.e. they unload the vehicle max capacity), and a slackVar in range [0, vehicle_max_capacity] in order to set to zero if vehicle is not fully loaded when returning to depot.
cf comment
#!/usr/bin/env python
# This Python file uses the following encoding: utf-8
# Copyright 2015 Tin Arm Engineering AB
# Copyright 2018 Google LLC
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""Capacitated Vehicle Routing Problem (CVRP).

   This is a sample using the routing library python wrapper to solve a CVRP
   problem.
   A description of the problem can be found here:
   http://en.wikipedia.org/wiki/Vehicle_routing_problem.

   Distances are in meters.
"""

from __future__ import print_function
from six.moves import xrange
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

###########################
# Problem Data Definition #
###########################
def create_data_model():
  """Stores the data for the problem"""
  data = {}
  # Locations in block unit
  _locations = [
      (4, 4), # depot
      (4, 4), # unload depot_prime
      (4, 4), # unload depot_second
      (4, 4), # unload depot_third
      (2, 0), (8, 0), # locations to visit
      (0, 1), (1, 1),
      (5, 2), (7, 2),
      (3, 3), (6, 3),
      (5, 5), (8, 5),
      (1, 6), (2, 6),
      (3, 7), (6, 7),
      (0, 8), (7, 8)]
  # 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"
  data["locations"] = [(l[0] * 114, l[1] * 80) for l in _locations]
  data["num_locations"] = len(data["locations"])
  _capacity = 15
  data["demands"] = \
        [0, # depot
         -_capacity, -_capacity, -_capacity, # prime, second, third are unload node
         1, 1, # 1, 2
         2, 4, # 3, 4
         2, 4, # 5, 6
         8, 8, # 7, 8
         1, 2, # 9,10
         1, 2, # 11,12
         4, 4, # 13, 14
         8, 8] # 15, 16
  data["num_vehicles"] = 1
  data["vehicle_capacity"] = _capacity
  data["depot"] = 0
  return data

#######################
# 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]))

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

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

  return distance_evaluator

def create_demand_evaluator(data):
  """Creates callback to get demands at each location."""
  _demands = data["demands"]

  def demand_evaluator(from_node, to_node):
    """Returns the demand of the current node"""
    del to_node
    return _demands[from_node]

  return demand_evaluator

def add_capacity_constraints(routing, data, demand_evaluator):
  """Adds capacity constraint"""
  vehicle_capacity = data["vehicle_capacity"]
  capacity = 'Capacity'
  routing.AddDimension(
      demand_evaluator,
      0, # Null slack
      vehicle_capacity,
      True,  # start cumul to zero
      capacity)

  # Add Slack for reseting to zero unload depot nodes.
  # e.g. vehicle with load 10/15 arrives at node 1 (depot unload)
  # so we have CumulVar = 10(current load) + -15(unload) + 5(slack) = 0.
  capacity_dimension = routing.GetDimensionOrDie(capacity)
  for node_index in [1, 2, 3]:
    index = routing.NodeToIndex(node_index)
    capacity_dimension.SlackVar(index).SetRange(0, vehicle_capacity)

###########
# Printer #
###########
def print_solution(data, routing, assignment):
  """Prints assignment on console"""
  print('Objective: {}'.format(assignment.ObjectiveValue()))
  total_distance = 0
  total_load = 0
  capacity_dimension = routing.GetDimensionOrDie('Capacity')
  dropped = []
  for order in range(0, routing.nodes()):
    if assignment.Value(routing.NextVar(order)) == order:
      dropped.append(order)
  print('dropped orders: {}'.format(dropped))

  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):
      load_var = capacity_dimension.CumulVar(index)
      plan_output += ' {} Load({}) -> '.format(
          routing.IndexToNode(index), assignment.Value(load_var))
      previous_index = index
      index = assignment.Value(routing.NextVar(index))
      distance += routing.GetArcCostForVehicle(previous_index, index,
                                               vehicle_id)
    load_var = capacity_dimension.CumulVar(index)
    plan_output += ' {0} Load({1})\n'.format(
        routing.IndexToNode(index), assignment.Value(load_var))
    plan_output += 'Distance of the route: {}m\n'.format(distance)
    plan_output += 'Load of the route: {}\n'.format(assignment.Value(load_var))
    print(plan_output)
    total_distance += distance
    total_load += assignment.Value(load_var)
  print('Total Distance of all routes: {}m'.format(total_distance))
  print('Total Load of all routes: {}'.format(total_load))

########
# Main #
########
def main():
  """Entry point of the program"""
  # Instantiate the data problem.
  data = create_data_model()

  # Create Routing Model
  routing = pywrapcp.RoutingModel(
      data["num_locations"],
      data["num_vehicles"],
      data["depot"])
  # Define weight of each edge
  distance_evaluator = create_distance_evaluator(data)
  routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
  # Add Capacity constraint
  demand_evaluator = create_demand_evaluator(data)
  add_capacity_constraints(routing, data, demand_evaluator)

  # Setting first solution heuristic (cheapest addition).
  search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
  search_parameters.first_solution_strategy = (
      routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)  # pylint: disable=no-member
  # Solve the problem.
  assignment = routing.SolveWithParameters(search_parameters)
  print_solution(data, routing, assignment)

if __name__ == '__main__':
  main()

That is great to see! If its not too much could you add the time window constraints? I have added it by myself but they don't give any solution, I guess I did it wrong (the same code without time window constraints works fine:
`#!/usr/bin/env python
This Python file uses the following encoding: utf-8
Copyright 2015 Tin Arm Engineering AB
Copyright 2018 Google LLC
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
"""Capacitated Vehicle Routing Problem (CVRP).
This is a sample using the routing library python wrapper to solve a CVRP
problem.
A description of the problem can be found here:
http://en.wikipedia.org/wiki/Vehicle_routing_problem.
Distances are in meters.
"""
from future import print_function
from six.moves import xrange
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
class CreateTimeEvaluator(object):
"""Creates callback to get total times between locations."""
@staticmethod
def service_time(data, node):
"""Gets the service time for the specified location."""
return data.demands[node] * data.time_per_demand_unit
@staticmethod
def travel_time(data, from_node, to_node):
    """Gets the travel times between two locations."""
    if from_node == to_node:
        travel_time = 0
    else:
        travel_time = manhattan_distance(
            data.locations[from_node],
            data.locations[to_node])
    return travel_time

def __init__(self, data):
    """Initializes the total time matrix."""
    self._total_time = {}
    # precompute total time to have time callback in O(1)
    for from_node in xrange(data.num_locations):
        self._total_time[from_node] = {}
        for to_node in xrange(data.num_locations):
            if from_node == to_node:
                self._total_time[from_node][to_node] = 0
            else:
                self._total_time[from_node][to_node] = int(
                    self.service_time(data, from_node) +
                    self.travel_time(data, from_node, to_node))

def time_evaluator(self, from_node, to_node):
    """Returns the total time between the two nodes"""
    return self._total_time[from_node][to_node]

def add_time_window_constraints(routing, data, time_evaluator):
"""Add Global Span constraint"""
time = "Time"
horizon = 64000
routing.AddDimension(
time_evaluator,
horizon, # allow waiting time
horizon, # maximum time per vehicle
False, # don't force start cumul to zero since we are giving TW to start nodes
time)
time_dimension = routing.GetDimensionOrDie(time)
for location_idx, time_window in enumerate(data.time_windows):
if location_idx == 0:
continue
index = routing.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
routing.AddToAssignment(time_dimension.SlackVar(index))
for vehicle_id in xrange(data.num_vehicles):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(data.time_windows[0][0], data.time_windows[0][1])
routing.AddToAssignment(time_dimension.SlackVar(index))
###########################
Problem Data Definition
###########################
class DataProblem():
"""Stores the data for the problem"""
def init(self):
"""Initializes the data for the problem"""
self.data = {};
self._locations = [(4, 4), # depot
(4, 4), # unload depot_prime
(2, 2), (2, 2)] # locations to visit
self._time_windows = [(0, 0),(0,0), (0, 10000), (20000, 63000)]
# 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"
self.data["locations"] = [(l[0] * 114, l[1] * 80) for l in self._locations]
self.data["num_locations"] = len(self.data["locations"])
self._capacity = 15
self.data["demands"] =
[0, # depot
-self._capacity,  # prime, second, third are unload node
15, 15] # 1, 2
self.data["num_vehicles"] = 1
self.data["vehicle_capacity"] = self._capacity
self.data["depot"] = 0
@property
def num_vehicles(self):
"""Gets number of vehicles"""
return self.data["num_vehicles"]
@property
def vehicle_capacity(self):
"""Gets capacity of vehicle"""
return self.data["vehicle_capacity"]
@property
def locations(self):
"""Gets locations"""
return self._locations
@property
def num_locations(self):
"""Gets number of locations"""
return len(self.data["locations"])
@property
def depot(self):
"""Gets depot location index"""
return self.data["depot"]
@property
def demands(self):
"""Gets demands at each location"""
return self.data["demands"]
@property
def time_per_demand_unit(self):
"""Gets the time (in min) to load a demand"""
return 5 # 5 minutes/unit
@property
def time_windows(self):
"""Gets (start time, end time) for each locations"""
return self._time_windows
def create_data_model():
"""Stores the data for the problem"""
data = DataProblem()
Locations in block unit
return data
#######################
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]))
def create_distance_evaluator(data):
"""Creates callback to return distance between points."""
_distances = {}
precompute distance between location to have distance callback in O(1)
for from_node in xrange(data.num_locations):
_distances[from_node] = {}
for to_node in xrange(data.num_locations):
if from_node == to_node:
_distances[from_node][to_node] = 0
else:
_distances[from_node][to_node] = (
manhattan_distance(data.locations[from_node],
data.locations[to_node]))
def distance_evaluator(from_node, to_node):
"""Returns the manhattan distance between the two nodes"""
return _distances[from_node][to_node]
return distance_evaluator
def create_demand_evaluator(data):
"""Creates callback to get demands at each location."""
_demands = data.demands
def demand_evaluator(from_node, to_node):
"""Returns the demand of the current node"""
del to_node
return _demands[from_node]
return demand_evaluator
def add_capacity_constraints(routing, data, demand_evaluator):
"""Adds capacity constraint"""
vehicle_capacity = data.vehicle_capacity
capacity = 'Capacity'
routing.AddDimension(
demand_evaluator,
0, # Null slack
vehicle_capacity,
True,  # start cumul to zero
capacity)
Add Slack for reseting to zero unload depot nodes.
e.g. vehicle with load 10/15 arrives at node 1 (depot unload)
so we have CumulVar = 10(current load) + -15(unload) + 5(slack) = 0.
capacity_dimension = routing.GetDimensionOrDie(capacity)
for node_index in [1, 2, 3]:
index = routing.NodeToIndex(node_index)
capacity_dimension.SlackVar(index).SetRange(0, vehicle_capacity)
###########
Printer
###########
def print_solution(data, routing, assignment):
"""Prints assignment on console"""
print('Objective: {}'.format(assignment.ObjectiveValue()))
total_distance = 0
total_load = 0
capacity_dimension = routing.GetDimensionOrDie('Capacity')
dropped = []
for order in range(0, routing.nodes()):
if assignment.Value(routing.NextVar(order)) == order:
dropped.append(order)
print('dropped orders: {}'.format(dropped))
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):
load_var = capacity_dimension.CumulVar(index)
plan_output += ' {} Load({}) -> '.format(
routing.IndexToNode(index), assignment.Value(load_var))
previous_index = index
index = assignment.Value(routing.NextVar(index))
distance += routing.GetArcCostForVehicle(previous_index, index,
vehicle_id)
load_var = capacity_dimension.CumulVar(index)
plan_output += ' {0} Load({1})\n'.format(
routing.IndexToNode(index), assignment.Value(load_var))
plan_output += 'Distance of the route: {}m\n'.format(distance)
plan_output += 'Load of the route: {}\n'.format(assignment.Value(load_var))
print(plan_output)
total_distance += distance
total_load += assignment.Value(load_var)
print('Total Distance of all routes: {}m'.format(total_distance))
print('Total Load of all routes: {}'.format(total_load))
########
Main
########
def main():
"""Entry point of the program"""
Instantiate the data problem.
data = create_data_model()
Create Routing Model
routing = pywrapcp.RoutingModel(
data.num_locations,
data.num_vehicles,
data.depot)
Define weight of each edge
distance_evaluator = create_distance_evaluator(data)
routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
Add Capacity constraint
demand_evaluator = create_demand_evaluator(data)
add_capacity_constraints(routing, data, demand_evaluator)
time_evaluator = CreateTimeEvaluator(data).time_evaluator
add_time_window_constraints(routing, data, time_evaluator)
Setting first solution heuristic (cheapest addition).
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)  # pylint: disable=no-member
Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)
print_solution(data, routing, assignment)
if name == 'main':
main()`

I think its using wrong metrics (due to multiple depots with negative capacity). will fix that.

Ok found out where the problem was, thank you, issue solved!

you sohuld have something like
#!/usr/bin/env python
# This Python file uses the following encoding: utf-8
# Copyright 2015 Tin Arm Engineering AB
# Copyright 2018 Google LLC
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""Capacitated Vehicle Routing Problem (CVRP).

   This is a sample using the routing library python wrapper to solve a CVRP
   problem.
   A description of the problem can be found here:
   http://en.wikipedia.org/wiki/Vehicle_routing_problem.

   Distances are in meters.
"""

from __future__ import print_function
from six.moves import xrange
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

###########################
# Problem Data Definition #
###########################
def create_data_model():
  """Stores the data for the problem"""
  data = {}
  _capacity = 15
  # Locations in block unit
  _locations = [
      (4, 4), # depot
      (4, 4), # unload depot_prime
      (4, 4), # unload depot_second
      (4, 4), # unload depot_third
      (2, 0), (8, 0), # locations to visit
      (0, 1), (1, 1),
      (5, 2), (7, 2),
      (3, 3), (6, 3),
      (5, 5), (8, 5),
      (1, 6), (2, 6),
      (3, 7), (6, 7),
      (0, 8), (7, 8)]
  # 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"
  data["locations"] = [(l[0] * 114, l[1] * 80) for l in _locations]
  data["num_locations"] = len(data["locations"])
  data["demands"] = \
        [0, # depot
         -_capacity, -_capacity, -_capacity, # prime, second, third are unload node
         1, 1, # 1, 2
         2, 4, # 3, 4
         2, 4, # 5, 6
         8, 8, # 7, 8
         1, 2, # 9,10
         1, 2, # 11,12
         4, 4, # 13, 14
         8, 8] # 15, 16
  data["time_per_demand_unit"] = 5 # 5 minutes/unit
  data["time_windows"] = \
        [(0, 0), # depot
         (0, 10000), (0, 10000), (0, 10000), # depot prime, second, third
         (75, 8500), (75, 8500), # 1, 2
         (60, 7000), (45, 5500), # 3, 4
         (0, 8000), (50, 6000), # 5, 6
         (0, 1000), (10, 2000), # 7, 8
         (0, 1000), (75, 8500), # 9, 10
         (85, 9500), (5, 1500), # 11, 12
         (15, 2500), (10, 2000), # 13, 14
         (45, 5500), (30, 4000)] # 15, 16
  data["num_vehicles"] = 1
  data["vehicle_capacity"] = _capacity
  data["vehicle_speed"] = 5*60/3.6 # Travel speed: 5km/h to convert in m/min
  data["depot"] = 0
  return data

#######################
# 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]))

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

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

  return distance_evaluator

def create_demand_evaluator(data):
  """Creates callback to get demands at each location."""
  _demands = data["demands"]

  def demand_evaluator(from_node, to_node):
    """Returns the demand of the current node"""
    del to_node
    return _demands[from_node]

  return demand_evaluator

def add_capacity_constraints(routing, data, demand_evaluator):
  """Adds capacity constraint"""
  vehicle_capacity = data["vehicle_capacity"]
  capacity = 'Capacity'
  routing.AddDimension(
      demand_evaluator,
      0, # Null slack
      vehicle_capacity,
      True,  # start cumul to zero
      capacity)

  # Add Slack for reseting to zero unload depot nodes.
  # e.g. vehicle with load 10/15 arrives at node 1 (depot unload)
  # so we have CumulVar = 10(current load) + -15(unload) + 5(slack) = 0.
  capacity_dimension = routing.GetDimensionOrDie(capacity)
  for node_index in [1, 2, 3]:
    index = routing.NodeToIndex(node_index)
    capacity_dimension.SlackVar(index).SetRange(0, vehicle_capacity)
    #routing.AddDisjunction([node_index])

def create_time_evaluator(data):
  """Creates callback to get total times between locations."""
  def service_time(data, node):
    """Gets the service time for the specified location."""
    return data["demands"][node] * data["time_per_demand_unit"]

  def travel_time(data, from_node, to_node):
    """Gets the travel times between two locations."""
    if from_node == to_node:
      travel_time = 0
    else:
      travel_time = manhattan_distance(
          data["locations"][from_node],
          data["locations"][to_node]) / data["vehicle_speed"]
    return travel_time

  _total_time = {}
  # precompute total time to have time callback in O(1)
  for from_node in xrange(data["num_locations"]):
    _total_time[from_node] = {}
    for to_node in xrange(data["num_locations"]):
      if from_node == to_node:
        _total_time[from_node][to_node] = 0
      else:
        _total_time[from_node][to_node] = int(
            service_time(data, from_node) +
            travel_time(data, from_node, to_node))

  def time_evaluator(from_node, to_node):
    """Returns the total time between the two nodes"""
    return _total_time[from_node][to_node]

  return time_evaluator

def add_time_window_constraints(routing, data, time_evaluator):
  """Add Time windows constraint"""
  time = 'Time'
  horizon = 250
  routing.AddDimension(
      time_evaluator,
      horizon,  # allow waiting time
      horizon,  # maximum time per vehicle
      False,  # don't force start cumul to zero since we are giving TW to start nodes
      time)
  time_dimension = routing.GetDimensionOrDie(time)
  # Add time window constraints for each location except depot
  # and "copy" the slack var in the solution object (aka Assignment) to print it
  for location_idx, time_window in enumerate(data["time_windows"]):
    if location_idx == 0:
      continue
    index = routing.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    routing.AddToAssignment(time_dimension.SlackVar(index))
  # Add time window constraints for each vehicle start node
  # and "copy" the slack var in the solution object (aka Assignment) to print it
  for vehicle_id in xrange(data["num_vehicles"]):
    index = routing.Start(vehicle_id)
    time_dimension.CumulVar(index).SetRange(data["time_windows"][0][0],
                                            data["time_windows"][0][1])
    routing.AddToAssignment(time_dimension.SlackVar(index))
    # Warning: Slack var is not defined for vehicle's end node
    #routing.AddToAssignment(time_dimension.SlackVar(self.routing.End(vehicle_id)))

###########
# Printer #
###########
def print_solution(data, routing, assignment):
  """Prints assignment on console"""
  print('Objective: {}'.format(assignment.ObjectiveValue()))
  total_distance = 0
  total_load = 0
  total_time = 0
  capacity_dimension = routing.GetDimensionOrDie('Capacity')
  time_dimension = routing.GetDimensionOrDie('Time')
  dropped = []
  for order in xrange(0, routing.nodes()):
    if assignment.Value(routing.NextVar(order)) == order:
      dropped.append(order)
  print('dropped orders: {}'.format(dropped))

  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):
      load_var = capacity_dimension.CumulVar(index)
      time_var = time_dimension.CumulVar(index)
      plan_output += ' {0} Load({1}) Time({2},{3}) ->'.format(
          routing.IndexToNode(index),
          assignment.Value(load_var),
          assignment.Min(time_var),
          assignment.Max(time_var))
      previous_index = index
      index = assignment.Value(routing.NextVar(index))
      distance += routing.GetArcCostForVehicle(previous_index, index,
                                               vehicle_id)
    load_var = capacity_dimension.CumulVar(index)
    time_var = time_dimension.CumulVar(index)
    plan_output += ' {0} Load({1}) Time({2},{3})\n'.format(
        routing.IndexToNode(index),
        assignment.Value(load_var),
        assignment.Min(time_var),
        assignment.Max(time_var))
    plan_output += 'Distance of the route: {}m\n'.format(distance)
    plan_output += 'Load of the route: {}\n'.format(assignment.Value(load_var))
    plan_output += 'Time of the route: {}\n'.format(assignment.Value(time_var))
    print(plan_output)
    total_distance += distance
    total_load += assignment.Value(load_var)
    total_time += assignment.Value(time_var)
  print('Total Distance of all routes: {}m'.format(total_distance))
  print('Total Load of all routes: {}'.format(total_load))
  print('Total Time of all routes: {}min'.format(total_time))

########
# Main #
########
def main():
  """Entry point of the program"""
  # Instantiate the data problem.
  data = create_data_model()

  # Create Routing Model
  routing = pywrapcp.RoutingModel(
      data["num_locations"],
      data["num_vehicles"],
      data["depot"])
  # Define weight of each edge
  distance_evaluator = create_distance_evaluator(data)
  routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
  # Add Capacity constraint
  demand_evaluator = create_demand_evaluator(data)
  add_capacity_constraints(routing, data, demand_evaluator)
  # Add Time Window constraint
  time_evaluator = create_time_evaluator(data)
  add_time_window_constraints(routing, data, time_evaluator)

  # Setting first solution heuristic (cheapest addition).
  search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
  search_parameters.first_solution_strategy = (
      routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)  # pylint: disable=no-member
  # Solve the problem.
  assignment = routing.SolveWithParameters(search_parameters)
  print_solution(data, routing, assignment)

if __name__ == '__main__':
  main()

%python3 cvrp_reload.py
Objective: 6872
dropped orders: []
Route for vehicle 0:
 0 Load(0) Time(0,0) -> 12 Load(0) Time(2,101) -> 8 Load(1) Time(9,108) -> 9 Load(3) Time(50,120) -> 11 Load(7) Time(72,142) -> 3 Load(15) Time(115,185) -> 10 Load(0) Time(43,113) -> 16 Load(8) Time(86,156) -> 15 Load(12) Time(108,178) -> 14 Load(14) Time(119,189) -> 2 Load(15) Time(130,200) -> 17 Load(0) Time(61,131) -> 19 Load(4) Time(83,153) -> 13 Load(12) Time(127,197) -> 5 Load(14) Time(141,211) -> 1 Load(15) Time(155,225) -> 4 Load(0) Time(87,157) -> 7 Load(1) Time(94,164) -> 6 Load(5) Time(115,185) -> 18 Load(7) Time(131,201) -> 0 Load(15) Time(180,250)
Distance of the route: 6872m
Load of the route: 15
Time of the route: 180

Total Distance of all routes: 6872m
Total Load of all routes: 15
Total Time of all routes: 180min

@Mizux Sorry, one thing left, the second part you said to use disjunctive constraint,
How those are going to help (maybe some example) if let's say all vehicles can do some routes but still 2 orders left, and thats the best possible solution with minimum orders not delivered, is there some condition that I can put to relax the constraints to solve to find solution with as less of non delivered orders as possible ?

You can use disjunction as follow, visit ONLY ONE node in the list or visit no node a add the penalty cost to the objectif cost.

If you want three node (A, B, C) to be independently optional you must use three disjunctions !

routing.addDisjunction([A], pealty)
routing.addDisjunction([B], pealty)
routing.addDisjunction([C], pealty)

playing with the penalty value you specify the trade off between visiting the node vs ingore it. i.e. big penalty means the solver as incentive to visit the node  while 0 means solver will avoid the node unless it has to visit (e.g. unload node are not needed unless vehicle is full and you need to unload it)

if node is not part of a disjunction, then the solver must find a route passing by it otherwise no solution is found...

Unfortunately AddDisjunction() seems currently broken/bug, for example, if in my previous code you uncomment the addDisjunction in the add_capacity_constraints() function. Which make the 3 unloading nodes (depot prime...) optionals (i.e. the solver can not visit them if it want) the solver start to drop 4 random nodes :confused: ...

Thank you very much. I understood it now. Regarding 4th: what was expected behavior, to drop only 3 or none? Because without disjunction constraints there is a solution which drops nothing.
I also noticed that the disjunction constraints are added to depot nodes in your code above?

regarding 4th since I use one vehicle of capacity 15 for a total 4*15=60 demands, the solver must the "three node unload duplicate" and since all others nodes are mandatory solver must visit all of them,
for examples is useful if I don't know how many unload are needed I can add let's say 8 and solver use three (mandatory) and drop the 5 others duplicates it avoid to have route like this:
0 -> order... -> 0' (unload) -> order.... -> node unload unused -> node unused -> node unused -> 0(end)

EDIT: I fix my print and add a Global Span on the distance (i.e. add incentive to minimize the longest road) so now I have an example with 2 vehicles and three unload duplicate, but

#!/usr/bin/env python
# This Python file uses the following encoding: utf-8
# Copyright 2015 Tin Arm Engineering AB
# Copyright 2018 Google LLC
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""Capacitated Vehicle Routing Problem (CVRP).

   This is a sample using the routing library python wrapper to solve a CVRP
   problem.
   A description of the problem can be found here:
   http://en.wikipedia.org/wiki/Vehicle_routing_problem.

   Distances are in meters.
"""

from __future__ import print_function
from six.moves import xrange
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

###########################
# Problem Data Definition #
###########################
def create_data_model():
  """Stores the data for the problem"""
  data = {}
  _capacity = 15
  # Locations in block unit
  _locations = [
      (4, 4), # depot
      (4, 4), # unload depot_prime
      (4, 4), # unload depot_second
      (4, 4), # unload depot_fourth
      (4, 4), # unload depot_fourth
      (4, 4), # unload depot_fifth
      (2, 0), (8, 0), # locations to visit
      (0, 1), (1, 1),
      (5, 2), (7, 2),
      (3, 3), (6, 3),
      (5, 5), (8, 5),
      (1, 6), (2, 6),
      (3, 7), (6, 7),
      (0, 8), (7, 8)]
  # 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"
  data["locations"] = [(l[0] * 114, l[1] * 80) for l in _locations]
  data["num_locations"] = len(data["locations"])
  data["demands"] = \
        [0, # depot
         -_capacity,
         -_capacity,
         -_capacity,
         -_capacity,
         -_capacity,
         1, 1, # 1, 2
         2, 4, # 3, 4
         2, 4, # 5, 6
         8, 8, # 7, 8
         1, 2, # 9,10
         1, 2, # 11,12
         4, 4, # 13, 14
         8, 8] # 15, 16
  data["time_per_demand_unit"] = 5 # 5 minutes/unit
  data["time_windows"] = \
        [(0, 0), # depot
         (0, 1000),
         (0, 1000),
         (0, 1000),
         (0, 1000),
         (0, 1000),
         (75, 8500), (75, 8500), # 1, 2
         (60, 7000), (45, 5500), # 3, 4
         (0,  8000), (50, 6000), # 5, 6
         (0,  1000), (10, 2000), # 7, 8
         (0,  1000), (75, 8500), # 9, 10
         (85, 9500), (5,  1500), # 11, 12
         (15, 2500), (10, 2000), # 13, 14
         (45, 5500), (30, 4000)] # 15, 16
  data["num_vehicles"] = 2
  data["vehicle_capacity"] = _capacity
  data["vehicle_speed"] = 5*60/3.6 # Travel speed: 5km/h to convert in m/min
  data["depot"] = 0
  return data

#######################
# 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]))

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

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

  return distance_evaluator

def add_distance_dimension(routing, distance_evaluator):
  """Add Global Span constraint"""
  distance = 'Distance'
  routing.AddDimension(
      distance_evaluator,
      0,  # null slack
      10000,  # maximum distance per vehicle
      True,  # start cumul to zero
      distance)
  distance_dimension = routing.GetDimensionOrDie(distance)
  # Try to minimize the max distance among vehicles.
  # /!\ It doesn't mean the standard deviation is minimized
  distance_dimension.SetGlobalSpanCostCoefficient(100)

def create_demand_evaluator(data):
  """Creates callback to get demands at each location."""
  _demands = data["demands"]

  def demand_evaluator(from_node, to_node):
    """Returns the demand of the current node"""
    del to_node
    return _demands[from_node]

  return demand_evaluator

def add_capacity_constraints(routing, data, demand_evaluator):
  """Adds capacity constraint"""
  vehicle_capacity = data["vehicle_capacity"]
  capacity = 'Capacity'
  routing.AddDimension(
      demand_evaluator,
      0, # Null slack
      vehicle_capacity,
      True,  # start cumul to zero
      capacity)

  # Add Slack for reseting to zero unload depot nodes.
  # e.g. vehicle with load 10/15 arrives at node 1 (depot unload)
  # so we have CumulVar = 10(current load) + -15(unload) + 5(slack) = 0.
  capacity_dimension = routing.GetDimensionOrDie(capacity)
  for node_index in [1, 2, 3, 4, 5]:
    index = routing.NodeToIndex(node_index)
    capacity_dimension.SlackVar(index).SetRange(0, vehicle_capacity)
    routing.AddDisjunction([node_index], 0)

def create_time_evaluator(data):
  """Creates callback to get total times between locations."""
  def service_time(data, node):
    """Gets the service time for the specified location."""
    return abs(data["demands"][node]) * data["time_per_demand_unit"]

  def travel_time(data, from_node, to_node):
    """Gets the travel times between two locations."""
    if from_node == to_node:
      travel_time = 0
    else:
      travel_time = manhattan_distance(
          data["locations"][from_node],
          data["locations"][to_node]) / data["vehicle_speed"]
    return travel_time

  _total_time = {}
  # precompute total time to have time callback in O(1)
  for from_node in xrange(data["num_locations"]):
    _total_time[from_node] = {}
    for to_node in xrange(data["num_locations"]):
      if from_node == to_node:
        _total_time[from_node][to_node] = 0
      else:
        _total_time[from_node][to_node] = int(
            service_time(data, from_node) +
            travel_time(data, from_node, to_node))

  def time_evaluator(from_node, to_node):
    """Returns the total time between the two nodes"""
    return _total_time[from_node][to_node]

  return time_evaluator

def add_time_window_constraints(routing, data, time_evaluator):
  """Add Time windows constraint"""
  time = 'Time'
  horizon = 1500
  routing.AddDimension(
      time_evaluator,
      horizon,  # allow waiting time
      horizon,  # maximum time per vehicle
      False,  # don't force start cumul to zero since we are giving TW to start nodes
      time)
  time_dimension = routing.GetDimensionOrDie(time)
  # Add time window constraints for each location except depot
  # and "copy" the slack var in the solution object (aka Assignment) to print it
  for location_idx, time_window in enumerate(data["time_windows"]):
    if location_idx == 0:
      continue
    index = routing.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    routing.AddToAssignment(time_dimension.SlackVar(index))
  # Add time window constraints for each vehicle start node
  # and "copy" the slack var in the solution object (aka Assignment) to print it
  for vehicle_id in xrange(data["num_vehicles"]):
    index = routing.Start(vehicle_id)
    time_dimension.CumulVar(index).SetRange(data["time_windows"][0][0],
                                            data["time_windows"][0][1])
    routing.AddToAssignment(time_dimension.SlackVar(index))
    # Warning: Slack var is not defined for vehicle's end node
    #routing.AddToAssignment(time_dimension.SlackVar(self.routing.End(vehicle_id)))

###########
# Printer #
###########
def print_solution(data, routing, assignment):
  """Prints assignment on console"""
  print('Objective: {}'.format(assignment.ObjectiveValue()))
  total_distance = 0
  total_load = 0
  total_time = 0
  capacity_dimension = routing.GetDimensionOrDie('Capacity')
  time_dimension = routing.GetDimensionOrDie('Time')
  dropped = []
  for order in xrange(0, routing.nodes()):
    index = routing.NodeToIndex(order)
    if assignment.Value(routing.NextVar(index)) == index:
      dropped.append(order)
  print('dropped orders: {}'.format(dropped))

  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):
      load_var = capacity_dimension.CumulVar(index)
      time_var = time_dimension.CumulVar(index)
      plan_output += ' {0} Load({1}) Time({2},{3}) ->'.format(
          routing.IndexToNode(index),
          assignment.Value(load_var),
          assignment.Min(time_var),
          assignment.Max(time_var))
      previous_index = index
      index = assignment.Value(routing.NextVar(index))
      distance += routing.GetArcCostForVehicle(previous_index, index,
                                               vehicle_id)
    load_var = capacity_dimension.CumulVar(index)
    time_var = time_dimension.CumulVar(index)
    plan_output += ' {0} Load({1}) Time({2},{3})\n'.format(
        routing.IndexToNode(index),
        assignment.Value(load_var),
        assignment.Min(time_var),
        assignment.Max(time_var))
    plan_output += 'Distance of the route: {}m\n'.format(distance)
    plan_output += 'Load of the route: {}\n'.format(assignment.Value(load_var))
    plan_output += 'Time of the route: {}min\n'.format(assignment.Value(time_var))
    print(plan_output)
    total_distance += distance
    total_load += assignment.Value(load_var)
    total_time += assignment.Value(time_var)
  print('Total Distance of all routes: {}m'.format(total_distance))
  print('Total Load of all routes: {}'.format(total_load))
  print('Total Time of all routes: {}min'.format(total_time))

########
# Main #
########
def main():
  """Entry point of the program"""
  # Instantiate the data problem.
  data = create_data_model()

  # Create Routing Model
  routing = pywrapcp.RoutingModel(
      data["num_locations"],
      data["num_vehicles"],
      data["depot"])
  # Define weight of each edge
  distance_evaluator = create_distance_evaluator(data)
  routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
  # Add Distance constraint to minimize the longuest route
  add_distance_dimension(routing, distance_evaluator)
  # Add Capacity constraint
  demand_evaluator = create_demand_evaluator(data)
  add_capacity_constraints(routing, data, demand_evaluator)
  # Add Time Window constraint
  time_evaluator = create_time_evaluator(data)
  add_time_window_constraints(routing, data, time_evaluator)

  # Setting first solution heuristic (cheapest addition).
  search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
  search_parameters.first_solution_strategy = (
      routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)  # pylint: disable=no-member
  # Solve the problem.
  assignment = routing.SolveWithParameters(search_parameters)
  print_solution(data, routing, assignment)

if __name__ == '__main__':
  main()

Thank you!
One more question, is the refueling example in c++ covering this case (with
time windows, etc)? I might consider c++
On Mon, Oct 1, 2018 at 7:24 PM Mizux<EMAIL_ADDRESS>wrote:

%python3 cvrp_reload.py
Objective: 358472
dropped orders: [1]
Route for vehicle 0:
0 Load(0) Time(0,0) -> 20 Load(0) Time(45,749) -> 8 Load(8) Time(91,795) -> 9 Load(10) Time(102,806) -> 6 Load(14) Time(124,828) -> 3 Load(15) Time(135,839) -> 14 Load(0) Time(212,916) -> 10 Load(1) Time(219,923) -> 11 Load(3) Time(231,935) -> 13 Load(7) Time(253,957) -> 5 Load(15) Time(296,1000) -> 0 Load(0) Time(371,1500)
Distance of the route: 3356m
Load of the route: 0
Time of the route: 371min
Route for vehicle 1:
0 Load(0) Time(0,0) -> 12 Load(0) Time(2,739) -> 18 Load(8) Time(45,782) -> 17 Load(12) Time(67,804) -> 16 Load(14) Time(85,815) -> 4 Load(15) Time(96,826) -> 19 Load(0) Time(176,906) -> 21 Load(4) Time(198,928) -> 15 Load(12) Time(242,972) -> 7 Load(14) Time(256,986) -> 2 Load(15) Time(270,1000) -> 0 Load(0) Time(345,1500)
Distance of the route: 3516m
Load of the route: 0
Time of the route: 345min
Total Distance of all routes: 6872m
Total Load of all routes: 0
Total Time of all routes: 716min
note: it still remain a "noisy" unload node just before the end node of
each route since I suspect like this, the CumulVar of Capacity Dimension is
zero on each route.
—
You are receiving this because you modified the open/close state.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/862#issuecomment-425905897,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AEnwrUYpy2sJiGZKrqdS1gLRzNk_AjFcks5ughdxgaJpZM4W-S43
.

@Mizux Hello again,
Here is updated example and code. Could you please take a look, I've used different capacities for vehicles plus I've added three more capacities. And time windows. 4 depots created 3 as fake depots with negative demand. Should have gone to the next route but all it does - drops two orders (plus 3 fake depots).
# This Python file uses the following encoding: utf-8
# Copyright 2015 Tin Arm Engineering AB
# Copyright 2018 Google LLC
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""Capacitated Vehicle Routing Problem (CVRP).

   This is a sample using the routing library python wrapper to solve a CVRP
   problem.
   A description of the problem can be found here:
   http://en.wikipedia.org/wiki/Vehicle_routing_problem.

   Distances are in meters.
"""

from __future__ import print_function
from six.moves import xrange
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
import sys
import math
import numpy as np

###########################fde
# Problem Data Definition #
###########################
def create_data_model():
  """Stores the data for the problem"""
  data = {}

  data['vehicle_horizon_time'] = [4800];
  data['time_windows'] = [(0, 0), (0, 8000), (0, 8000), (0, 8000), (0, 8000), (0, 8000), (0, 8000), (0, 8000)]
  data['demands_w'] = [0, -50, -50, -50, 3, 4, 4, 5]; #7
  data['demands_l'] = [0, -10, -10, -10, 3, 4, 5, 5]
  data['demands_h'] = [0, -10, -10, -10, 3, 4, 6, 5]
  data['demands']   = [0, -10, -10, -10, 40, 10, 20, 30]

  data['max_capacity'] = [50]
  data['max_time_limit'] = [8000]
  data['locations'] = [ (51.14, 71.44), (51.14, 71.44), (51.14, 71.44), (51.14, 71.44), #0,1,2,3
 			(51.14, 71.45), # 4
			(51.1467, 71.4583), #5
			(51.1053, 71.4404), #6
			(51.14, 71.42)]	#7
  data['vehicle_capacity_h'] = [10]
  data['vehicle_capacity_w'] = [10]
  data['vehicle_capacity_l'] = [10]
  data['vehicle_capacity_m'] = [50]
  data['num_locations'] = 8
  data['time_per_demand_unit'] = 5
  data['num_vehicles'] = 1
  data['depot'] = 0
  data['number_of_depots'] = 4
  data['vehicle_speed'] = 83.33333333333333

  return data

#######################
# Problem Constraints #
#######################

def gps_distance(position_1, position_2):
    lat1 = position_1[0]
    lat2 = position_2[0]
    lon1 = position_1[1]
    lon2 = position_2[1]

    R = 6378.137; # Radius of earth in KM
    dLat = lat2 * math.pi / 180 - lat1 * math.pi / 180;
    dLon = lon2 * math.pi / 180 - lon1 * math.pi / 180;
    a = math.sin(dLat/2) * math.sin(dLat/2) + math.cos(lat1 * math.pi / 180) * math.cos(lat2 * math.pi / 180) * math.sin(dLon/2) * math.sin(dLon/2);
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a));
    d = R * c * 1000; # in meters
    return d

def create_distance_evaluator(data):
  """Creates callback to return distance between points."""
  _distances = {}
  # precompute distance between location to have distance callback in O(1)
  for from_node in xrange(data["num_locations"]):
    _distances[from_node] = {}
    for to_node in xrange(data["num_locations"]):
      if from_node == to_node:
        _distances[from_node][to_node] = 0
      else:
        _distances[from_node][to_node] = (
            gps_distance(data["locations"][from_node],
                               data["locations"][to_node]))

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

  return distance_evaluator

def create_demand_evaluator_dwhl(data, ind):
  """Creates callback to get demands at each location."""
  if ind == 0:
    _demands = data["demands"]
  elif ind == 1:
    _demands = data["demands_w"]
  elif ind == 2:
    _demands = data["demands_h"]
  elif ind == 3:
    _demands = data["demands_l"]
  history = []

  def demand_evaluator(from_node, to_node):
    """Returns the demand of the current node"""
    del to_node
    return _demands[from_node]

  return demand_evaluator

def add_capacity_constraints(routing, data, demand_evaluator, ind):
  """Adds capacity constraint"""
  if ind == 0:
    vehicle_capacity = data["vehicle_capacity_m"]
  elif ind == 1:
    vehicle_capacity = data["vehicle_capacity_w"]
  elif ind == 2:
    vehicle_capacity = data["vehicle_capacity_h"]
  elif ind == 3:
    vehicle_capacity = data["vehicle_capacity_l"]
  capacity = 'Capacity' + str(ind);
  routing.AddDimensionWithVehicleCapacity(
      demand_evaluator,
      0, # Null slack
      vehicle_capacity,
      True,  # start cumul to zero
      capacity)

  # Add Slack for reseting to zero unload depot nodes.
  # e.g. vehicle with load 10/15 arrives at node 1 (depot unload)
  # so we have CumulVar = 10(current load) + -15(unload) + 5(slack) = 0.
  capacity_dimension = routing.GetDimensionOrDie(capacity)
  for node_index in [1, 2, 3]:
    index = routing.NodeToIndex(node_index)
    capacity_dimension.SlackVar(index).SetRange(0, np.max(vehicle_capacity))
  print(capacity_dimension);

  dodisjoint = 1
  if dodisjoint:
    penalty = 1000000
    for node_index in xrange(4, data["num_locations"]):
        routing.AddDisjunction([node_index], penalty)

def create_time_evaluator(data):
  """Creates callback to get total times between locations."""
  def service_time(data, node):
    """Gets the service time for the specified location."""
    if (data["demands"][node] < 0):
        return 0;
    return data["demands"][node] * data["time_per_demand_unit"]

  def travel_time(data, from_node, to_node):
    """Gets the travel times between two locations."""
    if from_node == to_node:
      travel_time = 0
    else:
      travel_time = gps_distance(
          data["locations"][from_node],
          data["locations"][to_node]) / data["vehicle_speed"]
    return travel_time

  _total_time = {}
  # precompute total time to have time callback in O(1)
  for from_node in xrange(data["num_locations"]):
    _total_time[from_node] = {}
    for to_node in xrange(data["num_locations"]):
      if from_node == to_node:
        _total_time[from_node][to_node] = 0
      else:
        _total_time[from_node][to_node] = int(
            service_time(data, from_node) +
            travel_time(data, from_node, to_node))

  def time_evaluator(from_node, to_node):
    """Returns the total time between the two nodes"""
    return _total_time[from_node][to_node]

  return time_evaluator

def add_time_window_constraints(routing, data, time_evaluator):
  """Add Time windows constraint"""
  time = 'Time'
  horizon = 48000 # total
  routing.AddDimension(
      time_evaluator,
      horizon,  # allow waiting time
      horizon,  # maximum time per vehicle
      False,  # don't force start cumul to zero since we are giving TW to start nodes
      time)
  time_dimension = routing.GetDimensionOrDie(time)
  # Add time window constraints for each location except depot
  # and "copy" the slack var in the solution object (aka Assignment) to print it
  for location_idx, time_window in enumerate(data["time_windows"]):
    if location_idx == 0:
      continue
    index = routing.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    routing.AddToAssignment(time_dimension.SlackVar(index))
  # Add time window constraints for each vehicle start node
  # and "copy" the slack var in the solution object (aka Assignment) to print it
  for vehicle_id in xrange(data["num_vehicles"]):
    index = routing.Start(vehicle_id)
    time_dimension.CumulVar(index).SetRange(data["time_windows"][0][0],
                                            data["time_windows"][0][1])
    routing.AddToAssignment(time_dimension.SlackVar(index))
    # Warning: Slack var is not defined for vehicle's end node
    #routing.AddToAssignment(time_dimension.SlackVar(self.routing.End(vehicle_id)))

###########
# Printer #
###########
def print_solution(data, routing, assignment):
  """Prints assignment on console"""
  print('Objective: {}'.format(assignment.ObjectiveValue()))
  total_distance = 0
  total_load = 0
  total_time = 0
  capacity_dimension = routing.GetDimensionOrDie('Capacity0')
  time_dimension = routing.GetDimensionOrDie('Time')
  dropped = []
  for order in xrange(0, routing.nodes()):
    if assignment.Value(routing.NextVar(order)) == order:
      dropped.append(order)
  print('dropped orders: {}'.format(dropped))

  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):
      load_var = capacity_dimension.CumulVar(index)
      time_var = time_dimension.CumulVar(index)
      plan_output += ' {0} Load({1}) Time({2},{3}) ->'.format(
          routing.IndexToNode(index),
          assignment.Value(load_var),
          assignment.Min(time_var),
          assignment.Max(time_var))
      previous_index = index
      index = assignment.Value(routing.NextVar(index))
      distance += routing.GetArcCostForVehicle(previous_index, index,
                                               vehicle_id)
    load_var = capacity_dimension.CumulVar(index)
    time_var = time_dimension.CumulVar(index)
    plan_output += ' {0} Load({1}) Time({2},{3})\n'.format(
        routing.IndexToNode(index),
        assignment.Value(load_var),
        assignment.Min(time_var),
        assignment.Max(time_var))
    plan_output += 'Distance of the route: {}m\n'.format(distance)
    plan_output += 'Load of the route: {}\n'.format(assignment.Value(load_var))
    plan_output += 'Time of the route: {}\n'.format(assignment.Value(time_var))
    print(plan_output)
    total_distance += distance
    total_load += assignment.Value(load_var)
    total_time += assignment.Value(time_var)
  print('Total Distance of all routes: {}m'.format(total_distance))
  print('Total Load of all routes: {}'.format(total_load))
  print('Total Time of all routes: {}min'.format(total_time))

########
# Main #
########
def main( ):
  """Entry point of the program"""
  # Instantiate the data problem.
  data = create_data_model()

  # Create Routing Model
  routing = pywrapcp.RoutingModel(
      data["num_locations"],
      data["num_vehicles"],
      data["depot"])
  # Define weight of each edge
  distance_evaluator = create_distance_evaluator(data)
  routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
  # Add Capacity constraint
  demand_evaluator = create_demand_evaluator_dwhl(data, 0)
  add_capacity_constraints(routing, data, demand_evaluator, 0)

  demand_evaluator_w = create_demand_evaluator_dwhl(data, 1)
  add_capacity_constraints(routing, data, demand_evaluator_w, 1)
  demand_evaluator_h = create_demand_evaluator_dwhl(data, 2)
  add_capacity_constraints(routing, data, demand_evaluator_h, 2)
  demand_evaluator_l = create_demand_evaluator_dwhl(data, 3)
  add_capacity_constraints(routing, data, demand_evaluator_l, 3)

  # Add Time Window constraint
  time_evaluator = create_time_evaluator(data)
  add_time_window_constraints(routing, data, time_evaluator)

  # Setting first solution heuristic (cheapest addition).
  search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
  search_parameters.first_solution_strategy = (
      routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)  # pylint: disable=no-member
  # Solve the problem.
  assignment = routing.SolveWithParameters(search_parameters)
  print_solution(data, routing, assignment)

if __name__ == '__main__':
  main( )```

I can't find my mistake here..

So it uses time windows but I set them such that any time is ok.
Here is the output:

Objective: 8003121
dropped orders: [1, 2, 3, 6, 7]
Route for vehicle 0:
0 Load(0) Time(0,0) -> 4 Load(0) Time(8,7789) -> 5 Load(40) Time(219,8000) -> 0 Load(50) Time(286,48000)
Distance of the route: 3121m
Load of the route: 50
Time of the route: 286
Total Distance of all routes: 3121m
Total Load of all routes: 50
Total Time of all routes: 286min

You have some mismatch between vehicle and demand mwhl but still it doesn't work as expected
Also one one node is set optional all node become optional in the current implementation...

here a gist: https://gist.github.com/Mizux/5d71f6be084bda75e2b98b19a1499e45
(I modify a little demands to test various things)
without disjunction (i.e. dodijunction = 0)
Demand_0: [0, -50, -50, -50, 50, 50, 50, 50]
Vehicle Capacity_0: 50
Demand_1: [0, -10, -10, -10, 8, 2, 4, 6]
Vehicle Capacity_1: 10
Demand_2: [0, -10, -10, -10, 8, 2, 4, 6]
Vehicle Capacity_2: 10
Demand_3: [0, -10, -10, -10, 8, 2, 4, 6]
Vehicle Capacity_3: 10
---------------------------
Objective: 14870
dropped orders: []
Route for vehicle 0:
 0 Load(0) Time(0,0) -> 4 Load(0) Time(8,6834) -> 3 Load(50) Time(266,7092) -> 7 Load(0) Time(282,7108) -> 2 Load(50) Time(548,7374) -> 5 Load(0) Time(565,7391) -> 1 Load(50) Time(832,7658) -> 6 Load(0) Time(878,7704) -> 0 Load(50) Time(1174,8000)
Distance of the route: 14870m
Load of the route: 50
Time of the route: 1174

Total Distance of all routes: 14870m
Total Load of all routes: 50
Total Time of all routes: 1174min

with disjunction (line 167: dodisjoint = 1)

Demand_0: [0, -50, -50, -50, 50, 50, 50, 50]
Vehicle Capacity_0: 50
Demand_1: [0, -10, -10, -10, 8, 2, 4, 6]
Vehicle Capacity_1: 10
Demand_2: [0, -10, -10, -10, 8, 2, 4, 6]
Vehicle Capacity_2: 10
Demand_3: [0, -10, -10, -10, 8, 2, 4, 6]
Vehicle Capacity_3: 10
Depot NodeIndex: 1
Depot NodeIndex: 2
Depot NodeIndex: 3
Location NodeIndex: 4
Location NodeIndex: 5
Location NodeIndex: 6
Location NodeIndex: 7
Objective: 3001396
dropped orders: [5, 6, 7]
Route for vehicle 0:
0 Load(0) Time(0,0) -> 3 Load(0) Time(0,7734) -> 2 Load(0) Time(0,7734) -> 1 Load(0) Time(0,7734) -> 4 Load(0) Time(8,7742) -> 0 Load(50) Time(266,8000)
Distance of the route: 1396m
Load of the route: 50
Time of the route: 266
Total Distance of all routes: 1396m
Total Load of all routes: 50
Total Time of all routes: 266min
note: this time three useful node  droped (penalty `1,000,000`) ->  objective `~3,000,000`

As I remember solvers can have constraints such as: do as many locations as possible, is there any "parameter" to switch that option into "ON"? Or tweak something in the code of the solver?
So the feature with multiple returns to depots is not really working, is it an issue with python only or c++ too?

By the way, you made that example for a single vehicle, what If I want to use multiple vehicles with different capacities? I just have tried to set
demands for a depots like this [0, -100000, -100000, -100000, etc]
So that its subtracting maximum value and then slack should fix the negative values. (unloading). But its stops giving any solution. How should I then use multiple vehicles with different capacities?

you should have something like this:
#!/usr/bin/env python
# This Python file uses the following encoding: utf-8
# Copyright 2015 Tin Arm Engineering AB
# Copyright 2018 Google LLC
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""Capacitated Vehicle Routing Problem (CVRP).

   This is a sample using the routing library python wrapper to solve a CVRP
   problem.
   A description of the problem can be found here:
   http://en.wikipedia.org/wiki/Vehicle_routing_problem.

   Distances are in meters.
"""

from __future__ import print_function
from six.moves import xrange
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

###########################
# Problem Data Definition #
###########################
def create_data_model():
  """Stores the data for the problem"""
  data = {}
  _capacity = 15
  # Locations in block unit
  _locations = [
      (4, 4), # depot
      (4, 4), # unload depot_prime
      (4, 4), # unload depot_second
      (4, 4), # unload depot_third
      (2, 0), (8, 0), # locations to visit
      (0, 1), (1, 1),
      (5, 2), (7, 2),
      (3, 3), (6, 3),
      (5, 5), (8, 5),
      (1, 6), (2, 6),
      (3, 7), (6, 7),
      (0, 8), (7, 8)]
  # 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"
  data["locations"] = [(l[0] * 114, l[1] * 80) for l in _locations]
  data["num_locations"] = len(data["locations"])
  data["demands"] = \
        [0, # depot
         -_capacity, -_capacity, -_capacity, # prime, second, third are unload node
         1, 1, # 1, 2
         2, 4, # 3, 4
         2, 4, # 5, 6
         8, 8, # 7, 8
         1, 2, # 9,10
         1, 2, # 11,12
         4, 4, # 13, 14
         8, 8] # 15, 16
  data["time_per_demand_unit"] = 5 # 5 minutes/unit
  data["time_windows"] = \
        [(0, 0), # depot
         (0, 10000), (0, 10000), (0, 10000), # depot prime, second, third
         (75, 8500), (75, 8500), # 1, 2
         (60, 7000), (45, 5500), # 3, 4
         (0, 8000), (50, 6000), # 5, 6
         (0, 1000), (10, 2000), # 7, 8
         (0, 1000), (75, 8500), # 9, 10
         (85, 9500), (5, 1500), # 11, 12
         (15, 2500), (10, 2000), # 13, 14
         (45, 5500), (30, 4000)] # 15, 16
  data["num_vehicles"] = 1
  data["vehicle_capacity"] = _capacity
  data["vehicle_speed"] = 5*60/3.6 # Travel speed: 5km/h to convert in m/min
  data["depot"] = 0
  return data

#######################
# 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]))

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

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

  return distance_evaluator

def create_demand_evaluator(data):
  """Creates callback to get demands at each location."""
  _demands = data["demands"]

  def demand_evaluator(from_node, to_node):
    """Returns the demand of the current node"""
    del to_node
    return _demands[from_node]

  return demand_evaluator

def add_capacity_constraints(routing, data, demand_evaluator):
  """Adds capacity constraint"""
  vehicle_capacity = data["vehicle_capacity"]
  capacity = 'Capacity'
  routing.AddDimension(
      demand_evaluator,
      0, # Null slack
      vehicle_capacity,
      True,  # start cumul to zero
      capacity)

  # Add Slack for reseting to zero unload depot nodes.
  # e.g. vehicle with load 10/15 arrives at node 1 (depot unload)
  # so we have CumulVar = 10(current load) + -15(unload) + 5(slack) = 0.
  capacity_dimension = routing.GetDimensionOrDie(capacity)
  for node_index in [1, 2, 3]:
    index = routing.NodeToIndex(node_index)
    capacity_dimension.SlackVar(index).SetRange(0, vehicle_capacity)
    #routing.AddDisjunction([node_index])

def create_time_evaluator(data):
  """Creates callback to get total times between locations."""
  def service_time(data, node):
    """Gets the service time for the specified location."""
    return data["demands"][node] * data["time_per_demand_unit"]

  def travel_time(data, from_node, to_node):
    """Gets the travel times between two locations."""
    if from_node == to_node:
      travel_time = 0
    else:
      travel_time = manhattan_distance(
          data["locations"][from_node],
          data["locations"][to_node]) / data["vehicle_speed"]
    return travel_time

  _total_time = {}
  # precompute total time to have time callback in O(1)
  for from_node in xrange(data["num_locations"]):
    _total_time[from_node] = {}
    for to_node in xrange(data["num_locations"]):
      if from_node == to_node:
        _total_time[from_node][to_node] = 0
      else:
        _total_time[from_node][to_node] = int(
            service_time(data, from_node) +
            travel_time(data, from_node, to_node))

  def time_evaluator(from_node, to_node):
    """Returns the total time between the two nodes"""
    return _total_time[from_node][to_node]

  return time_evaluator

def add_time_window_constraints(routing, data, time_evaluator):
  """Add Time windows constraint"""
  time = 'Time'
  horizon = 250
  routing.AddDimension(
      time_evaluator,
      horizon,  # allow waiting time
      horizon,  # maximum time per vehicle
      False,  # don't force start cumul to zero since we are giving TW to start nodes
      time)
  time_dimension = routing.GetDimensionOrDie(time)
  # Add time window constraints for each location except depot
  # and "copy" the slack var in the solution object (aka Assignment) to print it
  for location_idx, time_window in enumerate(data["time_windows"]):
    if location_idx == 0:
      continue
    index = routing.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    routing.AddToAssignment(time_dimension.SlackVar(index))
  # Add time window constraints for each vehicle start node
  # and "copy" the slack var in the solution object (aka Assignment) to print it
  for vehicle_id in xrange(data["num_vehicles"]):
    index = routing.Start(vehicle_id)
    time_dimension.CumulVar(index).SetRange(data["time_windows"][0][0],
                                            data["time_windows"][0][1])
    routing.AddToAssignment(time_dimension.SlackVar(index))
    # Warning: Slack var is not defined for vehicle's end node
    #routing.AddToAssignment(time_dimension.SlackVar(self.routing.End(vehicle_id)))

###########
# Printer #
###########
def print_solution(data, routing, assignment):
  """Prints assignment on console"""
  print('Objective: {}'.format(assignment.ObjectiveValue()))
  total_distance = 0
  total_load = 0
  total_time = 0
  capacity_dimension = routing.GetDimensionOrDie('Capacity')
  time_dimension = routing.GetDimensionOrDie('Time')
  dropped = []
  for order in xrange(0, routing.nodes()):
    if assignment.Value(routing.NextVar(order)) == order:
      dropped.append(order)
  print('dropped orders: {}'.format(dropped))

  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):
      load_var = capacity_dimension.CumulVar(index)
      time_var = time_dimension.CumulVar(index)
      plan_output += ' {0} Load({1}) Time({2},{3}) ->'.format(
          routing.IndexToNode(index),
          assignment.Value(load_var),
          assignment.Min(time_var),
          assignment.Max(time_var))
      previous_index = index
      index = assignment.Value(routing.NextVar(index))
      distance += routing.GetArcCostForVehicle(previous_index, index,
                                               vehicle_id)
    load_var = capacity_dimension.CumulVar(index)
    time_var = time_dimension.CumulVar(index)
    plan_output += ' {0} Load({1}) Time({2},{3})\n'.format(
        routing.IndexToNode(index),
        assignment.Value(load_var),
        assignment.Min(time_var),
        assignment.Max(time_var))
    plan_output += 'Distance of the route: {}m\n'.format(distance)
    plan_output += 'Load of the route: {}\n'.format(assignment.Value(load_var))
    plan_output += 'Time of the route: {}\n'.format(assignment.Value(time_var))
    print(plan_output)
    total_distance += distance
    total_load += assignment.Value(load_var)
    total_time += assignment.Value(time_var)
  print('Total Distance of all routes: {}m'.format(total_distance))
  print('Total Load of all routes: {}'.format(total_load))
  print('Total Time of all routes: {}min'.format(total_time))

########
# Main #
########
def main():
  """Entry point of the program"""
  # Instantiate the data problem.
  data = create_data_model()

  # Create Routing Model
  routing = pywrapcp.RoutingModel(
      data["num_locations"],
      data["num_vehicles"],
      data["depot"])
  # Define weight of each edge
  distance_evaluator = create_distance_evaluator(data)
  routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
  # Add Capacity constraint
  demand_evaluator = create_demand_evaluator(data)
  add_capacity_constraints(routing, data, demand_evaluator)
  # Add Time Window constraint
  time_evaluator = create_time_evaluator(data)
  add_time_window_constraints(routing, data, time_evaluator)

  # Setting first solution heuristic (cheapest addition).
  search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
  search_parameters.first_solution_strategy = (
      routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)  # pylint: disable=no-member
  # Solve the problem.
  assignment = routing.SolveWithParameters(search_parameters)
  print_solution(data, routing, assignment)

if __name__ == '__main__':
  main()

%python3 cvrp_reload.py
Objective: 6872
dropped orders: []
Route for vehicle 0:
 0 Load(0) Time(0,0) -> 12 Load(0) Time(2,101) -> 8 Load(1) Time(9,108) -> 9 Load(3) Time(50,120) -> 11 Load(7) Time(72,142) -> 3 Load(15) Time(115,185) -> 10 Load(0) Time(43,113) -> 16 Load(8) Time(86,156) -> 15 Load(12) Time(108,178) -> 14 Load(14) Time(119,189) -> 2 Load(15) Time(130,200) -> 17 Load(0) Time(61,131) -> 19 Load(4) Time(83,153) -> 13 Load(12) Time(127,197) -> 5 Load(14) Time(141,211) -> 1 Load(15) Time(155,225) -> 4 Load(0) Time(87,157) -> 7 Load(1) Time(94,164) -> 6 Load(5) Time(115,185) -> 18 Load(7) Time(131,201) -> 0 Load(15) Time(180,250)
Distance of the route: 6872m
Load of the route: 15
Time of the route: 180

Total Distance of all routes: 6872m
Total Load of all routes: 15
Total Time of all routes: 180min

Hope you are doing well!
Actually I was going through your codes from here[ https://github.com/google/or-tools/issues/862#issuecomment-425872785] and solving a problem.
I was struggling to find the solution but your logic helped me solve the problem. Thanks.
But I have one more question. From the code we are getting the output like this:
Route for vehicle 0:
0 Load(0) Time(0,0) -> 12 Load(0) Time(2,101) -> 8 Load(1) Time(9,108) -> 9 Load(3) Time(50,120) -> 11 Load(7) Time(72,142) -> 3 Load(15) Time(115,185) -> 10 Load(0) Time(43,113) -> 16 Load(8) Time(86,156) -> 15 Load(12) Time(108,178) -> 14 Load(14) Time(119,189) -> 2 Load(15) Time(130,200) -> 17 Load(0) Time(61,131) -> 19 Load(4) Time(83,153) -> 13 Load(12) Time(127,197) -> 5 Load(14) Time(141,211) -> 1 Load(15) Time(155,225) -> 4 Load(0) Time(87,157) -> 7 Load(1) Time(94,164) -> 6 Load(5) Time(115,185) -> 18 Load(7) Time(131,201) -> 0 Load(15) Time(180,250)
As you see each time vehicle is unloading and starting the journey again the time also starts again, that is why 3 Load(15) Time(115,185) -> 10 Load(0) Time(43,113) as in this when time is already between (115,185) then timer starts again and giving the value (43,113). Actually I don't want timer to starts again I just want that time windows should give values without resetting. I will be really grateful if you could please me with this

Working on a similar problem and I think I have found a bug with the above examples. I don't think the following section of code is working es explained in the comments. In all of the examples above the truck only returns to one of the dummy nodes when it's capacity is exactly full. If you pick a different capacity, eg 17, the solver will not find a solution. Any advice on this would be much appreciated.
Add Slack for reseting to zero unload depot nodes.
e.g. vehicle with load 10/15 arrives at node 1 (depot unload)
so we have CumulVar = 10(current load) + -15(unload) + 5(slack) = 0.
capacity_dimension = routing.GetDimensionOrDie(capacity)
for node_index in [1, 2, 3]:
index = routing.NodeToIndex(node_index)
capacity_dimension.SlackVar(index).SetRange(0, vehicle_capacity)

Thank you for providing insights on how the multi-trip VRP work. Although, while learning, when I tried to implement the same above program (with only capacity constraints excluding time window constraints) in my system, I am facing a TypeError. The error displayed is as follows:
**line 2842, in init
_pywrapcp.RoutingModel_swiginit(self, _pywrapcp.new_RoutingModel(*args))
TypeError: Wrong number or type of arguments for overloaded function 'new_RoutingModel'.
Possible C/C++ prototypes are:
operations_research::RoutingModel::RoutingModel(operations_research::RoutingIndexManager const &)
operations_research::RoutingModel::RoutingModel(operations_research::RoutingIndexManager const &,operations_research::RoutingModelParameters const &)
Process finished with exit code 1**
Can anyone explain why is it happening? What is it that I am missing and I should change? Please let me know. Your help will be highly appreciated. Thanks in advance.

@Subram0212, this example for pretty old version of or-tools
If you use version newer than 7.0, you should look at example at https://github.com/google/or-tools/blob/master/ortools/constraint_solver/samples/cvrp_reload.py

If I want to add constraint «vehicle should always return to depot unloaded» AKA «last point before returning to depot should be unload point» how can I do this
i've tried to add
solver=routing.solver()
solver.Add(capacity_dimension.CumulVar(0) == 0 )
with no visible effect (seems this condition checked at route's start, when it always true)
and
solver=routing.solver()
solver.Add(capacity_dimension.CumulVar(routing.End(0)) == 0 )
then it seems never ends, i'm waited 5 minutes and killed process
How to do it correctly?

also i've tried
capacity_dimension.CumulVar(manager.NodeToIndex(0)).SetRange(0, 0)
as in 1st try, solution is exactly same as without it

@morruth Have you solved your problem? I'm also trying set the last point before the depot as the unload point. Actually, since we are saying that last 2 nodes are always "unload - depot", there is nothing to optimize there. So, setting the end location as the unload point then add "depot" at the end of the solution can be a workaround. Still, I wasn't able to set the ending point as "unload point".


update Hover effect on all buttons

/approve

Please keep patient to wait for reviewer come in. You cannot approve any PR opened by yourself.

Hi @anurag4499, Always write a description on the PR as what changes are from your side, will help reviewers understand the PR.

/area web-development

Looks like the improvement is done and merged in another PR, shall we close this one?

Closing this due to this PR: https://github.com/kubernetes/website/pull/43175
/close


Assign dahsboard does not open if config was run first

What's going wrong?
The assign dashboard does not open if assign config is run first.
How can the urcli team reproduce the problem?

Remove ~/.urcli/
Run urcli setup and configure everything normally.
Run urcli assign config
Runurcli assign number-of-a-project
It get stuck in

✔ Environment ready. Starting main submission request loop.

supporting information:

node -v prints: v6.10.3
urcli -V prints: 4.0.0
Windows, OS X/macOS, or Linux?: Linux

I wasn't able to reproduce this. Are you having network errors?

I don't think so. I tested it on my local Linux and a server.

Are you able to replicate it every time?

Yes. I will record a video/gif and upload it here.

@gabraganca could you confirm that this is still happening for you after the update?

@trolster I'll check it later today.

+1

I wasn't able to reproduce this, but I think I've fixed it in v4.0.3. Try updating and let me know if it works or not.

That fixed. Thanks. :+1:


Add Djangonaut Space

Project Information

Project Name: Djangonaut Space

Project URL: https://djangonaut.space

Description:
Free peer-mentoring program for the Django community to launch people into the universe of open source contributions.

Criteria
Please answer the following questions about the project you are submitting. This will help us evaluate if the project should be included in the Awesome Django list.
Note: If your project is only a few months old or has under 50 to 100 stars on GitHub, it may NOT meet the criteria for inclusion in the Awesome Django list. We recommend that you promote your project more and then consider a submission at a later date when it has gained more visibility and community support.

Is the project new?

[ ] Yes
[x] No

How long has the project been maintained?
Djangonaut Space has been worked on for 16 months. The pilot session was Fall of 2023. The first official session occurred in Jan of 2024. The second session starts in June of 2024.

How many releases has it had if it's a library or package?
N/A

Are you the author or are you submitting the project on behalf of a company?

[ ] I am the author
[ ] I am submitting on behalf of a company
[x] Other (please specify): Organizer

What makes it awesome?
Djangonaut Space places an emphasis on group-learning, sustainability and longevity. Djangonauts are members of the community who wish to level up their current Django code contributions and potentially take on leadership roles in Django in the future. 🦄

This is a free, 8-week group mentoring program where individuals will work self-paced in a semi-structured learning environment.

Additional Information

Blog
Program documentation
Sessions list

Thanks Tim.


[FEATURE] Add support to recommend threshold tuning for heap based task cancellations by SearchBackpressureService

Is your feature request related to a problem?
Recently opensearch introduced a new feature called searchbackpressure to make the service more resilient to node drops and performance degradation. It solves the problem by cancelling resource guzzling search queries at shard level and coordinator node level. In order to achieve this it uses various settings to cancel a search query based on the resource the query is making heavy use of. As part of this feature we will try to add support to recommend threshold tuning for those settings for heap based query cancellation at shard and coordinator level.
What solution would you like?
Since there are multiple settings for each resource based cancellation. We will only recommend a single value (a multiplier) by which the thresholds should increase/decrease for a resource(In this case heap) as that would complicate the solution and number of RCAs we will need to create. We will emit actions for both the searchTask(Coordinator) and shard level differently.
Logic to mark the RCA unhealthy to increase the thresholds (Node level)

If the max heap used by openSearch process is below 85% for a minute. Since RCA runs at 5 seconds interval, we will keep a sliding window of heapUsed values for a minute.
And the heap based task cancellations are more than 3%. (Since there are rate limiters to limit the amount of cancellations. Can't cancel more than 10% of all successful tasks both at shard level and coordinator level).

Logic to mark the RCA unhealthy to decrease the thresholds (Node level)

If the max heap used by openSearch process is above 90% for a minute. Since RCA runs at 5 seconds interval, we will keep a sliding window of heapUsed values for a minute.
And the heap based task cancellations are less than 3%. (Since there are rate limiters to limit the amount of cancellations. Can't cancel more than 10% of all successful tasks both at shard level and coordinator level).

Marking the cluster level RCAs unhealthy
We will mark the cluster level RCA as unhealthy if any of the node in the cluster has unhealthy node level RCA for an hour with a cool off period of one day.
Adjusted SBP Settings

search_backpressure.search_task.total_heap_percent_threshold
search_backpressure.search_task.heap_percent_threshold
search_backpressure.search_task.heap_variance
search_backpressure.search_task.heap_moving_average_window_size

What alternatives have you considered?
The RCA framework is already in place to which runs as a side car and does not share the opensearch process resources. The alternate solution could have been to place this logic in the opensearch but that can create the resource scarcity and performance degradation of opensearch process under duress
Do you have any additional context?
Add any other context or screenshots about the feature request here.

[Triage -- attendees 1, 2, 3, 4, 5, 6, 7]
Looks like a legit feature request, thanks for opening it.


Implement spi layer for Logging service

System tests will come later with LoggingImpl.

Coverage decreased (-0.4%) to 83.745% when pulling 329edbd1297e43571320bfd7e38e507baaaf83be on mziccard:logging-spi into a327c6461cd178a9eceb4651f51aa4ddb98f03e1 on GoogleCloudPlatform:logging-alpha.

/cc @lesv

LGTM - though you might wish to look at codecy/pr's comments and fix them -- or comment why we need redundant methods.

@lesv all overrides claimed to be redundant by codacy in this PR are made so that overridden methods are visible in the "logging.spi" package.


Solved BUILD FAILED by updating gradle to 2.10 version in wrapper

I signed it!

This sample has been deprecated/archived (check README for more information on newer samples related to this technology).
As recommended by GitHub, we are closing all issues and pull requests.


Update samples to use env: flex

Additional Updates needed:

Update Ruby Client Library calls in samples
Update entrypoint: bundle exec rackup -p $PORT
Update Google Managed VMs in READMEs
Update supported Ruby versions in READMEs

[x] Hello World
[x] Cloud SQL
[x] Cloud Datastore
[x] Cloud Storage
[x] Google Authentication
[x] Logging
[x] Task Queueing

PTAL @remi

PTAL @remi


x/build: report failures fast but still make all test results available

(This feature request/enhancement is related to issue #34119, the goal is to improve developer experience at the expense of using more computational resources.)
In https://github.com/golang/go/issues/14305#issuecomment-565093254, there is discussion of whether to use -k on which branches, and on post-submit only vs trybots too. There is a trade-off in that the flag improves information that a failed build reports, but makes the test failure get reported more slowly.
A more ideal (for user developer experience) solution is to report a failure fast, as soon as the first test fails, but keep going and make all test results available for later viewing by interested parties.
See the fast-finish builds feature of Travis CI for some related precedent.
/cc @bradfitz @bcmills @toothrot @cagedmantis

/cc @findleyr


GraphQL subscription WebSocket issue

For GraphQL subscription WebSocket
1. Chrome 87.0.4280.0

Succeed locally
Succeed in production

2. Firefox 83.0a1

Succeed locally
Failed in production

Firefox can’t establish a connection to the server at wss://www.hongbomiao.com/graphql.
periodically in production.

3. Safari 13.2

Failed locally
Failed in production

Refused to connect to wss://localhost:5000/graphql because it does not appear in the connect-src directive of the Content Security Policy.

Safari both local and production issues are fixed by https://github.com/Hongbo-Miao/hongbomiao.com/pull/968
Firefox production issue left.

Got

WebSocket connection to 'wss://www.hongbomiao.com/graphql' failed: WebSocket is closed before the connection is established.
on WeChat Devtools.

Second time opening is fine.

Got another

Firefox can’t establish a connection to the server at wss://www.hongbomiao.com/graphql. 2.2c591de4.chunk.js:2:134796
The connection to wss://www.hongbomiao.com/graphql was interrupted while the page was loading.

for Firefox in production.

Created an issue at https://github.com/enisdenjo/graphql-transport-ws/issues/25

I don't which version might potentially fixed it.
But after upgrading graphql-ws to version 1.13.1. The Firefox issue disappeared.


Typography & Heading: add components to Syntax

Changes

Adds Typography and Heading components to Syntax

FAQ
What is the Heading component for?
Heading enforces a consistent style & accessibility best practices for headings.
Typography is quite different from what we do in Cambly-Frontend, why is that?

Sizes now go from small (100) to big (800) - previously the smallest size was body300 which didn't make a lot of sense
We now see Typography is the root component for all text to be rendered on Cambly. It allows for custom components such as Heading and has more flexibility built-in.

Screenshots
Typography

Heading

did you run changeset on this? it said no changeset found and was just double checking

did you run changeset on this? it said no changeset found and was just double checking

@somethiiing added - thank you

@christianvuerings 700 and 800 should be using font-weight:860 (Heavy) instead of bold. I understand this only affects Apple people lol


Avoid typecasting unexpected strings to symbols to prevent DoS due to memory leak

This gem will typecast any string to a symbol when assigned to an enum column, even if the string does not fit the enum. This exposes a potential DoS vulnerability with common usage.  Consider a model Enumeration with an enum column "color". Suppose a user fakes a form submit with the parameter color=invalid_color. The controller methods below will catch this in validation and prevent the model from being saved, but the symbol :invalid_color will still be created. Since symbols are never garbage-collected, a bunch of requests with random color params will eventually crash the server.
class EnumerationController < ApplicationController
  def new
    e = Enumeration.new(params) #symbol is created here
    e.save #validations fail here if turned on
  end
  def update
    Enumeration.find(params[:id]).update_attributes(params)
  end
end

This patch changes functionality slightly so that if an enum attribute is set to an invalid string, it'll just typecast it to nil instead of converting it to a symbol. You can bypass this by assigning the symbol directly.
Enumeration.color = 'invalid' # Enumeration.color == nil
Enumeration.color = :invalid #  Enumeration.color == :invalid

What do you think?

Closing this ancient PR as Ruby's now better at handling dynamic symbols.


[SPARK-41092][SQL] Do not use identifier to match interval units

What changes were proposed in this pull request?

The current antlr-based SQL parser is pretty fragile due to the fact that we make the antlr parser rule pretty flexible and push more parsing logic to the Scala side (AstBuilder). A tiny change to the antlr parser rule may break the parser unexpectedly. As an example, in https://github.com/apache/spark/pull/38404 , we added a new parser rule to extend the INSERT syntax, and it breaks interval literal. select b + interval '1 month' from values (1, 1) can't be parsed after https://github.com/apache/spark/pull/38404
This PR makes the interval literal parser rule stricter. Now it lists all the allowed interval units instead of matching an identifier. This fixes the issue we hit in https://github.com/apache/spark/pull/38404 .
In the future, we can revisit other parser rules and try to rely on antlr more to do the parsing work.
Why are the changes needed?

fix parser issues we hit in https://github.com/apache/spark/pull/38404
Does this PR introduce any user-facing change?

The error message is changed a little bit for SELECT INTERVAL 1 wrong_unit.
How was this patch tested?

existing tests

cc @gengliangwang @MaxGekk @viirya

But seems it doesn't add test for select b + interval '1 month' from values (1, 1)?

This is an existing test and it fails in https://github.com/apache/spark/pull/38404 . After the changes here, it can pass.

+1, LGTM. Merging to master.
Thank you, @cloud-fan and @viirya for review.


Add "Google Cloud API manager"

It can contain the full list of supported Google Cloud APIs

Add/Remove nuget packages of the APIs

Insert necessary initialization code, especially for authentication etc
Example:  Log4Net,   adding the config, reading config etc code.
Error Reporting Diagnostics,   adding the code easily...

Links to documentation, samples

This is done today in the templates. The apps are created fully supporting logging, error reporting and with the right nuget packages added to them.
As for adding new APIs, and possibly examples, etc... we should track this in #358, since this will also involve enabling APIs.

This is not full duplicate however, I think that this is more of full fledge API manager feature.


automate model spawning and removing

A pbr/box model can be spawned by a launch file and be removed manually in gazebo. However, we need automation for all processes to repeat experiments with different motion parameters.
Gazebo provides service servers to spawn and delete models.

to delete a model: http://gazebosim.org/tutorials/?tut=ros_comm
to spawn a model: https://github.com/ros-simulation/gazebo_ros_pkgs/blob/kinetic-devel/gazebo_ros/scripts/spawn_model

There are four steps in one automation iteration.

load pbr model
trigger pulse motion
delete pbr model
reset shape model

A python ros node has been added for the automation pulse_motion_smart_client.py

Implemented pulse_motion_smart_client.py. Here is a demo: https://www.youtube.com/watch?v=XEWoWZ7U458


Gather file descriptors as process metric

Fixes #729
Any other bits we should to gather? I'm not super-convinced it's actually all that useful?
@2opremio, wdyt?
See "Open Files" sparkline below.

I think it's a  very useful metric, but I am not convinced it should have
such protagonism, or whether it's useful to show it it's history in a
sparkline.
On Friday, February 12, 2016, Paul Bellamy<EMAIL_ADDRESS>wrote:

Assigned #961 https://github.com/weaveworks/scope/pull/961 to @2opremio
https://github.com/2opremio.
—
Reply to this email directly or view it on GitHub
https://github.com/weaveworks/scope/pull/961#event-548798348.

Yes it would be good to have this hidden behind a show more.
On Friday, 12 February 2016, Alfonso Acosta<EMAIL_ADDRESS>wrote:

I think it's a very useful metric, but I am not convinced it should have
such protagonism, or whether it's useful to show it it's history in a
sparkline.
On Friday, February 12, 2016, Paul Bellamy<EMAIL_ADDRESS><javascript:_e(%7B%7D,'cvml','notifications@github.com');>> wrote:

Assigned #961 https://github.com/weaveworks/scope/pull/961 to
@2opremio
https://github.com/2opremio.
—
Reply to this email directly or view it on GitHub
https://github.com/weaveworks/scope/pull/961#event-548798348.

—
Reply to this email directly or view it on GitHub
https://github.com/weaveworks/scope/pull/961#issuecomment-183423122.

Hiding a single element seems needless.

@paulbellamy From my own debugging experience, open files gets you straight into root cause analysis, whereas cpu and memory are quite vague. so I love its prominence there (until a better metric comes along).

Tried the branch, JS part looks good too.

minor-comments aside, LGTM


Ignore group/owner/mode attrs on Windows machine until implemented

Implementing @joelwilson 's fix from https://github.com/chef/chef-provisioning/issues/285.
Attempting to set group/owner/mode on uploaded files bombs on Windows nodes with the message
set_attributes not overridden on Chef::Provisioning::Machine::WindowsMachine
We should ignore this on windows nodes until implemented.

I'll add a comment around that block in case we ever get time to fix the WindowsMachine


error on startup

2020-07-28 08:12:47.305 [INF] LTND: Version: 0.10.1-beta commit=v0.10.1-beta, build=production, logging=default
2020-07-28 08:12:47.306 [INF] LTND: Active chain: Bitcoin (network=mainnet)
2020-07-28 08:12:47.306 [INF] LTND: Opening the main database, this might take a few minutes...
panic: freepages: failed to get all reachable pages (page -1835263452: out of bounds: 28694)
tried to recover using chantools with not success.
./chantools compactdb --sourcedb ~/.lnd/data/graph/mainnet/channel.db --destdb /tmp/compacted.db
2020-07-28 08:33:20.717 [INF] CHAN: chantools version v0.2.0 commit v0.2.0-6-gaf2094b
panic: runtime error: index out of range [3253368639] with length 268435455

goroutine 1 [running]:
github.com/coreos/bbolt.(*leafPageElement).key(...)
	/home/bitcoin/go/pkg/mod/github.com/coreos/bbolt@v1.3.3/page.go:120
github.com/coreos/bbolt.(*Cursor).keyValue(0x253bc68, 0x5c72137b, 0x29, 0x2c8a10, 0x24c4340, 0x2580ce0, 0x2586710, 0x1)
	/home/bitcoin/go/pkg/mod/github.com/coreos/bbolt@v1.3.3/cursor.go:350 +0x1ac

What should I do ?

It sounds like the data part of your channel DB was corrupted, not just the freepages (which can happen on improper shutdown).
I'm not sure you can recover to a normal state from this if compactdb fails. Do you have a channel.backup file? You might want to recover your funds from the SCB. Unfortunately this will close all channels and incur a lot of on-chain fees, depending on when the last fee update happened (when was the node operational last?).

@offerm can be closed?

I guess so. I was not able to recover from this and had to recreate the node and close all channels using the backup.
A few days back I has a similar error after node crash but second restrat of lnd was ok.

What storage medium are you using for the lnd data directory? This sounds like you might have a faulty drive if you continue to get these errors.

I was using external hard drive for bitcoin and lnd directories.
Afrer last event I move the lnd directory to the local drive.
Both incidents happened after the machine halted for some reason.
Offer
On Wed, Dec 2, 2020 at 1:51 PM Oliver Gugger<EMAIL_ADDRESS>wrote:

What storage medium are you using for the lnd data directory? This sounds
like you might have a faulty drive if you continue to get these errors.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/lightningnetwork/lnd/issues/4491#issuecomment-737182081,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/ACKDI4WQXJQK5IMPCGAAMYDSSYS4BANCNFSM4PKNCH4Q
.

Both incidents happened after the machine halted for some reason.

Thanks for the information. Judging from that, I suspect this is a hardware issue. Not cleanly shutting down will often result in DB corruption. I'd suggest investigating the unexpected halts of the machine to avoid future problems.
Closing this for now.