Adding dimension with individual vehicle performance

[dima kal]

Hi,
I have a VRPTW problem with a constraint of individual vehicle performance,
for example an old driver would probably have a slower driving speed and higher service time
a younger driver would probably have higher driving speed and lower service time

I am using this example:
https://developers.google.com/optimization/routing/routing_tasks
i've changed the units in the above program to meters and seconds

in my code i removed the capacity constraint since it is not relevant to my solution,
what i've tried:
in the main function ive changed costevaluator from SetArcCostEvaluatorOfAllVehicles to SetArcCostEvaluatorOfVehicle and implemented a differenct cost evaluator function with an efficiency variable that reduces the ditances in the distance matrix:

distance_evaluators = []
for veh_id in range(len(couriers_list)):
distance_evaluators.append(
deepcopy(
CreateDistanceEvaluator(data, veh_id).distance_evaluator))
routing.SetArcCostEvaluatorOfVehicle(distance_evaluators[-1], veh_id)

def distance_evaluator(self, from_node, to_node):
self._distances[from_node][to_node] = int(
data.distance_matrix[from_node][to_node]/data.vehicles[veh_id].efficiency)
that seemed to help a bit but still a bad division of labor, and times are not precise at all

the problem is that adding a dimension has only a callback of from node and to node, without a vehicle variable so i cant distinguish between vehicles...

i've read the documentation thoughtfully for the past 2 days and viewed tons of examples but just couldn't find anything for my problem

any help?

[dima kal]

I've managed to figure out a solution using addDimensionWithVehicleCapacity
And defining an individual "timeline capacity" for each vehicle with the capacity array argument and streching the timeline capacity for each vehicle with an efficiency factor
Works like a charm

[dima kal]

after using my solution for a while, i've stumbled upon an issue with that still reverts me to my original question.
because although the time capacity of each vehicle is bigger, the time window for each task is still the same, and not a real representation of the time window for each vehicle's personal ability. because each time window still has the same real time constrain and they are unable to utilize the bigger time capacity that the more efficient vehicles have...
lets say i have a vehicle that his shift is from 16:00 to 21:00 and he is very efficient, so i stretch him to 23:00, and when the routing module done with building the route for this vehicle i shrink back the time (and each task's start time too) to 21:00. but during the route building, he is unable to use the stretched time because lets say i have a task that is from 18:00 to 21:00, the solver can't put it after 21:00 on that vehicle because he doesn't know that he actually finishes at 21:00 but he is a faster vehicle so it has a bigger capacity...
so my solution was not perfect, any other suggestions?

[Paul Trow]

I think you want to use AddDimensionWithVehicleTransits. See

https://groups.google.com/forum/#!searchin/or-tools-discuss/vehicle$20speed%7Csort:date/or-tools-discuss/yyQxgaZo8Zk/i1Cxw4e2DwAJ

Time windows specify when a vehicle can visit a location. They depend on the locations, not the vehicles. A vehicle being faster doesn't change the time intervals.

[dima kal]

Thank you for your reply,
The link you've provided did not work for me
How can i use this module? Does it return vehicle index for the evaluator?

[Paul Trow]

Sorry the link didn't work.

 I believe you need to create separate transit-time callbacks for each vehicle, say TransitTime1, TransitTime2, and so on. Transit_timei takes a pair of nodes, node1 and node2 and returns the transit time from node1 to node2 using vehicle i. For example, this could be

distance(node1, node2) / speed vechicle i.

Then you create an array of callbacks, TransitTimeArray =  [TransitTime1, TransitTime2, ..], and create the time dimension by

routing.AddDimensionWithVehicleTransits(TransitTImeArray, nHorizon, nHorizon, False, "Time")

I haven't tested this yet, however. 

[dima kal]

Seems to work properly
What I've done is to define for each vehicle an individual travel time matrix, and the node from/to that goes to the evaluator references to the individual matrix of each vehicle.

Thanks for the help
Here's the code if anyone would like an idea of how to use this

# Add Time Window constraint
time_evaluators = []
for veh_id in range(len(data.couriers)):
time_evaluators.append(data.vehicles[veh_id].time_evaluator)

time = "Time"
horizon = 24 * 3600
routing.AddDimensionWithVehicleTransits(
time_evaluators,
horizon, #
horizon, # vehicle shift time capacity
False, # don't force start cumul to zero since we are giving TW to start nodes
time)

time_dimension = routing.GetDimensionOrDie(time)
for vehicle_id in xrange(data.num_vehicles):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(data.vehicles[vehicle_id].start_time,
data.vehicles[vehicle_id].start_time)
index = routing.End(vehicle_id)
time_dimension.CumulVar(index).SetRange(data.vehicles[vehicle_id].end_time,
data.vehicles[vehicle_id].end_time)

for location_idx, time_window in enumerate(data.time_windows):
if time_window[0] == 0:
continue
index = routing.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])