ortools vrp не дает мне никакого решения

Я хочу решить проблему с маршрутизацией транспортного средства с помощью ORTools, будет использоваться матрица расстояния и продолжительности. но проблема в том, что когда я меняю матрицу, это больше не дает мне никаких решений! есть 2 группы матриц. с прокомментированными матрицами решение есть, а с другой группой - нет. Вы хоть представляете, почему это происходит:

from __future__ import print_function
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, 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]]
    
    data['distance_matrix']=[[0, 228, 299, 301, 235, 208, 405, 447, 144, 579], [228, 0, 343, 288, 357, 426, 530, 510, 122, 490], [299, 343, 0, 236, 228, 523, 274, 377, 397, 530], [301, 288, 236, 0, 594, 523, 289, 397, 154, 380], [235, 357, 228, 594, 0, 558, 370, 444, 173, 558], [208, 426, 523, 523, 558, 0, 219, 278, 504, 507], [405, 530, 274, 289, 370, 219, 0, 195, 283, 257], [447, 510, 377, 397, 444, 278, 195, 0, 407, 417], [144, 122, 397, 154, 173, 504, 283, 407, 0, 273], [579, 490, 530, 380, 558, 507, 257, 417, 273, 0]]
     data['time_matrix']=[[0, 205, 519, 308, 428, 574, 399, 138, 573, 541], [205, 0, 447, 578, 296, 536, 135, 345, 198, 315], [519, 447, 0, 209, 438, 174, 231, 382, 104, 522], [308, 578, 209, 0, 235, 264, 492, 305, 134, 538], [428, 296, 438, 235, 0, 600, 177, 435, 204, 556], [574, 536, 174, 264, 600, 0, 476, 119, 183, 476], [399, 135, 231, 492, 177, 476, 0, 497, 208, 167], [138, 345, 382, 305, 435, 119, 497, 0, 344, 454], [573, 198, 104, 134, 204, 183, 208, 344, 0, 422], [541, 315, 522, 538, 556, 476, 167, 454, 422, 0]]
    data['cost_matrix']=[[0, 160, 135, 433, 581, 453, 336, 329, 343, 237], [160, 0, 313, 596, 576, 458, 264, 380, 348, 354], [135, 313, 0, 591, 391, 211, 561, 236, 304, 414], [433, 596, 591, 0, 539, 253, 427, 300, 214, 118], [581, 576, 391, 539, 0, 243, 521, 499, 560, 255], [453, 458, 211, 253, 243, 0, 571, 216, 121, 314], [336, 264, 561, 427, 521, 571, 0, 425, 271, 165], [329, 380, 236, 300, 499, 216, 425, 0, 425, 549], [343, 348, 304, 214, 560, 121, 271, 425, 0, 176], [237, 354, 414, 118, 255, 314, 165, 549, 176, 0]]
    data['num_vehicles'] = 4
    data['depot'] = 0
    return data


def print_solution(data, manager, routing, assignment):
"""Prints assignment on console."""
total_cost ,total_distance,total_time= 0,0,0
print('Objective: {}'.format(assignment.ObjectiveValue()))
distance_dimension=routing.GetDimensionOrDie('Distance')
time_dimension=routing.GetDimensionOrDie('Time')
for vehicle_id in range(data['num_vehicles']):
    index = routing.Start(vehicle_id)
    plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
    route_cost = 0
    route_distance = 0
    route_time = 0
    while not routing.IsEnd(index):
        plan_output += ' {} -> '.format(manager.IndexToNode(index))
        distance_var=distance_dimension.CumulVar(index)
        time_var=time_dimension.CumulVar(index)
        previous_index = index
        index = assignment.Value(routing.NextVar(index))
        route_cost += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
        route_distance+=assignment.Value(distance_var)
        route_time+=assignment.Value(time_var)
    plan_output += '{}\n'.format(manager.IndexToNode(index))
    plan_output += 'Cost of the route: {0}\nDistance of the route: {1}m\nTime of route: {2}\n'.format(
        route_cost,
        route_distance,
        route_time)
    print(plan_output)
    total_cost += route_cost
    total_time+=route_time
    total_distance+=route_distance
print('Total Cost of all routes: {}\nTotal Distance of all routes: {}\nTotal Time of all routes: {}\n'.format(total_cost,total_distance,total_time))

def get_routes(manager, routing, solution, num_routes):
"""Get vehicle routes from a solution and store them in an array."""
# Get vehicle routes and store them in a two dimensional array whose
# i,j entry is the jth location visited by vehicle i along its route.
routes = []
for route_nbr in range(num_routes):
    index = routing.Start(route_nbr)
    route = [manager.IndexToNode(index)]
    while not routing.IsEnd(index):
        index = solution.Value(routing.NextVar(index))
        route.append(manager.IndexToNode(index))
    routes.append(route)
return routes

def main():
# Instantiate the data problem.
data = create_data_model()

# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['cost_matrix']), data['num_vehicles'], data['depot'])

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

# Create and register a transit callback.
def cost_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['cost_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(cost_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add Cost constraint.
routing.AddDimension(
    transit_callback_index,
    0,  # no slack
    3000,  # vehicle maximum travel distance
    False,  # start cumul to zero
    'Cost')
cost_dimension = routing.GetDimensionOrDie('Cost')
cost_dimension.SetGlobalSpanCostCoefficient(1000)

#Add Distance constraint.
def distance_callback(from_index,to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]

distance_callback_index=routing.RegisterTransitCallback(distance_callback)
routing.AddDimension(
    distance_callback_index,
    0,
    3000,
    False,
    'Distance')
distance_dimension=routing.GetDimensionOrDie('Distance')

#Add Time constraint.
def time_callback(from_index,to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['time_matrix'][from_node][to_node]

time_callback_index=routing.RegisterTransitCallback(time_callback)
routing.AddDimension(
    time_callback_index,
    0,
    300,
    False,
    'Time')
time_dimension=routing.GetDimensionOrDie('Time')

# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.solution_limit = 100
search_parameters.time_limit.seconds = 3

# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)

# Print solution on console.
if assignment:
    print_solution(data, manager, routing, assignment)
routes = get_routes(manager, routing, assignment, data['num_vehicles'])
# Display the routes.
for i, route in enumerate(routes):
    print('Route', i, route)

if __name__ == '__main__':
main()

person k_afr    schedule 14.02.2020    source источник


Ответы (1)


Ничто не могло означать, что не нашло решения. Скорее всего, ваши лимиты занижены, увеличив лимиты, работает нормально. но для лучшего понимания лучше проверить статус решателя. Ошибки ограничения времени в основном относятся к низким ограничениям. в этом примере у нас есть много значений больше 300 во временной матрице, но максимальное время для каждого транспортного средства равно 300, поэтому для этой проблемы нет приемлемого решения.

person k_afr    schedule 15.02.2020
comment
Как вы проверяете статус решателя? Использование routing.solver.status() не работает, поскольку solver не является методом pywrapcp.RoutingModel(manager). Что такое solver метод? - person geominded; 17.03.2021
comment
Пример в документации кажется бесполезным, поскольку мы не знаем, как solver был создан как :( разработчики .google.com / optimisation / routing / routing_options - person geominded; 17.03.2021