Behavior of max duration constraint with CVRPTW

[jvm1]

I experience the following behavior on v0.5.1: when setting the duration property and using time windows, a vehicle can wait upon arrival at a node for an unlimited amount of time without this waiting time being included in the total duration of the route. e.g these arrival times:

{'Source': 0,
 'node1': 45,
 'node2': 97,
 'node3': 10800,
 'Sink': 10895}

yield a route duration of 192.
Is this supposed to happen? It seems rather unintuitive and impractical to me.

[Kuifje02]

Hi ! This seems odd indeed.
Could you provide a complete reproducible example so that we can replicate this on our side and investigate ?

[jvm1]

Hi, this is a simplified example

G = nx.DiGraph()
G.add_nodes_from([
    "Source",
    "Sink",
    ("node01", {'demand': 10, 'lower': 0, 'upper': 10}),
    ("node02", {'demand': 10, 'lower': 0, 'upper': 10}),
    ("node03", {'demand': 10, 'lower': 40, 'upper': 50})
])
G.add_edges_from([
    ("Source", "node01", {'cost': 10, 'time': 10}),
    ("Source", "node02", {'cost': 10, 'time': 10}),
    ("Source", "node03", {'cost': 10, 'time': 10}),
    ("node01", "Sink",   {'cost': 10, 'time': 10}),
    ("node01", "node02", {'cost': 20, 'time': 20}),
    ("node01", "node03", {'cost': 0,  'time': 0}),
    ("node02", "Sink",   {'cost': 10, 'time': 10}),
    ("node02", "node01", {'cost': 20, 'time': 20}),
    ("node02", "node03", {'cost': 10, 'time': 10}),
    ("node03", "Sink",   {'cost': 10, 'time': 10}),
    ("node03", "node01", {'cost': 0,  'time': 0}),
    ("node03", "node02", {'cost': 10, 'time': 10})
])

prob = VehicleRoutingProblem(G, load_capacity=20, duration=40, time_windows=True)
prob.solve()

print(prob.best_routes)
print(prob.arrival_time)
print(prob.best_routes_duration)

Output:

{1: ['Source', 'node02', 'Sink'], 2: ['Source', 'node01', 'node03', 'Sink']}
{1: {'Source': 0, 'node02': 10, 'Sink': 20}, 2: {'Source': 0, 'node01': 10, 'node03': 40, 'Sink': 50}}
{1: 20, 2: 20}

I would expect route 2 to have a duration of 50, and thus be infeasible.

[torressa]

Thanks, can reproduce this with cspy=False too.
It's a bit strange example as basically node03 can't really be in any route: Source->node03->Sink will already have a duration of 50. Maybe we should through an error in the checks and stop as this is infeasible.

[torressa]

This raises an error now with a3578b5