constraints - How to assign grouped orders to a single vehicle in a routing problem with OR-Tools? - Stack Overflow

admin管理员组

文章数量:1432334

I am working on a routing problem using OR-Tools where groups of orders (containers) must be delivered by the same vehicle, but any vehicle can be assigned to the group. The orders within a group cannot be split between vehicles, and the solver should optimize the assignment of groups to vehicles.

Here is what I have tried so far:

I imposed a constraint ensuring that each group is served by at most one vehicle, but the solver couldn't find a solution.

for i in range(self.num_items):
    group = self.items_group[i]
    idx = i+self.num_depots
    group_vehicles[group].append(self.routing.VehicleVar(self.manager.NodeToIndex(idx)))

for v_list in group_vehicles.values():
    used_vehicles = [v for v in v_list if v>-1]
    constraint = len(used_vehicles)==0 or self.routing.solver().Max(used_vehicles)==self.routing.solver().Min(used_vehicles)
    self.routing.solver().Add(constraint>0)

I attempted to add pairwise constraints between orders within the same group to ensure they are served by the same vehicle, but this approach also failed to work.

I am struggling to implement this requirement correctly. Obviously the problem does have a solution and just to be sure I'm working without any other constraint but this. Does anyone have any suggestions on how to model this type of constraint in OR-Tools?

Thanks in advance for your help!

I am working on a routing problem using OR-Tools where groups of orders (containers) must be delivered by the same vehicle, but any vehicle can be assigned to the group. The orders within a group cannot be split between vehicles, and the solver should optimize the assignment of groups to vehicles.

Here is what I have tried so far:

I imposed a constraint ensuring that each group is served by at most one vehicle, but the solver couldn't find a solution.

for i in range(self.num_items):
    group = self.items_group[i]
    idx = i+self.num_depots
    group_vehicles[group].append(self.routing.VehicleVar(self.manager.NodeToIndex(idx)))

for v_list in group_vehicles.values():
    used_vehicles = [v for v in v_list if v>-1]
    constraint = len(used_vehicles)==0 or self.routing.solver().Max(used_vehicles)==self.routing.solver().Min(used_vehicles)
    self.routing.solver().Add(constraint>0)

I attempted to add pairwise constraints between orders within the same group to ensure they are served by the same vehicle, but this approach also failed to work.

I am struggling to implement this requirement correctly. Obviously the problem does have a solution and just to be sure I'm working without any other constraint but this. Does anyone have any suggestions on how to model this type of constraint in OR-Tools?

Thanks in advance for your help!

• constraints
• or-tools
• vehicle-routing

Share Improve this question Follow edited Nov 19, 2024 at 7:13 Mizux 9,39977 gold badges4040 silver badges5959 bronze badges asked Nov 18, 2024 at 17:54 Donato MallozziDonato Mallozzi 9411 silver badge77 bronze badges

Add a comment  | 

2 Answers 2

Sorted by: Reset to default 0

At the start of the solve all nodes are unassigned thus the VehicleVar is equal to -1 (a semaphore value used when unvisited) .

Since solver will try to add node one by one to built its first solution, you constraint must be "all VehicleVar of my group must be -1 or use the same vehicle index value".

note: You could try to also use the ActiveVar(index) which is a boolean set to false if node is not visited aka ActiveVar(index) * VehicleVar(index) is 0 if unvisited or vehicle_index otherwise...

instead of adding a hard constraint you may first want to try a penalty of

cost += 10000* self.routing.solver().Max(used_vehicles)==self.routing.solver().Min(used_vehicles)

to see if the solver can find a feasible solution, or is there a bug in your program. It sometimes helps to relax the problem to help solver find initial feasible solution which might be difficult to reach in a more constrained original problem.

本文标签：