OR-Tools VRP - 使用软时间最大限度地减少延迟交付的数量 windows
OR-Tools VRP - Minimize number of late deliveries with soft time windows
我正在尝试解决车辆路线问题，我希望将延迟交货的次数降至最低。通过使用 SetCumulVarSoftUpperBound，我能够设置软时间 windows 以允许延迟交付。但是，由于 SetCumulVarSoftUpperBound 给出的惩罚与超出边界的程度成正比，因此求解器将生成一条路线，其中多次交付会稍微延迟。
例如，给定以下时间矩阵和windows：
data['time_matrix'] = [
[0, 2, 2, 2, 2], # depot
[2, 0, 2, 2, 2], # 1
[2, 2, 0, 2, 2], # 2
[2, 2, 2, 0, 2], # 3
[2, 2, 2, 2, 0], # 4
]
data['time_windows'] = [
(0, 0), # depot
(0, 2), # 1
(0, 3), # 2
(0, 4), # 3
(0, 6), # 4
]
解算器将return解决以下问题：
0 -> 1 (On Time) -> 2 (Late by 1) -> 3 (Late by 2) -> 4 (Late by 2)。我正在寻找的是更接近 0 -> 1 (On Time) -> 3 (On Time) -> 4 (On Time) -> 2 (Late by 5) 的路线，其中延迟交货的数量保持在最低水平。
如有任何帮助，我们将不胜感激。
编辑： 说明问题的示例程序
import sys
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model(return_to_depot = False):
"""Stores the data for the problem."""
data = {}
data['time_matrix'] = [
[0, 2, 2, 2, 2], # depot
[2, 0, 2, 2, 2],
[2, 2, 0, 2, 2],
[2, 2, 2, 0, 2],
[2, 2, 2, 2, 0],
]
data['time_windows'] = [
(0, 0), # depot
(0, 2),
(0, 3),
(0, 4),
(0, 6),
]
data['num_vehicles'] = 1
data['depot'] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
time_dimension = routing.GetDimensionOrDie('Time')
total_time = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
plan_output += '{0} (A:{1}, D:{2}, L:{3}) -> '.format(
manager.IndexToNode(index),
solution.Min(time_var),
solution.Max(time_var),
solution.Min(time_var) - data['time_windows'][manager.IndexToNode(index)][1])
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
plan_output += '\nTime of the route: {}min\n'.format(
solution.Min(time_var))
print(plan_output)
total_time += solution.Min(time_var)
def main():
"""Solve the VRP with time windows."""
# Instantiate the data problem.
data = create_data_model()
# Initialize the penalty value
penalty = sum([sum(i) for i in data['time_matrix']]) + 1
# 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)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Time Windows constraint.
time = 'Time'
routing.AddDimension(
transit_callback_index,
sys.maxsize, # maximum waiting time
sys.maxsize, # maximum travel 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).SetMin(time_window[0])
time_dimension.SetCumulVarSoftUpperBound(index, time_window[1], penalty)
# 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)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 1
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
else:
print("\nNo solutions founds")
if __name__ == '__main__':
main()
我认为问题在于您可能使用了错误的工具来完成这项工作。
您提到：
I am trying to solve a vehicle routing problem where I wish to minimize the number of late deliveries.
在那种情况下，您应该使用线性或非线性规划（取决于您的所有约束是否都是线性的），而不是尝试使用约束求解器来解决此问题。您的 objective 将尽量减少延迟交货的次数。
来自维基百科：
Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization).
More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polytope where this function has the smallest (or largest) value if such a point exists.
您似乎在使用 Google 的 OR 工具，其中包括线性和混合整数规划求解器：
https://developers.google.com/optimization/lp/mpsolver
除了违反时间的比例成本 windows 之外，我还通过实施固定惩罚来解决这个问题。通过施加高固定成本和低比例成本，求解器将更有动力延迟已经迟到的作业，而不是迟到另一项作业。
可以在 or-tools Github 页面上的 discussion thread 中找到实施细节。实施概要如下：
- 将所有现有位置拆分为两个单独的节点； 'on-time' 节点的硬时间 window（即
setRange）和 'late' 节点的软时间 window（即 SetCumulVarSoftUpperBound）
- 添加析取，求解器只需访问两个节点之一
- 向 'on-time' 节点添加另一个析取，以便必须为删除它支付固定成本。您需要确保固定成本足够高，以便求解器仅在绝对必要时才删除 'on-time' 节点（即工作迟到）。
我正在尝试解决车辆路线问题，我希望将延迟交货的次数降至最低。通过使用 SetCumulVarSoftUpperBound，我能够设置软时间 windows 以允许延迟交付。但是，由于 SetCumulVarSoftUpperBound 给出的惩罚与超出边界的程度成正比，因此求解器将生成一条路线，其中多次交付会稍微延迟。
例如，给定以下时间矩阵和windows：
data['time_matrix'] = [
[0, 2, 2, 2, 2], # depot
[2, 0, 2, 2, 2], # 1
[2, 2, 0, 2, 2], # 2
[2, 2, 2, 0, 2], # 3
[2, 2, 2, 2, 0], # 4
]
data['time_windows'] = [
(0, 0), # depot
(0, 2), # 1
(0, 3), # 2
(0, 4), # 3
(0, 6), # 4
]
解算器将return解决以下问题：
0 -> 1 (On Time) -> 2 (Late by 1) -> 3 (Late by 2) -> 4 (Late by 2)。我正在寻找的是更接近 0 -> 1 (On Time) -> 3 (On Time) -> 4 (On Time) -> 2 (Late by 5) 的路线，其中延迟交货的数量保持在最低水平。
如有任何帮助，我们将不胜感激。
编辑： 说明问题的示例程序
import sys
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model(return_to_depot = False):
"""Stores the data for the problem."""
data = {}
data['time_matrix'] = [
[0, 2, 2, 2, 2], # depot
[2, 0, 2, 2, 2],
[2, 2, 0, 2, 2],
[2, 2, 2, 0, 2],
[2, 2, 2, 2, 0],
]
data['time_windows'] = [
(0, 0), # depot
(0, 2),
(0, 3),
(0, 4),
(0, 6),
]
data['num_vehicles'] = 1
data['depot'] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
time_dimension = routing.GetDimensionOrDie('Time')
total_time = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
plan_output += '{0} (A:{1}, D:{2}, L:{3}) -> '.format(
manager.IndexToNode(index),
solution.Min(time_var),
solution.Max(time_var),
solution.Min(time_var) - data['time_windows'][manager.IndexToNode(index)][1])
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
plan_output += '\nTime of the route: {}min\n'.format(
solution.Min(time_var))
print(plan_output)
total_time += solution.Min(time_var)
def main():
"""Solve the VRP with time windows."""
# Instantiate the data problem.
data = create_data_model()
# Initialize the penalty value
penalty = sum([sum(i) for i in data['time_matrix']]) + 1
# 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)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Time Windows constraint.
time = 'Time'
routing.AddDimension(
transit_callback_index,
sys.maxsize, # maximum waiting time
sys.maxsize, # maximum travel 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).SetMin(time_window[0])
time_dimension.SetCumulVarSoftUpperBound(index, time_window[1], penalty)
# 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)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 1
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
else:
print("\nNo solutions founds")
if __name__ == '__main__':
main()
我认为问题在于您可能使用了错误的工具来完成这项工作。
您提到：
I am trying to solve a vehicle routing problem where I wish to minimize the number of late deliveries.
在那种情况下，您应该使用线性或非线性规划（取决于您的所有约束是否都是线性的），而不是尝试使用约束求解器来解决此问题。您的 objective 将尽量减少延迟交货的次数。
来自维基百科：
Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization).
More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polytope where this function has the smallest (or largest) value if such a point exists.
您似乎在使用 Google 的 OR 工具，其中包括线性和混合整数规划求解器： https://developers.google.com/optimization/lp/mpsolver
除了违反时间的比例成本 windows 之外，我还通过实施固定惩罚来解决这个问题。通过施加高固定成本和低比例成本，求解器将更有动力延迟已经迟到的作业，而不是迟到另一项作业。
可以在 or-tools Github 页面上的 discussion thread 中找到实施细节。实施概要如下：
- 将所有现有位置拆分为两个单独的节点； 'on-time' 节点的硬时间 window（即
setRange）和 'late' 节点的软时间 window（即SetCumulVarSoftUpperBound） - 添加析取，求解器只需访问两个节点之一
- 向 'on-time' 节点添加另一个析取，以便必须为删除它支付固定成本。您需要确保固定成本足够高，以便求解器仅在绝对必要时才删除 'on-time' 节点（即工作迟到）。