lkillora
commented
5 years ago SlackVar does not seem to work at all. Below is a simple example with a depot and one node. They have demands of 0 and -5 respectively. Now set the SlackVar to any range, and it won't allow the solution 0Load(0) -> 1Load(-5) -> 0Load(-5). Of course, if you set the capacity slack from null (0) to 5, then it will work, but for this, no SlackVar is needed. In summary, SlackVar does not seem to affect the outcomes in any way.
from __future__ import print_function
import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
def euclid_distance(x1, y1, x2, y2):
# Euclidean distance between points.
dist = math.sqrt((x1 - x2)**2 + (y1 - y2)**2)
return dist
def create_distance_matrix(locations):
# Create the distance matrix.
size = len(locations)
dist_matrix = {}
for from_node in range(size):
dist_matrix[from_node] = {}
for to_node in range(size):
x1 = locations[from_node][0]
y1 = locations[from_node][1]
x2 = locations[to_node][0]
y2 = locations[to_node][1]
dist_matrix[from_node][to_node] = euclid_distance(x1, y1, x2, y2)
return dist_matrix
def create_data_model():
"""Creates the data for the example."""
data = {}
# Array of distances between locations.
_locations = [
(0, 0),
(0, 0)]
capacities = 25
_distances = create_distance_matrix(_locations)
demands = [
0,
-5]
data["distances"] = _distances
data["num_locations"] = len(_distances)
data["num_vehicles"] = 1
data["depot"] = 0
data["demands"] = demands
data["vehicle_capacities"] = capacities
return data
def create_distance_callback(data):
"""Creates callback to return distance between points."""
distances = data["distances"]
def distance_callback(from_node, to_node):
"""Returns the manhattan distance between the two nodes"""
return distances[from_node][to_node]
return distance_callback
def create_demand_callback(data):
"""Creates callback to get demands at each location."""
def demand_callback(from_node, to_node):
del to_node
return data["demands"][from_node]
return demand_callback
def add_capacity_constraints(routing, data, demand_callback):
"""Adds capacity constraint"""
capacity = "Capacity"
routing.AddDimension(
demand_callback,
0, # null capacity slack
data["vehicle_capacities"], # vehicle maximum capacities
True, # start cumul to zero
capacity)
# Add Slack
# e.g. vehicle with load 0/5 arrives at node 1 (depot unload)
# so we have CumulVar = 0(current load) + -5(unload) + 5(slack) = 0.
capacity_dimension = routing.GetDimensionOrDie(capacity)
for node_index in [0, 1]:
index = routing.NodeToIndex(node_index)
capacity_dimension.SlackVar(index).SetRange(0, 5)
def print_solution(data, routing, assignment):
"""Print routes on console."""
total_dist = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {0}:\n'.format(vehicle_id)
route_dist = 0
route_load = 0
while not routing.IsEnd(index):
node_index = routing.IndexToNode(index)
next_node_index = routing.IndexToNode(assignment.Value(routing.NextVar(index)))
route_dist += routing.GetArcCostForVehicle(node_index, next_node_index, vehicle_id)
route_load += data["demands"][node_index]
plan_output += ' {0} Load({1}) -> '.format(node_index, route_load)
index = assignment.Value(routing.NextVar(index))
node_index = routing.IndexToNode(index)
total_dist += route_dist
plan_output += ' {0} Load({1})\n'.format(node_index, route_load)
plan_output += 'Distance of the route: {0}m\n'.format(route_dist)
plan_output += 'Load of the route: {0}\n'.format(route_load)
print(plan_output)
print('Total Distance of all routes: {0}m'.format(total_dist))
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_callback = create_distance_callback(data)
routing.SetArcCostEvaluatorOfAllVehicles(distance_callback)
# Add Capacity constraint
demand_callback = create_demand_callback(data)
add_capacity_constraints(routing, data, demand_callback)
# Setting first solution heuristic (cheapest addition).
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
print_solution(data, routing, assignment)
else:
print('No solution has been found')
if __name__ == '__main__':
main()
Mizux
quinlivanb
270ajay
jiangmouren
jmarca
amih77
hherbertb
vc-void
qesbalcha
The example below is a very simple vrp with capacity constraint, requiring one return journey to the depot. The truck should be able to travel to nodes 2 and 3 and accumulate a load of 20/25. It should then drop this at the depot, which has a demand of -25 and a SlackVar range of 0 25 before returning to node 4 and then back to the actual depot.
Example of a possible solution:
0 Load(0) -> 2 Load(10) -> 3 Load(20) -> 1 Load(0) -> 4 Load(20) -> 0 Load(20).
However the solver does not find this (or any) solution. The SlackVar at the dummy depot should allow the above route but it is not working expected.
Also note, if you set the capacity to 30 then it will solve the problem as it can now return to the dummy depot with the exact load required.