ortools vrp remained fuel constraint

39 Views Asked by At

I'm working on a VRP (Vehicle Routing Problem) that involves the following complexities:

  1. Start and end at an arbitrary node (node 0 represents the first row and column of the cost matrix).
  2. Multiple charging stations are available (charging stations are replicated across nodes).
  3. Vehicles have different speeds.

My primary challenge is ensuring that when a vehicle finishes visiting a node, its remaining fuel (or available operation time) is sufficient to reach the nearest charging station. I am currently using a fuel_dimension to track the remaining fuel. However, I'm struggling with enforcing the constraint that the remaining fuel must always be greater than the required fuel (or travel time) to reach the nearest charging station.

The varying speeds of each vehicle add complexity to this problem. Here's a snippet of my current implementation

        fuel_callback_indices = []
        for v_id in range(self.mission["n_vehicle"]):
            def vehicle_fuel_callback(from_index, to_index, i=v_id):
                from_node = manager.IndexToNode(from_index)
                to_node = manager.IndexToNode(to_index)
                transit_dist = (self.mission["distance_matrix"][from_node][to_node] / self.vehicle_vel[i] * self.scale)
                return -int(transit_dist)
            fuel_callback_index = routing.RegisterTransitCallback(vehicle_fuel_callback)
            fuel_callback_indices.append(fuel_callback_index)

        fuel_dimension_name = "fuel"
        routing.AddDimensionWithVehicleTransitAndCapacity(
            fuel_callback_indices,
            int(np.max(self.vehicle_max_time) * self.scale),
            (self.vehicle_max_time * self.scale).astype(int),
            False,
            fuel_dimension_name)
        fuel_dimension = routing.GetDimensionOrDie(fuel_dimension_name)

        for v in range(self.mission["n_vehicle"]):
            fuel_dimension.SlackVar(routing.Start(v)).SetValue(0)
            fuel_dimension.CumulVar(routing.Start(v)).SetValue(int(self.vehicle_initial_remained_time[v]*self.scale))

        penalty = 0
        for node in range(len(self.mission["distance_matrix"])):
            if (node in self.mission["starts"]) or (node in self.mission["ends"]):
                continue
            elif node in self.mission["task"]:
                index = manager.NodeToIndex(node)
                fuel_dimension.SlackVar(index).SetValue(0)
                routing.AddVariableMinimizedByFinalizer(fuel_dimension.CumulVar(index))
            else:
                index = manager.NodeToIndex(node)
                routing.AddDisjunction([index], penalty)

        solver = routing.solver()
        for node in range(len(self.mission["distance_matrix"])):
            if node in self.mission["charging_station"]:
                index = manager.NodeToIndex(node)
                if (index % self.vehicle_type_num) == 0:
                    solver.Add(fuel_dimension.CumulVar(index)+fuel_dimension.SlackVar(index) == int(self.vehicle_max_time[0]*self.scale))
                elif (index % self.vehicle_type_num) == 1:
                    solver.Add(fuel_dimension.CumulVar(index)+fuel_dimension.SlackVar(index) == int(self.vehicle_max_time[1]*self.scale))
                else:
                    raise NotImplementedError

Could anyone provide insights or suggestions on how to effectively implement this constraint, considering the different vehicle speeds? Any advice or direction towards relevant resources would be greatly appreciated.

Thank you!

0

There are 0 best solutions below