Refuelling and optional nodes in a VRP

Question

I am using the Google OR-Tools librairy for Python to solve a VRP problem.
My problem is quite simple :
It is a basic VRP problem where vehicles are "cleaning vehicles" responsible to clean some roads. The vehicles have a water tank and each of these roads consume a certain amount of water.
I have been able to implement the refuelling aspect in the problem but there is still one problem. For my VRP, the refuelling nodes must not be necessarily visited (e.g a vehicle that has enough water in its tank to solve the problem will not loose time refuelling its tank for nothing). I used the method AddDisjunction to solve this, it seemed to work when the vehicle must only do one water refill. If its tank capacity is lower than the half of the total water volume to clean all the roads, OR-Tools cannot solve the problem... When I disable the disjunction on the refill nodes, OR-Tools solves the problem and the vehicle does the refill two times.
So OR-Tools seems to want either (with only one vehicle to simplify) :

to make the refuelling nodes optional but only of them can be visited, so the problem cannot be solved if the tank vehicle capacity is too low
to make the refuelling nodes mandatory and the problem is solved the right way except that all the refuelling nodes must be visited (therefore solution may not be optimal)

My code is the following :

    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 !')

I have plotted the solution that must be generated with the following problem parameters :

Number of vehicle : 1
Water volume to clean all roads : 1410
Water tank volume : 500
Refuelling nodes locations : (21, 31) and (20, 2)

Here is the plot : Vehicle route to solve the problem

The number are the the order of visit, the red line are the road that has to be cleaned (round-trip)

I would really appreciate if anybody could help me with that :)

Have a nice day !

It works fine if the refill nodes are not at the "same" position. I add code to duplicate refill nodes if the tank capacity of the vehicles is too low (that way a vehicle can refill its tank on the same node many times) and it is not working anymore.
The duplicate refill nodes have the same "links" to other nodes as the original node. The distances between all the nodes representing the same refill node are equal to zero (because it is the same).
I don't really understand why it not working like that, here is what happens :

If each vehicle need only to do one stop (or zero) to a refill node, a solution is found BUT all the refill nodes are visited --> if a vehicle go to a refill node, he will visit all the duplicated ones in a row. With the disjunction, he would not need to do so...
If one vehicle need to do more than one stop to a refill node, then OR-Tools cannot find any solution...

I'm really out of ideas and I need these points to be visited many times if needed...

Refuelling and optional nodes in a VRP

Answers (1)

Related Questions