Or-tools: 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?
yerzhik
All 32 comments
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.
yerzhik
on 28 Sep 2018
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....
Two solutions to make your problem feasible:
- Put some nodes in a disjunction i.e. allow to not visit them BUT pay the penalty cost.
- Change the Time Windows so 2 vehicles can actually solve your problem.
Mizux
on 28 Sep 2018
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 all jobs but they can do 75% and leave the rest undone?
yerzhik
on 28 Sep 2018
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.
yerzhik
on 28 Sep 2018
1) No, solver can 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/unload.
Take a look at the refuel example
2) no, solver return a solution or nothing, you need to use disjunctive constraint to have "partial" solution
Mizux
on 28 Sep 2018
Thank you, got it,
Any such example for python (found only for c++)?
yerzhik
on 1 Oct 2018
Not yet unfortunately, maybe soon...
Mizux
on 1 Oct 2018
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()
Running it:
python3 cvrp_reload.py
Objective: 6872
dropped orders: []
Route for vehicle 0:
0 Load(0) -> 12 Load(0) -> 8 Load(1) -> 9 Load(3) -> 11 Load(7) -> 3 Load(15) -> 10 Load(0) -> 16 Load(8) -> 15 Load(12) -> 14 Load(14) -> 2 Load(15) -> 17 Load(0) -> 19 Load(4) -> 13 Load(12) -> 5 Load(14) -> 1 Load(15) -> 4 Load(0) -> 7 Load(1) -> 6 Load(5) -> 18 Load(7) -> 0 Load(15)
Distance of the route: 6872m
Load of the route: 15
Total Distance of all routes: 6872m
Total Load of all routes: 15
Node 1, 2, 3 are depot unload...
Mizux
on 1 Oct 2018
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:
```python
!/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: {}mn'.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()
```
yerzhik
on 1 Oct 2018
I think its using wrong metrics (due to multiple depots with negative capacity). will fix that.
in my case there are 2 locations 2 depots and one vehicle
the time window consraint computes the matrix:
[
[ 0, 0, 4, 4],
[ 0, 0, 4, 4],
[79, 79, 0, 75],
[79, 79, 74, 0],
]
That is cols and rows are related with locations from 1 to 4 (two depots at same location and two locations at same coordinate).
Still not giving any solution though. But will try more.
yerzhik
on 1 Oct 2018
Ok found out where the problem was, thank you, issue solved!
yerzhik
on 1 Oct 2018
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
@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 ?
yerzhik
on 1 Oct 2018
You can use disjunction as follow, visit ONLY ONE node in the list or visit no node and add the penalty cost to the objectif cost.
1) If you want three node (A, B, C) to be independently optional you must use three disjunctions !
routing.addDisjunction([A], penalty)
routing.addDisjunction([B], penalty)
routing.addDisjunction([C], penalty)
2) 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 it (e.g. unload node should be not mandatory unless vehicle is full and need to be unloaded to make some room)...
3) if node is not part of a disjunction, then the solver must find a route passing by it otherwise no solution is found...
4) 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: ...
EDIT: fixed was a problem in my print function, i'll try to upload the code soon...
Mizux
on 1 Oct 2018
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?
yerzhik
on 1 Oct 2018
regarding 4th since I use one vehicle of capacity 15 for a total 4*15=60 demands, the solver must use the three "optional unload/depot duplicate" nodes 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 duplicate and solver will use only three of them 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
Mizux
on 1 Oct 2018
#!/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()
%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. My best guess, is the solver try to minimize the CumulVar of Capacity Dimension.
Mizux
on 1 Oct 2018
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 notifications@github.com 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: 371minRoute 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: 345minTotal Distance of all routes: 6872m
Total Load of all routes: 0
Total Time of all routes: 716minnote: 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
.
yerzhik
on 2 Oct 2018
Yes, the only difference is this time we consume/unload capacity (i.e. the opposite):
- vehicle start with full capacity (note the
addDimension(... False...)to let the CumulVar non empty at start) - each transit cost is negative (i.e. you 'consume' oil when traveling) notice the NegManhattanDistance
- only refill nodes have non null SlackVar i.e. we use the the slack var to "refill" the vehicle fuel CumulVar().
note: SlackVar is alway positive that's why in the unload example above I have to use a demand of "-capacity" +slackVar.setRange(0, capacity)to modelise the "unload"...
relevant src: https://github.com/google/or-tools/blob/bc6af29eec17b555d780e3b12427233fea4dcc0d/examples/cpp/cvrptw_with_refueling.cc#L118-L132
Mizux
on 2 Oct 2018
@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).
#!/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
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..
yerzhik
on 5 Oct 2018
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: 286Total Distance of all routes: 3121m
Total Load of all routes: 50
Total Time of all routes: 286min
I expect it to go to any fake depot (1 2 or 3) and go to next route. But it stops instead.
yerzhik
on 5 Oct 2018
You have some issue:
- mismatch between vehicle and demand mwhl
- Disjunction shouldn't be part of add_constraint function
BUT still it doesn't work as expected :cry: (I play a little with your code...)
Also if one node is set optional then all nodes become optional in the current implementation...
Mizux
on 5 Oct 2018
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
we can also see that if we comment line 172-175 i.e. no disjunction on location (i.e. should be treated as mandatory node), instead solver add a disjunction with 0 penalty to them and happily drop them :disappointed:
Mizux
on 5 Oct 2018
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?
yerzhik
on 10 Oct 2018
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?
yerzhik
on 10 Oct 2018
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
abhiagra94
on 3 Feb 2019
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.
```python
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)
```
quinlivanb
on 14 Mar 2019
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**
Being new to ortools, I am unable to find a way to debug. 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
on 27 Oct 2020
@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
morruth
on 11 Nov 2020
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?
morruth
on 11 Nov 2020
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
on 11 Nov 2020
Related issues
frodrigo
·
5Comments
husamrahmanh2o
·
4Comments
hklarner
·
3Comments
gsittyz
·
3Comments
bhack
·
4Comments
Most helpful comment
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
Running it:
Node 1, 2, 3 are depot unload...