Python API Reference¶
Routing¶
Data Model¶
- class cuopt.routing.Objective(value)¶
Enums to configure objective of the solution
VEHICLE - Models with respect to number of vehicles
COST - Models with respect to total cost
TRAVEL_TIME - Models with respect to travel time
CUMUL_PACKAGE_TIME - How long an order has been out of the depot
It accumulates the difference between arrival time at a delivery node and the depot leave time. The depot leave time is the earliest time we can leave the depot such that there is no wait time at the first node.
CUMUL_EARLIEST_DIFF - How close to the node earliest time we are delivering
In the case of pickup and delivery we use the earliest time of the pickup node.
- VEHICLE = 0¶
- COST = 1¶
- TRAVEL_TIME = 2¶
- CUMUL_PACKAGE_TIME = 3¶
- CUMUL_EARLIEST_DIFF = 4¶
- class cuopt.routing.DataModel¶
Initialize a Data Model.
- Parameters
- n_locationsInteger
number of locations to visit, including vehicle/technician location.
- n_fleetInteger
number of vehicles/technician in the fleet.
- n_ordersInteger
number of orders, need to consider order for vehicle location as well.
- session_idInteger
This is used with dask for Multi GPU scenario.
- Note:
A cost matrix must be set before passing this object to the solver.
If vehicle locations is not set, then by default 0th index in cost/transit time matrix, time windows, capacity dimension, order location is considered as start and end location of all the vehicles.
Examples
>>> from cuopt import routing >>> locations = [0, 1, 2, 3, 4, 5, 6] >>> vehicles = [0, 1, 2, 3] >>> data_model = routing.DataModel(len(locations), len(vehicles))
Methods
add_break_dimension
(break_earliest, ...)Add break time windows to model the Vehicle Routing Problem with Time Windows (VRPTW).
add_capacity_dimension
(name, demand, capacity)Add capacity dimensions to model the Capacitated Vehicle Routing Problem (CVRP)
add_cost_matrix
(cost_mat[, vehicle_type])Add a matrix for all locations (vehicle/technician locations included) at once.
add_initial_solution
(initial_solution[, ...])Allows to feed the solver a custom initial solution.
add_order_precedence
(node_id, preceding_nodes)Add precedence constraint for a node.
add_order_vehicle_match
(order_id, vehicles)Control if an order should only be served by a subset of vehicles
add_transit_time_matrix
(mat[, vehicle_type])Add transit time matrix for all locations (vehicle/technician locations included) at once.
add_vehicle_order_match
(vehicle_id, orders)Control if a vehicle can only serve a subset of orders
Returns a dictionary containing break earliest, latest, duration under demand name.
Returns break locations as cudf.Series with int type.
Returns a dictionary containing demands and capacity under demand name.
get_cost_matrix
([vehicle_type])Returns cost matrix as 2D DeviceNDArray in row major format.
Returns drop return trips as cudf.Series with bool type.
Returns the number of vehicles in the fleet.
Returns initial solutions that's set, else it will return empty dictionary.
Returns max lateness per route.
Returns max slack time set.
Returns minimum vehicles set.
Returns the number of locations (vehicle start/end locations + task locations).
Return number of orders.
Returns objectives as cudf.Series with int type and weights as cudf.Series with float type.
Returns order locations as cudf.Series with int type.
Returns a list which contains tuples of node and precedence.
Returns order priorities as cudf.Series with uint8 type
Returns earliest, latest and service time windows as cudf.Series with int type.
Returns a dictionary containing the vehicles that can fulfill specified orders
Returns pick up and delivery order indices as cudf.Series with int type.
Returns skip first trips as cudf.Series with bool type.
Returns all transit time matrices as 2D DeviceNDArray in row major format as dictionary with vehicle types as keys.
get_transit_time_matrix
([vehicle_type])Returns transit time matrix as 2D DeviceNDArray in row major format.
Returns start and return locations as cudf.Series with int type.
Returns max costs per vehicles
Returns a dictionary containing the orders that can be fulfilled for specified vehicles
Returns priorities of vehicles in the fleet as cudf.Series with int type.
Returns earliest and latest time windows as cudf.Series with int type.
Returns types of vehicles in the fleet as cudf.Series with uint8 type
set_break_locations
(break_locations)The vehicle is allowed to stop at specific locations during a break.
set_drop_return_trips
(set_drop_return_trips)Control if individual vehicles in the fleet return to the end location after the last stop.
In soft time windows scope, only an excess on demand or max slack check will load a new vehicle.
set_max_slack_per_vehicle
(slack_max)Budget to let vehicles wait at locations up to the specified time.
set_min_vehicles
(min_vehicles)Request a minimum number of vehicles to be used for routing.
set_objective_function
(objectives, ...)During improvement phase the solver only optimizes for the cost.
set_order_locations
(order_locations)Set a location for each order.
set_order_priorities
(priorities)Set priorities for orders
set_order_time_windows
(earliest, latest, service)Add order time windows to model the Vehicle Routing Problem with Time Windows (VRPTW)
set_pickup_delivery_pairs
(pickup_indices, ...)Set pick-up delivery pairs given by indices to the orders.
set_skip_first_trips
(set_skip_first_trips)Skips/neglects cost of travel to first task location, implicitly skipping the travel to location.
set_vehicle_locations
(start_locations, ...)Set start and return locations for vehicles in the fleet.
set_vehicle_max_costs
(vehicle_max_costs)Limits per vehicle primary matrix cost accumulated along a route.
set_vehicle_priorities
(vehicle_priorities)Set vehicle priorities in the fleet.
set_vehicle_time_windows
(earliest_time, ...)Set vehicle time windows in the fleet.
set_vehicle_types
(vehicle_types)Set vehicle types in the fleet.
- add_break_dimension(break_earliest, break_latest, break_duration)¶
Add break time windows to model the Vehicle Routing Problem with Time Windows (VRPTW). The vehicles have break time windows within which the breaks must be taken. And multiple breaks can be added using the same api as another dimension, check the example.
Note: The values provided are considered as units and it is user’s responsibility to ensure all time related entries are normalized to one common unit (hours/minutes/seconds/any).
- Parameters
- break_earliest: cudf.Series
Earliest time a vehicle can be at a break location.
- break_latest: cudf.Series
Latest time a vehicle can be at a break location.
- break_service: cudf.Series
Time spent at the break location, internally equivalent to service time.
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> cost_mat = [ ... [0, 1, 5, 2], ... [2, 0, 7, 4], ... [1, 5, 0, 9], ... [5, 6, 2, 0] ... ] >>> cost_mat = cudf.DataFrame(cost_mat) >>> cost_mat 0 1 2 3 0 0 1 5 2 1 2 0 7 4 2 1 5 0 9 3 5 6 2 0 >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.add_cost_matrix(cost_mat) >>> time_mat = [ ... [0, 10, 50, 20], ... [20, 0, 70, 40], ... [10, 50, 0, 90], ... [50, 60, 20, 0] ... ] >>> time_mat = cudf.DataFrame(time_mat) >>> data_model.add_transit_time_matrix(time_mat) >>> # Considering vehicles need to take two breaks >>> lunch_break_earliest = [20, 25] >>> lunch_break_latest = [40, 45] >>> lunch_break_service = [5, 5] >>> data_model.add_break_dimension( ... cudf.Series(lunch_break_earliest), ... cudf.Series(lunch_break_latest), ... cudf.Series(lunch_break_service) ... ) >>> snack_break_earliest = [40, 45] >>> snack_break_latest = [60, 65] >>> snack_break_service = [5, 5] >>> data_model.add_break_dimension( ... cudf.Series(snack_break_earliest), ... cudf.Series(snack_break_latest), ... cudf.Series(snack_break_service)
- add_capacity_dimension(name, demand, capacity)¶
Add capacity dimensions to model the Capacitated Vehicle Routing Problem (CVRP)
The vehicles have a limited carrying capacity of the goods that must be delivered. This function can be called more than once to model multiple capacity dimensions (weight, volume, number of orders, skills). After solving the problem, the demands on each route will not exceed the vehicle capacities.
- Note:
If vehicle locations is not set, then by default 0th index in demand column is considered start and end location of all the vehicles. May be it is better to keep demand to be 0.
- Parameters
- namestr
user-specified name for the dimension
- demandcudf.Series
cudf.Series containing integer demand value for each locations, including the depot. Order is implicit and should be consitent with the data model.
- capacitycudf.Series
cudf.Series containing integer capacity value for each vehicle in the fleet. Size of this series must be equal to fleet_size in data model
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> demand_weight = [0, 10, 20, 40] >>> skill_x = [0, 1, 0, 1] # 0 - skill not needed, 1 - needed >>> skill_y = [0, 0, 1, 1] # 0 - skill not needed, 1 - needed >>> vehicles = [ 0, 1] >>> # Vehicle 0 can carry at max 50 units and vehicle 1 100 units >>> capacity_weight = [50, 100] >>> # If vehicle has skill keep a high value > number of orders, else 0 >>> veh_skill_x = [0, 1000] # vehicle-0 doesn't have the skill >>> veh_skill_y = [1000, 1000] # both vehicles have the skill >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> # Add weight capacity dimension >>> data_model.add_capacity_dimension( ... "weight", ... cudf.Series(demand_weight), ... cudf.Series(capacity_weight) ... ) >>> # Add skill x as capacity >>> data_model.add_capacity_dimension( ... "skill_x", ... cudf.Series(skill_x), ... cudf.Series(veh_skill_x) ... ) >>> # Add skill y as capacity >>> data_model.add_capacity_dimension( ... "skill_y", ... cudf.Series(skill_y), ... cudf.Series(veh_skill_y) ... )
- add_cost_matrix(cost_mat, vehicle_type=0)¶
Add a matrix for all locations (vehicle/technician locations included) at once.
A cost matrix is a square matrix containing the cost of travel which can be distance, time or any other metric, taken pairwise, between all locations. Diagonal elements should be 0.
This cost matrix will be used to find the routes through all the locations. The user can call add_cost_matrix multiple times. Setting the vehicle type will enable heterogenous fleet. It can model traveling distances for different vehicles (bicyces, bikes, trucks).
- Note:
If vehicle locations is not set, then by default 0th index and column are considered start and end location for all vehicles.
- Parameters
- cost_matcudf.DataFrame
cudf.DataFrame representing floating point square matrix with num_location rows and columns.
- vehicle_typeuint8
Identifier of the vehicle.
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> cost_mat_bikes = [ ... [0, 1, 5, 2], ... [2, 0, 7, 4], ... [1, 5, 0, 9], ... [5, 6, 2, 0] ... ] >>> cost_mat_bikes = cudf.DataFrame(cost_mat_bikes) >>> cost_mat_bikes 0 1 2 3 0 0 1 5 2 1 2 0 7 4 2 1 5 0 9 3 5 6 2 0 >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.add_cost_matrix(cost_mat_bikes, 1) >>> cost_mat_car = [ ... [0, 1, 2, 1], ... [1, 0, 3, 2], ... [1, 2, 0, 3], ... [1, 3, 9, 0] ... ] >>> cost_mat_car = cudf.DataFrame(cost_mat_bikes) >>> cost_mat_car 0 1 2 3 0 0 1 2 1 1 1 0 3 2 2 1 2 0 3 3 1 3 9 0 >>> data_model.add_cost_matrix(cost_mat_car, 2)
- add_initial_solution(initial_solution, solution_id=0)¶
Allows to feed the solver a custom initial solution.
The number of initial solutions will override the number of climbers. See the provided example for an idea of a valid initial solution.
- Parameters
- initial_solutioncudf.DataFrame
Expected column names are “truck_id” and “route”.
- solution_idint
An integer number to signify a particular solution
Examples
>>> d = routing.DataModel(n_locations, fleet_size, n_orders) >>> d.add_cost_matrix(distances) >>> cuopt_solution = routing.Solve(d) >>> df = cuopt_solution.get_route().copy() >>> df = df.drop('arrival_stamp',axis=1) >>> # Add the guess to use start from a pre-computed route >>> d.add_initial_solution(df, solution_id=0) >>> routing.Solve(d)
- add_order_precedence(node_id, preceding_nodes)¶
Add precedence constraint for a node.
It is guaranteed that the service begin time of node_id will be later than service end time of all the preceding nodes. Circular precedence of any form is not allowed. Chain precedences are possible.
- Parameters
- node_idInteger
Node id of the node that has precedence constraints.
- preceding_nodescudf.Series
cudf.Series contains the nodes that must precede the given node_id
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> cost_mat = [ ... [0, 1, 5, 2], ... [2, 0, 7, 4], ... [1, 5, 0, 9], ... [5, 6, 2, 0] ... ] >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.add_cost_matrix(cudf.DataFrame(cost_mat)) >>> # Consider a constraint where node 3 can be serviced only after >>> # node 2 and node 1 >>> data_model.add_order_precedence(3, cudf.Series([2, 1])) >>> routing.Solve(data_model).display_routes()
- add_order_vehicle_match(order_id, vehicles)¶
Control if an order should only be served by a subset of vehicles
- Parameters
- order_idInteger
order id of the order that has restriction on vehicles
- vehiclescudf.Series
cudf.Series contains the vehicles that can fulfill the order with order_id
- Note: A user can set this multiple times. However, if it is
set more than once for same order, the vehicle list will be overridden with the most recent function call
The vehicles in the give list can serve other orders as well. To make a vehicle serve only a subset of orders use add_vehicle_order_match function
Examples
>>> n_locations = 4 >>> n_vehicles = 3 >>> d = routing.DataModel(n_locations, n_vehicles) >>> distance = [ >>> [0., 1., 5., 2.], [2., 0., 7., 4.], >>> [1., 5., 0., 9.], [5., 6., 2., 0.]] >>> d.add_cost_matrix(cudf.DataFrame(distances)) >>> # order 1 can be served only by vehicle 0, >>> # order 2 can be served only by vehicle 1, >>> # order 3 can be served only by vehicle 2 >>> d.add_order_vehicle_match(1, cudf.Series([0])) >>> d.add_order_vehicle_match(2, cudf.Series([1])) >>> d.add_order_vehicle_match(3, cudf.Series([2])) >>> cuopt_solution = routing.Solve(d)
- add_transit_time_matrix(mat, vehicle_type=0)¶
Add transit time matrix for all locations (vehicle/technician locations included) at once.
This matrix is used to check constraints satisfiability rather than participating in cost optimization.
For instance, this matrix can be used to model the time to travel between locations with time windows referring to it while the solver could optimize for cost/distance. A transit time matrix is defined as a square matrix containing the cost, taken pairwise, between all locations. Users should pre-compute time between each pair of locations with their own technique before calling this function. Entries in this matrix could represent time, miles, meters or any metric that can be stored as a real number and satisfies the property above.
The user can call add_transit_time_matrix multiple times. Setting the vehicle type will enable heterogenous fleet. It can model traveling speeds for different vehicles (bicyces, bikes, trucks).
Time windows specified in set_order_time_windows will validate the time to travel with secondary matrix if it is available, else primary matrix is used to validate the constraint.
- Note:
The values provided are considered as units and it is user’s responsibility to ensure all time related entries are normalized to one common unit (hours/minutes/seconds/any).
If vehicle locations is not set, then by default 0th index and column are considered start and end location for all vehicles.
- Parameters
- matcudf.DataFrame
cudf.DataFrame representing floating point square matrix with num_location rows and columns.
- vehicle_typeuint8
Identifier of the vehicle.
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> cost_mat = [ ... [0, 1, 5, 2], ... [2, 0, 7, 4], ... [1, 5, 0, 9], ... [5, 6, 2, 0] ... ] >>> cost_mat = cudf.DataFrame(cost_mat) >>> cost_mat 0 1 2 3 0 0 1 5 2 1 2 0 7 4 2 1 5 0 9 3 5 6 2 0 >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.add_cost_matrix(cost_mat, 0) >>> time_mat = [ ... [0, 10, 50, 20], ... [20, 0, 70, 40], ... [10, 50, 0, 90], ... [50, 60, 20, 0] ... ] >>> time_mat = cudf.DataFrame(time_mat) >>> data_model.add_transit_time_matrix(time_mat, 0)
- add_vehicle_order_match(vehicle_id, orders)¶
Control if a vehicle can only serve a subset of orders
- Parameters
- vehicle_idInteger
vehicle id of the vehicle that has restriction on orders
- orderscudf.Series
cudf.Series contains the orders that can be fulfilled by vehicle with vehicle_id
- Note: A user can set this multiple times. However, if it is
set more than once for same vehicle, the order list will be overridden with the most recent function call.
The orders in the give list allowed to be served by other vehicles. To make any order served only by a particular vehicle, use add_order_vehicle_match function
Examples
>>> n_locations = 4 >>> n_vehicles = 3 >>> d = routing.DataModel(n_locations, n_vehicles) >>> distance = [ >>> [0., 1., 5., 2.], [2., 0., 7., 4.], >>> [1., 5., 0., 9.], [5., 6., 2., 0.]] >>> d.add_cost_matrix(cudf.DataFrame(distances)) >>> # vehicle 0 serves order 1, vehicle 1 serves order 2, >>> # vehicle 2 serves order 3 >>> d.add_vehicle_order_match(0, cudf.Series([1])) >>> d.add_vehicle_order_match(1, cudf.Series([2])) >>> d.add_vehicle_order_match(2, cudf.Series([3])) >>> cuopt_solution = routing.Solve(d)
- get_break_dimensions()¶
Returns a dictionary containing break earliest, latest, duration under demand name.
- get_break_locations()¶
Returns break locations as cudf.Series with int type.
- get_capacity_dimensions()¶
Returns a dictionary containing demands and capacity under demand name.
- get_cost_matrix(vehicle_type=0)¶
Returns cost matrix as 2D DeviceNDArray in row major format.
- get_drop_return_trips()¶
Returns drop return trips as cudf.Series with bool type.
- get_fleet_size()¶
Returns the number of vehicles in the fleet.
- get_initial_solutions()¶
Returns initial solutions that’s set, else it will return empty dictionary.
- get_max_lateness_per_vehicle()¶
Returns max lateness per route.
- get_max_slack_per_vehicle()¶
Returns max slack time set.
- get_min_vehicles()¶
Returns minimum vehicles set.
- get_num_locations()¶
Returns the number of locations (vehicle start/end locations + task locations).
- get_num_orders()¶
Return number of orders.
- get_objective_function()¶
Returns objectives as cudf.Series with int type and weights as cudf.Series with float type.
- get_order_locations()¶
Returns order locations as cudf.Series with int type.
- get_order_precedence()¶
Returns a list which contains tuples of node and precedence.
- get_order_priorities()¶
Returns order priorities as cudf.Series with uint8 type
- get_order_time_windows()¶
Returns earliest, latest and service time windows as cudf.Series with int type.
- get_order_vehicle_match()¶
Returns a dictionary containing the vehicles that can fulfill specified orders
- get_pickup_delivery_pairs()¶
Returns pick up and delivery order indices as cudf.Series with int type.
- get_skip_first_trips()¶
Returns skip first trips as cudf.Series with bool type.
- get_transit_time_matrices()¶
Returns all transit time matrices as 2D DeviceNDArray in row major format as dictionary with vehicle types as keys.
- get_transit_time_matrix(vehicle_type=0)¶
Returns transit time matrix as 2D DeviceNDArray in row major format.
- get_vehicle_locations()¶
Returns start and return locations as cudf.Series with int type.
- get_vehicle_max_costs()¶
Returns max costs per vehicles
- get_vehicle_order_match()¶
Returns a dictionary containing the orders that can be fulfilled for specified vehicles
- get_vehicle_priorities()¶
Returns priorities of vehicles in the fleet as cudf.Series with int type.
- get_vehicle_time_windows()¶
Returns earliest and latest time windows as cudf.Series with int type.
- get_vehicle_types()¶
Returns types of vehicles in the fleet as cudf.Series with uint8 type
- set_break_locations(break_locations)¶
The vehicle is allowed to stop at specific locations during a break. It can be at a customer node or another location representing for instance a gas station. The solver will pick the best stop out of all break nodes. The same break node can appear on several routes and satisfy multiple break constraints.
Note: If the break locations are not set, every location can be used as a break location
- Parameters
- break_locations: cudf.Series
representing the designated locations that can be used for breaks. The break locations should be numbered in between 0 and nlocations - 1.
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> cost_mat = [ ... [0, 1, 5, 2], ... [2, 0, 7, 4], ... [1, 5, 0, 9], ... [5, 6, 2, 0] ... ] >>> cost_mat = cudf.DataFrame(cost_mat) >>> cost_mat 0 1 2 3 0 0 1 5 2 1 2 0 7 4 2 1 5 0 9 3 5 6 2 0 >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.add_cost_matrix(cost_mat) >>> data_model.set_break_locations(cudf.Series([1, 3]))
- set_drop_return_trips(set_drop_return_trips)¶
Control if individual vehicles in the fleet return to the end location after the last stop.
End location is where vehicles will return after completing all the tasks assigned.
- Parameters
- set_drop_return_tripscudf.Series
Set True to the drop return trip to end location for each vehicle.
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [ 0, 1] >>> drop_return = [True, False] # Drop the return for the first vehicle >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.set_drop_return_trips(cudf.Series(drop_return))
- set_max_lateness_per_vehicle(max_lateness_per_vehicle)¶
In soft time windows scope, only an excess on demand or max slack check will load a new vehicle. To force new routes to be created the user can set a limit on the lateness allowed on a route. By default routes are allowed infinite lateness.
- Parameters
- max_lateness_per_vehicleFloat
Upper bound for max lateness cumulated on a route
Examples
>>> from cuopt import routing >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.set_max_lateness_per_vehicle(12.7)
- set_max_slack_per_vehicle(slack_max)¶
Budget to let vehicles wait at locations up to the specified time. By default vehicles can wait an infinite amount of time.
- Parameters
- slack_maxInteger
upper bound for wait time per location (including depot). Should be the same unit as the time windows.
Examples
>>> from cuopt import routing >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.set_max_slack_per_vehicle(1)
- set_min_vehicles(min_vehicles)¶
Request a minimum number of vehicles to be used for routing. Note: The resulting solution may not be optimal.
- Parameters
- min_vehiclesInteger
The minimum number of vehicle to use.
Examples
>>> from cuopt import routing >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> # Set minimum vehicles that needs to be used to find the solution >>> data_model.set_min_vehicles(data_model)
- set_objective_function(objectives, objective_weights)¶
During improvement phase the solver only optimizes for the cost. This function is used to select the best solution across all climbers based on other criterias (see Objective enum). The objective function can be defined as a linear combination of the different objectives. By default the solver optimizes for vehicle count first and cost second with weights INT_MAX and 1.
- Parameters
- objectivescudf.Series
Series of Objective criterias
- objective_weightscudf.Series
Series to the weighs associated with the objectives. Series will be cast to float32.
Examples
>>> from cuopt import routing >>> d = routing.DataModel(nodes, vehicle_num) >>> d.set_objective_function( >>> cudf.Series([routing.Objective.VEHICLE, routing.Objective.COST]), >>> cudf.Series([2**32, 1]))
- set_order_locations(order_locations)¶
Set a location for each order.
This allows the cases with multiple orders per locations run efficiently. Consider an example with 4 locations and 10 orders serving to these 4 locations the order_locations series can look like: [0, 2, 3, 1, 3, 1, 2, 1, 3, 2]. In this case, the ith entry in the series represents the location id of the ith order. Using this, the distance matrix is represented as size 4x4 instead of 10x10.
- Note:
0th order should be visiting 0th location. This will be ignored, but it is required.
- Parameters
- order_locationscudf.Series
cudf.Series representing location id of each order given as positive integers
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> orders = [0, 2, 3, 1, 3, 1, 2, 1, 3, 2] >>> data_model = routing.DataModel( ... len(locations), ... len(vehicles), ... len(orders) ... ) >>> data_model.set_order_locations(cudf.Series(orders))
- set_order_priorities(priorities)¶
Set priorities for orders
Higher priority orders (lower numerical value) will be routed before the lower priority orders. The solver always fulfills all the orders when it is successful, otherwise the solver returns a failure. However, when there are not enough resources/vehicles to fulfill all orders, one can use additional (or dummy) vehicles to get a feasible solution from the solver and discard all the orders fulfilled by these vehicles. In that context, using this feature allows to fulfill orders with high priority by active vehicles in the fleet first.
These priorities act only as soft constraints for the solver, similar to vehicle priorities. When high priority orders cannot be fulfilled by a vehicle because of other constraints, the solver will chooses lower priority vehicles.
- Parameters
- prioritiescudf.Series
cudf.Series containing integer priority for each order including the depot (if depot is included in the order list). Order is implicit and should be consitent with the data model. Size of this series must be equal to num_orders in data model, the entries of this should not be more than 256
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> priorities = [0, 1, 0, 1] # Higher the value lesser the priority >>> data_model.set_order_priorities(cudf.Series(priorities))
- set_order_time_windows(earliest, latest, service, penalties=None)¶
Add order time windows to model the Vehicle Routing Problem with Time Windows (VRPTW)
The locations have time windows within which the visits must be made. If transit time matrix has been set using add_transit_time_matrix, then that will be used to validate time windows, else primary matrix is used.
- Note:
The values provided are considered as units and it is user’s responsibility to ensure all time related entries are normalized to one common unit (hours/minutes/seconds/any).
If vehicle locations is not set, then by default 0th index in all columns are considered start and end location for all vehicles. So may be you need to provide big time window for completion of all jobs/depot time window with may be with service time to be 0.
- Parameters
- earliestcudf.Series
cudf.Series containing the earliest visit time for each location including the depot. Order is implicit and should be consitent with the data model.
- latestcudf.Series
cudf.Series containing the latest visit time for each location including the depot. Order is implicit and should be consitent with the data model.
- servicecudf.Series
cudf.Series containing the duration of the visit for each location including the depot. Order is implicit and should be consitent with the data model.
- penaltiescudf.Series
cudf.Series containing the penalty of each location allowing to model node priority. Order is implicit and should be consitent with the data model.
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> cost_mat = [ ... [0, 1, 5, 2], ... [2, 0, 7, 4], ... [1, 5, 0, 9], ... [5, 6, 2, 0] ... ] >>> cost_mat = cudf.DataFrame(cost_mat) >>> cost_mat 0 1 2 3 0 0 1 5 2 1 2 0 7 4 2 1 5 0 9 3 5 6 2 0 >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.add_cost_matrix(cost_mat) >>> time_mat = [ ... [0, 10, 50, 20], ... [20, 0, 70, 40], ... [10, 50, 0, 90], ... [50, 60, 20, 0] ... ] >>> time_mat = cudf.DataFrame(time_mat) >>> data_model.add_transit_time_matrix(time_mat) >>> earliest = [ 0, 15, 60, 0] # earliest a job can be started >>> latest = [500, 180, 150, 180] # latest a job can be started >>> service = [ 0, 10, 20, 30] # time required to service the jobs >>> penality = [ 0, 20, 10, 70] >>> data_model.set_order_time_windows( ... cudf.Series(earliest), ... cudf.Series(latest), ... cudf.Series(service) ... )
- set_pickup_delivery_pairs(pickup_indices, delivery_indices)¶
Set pick-up delivery pairs given by indices to the orders.
Currently mixed pickup and delivery is not supported, meaning that all the orders should be a included in the pick-up delivery pair indices apart from 0th order.
- Parameters
- pickup_indicescudf.Series
int cudf.Series representing the indices of pickup orders.
- delivery_indicescudf.Series
int cudf.Series representing the indices of delivery orders.
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3, 4] >>> vehicles = [0, 1] >>> order_locations = [2, 1, 3, 4, 1, 4] >>> pickup_indices = [0, 2, 4] >>> delivery_indices = [1, 3, 5] # 2 -> 1, 3 -> 4 and 1->4 >>> data_model = routing.DataModel( ... len(locations), ... len(vehicles), ... ) >>> data_model.set_order_locations(order_locations) >>> data_model.set_pickup_delivery_pairs( ... cudf.Series(pickup_indices), ... cudf.Series(delivery_indices) ... )
- set_skip_first_trips(set_skip_first_trips)¶
Skips/neglects cost of travel to first task location, implicitly skipping the travel to location.
- Parameters
- set_skip_first_tripscudf.Series
Set True to skip the trip cost to first task location.
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [ 0, 1] >>> skip_first_trip = [False, True] >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.set_skip_first_trips(cudf.Series(skip_first_trip))
- set_vehicle_locations(start_locations, return_locations)¶
Set start and return locations for vehicles in the fleet.
The start location is a point of start for that vehicle, and return location is designated return location for that vehicle. These can be depot, home or any other locations. The size of these arrays must be equal to fleet_size. When these arrays are not set, all the vehicles in the fleet are assumed to be starting from and returning to depot location, which is zero indexed location.
- Parameters
- start_locationscudf.Series
cudf.Series representing starting locations of vehicles
- return_locationscudf.Series
cudf.Series representing return locations of vehicles
Examples
>>> from cuopt import routing >>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> vehicle_start_location = [0, 0] >>> vehicle_end_location = [2, 3] >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.set_vehicle_locations( ... cudf.Series(vehicle_start_location), ... cudf.Series(vehicle_end_location) ... )
- set_vehicle_max_costs(vehicle_max_costs)¶
Limits per vehicle primary matrix cost accumulated along a route.
- Parameters
- vehicle_max_costscudf.Series float32
Upper bound per vehicle for max distance cumulated on a route
Examples
>>> from cuopt import routing >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> vehicle_max_costs = [150, 200] >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.set_vehicle_max_costs(cudf.Series(vehicle_max_costs))
- set_vehicle_priorities(vehicle_priorities)¶
Set vehicle priorities in the fleet.
Higher priority vehicles will be used before lower priority vehicles, but this is not a hard constraint. 0 is the highest priority and INT_MAX is the lowest priority. The size of this array must be equal to fleet_size. Vehicle priority.
This provides an option to user to prioritize different vehicles as per their pros and cons. The vehicle priorities are a hint to the solver but the main goal is to minimize the number of vehicles. So sometimes the priorities might get neglected.
- Parameters
- vehicle_prioritiescudf.Series
cudf.Series representing priorities of vehicles in the fleet given as positive integers.
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> vehicle_priority = [1, 0] # Higher the value lesser the priority >>> data_model = routing.DataModel( ... len(locations), ... len(vehicles), ... ) >>> data_model.set_vehicle_priorities(cudf.Series(vehicle_priority))
- set_vehicle_time_windows(earliest_time, latest_time)¶
Set vehicle time windows in the fleet.
The earliest time is the time vehicle can leave the starting location. The latest time is the time vehicle must be free. In case of drop_return_trip, latest time specifies the service end time with the last customer. The size of this array must be equal to fleet_size.
Note: The values provided are considered as units and it is user’s responsibility to ensure all time related entries are normalized to one common unit (hours/minutes/seconds/any).
This would help users to solve for routes which consider vehicle availability time window for each vehicle. If secondary matrix has been set using add_transit_time_matrix, then that will be used for time validation, else primary matrix is used.
- Parameters
- earliest_timecudf.Series
cudf.Series representing earliest available times of vehicles
- latest_timecudf.Series
cudf.Series representing latest time vehicle must be free.
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> cost_mat = [ ... [0, 1, 5, 2], ... [2, 0, 7, 4], ... [1, 5, 0, 9], ... [5, 6, 2, 0] ... ] >>> cost_mat = cudf.DataFrame(cost_mat) >>> cost_mat 0 1 2 3 0 0 1 5 2 1 2 0 7 4 2 1 5 0 9 3 5 6 2 0 >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.add_cost_matrix(cost_mat) >>> time_mat = [ ... [0, 10, 50, 20], ... [20, 0, 70, 40], ... [10, 50, 0, 90], ... [50, 60, 20, 0] ... ] >>> time_mat = cudf.DataFrame(time_mat) >>> data_model.add_transit_time_matrix(time_mat) >>> veh_earliest = [ 0, 20] # earliest a vehicle/tech start >>> veh_latest = [200, 180] # end of the vehicle/tech shift >>> data_model.set_vehicle_time_windows( ... cudf.Series(veh_earliest), ... cudf.Series(veh_latest), ... )
- set_vehicle_types(vehicle_types)¶
Set vehicle types in the fleet.
When multiple matrices are given as input the solver is enabling heterogenous cost matrix and time matrix optimization. We thus need the corresponding vehicle type id for all vehicles in the data model.
- Parameters
- vehicle_typescudf.Series
cudf.Series representing types of vehicles in the fleet given as positive integers.
Examples
>>> from cuopt import routing >>> import cudf >>> locations = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> vehicles = [0, 1, 2, 3, 4] >>> vehicle_tpes = [0, 1, 1, 0, 0] # 0 - Car 1 - bike >>> vehicle_priority = [1, 0] # Higher the value lesser the priority >>> data_model = routing.DataModel( ... len(locations), ... len(vehicles), ... ) >>> data_model.set_vehicle_types(cudf.Series(vehicle_types))
Solver Settings¶
- class cuopt.routing.InitialStrategy(value)¶
Options for Initial Strategy
INSERTION - Iteratively build a solution by inserting the cheapest node at its cheapest position
SAVINGS - Savings algorithm (Clarke & Wright) (Not maintained)
- INSERTION = 0¶
- SAVINGS = 1¶
- class cuopt.routing.SolutionStrategy(value)¶
Options for Solution Strategy
- HILL_CLIMBING = 0¶
- TABU_SEARCH = 1¶
- TABU_GLS = 2¶
- NONE = 3¶
- class cuopt.routing.Scope(value)¶
Option to configure scope of the solution
FEASIBLE - Find a solution if possible without any penalty
SOFT_TW - minimizes for cost + lateness at the beginning of solve even if the solution is feasible with hard time windows.
- FEASIBLE = 0¶
- SOFT_TW = 1¶
- class cuopt.routing.SolverSettings¶
Initialize a SolverSettings from a Data Model.
Methods
dump_best_results
(file_path, interval)Dump best results in a given file as csv, reports in given intervals.
dump_config_file
(file_name)Dump configuration information in a given file as yaml
Returns file path where result will be stored, if not set, it will return None.
Returns interval set, if not set, it will return None
Returns the full abs path of the file including the filename where the configuration data will be dumped if not set, it will return None
Returns initial solution strategy.
Returns number of climbers set.
Returns the number of improvement phase iterations set.
Returns solutions scope set.
Returns solution strategy.
Returns solving time set.
set_error_logging_mode
(logging)Displaying constraint error information during the solver execution.
Set a solution strategy for improvement phase.
set_number_of_climbers
(n_climbers)Set the number of climbers for the local search optimization.
set_number_of_iterations
(iterations)Set a fixed number of iterations for the improvement phase.
set_solution_scope
(scope)Restricts/expands the solver to feasible/unfeasible regions.
set_solution_strategy
(solution_strategy)Set a solution strategy for improvement phase.
set_time_limit
(seconds)Set a fixed solving time in seconds, the timer starts when Solve is called.
set_verbose_mode
(verbose)Displaying internal information during the solver execution.
- set_time_limit(seconds)¶
Set a fixed solving time in seconds, the timer starts when Solve is called.
Accuracy may be impacted. Problem under 100 locations may be solved with reasonable accuracy under a second. Larger problems may need a few minutes. A generous upper bond is to set the number of seconds to num_locations. By default it is set to num_locations/5 by considering n_climbers vs run-time tradeoff. If increased accuracy is desired, this needs to set to higher numbers.
- Parameters
- secondsFloat
The number of seconds
Examples
>>> from cuopt import routing >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> data_model = routing.DataModel(len(locations), len(vehicles)) ........... >>> solver = routing.SolverSettings() >>> solver.set_time_limit(0.1)
- set_number_of_iterations(iterations)¶
Set a fixed number of iterations for the improvement phase. Note that time limit overrides the number of iterations set if combined.
- Parameters
- iterationsInteger
The number of iterations
Examples
>>> from cuopt import routing >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> data_model = routing.DataModel(len(locations), len(vehicles)) ........... >>> solver = routing.SolverSettings() >>> solver.set_number_of_iterations(128)
- set_number_of_climbers(n_climbers)¶
Set the number of climbers for the local search optimization.
Number of climbers are number of instances trying to find solutions, which start at different initial status.
Number of climbers should be chosen with regards to chosen run-time. As number of climbers increase, there is more probability of getting better results in long run. However, if it is desired to have good results in a short time, lower number of climbers is better. By default, the number of climbers is chosen by considering occupancy of a small GPU and experimented run-time vs number of climbers trade-off (i.e. the best result in shortest time).
- Parameters
- restart_limitInteger
The number of climbers
Examples
>>> from cuopt import routing >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> data_model = routing.DataModel(len(locations), len(vehicles)) ........... >>> solver = routing.SolverSettings() >>> solver.set_number_of_climbers(1024)
- set_verbose_mode(verbose)¶
Displaying internal information during the solver execution.
- Parameters
- verbosebool
Set True to display information. Execution time may be impacted.
- set_error_logging_mode(logging)¶
Displaying constraint error information during the solver execution.
- Parameters
- loggingbool
Set True to display information. Execution time may be impacted.
- set_solution_scope(scope)¶
Restricts/expands the solver to feasible/unfeasible regions.
Setting the scope to FEASIBLE will fail as early as possible during execution if the solution is unfeasible. Setting the scope to SOFT_TW will expand the search to unfeasible regions.
Currently the SOFT_TW scope only relaxes the latest time. The solution can still be unfeasible due to demand and slack time constraints.
- Parameters
- scopeScope
Type of scope.
Examples
>>> from cuopt import routing >>> import cudf >>> cost_matrix = [ ... [0, 1, 2], ... [1, 0, 2], ... [3, 1, 0] ... ] >>> cost_matrix = cudf.DataFrame(cost_matrix) >>> # Jobs Depot A B >>> job_earliest_time = cudf.Series([ 0, 1, 1]) >>> job_latest_time = cudf.Series([20, 4, 4]) >>> job_service_time = cudf.Series([ 0, 4, 4]) >>> job_penalty = cudf.Series([ 0, 5, 6]) >>> # Lets consider single vehicle/tech for simplicity >>> # Vehicle/Techs v0 >>> vehicle_earliest_time = cudf.Series([ 0]) >>> vehicle_latest_time = cudf.Series([15]) >>> data_model = routing.DataModel( ... len(cost_matrix), ... len(vehicle_latest_time) ... ) >>> data_model.add_cost_matrix(cost_matrix) >>> data_model.add_transit_time_matrix(time_matrix) >>> # Lets try with no penalty and soft time window >>> data_model.set_order_time_windows( ... job_earliest_time, ... job_latest_time, ... job_service_time ... ) >>> data_model.set_vehicle_time_windows( ... vehicle_earliest_time, ... vehicle_latest_time ... ) >>> routing.Solve(data_model).get_status() 1 >>> # SolverSettings status is 1, >>> # means it failed to fulfill the order with >>> # hard constraints. Lets add penalty and soft time window. >>> data_model.set_order_time_windows( ... job_earliest_time, ... job_latest_time, ... job_service_time, ... job_penalty ... ) >>> solver_settings = routing.SolverSettings() >>> solver_settings.set_solution_scope(routing.Scope.SOFT_TW) >>> solution = routing.Solve(data_model, solver_settings) >>> solution.get_route() route arrival_stamp truck_id location 0 0 0.0 0 0 1 2 2.0 0 2 2 1 7.0 0 1 3 0 12.0 0 0 >>> # It can be observed that cost also includes the penalty >>> solution.get_cost() 19.0
- set_solution_strategy(solution_strategy)¶
Set a solution strategy for improvement phase. Available strategies are: HILL_CLIMBING, TABU_SEARCH, TABU_GLS, default is TABU_GLS
HILL_CLIMBING - A type of local search, for more information https://en.wikipedia.org/wiki/Hill_climbing
TABU_SEARCH - This is a metaheuristic search, for more information https://en.wikipedia.org/wiki/Tabu_search
TABU_GLS - TABU Search supported with Guided Local Seearch, for more information https://en.wikipedia.org/wiki/Guided_Local_Search
- Parameters
- solution_strategySolutionStrategy
type of solution strategy
- set_initial_solution_strategy(initial_solution_strategy)¶
Set a solution strategy for improvement phase. Available strategies are: INSERTION default is INSERTION
- Parameters
- initial_solution_strategyInitialStrategy
type of initial solution strategy
- dump_best_results(file_path, interval)¶
Dump best results in a given file as csv, reports in given intervals.
- Parameters
- file_pathAbsolute path of file to be written
- intervalReport intervals in seconds
Examples
>>> from cuopt import routing >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> data_model = routing.DataModel(len(locations), len(vehicles)) ........... >>> solver = routing.SolverSettings() >>> solver.dump_best_results("results.csv", 20)
- dump_config_file(file_name)¶
Dump configuration information in a given file as yaml
- Parameters
- file_nameAbsolute path of file to be written
- get_time_limit()¶
Returns solving time set.
- get_number_of_iterations()¶
Returns the number of improvement phase iterations set.
- get_number_of_climbers()¶
Returns number of climbers set.
- get_solution_scope()¶
Returns solutions scope set.
- get_solution_strategy()¶
Returns solution strategy.
- get_initial_solution_strategy()¶
Returns initial solution strategy.
- get_best_results_file_path()¶
Returns file path where result will be stored, if not set, it will return None.
- get_config_file_name()¶
Returns the full abs path of the file including the filename where the configuration data will be dumped if not set, it will return None
- get_best_results_interval()¶
Returns interval set, if not set, it will return None
Solve¶
- cuopt.routing.Solve(data_model, solver_settings=None)¶
Solves the routing problem.
- Parameters
- data_model: DataModel
data model containing orders, vehicles and constraints.
- solver_settings: SolverSettings
settings to configure solver configurations. By default, it uses default solver settings to solve.
- Returns
- assignmentAssignment
Assignment object containing the solver output.
Assignment¶
- class cuopt.routing.assignment.Assignment(vehicle_count, final_cost, final_objective_value, route_df, status, message, undeliverable_orders)¶
A container of vehicle routing solver output
- Parameters
- vehicle_countInteger
Number of vehicles in the solution
- final_costFloat
Cost calculated as per primary matrix and routes.
- final_objective_valueFloat
Objective value calculated as per objective function and routes.
- route_df: cudf.DataFrame
Contains route, vehicle_id, arrival_stamp.
- status: Integer
Solver status 0 - SUCCESS, 1 - FAIL, 2 - TIMEOUT and 3 - EMPTY.
- message: String
Any error message if there is failure
- undeliverable_orders: cudf.Series
Orders which can not be served, this might have values when drop_infeasible_option is set in SolverSettings
Methods
Display the solution in human readable format.
get_cost
()Returns the cost calculated based on the user provided input and the routes found by the solver.
Returns the infeasible order numbers as cudf.Series.
Returns the final solver message as per SolutionStatus.
Returns the objective value calculated based on the user provided objective function and the routes found by the solver.
Returns the route, truck ids for each stop and the arrival stamp as cudf.DataFrame.
Returns the final solver status as per SolutionStatus.
Returns the number of vehicle needed for this routing assignment.
- display_routes()¶
Display the solution in human readable format. Intended for relatively small inputs.
Examples
>>> import cuopt >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> cost_mat = [ ... [0, 1, 5, 2], ... [2, 0, 7, 4], ... [1, 5, 0, 9], ... [5, 6, 2, 0] ... ] >>> cost_mat = cudf.DataFrame(cost_mat) >>> cost_mat 0 1 2 3 0 0 1 5 2 1 2 0 7 4 2 1 5 0 9 3 5 6 2 0 >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.set_matrix(cost_mat) >>> data_model.set_min_vehicles(len(vehicles)) >>> solver_settings = routing.SolverSettings() >>> solution = routing.Solve(data_model, solver_settings) >>> solution.display_routes() Vehicle-0 starts at: 0.0, completes at: 3.0, travel time: 3.0, Route : 0->1->0 Vehicle-1 starts at: 0.0, completes at: 5.0, travel time: 5.0, Route : 0->3->2->0 This results in a travel time of 8.0 to deliver all routes
- get_cost()¶
Returns the cost calculated based on the user provided input and the routes found by the solver.
- get_infeasible_orders()¶
Returns the infeasible order numbers as cudf.Series.
- get_message()¶
Returns the final solver message as per SolutionStatus.
- get_objective_value()¶
Returns the objective value calculated based on the user provided objective function and the routes found by the solver.
- get_route()¶
Returns the route, truck ids for each stop and the arrival stamp as cudf.DataFrame.
Examples
>>> import cuopt >>> import cudf >>> locations = [0, 1, 2, 3] >>> vehicles = [0, 1] >>> cost_mat = [ ... [0, 1, 5, 2], ... [2, 0, 7, 4], ... [1, 5, 0, 9], ... [5, 6, 2, 0] ... ] >>> cost_mat = cudf.DataFrame(cost_mat) >>> cost_mat 0 1 2 3 0 0 1 5 2 1 2 0 7 4 2 1 5 0 9 3 5 6 2 0 >>> data_model = routing.DataModel(len(locations), len(vehicles)) >>> data_model.set_min_vehicles(len(vehicles)) >>> data_model.set_matrix(cost_mat) >>> solver_settings = routing.SolverSettings() >>> solution = routing.Solve(data_model, solver_settings) >>> solution.get_route() route arrival_stamp truck_id location 0 0 0.0 1 0 1 3 2.0 1 3 2 2 4.0 1 2 3 0 5.0 1 0 4 0 0.0 0 0 5 1 1.0 0 1 6 0 3.0 0 0
- get_status()¶
Returns the final solver status as per SolutionStatus.
- get_vehicle_count()¶
Returns the number of vehicle needed for this routing assignment.
Distance engine¶
Waypoint Matrix¶
- class cuopt.distance_engine.waypoint_matrix.WaypointMatrix(offsets, indices, weights)¶
Initialize a Waypoint Matrix.
- Parameters
- offsetsnumpy.ndarray
numpy.ndarray of size V + 1 (V: number of vertices). It contains the offsets for the vertices in this graph. Offsets must be in the range [0, E] (E: number of edges).
- indicesnumpy.ndarray
numpy.ndarray of size E (E: number of edges). It contains the destination index for each edge. Destination indices must be in the range [0, V) (V: number of vertices).
- weightsnumpy.ndarray
numpy.ndarray of size E (E: number of edges). It contains the weight value for each edge. The expected type is floating point number.
Examples
>>> import cuopt >>> import numpy as np >>> offsets= np.array([0, 3, 5, 7, 8, 9]) >>> edges= np.array([1, 2, 3, 0, 2, 0, 3, 4, 0]) >>> weights= np.array([1, 2, 3, 4, 5, 6, 7, 8, 9]) >>> w_matrix = routing.WaypointMatrix(offsets, edges, weights)
Methods
compute_cost_matrix
(target_locations)Compute the cost matrix over the passed graph and target locations.
Compute a custom matrix over the passed weights and target locations.
compute_waypoint_sequence
(target_locations, ...)Compute the waypoint sequence over the whole route.
- compute_cost_matrix(target_locations)¶
Compute the cost matrix over the passed graph and target locations.
This function can be used when the cost matrix is not acquirable due to an incomplete graph. The cost matrix is computed then returned. It can later be used for the Solver (see DataModel.set_matrix).
- Parameters
- target_locationsnumpy.ndarray
numpy.ndarray representing the target locations indices with respect to the graph. Target locations indices must be in the range [0, V) (V: number of vertices).
- Returns
- cudf.DataFrame
cudf.DataFrame representing the cost matrix
- Raises
- ValueError
Shape of target_locations needs to be of length 1
- ValueError
Target_locations length must be positive
Examples
>>> import cuopt >>> import numpy as np >>> offsets= np.array([0, 3, 5, 7, 8, 9]) >>> edges= np.array([1, 2, 3, 0, 2, 0, 3, 4, 0]) >>> weights= np.array([1, 2, 3, 4, 5, 6, 7, 8, 9]) >>> w_matrix = routing.WaypointMatrix(offsets, edges, weights) >>> target_locations = np.array([1, 3]) >>> cost_matrix = w_matrix.compute_cost_matrix(target_locations) >>> cost_matrix 0 1 0 0.0 7.0 1 18.0 0.0 >>> data_model = routing.DataModel(cost_matrix.shape[0], 2) >>> data_model.set_matrix(cost_matrix)
- compute_waypoint_sequence(target_locations, route_df)¶
Compute the waypoint sequence over the whole route.
The waypoint sequence is an extend version of the route. Between each route target locations, all the intermediate waypoints are added. Waypoints & target locations ids are based on the graph.
A new field is added to route_df to browse through the returned waypoint sequence. The ‘sequence_offset’ field associates an offset to each element in the route.
- Parameters
- target_locationsnumpy.ndarray
numpy.ndarray representing the target locations indices with respect to the graph. Target locations indices must be in the range [0, V) (V: number of vertices).
- route_df: cudf.DataFrame
Contains route, vehicle_id, arrival_stamp, and locations. Contains an extra ‘sequence_offset’ field after this call
- Returns
- cudf.DataFrame
waypoint_sequence cudf.Series representing the waypoint_sequence waypoint_type cudf.Series representing type of waypoint Start - Start location of the vehicle/tech/robot End - End location of the vehicle/tech/robot w - Location passing through to get to delivery location Delivery - Location where delivery needs to be made “-” - Separates vehicle sequence from another
- Raises
- ValueError
Shape of target_locations needs to be of length 1
- ValueError
Target_locations length must be positive
- ValueError
Route length must be positive
Notes
Calling this function before compute_cost_matrix is an error.
Examples
>>> import cuopt >>> import numpy as np >>> offsets= np.array([0, 3, 5, 7, 8, 9]) >>> edges= np.array([1, 2, 3, 0, 2, 0, 3, 4, 0]) >>> weights= np.array([1, 2, 3, 4, 5, 6, 7, 8, 9]) >>> w_matrix = routing.WaypointMatrix(offsets, edges, weights) >>> # Starting node is considered as depot >>> target_locations = np.array([0, 1, 3, 4]) >>> cost_matrix = w_matrix.compute_cost_matrix(target_locations) >>> cost_matrix 0 1 2 3 0 0.0 1.0 3.0 11.0 1 4.0 0.0 7.0 15.0 2 17.0 18.0 0.0 8.0 3 9.0 10.0 12.0 0.0 >>> data_model = routing.DataModel(cost_matrix.shape[0], 2) >>> data_model.set_matrix(cost_matrix) >>> data_model.set_min_vehicles(2) >>> solver_settings = routing.SolverSettings() >>> solution = solver.Solve(data_model, solver_settings) >>> route = solution.get_route() >>> # Location in this routes is actually ids positional indices of >>> # target location >>> route route arrival_stamp truck_id location 0 0 0.0 1 0 1 2 3.0 1 2 2 3 11.0 1 3 3 0 20.0 1 0 4 0 0.0 0 0 5 1 1.0 0 1 6 0 5.0 0 0 >>> # Call to this will also update location in route >>> # with actual target ids along with sequence offset >>> w_matrix.compute_waypoint_sequence(target_locations, route) waypoint_sequence waypoint_type 0 0 Start 1 3 Task 2 3 w 3 4 Task 4 4 w 5 0 End 6 0 - 7 0 Start 8 1 Task 9 1 w 10 0 End >>> # Difference in location and sequence offset in route can be seen >>> route route arrival_stamp truck_id location sequence_offset 0 0 0.0 1 0 0 1 2 3.0 1 3 2 2 3 11.0 1 4 4 3 0 20.0 1 0 6 4 0 0.0 0 0 7 5 1 1.0 0 1 9 6 0 5.0 0 0 11
- compute_shortest_path_costs(target_locations, weights)¶
Compute a custom matrix over the passed weights and target locations.
This is applied on shortest paths found during previous compute_cost_matrix call.
This function allows setting a custom cost between waypoints (for example time) and then getting the total cost it takes to go from one target location to all the others. The shortest paths are not recomputed. The path found from compute_cost_matrix between target locations stays the same but the new weight set is used to compute the output matrix.
- Parameters
- target_locationsnumpy.ndarray
numpy.ndarray representing the target locations indices with respect to the graph. Target locations indices must be in the range [0, V) (V: number of vertices).
- weightsnumpy.ndarray
numpy.ndarray of size E (E: number of edges). It contains the weight value for each edge. The expected type is floating point number.
- Returns
- cudf.DataFrame
cudf.DataFrame representing the custom cost matrix
- Raises
- ValueError
Shape of target_locations needs to be of length 1
- ValueError
Target_locations length must be positive
- ValueError
Shape of weights needs to be of length 1
- ValueError
Weights length must be positive
- ValueError
Weights length must be positive
- ValueError
Given weights and previously set weights length mismatch
Notes
Giving an edge ordering for weights different from the one given during waypoint matrix instanciation will lead to incorrect results.
Examples
>>> import cuopt >>> import numpy as np >>> offsets= np.array([ 0, 3, 5, 7, 8, 9]) >>> edges= np.array([ 1, 2, 3, 0, 2, 0, 3, 4, 0]) >>> weights= np.array([ 1, 2, 3, 4, 5, 6, 7, 8, 9]) >>> time_to_travel = np.array([10, 20, 30, 40, 50, 60, 70, 80, 90]) >>> w_matrix = routing.WaypointMatrix(offsets, edges, weights) >>> target_locations = np.array([1, 3]) >>> cost_matrix = w_matrix.compute_cost_matrix(target_locations) >>> time_matrix = w_matrix.compute_shortest_path_costs( >>> target_locations, time_to_travel >>> ) >>> cost_matrix 0 1 0 0.0 7.0 1 18.0 0.0 >>> time_matrix 0 1 0 0.0 70.0 1 180.0 0.0 >>> data_model = routing.DataModel(cost_matrix.shape[0], 2) >>> data_model.set_matrix(cost_matrix) >>> data_model.add_transit_time_matrix(time_matrix)