Developing railway timetables which guarantee a better service

In order to improve passenger service, a waiting cost function, weighting different types of waiting times and late arrivals, is designed and minimised. The approach is applied to a small part of the Belgian railway network. In the first phase of the approach, ideal buffer times are calculated to safeguard connections when the arriving train is late. These buffer times are based on the delay distributions of the arriving trains and on the weighting of different types of waiting times. In a second phase, standard linear programming is used to construct an improved timetable with well-scheduled connections and, whenever possible, with ideal buffer times. Simulation compares different timetables and optimises the LP timetable. For the case of the Belgian railway network, the final result is a timetable with well-scheduled connections and a waiting cost that is 40% lower than the current timetable. Since only LP modelling is applied, the proposed technique is very promising for developing better timetables—even for very extensive railway networks.     

公交网络时刻表再协同设计的多目标优化模型

为了改善公交服务质量,公交运营者试图调整现有时刻表的发车时间,使不同线路的车次协同到达换乘站点以方便乘客换乘。针对此场景,研究了公交时刻表重新协同设计问题,提出了求解该问题的多目标模型。模型考虑了对发车间隔灵敏的乘客需求、灵活的车次协同到站方式和发车时间的规则性,分析了该多目标模型的特征和计算复杂性,表明本文研究的问题是NP-hard问题,且它的帕累托最优前沿是非凸的,设计了基于非支配排序的遗传算法求解模型。算例表明,与枚举算法相比,提出的求解算法在较短的时间内可获得高质量的帕累托解。     

碳排放限制下的冷藏集装箱多式联运路径优化

为了降低碳排放限制下的冷藏集装箱多式联运成本,实现节能减排的目的,高效的路径选择至关重要.该文基于碳排放限制的视角,针对多式联运网络中铁路和水路运输具有发班时间限制,以及冷藏集装箱需要考虑制冷费用、货损货差的特点,建立了在碳排放限制下以总成本最低为目标的优化模型.构建总成本时不仅考虑了运输费用和转运费用,还考虑了受发班时间影响而动态变化的冷藏费用和货损费用.设计了遗传算法求解,并进行了算例分析.结果表明:通过该模型和算法,可根据决策者的要求快速地选出成本最少的运输方案,为决策者提供决策支持.     

单向航道船舶进港次序与泊位分配协同优化

为提高单向航道离散泊位港口的服务水平,研究船舶进港次序和泊位分配的协同优化。考虑船舶进出港及泊位作业的实际约束,以计划期内所有船舶的锚地、泊位等待成本、滞期成本和偏离成本之和最小为目标,构建了一个混合整数规划模型,结合问题特征设计了引入禁忌搜索算法的和声搜索算法进行求解。算例结果给出了计划期内每艘船舶的进港次序和靠泊泊位,并通过与单独优化方案的对比和不同规模算例求解效果的分析,验证了模型和算法的有效性;分析进出港时段变动对船舶作业成本的影响,确定不同船舶抵港规模下的最佳进出港时段长度,为单向航道港口时长设置提供借鉴。     

Using Discrete Distributions to Approximate General Service Time Distributions in Queueing Models

In solving discrete time queueing models by numerical techniques, the computational requirements (computer memory and time) are a practical limitation and are particularly dependent on the number of discrete time intervals required in the discrete distribution chosen to match the general service distribution. This paper shows that the minimum number of points required for matching to the first two moments depends on the size of the discrete interval relative to the mean and also on the coefficient of variation. Equations and graphs are provided that will enable the OR practitioner to select the discrete distribution to be used as an approximation. Additionally, it is concluded that discrete time modelling, using these approximations to model service time, now provides a practical means to model both steady-state measures and transient behaviour of M/G/c, M(t)/G/c and M(t)/G/c(t) queueing systems on a personal computer.     

Optimization of transit route network,vehicle headways and timetables for large-scale transit networks

This paper presents a metaheuristic method for optimizing transit networks, including route network design, vehicle headway, and timetable assignment. Given information on transit demand, the street network of the transit service area, and total fleet size, the goal is to identify a transit network that minimizes a passenger cost function. Transit network optimization is a complex combinatorial problem due to huge search spaces of route network, vehicle headways, and timetables. The methodology described in this paper includes a representation of transit network variable search spaces (route network, headway, and timetable); a user cost function based on passenger random arrival times, route network, vehicle headways, and timetables; and a metaheuristic search scheme that combines simulated annealing, tabu, and greedy search methods. This methodology has been tested with problems reported in the existing literature, and applied to a large-scale realistic network optimization problem. The results show that the methodology is capable of producing improved solutions to large-scale transit network design problems in reasonable amounts of time and computing resources.     

Optimizing pricing and location decisions for competitive service facilities charging uniform price

In this paper, we present the problem of optimizing the location and pricing for a set of new service facilities entering a competitive marketplace. We assume that the new facilities must charge the same (uniform) price and the objective is to optimize the overall profit for the new facilities. Demand for service is assumed to be concentrated at discrete demand points (customer markets); customers in each market patronize the facility providing the highest utility. Customer demand function is assumed to be elastic; the demand is affected by the price, facility attractiveness, and the travel cost for the highest-utility facility. We provide both structural and algorithmic results, as well as some managerial insights for this problem. We show that the optimal price can be selected from a certain finite set of values that can be computed in advance; this fact is used to develop an efficient mathematical programming formulation for our model.     

The variable radius covering problem

In this paper we propose a covering problem where the covering radius of a facility is controlled by the decision-maker; the cost of achieving a certain covering distance is assumed to be a monotonically increasing function of the distance (i.e., it costs more to establish a facility with a greater covering radius). The problem is to cover all demand points at a minimum cost by finding optimal number, locations and coverage radii for the facilities. Both, the planar and discrete versions of the model are considered. Heuristic approaches are suggested for solving large problems in the plane. These methods were tested on a set of planar problems. Mathematical programming formulations are proposed for the discrete problem, and a solution approach is suggested and tested.     

Location and allocation for distribution systems with transshipments and transportion economies of scale

Locating transshipment facilities and allocating origins and destinations to transshipment facilities are important decisions for many distribution and logistic systems. Models that treat demand as a continuous density over the service region often assume certain facility locations or a certain allocation of demand. It may be assumed that facility locations lie on a rectangular grid or that demand is allocated to the nearest facility or allocated such that each facility serves an equal amount of demand. These assumptions result in suboptimal distribution systems. This paper compares the transportation cost for suboptimal location and allocation schemes to the optimal cost to determine if suboptimal location and allocation schemes can produce nearly optimal transportation costs. Analytical results for distribution to a continuous demand show that nearly optimal costs can be achieved with suboptimal locations. An example of distribution to discrete demand points indicates the difficulties in applying these results to discrete demand problems.     

On an extension of Weber problem with Euclidean distance

The paper is an extension of the authors previous work [5] in which an approximate discrete technique is proposed to solve the Weber problem with the Euclidean distance. Now, it is assumed that the cost of connection (the cost associated with two points in the plane) depends upon the distance stronger than linearly. A model is formulated and an approximate discrete technique analogous to that in [5] is proposed. Its validity is proved. Both the numerical complexity and the practical efficiency of the algorithm are considered. An example is given     

A green train scheduling model and fuzzy multi-objective optimization algorithm

Train scheduling model is traditionally formulated to minimize the energy consumption for reducing the operation cost. As the European Union formulates the first carbon emission trading scheme in the world, it is necessary to extend the operation cost to include the expenses for buying/selling the carbon emission allowances. In this paper, we propose a multi-objective train scheduling model by minimizing the energy and carbon emission cost as well as the total passenger-time, and named it as green train scheduling model. For obtaining a non-dominated timetable which has equal satisfactory degree on both objectives, we apply a fuzzy multi-objective optimization algorithm to solve the model. Finally, we perform two numerical examples to illustrate the efficiency of the proposed model and solution methodology.     

Capacity planning in networks of queues with manufacturing applications

This paper addresses capacity planning in systems that can be modeled as a network of queues. More specifically, we present an optimization model and solution methods for the minimum cost selection of capacity at each node in the network such that a set of system performance constraints is satisfied. Capacity is controlled through the mean service rate at each node. To illustrate the approach and how queueing theory can be used to measure system performance, we discuss a manufacturing model that includes upper limits on product throughput times and work-in-process in the system. Methods for solving capacity planning problems with continuous and discrete capacity options are discussed. We focus primarily on the discrete case with a concave cost function, allowing fixed charges and costs exhibiting economies of scale with respect to capacity to be handled.     

A rolling stock circulation model for combining and splitting of passenger trains

This paper addresses the railway rolling stock circulation problem. Given the departure and arrival times as well as the expected numbers of passengers, we have to assign the rolling stock to the timetable services. We consider several objective criteria that are related to operational costs, service quality and reliability of the railway system.Our model is an extension of an existing rolling stock model for routing train units along a number of connected train lines. The extended model can also handle underway combining and splitting of trains.We illustrate our model by computational experiments based on instances of NS Reizigers, the main Dutch operator of passenger trains.     

考虑需求不确定的多级应急物流设施选址研究

为了对急物流设施选址问题进行合理的研究,建立了包含配送中心、配送点和需求点的多级应急物流网络。基于应急物资需求特点,使用三角模糊数表示应急物资需求的不确定性,同时考虑应急救援成本和应急救援时间两个目标,建立了应急物流设施选址模型。采用去模糊化方法将三角模糊数转化为确定数,利用成本和时间的单目标的最优结果将多目标转化为相对值,再对时间和成本目标进行加权处理,既消除了不同目标之间的单位及数量级差异,还可以进行动态调整。设计了遗传算法对模型进行求解,通过实际算例表明了模型和算法可以有效地解决应急物流设施选址问题。     

基于遗传算法的大学课程表问题研究

课程表问题是时间表问题之一 ,也是 NP难问题 .根据大学授课形式的特点建立了大学课程表问题的数学模型 ,给出了求解该问题的遗传算法 .根据模型和大学课程表问题的特点设计了一种全新的编码 ,提出了一种新形式的交叉方式 .实验结果表明该方法是可行和有效的 .     

A decision making procedure for robust train rescheduling based on mixed integer linear programming and Data Envelopment Analysis

This paper presents a self-learning decision making procedure for robust real-time train rescheduling in case of disturbances. The procedure is applicable to aperiodic timetables of mixed-tracked networks and it consists of three steps. The first two are executed in real-time and provide the rescheduled timetable, while the third one is executed offline and guarantees the self-learning part of the method. In particular, in the first step, a robust timetable is determined, which is valid for a finite time horizon. This robust timetable is obtained solving a mixed integer linear programming problem aimed at finding the optimal compromise between two objectives: the minimization of the delays of the trains and the maximization of the robustness of the timetable. In the second step, a merging procedure is first used to join the obtained timetable with the nominal one. Then, a heuristics is applied to identify and solve all conflicts eventually arising after the merging procedure. Finally, in the third step an offline cross-efficiency fuzzy Data Envelopment Analysis technique is applied to evaluate the efficiency of the rescheduled timetable in terms of delays minimization and robustness maximization when different relevance weights (defining the compromise between the two optimization objectives) are used in the first step. The procedure is thus able to determine appropriate relevance weights to employ when disturbances of the same type affect again the network. The railway service provider can take advantage of this procedure to automate, optimize, and expedite the rescheduling process. Moreover, thanks to the self-learning capability of the procedure, the quality of the rescheduling is improved at each reapplication of the method. The technique is applied to a real data set related to a regional railway network in Southern Italy to test its effectiveness.     

Siting and Sizing of Facilities under Probabilistic Demands

In this paper a discrete location model for non-essential service facilities planning is described, which seeks the number, location, and size of facilities, that maximizes the total expected demand attracted by the facilities. It is assumed that the demand for service is sensitive to the distance from facilities and to their size. It is also assumed that facilities must satisfy a threshold level of demand (facilities are not economically viable below that level). A Mixed-Integer Nonlinear Programming (MINLP) model is proposed for this problem. A branch-and-bound algorithm is designed for solving this MINLP and its convergence to a global minimum is established. A finite procedure is also introduced to find a feasible solution for the MINLP that reduces the overall search in the binary tree generated by the branch-and-bound algorithm. Some numerical results using a GAMS/MINOS implementation of the algorithm are reported to illustrate its efficacy and efficiency in practice.     

The Transit Route Arc-Node Service Maximization problem

This article presents a new method for determining optimal transit routes. The Transit Route Arc-Node Service Maximization model is a mathematical model that maximizes the service value of a route, rather than minimizing cost. Cost (distance) is considered as a budget constraint on the extent of the route. The mathematical formulation modifies and exploits the structure of linear programming problems designed for the traveling salesman problem. An innovative divide-and-conquer solution procedure is presented that not only makes the transit routing problem tractable, but also provides a range of high-quality alternate routes for consideration, some of which have substantially varying geometries. Variant formulations are provided for several common transit route types. The model is tested through its application to an existing street network in Richardson, TX. Optimal numeric results are obtained for several problem instances, and these results demonstrate that increased route cost is not correlated with increased service provision.     

Engineering graph-based models for dynamic timetable information systems

In the last years we have witnessed remarkable progress in providing efficient algorithmic solutions to the problem of computing best journeys (or routes) in schedule-based public transportation systems. We have now models to represent timetables that allow us to answer queries for optimal journeys in a few milliseconds, also at a very large scale. Such models can be classified into two types: those representing the timetable as an array, and those representing it as a graph. Array-based models have been shown to be very effective in terms of query time, while graph-based ones usually answer queries by computing shortest paths, and hence they are suitable to be combined with the speed-up techniques developed for road networks.In this paper, we study the behavior of graph-based models in the prominent case of dynamic scenarios, i.e., when delays might occur to the original timetable. In particular, we make the following contributions. First, we consider the graph-based reduced time-expanded model and give a simplified and optimized routine for handling delays, and a re-engineered and fine-tuned query algorithm. Second, we propose a new graph-based model, namely the dynamic timetable model, natively tailored to efficiently incorporate dynamic updates, along with a query algorithm and a routine for handling delays. Third, we show how to adapt the ALT algorithm to such graph-based models. We have chosen this speed-up technique since it supports dynamic changes, and a careful implementation of it can significantly boost its performance. Finally, we provide an experimental study to assess the effectiveness of all proposed models and algorithms, and to compare them with the array-based state of the art solution for the dynamic case. We evaluate both new and existing approaches by implementing and testing them on real-world timetables subject to synthetic delays.Our experimental results show that: (i) the dynamic timetable model is the best model for handling delays; (ii) graph-based models are competitive to array-based models with respect to query time in the dynamic case; (iii) the dynamic timetable model compares favorably with both the original and the reduced time-expanded model regarding space; (iv) combining the graph-based models with speed-up techniques designed for road networks, such as ALT, is a very promising approach.