Vehicle Routing Data Construction and Result with Cost/Time Matrix#
import json
Accumulate Problem Data#
json_data = {}
Set Cost/Travel Time Matrix
We need to provide square matrices for cost/time matrices which have positive float values.
Cost matrices act as a cost of travel between one location to another. This cost can be accumulated over the result to find the best possible solution. By default, this cost is accumulated, and it can be disabled with the objective value set to 0.
The travel time matrix is used to evaluate time window constraints for vehicles and tasks. So if any kind of time related constraint is used, the Time Matrix is a must-have.
Multiple cost and travel time matrices can be provided for different vehicle types when cost and time differ between types (For example, CAR and BIKE).
# Considering cost is half of travel time
# Car
car_cost_matrix = [
[0, 5, 4, 3, 5],
[5, 0, 6, 4, 3],
[4, 8, 0, 4, 2],
[1, 4, 3, 0, 4],
[3, 3, 5, 6, 0],
]
car_time_matrix = [
[ 0, 10, 8, 6, 10],
[10, 0, 12, 8, 6],
[ 8, 16, 0, 8, 4],
[ 2, 8, 6, 0, 8],
[ 6, 6, 10, 12, 0],
]
# 1 represents car type and 2 represents bike type
# Add cost matrix
json_data["cost_matrix_data"] = {
"data" : {
1:car_cost_matrix
}
}
# Add time matrix
json_data["travel_time_matrix_data"] = {
"data" : {
1:car_time_matrix
}
}
Set Fleet Data
Provide vehicle start and end locations along with vehicle features and capacity.
fleet_data = {
"vehicle_locations": [[0, 0], [0, 0], [0, 0], [0, 0], [0, 0]],
"vehicle_ids": ["Car-A", "Car-B", "Car-C", "Car-D", "Car-E"],
"vehicle_types": [1, 1, 1, 1, 1],
"capacities": [[75, 75, 75, 75, 75]],
"vehicle_time_windows": [
[0, 100],
[0, 100],
[0, 100],
[0, 100],
[0, 100]
],
# Vehicle can take breaks in this time window as per break duration provided
"vehicle_break_time_windows":[
[
[20, 25],
[20, 25],
[20, 25],
[20, 25],
[20, 25]
]
],
"vehicle_break_durations": [[1, 1, 1, 1, 1]],
# Maximum cost a vehicle can incur while delivering
"vehicle_max_costs": [100, 100, 100, 100, 100],
# Maximum time a vehicle can be working
"vehicle_max_times": [120, 120, 120, 120, 120]
}
json_data["fleet_data"] = fleet_data
Set Task Data
Provide details on task locations, demand, and time window; there are other options as well.
task_data = {
"task_locations": [1, 2, 3, 4],
"demand": [[30, 40, 40, 30]],
"task_time_windows": [
[3, 20],
[5, 30],
[1, 20],
[4, 40],
],
"service_times": [3, 1, 8, 4],
"prizes": [50, 50, 100, 50]
}
json_data["task_data"] = task_data
Set Solver Config
Larger problems might require more time.
solver_config = {
"objectives": {
"cost": 1,
"travel_time": 1,
"prize": 2
}
}
json_data["solver_config"] = solver_config
Solve the Problem#
For managed service, cuOpt endpoints can be triggered as shown in the thin client example for managed service.
For self-hosted, cuOpt endpoints can be triggered as shown in the thin client example for self-hosted.
Use this data and invoke cuOpt endpoint, which would return routes.
If the response status is 0,
then cuOpt found a feasible solution, under dictionary
solver_response
.
if status is 1,
then it found an infeasible solution by going over constraints. Warnings
will list what constraints caused the infeasible solution, which can be
analyzed further. Any other state indicating that cuOpt failed may be
due to invalid data or some unhandled issue. This will be under
dictionary solver_infeasible_response
.
Following example is using locally hosted server,
from cuopt_sh_client import CuOptServiceSelfHostClient
import json
# If cuOpt is not running on localhost:5000, edit ip and port parameters
cuopt_service_client = CuOptServiceSelfHostClient(
ip="localhost",
port=5000
)
optimized_routes = cuopt_service_client.get_optimized_routes(json_data)
print(json.dumps(optimized_routes, indent=4))
{
"response": {
"solver_response": {
"status": 0,
"num_vehicles": 2,
"solution_cost": -407.0,
"objective_values": {"cost": 25.0, "travel_time": 68.0, "prize": -250.0},
"vehicle_data": {
"Car-A": {
"task_id": ["Depot", "2", "Break", "3", "Depot"],
"arrival_stamp": [6.0, 12.0, 20.0, 29.0, 39.0],
"route": [0, 3, 3, 4, 0],
"type": ["Depot", "Delivery", "Break", "Delivery", "Depot"]
},
"Car-C": {
"task_id": [ "Depot", "0", "Break", "1", "Depot"],
"arrival_stamp": [0.0, 10.0, 25.0, 26.0, 35.0],
"route": [0, 1, 2, 2, 0],
"type": ["Depot", "Delivery", "Break", "Delivery", "Depot"]
}
},
"dropped_tasks": {
"task_id": [],
"task_index": []
},
"msg": ""
},
"perf_times": null
},
"reqId": "4a60ebbc-f582-4062-8258-43e2bf87a9e0"
}
Solution cost is -407.0
, this is due to objective value being set
for prize, which gets negated from other values.
If the vehicles have non-uniform breaks, how to tackle that?#
# Lets pop uniform breaks added earlier
del fleet_data["vehicle_break_time_windows"]
del fleet_data["vehicle_break_durations"]
Vehicle 2 and 3 requested for 2 additional breaks, lets update breaks as per the request
vehicle_breaks = [
{
"vehicle_id": 0,
"earliest": 20,
"latest": 25,
"duration": 1,
"locations": [0, 1, 2, 3, 4]
},
{
"vehicle_id": 1,
"earliest": 20,
"latest": 25,
"duration": 1,
"locations": [0, 1, 2, 3, 4]
},
{
"vehicle_id": 2,
"earliest": 12,
"latest": 15,
"duration": 1,
"locations": [0, 1, 2, 3, 4]
},
{
"vehicle_id": 2,
"earliest": 20,
"latest": 25,
"duration": 1,
"locations": [0, 1, 2, 3, 4]
},
{
"vehicle_id": 3,
"earliest": 10,
"latest": 14,
"duration": 1,
"locations": [0, 1, 2, 3, 4]
},
{
"vehicle_id": 3,
"earliest": 20,
"latest": 25,
"duration": 1,
"locations": [0, 1, 2, 3, 4]
},
{
"vehicle_id": 4,
"earliest": 20,
"latest": 25,
"duration": 1,
"locations": [0, 1, 2, 3, 4]
},
]
fleet_data["vehicle_breaks"] = vehicle_breaks
Lets test for non-uniform breaks
optimized_routes = cuopt_service_client.get_optimized_routes(json_data)
print(json.dumps(optimized_routes, indent=4))
{
"response": {
"solver_response": {
"status": 0,
"num_vehicles": 2,
"solution_cost": -403.0,
"objective_values": {
"cost": 26.0,
"travel_time": 71.0,
"prize": -250.0
},
"vehicle_data": {
"Car-A": {
"task_id": [
"Depot",
"2",
"Break",
"3",
"Depot"
],
"arrival_stamp": [
6.0,
12.0,
20.0,
29.0,
39.0
],
"type": [
"Depot",
"Delivery",
"Break",
"Delivery",
"Depot"
],
"route": [
0,
3,
3,
4,
0
]
},
"Car-C": {
"task_id": [
"Depot",
"0",
"Break",
"Break",
"1",
"Depot"
],
"arrival_stamp": [
0.0,
10.0,
13.0,
22.0,
29.0,
38.0
],
"type": [
"Depot",
"Delivery",
"Break",
"Break",
"Delivery",
"Depot"
],
"route": [
0,
1,
1,
3,
2,
0
]
}
},
"dropped_tasks": {
"task_id": [],
"task_index": []
}
}
},
"reqId": "925a48cd-ef91-4180-9382-3f1188ef0de0"
}
As you can observe, Car index 2 corresponding to Car-C is getting 2 breaks.