Improving the robustness in railway station areas

In order to improve the robustness of a railway system in station areas, this paper introduces an iterative approach to successively optimize the train routing through station areas and to enhance this solution by applying some changes to the timetable in a tabu search environment. We present our vision on robustness and describe how this vision can be used in practice. By introducing the spread of the trains in the objective function for the route choice and timetabling module, we improve the robustness of a railway system. Using a discrete event simulation model, the performance of our algorithms is evaluated based on a case study for the Brussels’ area. The computational results indicate an average improvement in robustness of 6.2% together with a decrease in delay propagation of about 25%. Furthermore, the effect of some measures like changing the train offer to further increase the robustness is evaluated and compared.     

An analytical approach to calculate the capacity of a railway system

Railway capacity is a concept that is not easily defined or quantified. Difficulties include the numerous interrelated factors present in the already complex structure of the railway layout. In this paper capacity is defined as the maximum number of trains that can traverse the entire railway in a given period of time, subject to management constraints (such as junction capacity, track capacity, line capacity and interference probability between trains). The proposed method is based on defining and solving an optimization problem which aims at finding out the capacity value of a railway system. It is not based on timetables and moreover it can indirectly take into account priorities between trains and possible delays; it is able to give the time occupation percentage in each component for each train category. It has been applied to a real-life case study showing the range of its validity and the possibility of application for any generic railway scheme.     

Routing of Railway Carriages

In the context of organizing timetables for railway companies the following railway carriage routing problem occurs. Given a timetable containing rail links with departure and destination times/stations and the composition of the trains, find a routing of railway carriages such that the required carriages are always available when a train departs. The problem is formulated as an integer multi-commodity network flow problem with nonlinear objective function. We will present a local search approach for this NP-hard problem. The approach uses structural properties of the integer multi-commodity network flow formulation of the problem. Computational results for a real world instance are given.     

Integration of AI and OR Techniques for Computer-Aided Algorithmic Design in the Vehicle Routing Domain

This paper shows how tools and techniques of artificial intelligence can be successfully integrated into a computer system working in the vehicle routing domain. The aim of this system, called ALTO, is to facilitate the development of routing algorithms for transportation vehicles. In this paper, we describe the general algorithmic framework and the rich interface provided by the system to the expert algorithm designer. We also introduce a methodology for acquiring useful knowledge in the domain, based on examples of successful and unsuccessful problem-solving strategies. With such knowledge, ALTO would then be capable of actively supporting the algorithm designer by suggesting good candidate algorithms for solving new problems.     

Sensitivity analysis of a railway station track layout with respect to a given timetable

An important step in the process of designing a railway station track layout is the verification of the robustness of the layout with respect to the timetables it is based on. For this purpose we develop in this paper an algorithm to randomly perturb a given timetable such that the perturbation is feasible and has the same structure as the given timetable. Mathematically, in this paper we study the problem of, given a set of integer variables and a set of binary relations stating minimal and maximal differences between the variables, to generate solutions uniformly at random. The algorithm involves the simulation of a Markov chain whose state space is a particular subset of the set of feasible timetables and whose limiting and equilibrium distribution is the uniform distribution. Whereas this idea seems simple, some technical pitfalls need to be overcome to make it sound.     

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.     

考虑多仓库的共享单车重新配置问题研究

共享单车是我国大力提倡的低碳交通出行模式,加快共享单车发展是解决最后一公里、城市拥堵和环境污染等问题的重要途径。由于人们停放共享单车的无规律性,使得共享单车系统中各车桩的单车库存量存在不平衡。如何合理的对车桩中的单车进行重新调配,来满足用户的需求,是相关企业亟待解决的问题。共享单车的调配路线优化是优化车桩库存量的重要手段之一。本文研究多仓库条件下的货车调配路线优化问题,建立了一个混合整数非线性规划模型。不同于传统的路径优化问题的研究大多是以成本或时间为目标,本文采用基于车桩库存量的非线性惩罚函数来表示用户需求,从而使得所研究的问题是一个凸函数优化问题。为了简化本文的问题,将目标函数分段线性化。基于车桩网络的特点,设计了变邻域搜索算法,以及构建初始解的贪婪算法。最后,以某共享单车公司为例,进行算例分析,来说明模型和算法的合理性和有效性。     

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

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

Timetabling optimization of a single railway track line with sensitivity analysis

The paper deals with the timetabling problem of a single-track railway line. To solve the timetabling problem, we propose a three-stage approach combining several optimization criteria. Initially and mainly, the maximum relative travel time (ratio of travel time to minimum possible travel time) is minimized subject to a set of constraints, including departure time, train speed, minimum and maximum dwell time, and headway at track segments and stations. Since this problem has many solutions, the process is repeated for other trains, keeping the relative travel times of the critical train fixed, until all trains have been assigned their optimal relative travel times. In the second stage, the prompt allocation of trains is a secondary objective, and finally, in the third stage, the one minimizing the sum of the station dwell times of all trains, keeping the relative travel times constant, is selected to reduce fuel consumption, as a tertiary objective. To consider the user preferences in the optimization problems, the user preference departure time is used instead of the actual planned departure times. In order to guarantee that the exact or a very good approximate global optimum is attained, an algorithm based on the bisection rule is used. This method allows the computation time to be reduced in at least one order of magnitude for 42 trains. The problem of sensitivity analysis is also discussed, and closed form formulas for the sensitivities in terms of the dual variables are given. Several examples of applications are presented to illustrate the goodness of the proposed method. The results show that an adequate selection of intermediate stations and of the departure times are crucial in the good performance of the line and that inadequate spacings between consecutive trains can block the line. In addition, it is shown that, in order to improve performance, regional trains must be scheduled just ahead of or following the long distance trains, rather than having independent schedules. The sensitivities are shown to be very useful in identifying critical trains, segments, stations, departure times, and headways and in suggesting line infrastructure changes.     

New exact method for large asymmetric distance-constrained vehicle routing problem

In this paper we revise and modify an old branch-and-bound method for solving the asymmetric distance–constrained vehicle routing problem suggested by Laporte et al. in 1987. Our modification is based on reformulating distance–constrained vehicle routing problem into a travelling salesman problem, and on using assignment problem as a lower bounding procedure. In addition, our algorithm uses the best-first strategy and new tolerance based branching rules. Since our method is fast but memory consuming, it could stop before optimality is proven. Therefore, we introduce the randomness, in case of ties, in choosing the node of the search tree. If an optimal solution is not found, we restart our procedure. As far as we know, the instances that we have solved exactly (up to 1000 customers) are much larger than the instances considered for other vehicle routing problem models from the recent literature. So, despite of its simplicity, this proposed algorithm is capable of solving the largest instances ever solved in the literature. Moreover, this approach is general and may be used for solving other types of vehicle routing problems.     

A Lagrangian heuristic algorithm for a real-world train timetabling problem

The train timetabling problem (TTP) aims at determining an optimal timetable for a set of trains which does not violate track capacities and satisfies some operational constraints.In this paper, we describe the design of a train timetabling system that takes into account several additional constraints that arise in real-world applications. In particular, we address the following issues:

•

Manual block signaling for managing a train on a track segment between two consecutive stations.

•

Station capacities, i.e., maximum number of trains that can be present in a station at the same time.

•

Prescribed timetable for a subset of the trains, which is imposed when some of the trains are already scheduled on the railway line and additional trains are to be inserted.

•

Maintenance operations that keep a track segment occupied for a given period.

We show how to incorporate these additional constraints into a mathematical model for a basic version of the problem, and into the resulting Lagrangian heuristic. Computational results on real-world instances from Rete Ferroviaria Italiana (RFI), the Italian railway infrastructure management company, are presented.     

Maintenance scheduling of rolling stock using a genetic algorithm

We have developed a Genetic algorithm (GA) for the optimisation of maintenance overhaul scheduling of rolling stock (trains) at the Hong Kong Mass Transit Railway Corporation (MTRC). The problem is one of combinatorial optimisation. Genetic algorithms (GAs) belong to the class of heuristic optimisation techniques that utilise randomisation as well as directed smart search to seek the global optima. The workshop at MTRC does have difficulties in establishing good schedules for the overhaul maintenance of the rolling stock. Currently, an experienced scheduler at MTRC performs this task manually. In this paper, we study the problem in a scientific manner and propose ways in which the task can be automated with the help of an algorithm embedded in a computer program. The algorithm enables the scheduler to establish the annual maintenance schedule of the trains in an efficient manner; the objective being to satisfy the maintenance requirements of various units of the trains as closely as possible to their due dates since there is a cost associated with undertaking the maintenance tasks either `too early’ or ‘too late’. The genetic algorithm developed is found to be very effective for solving this intractable problem. Computational results indicate that the genetic algorithm consistently provides significantly better schedules than those established manually at MTRC. More over, we provide evidence that the algorithm delivers close to optimal solutions for randomly generated problems with known optimal solutions. We also propose a local search method to reconfigure the trains in order to improve the schedule and to balance the work load of the overhaul maintenance section of the workshop throughout the planning horizon. We demonstrate that the reconfiguration of trains improves the schedule and reduces cost significantly.     

A hybrid tabu search based heuristic for the periodic distribution inventory problem with perishable goods

Most of the research on integrated inventory and routing problems ignores the case when products are perishable. However, considering the integrated problem with perishable goods is crucial since any discrepancy between the routing and inventory cost can double down the risk of higher obsolescence costs due to the limited shelf-life of the products. In this paper, we consider a distribution problem involving a depot, a set of customers and a homogeneous fleet of capacitated vehicles. Perishable goods are transported from the depot to customers in such a way that out-of-stock situations never occur. The objective is to simultaneously determine the inventory and routing decisions over a given time horizon such that total transportation cost is minimized. We present a new “arc-based formulation” for the problem which is deemed more suitable for our new tabu search based approach for solving the problem. We perform a thorough sensitivity analysis for each of the tabu search parameters individually and use the obtained gaps to fine-tune the parameter values that are used in solving larger sized instances of the problem. We solve different sizes of randomly generated instances and compare the results obtained using the tabu search algorithm to those obtained by solving the problem using CPLEX and a recently published column generation algorithm. Our computational experiments demonstrate that the tabu search algorithm is capable of obtaining a near-optimal solution in less computational time than the time required to solve the problem to optimality using CPLEX, and outperforms the column generation algorithm for solving the “path flow formulation” of the problem in terms of solution quality in almost all of the considered instances.     

A new mixed integer linear model for a rich vehicle routing problem with docking constraints

In this paper we address a rich vehicle routing problem that arises in real-life applications. Among other aspects we consider time windows, simultaneous delivery and pick-up at customer locations and multiple use of vehicles. To guarantee a coordinated material flow at the depot, we include the timed allocation of vehicles to loading bays at which the loading and unloading activities can occur. The resulting vehicle routing problem is formulated as a two-index vehicle-flow model which integrates the routing under real-life conditions and the assignment of vehicles to loading bays at the depot. We use CPLEX 11.0 to solve medium-sized instances that are derived from the extended Solomon test set. The selective implementation of preprocessing techniques and cutting planes improves the solver performance significantly.     

基于交通流的多模糊时间窗车辆路径优化

研究了基于交通流的多模糊时间窗车辆路径问题,考虑了实际中不断变化的交通流以及客户具有多个模糊时间窗的情况,以最小化配送总成本和最大化客户满意度为目标,构建基于交通流的多模糊时间窗车辆路径模型。根据伊藤算法的基本原理,设计了求解该模型的改进伊藤算法,结合仿真算例进行了模拟计算,并与蚁群算法的计算结果进行了对比分析,结果表明,利用改进伊藤算法求解基于交通流的多模糊时间窗车辆路径问题,迭代次数小,效率更高,能够在较短的时间内收敛到全局最优解,可以有效的求解多模糊时间窗车辆路径问题。     

满足路径约束的最优路算法

满足路径约束的最优路问题已被证明是NP-hard问题。本针对源点到宿点满足两个QoS(服务质量)度量的路由问题，给出一种保证时延的最小费用路由启发式算法。这个算法的优点是计算较简单、占用内存小、时间短。算法的复杂度是多项式的，表明算法是有效的。     

货物列车的编组调度问题

研究的是货物列车的编组和调度问题.通过对问题的深入研究,设计了一种车辆编组调度方案的算法.按照这种算法,在数据处理的基础上利用VC编写每个问题的处理程序,实现了对列车的快速安全高效的调度.对每个问题进行处理,都得到符合要求的结果.问题一首先对整个车辆编组调度的问题进行分析,在尽量保证新组装列车满载的基础上,使每班的中时尽可能少.为此,本文解决了两个关键问题:一是选车问题,二是拆解重组的问题.采用梯形方案对列车车辆进行编队重组,对选车问题主要采用按照时间先后顺序的选车方案,然后通过启发式算法配合遗传算法的选车方案对按时间先后顺序的方案进行检验.从编写的VC程序的运行结果来看,两种方案都可得到满意的结果,遗传算法得到的结果更为合理.另外,为了达到中时最短,采用双推双滑的方式利用驼峰线,提高了调度效率,并在驼峰线和编组道之间加入了碰撞检验模块,保证了列车调度时的安全性.问题二的求解是在问题一的基础上对待拆列车按优先级进行分类.对优先级高的列车先进行拆解.救灾车辆最高,其次是军列和发往S1的车辆,最后是一般车辆.问题三的处理主要是在问题二的基础上,通过提前获得列车的相关信息来决定编组场的列车离开编组场的时刻,从而缩短车辆的中时.问题四在原有模型基础上对编组方案进行了修改,利用编写的VC程序重新计算了每班的中时和列车的调度方案.问题五主要分析了整个系统瓶颈所在,分析了提高资源利用率的可行性.最后,通过对站名的调整,达到了对地质灾害等对铁路系统的破坏突发情况的有效处理,并且进一步分析了如何提高车站的效率的调度方案和建议.     

Stochastic single vehicle routing problem with delivery and pick up and a predefined customer sequence

In this paper we study the routing of a single vehicle that delivers products and picks up items with stochastic demand. The vehicle follows a predefined customer sequence and is allowed to return to the depot for loading/unloading as needed. A suitable dynamic programming algorithm is proposed to determine the minimum expected routing cost. Furthermore, the optimal routing policy to be followed by the vehicle’s driver is derived by proposing an appropriate theorem. The efficiency of the algorithm is studied by solving large problem sets.     

The robust network loading problem with dynamic routing

In this paper the Robust Network Loading problem with splittable flows and dynamic routing under polyhedral uncertainty for the demands is considered. Polyhedral results for the capacity formulation of the problem are given. The first exact approach for solving the problem is presented. A branch-and-cut algorithm based on the proposed capacity formulation is developed. Computational results using the hose polyhedron to model the demand uncertainty are discussed.