Date: Aug-17-2011

1) I have a question on the competition problem. Do we need to control the timing of work events? For example, if block B begins on train T1 and swaps to train T2 at yard Y, then we need to ensure that T1 arrives at Y before T2 departs from Y. For this, can we on the fact that each crew segment requires one work day? If so, how do we control the timing of work events that occur at yards that are in the interior of a crew segment?

You do not have to control the timing of work events. In real world train design, we have to consider the arrival and departure time of the trains for a feasible plan. But to simplify the problem, we have ignored the timing aspect in this competition.

2) I am confused on how the train routing works. What exactly is the criteria by which a train schedule is created? Is the output basically all possible routes given particular parameters and then the train is "created" in the BTA portion of problem?

We do not prescribe how you solve this problem, or in what order you generate the train routes or block-to-train assignments. It is up to the problem participants to determine the best routing for trains and block-to-train assignments given the problem definition. A train can be viewed as consisting of a train route, which is an itinerary of locations through which the train will pass, and a set of block-to-train assignments. Blocks can only be picked up and set off at locations that are in a train route. Since more then one train can be used to move a block, the pickup and setoff locations for a block on a specific train do not have to match the origin or destination locations for the block, though the overall sequence of trains to which the block is assigned must advance the block from its origin to its destination. Train routes must be legal in the sense that they respect the rules related to the crew districts. One can always opt not to move a block by paying a high penalty cost. In summary, the output is to create trains as required and identify their corresponding routes. Given the trains and train routes, identify how a block can travel from its origin to destination.

3) If a train, like the train #1 in for example, pass from the begin a segment to the end, and return by the same segment, This train count like one train passing in the segment or count two times?

In Table 3, it is mentioned that A to B can have a maximum of 3 trains. As all the links are considered symmetrical and bi-directional, B to A has the same attributes as A to B. Hence, 3 trains can travel from B to A and similarly, 3 trains can travel from A to B.

4) Are the Max Train Length (Feet) and the Max Tonnage (tons) for each train on a link or for all the trains on a link?

Maximum Train length and Maximum Tonnage are applicable to individual trains. For example, Max Train Length is 5000 feet and Max Tonnage is 40,000 tons on a link A – B. There can be 5 different trains going from A to B and 3 different trains going from B to A. None of these trains, individually, can exceed 5000 feet and 40,000 tons while traveling on the link A to B or B to A.

5) Some of the references mentioned in the description do not provide OR formulation of the problem, are you specifically looking for OR formulation of the problem or heuristic algorithm? Because the problem is NP-hard and the exact solution for the large size problems can not be obtained through the exact formulation?

We are not expecting one type of solution approach over the other. It is completely up to the participating group to decide their solution approach. Our judging panel would judge the solution quality based on the quality of the final solution and the soundness of the solution approach that can be either an exact method or a heuristic.

6) If a car (block) departs from its origin is it necessary to reach to the destination or it can be left somewhere within the route by assigning the missing car penalty?

If a block departs its origin and arrives at its destination, then a car is covered and not missed. If a block either does not depart from its origin or arrives at its destination, then the block is considered missing and the missing penalty cost is applied.

7) Can the crews switch trains on the middle of a crew segment?

No, the crews cannot switch trains in the middle of the crew segment. If a crew segment is A – B, then a crew can only board a train at A and get of the train at B or board a train at B and get off at A.

8) Can blocks be swapped on nodes that are in the middle of a crew segment?

Blocks can be swapped at any node along the crew segment. For example, A – C is a crew segment. The traveling/expanded route of A – C on the physical network is A – B – C. It means for the train to get from A to C, the train has to travel from A to B and then to C. As A – C is a crew segment, a single crew takes the train from A – B – C. Further, blocks can be swapped at Node B, if necessary.

9) We saw that the first question on the FAQ list says to not include time in our formulation. However this can lead to totally illogical and impossible solutions. For example if we have network that's a 3-clique of A-B-C, and there are blocks that need to go from A to B, A to C, B to C, B to A, C to A, and C to B, then the train could do a single cycle starting at A, and take all blocks from origin to destination. However this would not work in reality because if the train moves from A-B-C-A, then the blocks that need to go from C to B do not get there.

For example, Block1 arrives at node A at 10 AM. Block2 arrives at node A at 12 PM. If both the blocks are assigned to the same train, then that train can only depart after 12 PM. Considering all these timing aspects would complicate the problem further, even though it gets closer to reality. In this competition, we have assumed that irrespective of when the two blocks arrive at node A, both the blocks can be assigned to the same train departing anytime during the day.

In your example, if a train travels from A – B – C - A, then block C to B cannot be transported of the of the six blocks you mentioned. Also, we have to make sure that crew segments are connected all along the train route. Instead, if the train route is A – B – C – A – B, then the block C to B can be transported as well, subject to the connected crew segment requirement.

10) In the example and data files you provide, it seems that there is no information about length of individual trains. I wonder how I can deal with the constraints of train length and total tonnage.

Total Length and Total Tonnage per block is presented in the Input-Blocks spread sheet of the input data file. Different blocks can be assigned to a train and eventually, the length of train is the sum of lengths of blocks. Also, the size of the train decreases when a train stops to set off a block and similarly the length of the train increases when the train picks up a block. As the train is traveling on different links of the network, the maximum size of the train should not exceed the Max Train Length for any of the traveled links.

11) If the train route is A – B – C – A – B, as in one of your answers, (hence implying that the same train can pass more than one time on the same link), in the link A-B the passage of this train counts for one or for two? If the maximum number of trains passing through A - B is one then the above solution is feasible or not, since it is the same train that uses two times the link?

In the example you have provided, the first time the train travels from A to B, it is counted as one. The second time the same train travels from A to B, it is counted as two or second usage of the link A to B.

12) We have a question on the constraint on the maximum number of blocks a train can carry. Let us suppose that the train route is A – B – C – D - B – E. A block, say blk1, has to go from A to E. Another block, say blk2, has to go from C to D. The train cannot carry both the blocks at the same time because of the constraint on the maximum length of a train. The train can pick up the block blk1 in A and download it in B, then the train makes the tour B - C - D - B (moving the other block blk2 from C to D), then the train can pick up again the block blk1 in B and delivery it in E.

How many times do we need to count the block blk1 in the constraint on the maximum number of blocks the train can carry? If the limit for this train is "at most two blocks", the above solution is feasible or not?

First the number of blocks that can be assigned to a train is dependent on the length of each block and the maximum length of a train on each used link of train route.
In practice, if a block is on a train, the block would not be set off at some node for the same train to revisit the node to pick up the same block.
For this competition, we can assume that the unique number of blocks per train has to be nothing more than 8 as given in Table 5. But, such an operation can be considered as a block swap and hence should satisfy the constraint of maximum number of block swaps per block. In addition, as the train stops to perform a work event of picking up the block, maximum number of work events per train and cost per work event comes into picture.

13) We have studied the network data file and found that some part of the network is not connected to other parts. For example, nodes 7542 and 8602 stand alone and the blocks there just cannot go out.

In the given network, there may be situations where some of the blocks cannot be moved. In that case, the model can just pay the penalty cost of missing the block. Also, please note that we have given arcs as A-B and we considered all the arcs to be bi-directional. Hence, A-B represents A-B and B-A with the same attributes of distance, etc.

14) For each crew segment, does the crew have to follow the shortest path? In some cases, there are two paths with the exactly the same distance. Which one should we choose?

The crews have the follow the shortest path along the crew segment. You can pick either one of the routes or even choose both the routes separately for different trains, if necessary to cover different blocks.

15) In the data file, the shortest distance is given for each block. However, we find that there are several cases where the provided shortest distances are not right. For example, Block 119 is from node 10571 to node 410. The two nodes are directly connected with the distance of 133.6 miles. However, the data file lists 160.2 miles as the shortest distance for this block. Should we just ignore the listed shortest distance for each block?

You are correct and thank you for pointing that out. If you find a different shortest distance on a block, please use the shortest one.

16) We find several interesting cases in which three nodes are connected to each other. We understand the distances do not necessarily follow the triangular property. However, the distance of A-C is exactly the summation of A-B and B-C. Does it mean B is in the middle of A-C? Can a train goes from A to C without passing B? This kind of situation happens pretty often. For example, the three nodes could be 3683, 2544, and 6425.

Yes, you may see situations where the distance of A-C is the sum of A-B and B-C. In that case, B is somewhere along the route of A-C. You can create a train from A to C and the train can travel through B without stopping at B given that the other constraints are satisfied.

17) If we have four nodes called A, B, C and D and three links A-B, B-C and B-D, can we call a route of A-B-D-B-C-B-D as a train? We assume all three links are crew segments. Can a train pass the same link more than once?

Yes, your train can have the route as you mentioned given that it satisfies all the other constraints. A train has to start at one end of the crew segment and complete its journey to the other end of the crew segment. Every time, the train arrives at the other end of the crew segment, the crew has to change. Hence, in your example, you would need a total of 6 crews for your train.

18) This node only have two connections one with the node 10473 (34.2 miles) and other with the node 3753 (20.6 miles) but the node 10473 connect with the node 3753 with 13.6 miles!! Thus at least that exits an explicit crew segment that begin or end in the node 429 it never will be part of a shortest path. The node origin of the block Id 545 is 429, thus I do not have any crew to assign from the beginning of the train for this block.

If a node is not along the shortest path for a crew segment and there is a block to be picked up or dropped off at the node, then that block can be considered as a missed block by paying the block (sum of cars) missing penalty cost. In practice, trains go out of route to pick off-route blocks but for this competition, we can consider those blocks as missed.

Also, I would say please check and see if multiple shortest paths would be able to cover such off-route blocks. For example, A-B-C and A-D-C is the same distance, hence you can cover both nodes B and D using different trains and different crews from the same crew district.

19) Can we split blocks? We assume no, what implies that we will have to carry the whole block with the same train from one station to another (we could change the block from one train to another (block swap), but we will swap the whole block).

Yes, what you said is correct. A block cannot be split.

20) If train 1 stops at station A and set-off blk1, blk2 and blk3; train 2 pickup blk1 and blk2 and train 3 pickup blk3, how many block swap cost do we have to consider? 2*block swap cost (2*30 in the example) or 3*block swap cost (3*30)?

Anytime a block is set-off by a train and picked-up by a new train, it is considered as a block swap. In your example, three blocks were transferred from one train to another. If the block swap cost at Station A is 30, then the total block swap cost for the three blocks at station A is 3 *30.

21) If we have nodes B and D as crew segment home and away terminal respectively, considering the topology of the example, can we do BAD, BD and BCD (assuming this is the only crew segment)?

If you have a crew segment B – D and the shortest route between B and D is B-A-D, then the train and crew can travel BAD. Between B and D, if you find another (multiple) shortest route(s) like B-C-D, then you can either pick B-A-D or B-C-D, as needed. Or even, you can have one train travel B-A-D to pick up the block at A and another train travel B-C-D to pick up another block at C.

22) Can we leave (set-off) a block at a station and pick i up later? Does it interfere with the traffic?

For the competition, you can assume infinite capacities on the track at the yards, which is not the case in real world. You do not have to worry about set-off blocks interfering with traffic.

23) Related with the first answer in FAQ: As you said, we do not have to consider timing for this competition. Does this mean that it does not matter if we design solutions that will be infeasible considering the time (because we pick up blocks before other train can possibly set it off?

Example: nodes A, B, C, D, E, F, G, H, with arcs: AB, HB, BC, BG, CD, GD, DE, DF, train 1 (ABCDE), train 2 (FDGBH), train 1 set off two blocks (blk1 at B and blk2 at D), and will pick up two blocks (blk3 at B and blk4 at D) to deliver them at C and at E respectively. Train 2 will set off blk3 and blk4 and will pick up blk 1 and blk2 at B and D respectively to deliver them at H and G respectively. This solution is infeasible considering timing.

Yes, you do not have to consider time for this competition. We understand there could be infeasible solutions from a time perspective in practice. We simplified the problem for this competition.

24) Does it means that if we have a network with three nodes, A, B, C, completely interconnected, and with blocks in A to deliver to B and C, in B to A and C and in C to A and B, the solution train 1 ABCA will be consider feasible? Will we consider that the block in C to B has been delivered (because we travel from C to A and from A to B, though we go to B before we actually pick up the block)?

If you have a train going from A – B –C – A, then Blocks A to B, A to C, B to C, B to A and C to A can be delivered by the ABCA train. The block C to B can be picked up by ABCA train and set off at A. Subsequently, another train can pick-up the C to B block at A and drop off at B. If you want to use the same train, then you have to create a new second train ABCA by paying the train start cost or you can also create a train from A to B and avoid the trip miles B to C to A. Or even some other train traveling along A to B can pick up the C to B block at A and set-off at B.

25) Train 1 route is A-B-C-D, carrying Block 1 with origin = B and destination = C. So does the picking up of Block 1 at B and setting off at C count as work events for Train 1?

If a train travels from A-B-C-D and you have a block going from B to C. When the train stops at B to pick-up the block, then that is considered as the work event. Similarly, when the train stops at C to set-off the block, then that is considered as a work event.

On the other hand, if your block is A to D, then there are no work events as the block origin and destination matches with that of the train.

If your block is A to C, then there is a work event for set-off at C but not for pickup at A.

26) (a) The train route of each train is logically feasible (the sequence of edges they follow in the network form in fact a path and the work events for the train are in concordance with the route).

(b) The interaction between trains and blocks is logically feasible (avoid cases where, for example, a train 1 transports blocks needed by a train 2, which also transports blocks needed by train 1, making impossible for any of them to depart).

According to what we have read in the FAQ, (a) is the required in the competition, but not (b). Is this correct? In that case, what would happen with the following example:

Consider four cities A, B, C and D (on a cycle). A block has to go from C to B. Train 1 has the route A-B-C-D and train 2 has route D-A. Train 1 picks up the block in A and drops it in B, train 1 picks up the block in C and drops it in D, and train 2 picks up the block in D and drops it in A.

Is this solution valid? When considering time, the block travels first from C to D (in train 1), then from D to A (in train 2), and finally from A to B (in train 1); and this is impossible. But since the Competition does no consider time, this solution seems to be feasible.

For this competition, we ignored time aspect for simplification. Hence, the case you explained is feasible for this problem but not in practice.

Just for your understanding purpose, consider your Train1 and Train2 running on all the 7 days of the week. Then block C to B would travel from C to D on Train1 on Monday and then travel on Train2 from D to A on Tuesday. Later, on Wednesday Train1 transports the block from A to B. Consider trains as buses. A bus route is assigned a number and a bus travels the same route may be 5 days or 7 days of the week