Solver doesn't respect time windows

[Ben]

Hello, I have a vrp problem where each node correspond to a category (A, B or C), I duplicated the node from the category C. The thing is that I don't want 2 duplicated node to be include in the same route so what I did is that I added time windows. Let's say that I have 40 vehicle with 15 capacity (each visited node has a capacity of 1 it is just to limit the number of visited node per vehicle to 15), I divided all my vehicle to 2 start and end location. So I have start node 0 and end node 1 with 20 vehicles and start node 2 and end node 3 with 20 vehicles. I tried to set up time windows for my start and end location this way :

- start node 0 : [28800,28800] (corresponds to 8 am in seconds and it is the same start and end range to from the 20 vehicle to leave asap)

- end node 1 : [80000,80000]

- start node 2 : [115200, 115200]

- end node 3 : [166400,166400]

Those start and end node are dummy location so they have a 0 seconds distance to all the other nodes. Here is how my time_window matrix is setup :

[[28800, 28800],

[80000, 80000],

[115200, 115200],

[166400, 166400],

[[0, 86400], []],

[[], [0, 86400]],

[[0, 86400], []],

[[0, 86400], [0, 86400]]

For the visited nodes if the nodes is not a duplicated node is will be available from [28800,80000] and [115200,166400]. If it is a duplicated node one will be available during the first part [28800,80000] and the duplicated one from [115200,166400].

Unfortunately in the end I have duplicated node in the same route while it should be impossible cause vehicle either start from the first start and end node which means they should be back at 80000 or form the second meaning they can only start at 115200.

Could you help me solve this please ? 

Here are some code to see how I set up all of these :

# Add time window constraints for all start and end locations.

for i in range(0, n_freq*2):

if i in start_indices:

index = routing.Start(int(i/2))

elif i in end_indices:

index = routing.End(int((i-1)/2))

time_dimension.CumulVar(index).SetRange(

windows[i][0], windows[i][1])

# Time window constraints for visits

for location_index, time_window in enumerate(windows):

# Only add time window constraints for all visit locations (i.e. no start and end locations and no events)

if location_index in range(n_freq * 2, len(data["time_matrix"])):

index = manager.NodeToIndex(location_index)

# Time window constraints for visits can be much more complex

# (possibly multiple time-windows on possibly multiple days)

# Hence defining the available time range is more complex for visits.

# Add the range between the start of the first day and the end of the last day

time_dimension.CumulVar(index).SetRange(0, day_length_in_seconds * n_freq)

for Day in range(n_freq):

Day_Start = Day * day_length_in_seconds

Day_End = Day_Start + day_length_in_seconds

# Day*2 is the index of the start location of the given day

# if data is organized in the following way:

# Start, End, Start, End, ..., Visit, Visit, Visit, ...

Working_Start = windows[Day * 2][0]

# Day*2+1 is the index of the end location of the given day

# if data is organized in the above way

Working_End = windows[Day * 2 + 1][1]

if int(len(time_window[Day])/2) == 0:

time_dimension.CumulVar(index).RemoveInterval(Day_Start, Day_End)

else:

time_dimension.CumulVar(index).RemoveInterval(Day_Start, Working_Start)

# Remove the range between the end of work and the end of the day

time_dimension.CumulVar(index).RemoveInterval(Working_End, Day_End)

[sascha...@gmail.com]

"The thing is that I don't want 2 duplicated node to be include in the same route"

There is native support for that in the solver and i highly recommend making use of it: AddHardTypeIncompatibility

See: https://developers.google.com/optimization/reference/python/constraint_solver/pywrapcp#addhardtypeincompatibility

Imho: if you can do something without hacking on time-windows, do it! 

Aggressively exploiting time-window functionality is a dangerous endeavour (when tightening them; even worse: making them discontinuous). Among other reasons: even finding ANY solution to some TSP/VRP becomes NP-hard when there are time-windows. Reasoning about time-windows just makes everything more difficult.

Greetings,

Sascha

[Ben]

Hello,

Thank you very much for your answer, do you have any example on how to use this function. In my case each node represents a location with an ID in the pre-processing I duplicate the node that needs to be duplicated and add a suffix "_dup" in the end of the duplicated node id to recognize him from the original one. How could I use this function so all the time "id_dup" nodes can't be in the same route of the "id" nodes ?

[sascha...@gmail.com]

Conceptionally:

- think of an undirected graph where nodes are "colors" or "classes"

- add conflict-edges to this graph whenever two "colors" or "classes" are incompatible

- the term conflict-graph is well-known in combinatorial-opt

In your case, *it might make sense* (reason yourself!) to introduce color 0 as a default and for each node, which has dupes, introduce n_dupes + 1 new colors and add all edges of the this clique (fully connected subgraph)

Example: A, B, B', C, C', C'' (A has no dupe, B has a single dupe, C has two dupes)

Colors = 0, 1, 2, 3, 4, 5

Edges: (1, 2) = clique for B + (3,4), (4, 5),(3,5) clique for C

I recommend visualizing it on paper.

(The 0 was introduced as a default/dummy and there is no need to add a color for non-duped nodes; another D or E without dupes can reuse color 0 as it's not part of any edge we don't need it)

Implementation-wise:

- A: use SetVisitType to color nodes

- B: use CloseVisitTypes (search github issue-tracker or maybe this mailing-list about it)

- C: use AddHardTypeIncompatibility to add (conflict-)edges

I have no Python-code, but i did code something like this (C++) in the past, but keep in mind, that:

- this code is in some sense rather generic, as i compress / fuse multiple independent conflict-graphs defined at runtime (on some potentially very large graph) -> you can explicitly "compress"

- this code is in some sense reflecting some special use-case and therefore var-names and such can look strange

- this code calls into functions not shown (FindMaximalStrongStructuralEquivalence)

1     // "Compress" multiple independent conflict-graphs
2   FindMaximalStrongStructuralEquivalence mse(g);
3     mse.calculate();
4
5     absl::flat_hash_map<unsigned int, unsigned int> node_to_partition_class;
6     unsigned int pc = 0;
7     for(const auto& partition_class : mse.partition) {
8       for(auto node : partition_class) {
9         node_to_partition_class.insert( {node, pc} );
10       }
11       pc++;
12     }
13     VLOG(1) << absl::StrFormat("-> #partitions / visit-types: %d", mse.partition.size());
14
15     boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS> g_contracted(mse.partition.size());
16     {
17       auto es = boost::edges(g);
18       for(auto eit = es.first; eit != es.second; ++eit) {
19         auto v_source = boost::source(*eit, g);
20         auto v_target = boost::target(*eit, g);
21         boost::add_edge(node_to_partition_class.at(v_source), node_to_partition_class.at(v_target), g_contracted);
22       }
23     }
24    
25     // or-tools -> set visit-types of nodes (without depot)
26     for(unsigned int i=0; i<routing_model.routing_nodes.size(); ++i) { 
27       uint64_t node_shifted_zobrist_hash = node_to_hash[i + production_model.production_nodes.size()];  // shifted
28       unsigned int node_shifted_compressed_repr = ordered_unique_hashes_inverse.at(node_shifted_zobrist_hash);
29       VLOG(5) << absl::StrFormat("prep visit-type %d", i + 1);
30       model->SetVisitType(
31         i + 1,
32         node_to_partition_class.at(node_shifted_compressed_repr),
33         operations_research::RoutingModel::VisitTypePolicy::TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED);
34       VLOG(5) << absl::StrFormat("node %d visit-type %d", i + 1, node_to_partition_class.at(node_shifted_compressed_repr));
35     }
36     model->SetVisitType(0, -1, operations_research::RoutingModel::VisitTypePolicy::TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED);  // play it safe with -1
37     VLOG(5) << absl::StrFormat("node %d visit-type %d", 0, -1);
38
39     // or-tools -> add conflicts over visit-types
40     model->CloseVisitTypes();
41    
42     {
43       VLOG(1) << absl::StrFormat("-> #conflict-arcs over visit-types: %d", boost::num_edges(g_contracted));
44       auto es = boost::edges(g_contracted);
45       for(auto eit = es.first; eit != es.second; ++eit++) {
46         auto v_source = boost::source(*eit, g_contracted);
47         auto v_target = boost::target(*eit, g_contracted);
48         model->AddHardTypeIncompatibility(v_source, v_target);
49         VLOG(5) << absl::StrFormat("visit-type conflict: %d <-> %d", v_source, v_target);
50       }
51     }
52   }
53

The most relevant things for you:

- line 30/36 | A

- line 40       | B

- line 48       | C

operations_research::RoutingModel::VisitTypePolicy::TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED looks it a bit arbitrary, but you can copy it (i think i copy-pasted it from an internal test-case in the or-tools sources). There is some docstring, but i never really "got it" from a conceptional view.

The (3?) API-functions you need seem to exist in the Python-wrapper too.

Greetings,

Sascha

[Wael Ben Baccar]

Thank you,

I have tried this code to do that :

node_types = {}

type_counter = 1 # Start type counter

for location in locations:

crm_id = location['crm_id']

base_id = crm_id.replace('_dup', '') # Remove '_dup' to find the base ID

if base_id not in node_types and ('Very High Value' in location['category'] or 'High Value' in location['category']):

# Assign a unique type for both original and duplicated node

node_types[base_id] = type_counter

node_types[base_id + '_dup'] = type_counter # Assuming duplication for all high-value nodes

type_counter += 1

type_policy = pywrapcp.RoutingModel.TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED

# Step 2: Set visit types based on node iteration

for node in range(1, len(data["distance_matrix"])): # Starting from 1 assuming 0 is the depot

crm_id = locations[node-1]['crm_id'] # Adjusted to directly access 'crm_id' from 'locations'

if crm_id in node_types:

node_index = manager.NodeToIndex(node) # Directly use node as index

routing.SetVisitType(node_index, node_types[crm_id],type_policy)

# Step 3: Add hard incompatibility

for original_id, node_type in node_types.items():

if '_dup' not in original_id: # Working with original node pairs

duplicate_id = original_id + '_dup'

if duplicate_id in node_types: # Check if the duplicate exists

routing.AddHardTypeIncompatibility(node_type, node_types[duplicate_id])

# Step 4: Finalize visit types configuration

routing.CloseVisitTypes()

but whenever I add the type policy my kernel crashes, did I implemented this correctly ?