problem with objective solution

[niksaved pavlov]

Hey,

I have been working for a couple of months with google or tools in order to optimize a route for service engineers with prioritisation: I do this by giving larger penalties to nodes that are more important, just as suggested in the examples on the website. Works like a charm when my model remains at that.

But when I switch to an optimisation for the whole week (whereby I use dummy depot nodes with time windows, which fall in line with the end of day for the whole week), the objective solution does not seem to take into account the penalties from routing.addDisjunction anymore (please see the main definition in the code for which I use the optimisation). By playing around with the penalties (eg. giving a node that wasnt visited yet a very large penalty), I saw that penalties were not accounted for anymore, when I put in the time window constraints.

I hope somebody can advice me on how to make the solver still account for the penalties (such that penalties of the not-visited nodes are minimized), while using the time window constraints for the dummy depots. 

With regards,

Nikita

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

Hi Nikita,

First, your program is not executable as is, so I have to guess a bit
about what is wrong. Hopefully I have good guesses.

So I looked at the code and the first thing that I noticed is that
your time dimension is only one day long:

```python
routing.AddDimension(transit_callback_index,
30,
data['maxTimePerDay'],
True,
'timeCapacityPerday')
time_dimension = routing.GetDimensionOrDie('timeCapacityPerday')
```

So assuming that `data['maxTimePerDay']` is something like 480 (8
hours times 60 minutes), that means that your vehicles can only
"accumulate" up to one day of activity. So your depots have to be
"unloading" time in some way.

That is usually pretty tricky to get right.

If I was doing it I would have time continue over all the days. So
the max would be 3360, or 480 * 7, or (8hr per day * 7 days * 60
minutes per hour)


```python
routing.AddDimension(transit_callback_index,
30,
data['maxTimeForPeriod'],
True,
'timeCapacity')
time_dimension = routing.GetDimensionOrDie('timeCapacity')
```

Because you don't show your data, I can't guess at what the depot time
windows are in this code block:

```python
#set time windows for the dummy depots, such that the FSE
#'returns' back home by the end of each day.
for location_idx, time_window in enumerate(data['time_windowsDepot']):
if location_idx == data['depot']:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
```

But I'm guessing that this is wrong, or rather, confused.

Again, dimensions are simply accumulators. In your case, the
accumulator for time includes the travel time from A to B (distance
callback) and the service time (service time callback). But I see
nothing in there that would subtract anything from the accumulator.
So when the dimension accumulates to `data['maxTimePerDay']`, the
vehicle has accumulated all it can, and the solver will end its run.

Hope that helps.

Reply with your data, and/or actually running code, in order for me to
help more.

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/d56001ae-8614-4687-b0d2-335aec6da01en%40googlegroups.com.

> # -*- coding: utf-8 -*-
> """
> Created on Thu Apr 1 15:11:38 2021
>
> @author: NLAEXTNPA
> """
>
> def main(input_timeMatrix,input_normalDuration,input_penaltyScore):
> """Entry point of the program."""
> # Instantiate the data problem.
> data = create_data_model(input_timeMatrix,input_normalDuration,input_penaltyScore)
>
> # Create the routing index manager.
> manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
> data['num_vehicles'], data['depot'])
>
> # Create Routing Model.
> routing = pywrapcp.RoutingModel(manager)
>
> def serviceTime_callback(to_index):
> to_node = manager.IndexToNode(to_index)
> return data['Service_time'][to_node]
>
> def distance_callback(from_index, to_index):
> """Returns the distance between the two nodes."""
> # Convert from routing variable Index to distance matrix NodeIndex.
> from_node = manager.IndexToNode(from_index)
> to_node = manager.IndexToNode(to_index)
> return data['time_matrix'][from_node][to_node] + serviceTime_callback(to_index)
>
> transit_callback_index = routing.RegisterTransitCallback(distance_callback)
>
> # Define cost of each arc.
> routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
>
> routing.AddDimension(transit_callback_index,30,data['maxTimePerDay'],True,'timeCapacityPerday')
> time_dimension = routing.GetDimensionOrDie('timeCapacityPerday')
>
>
> #set time windows for the dummy depots, such that the FSE 'returns' back home by the end of each day.
> for location_idx, time_window in enumerate(data['time_windowsDepot']):
> if location_idx == data['depot']:
> continue
> index = manager.NodeToIndex(location_idx)
> time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
>
> #set the departure time on monday morning for the vehicle.
> depot_idx = data['depot']
> index = routing.Start(0)
> time_dimension.CumulVar(index).SetRange(
> data['time_windowsDepot'][depot_idx][0],
> data['time_windowsDepot'][depot_idx][1])
> routing.AddVariableMinimizedByFinalizer(
> time_dimension.CumulVar(routing.Start(0)))
> routing.AddVariableMinimizedByFinalizer(
> time_dimension.CumulVar(routing.End(0)))
>
>
> solver = routing.solver()
> lunchBreak = solver.FixedDurationIntervalVar(240,360,30,True,'Lunch')
> routing.GetDimensionOrDie('timeCapacityPerday').SetBreakIntervalsOfVehicle([lunchBreak],0)
>
> for node in range(1, len(data['time_matrix'])):
> routing.AddDisjunction([manager.NodeToIndex(node)], data['penalty_score'][node])
>
> # Setting first solution heuristic.
> 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.seconds = 60
>
> # Solve the problem.
> solution = routing.SolveWithParameters(search_parameters)
>
> # Print solution on console.
> if solution:
> visitedCustomers = print_solution(manager, routing, solution)
> return visitedCustomers
> else:
> print('No solution found')
> return []

--

James E. Marca
Activimetrics LLC

[niksaved pavlov]

Dear James,

Thank you very much for taking your time to look into my problem. I was indeed not very clear in my previous description, I will try harder to explain my problem better haha.

Commenting on your initial comments: data['maxTimePerDay'] indeed should be the total time for the whole week, that was my bad. As you will see in the python code below, this has already been implemented. In my case, I have to optimise for the 5 workdays of the week, with a working day of 8.5 hours. So data['maxTimePerDay'] is indeed = (8.5 * 5 * 60).. 

My provided code was indeed insufficient, hereby I provide my full code to run the optimisation. I also provide an example input inside the python code. The 3 keys stored in the dictionary are 1) 'travelTime_matrix' : is the matrix that contains the time in minutes to travel between two locations 2) 'service_time' : vector that contains the service time in minutes needed at each location. Obviously, for the depot and the dummy depots, the service time is 0. 3) 'penaltyScore' : vector that contains the penaltyscore for each location, if it is not included in the route, which is implemented through routing.addDisjunction. Note that for the depot, penalty is 0, and for the dummy depots it is very high penalty score, such that these dummy depots are for sure visited, as the service engineers need to return back home at the end of day.

Together with the python code, I provide the list of customers that should be considered for this specific optimisation, with confidential data filtered out. The last column 'UsedOrNot' is adjusted after the optimisation, whether or not this customer has been visited or not.

If you run the code, it should give an output as follows:

 

As you can see, it creates a nice route, where it indeed accounts for the service engineer to return back home at the end of the day (see the dummy depot indexes 1, 2, 3 and 4 in the route for vehicle 1). As you can also see, the objective value at the top of the screenshot is 2375 minutes, which is the total time in minutes it takes to complete the route (basically the sum of the printed travel times and service times, as you can see on the screenshot). But as can be seen inside the excel (see screenshot below), the model only takes the top 15 customers, and ignored the bottom 4 customers even though these customers have higher penalty scores (as these are considered more important customers).

The point of me using the routing.addDisjunction() is to include the most important customers in the route, and leave out the less important customers for the week thereafter, basically following the example as in: https://developers.google.com/optimization/routing/penalties . So what I would expect to happen with my objective value, is that besides the 2375 minutes in the objective value, the sum of the penalty scores of the locations that are not included in the route is added to the objective value. This would mean that I want the objective solution to minimize that sum, therefore trying to leave out customers that are less important in the optimisation, as that would decrease the objective value. As you can see, this does not seem to work anymore, because I added the code for the dummy depot time windows.

I hope this clears up a bit what I mean with my objective solution not being desirable with my expectations. I would be very grateful if you, or anybody on the google OR tools team, have a solution to this problem. Thanks in advance!

With regards,

Nikita

[Mizux Seiha]

Just try to run you main_ortools.py on linux (note: I added a dropped node list in the print function, convert it from dostounix, added a shebang and make it executable)
* I obtain a drop in objective from 6265 at around 10-12s (nuc10i7) to 2378 (so I set time limit to 15s ^^)

* there is no dropped node -> Are you sure of your post processing stuff ?

# Observed
./main_ortools.py

....

I0110 04:27:00.279296  5439 search.cc:264] Solution #5491 (2397, objective minimum = 2378, objective maximum = 14528, time = 14970 ms, branches = 33329, failures = 21285, depth = 33, TwoOpt, neighbors = 2526700, filtered neighbors = 11444, accepted neighbors = 5491, memory used = 14.23 MB, limit = 99%)

I0110 04:27:00.759521  5439 search.cc:264] Solution #5492 (2393, objective minimum = 2378, objective maximum = 14528, time = 14970 ms, branches = 33334, failures = 21287, depth = 33, TwoOpt, neighbors = 2526701, filtered neighbors = 11445, accepted neighbors = 5492, memory used = 14.23 MB, limit = 99%)

I0110 04:27:02.408691  5439 search.cc:264] Solution #5493 (2393, objective minimum = 2378, objective maximum = 14528, time = 14972 ms, branches = 33338, failures = 21289, depth = 33, TwoOpt, neighbors = 2526877, filtered neighbors = 11446, accepted neighbors = 5493, memory used = 14.23 MB, limit = 99%)

I0110 04:27:10.915527  5439 search.cc:264] Solution #5494 (2393, objective minimum = 2378, objective maximum = 14528, time = 14980 ms, branches = 33349, failures = 21294, depth = 33, TwoOpt, neighbors = 2528205, filtered neighbors = 11447, accepted neighbors = 5494, memory used = 14.23 MB, limit = 99%)

I0110 04:27:11.411376  5439 search.cc:264] Solution #5495 (2393, objective minimum = 2378, objective maximum = 14528, time = 14981 ms, branches = 33354, failures = 21296, depth = 33, TwoOpt, neighbors = 2528206, filtered neighbors = 11448, accepted neighbors = 5495, memory used = 14.23 MB, limit = 99%)

I0110 04:27:20.268310  5439 search.cc:264] Solution #5496 (2393, objective minimum = 2378, objective maximum = 14528, time = 14989 ms, branches = 33363, failures = 21301, depth = 33, TwoOpt, neighbors = 2529534, filtered neighbors = 11449, accepted neighbors = 5496, memory used = 14.23 MB, limit = 99%)

I0110 04:27:20.746826  5439 search.cc:264] Solution #5497 (2393, objective minimum = 2378, objective maximum = 14528, time = 14990 ms, branches = 33367, failures = 21303, depth = 33, TwoOpt, neighbors = 2529535, filtered neighbors = 11450, accepted neighbors = 5497, memory used = 14.23 MB, limit = 99%)

I0110 04:27:22.347412  5439 search.cc:264] Solution #5498 (2401, objective minimum = 2378, objective maximum = 14528, time = 14992 ms, branches = 33372, failures = 21305, depth = 33, TwoOpt, neighbors = 2529675, filtered neighbors = 11451, accepted neighbors = 5498, memory used = 14.23 MB, limit = 99%)

I0110 04:27:28.333251  5439 search.cc:264] Finished search tree (time = 14998 ms, branches = 33375, failures = 21334, neighbors = 2530626, filtered neighbors = 11451, accepted neigbors = 5498, memory used = 14.23 MB)

I0110 04:27:28.381347  5439 search.cc:264] End search (time = 14998 ms, branches = 33375, failures = 21334, memory used = 14.23 MB, speed = 2225 branches/s)

Objective: 2378 minutes+penalty

Dropped nodes:

Travel time + service time at destination:

Monday:

120

30

142

191

16

total time today (in hours): 8.32

Tuesday:

31

30

188

210

10

total time today (in hours): 7.82

Wednesday:

221

210

24

total time today (in hours): 7.58

Thursday:

251

180

15

total time today (in hours): 7.43

Friday:

41

180

157

131

0

Route for vehicle 0:

 0 -> 20 -> 19 -> 10 -> 9 -> 1 -> 16 -> 15 -> 8 -> 7 -> 2 -> 12 -> 11 -> 3 -> 17 -> 14 -> 4 -> 6 -> 5 -> 13 -> 18 -> 0

note: I've used

python -m pip show ortools

Name: ortools

Version: 8.2.8918 // master branch so little ahead of the last release

[Mizux Seiha]

My modified version, that I forget to attach (shame on me)

[niksaved pavlov]

Dear Mizux,

I indeed see what you mean.

As you mentioned, the optimisation is not dropping nodes, because my time matrix is of lower dimension than my service time and penalty score vectors, i forgot to incorporate the dummy depots into my time matrix... my bad haha. As you can see, the dimensions of the time matrix are 21x21, whereas servicetime and penaltyscore vectors 25x1. 

Thank you for looking at it anyways, google OR tools is a gem!

With regards,

Nikita