Intra-factory Transport#
Capacitated Pickup and Delivery Problem with Time Windows#
from cuopt import routing
from cuopt import distance_engine
import cudf
import numpy as np
import pandas as pd
/home/luffy/.local/lib/python3.12/site-packages/cupy/_environment.py:541: UserWarning:
--------------------------------------------------------------------------------
CuPy may not function correctly because multiple CuPy packages are installed
in your environment:
cupy, cupy-cuda12x
Follow these steps to resolve this issue:
1. For all packages listed above, run the following command to remove all
existing CuPy installations:
$ pip uninstall <package_name>
If you previously installed CuPy via conda, also run the following:
$ conda uninstall cupy
2. Install the appropriate CuPy package.
Refer to the Installation Guide for detailed instructions.
https://docs.cupy.dev/en/stable/install.html
--------------------------------------------------------------------------------
warnings.warn(f'''
Factory automation allows companies to raise the quality and consistency of manufacturing processes while also allowing human workers to focus on safer, less repetitive tasks that have higher cognitive and creative demands.
In this scenario we have a set of intra-factory transport orders to move products at various stages in the assembly process from one processing station to another. Each station represents a particular type of manufacturing process and a given product may need to visit each processing station more than once. Multiple autonomous mobile robots (AMRs) with a fixed capacity will execute pickup and delivery orders between target locations, all with corresponding time_windows.
Problem Details:#
4 Locations each with an associated demand
1 Start Location for AMRs
3 Process Stations
3 AMRs with associated capacity
Hours of operation
factory_open_time = 0
factory_close_time = 100
Waypoint Graph#
Compressed Sparse Row (CSR) representation of above weighted waypoint graph.#
For details on the CSR encoding of the above graph see the cost_matrix_and_waypoint_graph_creation.ipynb notebook.
offsets = np.array([0, 1, 3, 7, 9, 11, 13, 15, 17, 20, 22])
edges = np.array([2, 2, 4, 0, 1, 3, 5, 2, 6, 1, 7, 2, 8, 3, 9, 4, 8, 5, 7, 9, 6, 8])
weights = np.array([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2])
Select specific waypoints in the graph as target locations.#
In this case we would like the AMRs to begin from waypoint 0 and service locations 4, 5, and 6.
target_locations = np.array([0, 4, 5, 6])
Cost Matrix#
Use cuOpt to calculate the corresponding cost matrix and transit time matrix.#
Lets assume transit time is same as cost matrix.
waypoint_graph = distance_engine.WaypointMatrix(
offsets,
edges,
weights
)
cost_matrix = waypoint_graph.compute_cost_matrix(target_locations)
transit_time_matrix = cost_matrix.copy(deep=True)
target_map = {v:k for k, v in enumerate(target_locations)}
index_map = {k:v for k, v in enumerate(target_locations)}
print(f"Waypoint graph node to time matrix index mapping \n{target_map}\n")
print(cost_matrix)
Waypoint graph node to time matrix index mapping
{np.int64(0): 0, np.int64(4): 1, np.int64(5): 2, np.int64(6): 3}
0 1 2 3
0 0.0 6.0 4.0 6.0
1 6.0 0.0 4.0 6.0
2 4.0 4.0 0.0 4.0
3 6.0 6.0 4.0 0.0
Important Notes:#
If the user already has square cost matrix and transit time matrix, it can be used directly.
If there are different kinds of vehicles (e.g., bike, car, truck) requiring different cost and transit time matrices:
Provide vehicle type index while setting cost/transit time matrix.
Set vehicle type for each vehicle in
vehicle_data.Share all the vehicle types for all vehicles.
Transport Orders#
Setup Transport Order Data
The transport orders dictate the movement of parts from one area of the factory to another. In this example nodes 4, 5, and 6 represent the processing stations that parts must travel between and deliveries to node 0 represent the movement of parts off the factory floor.
transport_order_data = cudf.DataFrame({
"pickup_location": [4, 5, 6, 6, 5, 4],
"delivery_location": [5, 6, 0, 5, 4, 0],
"order_demand": [1, 1, 1, 1, 1, 1],
"earliest_pickup": [0, 0, 0, 0, 0, 0],
"latest_pickup": [10, 20, 30, 10, 20, 30],
"pickup_service_time": [2, 2, 2, 2, 2, 2],
"earliest_delivery": [0, 0, 0, 0, 0, 0],
"latest_delivery": [45, 45, 45, 45, 45, 45],
"delivery_serivice_time":[2, 2, 2, 2, 2, 2]
})
transport_order_data
| pickup_location | delivery_location | order_demand | earliest_pickup | latest_pickup | pickup_service_time | earliest_delivery | latest_delivery | delivery_serivice_time | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 4 | 5 | 1 | 0 | 10 | 2 | 0 | 45 | 2 |
| 1 | 5 | 6 | 1 | 0 | 20 | 2 | 0 | 45 | 2 |
| 2 | 6 | 0 | 1 | 0 | 30 | 2 | 0 | 45 | 2 |
| 3 | 6 | 5 | 1 | 0 | 10 | 2 | 0 | 45 | 2 |
| 4 | 5 | 4 | 1 | 0 | 20 | 2 | 0 | 45 | 2 |
| 5 | 4 | 0 | 1 | 0 | 30 | 2 | 0 | 45 | 2 |
AMR Data#
Set up AMR fleet data
n_robots = 2
robot_data = {
"robot_ids": [i for i in range(n_robots)],
"carrying_capacity":[2, 2]
}
robot_data = cudf.DataFrame(robot_data).set_index('robot_ids')
robot_data
| carrying_capacity | |
|---|---|
| robot_ids | |
| 0 | 2 |
| 1 | 2 |
cuOpt DataModel View#
Setup the routing.DataModel.
n_locations = len(cost_matrix)
n_vehicles = len(robot_data)
# a pickup order and a delivery order are distinct with additional pad for the depot with 0 demand
n_orders = len(transport_order_data) * 2
data_model = routing.DataModel(n_locations, n_vehicles, n_orders)
data_model.add_cost_matrix(cost_matrix)
data_model.add_transit_time_matrix(transit_time_matrix)
Set the Per-Order Demand#
From the perspective of the cuOpt solver_settings, each distinct transaction (pickup order or delivery order) are treated separately with demand for pickup denoted as positive and the corresponding delivery treated as negative demand.
# This is the number of parts that needs to be moved.
raw_demand = transport_order_data["order_demand"]
# When dropping off parts we want to remove one unit of demand from the robot.
drop_off_demand = raw_demand * -1
# Create pickup and delivery demand.
order_demand = cudf.concat([raw_demand, drop_off_demand], ignore_index=True)
order_demand
0 1
1 1
2 1
3 1
4 1
5 1
6 -1
7 -1
8 -1
9 -1
10 -1
11 -1
Name: order_demand, dtype: int64
# Add the capacity dimension.
data_model.add_capacity_dimension("demand", order_demand, robot_data['carrying_capacity'])
Setting Order Locations#
Set the order locations and pickup and delivery pairs.
pickup_order_locations = cudf.Series([target_map[loc] for loc in transport_order_data['pickup_location'].to_arrow().to_pylist()])
delivery_order_locations = cudf.Series([target_map[loc] for loc in transport_order_data['delivery_location'].to_arrow().to_pylist()])
order_locations = cudf.concat([pickup_order_locations, delivery_order_locations], ignore_index=True)
print(order_locations)
# add order locations
data_model.set_order_locations(order_locations)
0 1
1 2
2 3
3 3
4 2
5 1
6 2
7 3
8 0
9 2
10 1
11 0
dtype: int64
Mapping Pickups to Deliveries#
# IMPORTANT NOTE : Pickup and delivery pairs are indexed into the order locations array.
npair_orders = int(len(order_locations)/2)
pickup_orders = cudf.Series([i for i in range(npair_orders)])
delivery_orders = cudf.Series([i + npair_orders for i in range(npair_orders)])
# Add pickup and delivery pairs.
data_model.set_pickup_delivery_pairs(pickup_orders, delivery_orders)
Time Windows#
# create earliest times
vehicle_earliest_time = cudf.Series([factory_open_time] * n_vehicles)
order_time_window_earliest = cudf.concat([transport_order_data["earliest_pickup"], transport_order_data["earliest_delivery"]], ignore_index=True)
# create latest times
vehicle_latest_time = cudf.Series([factory_close_time] * n_vehicles)
order_time_window_latest = cudf.concat([transport_order_data["latest_pickup"], transport_order_data["latest_delivery"]], ignore_index=True)
# create service times
order_service_time = cudf.concat([transport_order_data["pickup_service_time"], transport_order_data["delivery_serivice_time"]], ignore_index=True)
# add time window constraints
data_model.set_order_time_windows(order_time_window_earliest, order_time_window_latest)
data_model.set_order_service_times(order_service_time)
data_model.set_vehicle_time_windows(vehicle_earliest_time, vehicle_latest_time)
CuOpt SolverSettings#
Set up routing.SolverSettings.
solver_settings = routing.SolverSettings()
# solver_settings will run for given time limit. Larger and/or more complex problems may require more time.
solver_settings.set_time_limit(5)
Solution#
routing_solution = routing.Solve(data_model, solver_settings)
if routing_solution.get_status() == 0:
print("Cost for the routing in time: ", routing_solution.get_total_objective())
print("Vehicle count to complete routing: ", routing_solution.get_vehicle_count())
print(routing_solution.route)
else:
print("NVIDIA cuOpt Failed to find a solution with status : ", routing_solution.get_status())
Cost for the routing in time: 32.0
Vehicle count to complete routing: 2
route arrival_stamp truck_id location type
0 0 0.0 0 0 Depot
1 1 4.0 0 2 Pickup
2 3 10.0 0 3 Pickup
3 7 12.0 0 3 Delivery
4 2 14.0 0 3 Pickup
5 9 20.0 0 2 Delivery
6 8 26.0 0 0 Delivery
7 0 28.0 0 0 Depot
8 0 0.0 1 0 Depot
9 4 4.0 1 2 Pickup
10 0 10.0 1 1 Pickup
11 10 12.0 1 1 Delivery
12 5 14.0 1 1 Pickup
13 6 20.0 1 2 Delivery
14 11 26.0 1 0 Delivery
15 0 28.0 1 0 Depot
Converting Solution to Waypoint Graph#
Because we maintained the mapping between cost matrix indices and locations in the waypoint graph, we can now convert our solution to reference the nodes in the waypoint graph corresponding to the selected target locations.
target_loc_route = [index_map[loc] for loc in routing_solution.route['location'].to_arrow().to_pylist()]
routing_solution.route['order_array_index'] = routing_solution.route['route']
routing_solution.route['route'] = target_loc_route
print(routing_solution.route)
route arrival_stamp truck_id location type order_array_index
0 0 0.0 0 0 Depot 0
1 5 4.0 0 2 Pickup 1
2 6 10.0 0 3 Pickup 3
3 6 12.0 0 3 Delivery 7
4 6 14.0 0 3 Pickup 2
5 5 20.0 0 2 Delivery 9
6 0 26.0 0 0 Delivery 8
7 0 28.0 0 0 Depot 0
8 0 0.0 1 0 Depot 0
9 5 4.0 1 2 Pickup 4
10 4 10.0 1 1 Pickup 0
11 4 12.0 1 1 Delivery 10
12 4 14.0 1 1 Pickup 5
13 5 20.0 1 2 Delivery 6
14 0 26.0 1 0 Delivery 11
15 0 28.0 1 0 Depot 0
Convert Routes from Target Location-Based Routes to Waypoint-Level Routes#
unique_robot_ids = routing_solution.route['truck_id'].unique()
all_routes = routing_solution.get_route()
for robot in unique_robot_ids.to_arrow().to_pylist():
route = all_routes[all_routes['truck_id']==robot]
waypoint_route = waypoint_graph.compute_waypoint_sequence(target_locations, route)
print(f"Target location level route for robot {robot}:\n{all_routes[all_routes['truck_id']==robot]['route']}\n\n")
print(f"Waypoint level route for robot {robot}:\n{waypoint_route}\n\n")
Target location level route for robot 0:
0 0
1 5
2 6
3 6
4 6
5 5
6 0
7 0
Name: route, dtype: int64
Waypoint level route for robot 0:
waypoint_sequence waypoint_type
0 0 w
1 2 w
2 5 Pickup
3 5 w
4 8 w
5 9 w
6 6 Pickup
7 6 Delivery
8 6 Pickup
9 6 w
10 9 w
11 8 w
12 5 Delivery
13 5 w
14 2 w
15 0 Delivery
16 0 Depot
Target location level route for robot 1:
8 0
9 5
10 4
11 4
12 4
13 5
14 0
15 0
Name: route, dtype: int64
Waypoint level route for robot 1:
waypoint_sequence waypoint_type
0 0 w
1 2 w
2 5 Pickup
3 5 w
4 8 w
5 7 w
6 4 Pickup
7 4 Delivery
8 4 Pickup
9 4 w
10 7 w
11 8 w
12 5 Delivery
13 5 w
14 2 w
15 0 Delivery
16 0 Depot