Freight transportation in railway networks with automated terminals: A mathematical model and MIP heuristic approaches

In this paper we propose a planning procedure for serving freight transportation requests in a railway network with fast transfer equipment at terminals. We consider a transportation system where different customers make their requests (orders) for moving boxes, i.e., either containers or swap bodies, between different origins and destinations, with specific requirements on delivery times. The decisions to be taken concern the route (and the corresponding sequence of trains) that each box follows in the network and the assignment of boxes to train wagons, taking into account that boxes can change more than one train and that train timetables are fixed.The planning procedure includes a pre-analysis step to determine all the possible sequences of trains for serving each order, followed by the solution of a 0-1 linear programming problem to find the optimal assignment of each box to a train sequence and to a specific wagon for each train in the sequence. This latter is a generalized assignment problem which is NP-hard. Hence, in order to find good solutions in acceptable computation times, two MIP heuristic approaches are proposed and tested through an experimental analysis considering realistic problem instances.     

基于三层C/S结构的专用铁路现车管理系统研究

专用铁路运输系统的进出车流量较大 ,由于行车信息不准 ,有时出现丢车现象 ,无法对路车在系统内的停留时间进行分析 .通过对专用铁路进出的路车信息进行统计分析 ,为行车调度人员提供准确的车辆信息 ,从而对正常列车及超时车进行监装监卸 ,建立了基于三层 C/ S体系结构的专用铁路现车管理信息系统 .     

A Method for Finding the Shortest Route Through a Road Network

When a new road is being planned it is necessary to assess how much traffic will be diverted to it from various parts of the existing road network. This allocation of traffic has usually been based on a comparison of journey times or journey costs on alternative routes, and has depended on the selection, by trial and error, of the cheapest route through the network.A method is described which determines the shortest or cheapest routes between points on the network and which can readily be extended to show how traffic between the points is distributed and to assess the total cost of vehicle operation on the network.The procedure is quite systematic and independent of the manner in which journey costs are derived, and it could be carried out on an electronic computer with considerable saving in time. It can be applied to any transportation or communication problem that involves finding the most economical routes through a network.     

货运列车编组调度问题的模型与算法研究

从双向编组站运输生产实际情况出发,以最大化车站发出车数和最小化车辆在站平均停留时间(中时)为目标,综合考虑解体、编组调机能力限制、到发列车车流接续、车流在站停留时间约束的影响,建立了车站货运列车编组调度问题的多目标非线性混合整数规划模型,结合该优化模型难以求解的特点,将编组调度问题分解为配流、待解车列解体和待编车列编组三个子问题,进而设计了求解该问题的分层启发式算法,对正常和特殊运输组织条件下的列车编组调度问题进行了求解.     

The empty wagons adjustment algorithm of Chinese heavy-haul railway

The paper studied the problem of empty wagons adjustment of Chinese heavy-haul railway. Firstly, based on the existing study of the empty wagons adjustment of heavy-haul railway in the world, Chinese heavy-haul railway was analyzed, especially the mode of transportation organization and characteristics of empty wagons adjustment. Secondly, the optimization model was set up to solve the empty wagons adjustment of heavy-haul railway and the model took the minimum idling period as the function goal. Finally, through application and solution of one case, validity and practicability of model and algorithm had been proved. So, the model could offer decision support to transport enterprises on adjusting empty wagons.     

Unobserved Component models applied to the assessment of wear in railway points: A case study

Railways are experiencing a fundamental transformation. The introduction of high speed networks and the increased traffic levels on suburban routes and freight lines require new technologies for both railway infrastructure and trains, all of which must be subjected to rigorous quality control before and during operation and must be supported with effective maintenance processes during their operating lives. Safety in railway infrastructure provision must be ensured by all the main components operating reliably all the time. From an economic, quality and safety point of view, points are probably one of the most critical infrastructure elements in railway transportation.     

Service network design for freight railway transportation: the Italian case

In this paper, we present a case study on freight railway transportation in Italy, which is a by-product of research collaboration with a major Italian railway company. We highlight the main features of the Italian reality and propose a customized mathematical model to design the service network, that is, the set of origin-destination connections. More specifically, the model suggests the services to provide, the number of trains travelling on each connection, the number of cars and their type. We consider both full and empty freight car movements and take handling costs into account. All decisions are taken in order to minimize the total costs. The quality of service is guaranteed by satisfying all the transportation demand and by implicitly minimizing the waiting time of cars at intermediate railway stations. Our approach yields to a multi-commodity network design problem with a concave cost function. To solve this problem, we implement a specialized tabu search procedure. Computational results on realistic instances show a significant improvement over current practice.     

Dynamic dairy facility location and supply chain planning under traffic congestion and demand uncertainty: A case study of Tehran

In this paper, dynamic dairy facility location and supply chain planning are studied through minimizing the costs of facility location, traffic congestion and transportation of raw/processed milk and dairy products under demand uncertainty. The proposed model dynamically incorporates possible changes in transportation network, facility investment costs, monetary value of time and changes in production process. In addition, the time variation and the demand uncertainty for dairy products in each period of the planning horizon is taken into account to determine the optimal facility location and the optimal production volumes. Computational results are presented for the model on a number of test problems. Also, an empirical case study is conducted in order to investigate the dynamic effects of traffic congestion and demand uncertainty on facility location design and total system costs.     

Optimal track class assignment for a railroad network

The track class and speed for North American railroads are governed by regulations from the Federal Railroad Administration. Better quality of track permits greater operational speeds and lower transportation cost but also requires greater maintenance expenditure. In this study, we considered the trade-off between maintenance and transportation costs, and developed an optimization framework determining the optimal assignment for track class based upon the characteristics of the track, traffic demand, and maintenance budget. We also presented a solution algorithm by using Lagrangian Relaxation techniques to improve the solution efficiency. This tool can help railroads maintain tracks at their most appropriate level so as to provide reliable and cost-effective services.     

Using fuzzy integral for evaluating subjectively perceived travel costs in a traffic assignment model

A good traffic assignment model can be a powerful tool to describe the characteristics of traffic behavior in a road network. The traffic assignment results often play an important role in transportation planning, e.g., an optimal and economical network design. Many traditional traffic assignment models rely heavily on the travel cost function established by Wardrop’s principles; however, the Wardrop’s travel cost function has been proven to be weak for explaining the uncertainty and interactivity of traffic among links. This study tries to construct a traffic assignment model that is different from Wardrop’s in many aspects. First, it considers the cross-effect among the links. Second, a fuzzy travel cost function is established based on the possibility concept instead of precise calculation of traffic volumes. Third, the techniques of fuzzy measure and fuzzy integral are applied to calculate the subjectively perceived travel costs during traffic assignment. Furthermore, in order to validate our model, a detailed network with 22 nodes and 36 links is used to illustrate it. Study results show that our model explains more interactivity and uncertainty of traffic among links when compared with the traditional model of Wardrop’s.     

The Geometry of Railway Geometric Overthrow Revisited Using Computer Algebra Methods

There are size standards for railway coaches and freight wagons in order to allow trains to pass from one railway line or even network to another. The maximum size and shape of the rolling stock is denoted gauge. On curves, vehicles sweep a larger path than on straight track. We shall focus on the geometric overthrow of the different kind of rolling stock (the geometric overthrow is that part of the vehicle element offset which is due to the track curve). We shall detail the influence of the kind of vehicle (two axles, classic bogies, shared bogies or Talgo vehicles) in the geometric overthrow. The computations can be easily carried out with a computer algebra system such as Maple and some curious results are obtained (for instance, a negative value (!) is obtained for Talgo coaches).     

An optimization based approach for deployment of roadway incident response vehicles with reliability constraints

In recent years transportation agencies have introduced patrol based response programs to remove roadway incidents rapidly. With the evolution of technology incident detection and notification from remote traffic operation centers is possible and patrols to detect incidents are not necessary. Instead, the response units can be placed at various depots in urban areas and dispatched to incident sites upon notification. In this paper, we propose a reliability based mixed integer programming model to find best locations of incidence response depots and assign response vehicles to these depots so that incidents can be cleared efficiently at a minimum cost. The approach is unique as it considers fixed and variable costs of vehicles and depots, occurrences of major and minor incidents, and reliability of response service in the same model. Numerical results are generated for an example problem and sensitivity analysis is conducted to explore the relationships between parameters of the problem.     

Solving the robust two-stage capacitated facility location problem with uncertain transportation costs

In this study, we start from a multi-source variant of the two-stage capacitated facility location problem (TSCFLP) and propose a robust optimization model of the problem that involves the uncertainty of transportation costs. Since large dimensions of the robust TSCFLP could not be solved to optimality, we design a memetic algorithm (MA), which represents a combination of an evolutionary algorithm (EA) and a modified simulated annealing heuristic (SA) that uses a short-term memory of undesirable moves from previous iterations. A set of computational experiments is conducted to examine the impact of different protection levels on the deviation of the objective function value. We also investigate the impact of variations of transportation costs that may occur on both transhipment stages on the total cost for a fixed protection level. The obtained results may help in identifying a sustainable and efficient strategy for designing a two stage capacitated transportation network with uncertain transportation costs, and may be applicable in the design and management of similar transportation networks.     

Enumeration and Search Procedures for a Hub Location Problem with Economies of Scale

Within a communications or transportation network, in which a number of locations exchange material or information, hubs can be used as intermediate switching points. In this way, traffic can be consolidated on inter-hub links and, thus, achieve economies of scale in transport costs. Recently, O'Kelly and Brian in 1998 proposed a model (termed the FLOWLOC model) that treats these economies of scale by means of piecewise-linear concave cost functions on the interhub arcs. We show that, for a fixed set of hubs, the FLOWLOC model can be solved using the classic Uncapacitated Facility Location Problem (UFLP). This observation then motivates an optimal enumeration procedure for the FLOWLOC model, as well as some search heuristics that are based upon tabu search and greedy random adaptive search procedures (GRASP). These search procedures would be especially applicable for large-sized problems. Some computational experience is described.     

Solving the minimum toll revenue problem in real transportation networks

As a means to relieve traffic congestion, toll pricing has recently received significant attention by transportation planners. Inappropriate use of transportation networks is one of the major causes of network congestion. Toll pricing is a method of traffic management in which traffic flow is guided to proper time and path in order to reduce the total delay in the network. This article investigates a method for solving the minimum toll revenue problem in real and large-scale transportation networks. The objective of this problem is to find link tolls that simultaneously cause users to efficiently use the transportation network and to minimize the total toll revenues to be collected. Although this model is linear, excessive number of variables and constraints make it very difficult to solve for large-scale networks. In this paper, a path-generation algorithm is proposed for solving the model. Implementation of this algorithm for different networks indicates that this method can achieve the optimal solution after a few iterations and a proper CPU time.     

Stochastic uncapacitated hub location

We study stochastic uncapacitated hub location problems in which uncertainty is associated to demands and transportation costs. We show that the stochastic problems with uncertain demands or dependent transportation costs are equivalent to their associated deterministic expected value problem (EVP), in which random variables are replaced by their expectations. In the case of uncertain independent transportation costs, the corresponding stochastic problem is not equivalent to its EVP and specific solution methods need to be developed. We describe a Monte-Carlo simulation-based algorithm that integrates a sample average approximation scheme with a Benders decomposition algorithm to solve problems having stochastic independent transportation costs. Numerical results on a set of instances with up to 50 nodes are reported.     

不确定条件下的乡村中小学布局优化

学校的合理规划布局是实现教育资源优化配置、提高办学效益和推动教育均衡发展的重要途径。已有许多学者研究了学校的布局问题,但基本上都忽略了交通网络条件以及不确定因素对学校布局的影响。本研究将在前人研究基础上,重点考虑交通网络对乡村中小学选址的影响,并假设旅行时间具有不确定性,从而以最小化学生旅行成本、学校建设、道路修建和道路升级成本为目标,构建不确定条件下的设施区位设计模型。在算法求解方面提出混合模拟退火算法,用于确定新建学校的最佳位置,以及新道路的修建和原有道路的升级情况。最后,将提出的模型和算法应用到实际案例中。     

带能力限制的混合形专用线非直达车流取送问题优化

针对铁路枢纽地方货物流小运转作业系统,研究一类带能力限制的混合形专用线非直达车流取送优化问题。以在站停留车小时费用和调机取送成本之和最小化为目标,考虑装卸站装卸能力、调机牵引能力、瓶颈区段能力、调机日走行时长等能力限制条件,构建问题模型。鉴于模型直接求解较为困难且效率低下,故设计三阶段综合优化策略。该策略首先利用基于作业编码、顺序调整与批次划分的TPA过程完成初始取送作业方案生成,进而基于迭代寻优思路设计FPUA更新过程完成取送作业方案的优化,最后考虑批次时间窗、空闲原则与调机走行利用EAA过程完成调机分配。设计实验场景,对所提出的方法进行过程验证,并设计不同规模问题,对算法进行测试对比与性能评估。     

Sensitivity analysis for the asymmetric network equilibrium problem

We consider the asymmetric continuous traffic equilibrium network model with fixed demands where the travel cost on each link of the transportation network may depend on the flow on this as well as other links of the network and we perform stability and sensitivity analysis. Assuming that the travel cost functions are monotone we first show that the traffic equlibrium pattern depends continuously upon the assigned travel demands and travel cost functions. We then focus on the delicate question of predicting the direction of the change in the traffic pattern and the incurred travel costs resulting from changes in the travel cost functions and travel demands and attempt to elucidate certain counter intuitive phenomena such as ‘Braess' paradox’. Our analysis depends crucially on the fact that the governing equilibrium conditions can be formulated as a variational inequality. This work was supported by the Program of University Research, U.S. Department of Transportation (Project number DTRS 5680-C-00007).     

Field test of nonintrusive traffic detection technologies

Accurate, low-cost methods of collecting historical traffic information are essential in making well-informed transportation planning decisions. In addition, detection of real-time traffic conditions is a key element in advanced traffic management and traveler information systems.Until the last decade, inductive loop detectors, pneumatic road tubes, and temporary manual counts were the primary methods for collecting both real-time and historical traffic data. However, technological innovations have given rise to design many different types of advanced traffic detectors. Recently developed traffic detectors use sonic, ultrasonic, microwave, or infrared energy. Most of these detectors can be mounted overhead or to the side of traffic lanes. Magnetic sensors are now being built in sizes small enough to be placed in conduits under the roadway. Artificial intelligence algorithms can process videotaped images of road scenes and output many useful traffic parameters.Even though nonintrusive technologies have been available for several years, there are still many uncertainties regarding their use. Traffic engineers lack a comprehensive comparison of the various types of traffic detection technology. A study conducted by the Minnesota Department of Transportation(Mn/DOT) and SRF Consulting Group, Inc. (SRF) and sponsored by the Federal Highway Administration (FHWA) seeks to address this need. Mn/DOT and SRF undertook a two-year effort to test a wide variety of nonintrusive traffic detection technologies. The purpose of this evaluation was to collect practical information on the performance, installation requirements, long-term maintenance requirements, and costs of various types of nonintrusive traffic detection technologies. More than a dozen devices representing magnetic, sonic, ultrasonic, microwave, infrared, and video image processing technologies were evaluated during this project. Devices were evaluated for their performance in both freeway and urban intersection monitoring situations.Testing consisted of two phases. During Phase I, which ran from November 1995 to January 1996, all participating devices measured traffic data on three lanes of Interstate 394 in Minneapolis at the Penn Avenue interchange. Phase II, which ran from February to November 1996, consisted of an all-season monitoring of the devices' performance and maintenance requirements and involved both freeway and intersection installations. The Minneapolis-St. Paul metropolitan area provided an excellent opportunity to evaluate the devices in many types of weather extremes, including very cold and very hot temperatures, rain, snow, fog, and high winds.