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.

VARIANCE_ROUTE_SIZE - Models with respect to dissimilarity of route sizes

It computes the L2 variance (squared) in the number of orders served by each route.

VARIANCE_ROUTE_SERVICE_TIME - Models with respect to disssimilarty of route

service times

It computes L2 variance (squared) of the accumulated service times of of each route

VEHICLE = 0

COST = 1

TRAVEL_TIME = 2

CUMUL_PACKAGE_TIME = 3

CUMUL_EARLIEST_DIFF = 4

VARIANCE_ROUTE_SIZE = 5

VARIANCE_ROUTE_SERVICE_TIME = 6

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.

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
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])	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_mandatory_orders()	Returns ids of mandatory orders
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_penalties()	Returns order penalties 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_service_times([vehicle_id])	Returns a dictionary containing the vehicles and their associated service times
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])	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_max_times()	Returns max times 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.
set_drop_return_trips(set_drop_return_trips)	Control if individual vehicles in the fleet return to the end location after the last stop.
set_mandatory_orders(mandatory_orders)	NOTE: Only applicable with set_drop_infeasible_orders.
set_max_lateness_per_vehicle(...)	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_penalties(penalties)	Set penalties for orders when using soft time window constraints
set_order_priorities(priorities)	Set priorities for orders
set_order_service_times(service_times[, ...])	In fully heterogeneous fleet mode, vehicle can take different amount of times to complete a task based on their profile and the order being served.
set_order_time_windows(earliest, latest)	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_max_times(vehicle_max_times)	Limits per vehicle the time 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 dtype - int32

Earliest time a vehicle can be at a break location.

break_latest: cudf.Series dtype - int32

Latest time a vehicle can be at a break location.

break_service: cudf.Series dtype - int32

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 dtype - int32

cudf.Series containing integer demand value for each locations, including the depot. Order is implicit and should be consistent with the data model.

capacitycudf.Series dtype - int32

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 heterogeneous fleet. It can model traveling distances for different vehicles (bicycles, 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 dtype - float32

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 dtype - int32

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 dtype - int32

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 heterogeneous fleet. It can model traveling speeds for different vehicles (bicycles, 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 dtype - float32

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 dtype - int32

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_mandatory_orders()

Returns ids of mandatory orders

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_penalties()

Returns order penalties 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_service_times(vehicle_id=-1)

Returns a dictionary containing the vehicles and their associated service times

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_max_times()

Returns max times 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 dtype-int32

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 dtype - bool

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_mandatory_orders(mandatory_orders)

NOTE: Only applicable with set_drop_infeasible_orders.

Set order ids as per order locations set in datamodel. These orders are mandatory and can’t be skipped, and would result in infeasible solution if the orders can’t be fulfilled.

Parameters:

mandatory_orderscudf.Series dtype - int32

Order IDs as per order locations set

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 criteria (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 dtype - cuopt.routing.Objective

Series of Objective criteria

objective_weightscudf.Series dtype - float32

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.

Parameters:

order_locationscudf.Series dtype - int32

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_penalties(penalties)

Set penalties for orders when using soft time window constraints

Parameters:

penaltiescudf.Series dtype - int32

cudf.Series containing the penalty of each location allowing to model node priority. Order is implicit and should be consistent 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)
... )
>>> data_model.set_order_service_times(
...   cudf.Sereis(service)
... )
>>> data_model.set_order_penalties(
...   cudf.Series(penalty)
... )

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 dtype - uint8

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 consistent 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_service_times(service_times, vehicle_id=-1)

In fully heterogeneous fleet mode, vehicle can take different amount of times to complete a task based on their profile and the order being served. Here we enable that ability to the user by setting for each vehicle id the corresponding service times. They can be the same for all orders per vehicle/vehicle type or unique.

The service times are defaulted for all vehicles unless vehicle id is specified. If no default service times are given then the solver expects all vehicle ids up to fleet size to be specified.

Parameters:

service_timescudf.Series dtype - int32

service times of size number of orders

vehicle_idint32

Vehicle id

Note: A user can set this multiple times. However, if it is

set more than once for same vehicle, the service times list will be overridden with the most recent function call

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))
>>> # default for all
>>> d.set_order_service_times(cudf.Series([0, 1, 1, 1]))
>>> # override vehicle 1
>>> d.set_order_service_times(cudf.Series([0, 2, 4, 5]), 1)
>>> cuopt_solution = routing.Solve(d)

set_order_time_windows(earliest, latest)

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 dtype - int32

cudf.Series containing the earliest visit time for each location including the depot. Order is implicit and should be consistent with the data model.

latestcudf.Series dtype - int32

cudf.Series containing the latest visit time for each location including the depot. Order is implicit and should be consistent 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
>>> data_model.set_order_time_windows(
...   cudf.Series(earliest),
...   cudf.Series(latest)
... )

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. These indices are indices to order locations set using set_order_locations.

Parameters:

pickup_indicescudf.Series dtype - int32

int cudf.Series representing the indices of pickup orders.

delivery_indicescudf.Series dtype - int32

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 dtype - bool

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 dtype - int32

cudf.Series representing starting locations of vehicles

return_locationscudf.Series dtype - int32

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 dtype - 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_max_times(vehicle_max_times)

Limits per vehicle the time accumulated along a route.

Parameters:

vehicle_max_timescudf.Series dtype - float32

Upper bound per vehicle for max duration cumulated on a route

Examples

>>> from cuopt import routing
>>> locations = [0,  1,  2,  3]
>>> vehicles  = [0, 1]
>>> vehicle_max_times = [150, 200]
>>> data_model = routing.DataModel(len(locations), len(vehicles))
>>> data_model.set_vehicle_max_times(cudf.Series(vehicle_max_times))

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 dtype - int32

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 dtype - int32

cudf.Series representing earliest available times of vehicles

latest_timecudf.Series dtype - int32

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 heterogeneous 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 dtype - uint8

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 for improvement phase.

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

NONE - No improvement phase

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.

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
get_best_results_file_path()	Returns file path where result will be stored, if not set, it will return None.
get_best_results_interval()	Returns interval set, 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_initial_solution_strategy()	Returns initial solution strategy.
get_number_of_climbers()	Returns number of climbers set.
get_number_of_iterations()	Returns the number of improvement phase iterations set.
get_solution_scope()	Returns solutions scope set.
get_solution_strategy()	Returns solution strategy.
get_time_limit()	Returns solving time set.
is_drop_infeasible_orders_enabled()	Returns True/False depending on if its enabled or disabled.
set_drop_infeasible_orders(enable)	Finds a solution by dropping any infeasible orders ensuring a partial solution with partial set of orders.
set_error_logging_mode(logging)	Displaying constraint error information during the solver execution.
set_initial_solution_strategy(...)	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))
...........
>>> settings = routing.SolverSettings()
>>> settings.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))
...........
>>> settings = routing.SolverSettings()
>>> settings.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))
...........
>>> settings = routing.SolverSettings()
>>> settings.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
... )
>>> data_model.set_order_service_times(
...     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
... )
>>> data_model.set_order_service_times(job_service_time)
>>> data_model.set_order_penalties(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

NONE - Without any improvement phase.

Parameters:

solution_strategycuopt.routing.SolutionStrategy

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_strategycuopt.routing.InitialStrategy

type of initial solution strategy

set_drop_infeasible_orders(enable)

Finds a solution by dropping any infeasible orders ensuring a partial solution with partial set of orders.

Parameters:

enablebool

True - enables dropping infeasible orders, by default False.

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))
...........
>>> settings = routing.SolverSettings()
>>> settings.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

is_drop_infeasible_orders_enabled()

Returns True/False depending on if its enabled or disabled.

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_routes()	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.
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.
get_status()	Returns the final solver status as per SolutionStatus.
get_vehicle_count()	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)
>>> solver = cuopt.Solver(data_model)
>>> solver.set_min_vehicles(len(vehicles))
>>> solver.set_min_vehicles(len(vehicles))
>>> solution = solver.solve()
>>> 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_matrix(cost_mat)
>>> solver = cuopt.Solver(data_model)
>>> solver.set_min_vehicles(len(vehicles))
>>> solver.set_min_vehicles(len(vehicles))
>>> solution = solver.solve()
>>> solution.get_route()
>>> 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_shortest_path_costs(...)	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)
>>> solver = cuopt.Solver(data_model)
>>> solver.set_min_vehicles(2)
>>> solution = solver.solve()
>>> 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)