VRPTW: independent cost/distance of edge and travel times #4019
Replies: 6 comments 4 replies
-
That’s seems pretty standard to me. The only issue you may run into is that the values of dimensions at nodes has to be positive or zero. The last time I tested it (several versions ago) if the link cost is so negative that the node value will be negative, the dimension will get silently floored at zero. So if that is a risk, bump everything up above some fictional hard floor, like 10000. JamesOn Dec 10, 2023, at 06:03, glanch ***@***.***> wrote:
Hello,
I currently try to solve a VRPTW (variant?).
In my VRPTW, each edge between two nodes has an associated cost/distance scalar and I'd like to minimize the cumulative edge costs. It is rather a cost than a distance, because it may be negative.
Furthermore, each each edge has an associated travel time and each node has an earliest and a latest arrival time.
—Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
Try it and see what happens JamesOn Dec 10, 2023, at 13:21, glanch ***@***.***> wrote:
The last time I tested it (several versions ago) if the link cost is so negative that the node value will be negative, the dimension will get silently floored at zero.
That is what I experienced, too. Laurent Perron claims [1] that all arc evaluators must be >= 0 and as cost is an arc evaluator, it cannot be negative -- or am I mixing up something here?
So if that is a risk, bump everything up above some fictional hard floor, like 10000
What do you mean? I think you don't mean to bump the edge costs such that they become positive -- obviously it would change the semantics of the model. But I can't think of anything others.
[1] https://groups.google.com/g/or-tools-discuss/c/YCUNTmWr8Us/m/thld_TayBQAJ
—Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you commented.Message ID: ***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
Add 10000 to everything, so the dimension stays positive. JamesOn Dec 11, 2023, at 07:57, glanch ***@***.***> wrote:
I tried. The following VRPTW instance should have an optimal solution with tour of vehicle 0 being 0->1->2->0 with total cost of -2.
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
```py
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["time_matrix"] = [
[0, 1, 1],
[1, 0, 1],
[1, 1, 0],
]
data["cost_matrix"] = [
[0, 2, -2],
[1, 0, -3],
[-1, 1, 0],
]
data["time_windows"] = [
(0, 3),
(0, 3),
(0, 3)
]
data["num_vehicles"] = 1
data["depot"] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
time_dimension = routing.GetDimensionOrDie("Time")
total_time = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
plan_output += (
f"{manager.IndexToNode(index)}"
f" Time({solution.Min(time_var)},{solution.Max(time_var)})"
" -> "
)
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
plan_output += (
f"{manager.IndexToNode(index)}"
f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n"
)
plan_output += f"Time of the route: {solution.Min(time_var)}min\n"
print(plan_output)
total_time += solution.Min(time_var)
print(f"Total time of all routes: {total_time}min")
def main():
"""Solve the VRP with time windows."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data["time_matrix"]), data["num_vehicles"], data["depot"]
)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def time_callback(from_index, to_index):
"""Returns the travel time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["time_matrix"][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(time_callback)
# Create and register a transit callback.
def cost_callback(from_index, to_index):
"""Returns the travel cost between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["cost_matrix"][from_node][to_node]
cost_callback_index = routing.RegisterTransitCallback(cost_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(cost_callback_index)
# Add Time Windows constraint.
time = "Time"
routing.AddDimension(
transit_callback_index,
30, # allow waiting time
30, # maximum time per vehicle
False, # Don't force start cumul to zero.
time,
)
time_dimension = routing.GetDimensionOrDie(time)
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(data["time_windows"]):
if location_idx == data["depot"]:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
depot_idx = data["depot"]
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(
data["time_windows"][depot_idx][0], data["time_windows"][depot_idx][1]
)
# Instantiate route start and end times to produce feasible times.
for i in range(data["num_vehicles"]):
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i))
)
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
# search_parameters.first_solution_strategy = (
# routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
# )
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
main()
```
—Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you commented.Message ID: ***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
Obviously only where appropriate. If you just add 10000 to all integers it makes no sense. But start the dimension(s) of interest with a +10000. JamesOn Dec 11, 2023, at 07:57, glanch ***@***.***> wrote:
I tried. The following VRPTW instance should have an optimal solution with tour of vehicle 0 being 0->1->2->0 with total cost of -2.
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["time_matrix"] = [
[0, 1, 1],
[1, 0, 1],
[1, 1, 0],
]
data["cost_matrix"] = [
[0, 2, -2],
[1, 0, -3],
[-1, 1, 0],
]
data["time_windows"] = [
(0, 3),
(0, 3),
(0, 3)
]
data["num_vehicles"] = 1
data["depot"] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
time_dimension = routing.GetDimensionOrDie("Time")
total_time = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
plan_output += (
f"{manager.IndexToNode(index)}"
f" Time({solution.Min(time_var)},{solution.Max(time_var)})"
" -> "
)
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
plan_output += (
f"{manager.IndexToNode(index)}"
f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n"
)
plan_output += f"Time of the route: {solution.Min(time_var)}min\n"
print(plan_output)
total_time += solution.Min(time_var)
print(f"Total time of all routes: {total_time}min")
def main():
"""Solve the VRP with time windows."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data["time_matrix"]), data["num_vehicles"], data["depot"]
)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def time_callback(from_index, to_index):
"""Returns the travel time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["time_matrix"][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(time_callback)
# Create and register a transit callback.
def cost_callback(from_index, to_index):
"""Returns the travel cost between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["cost_matrix"][from_node][to_node]
cost_callback_index = routing.RegisterTransitCallback(cost_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(cost_callback_index)
# Add Time Windows constraint.
time = "Time"
routing.AddDimension(
transit_callback_index,
30, # allow waiting time
30, # maximum time per vehicle
False, # Don't force start cumul to zero.
time,
)
time_dimension = routing.GetDimensionOrDie(time)
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(data["time_windows"]):
if location_idx == data["depot"]:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
depot_idx = data["depot"]
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(
data["time_windows"][depot_idx][0], data["time_windows"][depot_idx][1]
)
# Instantiate route start and end times to produce feasible times.
for i in range(data["num_vehicles"]):
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i))
)
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
# search_parameters.first_solution_strategy = (
# routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
# )
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
main()
—Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you commented.Message ID: ***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
here is what I did. Notice, you CANNOT get negative time. The dimensions must be positive. My adjustment to your code was simply to add 100 to the cost matrix. So 0 to 0 costs 100, etc. It gives your desired path. your mileage may vary. from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["time_matrix"] = [
[0, 1, 1],
[1, 0, 1],
[1, 1, 0],
]
data["cost_matrix"] = [
[100, 102, 98],
[101, 100, 97],
[99, 101, 100],
]
data["time_windows"] = [
(0, 3),
(0, 3),
(0, 3)
]
data["num_vehicles"] = 1
data["depot"] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
time_dimension = routing.GetDimensionOrDie("Time")
total_time = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
plan_output += (
f"{manager.IndexToNode(index)}"
f" Time({solution.Min(time_var)},{solution.Max(time_var)})"
" -> "
)
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
plan_output += (
f"{manager.IndexToNode(index)}"
f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n"
)
plan_output += f"Time of the route: {solution.Min(time_var)}min\n"
print(plan_output)
total_time += solution.Min(time_var)
print(f"Total time of all routes: {total_time}min")
def main():
"""Solve the VRP with time windows."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data["time_matrix"]), data["num_vehicles"], data["depot"]
)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def time_callback(from_index, to_index):
"""Returns the travel time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["time_matrix"][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(time_callback)
# Create and register a transit callback.
def cost_callback(from_index, to_index):
"""Returns the travel cost between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["cost_matrix"][from_node][to_node]
cost_callback_index = routing.RegisterTransitCallback(cost_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(cost_callback_index)
# Add Time Windows constraint.
time = "Time"
routing.AddDimension(
transit_callback_index,
30, # allow waiting time
30, # maximum time per vehicle
False, # Don't force start cumul to zero.
time,
)
time_dimension = routing.GetDimensionOrDie(time)
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(data["time_windows"]):
if location_idx == data["depot"]:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
depot_idx = data["depot"]
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(
data["time_windows"][depot_idx][0], data["time_windows"][depot_idx][1]
)
# Instantiate route start and end times to produce feasible times.
for i in range(data["num_vehicles"]):
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i))
)
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
# search_parameters.first_solution_strategy = (
# routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
# )
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
main() |
Beta Was this translation helpful? Give feedback.
-
I’m pretty sure it is the same thing. All I’ve done is offset by 100. Adding an integer rarely alters the fundamental nature of a problemIn a routing problem like this there are no loops, so there is no risk of accumulating hundreds by repeatedly passing through a point. If there are loops due to dummy nodes, you can handle those individually in your callback. But if you feel like using negative costs is important to you, I would suggest diving into the ORTools source code and making it work that way, then submitting a patch. I’m sure the google team would appreciate it. JamesOn Dec 11, 2023, at 12:03, glanch ***@***.***> wrote:
Thank you for your suggestion. But this alters my original problem which I want to solve. In your suggestion the cumulated costs are monotonous, which is not the case in my problem. Please correct me if I am wrong, allowing negative cost in the mathematical model yields a more expressive model than the model with correction of the costs as you proposed. The models aren't the same, unfortunately - and thus have no use for me.
I instead tried to only bump all outgoing edges from my depot to all other edges. This also resulted in a wrong path.
—Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you commented.Message ID: ***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
Hello,
I currently try to solve a VRPTW (variant?).
In my VRPTW, each edge between two nodes has an associated cost/distance scalar and I'd like to minimize the cumulative edge costs. It is rather a cost than a distance, because it may be negative.
Furthermore, each edge has an associated travel time and each node has a latest arrival time. A node cannot be visited if the sum of the predecessor edges' travel times plus the travel time to the node exceeds the latest arrival time.
How would I model this in OR-Tools Routing solver? As far as I am concerned travel time and edge costs are always the same.
Beta Was this translation helpful? Give feedback.
All reactions