Capacitated Route Feasibility

Problem

Check whether a single vehicle route is feasible for a capacitated problem.

The route must start and end at depot 0, must not repeat customers, and the sum of demands of visited customers must not exceed capacity. demands maps each node to its demand (depot demand is ignored) and route is the ordered node list. Return a boolean.

Hint

Repetition and capacity overload are the two classic infeasibilities.

Test cases

case 1

in: [[0,2,1],3,[0,1,2,0]]

expected: true

case 2

in: [[0,2,2],3,[0,1,2,0]]

expected: false

case 3

in: [[0,1],5,[1,0]]

expected: false

case 4

in: [[0,1,1],5,[0,1,1,0]]

expected: false

case 5

in: [[0],1,[0,0]]

expected: true

Starter codePython

def route_feasible(demands, capacity, route):
    # Your code here
    pass

5 test cases · run your code against them in the editor