Multiple Time Windows per Location, and Vehicle Specialties & Replenishment

[Douglas Stephan]

Hello,

I want to use or-tools to solve a service vehicle routing problem. I've reviewed the documentation and examples and it looks like it can handle most of the constraints we have however our problem includes a few additional constraints including:

1) multiple time windows (up to 3) for each customer location

2) certain vehicles have certain characteristics that are required by certain service orders, and 

3) vehicles can "replenish" their capacity (i.e., unload) during the day at various sites (not always the depot) and then service more orders 

Can or-tools handle these types of constraints (e.g., using Dimensions or some other mechanism)? If so, can you provide a brief, general description of how to handle each one? 

Also, we want the solver to determine the best selection of approximately 120 orders from several hundred (or a few thousand) candidates to meet our objectives. What might the solution time be for a problem of this size on a "fairly powerful" machine? Can it be solved in < 30 sec? What size machine might be required? Note: for the last question I understand the problem characteristics (e.g., number and width of time windows, etc) and computation power impact the solution time but I'm just trying to get an order of magnitude answer. 

Thanks in advance for your help with these questions.

Doug

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Here is a more detailed problem statement for those who are interested

Briefly, we are trying to solve a service vehicle routing and scheduling problem with the following constraints:

Service Vehicle characteristics / constraints:

Multiple vehicles being dispatched from several depots (we can solve each depot separately if necessary), return to depot each evening, single shift

Different Vehicle Types (some services require specific vehicle types)

Different capacity for each vehicle, different route start time, driving and duty times, etc

"Specialties" such as certain types of product, small size to fit in tight spaces, clean vs dirty, etc

Ability to "replenish" their capacity (i.e., unload) during the day at various sites (not always the depot) and then service more orders (<= very important!)

Service Order characteristics / constraints:

Priority: some orders must be serviced on the route date

Required Vehicle Type

Different service types, service times and volumes for each order  (there are about 6 service types, some vehicles are constrained to perform only certain services)

Multiple time windows (up to 3) for each order (<= very important!)

Some services can't be mixed together on the same vehicle (i.e., can be matched to vehicle specialties)

Some orders may require more than one vehicle resource (i.e., 2 or more vehicles must meet at the customer site simultaneously to perform the service) (<= can relax this and satisfy after optimization)

Objective:

Minimize costs while also maximizing loaded miles and ensure priority orders are serviced

Problem Size:

Could be as many as 10 vehicles and about 3000 candidate orders of which only about 100 can be served on any given day

Other:

We have the OD matrix for travel time / distance

Also eventually we would like to run the model for demands covering several days or weeks and have it build the globally optimal routes over all days but this not a hard requirement in the beginning

[Sylvain Ducomman]

Hello,

I'm not an expert of or-tools, then maybe my answer is wrong.
But I think it's possible to include your additional constraints.
1) multiple time windows :
    - when you include time windows in your problem, you will have cumulVar representing this time windows, and for representing the multiple time windows, you can remove interval in the domain of cumulVar.
    - I give you an example : here the 3 time windows T = [a,b] U [c,d] U [e,f]
After adding the time dimension, you can defined your cumulVar like this : "cumul_var->SetMin(a); cumul_var->SetMax(f)"
After you remove the value that you wan't : "cumul_var->RemoveInterval(b,d) ; cumul_var->RemoveInterval(d,e)"
2) characteristics of vehicles :
    - I think you can defined this constraint when you set the cost function for a vehicle. You can defined an arc cost function for all vehicles, and in your callback function you can assign a big cost for the vehicle which has not the required characteristics by orders.
3) Reload vehicle
    - In the example, you add capacity dimension constraint like this "routing.AddDimension(NewPermanentCallback(&demand, &RandomDemand::Demand), kNullCapacitySlack, kVehicleCapacity, kCapacity);", this create CumulVar, TransitVar and SlackVar.
The SlackVar so created can be view as the reload capacity. Then for specify node, you take the SlackVar of the dimension capacity and you make equal to the amount of capacity of the vehicle.

Maybe I'm wrong, but in any case I think or-tools can handle these constraint.
I hope my answer can help you,
Thanks,

--
Sylvain Ducomman

--
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.
For more options, visit https://groups.google.com/d/optout.

-- 
Sylvain Ducomman

[Douglas Stephan]

Sylvain,

Thank you for your prompt reply. The answer regarding how to implement multiple time windows seems straight forward and definitely should work. I had thought of a similar approach regarding Reload of Vehicles and will investigate your suggestion. The one concern I have is that if I set SlackVar to the vehicle capacity the vehicle could leave the node/depot with "extra" capacity if it entered at less than full capacity but "full" capacity is subtracted from it. I'm not sure if I have made myself clear and perhaps the answer will be more apparent to me after studying the mechanism you suggest, but feel free to provide further comments. Also hoping that others may comment as well, especially with more specifics regarding vehicle specialties.
Thanks again,
Doug

[Kostadin Moraliev]

For first point:

As far as I know - you can link several visits in relation and say - "visit just one of them is enough". Create 3 times same visit, but with different TimeWindow. Link them and routing engine will execute only one of them, depending of which one is proper fo r solution.

[Siddhartha Das]

How can we add waiting time penalty in multiple pickup and drop time windows or something to minimize overall waiting time while visiting each location?
the current implementation is this:

def apply_time_windows(self, data, manager, routing, time_callback):

time_cb_index = routing.RegisterTransitCallback(time_callback)

routing.AddDimension(

time_cb_index,

4000, # slack

1440000, # max time

False, # don't force start at 0

"Time"

)

time_dim = routing.GetDimensionOrDie("Time")

for order_idx, (pickup_loc, delivery_loc) in enumerate(data["pickups_deliveries"][1:], start=1):

# node indices

pickup_index = manager.NodeToIndex(pickup_loc)

delivery_index = manager.NodeToIndex(delivery_loc)

pickup_windows = data["pickup_time_windows"][order_idx]

delivery_windows = data["time_windows"][order_idx]

travel_time = data["time_matrix"][pickup_loc][delivery_loc]

# Find earliest pickup start and latest drop end

earliest_pickup = min(s for s, e in pickup_windows)

latest_drop = max(e for s, e in delivery_windows)

available_window = latest_drop - earliest_pickup

if travel_time > available_window:

if data.get("enable_hard_constraint_tw"):

# Hard constraint: do nothing, let solver fail if infeasible

pass

else:

# Soft constraint: update latest drop window end to allow breach

# Update all delivery windows' end to 20000

delivery_windows = [(s, 20000) for (s, e) in delivery_windows]

data["time_windows"][order_idx] = delivery_windows

# pickup

p_min = min(s for s, e in pickup_windows)

p_max = max(e for s, e in pickup_windows)

time_dim.CumulVar(pickup_index).SetRange(p_min, p_max)

# delivery

d_min = min(s for s, e in delivery_windows)

d_max = max(e for s, e in delivery_windows)

time_dim.CumulVar(delivery_index).SetRange(d_min, d_max)

# pickup remove intervals

p_wins_sorted = sorted(pickup_windows)

for i in range(len(p_wins_sorted) - 1):

end_i = p_wins_sorted[i][1]

next_start = p_wins_sorted[i+1][0]

# if there is a gap → block it

if end_i < next_start:

time_dim.CumulVar(pickup_index).RemoveInterval(end_i, next_start)

# delivery remove intervals

d_wins_sorted = sorted(delivery_windows)

for i in range(len(d_wins_sorted) - 1):

end_i = d_wins_sorted[i][1]

next_start = d_wins_sorted[i+1][0]

if end_i < next_start:

time_dim.CumulVar(delivery_index).RemoveInterval(end_i, next_start)

# time_dim.SetGlobalSpanCostCoefficient(1)

self.apply_travel_time_constraint(

data,

routing,

time_dim,

pickup_loc,

delivery_loc,

pickup_index,

delivery_index,

)

def apply_travel_time_constraint(

self,

data,

routing,

time_dimension,

pickup_loc,

delivery_loc,

pickup_index,

delivery_index,

):

travel_time = data["time_matrix"][pickup_loc][delivery_loc]

logging.info(f"Applying travel time constraint: pickup {pickup_loc} to delivery {delivery_loc} with travel time {travel_time}")

routing.solver().Add(

time_dimension.CumulVar(delivery_index)

>= time_dimension.CumulVar(pickup_index) + travel_time

)

max_waiting_time = 4000

routing.solver().Add(

time_dimension.CumulVar(delivery_index)

<= time_dimension.CumulVar(pickup_index)

+ travel_time

+ max_waiting_time

)