# A Simulated Annealing Approach for the Train Design Optimization Problem

Authors: Federico Alonso-Pecina; David Romero
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

The Train Design Optimization Problem regards making optimal decisions on the number and movement of locomotives and crews through a railway network, so as to satisfy requested pick-up and delivery of car blocks at stations. In a mathematical programming formulation, the objective function to minimize is composed of the costs associated with the movement of locomotives and cars, the loading/unloading operations, the number of locomotives, and the crews’ return to their departure stations. The constraints include upper bounds for number of car blocks per locomotive, number of car block swaps, and number of locomotives passing through railroad segments. We propose here a heuristic method to solve this highly combinatorial problem in two steps. The first one finds an initial, feasible solution by means of an ad hoc algorithm. The second step uses the simulated annealing concept to improve the initial solution, followed by a procedure aiming to further reduce the number of needed locomotives. We show that our results are competitive with those found in the literature.


---

## Body

## 1. Introduction

An ample range of investigations have been undertaken to develop optimization algorithms for various problems encountered in the realm of rail systems, like routing [1], scheduling [2–4], crew assignment [5, 6], and blocking [7, 8], among others [9–12]. However, to our knowledge, the Train Design Optimization Problem as defined below is the only attempt to simultaneously deal with block-to-train assignment, train routing, and crew assignment [13], arising as one of the most fundamental and difficult combinatorial optimization problems formulated in the railroad industry [13–17], with a huge potential to benefit from the application of operations research techniques.In rail systems, a railroad car, railcar, or train car (car, for short), is a vehicle used for the carrying of cargo. Such cars, when coupled together and hauled by one or more locomotives, form atrain. A car block (block, for short) is a semipermanently arranged formation of cars. Trains are then built of one or more blocks coupled together as needed. Also, in the operation of rail systems ablock swap can occur, namely, when a locomotive delivers a block at a station distinct from the block’s destination, and another locomotive picks up the block afterwards. Each time a train stops en route at a station to pick up and/or to deliver blocks, awork-event takes place.In this paper we address the Train Design Optimization Problem (TDOP) arising in the operation of railroad freight transport as part of the logistics chain. It consists in determining, at minimal total cost, and subject to capacity and operational constraints, the number of locomotives and crews, together with the logistics related to the movement of locomotives, blocks, and crews through a railway network, so as to transport goods from a set of shippers to a set of destinations.The total cost depends on the number of assigned locomotives, the distance traveled by locomotives and cars, the distance traveled by crews to return to their departure stations, the number of block swaps and work-events, the number of blocks not arriving to destination, and the difference between the number of locomotives arriving to and departing from stations. The constraints include maximum number of blocks per locomotive, maximum number of block swaps, maximum number of work-events per locomotive, maximum length, weight, and number of trains passing through a railroad segment, and crew limitations as to the route to follow.Only a handful of approaches have been developed for the solution of the TDOP. In [18] a mixed integer programming model is proposed; block routes are first generated together with train routes to cover them, then a matching is sought to minimize the objective function, and finally several greedy and local search rules are iteratively invoked to update the block-paths and train routes so as to improve the solution quality. In [19, 20] the problem is formulated as one of integer programming where the number of variables and constraints is exponential, proposing for its solution a column-row generation heuristic followed by clever tabu search methods. An iterative procedure is suggested in [21] to solve two subproblems of the TDOP: train design and block-to-train assignment, where the former consists in determining train routes to be operated, and the latter deals with the routing decision for blocks; both subproblems are solved by integer programming techniques. In [22, 23] a column-generation approach is designed: first, a set of promising train routes is generated based on the crew segments; then an integer linear programming model is developed for the subsequent decisions including train route selection and block-to-train assignment.We propose hereafter a method to heuristically solve the TDOP in two steps. By means of an ad hoc procedure the first step aims to produce an initial feasible solution, namely, a solution satisfying all the constraints. The second step uses the simulated annealing method to improve the initial solution, followed by simple, specialized procedures that attempt to reduce the number of needed trains without increasing the overall cost. To test our proposal we solved the only three published instances to date, finding it competitive with other approaches in the literature. Also, we randomly generated 20 synthetic instances as well as (improvable) lower bounds for their corresponding optimal solutions; our heuristic came up with results averaging an error close to 25% on these bounds.The rest of the paper is organized as follows: Section2 provides the necessary terminology and makes a detailed description of constraints and objective function of the TDOP; a toy example is also furnished to help understand the problem. In Section 3 the TDOP is formulated in mathematical programming terms. Our solution approach—basically combining an ad hoc algorithm to find an initial feasible solution followed by the metaheuristic known as simulated annealing—is explained in Section 4. Further, Section 5 is devoted to the computational experiments that we conducted to test our procedures; for this experimentation we used the three available known instances as well as a new set of 20 randomly generated ones. Finally, Section 6 presents our conclusions and a proposal for future work.


## 2. Problem Description

This section is aimed to describe the TDOP, borrowing some terminology from [20]. An alternative description can be found in [13]. The TDOP terminology, constraints, and objective function are provided in Section 2.1. To help in grasping our description, an instance of the TDOP is presented in Example 1 by means of a toy example, followed by one of its feasible solutions in Section 2.2.


### 2.1. Terminology, Constraints, and Objective Function

Terminology
(i)
Ablock is a formation of cars sharing origin and destination. Trains are built of one or more blocks coupled together as needed.
(ii)
Atrain is a locomotive carrying or not carrying blocks.
(iii)
Ablock swap occurs when a block is moved from one train to another.
(iv)
Ablock-path is a sequence of railroad segments through which a block can be feasibly routed from its origin to its destination.
(v)
Awork-event occurs each time a train stops en route at a station to pick up and/or deliver blocks. The train stop at its destination (or origin) station is not considered as a work-event.
(vi)
Acrew segment is a minimal length route between two stations, calledend points, on which crews operate trains in either direction.
(vii)
Thecrew imbalance on a crew segment, defined by say end points x and y, is the absolute difference between the number of crews going from x to y, and the number of crews going from y to x.
(viii)
Thetrain imbalance on a station, say x, is the absolute difference between the number of trains originating in x and the number of trains terminating in x.
(ix)
A car ismissed if it is not transported from its origin to its destination.Constraints
(i)
Blocks per train: trains are constrained by an upper bound on the number of blocks they carry.
(ii)
Swaps per block: each block is constrained by an upper bound on the number of times it can be swapped.
(iii)
End points: crews must start and end traveling at end points.
(iv)
Crew-to-train assignment: every train has to be assigned to a crew on each crew segment, and it must originate and terminate at the end points of a crew segment, even if the train has to move part of the way along a crew segment not carrying any blocks (the entire train routes should be decomposed in crew segments).
(v)
Upper bounds on segments: railroad segments are constrained by upper bounds on the number, length, and weight of trains traversing them in either direction.The objective of the TDOP is to minimize the sum of eight components:(1)
Locomotive cost: product of the number of scheduled locomotives and the unit locomotive cost C1.(2)
Locomotive travel cost: product of the total traveled miles by all scheduled locomotives, and the per mile locomotive travel cost C2.(3)
Work-event cost: product of the total number of work-events of all scheduled trains, and the unit work-event cost C3.(4)
Car travel cost: product of the total traveled miles by all cars, and the per mile car travel cost C4.(5)
Block swap cost: let sv be the unit block swap cost in station v. For a given block b, denote βb the set of stations where block b is swapped; then its (total) block swap cost is ∑v∈βbsv.(6)
Crew imbalance cost: product of the number of all crew imbalances and the unit crew imbalance cost C5.(7)
Train imbalance cost: product of the number of all train imbalances and the unit train imbalance cost C6.(8)
Missed car cost: product of the total number of missed cars and the cost per missed car C7.Example 1.
Consider a railroad network with five stations A, B, C, D, and E and six railroad segments as schematically depicted in Figure1, where distances (in miles) are assumed symmetrical and all segments are bidirectional. Seven blocks must be delivered. Table 1 furnishes the relevant data.
The only nonadjacent end points defining a crew segment are B and D. The corresponding crew segment is BCD because its length is minimal among all possible paths connecting B and D. Clearly, the other crew segments are trivially found. Thus, if the route of some train is, say, D→ C → B → A, then at D a crew from crew segment BCD could be assigned to this train in the subroute D → C → B, and subsequently at B a crew from crew segment BA could be assigned to the train in the subroute B → A. When a train crosses over from one crew segment to another, the onboard crew gets off the train and a new crew gets onboard. Further, crew segments are bidirectional. Hence, crews in crew segment BA can take a train from A to B or vice versa. It is assumed that crews always travel along the shortest path between any pair of stations.Table 1
Data of Example1.
(a)
Station
Block swap cost
A
60
B
60
C
80
D
20
E
20
(b)
Block
Origin
Destination
# of cars
Length (feet)
Weight (tons)
b1
C
A
5
290
420
b2
C
D
48
2,976
3,696
b3
A
D
13
819
962
b4
D
B
4
228
316
b5
E
D
12
708
936
b6
D
C
63
3,969
4,914
b7
B
A
42
2,730
3,570
(c)
Segment
Length (miles)
Maximum train length (feet)
Maximum train weight (tons)
Max number of trains
BC
76
4,100
5,600
6
AB
132
4,400
6,300
12
DE
151
5,700
5,400
6
CE
202
4,500
7,900
11
CD
210
4,000
10,000
9
AE
250
6,200
6,500
6
(d)
End points defining five crew segments
{
B
,
A
}
{
B
,
D
}
{
A
,
E
}
{
C
,
E
}
{
D
,
E
}
(e)
Description
Value
Unit locomotive cost (C1)
$400
Train travel cost per mile (C2)
$10
Cost per work-event (C3)
$350
Car travel cost per mile (C4)
$0.75
Unit crew imbalance penalty (C5)
$600
Unit train imbalance penalty (C6)
$1,000
Cost per missed car (C7)
$5,000
Maximum number of blocks per train (MB)
8
Maximum number of swaps per block (MS)
3
Maximum number of work-events per train (MW)
4Figure 1
Diagram of railroad networks. Example1.


### 2.2. A Feasible Solution of Example1

Consider the solution shown in Table2. Two trains, t1 and t2, are scheduled to transport blocks. Note that train t1 picks up 63 cars at station D and then goes to C, where it delivers 63 cars and picks up 5 cars. From station C train t1 travels to B to pick up 42 cars; then it goes to station A to deliver 47 cars and to pick up 13 cars. Finally, it travels to station B to deliver 13 cars.Table 2
Train routes solution of Example1.
Train
Sequence
Station
Cumulative miles
Deliver cars
Pick up cars
Cars in the train
Crew change
t1
1
D
0
0
63
63
NO
2
C
210
63
5
5
NO
3
B
286
0
42
47
YES
4
A
418
47
13
13
NO
5
B
550
13
0
0
NO
t2
1
E
0
0
12
12
NO
2
D
151
12
4
4
YES
3
C
361
0
0
4
NO
4
B
437
4
13
13
NO
5
C
513
0
48
61
NO
6
D
723
61
0
0
NO
Total mileage
1,273The distance traversed by botht1 and t2 is 1,273 miles. Train t1 stops to pick up or drop blocks in stations C, B, and A, while train t2 stops to pick up or drop blocks in stations D, B, and C. Hence, the total number of work-events produced by both trains is six.Table3 indicates the train on which each block travels between stations. For instance, block b3 travels first on train t1 from A to B, then on train t2 from B to D, yielding one block swap (with cost 60).Table 3
Block-to-train assignment of Example1.
Block
Sequence
Train
Start station
End station
block swap cost
Segment miles
# of cars
Car miles
b1
1
t
1
C
A
0
208
5
1,040
b2
1
t
2
C
D
0
210
48
10,080
b3
1
t
1
A
B
60
132
13
1,716
b3
2
t
2
B
D
0
286
13
3,718
b4
1
t
2
D
B
0
286
4
1,144
b5
1
t
2
E
D
0
151
12
1,812
b6
1
t
1
D
C
0
210
63
13,230
b7
1
t
1
B
A
0
132
42
5,544
Totals
60
38,284The column labeled “Car miles” is computed as the product of the distance traveled by a block on a segment, and the number of cars in the block. Note that the block-to-train assignment satisfies the constraints on the maximum number of block swaps, and on the maximum number of blocks per train (see Tables1(a) and 1(b)).In Table4 the crew-to-train assignment information is provided. It is shown, for instance, that a crew travels from D to B on train t1. Then another crew travels from B to A on train t1. Finally, this crew travels from A to B on the same train.Table 4
Crew-to-train assignment of Example1.
Crew segment
Train
Forward
Backward
BD
t
1
0
1
BA
t
1
1
1
DE
t
2
0
1
BD
t
2
1
1Note that there is one train imbalance in station B because it is the origin of no train, and one train terminates there. Similarly, there is one train imbalance in station E. Hence, this solution yields two train imbalances.The objective function value of this solution is as much as 47,603, computed in Table5 (costs in $).Table 5
Total costs of Example1.
Locomotive cost
2 (number of locomotives) × 400 = 800
Train travel cost
1,273 × 10 = 12,730 (see Table2)
Car travel cost
38,284 × 0.75 = 28,713 (see Table3)
Work-event cost
6 (number of train work-events) × 350 = 2,100
Blocks swap cost
60 (see Table3)
Crew imbalance cost
2 × 600 = 1,200 (see Table4)
Train imbalance cost
2 × 1,000 = 2,000
Missed cars cost
0


## 2.1. Terminology, Constraints, and Objective Function

Terminology
(i)
Ablock is a formation of cars sharing origin and destination. Trains are built of one or more blocks coupled together as needed.
(ii)
Atrain is a locomotive carrying or not carrying blocks.
(iii)
Ablock swap occurs when a block is moved from one train to another.
(iv)
Ablock-path is a sequence of railroad segments through which a block can be feasibly routed from its origin to its destination.
(v)
Awork-event occurs each time a train stops en route at a station to pick up and/or deliver blocks. The train stop at its destination (or origin) station is not considered as a work-event.
(vi)
Acrew segment is a minimal length route between two stations, calledend points, on which crews operate trains in either direction.
(vii)
Thecrew imbalance on a crew segment, defined by say end points x and y, is the absolute difference between the number of crews going from x to y, and the number of crews going from y to x.
(viii)
Thetrain imbalance on a station, say x, is the absolute difference between the number of trains originating in x and the number of trains terminating in x.
(ix)
A car ismissed if it is not transported from its origin to its destination.Constraints
(i)
Blocks per train: trains are constrained by an upper bound on the number of blocks they carry.
(ii)
Swaps per block: each block is constrained by an upper bound on the number of times it can be swapped.
(iii)
End points: crews must start and end traveling at end points.
(iv)
Crew-to-train assignment: every train has to be assigned to a crew on each crew segment, and it must originate and terminate at the end points of a crew segment, even if the train has to move part of the way along a crew segment not carrying any blocks (the entire train routes should be decomposed in crew segments).
(v)
Upper bounds on segments: railroad segments are constrained by upper bounds on the number, length, and weight of trains traversing them in either direction.The objective of the TDOP is to minimize the sum of eight components:(1)
Locomotive cost: product of the number of scheduled locomotives and the unit locomotive cost C1.(2)
Locomotive travel cost: product of the total traveled miles by all scheduled locomotives, and the per mile locomotive travel cost C2.(3)
Work-event cost: product of the total number of work-events of all scheduled trains, and the unit work-event cost C3.(4)
Car travel cost: product of the total traveled miles by all cars, and the per mile car travel cost C4.(5)
Block swap cost: let sv be the unit block swap cost in station v. For a given block b, denote βb the set of stations where block b is swapped; then its (total) block swap cost is ∑v∈βbsv.(6)
Crew imbalance cost: product of the number of all crew imbalances and the unit crew imbalance cost C5.(7)
Train imbalance cost: product of the number of all train imbalances and the unit train imbalance cost C6.(8)
Missed car cost: product of the total number of missed cars and the cost per missed car C7.Example 1.
Consider a railroad network with five stations A, B, C, D, and E and six railroad segments as schematically depicted in Figure1, where distances (in miles) are assumed symmetrical and all segments are bidirectional. Seven blocks must be delivered. Table 1 furnishes the relevant data.
The only nonadjacent end points defining a crew segment are B and D. The corresponding crew segment is BCD because its length is minimal among all possible paths connecting B and D. Clearly, the other crew segments are trivially found. Thus, if the route of some train is, say, D→ C → B → A, then at D a crew from crew segment BCD could be assigned to this train in the subroute D → C → B, and subsequently at B a crew from crew segment BA could be assigned to the train in the subroute B → A. When a train crosses over from one crew segment to another, the onboard crew gets off the train and a new crew gets onboard. Further, crew segments are bidirectional. Hence, crews in crew segment BA can take a train from A to B or vice versa. It is assumed that crews always travel along the shortest path between any pair of stations.Table 1
Data of Example1.
(a)
Station
Block swap cost
A
60
B
60
C
80
D
20
E
20
(b)
Block
Origin
Destination
# of cars
Length (feet)
Weight (tons)
b1
C
A
5
290
420
b2
C
D
48
2,976
3,696
b3
A
D
13
819
962
b4
D
B
4
228
316
b5
E
D
12
708
936
b6
D
C
63
3,969
4,914
b7
B
A
42
2,730
3,570
(c)
Segment
Length (miles)
Maximum train length (feet)
Maximum train weight (tons)
Max number of trains
BC
76
4,100
5,600
6
AB
132
4,400
6,300
12
DE
151
5,700
5,400
6
CE
202
4,500
7,900
11
CD
210
4,000
10,000
9
AE
250
6,200
6,500
6
(d)
End points defining five crew segments
{
B
,
A
}
{
B
,
D
}
{
A
,
E
}
{
C
,
E
}
{
D
,
E
}
(e)
Description
Value
Unit locomotive cost (C1)
$400
Train travel cost per mile (C2)
$10
Cost per work-event (C3)
$350
Car travel cost per mile (C4)
$0.75
Unit crew imbalance penalty (C5)
$600
Unit train imbalance penalty (C6)
$1,000
Cost per missed car (C7)
$5,000
Maximum number of blocks per train (MB)
8
Maximum number of swaps per block (MS)
3
Maximum number of work-events per train (MW)
4Figure 1
Diagram of railroad networks. Example1.


## 2.2. A Feasible Solution of Example1

Consider the solution shown in Table2. Two trains, t1 and t2, are scheduled to transport blocks. Note that train t1 picks up 63 cars at station D and then goes to C, where it delivers 63 cars and picks up 5 cars. From station C train t1 travels to B to pick up 42 cars; then it goes to station A to deliver 47 cars and to pick up 13 cars. Finally, it travels to station B to deliver 13 cars.Table 2
Train routes solution of Example1.
Train
Sequence
Station
Cumulative miles
Deliver cars
Pick up cars
Cars in the train
Crew change
t1
1
D
0
0
63
63
NO
2
C
210
63
5
5
NO
3
B
286
0
42
47
YES
4
A
418
47
13
13
NO
5
B
550
13
0
0
NO
t2
1
E
0
0
12
12
NO
2
D
151
12
4
4
YES
3
C
361
0
0
4
NO
4
B
437
4
13
13
NO
5
C
513
0
48
61
NO
6
D
723
61
0
0
NO
Total mileage
1,273The distance traversed by botht1 and t2 is 1,273 miles. Train t1 stops to pick up or drop blocks in stations C, B, and A, while train t2 stops to pick up or drop blocks in stations D, B, and C. Hence, the total number of work-events produced by both trains is six.Table3 indicates the train on which each block travels between stations. For instance, block b3 travels first on train t1 from A to B, then on train t2 from B to D, yielding one block swap (with cost 60).Table 3
Block-to-train assignment of Example1.
Block
Sequence
Train
Start station
End station
block swap cost
Segment miles
# of cars
Car miles
b1
1
t
1
C
A
0
208
5
1,040
b2
1
t
2
C
D
0
210
48
10,080
b3
1
t
1
A
B
60
132
13
1,716
b3
2
t
2
B
D
0
286
13
3,718
b4
1
t
2
D
B
0
286
4
1,144
b5
1
t
2
E
D
0
151
12
1,812
b6
1
t
1
D
C
0
210
63
13,230
b7
1
t
1
B
A
0
132
42
5,544
Totals
60
38,284The column labeled “Car miles” is computed as the product of the distance traveled by a block on a segment, and the number of cars in the block. Note that the block-to-train assignment satisfies the constraints on the maximum number of block swaps, and on the maximum number of blocks per train (see Tables1(a) and 1(b)).In Table4 the crew-to-train assignment information is provided. It is shown, for instance, that a crew travels from D to B on train t1. Then another crew travels from B to A on train t1. Finally, this crew travels from A to B on the same train.Table 4
Crew-to-train assignment of Example1.
Crew segment
Train
Forward
Backward
BD
t
1
0
1
BA
t
1
1
1
DE
t
2
0
1
BD
t
2
1
1Note that there is one train imbalance in station B because it is the origin of no train, and one train terminates there. Similarly, there is one train imbalance in station E. Hence, this solution yields two train imbalances.The objective function value of this solution is as much as 47,603, computed in Table5 (costs in $).Table 5
Total costs of Example1.
Locomotive cost
2 (number of locomotives) × 400 = 800
Train travel cost
1,273 × 10 = 12,730 (see Table2)
Car travel cost
38,284 × 0.75 = 28,713 (see Table3)
Work-event cost
6 (number of train work-events) × 350 = 2,100
Blocks swap cost
60 (see Table3)
Crew imbalance cost
2 × 600 = 1,200 (see Table4)
Train imbalance cost
2 × 1,000 = 2,000
Missed cars cost
0


## 3. The Model

We consider the railroad network as a directed graphG=V,E whose set of nodes V corresponds to the set of stations, and the set of arcs E is derived from the railroad segments between stations, associating a couple of arcs with opposite directions to each rail segment. The length of arc e=u,v∈E is equal to the distance between stations u,v∈V. Also, for e∈E, let L¯e, W¯e, and T¯e denote, respectively, the maximum train length, the maximum weight, and the maximum number of trains allowed to traverse arc (or segment) e in either direction.DenoteC the set of crew segments, where each crew segment c∈C is a path through a set of stations χc—including end points—and let H≔⋃c∈Cχc. We assume crews are always traveling on crew segments.LetB be the set of blocks to be delivered. For block b∈B, its origin, destination, number of cars, length, and weight are denoted ob, db, rb, lb, and wb, respectively.LetΓ be the set of all possible trains, and let P· be a generic sequence of arcs of E, with LP· denoting its length. Thus, the arc sequence followed by train t∈Γ is Pt, and that of block b is Pb; namely, Pb is a block-path of b. In case train t∈Γ is used, let CRt and WEt be, respectively, the set of crews traveling on train t and the number of work-events of train t. Our mathematical formulation below closely follows the one proposed in [20].Letctt denote the cost of train t∈Γ, which consists of the unit locomotive cost C1, plus the train travel cost, and plus the cost of work-events. Hence, (1)ctt=C1+C2×LPt+C3×WEt.Each traint∈Γ can be seen, in fact, as a sequence of crew segments, forming a path Pt. The subset of trains passing through arc e∈E is Te∈Γ, and Kte is the number of times train t passes through e. From set Γ and graph G, one can obtain a multigraph MG=V,A, where A is obtained by replacing each arc e∈E with ∑t∈TeKte copies of it. If a train passes several times through arc e, then each passage induces a different copy.The binary variableλt states whether train t∈Γ is used or not in the solution. Let Δvt be equal to -1 if train t starts its route in node v, and equal to +1 if train t ends its route in v. Thus, Δv=∑t∈ΓΔvtλt is the train imbalance in node v.Letu and v be the end points of a crew segment c∈C. Then Δct denotes the difference between the number of times train t goes through c, from u to v, and the number of times it goes through c from v to u. So, Δc=∑t∈ΓΔctλt is the crew imbalance of crew segment c.LetΩb denote the set of all block-paths Pb associated with block b∈B, which includes a dummy block-path of one arc from ob to db with cost C7×rb. Further, let Ωbt⊆Ωb be the subset of paths in Ωb that use train t, and let Ω=⋃b∈BΩb be the whole set of block-paths.Forb∈B, let cbb denote the block-path cost for block b, namely, in case of a dummy block-path; then cbb=C7×rb; otherwise (2)cbb=C4×rb×LPb+∑v∈βbsv, whose two terms correspond to block travel cost and block swap cost, respectively. Recall that rb is the number of cars of block b, each block swap at node v∈V costs sv, and βb is the set of stations where b is block swapped.LetΩe be the set of block-paths that use arc e∈A of multigraphMG. Note that there is one train corresponding to Ωe. Binary variable xPb states whether block-path Pb∈Ω is used or not in the solution.Therefore, our mathematical model of the TDOP is(3)minz=∑t∈Γcttλt+∑Pb∈ΩcbbxPb+C5∑c∈CΔc+C6∑v∈VΔv(4)subject to∑Pb∈ΩbxPb≥1,∀b∈B(5)∑Pb∈ΩbtxPb≤λt,∀t∈Γ(6)∑b∈B∑Pb∈ΩbtxPb≤MB,∀t∈Γ(7)∑Pb∈ΩelbxPb≤L¯e,∀e∈E(8)∑Pb∈ΩewbxPb≤W¯e,∀e∈E(9)∑t∈TeKteλt≤T¯e,∀e∈E(10)WEt≤MW,∀t∈Γ(11)xPb,λt∈0,1,∀Pb∈Ω,t∈Γ.The terms in the objective function (3) correspond to the costs of locomotives, blocks, crew imbalances, and train imbalances, in that order. Constraint (4) imposes the existence of a block-path—real or dummy—for each block b∈B. Constraint (5) forces selecting train t if any of the selected block-paths uses it. Constraints (6)–(10) stand for upper bounds on number of blocks that a train can transport, length and weight of trains passing through arcs, number of trains passing through arcs, and number of work-events per train, respectively. We emphasize that every sequence of train t∈Γ must be decomposed in a sequence of crew segments.


## 4. Algorithm

This section presents the algorithm developed by us to tackle the TDOP. It consists of two main steps.Step 1 (initial feasible solution).
Composed by substeps (1.1)–(1.3), this step is aimed to produce from scratch a feasible solution of the TDOP, namely, where constraints (6)–(11) are satisfied.(1.1) Crew Selection. For every block b∈B determine a minimum length path ξb from ob to db, where each arc can be operated by at least one crew. The set of crews πb to operate along path ξb is chosen following substeps (1.1.1)–(1.1.5) below. For every πb a minimum set of trains is constructed, so as only one train corresponds to every pair of crews such that one ends where the other starts. Note that with this rule the corresponding trains to carry b can be easily deduced. Let Q(b)≔{Q∣Q be a set of crew segments covering the arcs of ξb}.In substep (1.1.4) every possible effort is made to avoid the overlapping of crews inQb; therefore, even though Qb contained overlapping crews, this is not an issue since the probability of this happening is truly negligible. In the sequel Qb will be simply written Q. Although Q is theoretically of exponential size, in all our experiments we were able to enumerate it completely.(1.1.1) ForQ∈Q, let γQ be the number of swaps of block b when transported through crew segments Q. Determine γ∗≔min⁡γQ:Q∈Q and reduce Q by eliminating from it every Q such that γQ>γ∗. If Q has a unique element, say, Q^, make πb≔Q^; otherwise go to (1.1.2).(1.1.2) If inQ there is a crew set starting in ob, then reduce Q by eliminating from it every Q not starting in ob. If Q has a unique element, say, Q~, make πb≔Q~; otherwise go to (1.1.3).(1.1.3) If inQ there is a crew set ending in db, then reduce Q by eliminating from it every Q not ending in db. If Q has a unique element, say, Q¨, make πb≔Q¨; otherwise go to (1.1.4).(1.1.4) LetρQ be the total distance traveled by the trains corresponding to the crew segments in Q∈Q, and let ρ∗≔min⁡ρQ:Q∈Q. Reduce Q by eliminating from it every Q such that ρQ>ρ∗. If Q has a unique element, say, Q¯, then make πb≔Q¯; otherwise go to (1.1.5). For example, assume we have a block with origin A and destination D, together with crews A-B-C, B-C-D, and A-B. One solution is to use crews A-B-C and B-C-D, while another uses crews B-C-D and A-B; with this criterion the second solution is chosen.(1.1.5) Letq∗=min⁡Q:Q∈Q. Reduce Q by eliminating from it every Q such that Q>q∗. If Q has a unique element, say, Qˇ, make πb≔Qˇ; otherwise make πb equal to an arbitrarily selected Q∈Q.(1.2) Block Ordering. An order B¯ on the set of blocks B is constructed as follows. Let Lξb be the length of path ξb. If Lξb′>Lξb′′ then block b′ precedes block b′′ in B¯. However, if Lξb′=Lξb′′, then b′ precedes b′′ in B¯ whenever νb′>νb′′, where ν· denotes the number of blocks with origin o· and destination d·. In case Lξb′=Lξb′′ and νb′=νb′′ hold together, block b′ precedes b′′ whenever rb′>rb′′. Finally, if Lξb′=Lξb′′, νb′=νb′′, and rb′=rb′′, this tie between b′ and b′′ is arbitrarily broken to produce B¯.(1.3) Train Assignment. Blocks are considered one after the other, according to order B¯=b1,…,bm. First, assign block b1 to the crews selected in Step (1.1), together with the required train(s). For j=2,…,m, if path ξbj is contained in path ξbi for some i∈1,j-1, then assign block bj to path ξbi whenever upper bounds on feet, tons, and max blocks per train allow. Otherwise, assign block bj to the crews selected in Step (1.1), together with the required train(s). This step produces a feasible solution S.Step 2 (simulated annealing).
Proposed more than three decades ago [24, 25] Simulated Annealing (SA, for short) is one of the most successful metaheuristics to find good solutions of many combinatorial optimization problems (see [26] and the references therein), including the railroad freight transportation design problem [27]. In its theoretical formulation, SA converges with probability 1 to a global minimum under certain assumptions on the control parameters. In practice, these assumptions are impossible to be implemented, but adequate cooling schemes increase the likelihood of obtaining a near optimal solution [28].Central to SA is the neighborhood concept. For our proposal we hand tailored it as follows. LetΦJ denote the set of feasible solutions of an instance J of the TDOP. Theneighborhood of a solution S∈ΦJ is (12)NS=N1S∪N2S∪N3S, where (i) N1S⊆ΦJ contains every solution obtainable from S by adding one or more trains to deliver one block alone, say b, through ξb. (ii) N2S⊆ΦJ contains the solutions obtainable from S by removing one block, say b, from the set Ψ of trains carrying it and delivering it through a minimal length route from ob to db without using any train of Ψ, using another trains in S. (iii) N3S⊆ΦJ contains every solution obtainable from S by the removal of one block, say b, from the set Ψ of trains carrying it, and delivering it through a minimal length route from ob to db without using any train of Ψ, with at least one added train, and using at least one existing train.We implemented a simulated annealing procedure with geometrical cooling scheme as shown below, where the variableτ stands for the system temperature, and the parameters To,Tf,α,θ, denote, respectively, the initial and the final temperature, the cooling factor, and the internal cycle length.Procedure NeighborS randomly produces (with uniform distribution) a feasible solution in NS, and Rand delivers a uniformly distributed random number in the interval (0,1). SA starts with the solution S delivered by Step 1 above (see Algorithm 1).Algorithm 1:Algorithm simulated annealing.
τ
←
T
o; S∗←S;
While
τ
≥
T
f
do
k←0;
Whilek≤θdo
S′←NeighborS;
δ←zS′-zS;
If Rand0,1<e-δ/τorδ<0then
S←S′;
EndIf
k←k+1;
IfzS<zS∗then
S∗←S; k←0;
EndIf
EndWhile
τ←ατ;
EndWhile
call Fusion.Throughout the process, the variableS∗ holds the best solution so far, and the counter k helps to control the number of iterations of the internal cycle. Thus, the system temperature τ drops if and only if θ iterations occur without any improvement on S∗.Added at the end of the external cycle, procedure Fusion attempts to improve solution S∗ by successively applying the following four operations in the order shown. Before passing to the next operation, for each operation all possibilities are considered, repeating it exhaustively as long as the cost is lowered and feasibility is preserved.(1)
When two trains have identical routes, one locomotive is eliminated once its blocks are passed to the other.(2)
If there are stationsu, v, such that ∑t∈ΓΔutλt<0 and ∑t∈ΓΔvtλt>0, then a train with no blocks is added starting in v and ending in u.(3)
If a train starts its route in a station where another train terminates its travel, one locomotive is eliminated once its blocks are passed to the other.(4)
If there are trainst′, t′′, such that the t′′ route is contained in the t′ route, then the t′′ locomotive is eliminated once its blocks are passed to t′.Example 2.
For clarity sake, consider a railroad network as schematically depicted in Figure2. Assume a block b with ob= A and db= D, and let the crew segments be AF, AD, AI, AP, FD, IL, LD, QR, and DP. Also, let S be a feasible solution with six trains in correspondence to routes: A → E → F, F → G → D, A → H → I, I → J → F → K → L, A → N → O → P, and L → M → D, where block b is delivered by the trains assigned to routes A → E → F and F → G → D; hence 63 is their total traveled distance. Thus, solution S′∈N1S is identical to S with the exception that block b is delivered by a new train through route A → B → C → D, with length 42.
SolutionS′′∈N2S is identical to S with the exception that block b is delivered by the trains with routes A → H → I, I → J → F → K → L, and L → M → D, with total length 91, and without adding a new train.
SolutionS′′′∈N3S is identical to S with the exception that block b is delivered through route A → N → O → P, adding a new train for segment PD; the total length of this route is 47.
In regard to simulated annealing parameters, we tested diverse settings, modifying one parameter at a time. Among the possible combinations of the cooling factorα=0.70, 0.75, 0.80, 0.85, 090, 0.95, and 0.99, and the internal cycle lengths θ=500, 1,000, 1,500, 2,000, 4,000, 6,000, 8,000, and 10,000, for every pair α,θ we run ten times the algorithm on a PC with Windows 8.
Table6 displays the average results obtained for instanceData Set 2, where computer times are shown in italics. Thus, we chose α=0.90 and θ = 1,000 since together they yielded a good trade-off between computer time and solution quality. As initial temperature we chose To = 30,000, because on average it yielded an acceptance rate of around 95%. For the final temperature Tf=1 was selected, yielding an acceptance rate of around 1% on average.Table 6
Average results—objective function value rounded to nearest integer—of ten runs for instanceData Set 2. Time shown in seconds and italics.
θ∖α
0.70
0.75
0.80
0.85
0.90
0.95
0.99
500
3,209,687
3,210,058
3,212,176
3,209,065
3,205,954
3,195,864
3,185,775
2,790
2,226
2,446
2,666
2,783
3,934
10,877
1,000
3,205,775
3,204,303
3,203,858
3,200,948
3,201,772
3,191,151
3,184,551
2,459
2,593
2,771
3,351
4,259
5,181
19,899
1,500
3,200,260
3,201,520
3,192,792
3,190,837
3,187,281
3,190,916
3,173,312
2,605
2,634
2,901
3,450
4,355
7,264
29,082
2,000
3,201,157
3,196,194
3,192,166
3,195,499
3,188,878
3,188,311
3,175,760
3,070
2,890
2,540
4,332
4,997
9,066
36,945
4,000
3,195,857
3,187,514
3,187,182
3,185,158
3,184,931
3,176,745
3,173,650
3,808
4,771
5,339
6,844
8,904
16,043
76,952
6,000
3,192,045
3,189,039
3,185,947
3,180,655
3,181,356
3,175,733
3,169,176
5,857
5,976
7,398
8,711
16,026
25,530
116,304
8,000
3,188,106
3,185,158
3,184,032
3,181,325
3,179,988
3,172,099
3,167,935
6,741
6,844
9,216
12,206
18,319
37,695
153,931
10,000
3,186,663
3,184,824
3,182,085
3,178,864
3,176,411
3,168,984
3,164,844
7,466
8,622
10,846
14,772
21,081
42,862
218,506Figure 2
Diagram of railroad networks. Example2.


## 5. Numerical Results

Our simulated annealing approach, as described in Section4 to deal with the TDOP, was implemented on a computer with Xeon E5-2643 v2 3.5 GHz processor (we run in a single processor), 64 GB RAM, and g++ compiler. Two experiments were conducted to investigate its efficiency.In the first experiment—see Section5.1—we tested SA on three instances available to us:Example (a toy, synthetic instance),Data Set 1 (real), andData Set 2 (real), from [13].The second experiment was designed to evaluate the performance of SA from the point of view of the quality of the results and the required computer time. We did extensive testing on randomly generated instances of various sizes; they are dealt with in Section5.2.


### 5.1. Testing SA on Specific Instances

Employing parametersθ = 1000 and α = 0.9, we compared SA results on instancesExample,Data Set 1, andData Set 2, as can be seen in Table 7, where computation times are also shown to give an idea of the performance of the implementation, although the platforms used were not the same. So far [18] had provided—using a mixed integer programming model—the best results for the two real instances but at the expense of very high computing time. On the other hand, the network-oriented formulation in [21] yielded the fastest algorithm to date.Table 7
Performance comparison of our SA approach and other methods; computing times are given in seconds. The bottom row shows a lower bound on the optimal cost, computed as explained in Section5.3. (all figures rounded to integers).
Number of
Example
Data Set 1
Data Set 2
Nodes
4
94
221
Blocks
5
239
369
Arcs
5
134
294
Crew Segments
5
154
154
cost
time
cost
time
cost
time
[21]
—
2,043,471
45
3,187,999
225
[20]
—
2,032,516
2,201
3,188,500
2,067
[18]
—
2,018,644
80,000
3,152,019
75,000
[23]
14,916
0
2,069,752
342
3,240,177
2,700
SA
14,916
1
2,005,514
181
3,170,815
1,991
Lower boundσ
10,956
1,660,361
2,751,213Other approaches include column-generation [23], with better results than those found in [22], and column-generation combined with tabu search [20] improving on [19]. In the case of instanceExample the only published results come from [23]. The best results found with SA were 1,999,315 with θ = 8000 and α = 0.99, in 19,819 seconds for instanceData Set 1, and 3,155,267 with θ = 10,000 and α = 0.95 in 41,233 seconds for instanceData Set 2, with the more relevant results found in the literature; our results yield lower cost forData Set 1 (-0.95%), same cost forExample, and higher cost forData Set 2 (+0.10%).


### 5.2. Testing SA on Random Instances

A set of 20 random instances was generated as follows with the numbern of stations and number m of blocks shown in column II of Table 8. All random choices were made with uniform distribution.Table 8
Relevant data (columns I, II) and results (columns III, IV, and V) of 50 runs of SA on 20 random instances. A lower bound—explained in Section5.3—on the optimal solution cost is shown in column VI. The last column is an indicator of the solution quality.
I
II
III
IV
V
VI
VII
Instance
Number of stations, blocks, arcs, crew segments
Minimum cost (μ)
Average cost
Avg time (sec)
Lower bound(σ)
Difference in %100×μ-σσ
p5_7D
5 7 5 6
47,193
47,193
1
32,957
43.18
p5_10D
5 10 4 6
77,691
77,726
1
60,336
28.76
p10_15D
10 15 11 14
224,186
226,845
4
187,862
19.34
p10_20D
10 20 8 13
294,595
299,021
4
248,649
18.48
p20_30D
20 30 13 25
297,952
301,013
13
243,932
22.15
p20_40D
20 40 15 25
336,651
339,876
13
267,840
25.69
p40_60D
40 60 22 45
565,954
576,906
49
446,538
26.74
p40_80D
40 80 21 45
568,089
573,991
46
446,411
27.26
p80_120D
80 120 38 86
791,072
800,660
124
614,225
28.79
p80_160D
80 160 38 89
987,646
997,005
168
791,041
24.85
p160_240D
160 240 62 169
2,214,593
2,240,989
376
1,791,395
23.62
p160_320D
160 320 72 169
2,201,347
2,221,606
320
1,765,637
24.68
p200_300D
200 300 82 216
4,043,845
4,071,617
409
3,306,843
22.29
p200_400D
200 400 81 210
1,591,058
1,607,980
463
1,203,586
32.19
p250_375D
250 375 96 261
2,518,148
2,548,918
856
1,958,093
28.60
p250_500D
250 500 104 260
1,881,881
1,905,522
723
1,445,175
30.22
p300_450D
300 450 117 311
8,919,042
8,969,957
606
7,480,671
19.23
p300_600D
300 600 115 313
10,419,523
10,453,791
744
8,782,219
18.64
p320_480D
320 480 138 333
8,172,082
8,218,034
662
6,676,505
22.40
p320_640D
320 640 138 332
2,053,295
2,077,627
900
1,516,815
35.37For each pairn,m we first construct a complete graph Kn=V,E, whose vertex set V corresponds to a set of n integer points randomly generated in a square of side 215; the length of each edge u,v∈E is equal to the Euclidean distance between vertices u and v. Also, we determine the set Et⊂E of edges in a minimum length spanning tree on Kn, as well as the set Eh⊂E of edges in the convex hull of V. Finally, we make the railroad network of the instance correspond to graph G=V,Eh∪Et.Then, crew segments are randomly created so that every edge of the network belongs to one crew segment. The swap costsv in every station v∈V is also randomly assigned in the integer range[10, 100].We create next a set ofm blocks, one after the other, verifying that each does not exceed the maximum number of swaps allowed to arrive to destination when traveling along a minimal length path. The number of cars rb, length lb, and weight wb of every block b are randomly chosen in the integer ranges [1, 100], [56, 65], and [74, 86], respectively, as these ranges are similar to those found in real instances. Each time we tentatively form a block, Step 1 of Section 4 is performed for feasibility verification.Also, for every edgee∈E, the values of L¯e, W¯e, and T¯e are randomly chosen in the ranges [7,000, 14,000] and [9,000, 18,000], [6, 12], respectively.Once random instances were generated, SA run 50 times for each. Results are displayed in columns III–V of Table8 (indeed, instance p5_7D was taken as Example 1 in Section 2).


### 5.3. Lower Bounds

Establishing good lower bounds for the optimal solution of the TDOP seems a very difficult task. However, to assess the SA performance, we propose here a lower boundσ for each solved instance; see Tables 7 and 8. To this aim we computed as explained below lower bounds for total travel cost (σ1), train start cost (σ2), train travel cost (σ3), work-event cost (σ4), and missed car cost (σ5). Thus, σ=∑j=15σj.In regard to travel cost letσ1=C4∑b∈Bψb×rb, where ψb is the length of the shortest route from ob to db. In the case of the two real instances σ1 is identical to the bound computed in [23].For the train start cost a trivial lower bound isσ2=C1×m/MB, where MB stands for the maximum number of blocks per train.Letψ1,…,ψm be an order on Ψ=ψb:b∈B, with ψj≥ψj+1, for j=1,…,m-1. Thus, for the train travel cost our proposed lower bound is σ3=C2∑j∈Jψj, where J=j:1=jmodMBand1≤j≤m. Bound σ3 slightly improves on that from [20].For every stationv∈V, let ρv be the number of blocks b such that ob=v or db=v. Then σ4=C3∑v∈Xρv/MB, where X is the set of stations belonging to a crew segment with the exclusion of its end points. As far as we know this lower bound for the work-event cost is proposed here for the first time.LetY denote the set of blocks b such that ob or db does not belong to H (refer to Section 3 for a definition of vertex set H). Thus, it is impossible to deliver any block in Y. Our lower bound for the missed car cost is then σ5=C7∑b∈Yrb. Although in practice it is not likely to get σ5>0, instanceData Set 02 contains some blocks belonging to Y.Thus, in regard to the best solutions found for instancesExample,Data Set 1, andData Set 2 (see Table 7) our lower bound σ yields differences of 36.14%, 20.79%, and 14.57%, respectively, namely, 23.83% on average. Column VII of Table 8 shows a similar behavior of σ for the synthetic instances. These facts lead us to believe that σ, although the highest lower bound known to us is far from the true optimum.


## 5.1. Testing SA on Specific Instances

Employing parametersθ = 1000 and α = 0.9, we compared SA results on instancesExample,Data Set 1, andData Set 2, as can be seen in Table 7, where computation times are also shown to give an idea of the performance of the implementation, although the platforms used were not the same. So far [18] had provided—using a mixed integer programming model—the best results for the two real instances but at the expense of very high computing time. On the other hand, the network-oriented formulation in [21] yielded the fastest algorithm to date.Table 7
Performance comparison of our SA approach and other methods; computing times are given in seconds. The bottom row shows a lower bound on the optimal cost, computed as explained in Section5.3. (all figures rounded to integers).
Number of
Example
Data Set 1
Data Set 2
Nodes
4
94
221
Blocks
5
239
369
Arcs
5
134
294
Crew Segments
5
154
154
cost
time
cost
time
cost
time
[21]
—
2,043,471
45
3,187,999
225
[20]
—
2,032,516
2,201
3,188,500
2,067
[18]
—
2,018,644
80,000
3,152,019
75,000
[23]
14,916
0
2,069,752
342
3,240,177
2,700
SA
14,916
1
2,005,514
181
3,170,815
1,991
Lower boundσ
10,956
1,660,361
2,751,213Other approaches include column-generation [23], with better results than those found in [22], and column-generation combined with tabu search [20] improving on [19]. In the case of instanceExample the only published results come from [23]. The best results found with SA were 1,999,315 with θ = 8000 and α = 0.99, in 19,819 seconds for instanceData Set 1, and 3,155,267 with θ = 10,000 and α = 0.95 in 41,233 seconds for instanceData Set 2, with the more relevant results found in the literature; our results yield lower cost forData Set 1 (-0.95%), same cost forExample, and higher cost forData Set 2 (+0.10%).


## 5.2. Testing SA on Random Instances

A set of 20 random instances was generated as follows with the numbern of stations and number m of blocks shown in column II of Table 8. All random choices were made with uniform distribution.Table 8
Relevant data (columns I, II) and results (columns III, IV, and V) of 50 runs of SA on 20 random instances. A lower bound—explained in Section5.3—on the optimal solution cost is shown in column VI. The last column is an indicator of the solution quality.
I
II
III
IV
V
VI
VII
Instance
Number of stations, blocks, arcs, crew segments
Minimum cost (μ)
Average cost
Avg time (sec)
Lower bound(σ)
Difference in %100×μ-σσ
p5_7D
5 7 5 6
47,193
47,193
1
32,957
43.18
p5_10D
5 10 4 6
77,691
77,726
1
60,336
28.76
p10_15D
10 15 11 14
224,186
226,845
4
187,862
19.34
p10_20D
10 20 8 13
294,595
299,021
4
248,649
18.48
p20_30D
20 30 13 25
297,952
301,013
13
243,932
22.15
p20_40D
20 40 15 25
336,651
339,876
13
267,840
25.69
p40_60D
40 60 22 45
565,954
576,906
49
446,538
26.74
p40_80D
40 80 21 45
568,089
573,991
46
446,411
27.26
p80_120D
80 120 38 86
791,072
800,660
124
614,225
28.79
p80_160D
80 160 38 89
987,646
997,005
168
791,041
24.85
p160_240D
160 240 62 169
2,214,593
2,240,989
376
1,791,395
23.62
p160_320D
160 320 72 169
2,201,347
2,221,606
320
1,765,637
24.68
p200_300D
200 300 82 216
4,043,845
4,071,617
409
3,306,843
22.29
p200_400D
200 400 81 210
1,591,058
1,607,980
463
1,203,586
32.19
p250_375D
250 375 96 261
2,518,148
2,548,918
856
1,958,093
28.60
p250_500D
250 500 104 260
1,881,881
1,905,522
723
1,445,175
30.22
p300_450D
300 450 117 311
8,919,042
8,969,957
606
7,480,671
19.23
p300_600D
300 600 115 313
10,419,523
10,453,791
744
8,782,219
18.64
p320_480D
320 480 138 333
8,172,082
8,218,034
662
6,676,505
22.40
p320_640D
320 640 138 332
2,053,295
2,077,627
900
1,516,815
35.37For each pairn,m we first construct a complete graph Kn=V,E, whose vertex set V corresponds to a set of n integer points randomly generated in a square of side 215; the length of each edge u,v∈E is equal to the Euclidean distance between vertices u and v. Also, we determine the set Et⊂E of edges in a minimum length spanning tree on Kn, as well as the set Eh⊂E of edges in the convex hull of V. Finally, we make the railroad network of the instance correspond to graph G=V,Eh∪Et.Then, crew segments are randomly created so that every edge of the network belongs to one crew segment. The swap costsv in every station v∈V is also randomly assigned in the integer range[10, 100].We create next a set ofm blocks, one after the other, verifying that each does not exceed the maximum number of swaps allowed to arrive to destination when traveling along a minimal length path. The number of cars rb, length lb, and weight wb of every block b are randomly chosen in the integer ranges [1, 100], [56, 65], and [74, 86], respectively, as these ranges are similar to those found in real instances. Each time we tentatively form a block, Step 1 of Section 4 is performed for feasibility verification.Also, for every edgee∈E, the values of L¯e, W¯e, and T¯e are randomly chosen in the ranges [7,000, 14,000] and [9,000, 18,000], [6, 12], respectively.Once random instances were generated, SA run 50 times for each. Results are displayed in columns III–V of Table8 (indeed, instance p5_7D was taken as Example 1 in Section 2).


## 5.3. Lower Bounds

Establishing good lower bounds for the optimal solution of the TDOP seems a very difficult task. However, to assess the SA performance, we propose here a lower boundσ for each solved instance; see Tables 7 and 8. To this aim we computed as explained below lower bounds for total travel cost (σ1), train start cost (σ2), train travel cost (σ3), work-event cost (σ4), and missed car cost (σ5). Thus, σ=∑j=15σj.In regard to travel cost letσ1=C4∑b∈Bψb×rb, where ψb is the length of the shortest route from ob to db. In the case of the two real instances σ1 is identical to the bound computed in [23].For the train start cost a trivial lower bound isσ2=C1×m/MB, where MB stands for the maximum number of blocks per train.Letψ1,…,ψm be an order on Ψ=ψb:b∈B, with ψj≥ψj+1, for j=1,…,m-1. Thus, for the train travel cost our proposed lower bound is σ3=C2∑j∈Jψj, where J=j:1=jmodMBand1≤j≤m. Bound σ3 slightly improves on that from [20].For every stationv∈V, let ρv be the number of blocks b such that ob=v or db=v. Then σ4=C3∑v∈Xρv/MB, where X is the set of stations belonging to a crew segment with the exclusion of its end points. As far as we know this lower bound for the work-event cost is proposed here for the first time.LetY denote the set of blocks b such that ob or db does not belong to H (refer to Section 3 for a definition of vertex set H). Thus, it is impossible to deliver any block in Y. Our lower bound for the missed car cost is then σ5=C7∑b∈Yrb. Although in practice it is not likely to get σ5>0, instanceData Set 02 contains some blocks belonging to Y.Thus, in regard to the best solutions found for instancesExample,Data Set 1, andData Set 2 (see Table 7) our lower bound σ yields differences of 36.14%, 20.79%, and 14.57%, respectively, namely, 23.83% on average. Column VII of Table 8 shows a similar behavior of σ for the synthetic instances. These facts lead us to believe that σ, although the highest lower bound known to us is far from the true optimum.


## 6. Conclusion

In this paper we proposed a simulated annealing approach for the Train Design Optimization Problem. This approach was computationally tested with three instances well-known in the specialized literature, and with 20 instances randomly generated by us, of sizes up to 320 stations and 640 car blocks. Its results show superiority—in regard to the objective function value—over those obtained elsewhere for instanceData Set 01, and competitivity (in fact the runner-up) for instanceData Set 02, both results using reasonable computing resources.We think however that much research, be it theoretical or empirical, must still be carried out to successfully deal with this most challenging, combinatorial optimization problem. The TDOP being so fundamental in the railroad industry, there is a need to develop new heuristics or metaheuristics, which, working alone or hybridized, improve the best results obtained so far. Also, a pending and difficult task is to produce efficient procedures that yield good lower bounds for the TDOP objective function, so as to help assess the performance of proposed approaches.



---

*Source: 4703106-2017-08-10.xml*