我搜索了许多类似的问题，但找不到适合我情况的解决方案。如果你们中的任何人能给我一些建议，我将不胜感激。
这是我的情况
车辆在仓库装载一些新机器，然后访问多个位置。当车辆向每个节点交付新机器时，它们还会从每个节点收集损坏的机器。
同时，车辆有容量限制。
此外，我需要复制仓库以允许多次旅行：车辆需要返回仓库卸载损坏的机器并装载新机器并再次行驶，直到所有交付和取货都完成。
主要思想类似于这个例子：https ://github.com/google/or-tools/blob/master/ortools/constraint_solver/samples/cvrp_reload.py ，但现在我不考虑时间限制。
我做了什么
主要思想是：
- 取消注释时间窗口约束。
- 使用交付维度来跟踪新机器的交付
- 使用拾取维度来跟踪损坏机器的拾取情况
- 在每个节点添加一个约束，CumulVar(pickups) + CumulVar(deliveries) <= capacity
请求帮忙
示例任务是这样的：
问题是：
如果我将车辆容量设置为10，则问题可以解决。但是当我设置为 7 时，“找不到解决方案”！
但显然，车辆至少可以行驶 4 次才能完成所有工作：
第1轮：在仓库加载5台新机器，到节点1，卸载它们，然后捡起4台坏机器回到仓库
回合2：在仓库加载5台新机器，到节点2，卸载它们，然后捡起6台坏机器回到仓库
回合3：在仓库加载2台新机器，到节点3，卸载它们，然后捡起7台坏机器回到仓库
第4轮：在仓库加载3台新机器，到节点4，卸载它们，然后拿起3台坏机器回到仓库
我可以理解为什么求解器没有找到这个解决方案。因为每次车辆离开重复的站点节点时，交付维度都会重置为_capacity 。当_capacity为 7 时，车辆可以满足节点 1 和节点 4 的需求。（节点 1 卸载 5 台新机器，加载 4 台坏机。节点 4 卸载 3 台坏机，加载 3 台新机器。）
但在节点 2 和节点 3，取货/送货是 +6/-5 和 +7/-2。当车辆离开重复站点节点时，其容量为 7，节点 2 和节点 3 都将打破容量约束。(+6-5>0, +7-2>0)
所以这个问题的根本原因是：重复的depot节点不应该将deliveries维度值设置为一个固定值（_capacity），而是一个介于[0,_capacity]之间的值。
但是 max_slack 是一个正数，我不知道如何使交付维度的值介于 [0, _capacity] 之间。
有人可以帮我吗？太感谢了。
下面是我的代码。
from functools import partial
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
from itertools import repeat
###########################
# Problem Data Definition #
###########################
def create_data_model():
"""Stores the data for the problem"""
data = {}
_capacity = 10 # 7 doesn't work
_duplicate_depot_num = 5
# Locations in block unit
_locations = [
(4, 4), # depot
(2, 0), (8, 0), # 1, 2
(0, 1), (1, 1)] # 3, 4
_locations[1:1] = tuple(repeat(_locations[0], _duplicate_depot_num))
data['locations'] = _locations
data['num_locations'] = len(data['locations'])
data['pickups'] = [0, # depot
4, 6, # 1, 2
7, 3] # 3, 4
data['pickups'][1:1] = tuple(repeat(-_capacity, _duplicate_depot_num))
data['deliveries'] = [0, # depot
-5, -5, # 1, 2
-2, -3] # 3, 4
data['deliveries'][1:1] = tuple(repeat(_capacity, _duplicate_depot_num))
data['vehicle_max_distance'] = 1000
data['vehicle_capacity'] = _capacity
data['num_vehicles'] = 1
data['depot'] = 0
data['dup_depot_num'] = _duplicate_depot_num
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 range(data['num_locations']):
_distances[from_node] = {}
for to_node in range(data['num_locations']):
if from_node == to_node:
_distances[from_node][to_node] = 0
# Forbid start/end/reload node to be consecutive.
elif from_node in range(data['dup_depot_num']+1) and to_node in range(data['dup_depot_num']+1):
_distances[from_node][to_node] = data['vehicle_max_distance']
else:
_distances[from_node][to_node] = (manhattan_distance(
data['locations'][from_node], data['locations'][to_node]))
def distance_evaluator(manager, from_node, to_node):
"""Returns the manhattan distance between the two nodes"""
return _distances[manager.IndexToNode(from_node)][manager.IndexToNode(
to_node)]
return distance_evaluator
def add_distance_dimension(routing, manager, data, distance_evaluator_index):
"""Add Global Span constraint"""
distance = 'Distance'
routing.AddDimension(
distance_evaluator_index,
0, # null slack
data['vehicle_max_distance'], # 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['pickups']
def demand_evaluator(manager, from_node):
"""Returns the demand of the current node"""
return _demands[manager.IndexToNode(from_node)]
return demand_evaluator
def add_pickups_constraints(routing, manager, data, pickups_evaluator_index):
"""Adds capacity constraint"""
vehicle_capacity = data['vehicle_capacity']
capacity = 'pickups'
routing.AddDimension(
pickups_evaluator_index,
vehicle_capacity,
vehicle_capacity,
True, # since this is pickups, so start cumul should be zero
capacity)
def create_deliveries_evaluator(data):
"""Creates callback to get demands at each location."""
_deliveries = data['deliveries']
def deliveries_evaluator(manager, from_node):
"""Returns the demand of the current node"""
return _deliveries[manager.IndexToNode(from_node)]
return deliveries_evaluator
def add_deliveries_constraints(routing, manager, data, deliveries_evaluator_index):
"""Adds capacity constraint"""
vehicle_capacity = data['vehicle_capacity']
capacity = 'deliveries'
routing.AddDimension(
deliveries_evaluator_index,
vehicle_capacity,
vehicle_capacity,
False, # there is a initial capacity to be delivered
capacity)
###########
# Printer #
###########
def print_solution(data, manager, routing, assignment): # pylint:disable=too-many-locals
"""Prints assignment on console"""
print(f'Objective: {assignment.ObjectiveValue()}')
total_distance = 0
total_pickups = 0
# total_time = 0
total_deliveries = 0
pickups_dimension = routing.GetDimensionOrDie('pickups')
# time_dimension = routing.GetDimensionOrDie('Time')
deliveries_dimension = routing.GetDimensionOrDie('deliveries')
dropped = []
for order in range(6, routing.nodes()):
index = manager.NodeToIndex(order)
if assignment.Value(routing.NextVar(index)) == index:
dropped.append(order)
print(f'dropped orders: {dropped}')
for reload in range(1, 6):
index = manager.NodeToIndex(reload)
if assignment.Value(routing.NextVar(index)) == index:
dropped.append(reload)
print(f'dropped reload stations: {dropped}')
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = f'Route for vehicle {vehicle_id}:\n'
distance = 0
while not routing.IsEnd(index):
pickups_var = pickups_dimension.CumulVar(index)
deliveries_var = deliveries_dimension.CumulVar(index)
# time_var = time_dimension.CumulVar(index)
plan_output += ' {0} Pickups({1}) Deliveries({2})->'.format(
manager.IndexToNode(index),
assignment.Value(pickups_var),
assignment.Value(deliveries_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)
pickups_var = pickups_dimension.CumulVar(index)
deliveries_var = deliveries_dimension.CumulVar(index)
# time_var = time_dimension.CumulVar(index)
plan_output += ' {0} Pickups({1}) Deliveries({2})\n'.format(
manager.IndexToNode(index),
assignment.Value(pickups_var),
assignment.Value(deliveries_var)
# assignment.Min(time_var), assignment.Max(time_var)
)
plan_output += f'Distance of the route: {distance}m\n'
plan_output += f'Pickups of the route: {assignment.Value(pickups_var)}\n'
plan_output += f'Deliveries of the route: {assignment.Value(deliveries_var)}\n'
# plan_output += f'Time of the route: {assignment.Value(time_var)}min\n'
print(plan_output)
total_distance += distance
total_pickups += assignment.Value(pickups_var)
total_deliveries += assignment.Value(deliveries_var)
# total_time += assignment.Value(time_var)
print('Total Distance of all routes: {}m'.format(total_distance))
print('Total Pickups of all routes: {}'.format(total_pickups))
print('Total Deliveries of all routes: {}'.format(total_deliveries))
# 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()
print(data['locations'])
# Create the routing index manager
manager = pywrapcp.RoutingIndexManager(data['num_locations'],
data['num_vehicles'], data['depot'])
# Create Routing Model
routing = pywrapcp.RoutingModel(manager)
# Define weight of each edge
distance_evaluator_index = routing.RegisterTransitCallback(
partial(create_distance_evaluator(data), manager))
routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator_index)
# Add Distance constraint to minimize the longuest route
add_distance_dimension(routing, manager, data, distance_evaluator_index)
# Add Demand constraint
demand_evaluator_index = routing.RegisterUnaryTransitCallback(partial(create_demand_evaluator(data), manager))
add_pickups_constraints(routing, manager, data, demand_evaluator_index)
# Add deliveries constraint
deliveries_evaluator_index = routing.RegisterUnaryTransitCallback(
partial(create_deliveries_evaluator(data), manager))
add_deliveries_constraints(routing, manager, data, deliveries_evaluator_index)
# # 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.
pickups_dimension = routing.GetDimensionOrDie("pickups")
deliveries_dimension = routing.GetDimensionOrDie('deliveries')
# Allow to drop reloading nodes with zero cost.
for node in range(1, data['dup_depot_num']+1):
node_index = manager.NodeToIndex(node)
routing.AddDisjunction([node_index], 0)
for node in range(data['dup_depot_num']+1, len(data['pickups'])):
node_index = manager.NodeToIndex(node)
pickups_dimension.SlackVar(node_index).SetValue(0)
deliveries_dimension.SlackVar(node_index).SetValue(0) # ordinary node don't allow slack
# routing.AddDisjunction([node_index], 100_000) # Allow to drop regular node with a cost.
# Add Constraint: Pick + Deliveries <= max_capacity
for node in range(len(data['pickups'])):
index = manager.NodeToIndex(node)
routing.solver().Add(
pickups_dimension.CumulVar(index) + deliveries_dimension.CumulVar(index) <= data["vehicle_capacity"])
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
) # pylint: disable=no-member
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(3)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
if solution:
print_solution(data, manager, routing, solution)
else:
print("No solution found !")
if __name__ == '__main__':
main()