关于AMPL实现TSPTW代码的约束及参数疑问咨询

Hey there, let's unpack each of your questions about this TSPTW (Traveling Salesman Problem with Time Windows) AMPL code step by step:

1. Clarification on the rank Matrix #

Your understanding is mostly correct: rank is an n×n binary matrix (where n is the total number of nodes, including the depot) where rank[i,j] = 1 means we select the arc from node i to node j. A quick note: it's not 2×2 unless your problem only has 2 nodes, which is unusual for TSPTW—probably a typo on your end!

2. Constraints 11, 12, 13 #

Let's break these down in the context of TSP modeling:

• Constraint 11 (Single incoming arc per node): This enforces that every node (except possibly the depot, depending on setup) has exactly one predecessor. Mathematically, it's sum{i in V, i != j} rank[i,j] = 1 for all j in V. This is standard for ensuring no node is visited more than once.
• Constraint 12 (Single outgoing arc per node): Similarly, this ensures every node has exactly one successor: sum{j in V, j != i} rank[i,j] = 1 for all i in V. Together with Constraint 11, this forms the basic "tour" structure of TSP.
• Constraint 13 (Arc 0→0 must be selected): This is a bit unusual for standard TSPTW, where we typically model the depot (node 0) with one outgoing arc (starting the tour) and one incoming arc (ending the tour). If rank[0,0] = 1, this implies the tour starts and ends at the depot without visiting any other nodes—unless this is a special case (like a trivial tour when no other nodes need visiting), this might be a mistake in the code, or a specific modeling choice for a variant of TSPTW.

3. Purpose of Constraint 21's Code Snippet #

The line +sum{i in V,j in V:i!=j}(c[i,j])*y[i,k-1,j,k]; is almost certainly part of the objective function (minimizing total travel cost) rather than a constraint. Here's what it does:

• c[i,j] is the cost (distance, time, etc.) of traveling from node i to node j.
• y[i,k-1,j,k] is a binary variable that equals 1 if we are at node i in step k-1 of the tour, then move to node j in step k.
• The sum accumulates the total cost of all consecutive moves in the tour, adding up the cost of each arc taken in sequence.

4. Explanation of Constraints 31, 32, 33 #

Since you didn't share the exact code for these, I'll explain the most common TSPTW constraints that fit this numbering—these are critical for enforcing time window rules:

• Constraint 31 (Time continuity): This ensures that if we travel from node i to j, the arrival time at j is at least the departure time from i plus travel time. Mathematically, this looks like:

  t[j] >= t[i] + p[i] + travel_time[i,j] - M*(1 - rank[i,j]) for all i,j in V, i != j;
  

  Here, M is a large constant (big enough to make the constraint irrelevant if rank[i,j] = 0), t[i] is the arrival time at node i, and p[i] is the service time at i.
• Constraint 32 (Early arrival limit): Enforces that we can't arrive at a node before its earliest allowed time window:

  t[i] >= r[i] for all i in V;
  

• Constraint 33 (Late departure limit): Ensures we can't leave a node after its latest allowed time window (arrival time plus service time can't exceed the due time):

  t[i] + p[i] <= d[i] for all i in V;
  

5. Constraints 4 and 5 #

Your description of these constraints seems off compared to standard TSPTW modeling:

• *Constraint 4 ("Must arrive after sum{j in V}(r[j]rank[j,k])"): This would imply arrival time at k depends on the earliest time window of its predecessor j, which doesn't make sense—time windows are per-node, so you should enforce t[k] >= r[k] (arrive no earlier than node k's own earliest time). The sum sum{j} r[j]*rank[j,k] just picks out r[j] where j is k's predecessor (since only one rank[j,k] is 1), but this doesn't align with standard time window rules.
• *Constraint 5 ("Can't leave before sum{j in V}(d[j]rank[j,k])"): Similarly, this would tie departure time from k to the predecessor j's due time, which is incorrect. The correct constraint is t[k] + p[k] <= d[k]—you can't leave k later than its own latest allowed time.

6. Parameter Definition Question #

You're right to question this! The definitions you listed are misleading:

• r should almost always be the earliest allowed arrival time (release time) for node i, not the "arrival time" (arrival time is a decision variable, usually t[i]).
• d should be the latest allowed departure time (due time) for node i, not the "leave node time" (leave time is t[i] + p[i], a derived value from arrival time and service time).
• p is correctly defined as the service/stop duration at node i.

If the code defines r as arrival time and d as leave time, that's a confusing choice—those should be decision variables, not parameters. The parameters should represent the fixed time window bounds for each node.

内容的提问来源于stack exchange，提问作者Joe Banban