OR-Tools-TSP

时间：2023-06-23 01:37:00 2408连接器

https://developers.google.cn/optimization/routing/vrptw
模型学习中，如有理解不对希望大家帮忙指正。
下面的例子修改了原解释案例中的目标

VRP问题(经典旅游推销员和车辆路径)

概述

在大多数情况下，VRP有限制：例如，车辆可能有能力携带最大重量或体积的物品，或要求驾驶员在客户要求的指定时间窗口内访问位置。或者工具可以解决各种类型的问题VRP，包括以下内容：

商旅问题（TSP），经典的路线问题(只有一辆车)
车辆路径问题，多车辆TSP的推广。
CVRP，容量限制VRP，车辆对其可携带物品的容量最大。
VRPTWs，有时间窗VRP，车辆必须在指定的时间间隔内访问这些位置。
VRPTW，有资源限制VRP，例如，在车辆段（路线起点）装卸车辆的空间或人员。
放弃访问的VRP，车辆不需要访问所有位置，但每次放弃的访问必须支付罚款。

注：车辆路径问题本质上难以解决：随着问题规模的增加，解决这些问题所需的时间呈指数级增长。对于特大问题，可能需要OR-Tools（或任何其他路由软件）数年才能找到最佳解决方案。OR-Tools有时候返回的不是最优解。

1.图片注释
蓝色圆圈是16个需要访问的节点；黑色圆圈的起始位置，即车辆(商人)的起始位置。
2.需求
从0节点出发，车辆(商人)应访问1-16个节点。
3.数据说明
1）distance_matrix：每个节点之间的距离，即距离矩阵，是一个数组，表示从节点i到节点j的距离（以米为单位，可由实际业务场景修改）
2)距离矩阵的位置顺序是任意的，与访问顺序无关
3）num_vehicles：这里默认为1，因为这是一个TSP(车辆路径问题（VRP），车辆数量可大于1)
4）depot：车场，即路线的起点和终点。在这种情况下，depot为0节点

（二）代码逻辑

1.创建数据集
2.创建routing model

代码

from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp   ######################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################## # 创建数据 # ######################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################## def create_data_model():     data = { 
        }     # 矩阵     distance_matrix= [         [0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],         [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],
        [713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],
        [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],
        [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],
        [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],
        [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],
        [213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],
        [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],
        [875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],
        [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],
        [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],
        [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0]
    ] 
    data['distance_matrix'] = distance_matrix
    # 车辆数
    data['num_vehicles'] = 1 
    # 车辆起始
    data['depot'] = 0 
    return data

#########################################################################
# 创建routing model #
#########################################################################
''' 作用： 1.创建索引管理器（manager）和 routing model （routing） 2.manager.IndexToNode 方法的作用是将求解器内部的索引转换为numbers for locations（下标？） 3.numbers for locations与距离矩阵的索引相对应 '''
data = create_data_model()
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                       data['num_vehicles'], 
                                       data['depot'])
routing = pywrapcp.RoutingModel(manager)

#############################################################
# 创建距离的callback函数
##############################################################
''' 作用： 1.使用routing solver,需要创建一个距离的回调函数：一个用于获取任意位置对并返回它们之间的距离的函数。最简单的方法是使用距离矩阵。 2.回调函数接收两个参数，from_index和to_index，并返回距离矩阵的相应条目 '''
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]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
      

######################################################
# Set the cost of travel # 费用
######################################################

''' 作用：设置arc cost evaluator arc cost evaluator告诉解算器如何计算任意两个位置之间的旅行成本，即问题的图形中连接它们的边（或圆弧）的成本。 在本例中，arc cost evaluator是transit_callback_index，它是解算器对距离回调函数的内部引用。本例中，任何两个地点之间的旅行成本只是它们之间的距离。成本也可能涉及其他因素。 '''
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)


######################################################
# 设置搜索参数 #
####################################################################
''' 作用：设置默认搜索参数和用于查找第一个解决方案的启发式方法 将第一个解决方案策略设置给PATH_CHEAPEST_ARC， 该策略通过重复添加权重最小的边来为求解器创建初始路由，这些边不会指向以前访问过的节点（车场除外） '''
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

####################################################################
# 添加解决方案printer #
####################################################################
''' 作用： 1.该函数返回并展示求解器的结，并从解决方案中提取路由并将其打印到console。 2.该函数通过ObjectiveValue（）显示最佳路线及其距离， '''
#
####################################################################
def print_solution(manager, routing, solution):
    print('Objective: {} meter'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    plan_output = 'Route for vehicle 0:\n'
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += ' {} ->'.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += ' {}\n'.format(manager.IndexToNode(index))
    print(plan_output)
    plan_output += 'Route distance: {}miles\n'.format(route_distance)

####################################################################
# 求解并打印解决方案
# 最后，可以调用求解器并打印解决方案，返回解决方案并显示最佳路线
####################################################################
solution = routing.SolveWithParameters(search_parameters)
if solution:
    print_solution(manager, routing, solution)

锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

OR-Tools-TSP

相关文章