Routing Crashes mid Search #4686
Answered
by
Mizux
yahia-galal
asked this question in
Routing (and legacy CP) questions
-
|
What version of OR-Tools and what language are you using? Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi) What operating system (Linux, Windows, ...) and version? What did you do? solver.pyimport requests
import absl.logging
absl.logging.set_verbosity(absl.logging.INFO)
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
from logging import getLogger
logger = getLogger(__name__)
# ----------------------
# OSRM Distance Matrix
# ----------------------
OSRM_BASE_URL = "http://router.project-osrm.org/table/v1/driving/"
def swap_coordinates(latlon: tuple) -> str:
"""
OSRM wants "lon,lat". This helper takes (lat, lon) and flips it.
"""
lat, lon = latlon
return f"{lon},{lat}"
def get_osrm_matrix(latlon_list):
"""
Query the public OSRM Table API for distances only.
Returns:
distance_matrix: 2D list in meters
"""
if len(latlon_list) < 2:
raise ValueError("At least two coordinates are required for a matrix.")
coords = [swap_coordinates(c) for c in latlon_list]
url = OSRM_BASE_URL + ";".join(coords) + "?annotations=distance"
# logger.warning(f"Fetching OSRM distance matrix from: {url}")
resp = requests.get(url)
resp.raise_for_status()
data = resp.json()
return data["distances"]
# ----------------------
# Multi-Pickup & Delivery Solver with Vehicle Speeds
# ----------------------
def solve_multi_pickup_delivery(reqs, vehicles, depot, max_search_time=10):
"""
Solves a multi-pickup & delivery Vehicle Routing Problem with per-vehicle speeds.
Inputs (all Python-native dict/list structures):
- reqs: list of requests, each request is a dict with:
- 'id': unique string
- 'pickups': list of pickups, each with:
- 'id': unique string
- 'location': [lat, lon]
- optional 'time_window': [start_s, end_s]
- optional 'service_time': seconds
- optional 'parking_time': seconds
- 'delivery': dict with:
- 'id': unique string
- 'location': [lat, lon]
- optional 'time_window': [start_s, end_s]
- optional 'service_time': seconds
- optional 'parking_time': seconds
- optional 'late_time': seconds
- vehicles: list of vehicles, each is a dict:
- 'id': unique string
- 'speed': float (meters/second)
- 'capacity': integer (max capacity)
- 'max_orders': integer (max drop-offs)
- 'time_window': [start_time_s, end_time_s] (vehicle availability)
- depot: a single dict with:
- 'id': string (e.g. "depot")
- 'location': [lat, lon]
- optional 'time_window': [start_s, end_s]
- optional 'service_time': seconds
- optional 'parking_time': seconds
Returns:
- routes: a list of dicts, each dict has:
- 'vehicle_id': string
- 'route': list of 4-tuples (node_id, start_parking_s, arrival_time_s, departure_time_s),
starting and ending at depot['id']. Times are in seconds.
"""
logger.warning(f"Max search time: {max_search_time} seconds")
MAX_ATTEMPTS = 2
# 1) Build node lists: using tuples and ids instead of integer indices
all_nodes = [tuple(depot['location'])]
node_ids = [depot['id']]
time_windows = [tuple(depot.get('time_window', (0, 24*3600)))]
service_times = [depot.get('service_time', 0)]
parking_times = [depot.get('parking_time', 0)]
demands = [0]
late_times = []
has_late_times = False
pd_pairs = [] # list of (pickup_node_index, delivery_node_index)
delivery_node_indices = []
vehicle_ids = [v['id'] for v in vehicles]
# For each request, append its pickups and delivery
for req in reqs:
num_pickups = len(req['pickups'])
# (a) add all pickups
for pu in req['pickups']:
pu_id = pu['id']
pu_loc = tuple(pu['location'])
pu_tw = tuple(pu.get('time_window', (0, 24*3600)))
pu_svc = pu.get('service_time', 0)
pu_prk = pu.get('parking_time', 0)
pu_index = len(all_nodes)
all_nodes.append(pu_loc)
node_ids.append(pu_id)
time_windows.append(pu_tw)
service_times.append(pu_svc)
parking_times.append(pu_prk)
demands.append(1)
# Store this pickup's index temporarily on the request
if "_pu_indices" not in req:
req["_pu_indices"] = []
req["_pu_indices"].append(pu_index)
# (b) add delivery
d = req['delivery']
d_id = d['id']
d_loc = tuple(d['location'])
d_tw = tuple(d.get('time_window', (0, 24*3600)))
d_svc = d.get('service_time', 0)
d_prk = d.get('parking_time', 0)
d_late = d.get('late_time', 0)
del_index = len(all_nodes)
all_nodes.append(d_loc)
node_ids.append(d_id)
time_windows.append(d_tw)
service_times.append(d_svc)
parking_times.append(d_prk)
demands.append(-num_pickups)
late_times.append(d_late)
if d_late > 0:
has_late_times = True
delivery_node_indices.append(del_index)
# Pair each pickup index with this delivery index
for pu_index in req["_pu_indices"]:
pd_pairs.append((pu_index, del_index))
del req["_pu_indices"]
num_nodes = len(all_nodes)
num_vehicles = len(vehicles)
depot_index = 0
for l in late_times:
if l > 0:
has_late_times = True
break
# 2) Fetch OSRM distance matrix (meters)
distance_matrix = get_osrm_matrix(all_nodes)
logger.warning(f"all nodes: {all_nodes}")
logger.warning(f"distance matrix size: {distance_matrix}")
logger.warning(f"late_times: {late_times}, has_late_times: {has_late_times}")
for attempt in range(MAX_ATTEMPTS):
logger.warning(f"Attempt #{attempt + 1} to solve VRP")
# 3) Create OR-Tools manager & model
manager = pywrapcp.RoutingIndexManager(
num_nodes, num_vehicles,
[depot_index] * num_vehicles,
[depot_index] * num_vehicles
)
routing = pywrapcp.RoutingModel(manager)
logger.warning(f"Created routing model with {num_nodes} nodes and {num_vehicles} vehicles.")
# 4) Register one transit callback per vehicle (using the matrix)
time_cb_idxs = []
for veh in vehicles:
speed_m_s = veh['speed']
def make_time_cb(speed):
def time_cb(from_index, to_index):
i = manager.IndexToNode(from_index)
j = manager.IndexToNode(to_index)
travel_time = distance_matrix[i][j] / speed
if distance_matrix[i][j] < 30:
return int(travel_time + service_times[i])
return int(travel_time + service_times[i] + parking_times[j])
return time_cb
cb_idx = routing.RegisterTransitCallback(make_time_cb(speed_m_s))
time_cb_idxs.append(cb_idx)
logger.warning(f"Registered {len(time_cb_idxs)} per-vehicle time callbacks.")
# 5) Set per-vehicle cost evaluator to be the time callback for that vehicle
for v_idx, cb_idx in enumerate(time_cb_idxs):
routing.SetArcCostEvaluatorOfVehicle(cb_idx, v_idx)
logger.warning("Set per-vehicle cost evaluators.")
# 6) Add Time dimension with per-vehicle callbacks
routing.AddDimensionWithVehicleTransits(
time_cb_idxs,
slack_max=24*3600,
capacity=24*3600,
fix_start_cumul_to_zero=True,
name="Time"
)
time_dim = routing.GetDimensionOrDie("Time")
# Apply time windows to all nodes
for node_idx, (start, end) in enumerate(time_windows):
idx = manager.NodeToIndex(node_idx)
time_dim.CumulVar(idx).SetRange(start, end)
# Apply time windows to vehicle start/end
for vid, veh in enumerate(vehicles):
start, end = tuple(veh['time_window'])
time_dim.CumulVar(routing.Start(vid)).SetRange(start, end)
time_dim.CumulVar(routing.End(vid)).SetRange(start, end)
logger.warning("Added time dimension with per-vehicle callbacks and applied time windows.")
logger.warning(f"demands: {demands}")
logger.warning(f"vehicle capacities: {[v['capacity'] for v in vehicles]}")
# 7b) Add dropoffs capacity
delivery_flag = [0] * num_nodes
for idx in delivery_node_indices:
delivery_flag[idx] = 1
def dropoff_callback(index):
node = manager.IndexToNode(index)
return delivery_flag[node]
dropoff_cb_idx = routing.RegisterUnaryTransitCallback(dropoff_callback)
routing.AddDimensionWithVehicleCapacity(
dropoff_cb_idx,
0, # no slack
[v['max_orders'] for v in vehicles],
True,
"DropOffCount"
)
logger.warning("Added dropoff capacity dimension.")
# 8) Enforce pickup & delivery pairing
for (pu_node, de_node) in pd_pairs:
pu_index = manager.NodeToIndex(pu_node)
de_index = manager.NodeToIndex(de_node)
routing.AddPickupAndDelivery(pu_index, de_index)
routing.solver().Add(routing.VehicleVar(pu_index) == routing.VehicleVar(de_index))
routing.solver().Add(time_dim.CumulVar(pu_index) <= time_dim.CumulVar(de_index))
logger.warning(f"Added {len(pd_pairs)} pickup-delivery pairs.")
# 10) Search parameters
search_params = pywrapcp.DefaultRoutingSearchParameters()
search_params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
search_params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
search_params.time_limit.seconds = max_search_time
search_params.log_search = True
logger.warning(f"Search parameters set with max time limit: {max_search_time} seconds.")
logger.warning("→ About to call SolveWithParameters()")
try:
solution = routing.SolveWithParameters(search_params)
logger.warning("← SolveWithParameters() returned, assignment=%r", solution)
except Exception as e:
logger.error("❌ SolveWithParameters() raised: %r", e)
raise
routes = []
# If no solution is found, we can try to extend time windows for deliveries
if solution is None:
logger.warning(f"No solution found on attempt #{attempt + 1}.")
if attempt < MAX_ATTEMPTS - 1 and has_late_times:
logger.warning("Retrying with extended time windows...")
i = 0
for del_idx in delivery_node_indices:
orig_start, orig_end = time_windows[del_idx]
extension = late_times[i]
time_windows[del_idx] = (orig_start, orig_end + extension)
logger.warning(f"Extended time window for delivery {node_ids[del_idx]} to {time_windows[del_idx]}")
i += 1
# Loop will attempt to rebuild & re-solve with updated time_windows
else:
logger.warning(f"No feasible solution found after {MAX_ATTEMPTS} attempts.")
break
# 12) Extract routes with IDs and times
else:
for vid in range(num_vehicles):
index = routing.Start(vid)
route_info = []
while not routing.IsEnd(index):
node = manager.IndexToNode(index)
nid = node_ids[node]
logger.warning(f"Vehicle {vehicle_ids[vid]} visiting node {nid} at index {index}")
logger.warning(f"Node {nid} time window: {time_windows[node]}")
logger.warning(f"Node {nid} service time: {service_times[node]}, parking time: {parking_times[node]}")
logger.warning(f"Node {nid} demand: {demands[node]}")
arrival = solution.Min(time_dim.CumulVar(index))
started_parking = arrival - parking_times[node]
departure = arrival
route_info.append((nid, started_parking, arrival, departure))
index = solution.Value(routing.NextVar(index))
# Finally the depot return
node = manager.IndexToNode(index)
nid = node_ids[node]
arrival = solution.Min(time_dim.CumulVar(index))
started_parking = arrival - parking_times[node]
route_info.append((nid, started_parking, arrival, arrival))
# Only include routes with something more than just start+end
if len(route_info) > 2:
routes.append({
'vehicle_id': vehicle_ids[vid],
'route': route_info
})
logger.warning(f"Found {len(routes)} routes for {num_vehicles} vehicles.")
return routes
return routes
# A thin wrapper that expects pure Python lists/dicts (JSON‐serializable) and returns JSON‐serializable output:
def solve_vrp_json(payload: dict) -> dict:
"""
payload: {
"requests": [
{
"id": "req1",
"pickups": [
{ "id": "req1_pu1", "location": [lat, lon], "time_window": [start, end], "service_time": int, "parking_time": int },
...
],
"delivery": {
"id": "req1_del", "location": [lat, lon], "time_window": [start, end], "service_time": int, "parking_time": int, "late_time": int
}
},
...
],
"vehicles": [
{ "id": "veh1", "speed": float_m/s, "max_orders": int, "capacity": int, "time_window": [start, end] },
...
],
"depot": { "id": "depot", "location": [lat, lon], "time_window": [start, end], "service_time": int, "parking_time": int }
}
Returns:
{
"routes": [
{
"vehicle_id": "veh1",
"route": [
["depot", start_parking_s, arrival_s, departure_s],
["req1_pu1", start_parking_s, arrival_s, departure_s],
["req1_del", start_parking_s, arrival_s, departure_s],
["depot", start_parking_s, arrival_s, departure_s]
]
},
...
]
}
"""
logger.warning(f"raw payload keys: {list(payload.keys())}")
logger.warning(f"from payload, max_search_time = {payload.get('max_search_time', 10)}")
reqs = payload.get("requests", [])
vehicles = payload.get("vehicles", [])
depot = payload.get("depot")
max_search_time = payload.get("max_search_time", 10)
if depot is None:
raise ValueError("depot must be provided in payload.")
routes = solve_multi_pickup_delivery(reqs, vehicles, depot, max_search_time)
# Convert tuple entries into lists so JSON‐serialization works
out_routes = []
for r in routes:
out_routes.append({
"vehicle_id": r["vehicle_id"],
"route": [ [nid, int(prk), int(arr), int(dep)] for (nid, prk, arr, dep) in r["route"] ]
})
return {"routes": out_routes}
# A thin wrapper that expects pure Python lists/dicts (JSON‐serializable) and returns JSON‐serializable output:
def solve_vrp_json(payload: dict) -> dict:
"""
payload: {
"requests": [
{
"id": "req1",
"pickups": [
{ "id": "req1_pu1", "location": [lat, lon], "time_window": [start, end], "service_time": int, "parking_time": int },
...
],
"delivery": {
"id": "req1_del", "location": [lat, lon], "time_window": [start, end], "service_time": int, "parking_time": int, "late_time": int
}
},
...
],
"vehicles": [
{ "id": "veh1", "speed": float_m/s, "max_orders": int, "capacity": int, "time_window": [start, end] },
...
],
"depot": { "id": "depot", "location": [lat, lon], "time_window": [start, end], "service_time": int, "parking_time": int }
}
Returns:
{
"routes": [
{
"vehicle_id": "veh1",
"route": [
["depot", start_parking_s, arrival_s, departure_s],
["req1_pu1", start_parking_s, arrival_s, departure_s],
["req1_del", start_parking_s, arrival_s, departure_s],
["depot", start_parking_s, arrival_s, departure_s]
]
},
...
]
}
"""
logger.warning(f"raw payload keys: {list(payload.keys())}")
logger.warning(f"from payload, max_search_time = {payload.get('max_search_time', 10)}")
reqs = payload.get("requests", [])
vehicles = payload.get("vehicles", [])
depot = payload.get("depot")
max_search_time = payload.get("max_search_time", 10)
if depot is None:
raise ValueError("depot must be provided in payload.")
routes = solve_multi_pickup_delivery(reqs, vehicles, depot, max_search_time)
# Convert tuple entries into lists so JSON‐serialization works
out_routes = []
for r in routes:
out_routes.append({
"vehicle_id": r["vehicle_id"],
"route": [ [nid, int(prk), int(arr), int(dep)] for (nid, prk, arr, dep) in r["route"] ]
})
return {"routes": out_routes}
payload= {
"requests": [
{
"id": "34605689",
"pickups": [
{
"id": "pickup_34605689_1",
"location": [29.974462, 31.278598],
"time_window": [309, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
],
"delivery": {
"id": "delivery_34605689_1",
"location": [29.974445, 31.27551],
"time_window": [0, 2409],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
},
{
"id": "34605705",
"pickups": [
{
"id": "pickup_34605705_3",
"location": [29.97446, 31.278685],
"time_window": [630, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
},
{
"id": "pickup_34605705_1",
"location": [29.974462, 31.278598],
"time_window": [0, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
],
"delivery": {
"id": "delivery_34605705_1",
"location": [29.97839, 31.278999],
"time_window": [0, 1110],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
},
{
"id": "34605706",
"pickups": [
{
"id": "pickup_34605706_1",
"location": [29.974462, 31.278598],
"time_window": [331, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
],
"delivery": {
"id": "delivery_34605706_1",
"location": [29.979483, 31.277918],
"time_window": [0, 2431],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
},
{
"id": "34605708",
"pickups": [
{
"id": "pickup_34605708_1",
"location": [29.974462, 31.278598],
"time_window": [332, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
],
"delivery": {
"id": "delivery_34605708_1",
"location": [29.962991, 31.281847],
"time_window": [0, 2432],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
},
{
"id": "34605737",
"pickups": [
{
"id": "pickup_34605737_1",
"location": [29.974462, 31.278598],
"time_window": [371, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
],
"delivery": {
"id": "delivery_34605737_1",
"location": [29.976069, 31.279793],
"time_window": [0, 2471],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
},
{
"id": "34605746",
"pickups": [
{
"id": "pickup_34605746_3",
"location": [29.97446, 31.278685],
"time_window": [678, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
},
{
"id": "pickup_34605746_1",
"location": [29.974462, 31.278598],
"time_window": [0, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
],
"delivery": {
"id": "delivery_34605746_1",
"location": [29.965459, 31.269997],
"time_window": [0, 1158],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
},
{
"id": "34605774",
"pickups": [
{
"id": "pickup_34605774_1",
"location": [29.974462, 31.278598],
"time_window": [421, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
],
"delivery": {
"id": "delivery_34605774_1",
"location": [29.964215, 31.284641],
"time_window": [0, 2521],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
},
{
"id": "34605777",
"pickups": [
{
"id": "pickup_34605777_1",
"location": [29.974462, 31.278598],
"time_window": [424, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
],
"delivery": {
"id": "delivery_34605777_1",
"location": [29.973169, 31.283091],
"time_window": [0, 2524],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
},
{
"id": "34605859",
"pickups": [
{
"id": "pickup_34605859_1",
"location": [29.974462, 31.278598],
"time_window": [112, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
],
"delivery": {
"id": "delivery_34605859_1",
"location": [29.971526, 31.276813],
"time_window": [0, 1312],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
},
{
"id": "34605867",
"pickups": [
{
"id": "pickup_34605867_3",
"location": [29.97446, 31.278685],
"time_window": [841, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
},
{
"id": "pickup_34605867_1",
"location": [29.974462, 31.278598],
"time_window": [541, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
],
"delivery": {
"id": "delivery_34605867_1",
"location": [29.97398, 31.275279],
"time_window": [0, 2041],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
}
],
"vehicles": [
{"id": "driver_1640702", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1231756", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1308439", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1986455", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1120028", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1454376", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_285612", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1408567", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1114425", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_765372", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1422398", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_829381", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_949982", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1681248", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1933670", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1954927", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1102197", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1406967", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1962362", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_1736827", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]},
{"id": "driver_354690", "speed": 9, "capacity": 10, "max_orders": 3, "time_window": [0, 86400]}
],
"depot": {
"id": "depot_fp",
"location": [29.9744621, 31.278598],
"time_window": [0, 86400],
"service_time": 60,
"parking_time": 60
},
"max_search_time": 3
}What did you expect to see What did you see instead? stops here Make sure you include information that can help us debug (full error message, model Proto). Anything else we should know about your project / environment it gave me windows access violation on the crash. i even tried it on google collab and on vstudio notebooks and still the same problem this is not only the input that causes crashing, and for this input when i commented out the picking and delivery constraints loop it returns a response (doesn't crash) Thank you |
Beta Was this translation helpful? Give feedback.
Answered by
Mizux
Jun 16, 2025
Replies: 4 comments 5 replies
-
|
One small comment: When i comment out time windows and drop off capacity, it doesn't prevent the crashing, it only stops crashing when i comment out this loop: for (pu_node, de_node) in pd_pairs:
pu_index = manager.NodeToIndex(pu_node)
de_index = manager.NodeToIndex(de_node)
routing.AddPickupAndDelivery(pu_index, de_index)
routing.solver().Add(routing.VehicleVar(pu_index) == routing.VehicleVar(de_index))
routing.solver().Add(time_dim.CumulVar(pu_index) <= time_dim.CumulVar(de_index)) |
Beta Was this translation helpful? Give feedback.
0 replies
-
|
small comments: The code does not use GLOG. |
Beta Was this translation helpful? Give feedback.
0 replies
-
|
in your json, we can see {
"id": "34605867",
"pickups": [
{
"id": "pickup_34605867_3",
"location": [29.97446, 31.278685],
"time_window": [841, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
},
{
"id": "pickup_34605867_1",
"location": [29.974462, 31.278598],
"time_window": [541, 86400],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
],
"delivery": {
"id": "delivery_34605867_1",
"location": [29.97398, 31.275279],
"time_window": [0, 2041],
"service_time": 60,
"parking_time": 60,
"late_time": 1800
}
}Routing solver need one pickup node per delivery node so you must duplicate the delivery node to get a 1:1 releationship. aka you can have several pickup node for on delivery node. If this pickups are alternatives then you may use the following api instead... or-tools/ortools/routing/routing.h Lines 1004 to 1008 in 63b9ecd note: not sure it is available in Python... e.g. when calling |
Beta Was this translation helpful? Give feedback.
5 replies
-
|
What if I want for a delivery node to be able to have multiple pickups (but not as alternative pickups, all must be visited) |
Beta Was this translation helpful? Give feedback.
-
|
if i duplicated the delivery node and made 1:1 relationships, the solver can make multiple visits to the same delivery, which is not logical. |
Beta Was this translation helpful? Give feedback.
-
Beta Was this translation helpful? Give feedback.
-
|
Beta Was this translation helpful? Give feedback.
-
|
Since node are inserted one by one or by pair if part of a P&D (one pair at a time!) to enforce two P&D it is tricky, you must use something along this line: pickup_1 = manager.NodeToIndex(X_node_index)
pickup_2 = manager.NodeToIndex(Y_node_index)
active_p1_p2 = routing.ActiveVar(pickup_1) * routing.ActiveVar(pickup_2)
# if both Pickup are actives then they must be on the same vehicle i.e. one vehicle to serve both part of the delivery...
routing.solver().Add(
active_p1_p2 * routing.VehicleVar(pickup_1) ==
active_p1_p2 * routing.VehicleVar(pickup_2))ref: https://gist.github.com/Mizux/9e37c370a459bd472a6ac13c304f0b54 |
Beta Was this translation helpful? Give feedback.
Answer selected by
Mizux
-
|
please do not spam
Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53
00
Le lun. 16 juin 2025 à 14:32, yahia-galal ***@***.***> a
écrit :
… @Mizux <https://github.com/Mizux>
—
Reply to this email directly, view it on GitHub
<#4686 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACUPL3PCBJRB7KEVVTVO5PT3D22MFAVCNFSM6AAAAAB7NBEEP2VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTGNBYGM3DQNQ>
.
You are receiving this because you commented.Message ID:
***@***.***>
|
Beta Was this translation helpful? Give feedback.
0 replies
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
in your json, we can see
{ "id": "34605867", "pickups": [ { "id": "pickup_34605867_3", "location": [29.97446, 31.278685], "time_window": [841, 86400], "service_time": 60, "parking_time": 60, "late_time": 1800 }, { "id": "pickup_34605867_1", "location": [29.974462, 31.278598], "time_window": [541, 86400], "service_time": 60, "parking_time": 60, "late_t…