不访问每个节点的CVRP
创始人
2024-12-24 00:30:27
0次

以下是一个解决“不访问每个节点的CVRP”的示例代码:

import numpy as np
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def solve_cvrp_without_visiting_all_nodes(num_vehicles, num_nodes, vehicle_capacities, demands, distances):
    # 创建求解器
    routing = pywrapcp.RoutingModel(num_nodes, num_vehicles, 0)
    
    # 设置车辆容量限制
    def vehicle_capacity_callback(from_index):
        # 获取节点索引
        node_index = routing.IndexToNode(from_index)
        return vehicle_capacities[node_index]
    
    capacity_callback_index = routing.RegisterUnaryTransitCallback(vehicle_capacity_callback)
    routing.AddDimensionWithVehicleCapacity(capacity_callback_index, 0, vehicle_capacities, True, "Capacity")
    
    # 设置节点需求
    def demand_callback(from_index):
        # 获取节点索引
        node_index = routing.IndexToNode(from_index)
        return demands[node_index]
    
    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(demand_callback_index, 0, demands, True, "Demand")
    
    # 设置距离回调函数
    def distance_callback(from_index, to_index):
        # 获取节点索引
        from_node = routing.IndexToNode(from_index)
        to_node = routing.IndexToNode(to_index)
        return distances[from_node][to_node]
    
    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
    # 设置每个车辆的起始节点
    for vehicle_id in range(num_vehicles):
        start_node = 0  # 起始节点为0
        routing.SetArcCostEvaluatorOfVehicle(transit_callback_index, vehicle_id, distance_callback)
        routing.AddDisjunction([start_node], 0)  # 不访问其他节点
    
    # 设置搜索参数
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    
    # 解决问题
    solution = routing.SolveWithParameters(search_parameters)
    
    # 输出解决方案
    if solution:
        total_distance = 0
        total_demand = 0
        for vehicle_id in range(num_vehicles):
            index = routing.Start(vehicle_id)
            plan_output = f"Vehicle {vehicle_id}:\n"
            route_distance = 0
            route_demand = 0
            while not routing.IsEnd(index):
                node_index = routing.IndexToNode(index)
                next_node_index = routing.IndexToNode(solution.Value(routing.NextVar(index)))
                route_distance += routing.GetArcCostForVehicle(node_index, next_node_index, vehicle_id)
                route_demand += demands[node_index]
                plan_output += f" -> {node_index}"
                index = solution.Value(routing.NextVar(index))
            plan_output += f" -> {routing.IndexToNode(index)}\n"
            plan_output += f"Distance of the route: {route_distance}m\n"
            plan_output += f"Demand of the route: {route_demand}\n"
            print(plan_output)
            total_distance += route_distance
            total_demand += route_demand
        print(f"\nTotal distance of all routes: {total_distance}m")
        print(f"Total demand of all routes: {total_demand}")
    else:
        print("No solution found!")

# 示例数据
num_vehicles = 2
num_nodes = 6
vehicle_capacities = [10, 10]
demands = [0, 1, 2, 3, 4, 5]
distances = [[0, 1, 2, 3, 4, 5],
             [1, 0, 1, 2, 3, 4],
             [2, 1, 0, 1, 2, 3],
             [3, 2, 1, 0, 1, 2],
             [4, 3, 2, 1, 0, 1],
             [5, 4, 3, 2, 1, 0]]

# 解决问题
solve_cvrp_without_visiting_all_nodes(num_vehicles, num_nodes, vehicle_capacities, demands, distances)

请注意,这个示例使用Google OR-Tools库来解决CVRP问题。在这个示例中,我们通过设置

相关内容

热门资讯

科普攻略透视挂!久久大厅辅助透... 科普攻略透视挂!久久大厅辅助透视挂,中至常熟麻将真的有外挂,一贯有人有挂1、金币登录送、破产送、升级...
迎来新发展透视挂!寓教娱乐辅助... 迎来新发展透视挂!寓教娱乐辅助透视挂,天天温岭麻将存在有外挂,切实有挂透明挂1、实时寓教娱乐透视辅助...
技巧知识分享透视挂!哥哥斗地主... 技巧知识分享透视挂!哥哥斗地主辅助透视挂,都城麻将真的有外挂,果然有挂头条1、打开软件启动之后找到中...
热点推荐透视挂!极速暗宝辅助透... 热点推荐透视挂!极速暗宝辅助透视挂,开心廉江麻将是真的有外挂,都是有挂规律1)极速暗宝辅助插件:进一...
大神推荐开挂!随意玩辅助透视挂... 大神推荐开挂!随意玩辅助透视挂,灵飞承德麻将确实有外挂,真是有挂攻略暗藏猫腻,小编详细说明随意玩破解...
我来教大家辅助!云海辅助透视挂... 我来教大家辅助!云海辅助透视挂,原味麻将真的是有外挂,真是有挂攻略;1、在云海插件功能辅助器技巧中,...
据目击者称开挂!大胜跑得快辅助... 据目击者称开挂!大胜跑得快辅助透视挂,新上游真的有外挂,果然有挂方法1、大胜跑得快辅助软件下载优化,...
这一问题亟待解决开挂!追忆辅助... 这一问题亟待解决开挂!追忆辅助透视挂,土豆棋牌真的是有外挂,原来有挂存在1、全新机制【追忆ai辅助工...
每日必看教程辅助!同城游红十辅... 每日必看教程辅助!同城游红十辅助透视挂,中至常熟麻将真的是有外挂,都是有挂功能同城游红十破解侠是真的...
科技新动态透视挂!决胜奕福辅助... 科技新动态透视挂!决胜奕福辅助透视挂,happyworkbook存在有外挂,竟然果真有挂1、该软件可...