VRP - Large variation in feasibility requirements after tiny change to cost matrix

[Oliver Grund]

Hello,

I am using ortools (9.10.4067) to optimize ordering on textile machines, which is a VRP problem with additional constraints. Attached to this message is ortools_data.zip  which contains the script and all the necessary files.

The constraints are as follows:
1. There are 3 machines (from now referred to as vehicles) to produce from a pool of orders (locations)
2. Locations are divided into 2 types: either ALL vehicles may visited them or only vehicle 2,3

3. Time starts at 0, each location takes 1 unit of time to visit. Locations have with them, associated time windows, where the time windows is from t=0 till t=days_remaining*n_day, where days_remaining is the no. of days till the order's deadline and n_day the number of orders that can be manufactured in a single day respectively.

4. Open ends

I have encountered strange behaviour by the library, after changing something about the last location, which results in a different cost_matrix for only a single row,column. ortools will not produce a solution unless I significantly increase the n_day from 14 to 19 (+30% time window size), in short it requires CONSIDERABLY larger time windows, note the location is only one of over 350 so its very disproportional.
What I'm asking then:
- Isn't this clearly wrong? Considering how little about the input parameters has changed, the expected behaviour would be either a +1 increase in n_day maximum, or no change to it would be required at all.
I might be misunderstanding something about how dimensions should be set up in OR tools or how to correctly restrict locations for vehicles, feel free to point out any mistakes in the code.

Thanks for any advice or help,

Oliver G.

[Oliver Grund]

I'd also like to add that changes in the cost matrix shouldn't even affect feasibility along the time axis which isn't dependent on distance but I might be misunderstanding something

Dne pondělí 8. července 2024 v 1:29:01 UTC uživatel Oliver Grund napsal:

[blind.lin...@gmail.com]

Oliver,

I took a look at your code and the problem seems to be that you do not
allow nodes to be dropped.

I know this sounds counter-intuitive, because you do not want jobs
to be dropped. However, the key insight is that the initial heuristic
must be able to generate a feasible solution. These heuristics are
not as good as the full search, and so sometimes they just can't
figure out a full feasible solution unless they are allowed to drop
nodes.

The trick is to assign a very large penalty for dropping nodes, and
then you cross your fingers and hope that the search stage will
eventually figure out a solution that does not drop any nodes. If it
can't be done, then you can go ahead and add days to your time
window.

In this case, I added the following function:

# define a very large penalty for dropping nodes such that the solver  
# will try very hard to not drop anything  
disjunction_penalty = 100000  

def add_disjunctions(routing, manager, data):  
    # Allow all locations except the depot to be droppable.  
    for location_idx, time_window in enumerate(data['time_windows']):  
        index = manager.NodeToIndex(location_idx)  
        routing.AddDisjunction([index], disjunction_penalty)  

Then in your main function, I added:

    add_time_window_constraints(routing, manager, data_model)  
    add_distance_constraints(routing, manager, data_model)  
    add_disjunctions(routing, manager, data_model)  

With this change, the solver initially drops some nodes, as you can
see from the output below. Note the solution value is initially
1209262, which means it drops 12 nodes (12 * 100000). I like to make
the penalty large enough so that there is at least one zero between
the regular solution part (9262) and the dropped node penalty part (1200000).

If you scroll down the output, you'll see that at solution #14, the
solver starts adding in the dropped nodes, and then eventually at
solution #25 it is no longer dropping nodes.

I0000 00:00:1720466466.461825      99 search.cc:285] Root node processed (time = 3 ms, constraints = 3234, memory used = 105.73 MB)  
I0000 00:00:1720466466.474874      99 search.cc:285] Solution #0 (1209262, time = 16 ms, branches = 399, failures = 0, depth = 33, memory used = 105.73 MB, limit = 0%)  
I0000 00:00:1720466466.479090      99 search.cc:285] Solution #1 (1209261, maximum = 1209262, time = 20 ms, branches = 414, failures = 2, depth = 33, Relocate<1>, neighbors = 1034, filtered neighbors = 1, accepted neighbors = 1, memory used = 105.73 MB, limit = 0%)  
...  
I0000 00:00:1720466468.479744      99 search.cc:285] Solution #13 (1206458, maximum = 1209262, time = 2021 ms, branches = 604, failures = 26, depth = 33, TwoOpt, neighbors = 484160, filtered neighbors = 13, accepted neighbors = 13, memory used = 106.49 MB, limit = 10%)  
I0000 00:00:1720466469.317476      99 search.cc:285] Solution #14 (1106463, maximum = 1209262, time = 2859 ms, branches = 619, failures = 28, depth = 33, MakeActiveOperator, neighbors = 668680, filtered neighbors = 14, accepted neighbors = 14, memory used = 106.49 MB, limit = 14%)  
I0000 00:00:1720466469.319449      99 search.cc:285] Solution #15 (1006463, maximum = 1209262, time = 2861 ms, branches = 632, failures = 30, depth = 33, MakeActiveOperator, neighbors = 668681, filtered neighbors = 15, accepted neighbors = 15, memory used = 106.49 MB, limit = 14%)  
I0000 00:00:1720466469.321607      99 search.cc:285] Solution #16 (906463, maximum = 1209262, time = 2863 ms, branches = 648, failures = 32, depth = 33, MakeActiveOperator, neighbors = 668682, filtered neighbors = 16, accepted neighbors = 16, memory used = 106.49 MB, limit = 14%)  
I0000 00:00:1720466469.324057      99 search.cc:285] Solution #17 (806463, maximum = 1209262, time = 2865 ms, branches = 659, failures = 34, depth = 33, MakeActiveOperator, neighbors = 668683, filtered neighbors = 17, accepted neighbors = 17, memory used = 106.49 MB, limit = 14%)  
I0000 00:00:1720466469.326143      99 search.cc:285] Solution #18 (706466, maximum = 1209262, time = 2867 ms, branches = 670, failures = 36, depth = 33, MakeActiveOperator, neighbors = 668684, filtered neighbors = 18, accepted neighbors = 18, memory used = 106.49 MB, limit = 14%)  
I0000 00:00:1720466469.327787      99 search.cc:285] Solution #19 (606466, maximum = 1209262, time = 2869 ms, branches = 679, failures = 38, depth = 33, MakeActiveOperator, neighbors = 668685, filtered neighbors = 19, accepted neighbors = 19, memory used = 106.49 MB, limit = 14%)  
I0000 00:00:1720466469.330092      99 search.cc:285] Solution #20 (506466, maximum = 1209262, time = 2871 ms, branches = 689, failures = 40, depth = 33, MakeActiveOperator, neighbors = 668686, filtered neighbors = 20, accepted neighbors = 20, memory used = 107.25 MB, limit = 14%)  
I0000 00:00:1720466469.332030      99 search.cc:285] Solution #21 (406466, maximum = 1209262, time = 2873 ms, branches = 696, failures = 42, depth = 33, MakeActiveOperator, neighbors = 668687, filtered neighbors = 21, accepted neighbors = 21, memory used = 107.25 MB, limit = 14%)  
I0000 00:00:1720466469.334052      99 search.cc:285] Solution #22 (306466, maximum = 1209262, time = 2875 ms, branches = 703, failures = 44, depth = 33, MakeActiveOperator, neighbors = 668688, filtered neighbors = 22, accepted neighbors = 22, memory used = 107.25 MB, limit = 14%)  
I0000 00:00:1720466469.335904      99 search.cc:285] Solution #23 (206874, maximum = 1209262, time = 2877 ms, branches = 708, failures = 46, depth = 33, MakeActiveOperator, neighbors = 668895, filtered neighbors = 23, accepted neighbors = 23, memory used = 107.25 MB, limit = 14%)  
I0000 00:00:1720466469.337469      99 search.cc:285] Solution #24 (106874, maximum = 1209262, time = 2879 ms, branches = 715, failures = 48, depth = 33, MakeActiveOperator, neighbors = 668896, filtered neighbors = 24, accepted neighbors = 24, memory used = 107.25 MB, limit = 14%)  
I0000 00:00:1720466469.339008      99 search.cc:285] Solution #25 (7278, maximum = 1209262, time = 2880 ms, branches = 718, failures = 50, depth = 33, MakeActiveOperator, neighbors = 668897, filtered neighbors = 25, accepted neighbors = 25, memory used = 107.25 MB, limit = 14%)  

Then the final output solution is:

running broken data, n_day is 14  
Objective: 5958  
Route for vehicle 0:  
 0 ->  18 ->  17 ->  16 ->  12 ->  11 ->  10 ->  9 ->  8 ->  7 ->  6 ->  5 ->  4 ->  3 ->  302 ->  305 ->  343 ->  334 ->  317 ->  316 ->  312 ->  304 ->  229 ->  303 ->  294 ->  286 ->  278 ->  277 ->  273 ->  148 ->  147 ->  259 ->  251 ->  240 ->  230 ->  221 ->  195 ->  194 ->  190 ->  183 ->  177 ->  163 ->  162 ->  161 ->  160 ->  146 ->  145 ->  159 ->  158 ->  157 ->  156 ->  155 ->  154 ->  153 ->  152 ->  151 ->  150 ->  149 ->  212 ->  220 ->  326 -> 356  
Distance of the route: 44  

Route for vehicle 1:  
 1 ->  333 ->  332 ->  331 ->  330 ->  329 ->  328 ->  327 ->  100 ->  99 ->  98 ->  97 ->  96 ->  95 ->  113 ->  112 ->  111 ->  110 ->  109 ->  108 ->  107 ->  106 ->  105 ->  104 ->  103 ->  102 ->  101 ->  89 ->  88 ->  83 ->  82 ->  81 ->  80 ->  79 ->  78 ->  77 ->  76 ->  75 ->  74 ->  73 ->  172 ->  173 ->  174 ->  175 ->  176 ->  178 ->  179 ->  180 ->  181 ->  182 ->  164 ->  165 ->  166 ->  167 ->  168 ->  169 ->  170 ->  171 ->  196 ->  197 ->  198 ->  199 ->  200 ->  201 ->  202 ->  203 ->  231 ->  232 ->  233 ->  234 ->  235 ->  236 ->  237 ->  238 ->  239 ->  241 ->  242 ->  243 ->  244 ->  245 ->  246 ->  247 ->  32 ->  31 ->  30 ->  29 ->  28 ->  27 ->  26 ->  25 ->  114 ->  115 ->  116 ->  117 ->  118 ->  119 ->  120 ->  121 ->  24 ->  23 ->  22 ->  21 ->  20 ->  19 ->  344 ->  345 ->  346 ->  347 ->  348 ->  349 ->  350 ->  351 ->  125 ->  124 ->  123 ->  211 ->  210 ->  209 ->  208 ->  207 ->  206 ->  205 ->  204 ->  126 ->  127 ->  128 ->  129 ->  130 ->  131 ->  132 ->  133 ->  134 ->  135 ->  136 ->  137 ->  138 ->  139 ->  140 ->  141 ->  142 ->  143 ->  276 ->  275 ->  274 ->  272 ->  271 ->  270 ->  269 ->  268 ->  267 -> 356  
Distance of the route: 56  

Route for vehicle 2:  
 2 ->  92 ->  91 ->  90 ->  342 ->  341 ->  340 ->  339 ->  338 ->  337 ->  336 ->  335 ->  87 ->  93 ->  94 ->  85 ->  248 ->  249 ->  250 ->  306 ->  307 ->  308 ->  309 ->  310 ->  313 ->  311 ->  314 ->  315 ->  52 ->  53 ->  54 ->  55 ->  33 ->  34 ->  35 ->  36 ->  37 ->  38 ->  39 ->  40 ->  41 ->  42 ->  13 ->  14 ->  122 ->  352 ->  353 ->  354 ->  15 ->  355 ->  84 ->  222 ->  228 ->  227 ->  226 ->  225 ->  224 ->  223 ->  325 ->  324 ->  323 ->  322 ->  321 ->  320 ->  319 ->  318 ->  266 ->  265 ->  264 ->  263 ->  262 ->  261 ->  260 ->  258 ->  257 ->  256 ->  255 ->  254 ->  253 ->  252 ->  63 ->  62 ->  61 ->  60 ->  59 ->  58 ->  57 ->  56 ->  219 ->  218 ->  217 ->  216 ->  215 ->  214 ->  213 ->  86 ->  193 ->  192 ->  191 ->  189 ->  188 ->  187 ->  186 ->  185 ->  184 ->  44 ->  43 ->  51 ->  50 ->  49 ->  48 ->  47 ->  46 ->  45 ->  285 ->  284 ->  283 ->  282 ->  281 ->  280 ->  279 ->  72 ->  71 ->  70 ->  69 ->  68 ->  67 ->  66 ->  65 ->  64 ->  301 ->  300 ->  299 ->  298 ->  297 ->  296 ->  295 ->  293 ->  292 ->  291 ->  290 ->  289 ->  288 ->  287 ->  144 -> 356  
Distance of the route: 58  

Sum of the route distances: 158  

Regards,

James

-- You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/bf891c92-8906-4fcf-a05f-c095071bc6c6n%40googlegroups.com.

--

James E. Marca  
Activimetrics LLC  

[Oliver Grund]

Dear James,

you are right, I'd have never come up with this. I didnt consider dropping the nodes to be a problem because I thought adding -1 to every node's VehicleVar would be sufficient. Either way, thank you very much.

Best,

Oliver G.

Dne pondělí 8. července 2024 v 19:37:35 UTC uživatel blind.lin...@gmail.com napsal: