[Python] How to enforce per-passenger maximum ride time as a soft constraint in OR-Tools VRP?

I’m working on a Vehicle Routing Problem using Google OR-Tools. The context is that each “customer” (or passenger) has to be picked up and eventually delivered to a common destination (for example, a school in the morning, or from the school to home in the afternoon).

What I need is a way to enforce or at least strongly encourage that:

(Arrival time at destination) – (Pickup time of customer) ≤ MaxRideTime

For example, each passenger should not spend more than 60 minutes on the vehicle.

I already have:

A Duration (time) dimension for travel times.

Capacity constraints per vehicle.

A route duration cap (e.g., max 3 hours per bus).

What I’m struggling with is how to express the per-customer ride time constraint inside the OR-Tools RoutingModel:

It depends on both the end cumul (at the route’s final stop) and the pickup cumul for each customer.

OR-Tools’ Routing API lets me set soft/hard bounds on individual cumul vars, but not directly on a difference like (End – Pickup).

I would like the solver to prefer solutions where all customers have ride times ≤ 60 minutes (soft constraint, penalize violations), but I’m not sure what the best modeling strategy is.

Has anyone modeled this before?

Is there a clean way to add a soft penalty for (end – pickup) directly in OR-Tools?

Do I need to introduce auxiliary variables with big-M constraints?

Or is there another approach (multi-stage solving, custom dimensions, etc.) that works better?

Any ideas, patterns, or references would be really helpful. Thanks!

data = self._create_data_model(route_id, is_am)
if not data:
print("Failed to create data model")
return None

print("Data model created successfully, starting OR-Tools solver...")

# Create routing manager and model
manager = pywrapcp.RoutingIndexManager(
len(data['duration_matrix']),
data['num_vehicles'],
data['starts'],
data['ends']
)
routing = pywrapcp.RoutingModel(manager)

# Create distance callback
def distance_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['duration_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add duration constraint (4 hours max)
dimension_name = 'Duration'
routing.AddDimension(
transit_callback_index,
0, # slack
data['route_duration'], # vehicle maximum travel time (4 hours)
True, # start cumul to zero
dimension_name
)

# Add capacity constraint
def demand_callback(from_index):
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]

demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0,
data['vehicle_capacities'],
True,
'Capacity'
)

# Set search parameters with 1 hour time limit
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.time_limit.seconds = 3600 # 1 hour solver time limit

print("Running OR-Tools solver with 1 hour time limit...")

start_time = datetime.now()
start_timestamp = time.time()

print(f"Optimization started at: {start_time.strftime('%Y-%m-%d %H:%M:%S')}")

assignment = routing.SolveWithParameters(search_parameters)

# Record end time
end_time = datetime.now()
end_timestamp = time.time()

solve_duration = end_timestamp - start_timestamp

print(f"Optimization completed at: {end_time.strftime('%Y-%m-%d %H:%M:%S')}")
print(f"Total solve time: {solve_duration:.2f} seconds ({solve_duration/60:.1f} minutes)")

if assignment:
print("Solution found! Saving results...")
solution = self._save_solution_to_json(data, manager, routing, assignment,
start_time, end_time, solve_duration)
return solution
else:
print("No solution found within 1 hour time limit")
# Still save timing info even if no solution
no_solution_data = {
'route_id': data['route_id'],
'district_id': data['district_id'],
'is_am': data['is_am'],
'status': 'no_solution_found',
'optimization_start_time': start_time.isoformat(),
'optimization_end_time': end_time.isoformat(),
'solve_duration_seconds': solve_duration,
'solve_duration_minutes': solve_duration/60,
'time_limit_seconds': 3600,
'max_route_duration_hours': data['route_duration']/3600
}

filename = f"route_no_solution_{data['route_id']}_{'AM' if data['is_am'] else 'PM'}.json"
with open(filename, 'w') as f:
json.dump(no_solution_data, f, indent=2)
print(f"No solution info saved to {filename}")

return None

Continue reading...