VRP中的加油和可选节点

Question

我正在使用Google Or-Tools库来解决VRP问题。
我的问题很简单：
这是一个基本的VRP问题，其中车辆“清洁车辆”负责清洁某些道路。车辆有一个水箱，每条道路都会消耗一定数量的水。
我已经能够在问题中实施加油方面，但仍然存在一个问题。对于我的VRP而言，不一定要访问加油的节点（例如，在其水箱中有足够的水以解决问题的车辆不会花费时间将其储罐加油的时间零散）。 我使用了方法 adddisJuntion 来解决此问题，当车辆只能进行一次水上补充时，它似乎可以工作。如果其水箱容量低于总水量的一半以清洁所有道路，则无法解决问题……当我禁用补充节点上的分离时，OR-Tools可以解决问题，并且车辆确实可以解决问题。补充两次。
因此，Or-Tools似乎想要（只有一辆工具可以简化）：

• 才能使加油节点可选，但只能参观其中的节点，因此问题不能是解决了油罐车的容量太低，
• 无法强制加油节点，并且以正确的方式解决了问题，除非必须访问所有加油节点（因此解决方案可能不是最佳的）

我的代码：

    def solve_problem(self):
        data = self.problem_data

        # Create the routing index manager.
        manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'],
                                               data['starts'], data['ends'])

        # 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 Distance constraint.
        distance_dimension_name = 'Distance'
        routing.AddDimension(
            transit_callback_index,
            0,  # no slack
            self.max_distance_to_travel,  # vehicle maximum travel distance
            True,  # start cumul to zero
            distance_dimension_name)

        distance_dimension = routing.GetDimensionOrDie(distance_dimension_name)
        distance_dimension.SetGlobalSpanCostCoefficient(100)

        # create and register a callback to set the water cost on each node
        def water_cost_callback(from_index):
            """Returns the distance between the two nodes."""
            # Convert from routing variable Index to distance matrix NodeIndex.
            from_node = manager.IndexToNode(from_index)
            return -(data['water_cost'][from_node])

        water_callback_index = routing.RegisterUnaryTransitCallback(water_cost_callback)

        # Add water cost constraint.
        water_dimension_name = 'Water'
        routing.AddDimensionWithVehicleCapacity(
            water_callback_index,
            int(np.sum(data['water_cost'])),
            data['vehicles_capacity'],
            False,
            water_dimension_name)

        water_dimension = routing.GetDimensionOrDie(water_dimension_name)

        # only let slack free for refueling nodes.
        for i in range(len(data['distance_matrix'])):
            idx = manager.NodeToIndex(i)
            if (i not in data['refill']) and (i not in data['starts']) and (i not in data['ends']):
                water_dimension.SlackVar(idx).SetValue(0)

        # for each refill node, set that it has to be necessarily visited
        refill_nodes = [manager.NodeToIndex(i) for i in data['refill']]
        routing.AddDisjunction(refill_nodes, 0)

        search_parameters = pywrapcp.DefaultRoutingSearchParameters()
        search_parameters.first_solution_strategy = (
            routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC)

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

        if solution:
            # build the solution array
            vehicle_routes = []
            max_route_distance = 0
            for vehicle_id in range(data['num_vehicles']):
                vehicle_route = []
                route_distance = 0
                index = routing.Start(vehicle_id)
                while not routing.IsEnd(index):
                    vehicle_route.append(manager.IndexToNode(index))
                    previous_index = index
                    index = solution.Value(routing.NextVar(index))
                    route_distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
                vehicle_route.append(manager.IndexToNode(index))
                vehicle_routes.append(self.reformat_solution_array(vehicle_route))
                max_route_distance = max(route_distance, max_route_distance)
            # print('Maximum of the route distances: {}m'.format(max_route_distance))

            print_solution_ortools(data, manager, routing, solution)

            return vehicle_routes, max_route_distance
        else:
            print('No solution found !')

我已经绘制了我的代码 ：必须使用以下问题参数生成的解决方案：

• 车辆数量：1
• 水量以清洁所有道路：1410
• 水箱量：500
• 加油节点位置：（21，31）和（20，2）

这是图：< a href =“ https://i.sstatic.net/fv11v.png” rel =“ nofollow noreferrer”>解决问题的车辆路线

这个数字是访问的顺序，红线是道路必须清理（往返），

如果有人能帮助我，我真的很感激:)

祝您有美好的一天！

---

如果补充节点不在“相同”位置，则可以正常工作。 如果车辆的储罐容量太低（这样，车辆可以多次在同一节点上重新填充其储罐），并且它不再起作用。

重复的补充节点与其他节点具有与原始节点相同的“链接”。代表相同补充节点的所有节点之间的距离等于零（因为它是相同的）。
我真的不明白为什么它不那么工作，这就是发生的事情：

• 如果每辆车只需要一个站（或零）到补充节点，则找到解决方案，但 访问了补充节点 - ＆gt;如果车辆转到补充节点，他将连续访问所有重复的节点。有了析取，他就不需要这样做...
• 如果一辆车需要多个一个以上的插入节点，那么Or-Tools就找不到任何解决方案...

我真的没有想法，我需要如果需要的话，这些点要多次访问...

Answer 1

在您使用的代码中：

# for each refill node, set that it has to be necessarily visited
refill_nodes = [manager.NodeToIndex(i) for i in data['refill']]
routing.AddDisjunction(refill_nodes, 0)

这意味着所有补充节点都是相同析取的一部分，因此求解器只需要访问其中一个（集合的ED基数为1）。

But you want one disjunction per refill node...

So you should instead use:

for i in data['refill']:
    index = manager.NodeToIndex(i)
    routing.AddDisjunction([index], 0)

ref: