所以,我一直试图了解以下实验的问题是什么,但未能找到问题所在。 因此,下面是我正在使用的代码(请注意,有一个重复的节点,因为该节点既是提货节点又是交付节点):
"""Capacited Vehicles Routing Problem (CVRP)."""
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['distance_matrix'] = [
[ 0, 220, 460, 460, 700, 280, 610],
[220, 0, 570, 570, 670, 500, 500],
[460, 570, 0, 0, 350, 550, 450],
[460, 570, 0, 0, 350, 550, 450],
[700, 670, 350, 350, 0, 850, 250],
[280, 500, 550, 550, 850, 0, 830],
[610, 500, 450, 450, 250, 830, 0]
]
data['pickups_deliveries'] = [
[1, 2], #1,2
[3, 6], #3,4
[4, 5], #5,6
]
data['demands'] = [
0, # departs empty
1, # load in 1
-1, # unload in 2
1, # load in 3 (duplicate of 2)
1, # load in 4
-1, # unload in 5
-1] # unload in 5
data['vehicle_capacities'] = [1]
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()}')
total_distance = 0
total_load = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_distance = 0
route_load = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
route_load += data['demands'][node_index]
plan_output += ' {0} Load({1}) -> '.format(node_index, route_load)
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += ' {0} Load({1})\n'.format(manager.IndexToNode(index),
route_load)
plan_output += 'Distance of the route: {}m\n'.format(route_distance)
plan_output += 'Load of the route: {}\n'.format(route_load)
print(plan_output)
total_distance += route_distance
total_load += route_load
print('Total distance of all routes: {}m'.format(total_distance))
print('Total load of all routes: {}'.format(total_load))
def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Capacity constraint.
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data['vehicle_capacities'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity')
# Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimension(
transit_callback_index,
0, # no slack
3000, # vehicle maximum travel distance
True, # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)
# Define Transportation Requests.
for request in data['pickups_deliveries']:
pickup_index = manager.NodeToIndex(request[0])
delivery_index = manager.NodeToIndex(request[1])
routing.AddPickupAndDelivery(pickup_index, delivery_index)
routing.solver().Add(
routing.VehicleVar(pickup_index) == routing.VehicleVar(
delivery_index))
routing.solver().Add(
distance_dimension.CumulVar(pickup_index) <=
distance_dimension.CumulVar(delivery_index))
# 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.FromSeconds(1)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
if __name__ == '__main__':
main()
运行时,算法返回:
Objective: 264620
Route for vehicle 0:
0 Load(0) -> 1 Load(1) -> 2 Load(0) -> 3 Load(1) -> 6 Load(0) -> 4 Load(1) -> 5 Load(0) -> 0 Load(0)
Distance of the route: 2620m
Load of the route: 0
Total distance of all routes: 2620m
Total load of all routes: 0
这很好。现在,如果我仅将 pickups_deliveries
的顺序从节点 4->5
更改为 5->4
(只是颠倒它们的角色),由此说来
data['pickups_deliveries'] = [
[1, 2], #1,2
[3, 6], #3,4
[4, 5], #5,6
]
到此
data['pickups_deliveries'] = [
[1, 2], #1,2
[3, 6], #3,4
[5, 4], #5,6
]
并据此更改要求:
data['demands'] = [
0, # departs empty
1, # load in 1
-1, # unload in 2
1, # load in 3 (duplicate of 2)
1, # load in 4
-1, # unload in 5
-1] # unload in 6
对此:
data['demands'] = [
0, # departs empty
1, # load in 1
-1, # unload in 2
1, # load in 3 (duplicate of 2)
-1, # unload in 4
1, # load in 5
-1] # unload in 6
算法无法找到解决方案。当唯一改变的是最后一段的顺序时。我在这里做错了什么?任何帮助将非常感激! 提前致谢!
PD:一个可能的解决方案是:
- 出发时间为 (0),
- 在 1 中加载 ---> 在 2 中卸载,
- 在 3 中加载(与 2 相同的节点)---> 在 6 中卸载
- 加载5--->卸载4
最佳答案
如果您查看原始解决方案,我们可以看到
Distance of the route: 2620m
我们有
routing.AddDimension(
transit_callback_index,
0, # no slack
3000, # vehicle maximum travel distance
所以我很确定增加限制会有所帮助,所以让我们将其增加到 3500
你会得到:
./plop.py
Objective: 346430
Route for vehicle 0:
0 Load(0) -> 5 Load(1) -> 4 Load(0) -> 1 Load(1) -> 2 Load(0) -> 3 Load(1) -> 6 Load(0) -> 0 Load(0)
Distance of the route: 3430m
Load of the route: 0
Total distance of all routes: 3430m
Total load of all routes: 0
注意:
Distance of the route: 3430m
ps:下次请保留import
声明
pps:您的代码片段不起作用,因为您在距离矩阵中添加了一些 float ,请仅使用 int 矩阵或在回调中使用 return int(data[...][][])
关于python - 使用 OR-TOOLS 理解取货和送货阵列时遇到的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/73128897/