Integrated Optimization of Service-Oriented Train Plan and Schedule on Intercity Rail Network with Varying Demand

Abstract

For a better service level of a train operating plan, we propose an integrated optimization method of train planning and train scheduling, which generally are optimized, respectively. Based on the cost analysis of both passengers travelling and enterprises operation, and the constraint analysis of trains operation, we construct a multiobjective function and build an integrated optimization model with the aim of reducing both passenger travel costs and enterprise operating costs. Then, a solving algorithm is established based on the simulated annealing algorithm. Finally, using as an example the Changzhutan intercity rail network, as an example we analyze the optimized results and the influence of the model parameters on the results.

Academic Editor:Govindan Kannan

School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China

Received 8 December 2014; Accepted 21 January 2015; 12 April 2015

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

A passenger train operating plan (TOP) is not only the basis of train organization and station operation for enterprise, but also the foundation of train choice for passengers travelling by rail transit (e.g., an urban railway system, intercity railway system, and high-speed railway system). A high-quality TOP directly contributes to improving the level of passenger service and boosts enterprise operation efficiency. The TOP generally should arrange origin and destination stations, run routes, intermediate stations, vehicle numbers, and schedule for trains. More broadly, it also determines the crew scheduling and usage plan of the locomotive or electric multiple units (EMUs). However, the latter part of the TOP is not considered in this paper. Due to the complexity and difficulty of solving the TOP of a large-scale rail network, the TOP problem is usually divided into two subproblems: the train planning problem and train scheduling problem, which are solved one by one. Firstly, the train plan is optimized to arrange the origin and destination station, run route, intermediate stations, vehicle number, and frequency of trains with the aim of improving both the passenger travel benefit and enterprise operation profit. And then the train scheduling problem is solved in order to schedule each train's departure and arrival time at each station based on the former optimized train plan.

Most research on the train planning problem so far concentrates on designing an optimization model and its algorithm, aiming at getting a better service-level and high-benefit train plan with constraints of line and station capacity and rail resources (e.g., maximum departure number per day and available vehicles, etc.). Anthony [1] gave a basic frame for solving the passenger train planning problem as early as 1965. Chang et al. [2] proposed a multiobjective model and its algorithm of a train plan with the aim of reducing both enterprise operating costs and passenger travel cost. Yaghini et al. [3] took into account the passenger direct ratio besides travel costs in optimizing train plan. Wang et al. [4] provided an optimization method for a periodic train plan. Recently, some studies [5-7] combined the passenger train choice problem into the train plan problem and accordingly proposed the bilevel programming method of a train plan based on the leader-following relation between formulating a train plan and passenger train choice. For more examples of train plan optimization, see Schmidt and Schöbel [8], Goossens et al. [9], and Schöbel and Scholl [10].

The train scheduling problem is to generally find an optimal or satisfying train timetable with a given optimization objective, subject to a lot of operational and safety constraints (e.g., arrival and departure headway requirements). A branch-and-bound algorithm, Lagrangian relaxation algorithm, and simulation method are widespread used to solve this problem. Higgins et al. [11] developed a branch-and-bound solution framework and some heuristic techniques to find feasible train timetables, and Zhou and Zhong [12] further incorporated some effective rules into the branch-and-bound algorithm for improving its solving efficiency. Brannlund et al. [13] proposed a Lagrangian relaxation approach to find a profit-maximizing train timetable. Dorfman and Medanic [14] proposed an effective simulation approach called TAS to solve the large-scale and real-world train scheduling problem, and Li et al. [15] and Xu et al. [16] further improved TAS by introducing some modified rules and efficient strategies inserted into it. For more studies of train scheduling, refer to Jong et al. [17], Sahana et al. [18], Yalçinkaya and Mirac Bayhan [19], and Zhou et al. [20].

Obviously, optimizing a train plan and train schedule successively has some drawbacks in enhancing the passenger service level and satisfying varying travel demands of intercity rail. First, with the lack of time information, when optimizing a train plan, it is impossible to describe in detail passenger transfer time, wait time, and in-vehicle time determined exactly by a train timetable. Thus, improving passenger travel time is beyond the train plan problem to some extent. And the optimization of a train timetable generally aims to minimize the total travel time of trains, but not of passengers, because it has no passenger volume information about the train. Moreover, this two-stage method cannot make trains' time distribution fit passenger demand distribution better in one day. To overcome the drawbacks thoroughly, combining the train plan and train schedule as a whole, that is, TOP, an integrated optimization of them is an effective alternative. Compared with the two-stage approach, the integrated optimization method has the following differences.

(1) It is to optimize train plan and train schedule simultaneously based on a rail network and its passengers demand distributions, while the two-stage method is firstly to determine a train plan which is taken as one input when scheduling trains latter. Thus, the integrated method has the decision variables and constraints of both train planning and train scheduling.

(2) Although reducing passengers travel costs and enterprise operating costs is taken as the objective in both two methods, their calculation is based on a train schedule in the integrated method while that is only based on a train plan in the two-stage method.

It should be noted that the efficiency of this integrated optimization is not a knotty obstacle for an intercity rail network with a relatively small scale owing to the improvement of computer speed and the development of modern optimization algorithm.

The main contributions of this paper are as follows.

(1) An integrated optimization model of train planning and scheduling is built to minimize both passenger travel costs and enterprise operating costs. It can more exactly and fully describe passenger travel costs.

(2) A solving algorithm based on simulated annealing algorithms (SA) is designed to solve the proposed optimization model.

The remainder of this paper is organized as follows. In Section 2, we describe the problem of TOP optimization and analyze passenger travel costs and enterprise operating costs. In Section 3, we discuss the constraints and multiobjective function and present the integrated optimization model of TOP. In Section 4, we design a solving algorithm based on SA. Moreover, the case of the Changzhutan intercity rail network is used to illustrate the application of the proposed model and algorithm and also to analyze the impact of their parameters on passenger travel costs and enterprise operating costs in Section 5. Finally, the conclusion and further study are given in Section 6.

2. Problem Description

An intercity rail network [figure omitted; refer to PDF] is represented by a set of stations [figure omitted; refer to PDF] and a set of double-track sections [figure omitted; refer to PDF] in which [figure omitted; refer to PDF] and [figure omitted; refer to PDF] show, respectively, the down and up direction sections connecting station [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . The mileage of [figure omitted; refer to PDF] is denoted by [figure omitted; refer to PDF] or by [figure omitted; refer to PDF] .

Intercity rail passenger flow has the obvious characteristic of fluctuating with the time of day, and it has peak hours and low hours of travel. So, it is called varying demand in this paper. The varying demand from origin [figure omitted; refer to PDF] to destination [figure omitted; refer to PDF] in one day is denoted by a function of time [figure omitted; refer to PDF] denoted by [figure omitted; refer to PDF] .

For simplification, the following assumptions are made based on the actual condition of intercity railway in this paper.

(A1) The research range is limited to an independent intercity rail network and passenger total demand of one day among stations is not affected by travel costs determined by the TOP.

(A2) The intercity rail network provides only one speed type (e.g., 200 km/h) of train servicing passengers, and all vehicles have the same capacity for passengers.

(A3) The network capacity is enough to satisfy passengers travelling by the mileage-shortest route; thus, all passengers can travel with those routes.

(A4) Passengers get on the train according to their arriving order.

The TOP can be expressed as a set of trains [figure omitted; refer to PDF] , and each train is made up by route, vehicle number, and schedule. The route of train [figure omitted; refer to PDF] is denoted by [figure omitted; refer to PDF] , which is composed of a set of stations or a set of sections, the vehicle number of train [figure omitted; refer to PDF] is expressed by [figure omitted; refer to PDF] , and the sequences of departure time and arrival time arranged by ascending order are denoted by [figure omitted; refer to PDF] , respectively. Meanwhile, the arrival time and departure time of train [figure omitted; refer to PDF] at station [figure omitted; refer to PDF] are denoted by [figure omitted; refer to PDF] , respectively.

2.1. Analysis of Passenger Travel Costs

Passenger travel costs mainly consist of wait time at the origin station, transfer time including necessary walking time and wait time during the process from getting off the train to getting on board of another train at the transfer station, in-vehicle time, and fare spending. Considering the additional inconvenience produced by transfer, an additional cost is imposed on transfer passengers besides transfer time. This additional cost contributes to avoiding transfer for passengers when they have other nontransfer paths for travelling. Under the assumption (A3), passenger fare spending calculated by travel mileage multiplying price rate per mileage is a constant and is not considered in this paper.

Wait time at the origin station depends on passengers' arriving time and boarding time. When passengers arrive at station [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] and wait there until boarding train [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] , their wait time [figure omitted; refer to PDF] can be calculated by [figure omitted; refer to PDF]

When passengers transfer in station [figure omitted; refer to PDF] with train [figure omitted; refer to PDF] and transfer out with train [figure omitted; refer to PDF] , their transfer time [figure omitted; refer to PDF] can be determined as follows according to departure time [figure omitted; refer to PDF] of train [figure omitted; refer to PDF] and arrival time [figure omitted; refer to PDF] of train [figure omitted; refer to PDF] : [figure omitted; refer to PDF] Moreover, their additional cost of transfer [figure omitted; refer to PDF] can be given as [figure omitted; refer to PDF] multiple of their transfer time; namely, [figure omitted; refer to PDF]

In-vehicle time comprises train operation time and dwell time of each intermediate station. When passengers travel with train [figure omitted; refer to PDF] from station [figure omitted; refer to PDF] to station [figure omitted; refer to PDF] , their in-vehicle time [figure omitted; refer to PDF] spent on this train is [figure omitted; refer to PDF]

Passenger travel cost is the total of wait time, transfer time and transfer additional cost, and in-vehicle time. For passengers travelling by path [figure omitted; refer to PDF] from station [figure omitted; refer to PDF] to station [figure omitted; refer to PDF] , their travel cost [figure omitted; refer to PDF] is [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the travel path of passengers, [figure omitted; refer to PDF] is the first train for passengers of path [figure omitted; refer to PDF] travelling, and [figure omitted; refer to PDF] shows passengers of path [figure omitted; refer to PDF] needing to transfer from train [figure omitted; refer to PDF] to train [figure omitted; refer to PDF] at station [figure omitted; refer to PDF] . And [figure omitted; refer to PDF] means that passengers of path [figure omitted; refer to PDF] have to travel by train [figure omitted; refer to PDF] when going from station [figure omitted; refer to PDF] to station [figure omitted; refer to PDF] .

2.2. Analysis of Enterprise Operating Costs

With the action of assumptions (A1) and (A3), an intercity rail enterprise has a fixed ticket income, the product of passenger flow, and its corresponding fare. Thus, the operating costs are considered only in this paper. Operating cost is the sum of the following three components: that is, train organization cost [figure omitted; refer to PDF] , rail line cost [figure omitted; refer to PDF] , and rail vehicle cost [figure omitted; refer to PDF] . It is represented as [figure omitted; refer to PDF]

Train organization cost is the fee spent mainly on the train crew and the organizing operation at the train's origin station. It is the product of train number [figure omitted; refer to PDF] and the organization cost [figure omitted; refer to PDF] per train; namely, [figure omitted; refer to PDF]

Rail line cost is generated for line maintenance and is directly related to the total travel mileage of a train. It can be expressed as [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the maintenance cost per kilometer line and [figure omitted; refer to PDF] is the travel mileage of train [figure omitted; refer to PDF] .

Vehicle cost is used for vehicle maintenance. It can be calculated as [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the fixed cost for each vehicle maintenance and [figure omitted; refer to PDF] is the average maintenance cost of vehicle per mileage.

3. Optimization Model

3.1. Analysis of Constraints

Train origin and destination must be a technical station that has the areas and facilities for a train's technical operation and servicing work. The set of technical stations on an intercity rail network is denoted by [figure omitted; refer to PDF] , and then the origin station [figure omitted; refer to PDF] and destination station [figure omitted; refer to PDF] of train [figure omitted; refer to PDF] must be included in set [figure omitted; refer to PDF] ; namely, [figure omitted; refer to PDF]

The vehicle number of a train should be set for an upper bound limited by the length of station track. The train vehicle number of upper bound for all travel routes is expressed as [figure omitted; refer to PDF] . That is, [figure omitted; refer to PDF] Meanwhile, the vehicle number of a train should not be less than the number that makes this train operate without profit when it reaches its passenger capacity. When train [figure omitted; refer to PDF] reaches its passenger capacity, its operating cost [figure omitted; refer to PDF] and ticket income [figure omitted; refer to PDF] can be given, respectively, by [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the fare rate per passenger per kilometer and [figure omitted; refer to PDF] is the passenger capacity of vehicle.

To make train [figure omitted; refer to PDF] profitable, its ticket income [figure omitted; refer to PDF] should be more than the operating cost [figure omitted; refer to PDF] ; that is, [figure omitted; refer to PDF] Based on that, the vehicle number of train [figure omitted; refer to PDF] should satisfy another constraint as [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the symbol of rounding up.

The train schedule should meet the constraint of operating time period from time [figure omitted; refer to PDF] to time [figure omitted; refer to PDF] . That is, [figure omitted; refer to PDF]

Two same-direction trains departing from or arriving at the same station should satisfy the minimum safety time interval; namely, [figure omitted; refer to PDF] where [figure omitted; refer to PDF] are separately the minimum safety time interval between departure operations and between arrival operations.

In addition, a train's departure and arrival time in section should meet the constraint of minimum total run time. The technical speed of the train is denoted by [figure omitted; refer to PDF] , and train additional times for starting and stopping in section [figure omitted; refer to PDF] are expressed by [figure omitted; refer to PDF] , respectively. That is, [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the symbol of describing whether train [figure omitted; refer to PDF] should stop at station [figure omitted; refer to PDF] or not. If train [figure omitted; refer to PDF] stops at station [figure omitted; refer to PDF] , then [figure omitted; refer to PDF] ; otherwise, [figure omitted; refer to PDF] .

Meanwhile, a train's arrival and departure time at the station should satisfy the constraint of minimum dwell time related to the volume of passengers getting on and getting off train. That is, [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the minimum dwell time of train [figure omitted; refer to PDF] at station [figure omitted; refer to PDF] for ensuring that passengers get on and off safely. It can be given by [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the volume of passengers getting on and getting off train [figure omitted; refer to PDF] at station [figure omitted; refer to PDF] , [figure omitted; refer to PDF] is the maximum number of passengers for getting on and off the train in one minute, and [figure omitted; refer to PDF] is the parameter affecting the increase of train dwell time.

3.2. Objective Function and Optimization Model

The cost minimization of intercity rail transit system, that is, minimizing both enterprise operating costs and passenger travel costs, is mostly used as the optimization objective of the train plan in many studies [2, 5-7]. In this paper, it is also adopted as the optimization objective of the TOP, but passenger travel costs including not only in-vehicle time, but also wait time and transfer time, are more full-scale and are calculated more exactly.

The objective function is expressed as the weighted sum of an enterprise's operating costs and passengers' travel costs. That is, [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the weight parameter balancing the enterprise's operating costs and passengers' travel costs, [figure omitted; refer to PDF] is the average time value of passengers, and [figure omitted; refer to PDF] is the volume of passengers of path [figure omitted; refer to PDF] from origin [figure omitted; refer to PDF] to destination [figure omitted; refer to PDF] .

Based on the above analysis, with the decision variables of train set [figure omitted; refer to PDF] , the optimization model (M1) of the TOP consists of the objective function (20) and all constraints (10), (11), and (14) through (18). It should be noted that model (M1) has to determine not only each train's route, vehicle number, and schedule, but also train number.

4. Optimization Algorithm Based on SA

4.1. Algorithm for Passenger Train Choice and Calculation of Passenger Travel Costs

All passengers have to obey the rule of time-space priority when choosing a train. In other words, passengers arriving at a station earlier have the priority of boarding the train, but they also have to yield to those on the train as to the limit of train capacity. For that, passengers are distributed to trains according to the ascending order of train departure and arrival time treated as the decision-making time.

At the decision-making time of a train departing, which passengers waiting in the station will choose this train and how many of them can get on it should be determined. Passengers waiting in the station can be divided into two parts, original departing and transferring passengers. The sets of original departing passengers and transferring passengers at station [figure omitted; refer to PDF] are denoted by [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , respectively. For original departing passengers [figure omitted; refer to PDF] , their earliest arriving time is [figure omitted; refer to PDF] and destination is [figure omitted; refer to PDF] . And for transferring passengers [figure omitted; refer to PDF] , their transferring in time is [figure omitted; refer to PDF] , destination is [figure omitted; refer to PDF] , and their number is [figure omitted; refer to PDF] .

When train [figure omitted; refer to PDF] departs from station [figure omitted; refer to PDF] , passengers whose cost-shortest path from station [figure omitted; refer to PDF] to their destination contains train [figure omitted; refer to PDF] need to get on it, but the number of those who can get on board successfully depends on the empty seat number [figure omitted; refer to PDF] of train [figure omitted; refer to PDF] . Based first-arriving-first-boarding principle, the number of passengers getting on the train is given as [figure omitted; refer to PDF] where [figure omitted; refer to PDF] are the sets of original departing passengers and transferring passengers needing to get on train [figure omitted; refer to PDF] at station [figure omitted; refer to PDF] and [figure omitted; refer to PDF] is the time boundary deciding what time passengers arriving can get on board of the train. It means that passengers arriving before [figure omitted; refer to PDF] can get on the train, but those arriving after this time cannot get on board, because there are no empty seats left. When the passenger total number of [figure omitted; refer to PDF] is less than [figure omitted; refer to PDF] , then [figure omitted; refer to PDF] . Otherwise, the value of [figure omitted; refer to PDF] can be calculated by solving the following equality: [figure omitted; refer to PDF]

The wait time, transfer time, and additional cost for transfer at station [figure omitted; refer to PDF] of passengers getting on train [figure omitted; refer to PDF] can be calculated by [figure omitted; refer to PDF]

At the decision-making time of train [figure omitted; refer to PDF] arriving station [figure omitted; refer to PDF] , passengers having arrived at their destination or whose cost-shortest path from station [figure omitted; refer to PDF] to their destination does not include train [figure omitted; refer to PDF] again have to get off. The set of passengers arriving at station [figure omitted; refer to PDF] with train [figure omitted; refer to PDF] is denoted by [figure omitted; refer to PDF] , with the subset of those getting off the train being denoted by [figure omitted; refer to PDF] . For passengers [figure omitted; refer to PDF] , their destination is [figure omitted; refer to PDF] , and their number is [figure omitted; refer to PDF] . The in-vehicle time of passengers [figure omitted; refer to PDF] from the rear station [figure omitted; refer to PDF] to station [figure omitted; refer to PDF] can be calculated by [figure omitted; refer to PDF] And the total of their in-vehicle time is given as [figure omitted; refer to PDF]

Based on the above analysis, Algorithm 1 for passenger train choice and calculation of passenger travel costs is described as follows.

Algorithm 1.

Consider the following.

Step 1 (initialization). Set [figure omitted; refer to PDF] and [figure omitted; refer to PDF] of each train and [figure omitted; refer to PDF] of each station. Find all original departing passengers [figure omitted; refer to PDF] of each station and let [figure omitted; refer to PDF] as the total travel costs of passengers.

Step 2 (find the earliest decision-making time [figure omitted; refer to PDF] ). If [figure omitted; refer to PDF] corresponds to departure time [figure omitted; refer to PDF] , then go to Step 2.1; otherwise, if [figure omitted; refer to PDF] corresponds to arrival time [figure omitted; refer to PDF] , then go to Step 2.2.

Step 2.1 . Determine boarding passengers [figure omitted; refer to PDF] , [figure omitted; refer to PDF] and their number [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] ), [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] ). Then, calculate their wait time [figure omitted; refer to PDF] , transfer time [figure omitted; refer to PDF] , and transfer additional cost [figure omitted; refer to PDF] . Set [figure omitted; refer to PDF] and update empty seats number [figure omitted; refer to PDF] , transferring passengers [figure omitted; refer to PDF] , original departing passengers [figure omitted; refer to PDF] , and train passengers [figure omitted; refer to PDF] . Go to Step 3.

Step 2.2 . Determine getting-off passengers [figure omitted; refer to PDF] and calculate their in-vehicle time [figure omitted; refer to PDF] . Then, set [figure omitted; refer to PDF] and update empty seats number [figure omitted; refer to PDF] , transferring passengers [figure omitted; refer to PDF] and train passengers [figure omitted; refer to PDF] .

Step 3 (judge whether there are other decision-making times or not). If yes, then return to Step 2. Otherwise, [figure omitted; refer to PDF] is the passengers' total travel costs, and terminate this algorithm.

4.2. The General Algorithm for Optimizing TOP

4.2.1. Generation of an Initial Solution of TOP

Trains of the initial solution are created one by one based on the varying demand on the network. A new train is organized with departing time [figure omitted; refer to PDF] when the product of its boarding passengers' number [figure omitted; refer to PDF] and their average wait time [figure omitted; refer to PDF] including wait time and transfer wait time at a technical station satisfies [figure omitted; refer to PDF] and its vehicle number is determined by [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the control parameter for organizing one new train and [figure omitted; refer to PDF] is the average usage rate of train capacity.

From formula (26), we know that a train should be organized either when there are enough passengers waiting for boarding, or when some passengers have waited for too long.

The newly created train is assumed to stop at all the passed stations during the process of generating the initial solution. When it arrives at the next technical station, if the sum of passengers waiting to get on and those on the train is more than [figure omitted; refer to PDF] percent of its capacity, it moves forward along the direction with the largest value of [figure omitted; refer to PDF] . Otherwise, it stops here as its destination.

4.2.2. Generation of a Neighbor Solution of TOP

A new solution is generated by changing the train's route, stop stations, vehicle number, and starting time of the current solution with the probability method. As for the train route, it is adjusted by adding some new sections to its front and end or removing partial sections depending on train's operating costs and passenger volume of them. Two Boolean variables [figure omitted; refer to PDF] and [figure omitted; refer to PDF] both created by Bernoulli distribution are, respectively, used to indicate whether partial sections should be added to the train route and removed from it. If [figure omitted; refer to PDF] , the corresponding sections are added to the train route, and when [figure omitted; refer to PDF] , the corresponding sections are removed from it. As for the train sections [figure omitted; refer to PDF] between two technical stations, the probability of [figure omitted; refer to PDF] is given by [figure omitted; refer to PDF] where [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] are the passenger-kilometer, passengers' average travel costs, and operating cost in train section [figure omitted; refer to PDF] respectively, and [figure omitted; refer to PDF] is the current temperature.

For new sections [figure omitted; refer to PDF] , the probability of [figure omitted; refer to PDF] is given by [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the number of passengers transferring from or transferring to the current train and [figure omitted; refer to PDF] is their average transfer cost.

The alteration of train stop stations is also based on a Bernoulli distribution. For station [figure omitted; refer to PDF] of train [figure omitted; refer to PDF] , the probability of a train's stop is given by [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the number of passengers getting on and off the train and [figure omitted; refer to PDF] is the average travel cost of passengers getting on the train at station [figure omitted; refer to PDF] .

The modification of both the train vehicle number and starting time is given as follows: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] are the value of current solution and neighboring solution, respectively, and [figure omitted; refer to PDF] is generated by the next probability density function, which makes the vehicle number and starting time of one train with low benefit or efficiency have a high adjustment chance. Consider [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is determined by the indexes of train [figure omitted; refer to PDF] . For train vehicle number and starting time, it is given, respectively, by [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the passenger kilometer, [figure omitted; refer to PDF] is the average operating cost per vehicle, [figure omitted; refer to PDF] is the total wait time and transfer cost, and [figure omitted; refer to PDF] is the number of passengers on the train.

In formulas (28), (29), (30), and (32), the calculation of their probabilities is mainly based on train's service level, passenger volume, operating costs, and the current temperature as a parameter of SA, and the higher the current temperature is, the larger their probabilities are.

With the above generation method of an initial solution and a neighborhood solution, the general Algorithm 2 based on SA for optimizing TOP is described as follows.

Algorithm 2.

Consider the following.

Step 1 (initialization). Generate the initial feasible solution [figure omitted; refer to PDF] under the initial temperature [figure omitted; refer to PDF] and then calculate the objective value [figure omitted; refer to PDF] based on simulating passenger train choice and calculating passenger travel costs with Algorithm 1. Set [figure omitted; refer to PDF] as the current running times of the outer cycle. Let [figure omitted; refer to PDF] be the current running times of the inner cycle and let [figure omitted; refer to PDF] be the current temperature. Set [figure omitted; refer to PDF] as the minimum temperature of the outer cycle and [figure omitted; refer to PDF] as the number of iterations at each temperature.

Step 2 (construction of neighborhood). Generate a new solution [figure omitted; refer to PDF] and calculate its objective value corresponding to [figure omitted; refer to PDF] based on simulating passenger train choice and calculating passenger travel costs with Algorithm 1.

Step 3 (metropolis sampling). When [figure omitted; refer to PDF] , then set [figure omitted; refer to PDF] ; otherwise, if [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] is a random number in [figure omitted; refer to PDF] and [figure omitted; refer to PDF] is the difference between them, the current and optimal solution), then let [figure omitted; refer to PDF] . Then, set [figure omitted; refer to PDF] .

Step 4 (test of the termination criterion of the inner cycle). If [figure omitted; refer to PDF] , terminate the inner cycle and let [figure omitted; refer to PDF] ; otherwise, return to Step 2.

Step 5 (cooling schedule). Calculate the temperature [figure omitted; refer to PDF] .

Step 6 (test of the termination criterion of the outer cycle). When [figure omitted; refer to PDF] , terminate this algorithm and output the optimal solution; otherwise, return to Step 2.

5. Numerical Studies in Changzhutan Intercity Rail Network

The Changzhutan intercity rail network in the cluster including the cities of Changsha, Zhuzhou, and Xiangtan of China is planned to be completed in 2016. It consists of 21 stations and has the total length of 96 km. The above algorithm is developed with computer language C# on the platform of Microsoft Visual Studio.net and runs on the computer with the system of Microsoft Windows XP (Home Edition), RAM configuration of Pentium(R) Dual-Core CPU E5800, 3.19 GHz, 2.96 GB. The values of parameters in model (M1) and its solving algorithm are given in Tables 1 and 2, respectively.

Table 1: Parameter values of model (M1).

Symbol	Value	Unit	Symbol	Value	Unit
[figure omitted; refer to PDF]	2.0	-	[figure omitted; refer to PDF]	4200	¥/vehicle
[figure omitted; refer to PDF]	25000	¥/train	[figure omitted; refer to PDF]	6.5	¥/vehicle·km
[figure omitted; refer to PDF]	31.5	¥/train·km	[figure omitted; refer to PDF]	10	Vehicle
[figure omitted; refer to PDF]	2.5	¥/passenger·km	[figure omitted; refer to PDF]	80	Passenger/vehicle
[figure omitted; refer to PDF]	6:30	-	[figure omitted; refer to PDF]	22:00	-
[figure omitted; refer to PDF]	6	Min	[figure omitted; refer to PDF]	8	Min
[figure omitted; refer to PDF]	200	Km/h	[figure omitted; refer to PDF]	1	Min
[figure omitted; refer to PDF]	1	Min	[figure omitted; refer to PDF]	200	Passenger
[figure omitted; refer to PDF]	150	Passenger/min	[figure omitted; refer to PDF]	80	¥/h

Table 2: Parameter values of algorithm.

Symbol	Value	Unit	Symbol	Value	Unit
[figure omitted; refer to PDF]	15500	Passenger·min	[figure omitted; refer to PDF]	0.5	-
[figure omitted; refer to PDF]	0.4	-	[figure omitted; refer to PDF]	1000	-
[figure omitted; refer to PDF]	1	-	[figure omitted; refer to PDF]	50	-

Firstly, some observations on the convergence process of the algorithm with the value of [figure omitted; refer to PDF] being 0.2, 0.5, and 0.8, respectively, are made. The change relations between the best objective values with the total computing times of algorithm running are shown in Figure 1. As seen from it, the objective values decline sharply with the computing time in the first 10 minutes or so for both three instances and then drop slowly until about 17 minutes. After that, they became stable, which indicates that the algorithm has converged to a better solution.

Figure 1: Convergence of the solution with different values of weight para [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

Table 3 shows the optimization results with the value of [figure omitted; refer to PDF] being 0.4, 0.6, and 0.8, respectively. From these results, passenger average wait time and each operating cost vary sharply with a different value of [figure omitted; refer to PDF] , but the differences of average transfer cost, proportion of transfer passengers, and passenger in-vehicle speed are smaller. This is because the number of operating trains rising with the increase of [figure omitted; refer to PDF] mainly determines the enterprise operating cost, and the higher the trains' departure frequency is, the shorter the wait time varying passengers have. But trains can have a high travel speed, and their arrival and departure time can connect well, no matter how many trains there are.

Table 3: Optimization results with different value of [figure omitted; refer to PDF] .

The value of weight para [figure omitted; refer to PDF]	0.4	0.6	0.8
Average wait time per passenger (min)	13.6	14.1	22.2
Average transfer time per passenger (min)	19.6	20.2	21.5
Average transfer additional cost per passenger (min)	39.2	40.4	43.0
The proportion of transfer passenger (%)	11.3	12.5	12.2
Passenger in-vehicle speed (km/h)	172.4	171.6	172.8
Train organization cost (¥)	3550000	3175000	2725000
Rail line cost (¥)	237069	231030	206010
Rail vehicle cost (¥)	458272	435136	334520

For different values of [figure omitted; refer to PDF] , the percentage distributions of passenger wait time are shown in Figure 2. As we can see, regardless of [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , or [figure omitted; refer to PDF] , their passenger percentage distributions are similar to a normal distribution. But their wait time with the maximum percentage increases from 10.2 min to 11.8 min and then to 18.3 min with the increase of [figure omitted; refer to PDF] . The wait time of 75% of the passengers is mainly concentrated in 0 to 16 min both when [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , and that of 80% of the passengers is located in 0 to 20 min while [figure omitted; refer to PDF] . The maximum wait time of these three cases is 30 min, which is the ultimate value passengers can bear.

Figure 2: Distribution of passenger wait time.

[figure omitted; refer to PDF]

The percentage distributions of passenger transfer time with a different value of [figure omitted; refer to PDF] are shown in Figure 3. As passenger average walking time for each transfer is assumed to be 10 min, passenger minimum transfer times when [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] are all 10 min. As seen in Figure 3, the transfer time with the maximum percentage of about 18% does not vary with the different value of [figure omitted; refer to PDF] , and it is 16 min or so, corresponding to a passenger transfer wait time of 6 min, in all three cases. Moreover, the transfer time of 90% of the transfer passengers is mainly concentrated in 10 to 24 min. Through a comprehensive comparison of the transfer time and the transfer passenger number of three cases, it can be found that the average transfer time and total number of transfer passenger with [figure omitted; refer to PDF] are slightly less than these with [figure omitted; refer to PDF] , but their differences are very small, which indicates that the factor [figure omitted; refer to PDF] has a little effect on passenger service level of transfer.

Figure 3: Distribution of passenger transfer time.

[figure omitted; refer to PDF]

For determining the influence of weight parameter [figure omitted; refer to PDF] , the objective values composed of enterprise operating cost and passenger travel cost are calculated with different values of [figure omitted; refer to PDF] , and the change in these two partial costs for various [figure omitted; refer to PDF] is shown in Figure 4. As we can see, operating cost decreases rapidly when [figure omitted; refer to PDF] increases from 0.1 to 0.3, and later it has a relative slow-down speed as [figure omitted; refer to PDF] continues to increase. However, travel time increases smoothly with [figure omitted; refer to PDF] increasing from 0.1 to 0.9. A balance with the minimum of their total can be made between these two parts when [figure omitted; refer to PDF] is taken as a reasonable value.

Figure 4: Relationship between objective function values and weight parameter [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

6. Conclusion and Further Study

In this paper, for the integrated optimization of train planning and train scheduling, based on analyzing passenger travel costs and enterprise operating costs, we present their integrated optimization model aiming to minimize both passenger and enterprise costs with the constraints of trains operating and build a solution algorithm based on SA algorithm. From the analysis of the optimization results for the Changzhutan intercity rail network, the proposed model and algorithm can effectively obtain a satisfactory TOP, and a solution with the total minimum of operating costs and travel costs can be reached when the value of weight parameter [figure omitted; refer to PDF] is about 0.7.

As passenger demand of intercity rail largely depends on their service level under the competitive environment between railway and highway, one further research area is to optimize TOP considering this effect. Another one is to study it involving the allocation of vehicles to train, which can determine more exactly the train operating costs.

Acknowledgments

This research is supported by Natural Science Foundation of China (Grant nos. 71401182 and 71471179), Doctoral Scientific Foundation of the Ministry of Education of China (Grant no. 20120162120042), and Natural Science Foundation of Hunan Province (Grant no. 14JJ3030).

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] R. N. Anthony Planning and Control Systems: A Framework for Analysis , Harvard University, Boston, Mass, USA, 1965.

[2] Y. H. Chang, C. H. Yeh, C. C. Shen, "A multiobjective model for passenger train services planning: application to Taiwan's high-speed rail line," Transportation Research Part B: Methodological , vol. 34, no. 2, pp. 91-106, 2000.

[3] M. Yaghini, M. Momeni, M. Sarmadi, "An improved local branching approach for train formation planning," Applied Mathematical Modelling , vol. 37, no. 4, pp. 2300-2307, 2013.

[4] B. Wang, H. Yang, Z. H. Zhang, "Research on train plan of Jingjin intercity railway based on cycle timetable," Journal of the China Railway Society , vol. 29, no. 2, pp. 8-13, 2007.

[5] F. Shi, L. B. Deng, L. Huo, "Bi-level programming model and algorithm of passenger train operation plan," China Railway Science , vol. 28, no. 3, pp. 110-116, 2007.

[6] R. Borndörfer, M. Grötschel, M. E. Pfetsch, "A column-generation approach to line planning in public transport," Transportation Science , vol. 41, no. 1, pp. 123-132, 2007.

[7] B. H. Park, Y.-I. Seo, S.-P. Hong, H.-L. Rho, "Column generation approach to line planning with various halting patterns-application to the Korean high-speed railway," Asia-Pacific Journal of Operational Research , vol. 30, no. 4, pp. 134-151, 2013.

[8] M. Schmidt, A. Schöbel, "The complexity of integrating routing decisions in public transportation models," in Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS '10), vol. 14, pp. 156-169, September 2010.

[9] J.-W. Goossens, S. van Hoesel, L. Kroon, "A branch-and-cut approach for solving railway line-planning problems," Transportation Science , vol. 38, no. 3, pp. 379-393, 2004.

[10] A. Schöbel, S. Scholl, "Line planning with minimal traveling time," in Proceedings of the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS '05), Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, 2005.

[11] A. Higgins, E. Kozan, L. Ferreira, "Optimal scheduling of trains on a single line track," Transportation Research Part B: Methodological , vol. 30, no. 2, pp. 147-161, 1996.

[12] X. Zhou, M. Zhong, "Single-track train timetabling with guaranteed optimality: branch-and-bound algorithms with enhanced lower bounds," Transportation Research Part B: Methodological , vol. 41, no. 3, pp. 320-341, 2007.

[13] U. Brannlund, P. O. Lindberg, A. Nõu, J.-E. Nilsson, "Railway timetabling using Lagrangian relaxation," Transportation Science , vol. 32, no. 4, pp. 358-369, 1998.

[14] M. J. Dorfman, J. Medanic, "Scheduling trains on a railway network using a discrete event model of railway traffic," Transportation Research Part B: Methodological , vol. 38, no. 1, pp. 81-98, 2004.

[15] F. Li, Z. Y. Gao, K. P. Li, L. X. Yang, "Efficient scheduling of railway traffic based on global information of train," Transportation Research Part B: Methodological , vol. 42, no. 10, pp. 1008-1030, 2008.

[16] X. Xu, K. Li, L. Yang, J. Ye, "Balanced train timetabling on a single-line railway with optimized velocity," Applied Mathematical Modelling , vol. 38, no. 3, pp. 894-909, 2014.

[17] J. C. Jong, S. Chang, Y. C. R. Lai, "Development of a two-stage hybrid method for solving high speed rail train scheduling problem," Annals of Operations Research , vol. 42, no. 8, pp. 212-226, 2012.

[18] S. K. Sahana, A. Jain, P. K. Mahanti, "Ant colony optimization for train scheduling: an analysis," International Journal of Intelligent Systems and Applications , vol. 6, no. 2, pp. 321-342, 2014.

[19] Ö. Yalçinkaya, G. Mirac Bayhan, "A feasible timetable generator simulation modelling framework for train scheduling problem," Simulation Modelling Practice and Theory , vol. 20, no. 1, pp. 124-141, 2012.

[20] W. Zhou, L. Deng, M. Xie, X. Yang, "Coordination optimization of the first and last trains' departure time on urban rail transit network," Advances in Mechanical Engineering , vol. 2013, 2013.