基于成对最廉价路径的双列车无冲突最小总成本/时间规划技术问询

Alright, let's work through how to solve this train routing problem using the paired cheapest paths method—here's a step-by-step breakdown tailored to your constraints.

We have two trains with non-negotiable routing rules:

• Train 1 departs from $A_1$ must stop at $B_1$ en route to its final destination
• Train 2 departs from $A_2$ must stop at $B_2$ en route to its final destination
• Hard constraints: Both trains leave at the same time, and they can never occupy the same track segment at the same moment
• Goal: Minimize the sum of each train's total cost/time (note: cost/time doesn't have to be symmetric between trains or track segments)

The key to handling the collision avoidance constraint is to model the problem using joint states of both trains, rather than treating them as separate entities. This lets us naturally enforce track occupancy rules while searching for the minimal total cost.

What's a Joint State? #

Each state in our search will represent:

• Current position of Train 1

• Current position of Train 2

• Total accumulated cost/time so far

• A flag for whether Train 1 has stopped at $B_1$ yet, and another flag for Train 2 at $B_2$

• Initial State: ($A_1$, $A_2$, 0, B1_not_stopped, B2_not_stopped)

• Termination State: Any state where both trains have reached their final destinations, and both have completed their required stops at $B_1$/$B_2$

We'll adapt Dijkstra's algorithm here (since we're looking for the minimal cost path) to work with our joint state space:

1. Build Your Track Cost/Time Matrix

   • Map every track segment with its cost/time for each direction (since costs don't have to be symmetric)
   • Note which segments are shared between the two trains' possible routes—these are the high-risk areas for collisions

2. Initialize Your Priority Queue

   • Use a min-heap (priority queue) sorted by total accumulated cost/time
   • Start by pushing the initial state into the queue, and keep a lookup table to track the minimal cost for each joint state (to avoid redundant processing)

3. Process States in Order of Minimal Cost

   • Pop the state with the lowest total cost from the queue
   • If this state is a termination state (both trains done with stops and at final destinations), you've found your optimal solution—return the total cost
   • Otherwise, generate all valid next states:
     • For each train, consider valid moves: stay at the current position (cost 0, time increments by a small Δt) or move to an adjacent track segment (cost/time as per your matrix)
     • Critical Constraint Check: Reject any move where both trains would occupy the same track segment at the same time (this includes head-on travel on a single segment, or both entering the same segment simultaneously)
     • Don't forget the mandatory stop rule: If Train 1 hasn't stopped at $B_1$ yet, all its moves must lead it toward $B_1$ (or include stopping there next); same for Train 2 and $B_2$
     • Calculate the new total cost for the joint state. If this new cost is lower than any previously recorded cost for that state, update the lookup table and push the state into the queue

4. Prune Redundant States

   • If a joint state's accumulated cost is already higher than the best solution you've found so far, skip processing it entirely—this saves a lot of computation time

• State Compression: Use binary flags for the mandatory stop status (e.g., 00 = neither train has stopped, 01 = Train 2 has stopped, 10 = Train 1 has stopped, 11 = both have stopped) to reduce the number of unique states you need to track
• Prioritize Mandatory Stops: Early on in the search, prioritize paths that get each train to their required stop ($B_1$/$B_2$) first—this reduces the number of invalid states later on
• Wait Moves: Don't overlook stationary moves (one train waits while the other clears a shared track)—this is often the cheapest way to avoid collisions without adding excessive cost/time

Suppose the track network looks like this:
$A_1$ ↔ $C$ ↔ $B_1$
$A_2$ ↔ $C$ ↔ $B_2$
Where $C$ is the only shared segment between the two routes.

The optimal solution would involve one train moving through $C$ first while the other waits, then the second train proceeds once the shared segment is clear. The choice of which train goes first depends on which option gives a lower total cost/time sum.

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