时间窗路由中slack_max与CumulVar关系及OR-Tools模型技术问询

1. How CumulVar(node) Relates to slack_max #

Let’s break this down with clear examples and plain language:

First, let’s separate the two constraints you’re working with:

• The node-specific time window set via CumulVar(node).SetRange(time_window[0], time_window[1]) is a hard, non-negotiable rule for that node’s cumulative variable (in your case, arrival time). This means CumulVar(node) must fall exactly within [time_window[0], time_window[1]]—no exceptions, regardless of the slack_max value.
• The slack_max parameter in routing.AddDimension() applies to edges (routes between nodes), not individual nodes. It defines the maximum extra time you can "waste" between two consecutive nodes beyond the minimal travel time specified by your evaluator (e.g., time matrix). For example, if traveling from node A to B takes 10 minutes minimum, slack_max=5 lets you take up to 15 minutes for that leg—this usually represents waiting at node A before departing, rather than taking a slower path.

Now answering your specific sub-questions:

• Is CumulVar=45 acceptable with time window (50,60) and slack_max=5? No, absolutely not. The SetRange(50,60) constraint locks CumulVar(node) to that interval—slack doesn’t override this. 45 falls outside the window, so it’s invalid.
• Does slack act on values within the time window? No. Slack only affects the transition between nodes, not the allowed values at the nodes themselves. It gives flexibility in how you reach the node (e.g., arriving later than the earliest possible time via waiting), but once you’re at the node, you still have to be within its time window.
• If slack_max=0, does CumulVar have to be exactly 50 or 60? No. It just means you can’t have any waiting time between nodes—you have to take the minimal travel time between every pair of consecutive nodes. CumulVar(node) can still be any value between 50 and 60, as long as it’s reachable via the minimal travel times from the start node. For example, if the earliest you can reach the node is 55 (via minimal paths), you can arrive at 55, 56, ..., up to 60—you just can’t arrive earlier than 55, and can’t wait longer than needed to stay within the window.

2. Mathematical Model Documentation for OR-Tools Routing #

OR-Tools doesn’t have a single standalone paper dedicated to its routing model, but the official documentation includes detailed breakdowns of the underlying mathematical frameworks, especially for common problems like the Vehicle Routing Problem with Time Windows (VRPTW).

At its core, the routing module builds on classic integer programming and constraint programming models for VRPs. Key components of the model include:

• Binary variables indicating whether a route uses the edge between node i and node j
• Cumulative variables (like arrival time, vehicle load) that track state as the route progresses
• Constraints for flow conservation (each node is visited exactly once, except depots), time window adherence, minimal/maximal travel time between nodes, and vehicle capacity limits.

The OR-Tools team also explains their solver implementations (like CP-SAT and heuristic algorithms) that power the routing module, which align closely with standard academic formulations of VRPs—with optimizations for large-scale problem solving.

内容的提问来源于stack exchange，提问作者Leevi L