Resource Constrained Shortest Path with PathModel

This example uses PathModel to solve a resource-constrained shortest path problem with time windows, capacity, and NG-set (neighbourhood) constraints. PathModel returns solutions as lists of edge IDs.

Find the shortest simple path from vertex 0 to vertex 5 in a network where paths must respect time windows at each vertex, a cumulative capacity bound, and NG-set neighbourhood constraints that strengthen the simple path requirement.

import flowty


def rcspp():
    #        1 ---3--- 3
    #       / \       / \
    #      2   1     2   4
    #     /     \   /     \
    #    0 --5-- 2 --4--- 4
    #                     |
    #                     3
    #                     |
    #                     5
    edges = [
        (0, 1), (0, 2),  # from 0
        (1, 2), (1, 3),  # from 1
        (2, 3), (2, 4),  # from 2
        (3, 4),           # from 3
        (4, 5),           # from 4
    ]
    costs = [2.0, 5.0, 1.0, 3.0, 2.0, 4.0, 4.0, 3.0]

    # time window resource: edge travel times + per-vertex [earliest, latest]
    travel   = [2, 3, 1, 2, 2, 4, 3, 2]
    earliest = [0, 1, 1, 2, 3, 0]
    latest   = [0, 5, 6, 8, 9, 12]
    time = ({"E": [travel], "V": [earliest, latest]}, "time")

    # capacity resource: per-edge consumption with global bound
    weight = [1, 2, 1, 1, 1, 2, 1, 1]
    cap = 4
    capacity = ({"E": [weight], "G": [cap]}, "load")

    # NG-set neighbourhoods: vertices that are "near" each other
    # strengthens the simple path enforcement
    NG = [
        [1, 2],     # vertex 0 neighbours
        [0, 2, 3],  # vertex 1 neighbours
        [0, 1, 3],  # vertex 2 neighbours
        [1, 2, 4],  # vertex 3 neighbours
        [3, 5],     # vertex 4 neighbours
        [4],        # vertex 5 neighbours
    ]

    model = flowty.PathModel()

    timeRule = "Window", ["time"]
    loadRule = "Capacity", ["load"]

    graph = model.addGraph(
        edges=edges,
        edgeCosts=costs,
        resources=[time, capacity],
        pathSense="S",
        neighbourhoods=NG,
    )
    model.addSubproblem(
        graph, 0, 5, 0.0, 1.0, 1.0, "B",
        rules=[timeRule, loadRule],
    )

    status = model.solve()
    solution = model.getPathSolution()
    if solution:
        print(f"Cost: {solution.cost}")
        for path in solution.paths:
            print(f"Path (edge IDs): {path}")


if __name__ == "__main__":
    rcspp()

Without capacity constraints, the shortest path 0->1->2->4->5 costs 10 but exceeds the capacity bound of 4 (total weight 5). The solver finds the best feasible path 0->1->3->4->5 with cost 12, respecting all time windows, capacity, and NG-set constraints.