[Question] Driver Schedules and Locking Locations to Certain Drivers

[calatian]

Hello,

I am working on a Vehicle Routing problem and have the basic VRP running, but I need some direction on how to add the following constraints next:

• Certain locations can only be serviced by a specific driver.

• Schedules: Each driver has a workday start/end time, as well as available slts throughout the day. The services should only be scheduled within those slots, and of course within their workday. Service times and travel time should also be considered, so that they are able to arrive it to the end depot before their workday ends.

Any help to get me started with these constraints would be very helpful. I am working in Python.
Thanks!

[Mizux]

1. Please take a look at [Question] How to specify which nodes a vehicle is allowed to visit in cscvrptw? #334 (comment)

index = manager.NodeToIndex(location_index)
# use vehicle 2, 3, or 4 (-1 is sentinel for unactive node since solver add node to route little by little)
routing.VehicleVar(index).SetValues([-1, 2,3,4])

2. Time Windows constraint on vehicle start/end node ?
   also take a look at https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/doc/VRP.md#time-window-constraints

Transit_time can be service_time + travel_time in your callback

or-tools/ortools/constraint_solver/samples/cvrptw.py

Lines 138 to 171 in 39f4470

	def create_time_evaluator(data):
	"""Creates callback to get total times between locations."""
	def service_time(data, node):
	"""Gets the service time for the specified location."""
	return data['demands'][node] * data['time_per_demand_unit']
	def travel_time(data, from_node, to_node):
	"""Gets the travel times between two locations."""
	if from_node == to_node:
	travel_time = 0
	else:
	travel_time = manhattan_distance(data['locations'][from_node], data[
	'locations'][to_node]) / data['vehicle_speed']
	return travel_time
	_total_time = {}
	# precompute total time to have time callback in O(1)
	for from_node in xrange(data['num_locations']):
	_total_time[from_node] = {}
	for to_node in xrange(data['num_locations']):
	if from_node == to_node:
	_total_time[from_node][to_node] = 0
	else:
	_total_time[from_node][to_node] = int(
	service_time(data, from_node) + travel_time(
	data, from_node, to_node))
	def time_evaluator(manager, from_node, to_node):
	"""Returns the total time between the two nodes"""
	return _total_time[manager.IndexToNode(from_node)][manager.IndexToNode(
	to_node)]
	return time_evaluator

[calatian]

Thank you for the answer, @Mizux. As far as #2 goes, I don't only need route start/end time constraints; each vehicle would have several time windows in which they are available. For example:

Vehicle 1:
Workday: 8AM to 5PM
Available: 8AM to 9AM, 10AM to 12PM, 2PM to 3PM, 4PM to 5PM.

And a similar situation for the rest of the vehicles.

Do you know if this is doable? Thanks again.

[Mizux]

Actually, do you want three breaks ? [9AM, 10AM], [12PM, 2PM] and [3PM, 4PM] ?
i.e. vehicle can't travel during this period

or vehicle can only deliver customer during this time windows ?

[calatian]

Ideally, the vehicle can only deliver during these time windows (but it can be any customer, not a specific location).

Otherwise, I could try "negating" the available times and using breaks instead.

Thanks again!

[Mizux]

you can remove some interval in time windows...

[calatian]

Could you give me some more details on how to do this? Thanks again!

[Mizux]

suppose you must have

or-tools/ortools/constraint_solver/samples/vrp_time_windows.py

Lines 147 to 148 in 5b5116d

	index = manager.NodeToIndex(location_idx)
	time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

and you want to remove [A,B], then simply add

 time_dimension.CumulVar(index).RemoveInterval(A, B) 

src:

or-tools/ortools/constraint_solver/constraint_solver.h

Lines 3980 to 3988 in 39f4470

	// This method removes the value 'v' from the domain of the variable.
	virtual void RemoveValue(int64 v) = 0;
	// This method removes the interval 'l' .. 'u' from the domain of
	// the variable. It assumes that 'l' <= 'u'.
	virtual void RemoveInterval(int64 l, int64 u) = 0;
	// This method remove the values from the domain of the variable.
	virtual void RemoveValues(const std::vector<int64>& values);

note: note tested however

[calatian]

When you say you remove an interval, the interval would be each break (times when a driver is not available); is that correct?

[Mizux]

yup, but in this case it means this location must not be served during the driver "break" but the solver can still use this range to make the vehicle travel during this time i.e. it's a break for the delivery, not for the driver ;)

[calatian]

However, this would be linked to the location itself (from what you are explaining), which wouldn't work for my situation. In my situation, it is the driver that cannot have any assignments during certain times (breaks). Does that make sense?

[Mizux]

so you want vehicle break interval like in

or-tools/ortools/constraint_solver/samples/cvrptw_break.py

Lines 308 to 317 in 39f4470

	break_intervals = {}
	#for v in xrange(data['num_vehicles']):
	for v in [0]:
	vehicle_break = data['breaks'][v]
	break_intervals[v] = [
	routing.solver().FixedDurationIntervalVar(
	15, 100, vehicle_break[0], vehicle_break[1], 'Break for vehicle {}'.format(v))
	]
	time_dimension.SetBreakIntervalsOfVehicle(
	break_intervals[v], v, node_visit_transit)

[calatian]

That's correct, but can you set specific times in which those breaks should be taken for each vehicle?

[Mizux]

comes from:

or-tools/ortools/constraint_solver/constraint_solver.h

Lines 1757 to 1763 in 39f4470

	// Creates an interval var with a fixed duration. The duration must
	// be greater than 0. If optional is true, then the interval can be
	// performed or unperformed. If optional is false, then the interval
	// is always performed.
	IntervalVar* MakeFixedDurationIntervalVar(int64 start_min, int64 start_max,
	int64 duration, bool optional,
	const std::string& name);

(rename in python in FixedDurationIntervalVar) so i would say for the break 9AM-10AM

# suppose uor time are in minute and you start at 0AM
start_min = 9 *60
start_max = start_min
duration = 60 # 1 Hours from 9AM to 10AM
is_optional = false
routing.solver().FixedDurationIntervalVar(start_min, start_max, duration, is_optional, "lorem ipsum...")

[calatian]

Thank you so much, Mixuz! I will look into this.

[calatian]

Hi @Mizux, thanks again for your help. I have been implementing the breaks and I don't think I have understood how to set the break intervals correctly; I keep getting an error.

I have hard-coded an example where vehicle 1 is getting a break from 11am-2pm and another one from 4-5pm, vehicle 2 gets a break from 12pm-3pm:

driver_breaks = [
    [1, [[11 * 60, 14 * 60], [16 * 60, 17 * 60]]],
    [2, [[12 * 60, 15 * 60]]]
]

    for driver in driver_breaks:
        driver_id = driver[0]
        intervals = []
        for br in driver[1]:
            start_min = br[0]
            start_max = start_min
            duration = br[1] - br[0]
            is_optional = False
            intervals.append(routing.solver().FixedDurationIntervalVar(
            start_min,
            start_max,
            duration,
            is_optional,
            "break"))
        time_dimension.SetBreakIntervalsOfVehicle(intervals, driver_id, transit_callback_index)`

I keep getting the following error:

in SetBreakIntervalsOfVehicle return _pywrapcp.RoutingDimension_SetBreakIntervalsOfVehicle(self, breaks, vehicle, node_visit_transits) TypeError: 'int' object is not iterable

I have tried to follow your example but I am not sure what I am doing wrong. Could you advise?
Thanks in advance.

[Mizux]

AFAIK break API take an array of service time (of locations size)

or-tools/ortools/constraint_solver/routing.h

Lines 2031 to 2042 in f3fd201

	// Sets the breaks for a given vehicle. Breaks are represented by
	// IntervalVars. They may interrupt transits between nodes and increase
	// the value of corresponding slack variables. However a break interval cannot
	// overlap the transit interval of a node, which is
	// [CumulVar(node), CumulVar(node) + node_visit_transits[node]), i.e. the
	// break interval must either end before CumulVar(node) or start after
	// CumulVar(node) + node_visit_transits[node].
	// In the case where the route entails some group delay on a visit, the break
	// cannot overlap that delay either, so the time window it cannot overlap is
	// [CumulVar(node) - delay, CumulVar(node) + node_visit_transits[node]).
	void SetBreakIntervalsOfVehicle(std::vector<IntervalVar*> breaks, int vehicle,
	std::vector<int64> node_visit_transits);

i.e. breaks don't overlap with service time of each nodes so you must provide the service time info since a dimension transit callback is:

transit_time(A, B) == service_time(A) + travel_time(A, B)

[calatian]

Thank you, that really helped! It works now.

[abduakhatov]

@Mizux in cvrptw_break.py#L310 example, if more than one vehicle break is added, it stucks. Whats wrong?

    # for v in xrange(data['num_vehicles']): # stucks
    for v in [0]: # works fast 

[abduakhatov]

@calatian Is it working with multiple vehicles?

[routemegood]

@abduakhatov @Mizux You can get it to work with multiple vehicles if change the way it solves. You need to add a disjunction for every node (make them optional) and then change the first_solution_strategy parameter to "ALL_UNPERFORMED". It then inserts the node visits one by one around the break, and usually returns a feasible solution with all nodes visited.

The problem is it doesn't scale too well. With lots more vehicles and nodes (10 vehicles and 320 nodes) it really struggles. After 10 minutes it had only found about 35 solutions, where without breaks it would be in the tens of thousands.

I think the problem with the example "as is" is that the default first solution strategy (or all except the one I recommended) doesn't find a feasible solution that includes breaks, or gets stuck trying to find one, even when all nodes are optional.

[sreyas7]

Thank you, that really helped! It works now.

I am trying to create a similar CVRPTW where I am allowing the vehicle to travel for multiple days and one of the constraints is that the vehicle can only travel for a duration of 'max working hours' for each day.
I am trying to implement the same approach that @Mizux had suggested but somehow I am still unable to get it.
I did the following change to overcome the exact same error that you had encountered but something seems to be wrong which leads to an infeasible solution.

I am giving it a service time of 10 minutes for each location.

Can you show what changed did you have to make?

Thanks.