3
$\begingroup$

I am using or-tools to solve a CVRP with multiple time window, and multiple location. Meaning that a customer can move during the day. I can't achieve to add constraint like if i deliver the customer once i don't need to deliver him again in his next/previous location. For now i tried defined Sets of delivery but i'm not sure to really understand how it works.

def solve(self):
        print("INIT SOLVER")
        self.manager = pywrapcp.RoutingIndexManager(len(self.data['time_matrix']), self.data["num_vehicles"], self.data['depot'])
        self.routing = pywrapcp.RoutingModel(self.manager)

        def time_callback(from_index, to_index):
            # Convert from self.routing variable Index to time matrix NodeIndex.
            from_node = self.manager.IndexToNode(from_index)
            to_node = self.manager.IndexToNode(to_index)
            return self.data['time_matrix'][from_node][to_node]

        def demand_callback(from_index):
            # Convert from self.routing variable Index to demands NodeIndex.
            from_node = self.manager.IndexToNode(from_index)
            return self.data['demands'][from_node]

        transit_callback_index = self.routing.RegisterTransitCallback(time_callback)
        self.routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

        #transit_callback_index = self.routing.RegisterTransitCallback(self.distance_callback)
        #self.routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

        demand_callback_index = self.routing.RegisterUnaryTransitCallback(demand_callback)
        self.routing.AddDimensionWithVehicleCapacity(demand_callback_index,0,  # null capacity slack
            self.data['vehicle_capacities'],  # vehicle maximum capacities
            True,  # start cumul to zero
            'Capacity')

        time = 'Time'
        self.routing.AddDimension(transit_callback_index, 30,  self.T, False, time)
        time_dimension = self.routing.GetDimensionOrDie(time)

        #SETTING UP TIME WINDOWS
        for location_idx, time_window in enumerate(self.data['time_windows']):
            if location_idx == self.data['depot']:
                continue
            index = self.manager.NodeToIndex(location_idx)
            time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])



        depot_idx = self.data['depot']
        for vehicle_id in range(self.data['num_vehicles']):
            index = self.routing.Start(vehicle_id)
            time_dimension.CumulVar(index).SetRange(
                self.data['time_windows'][depot_idx][0],
                self.data['time_windows'][depot_idx][1])

        for i in range(self.data['num_vehicles']):
            self.routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(self.routing.Start(i)))
            self.routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(self.routing.End(i)))

        #DEFINING CUSTOMER CLUSTER
        print(self.data["index"])
        for i in self.data['index']:
            print(i)
            delivery_node = i.copy()
            delivery_index = []
            for z in delivery_node:
                delivery_index.append(self.manager.NodeToIndex(z))
            delivery_disjunction_index = self.routing.AddDisjunction(delivery_index, -1)
            self.routing.AddPickupAndDeliverySets(0, delivery_disjunction_index)
        print("Done")

        search_parameters = pywrapcp.DefaultRoutingSearchParameters()
        search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
        #search_parameters.local_search_metaheuristic = (
        #routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
        #search_parameters.time_limit.FromSeconds(10)

        print("Start solver")

        self.solution = self.routing.SolveWithParameters(search_parameters)

        if self.solution:
            self.display_solution()```
$\endgroup$
2
  • 1
    $\begingroup$ Maybe add a disjunction constraint on the nodes of a customer. Example $\endgroup$ Nov 30, 2022 at 8:06
  • $\begingroup$ I don't get how to do it, i tried to add disjunction on each customer, and add a constraint like sum(visited customer location) == 1, but it can t find any solution. Is it possible to "delete" the constraint that say that each node has to be visited and replace it by something like : all set of node has to be visited once ? $\endgroup$
    – Cyprien
    Dec 3, 2022 at 21:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.