Or-tools: CP Solver Fail

[Ayoubsaab7]

Hello. I am attempting to solve the CVRPTW. I have modified the distance function, to take real distances from the googlemaps API. The same was done for the time_evaluator: the time is no longer the distance divided by the speed...

Here is the distance_matrix (in km):
{0: {0: 0, 1: 13.6, 2: 13.8, 3: 15.9, 4: 13.1, 5: 13.5, 6: 14.4, 7: 13.1, 8: 13.1}, 1: {0: 16.2, 1: 0, 2: 1.6, 3: 1.2, 4: 2.2, 5: 1.3, 6: 0.9, 7: 2.0, 8: 2.2}, 2: {0: 13.9, 1: 1.9, 2: 0, 3: 1.0, 4: 0.6, 5: 1.0, 6: 2.2, 7: 1.3, 8: 0.6}, 3: {0: 16.7, 1: 0.8, 2: 0.4, 3: 0, 4: 1.0, 5: 0.1, 6: 1.4, 7: 1.7, 8: 1.0}, 4: {0: 13.7, 1: 2.7, 2: 2.9, 3: 2.4, 4: 0, 5: 2.6, 6: 3.0, 7: 1.0, 8: 0.004}, 5: {0: 16.4, 1: 1.4, 2: 1.7, 3: 1.3, 4: 2.3, 5: 0, 6: 1.1, 7: 3.0, 8: 2.3}, 6: {0: 15.7, 1: 0.6, 2: 1.8, 3: 1.4, 4: 2.4, 5: 1.5, 6: 0, 7: 2.4, 8: 2.4}, 7: {0: 12.7, 1: 1.7, 2: 1.9, 3: 1.6, 4: 1.2, 5: 1.6, 6: 2.0, 7: 0, 8: 1.2}, 8: {0: 13.7, 1: 2.7, 2: 2.9, 3: 2.4, 4: 2.0, 5: 2.6, 6: 3.0, 7: 1.0, 8: 0}}

travel_time_matrix:
{0: {0: 0, 1: 16, 2: 16, 3: 16, 4: 15, 5: 16, 6: 13, 7: 13, 8: 15}, 1: {0: 17, 1: 0, 2: 5, 3: 4, 4: 8, 5: 5, 6: 4, 7: 8, 8: 8}, 2: {0: 17, 1: 5, 2: 0, 3: 5, 4: 3, 5: 5, 6: 6, 7: 4, 8: 3}, 3: {0: 17, 1: 3, 2: 1, 3: 0, 4: 4, 5: 1, 6: 3, 7: 5, 8: 4}, 4: {0: 16, 1: 8, 2: 8, 3: 8, 4: 0, 5: 8, 6: 8, 7: 3, 8: 1}, 5: {0: 17, 1: 5, 2: 6, 3: 5, 4: 9, 5: 0, 6: 4, 7: 10, 8: 9}, 6: {0: 15, 1: 3, 2: 6, 3: 4, 4: 8, 5: 5, 6: 0, 7: 9, 8: 8}, 7: {0: 13, 1: 5, 2: 5, 3: 6, 4: 4, 5: 5, 6: 5, 7: 0, 8: 4}, 8: {0: 16, 1: 8, 2: 8, 3: 8, 4: 6, 5: 8, 6: 8, 7: 3, 8: 0}}

time_windows:
[(0, 0), (840, 1199), (840, 1199), (930, 990), (840, 1199), (1170, 1200), (1200, 1439), (840, 1199), (840, 1199)]

I am getting the following error:

Traceback (most recent call last):
  File "cvrptw_mod.py", line 199, in <module>
    main()
  File "cvrptw_mod.py", line 133, in main
    cvrptw_helper.add_time_window_constraints(routing, data, time_evaluator)
  File "C:\Users\path\cvrptw_helper.py", line 229, in add_time_window_constraints
    time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
  File "C:\Users\admin\AppData\Roaming\Python\Python37\site-packages\ortools\constraint_solver\pywrapcp.py", line 1342, in SetRange
    return _pywrapcp.IntExpr_SetRange(self, l, u)
Exception: CP Solver fail

I have tried increasing the number of vehicles and their capacity, but this did not resolve the issue.
Can you please advise? Thanks!

[lperron]

Are the distance integers?

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le ven. 19 oct. 2018 à 16:03, Ayoubsaab7 [e-mail] a
écrit :

Hello. I am attempting to solve the CVRPTW. I have modified the distance
function, to take real distances from the googlemaps API. The same was done
for the time_evaluator: the time is no longer the distance divided by the
speed...

Here is the distance_matrix (in km):
{0: {0: 0, 1: 13.6, 2: 13.8, 3: 15.9, 4: 13.1, 5: 13.5, 6: 14.4, 7: 13.1,
8: 13.1}, 1: {0: 16.2, 1: 0, 2: 1.6, 3: 1.2, 4: 2.2, 5: 1.3, 6: 0.9, 7:
2.0, 8: 2.2}, 2: {0: 13.9, 1: 1.9, 2: 0, 3: 1.0, 4: 0.6, 5: 1.0, 6: 2.2, 7:
1.3, 8: 0.6}, 3: {0: 16.7, 1: 0.8, 2: 0.4, 3: 0, 4: 1.0, 5: 0.1, 6: 1.4, 7:
1.7, 8: 1.0}, 4: {0: 13.7, 1: 2.7, 2: 2.9, 3: 2.4, 4: 0, 5: 2.6, 6: 3.0, 7:
1.0, 8: 0.004}, 5: {0: 16.4, 1: 1.4, 2: 1.7, 3: 1.3, 4: 2.3, 5: 0, 6: 1.1,
7: 3.0, 8: 2.3}, 6: {0: 15.7, 1: 0.6, 2: 1.8, 3: 1.4, 4: 2.4, 5: 1.5, 6: 0,
7: 2.4, 8: 2.4}, 7: {0: 12.7, 1: 1.7, 2: 1.9, 3: 1.6, 4: 1.2, 5: 1.6, 6:
2.0, 7: 0, 8: 1.2}, 8: {0: 13.7, 1: 2.7, 2: 2.9, 3: 2.4, 4: 2.0, 5: 2.6, 6:
3.0, 7: 1.0, 8: 0}}

travel_time_matrix:
{0: {0: 0, 1: 16, 2: 16, 3: 16, 4: 15, 5: 16, 6: 13, 7: 13, 8: 15}, 1: {0:
17, 1: 0, 2: 5, 3: 4, 4: 8, 5: 5, 6: 4, 7: 8, 8: 8}, 2: {0: 17, 1: 5, 2: 0,
3: 5, 4: 3, 5: 5, 6: 6, 7: 4, 8: 3}, 3: {0: 17, 1: 3, 2: 1, 3: 0, 4: 4, 5:
1, 6: 3, 7: 5, 8: 4}, 4: {0: 16, 1: 8, 2: 8, 3: 8, 4: 0, 5: 8, 6: 8, 7: 3,
8: 1}, 5: {0: 17, 1: 5, 2: 6, 3: 5, 4: 9, 5: 0, 6: 4, 7: 10, 8: 9}, 6: {0:
15, 1: 3, 2: 6, 3: 4, 4: 8, 5: 5, 6: 0, 7: 9, 8: 8}, 7: {0: 13, 1: 5, 2: 5,
3: 6, 4: 4, 5: 5, 6: 5, 7: 0, 8: 4}, 8: {0: 16, 1: 8, 2: 8, 3: 8, 4: 6, 5:
8, 6: 8, 7: 3, 8: 0}}

time_windows:
[(0, 0), (840, 1199), (840, 1199), (930, 990), (840, 1199), (1170, 1200),
(1200, 1439), (840, 1199), (840, 1199)]

I am getting the following error:
Traceback (most recent call last):
File "cvrptw_mod.py", line 199, in
main()
File "cvrptw_mod.py", line 133, in main
cvrptw_helper.add_time_window_constraints(routing, data, time_evaluator)
File "C:Userspathcvrptw_helper.py", line 229, in
add_time_window_constraints
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
File
"C:UsersadminAppDataRoamingPythonPython37site-packagesortoolsconstraint_solverpywrapcp.py",
line 1342, in SetRange
return _pywrapcp.IntExpr_SetRange(self, l, u)
Exception: CP Solver fail

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/894, or mute the thread
https://github.com/notifications/unsubscribe-auth/AKj17Ypb6DdigDAdr8pihEnA8iAZ8L3pks5umdu7gaJpZM4XwbDv
.

[Ayoubsaab7]

The distances are in kilometers, so they are floating point numbers. But note that when I change the time_windows to:
[(0, 0), # depot
(0, 30), (0, 30), # 1, 2
(0, 30), (0, 30), # 3, 4
(30, 60), (30, 60), # 5, 6
(30, 60), (30, 60)]# 7, 8
the algorithm works.

[lperron]

The solver expects integers, so it will silently convert everything to
integers.
Make sure you know what is passed and do the conversion yourself.

You can scale everything up (in meters for instance) if you think this is
important.

Thanks
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le ven. 19 oct. 2018 à 16:29, Ayoubsaab7 [e-mail] a
écrit :

The distances are in kilometers, so they are floating point numbers. But
note that when I change the time_windows to:
[(0, 0), # depot
(0, 30), (0, 30), # 1, 2
(0, 30), (0, 30), # 3, 4
(30, 60), (30, 60), # 5, 6
(30, 60), (30, 60)]# 7, 8
the algorithm works.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/894#issuecomment-431382200,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKj17Wpw6dWWGB-KltJwhfXDP9JcLRjbks5umeHSgaJpZM4XwbDv
.

[Ayoubsaab7]

I changed the _distances[from_node][to_node] to an integer (in meters) and it still failed.

How come it works smoothly whenever I change the time windows? It seems that the issue is arising from there, because when I selected time_windows as:
[(0, 0), # depot
(0, 30), (0, 30), # 1, 2
(0, 30), (0, 30), # 3, 4
(30, 60), (30, 60), # 5, 6
(30, 60), (30, 60)]# 7, 8

instead of:
[(0, 0), (840, 1199), (840, 1199), (930, 990), (840, 1199), (1170, 1200), (1200, 1439), (840, 1199), (840, 1199)]

the algorithm converges.

[braktar]

Did you provide a maximum slack value with your time dimension?
https://github.com/google/or-tools/blob/master/ortools/constraint_solver/routing.cc#L710
slack_max here

Or an exclusion cost in order to drop some nodes out of the solution if unfeasible?
https://github.com/google/or-tools/blob/master/ortools/constraint_solver/routing.cc#L1319

A cost applied to time nor distance, would also help, if not already provided
https://github.com/google/or-tools/blob/master/ortools/constraint_solver/routing.cc#L5101

[Mizux]

Seems you didn't allow for waiting time aka use of positive slack var...

[Ayoubsaab7]

Before, the maximum slack was equal to horizon = 120.

Since I'm dealing with times from 12:00AM (which maps to 0 minutes) until 11:30PM (which maps to 1410 minutes), I've set the horizon to be equal to 1410. The algorithm converges! Is my approach correct or am I misunderstanding the meaning of horizon?

[rohitkumar93]

Before, the maximum slack was equal to horizon = 120.

Since I'm dealing with times from 12:00AM (which maps to 0 minutes) until 11:30PM (which maps to 1410 minutes), I've set the horizon to be equal to 1410. The algorithm converges! Is my approach correct or am I misunderstanding the meaning of horizon?

Did you manage to solve the issue ?
I have a similar problem..

[lperron]

Most likely a modeling issue with too tight time windows, constraints.

Try relaxing then one by one, until you find the problem.