Мне нужно кодировать маршрут транспортного средства с несколькими ограничениями с помощью модуля pywrapcp, но я не смог найти надлежащую документацию или объяснение функций. Есть несколько примеров кодов, которые использовали ortools.constraint_solver, но они просты и не соответствуют моим потребностям. У меня есть матрица затрат и другие параметры, такие как время, расстояние, емкость, которые необходимо рассчитать, но я не знаю, как узнать об этом, есть ли документация, чтобы понять эту библиотеку? это мой код, представляющий собой комбинацию разных примеров, но я получаю неверный вывод:
from __future__ import print_function
from functools import partial
from six.moves import xrange
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, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],
[6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],
[9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],
[8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],
[7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],
[3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],
[6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],
[2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],
[3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],
[2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],
[6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],
[6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],
[4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],
[4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],
[5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],
[9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],
[7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],
]
data['distance_matrix']=[[0, 329, 146, 157, 318, 528, 457, 242, 491, 335, 471, 456, 391, 128, 461, 555, 460], [329, 0, 399, 384, 544, 493, 339, 378, 108, 243, 125, 394, 136, 561, 505, 315, 447], [146, 399, 0, 262, 471, 316, 297, 227, 548, 377, 267, 430, 383, 154, 234, 188, 400], [157, 384, 262, 0, 440, 271, 383, 525, 223, 367, 511, 354, 112, 539, 159, 152, 373], [318, 544, 471, 440, 0, 423, 112, 381, 346, 512, 161, 239, 581, 291, 284, 145, 143], [528, 493, 316, 271, 423, 0, 380, 196, 409, 212, 199, 277, 387, 515, 391, 261, 318], [457, 339, 297, 383, 112, 380, 0, 379, 298, 267, 482, 247, 462, 256, 296, 533, 200], [242, 378, 227, 525, 381, 196, 379, 0, 156, 230, 551, 555, 338, 372, 403, 358, 506], [491, 108, 548, 223, 346, 409, 298, 156, 0, 140, 532, 405, 531, 129, 220, 482, 222], [335, 243, 377, 367, 512, 212, 267, 230, 140, 0, 418, 440, 526, 255, 455, 296, 430], [471, 125, 267, 511, 161, 199, 482, 551, 532, 418, 0, 439, 285, 181, 254, 208, 304], [456, 394, 430, 354, 239, 277, 247, 555, 405, 440, 439, 0, 397, 229, 121, 385, 147], [391, 136, 383, 112, 581, 387, 462, 338, 531, 526, 285, 397, 0, 544, 205, 197, 226], [128, 561, 154, 539, 291, 515, 256, 372, 129, 255, 181, 229, 544, 0, 150, 204, 516], [461, 505, 234, 159, 284, 391, 296, 403, 220, 455, 254, 121, 205, 150, 0, 192, 544], [555, 315, 188, 152, 145, 261, 533, 358, 482, 296, 208, 385, 197, 204, 192, 0, 138], [460, 447, 400, 373, 143, 318, 200, 506, 222, 430, 304, 147, 226, 516, 544, 138, 0]]
time=data['time_matrix']
time2=[[time[i][j]*2 for i in range(len(time))]for j in range(len(time))]
distance=data['distance_matrix']
dis2=[[distance[a][b]*0.01 for a in range(len(distance))] for b in range(len(distance))]
total= [[time2[i][j]+dis2[i][j] for i in range(len(dis2))]for j in range(len(dis2))]
cost=[[int(total[i][j]*10) for i in range(len(total))]for j in range(len(total))]
#cost2=[[int(total[i][j]*100) for i in range(len(total))]for j in range(len(total))]
data['cost_matrix']=cost
data['demands'] = \
[0, # depot
1, 1, # 1, 2
2, 4, # 3, 4
2, 4, # 5, 6
8, 8, # 7, 8
1, 2, # 9,10
1, 2, # 11,12
4, 4, # 13, 14
8, 8] # 15, 16
data['vehicle_capacity'] = 15
data['num_vehicles'] = 4
data['vehicle_speed'] = 83
data['depot'] = 0
return data
def create_demand_evaluator(data):
"""Creates callback to get demands at each location."""
_demands = data['demands']
def demand_evaluator(manager, node):
"""Returns the demand of the current node"""
return _demands[manager.IndexToNode(node)]
return demand_evaluator
def print_solution(data, manager, routing, assignment):
"""Prints assignment on console."""
print('Objective: {}'.format(assignment.ObjectiveValue()))
time_dimension = routing.GetDimensionOrDie('Time')
total_distance = 0
total_load = 0
total_cost=0
total_time = 0
cost_dimension=routing.GetDimensionOrDie('Cost')
capacity_dimension = routing.GetDimensionOrDie('Capacity')
distance_dimension = routing.GetDimensionOrDie('Distance')
vehicles_order={}
cost_dimension.SetGlobalSpanCostCoefficient(100)
for vehicle_id in xrange(data['num_vehicles']):
order=[]
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
#distance = 0
while not routing.IsEnd(index):
order.append(manager.IndexToNode(index))
load_var = capacity_dimension.CumulVar(index)
time_var = time_dimension.CumulVar(index)
distance_var = distance_dimension.CumulVar(index)
cost_var=cost_dimension.CumulVar(index)
plan_output += ' {0} Load({1}) Time({2},{3}) Distance({4}) ->'.format(
manager.IndexToNode(index),
assignment.Value(load_var),
assignment.Min(time_var),
assignment.Max(time_var),
assignment.Value(distance_var))
previous_index = index
index = assignment.Value(routing.NextVar(index))
total_cost += routing.GetArcCostForVehicle(previous_index, index,
vehicle_id)
vehicles_order[vehicle_id]=order
load_var = capacity_dimension.CumulVar(index)
time_var = time_dimension.CumulVar(index)
plan_output += ' {0} Load({1}) Time({2},{3})\n'.format(
manager.IndexToNode(index),
assignment.Value(load_var),
assignment.Min(time_var), assignment.Max(time_var))
plan_output += 'Distance of the route: {0}m\n'.format(assignment.Value(distance_var))
plan_output += 'Load of the route: {}\n'.format(
assignment.Value(load_var))
plan_output += 'Time of the route: {}\n'.format(
assignment.Value(time_var))
plan_output += 'Cost of the route: {}\n'.format(
assignment.Value(cost_var))
print(plan_output)
total_distance += assignment.Value(distance_var)
total_load += assignment.Value(load_var)
total_time += assignment.Value(time_var)
total_cost+= assignment.Value(cost_var)
print('Total Distance of all routes: {0}m'.format(total_distance))
print('Total Load of all routes: {}'.format(total_load))
print('Total Time of all routes: {0}min'.format(total_time))
print('Total cost of all routes: {0}'.format(total_cost))
print('vehicle route order : {}'.format(vehicles_order))
def main():
"""Solve the VRP with time windows."""
data = create_data_model()
manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
data['num_vehicles'], data['depot'])
routing = pywrapcp.RoutingModel(manager)
def cost_callback(manager,from_index, to_index):
f_node = manager.IndexToNode(from_index)
t_node = manager.IndexToNode(to_index)
return data['cost_matrix'][f_node][t_node]
def time_callback(managr,from_index, to_index):
_total_time=data['time_matrix']
return _total_time[manager.IndexToNode(from_index)][manager.IndexToNode(
to_index)]
def distance_callback(manager,from_index,to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]
time_callback_index = routing.RegisterTransitCallback(time_callback)
cost_callback_index=routing.RegisterTransitCallback(cost_callback)
time = 'Time'
routing.AddDimension(
time_callback_index,
0, # allow waiting time
100, # maximum time per vehicle
False, # Don't force start cumul to zero.
time)
cost='Cost'
routing.AddDimension(
cost_callback_index,
30, # allow waiting time
10000, # maximum time per vehicle
False, # Don't force start cumul to zero.
cost)
cost_dimension = routing.GetDimensionOrDie(cost)
demand_evaluator_index = routing.RegisterUnaryTransitCallback(
partial(create_demand_evaluator(data), manager))
distance_callback_index=routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(cost_callback_index)
distance= 'Distance'
routing.AddDimension(
distance_callback_index,
0, # no slack
10000, # vehicle maximum travel distance
True, # start cumul to zero
distance)
#distance_dimension = routing.GetDimensionOrDie(distance)
cost_dimension.SetGlobalSpanCostCoefficient(100)
"""Adds capacity constraint"""
capacity = 'Capacity'
routing.AddDimension(
demand_evaluator_index,
0, # null capacity slack
data['vehicle_capacity'],
True, # start cumul to zero
capacity)
for i in range(data['num_vehicles']):
routing.AddVariableMinimizedByFinalizer(
cost_dimension.CumulVar(routing.Start(i)))
routing.AddVariableMinimizedByFinalizer(
cost_dimension.CumulVar(routing.End(i)))
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.log_search = False
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.time_limit.seconds = 100
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
print_solution(data, manager, routing, assignment)
if __name__ == '__main__':
main()