Server Data construction and Result - with waypoint matrix

[1]:
import json

Accumulate problem data

[1]:
json_data = {}

Set waypoint graph


Need to provide offsets, edges, and weights; weights can’t be negative values.

Considering 2 types of vehicle, a Van and a Truck, Van would be faster/costs less in few paths compared to Trucks, which would depict change in weights of the cost of trvael

Similarly travel_time_graph_data can also be set.

[3]:
# Van
graph_data_1 = {
    "offsets": [0,       3,    5,           9,    11,   13,   15,   17, 18, 19, 20, 21],
    "edges":   [1, 2, 9, 0, 7, 0, 3, 4, 10, 2, 4, 2, 5, 6, 9, 5, 8, 1,  6,  0,  5],
    "weights": [1, 1, 2, 1, 2, 1, 1, 1,  3, 2, 3, 2, 1, 2, 1, 3, 4, 2,  3,  1,  1]
}

# Truck
graph_data_2 = graph_data_1.copy()
graph_data_2["weights"] = [2, 2, 3, 2, 3, 2, 2, 2, 4, 4, 4, 3, 2, 3, 2, 4, 5, 3,  4,  2,  1]

json_data["cost_waypoint_graph_data"] = {
    'waypoint_graph': {
        1: graph_data_1, # Van
        2: graph_data_2  # Truck
    }
}

# For simplicity, we are using the same graph data for travel time here.
# In a real use case this would likely be different
json_data["travel_time_waypoint_graph_data"] = {
    'waypoint_graph': {
        1: graph_data_1, # Van
        2: graph_data_2  # Truck
    }
}

Set Fleet data


Provide vehicle start and end locations along with vehicle features and capacity.

[4]:
fleet_data = {
    "vehicle_locations": [[0, 0], [1, 1], [0, 1], [1, 0], [0, 0]],
    "vehicle_ids": ["Van-A", "Truck-A", "Van-B", "Truck-B", "Van-C"],
    "vehicle_types": [1, 2, 1, 2, 1],
    "capacities": [[10, 12, 15, 8, 10]],
    "vehicle_time_windows": [
        [0, 80],
        [1, 40],
        [3, 30],
        [5, 80],
        [20, 100]
    ],
    # Vehicle can take breaks in this time window as per berak duration provided
    "vehicle_break_time_windows":[
        [
            [20, 25],
            [20, 25],
            [20, 25],
            [20, 25],
            [20, 25]
        ]
    ],
    "vehicle_break_durations": [[1, 1, 1, 1, 1]],
    # Vehicle Id 0 can only serve Order 0 and 4
    "vehicle_order_match": [
        {
            "vehicle_id": 0,
            "order_ids": [0, 4]
        }
    ],  # 0th vehicle can only serve 0th and 4th order only
    "priorities": [4, 3, 2, 1, 0],
    # Don't count trip from depot to first task location
    "skip_first_trips": [False, True, True, False, False],
    # Don't count trip from last task location to depot
    "drop_return_trips": [False, True, True, False, False],
    # 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],
    # Minimum 2 vehicles are required to be in solution
    "min_vehicles": 2,
}

json_data["fleet_data"] = fleet_data

Set Task data


Provide details on task locations, demand and time window, there are other options as well.

[5]:
task_data = {
    "task_locations": [1, 3, 4, 6, 8],
    "demand": [[3, 4, 4, 3, 2]],
    "task_time_windows": [
        [3, 20],
        [5, 30],
        [1, 20],
        [4, 40],
        [0, 30],
    ],
    "service_times": [3, 1, 8, 4, 0],
    "priorities": [0, 1, 2, 3, 4],
    # Order Id 0 and 4 can be served only by vehicle with id 0
    "order_vehicle_match": [
        {
            "order_id": 0,
            "vehicle_ids": [0]
        },
        {
            "order_id": 4,
            "vehicle_ids": [0]
        }
    ],
    # If drop infeasible tasks is enabled,
    # then at any cost these tasks needs to be completed, else it will result in
    # infeasible solution
    "mandatory_task_ids": [0, 4]
}

json_data["task_data"] = task_data

Set solver config


larger problems might require more time.

[6]:
solver_config = {
    "time_limit": 1,
    "drop_infeasible_tasks": True
}

json_data["solver_config"] = solver_config

Complete Problem data

[7]:
print(json.dumps(json_data, indent=4))
{
    "cost_waypoint_graph_data": {
        "waypoint_graph": {
            "1": {
                "offsets": [
                    0,
                    3,
                    5,
                    9,
                    11,
                    13,
                    15,
                    17,
                    18,
                    19,
                    20,
                    21
                ],
                "edges": [
                    1,
                    2,
                    9,
                    0,
                    7,
                    0,
                    3,
                    4,
                    10,
                    2,
                    4,
                    2,
                    5,
                    6,
                    9,
                    5,
                    8,
                    1,
                    6,
                    0,
                    5
                ],
                "weights": [
                    1,
                    1,
                    2,
                    1,
                    2,
                    1,
                    1,
                    1,
                    3,
                    2,
                    3,
                    2,
                    1,
                    2,
                    1,
                    3,
                    4,
                    2,
                    3,
                    1,
                    1
                ]
            },
            "2": {
                "offsets": [
                    0,
                    3,
                    5,
                    9,
                    11,
                    13,
                    15,
                    17,
                    18,
                    19,
                    20,
                    21
                ],
                "edges": [
                    1,
                    2,
                    9,
                    0,
                    7,
                    0,
                    3,
                    4,
                    10,
                    2,
                    4,
                    2,
                    5,
                    6,
                    9,
                    5,
                    8,
                    1,
                    6,
                    0,
                    5
                ],
                "weights": [
                    2,
                    2,
                    3,
                    2,
                    3,
                    2,
                    2,
                    2,
                    4,
                    4,
                    4,
                    3,
                    2,
                    3,
                    2,
                    4,
                    5,
                    3,
                    4,
                    2,
                    1
                ]
            }
        }
    },
    "fleet_data": {
        "vehicle_locations": [
            [
                0,
                0
            ],
            [
                1,
                1
            ],
            [
                0,
                1
            ],
            [
                1,
                0
            ],
            [
                0,
                0
            ]
        ],
        "vehicle_ids": [
            "Van-A",
            "Truck-A",
            "Van-B",
            "Truck-B",
            "Van-C"
        ],
        "vehicle_types": [
            1,
            2,
            1,
            2,
            1
        ],
        "capacities": [
            [
                10,
                12,
                15,
                8,
                10
            ]
        ],
        "vehicle_time_windows": [
            [
                0,
                80
            ],
            [
                1,
                40
            ],
            [
                3,
                30
            ],
            [
                5,
                80
            ],
            [
                20,
                100
            ]
        ],
        "vehicle_break_time_windows": [
            [
                [
                    20,
                    25
                ],
                [
                    20,
                    25
                ],
                [
                    20,
                    25
                ],
                [
                    20,
                    25
                ],
                [
                    20,
                    25
                ]
            ]
        ],
        "vehicle_break_durations": [
            [
                1,
                1,
                1,
                1,
                1
            ]
        ],
        "vehicle_order_match": [
            {
                "vehicle_id": 0,
                "order_ids": [
                    0,
                    4
                ]
            }
        ],
        "priorities": [
            4,
            3,
            2,
            1,
            0
        ],
        "skip_first_trips": [
            false,
            true,
            true,
            false,
            false
        ],
        "drop_return_trips": [
            false,
            true,
            true,
            false,
            false
        ],
        "vehicle_max_costs": [
            100,
            100,
            100,
            100,
            100
        ],
        "vehicle_max_times": [
            120,
            120,
            120,
            120,
            120
        ],
        "min_vehicles": 2
    },
    "task_data": {
        "task_locations": [
            1,
            3,
            4,
            6,
            8
        ],
        "demand": [
            [
                3,
                4,
                4,
                3,
                2
            ]
        ],
        "task_time_windows": [
            [
                3,
                20
            ],
            [
                5,
                30
            ],
            [
                1,
                20
            ],
            [
                4,
                40
            ],
            [
                0,
                30
            ]
        ],
        "service_times": [
            3,
            1,
            8,
            4,
            0
        ],
        "priorities": [
            0,
            1,
            2,
            3,
            4
        ],
        "order_vehicle_match": [
            {
                "order_id": 0,
                "vehicle_ids": [
                    0
                ]
            },
            {
                "order_id": 4,
                "vehicle_ids": [
                    0
                ]
            }
        ],
        "mandatory_task_ids": [
            0,
            4
        ]
    },
    "solver_config": {
        "time_limit": 1,
        "drop_infeasible_tasks": true
    }
}

Solve the problem


cuOpt endpoint can be triggered as shown in the thin client example.

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 constarints. Warnings will list what constraints caused infeasible solution which can be analysed more. Any other state means cuOpt failed may be due invalid data or some unhandled issue. This will be under dictionary “solver_infeasible_response”

{
'response':
{
    'solver_response':
    {
        'status': 0,
        'num_vehicles': 4,
        'solution_cost': 24.0,
        'vehicle_data': {
        'Van-A': {
            'task_id': ['Depot', '0', 'Break', '4', 'Depot'],
            'arrival_stamp': [0.0, 3.0, 20.0, 21.0, 29.0],
            'route': [0, 1, 0, 2, 4, 5, 6, 8, 8, 6, 5, 9, 0],
            'type': ['Depot', 'Delivery', 'w', 'w', 'w', 'w', 'w', 'Break', 'Delivery', 'w', 'w', 'w', 'Depot']
        },
        'Van-B': {
            'task_id': ['1', '2', 'Break'],
            'arrival_stamp': [5.0, 9.0, 20.0],
            'route': [3, 4, 4],
            'type': ['Delivery', 'Delivery', 'Break']
        },
        'Truck-A': {
            'task_id': ['Break', '3'],
            'arrival_stamp': [20.0, 21.0],
            'route': [6, 6],
            'type': ['Break', 'Delivery']
         },
    }
}
'warnings': []
}

Warnings, Warnings will be listed as a list in the response such as deprecation or any contstraints causing infeasible results.