Application of Lagrangian relaxation approach to α-reliable path finding in stochastic networks with correlated link travel times

This study investigates the important problem of determining a reliable path in a stochastic network with correlated link travel times. First, the distribution of path travel time is quantified by using trip records from GPS probe vehicles. Second, the spatial correlation of link travel time is explicitly considered by using a correlation coefficient matrix, which is incorporated into the α-reliable path problem by Cholesky decomposition. Third, the Lagrangian relaxation based framework is used to handle the α-reliable path problem, by which the intractable problem with a non-linear and non-additive structure can be decomposed into several easy-to-solve problems. Finally, the path-finding performance of this approach is tested on a real-world network. The results show that 15 iterations of calculation can yield a small relative gap between upper and lower bounds of the optimal solution and the average running time is about 5 s for most OD settings. The applicability of α-reliable path finding is validated by a case study.     

A tool to aid redesign of flexible transport services to increase efficiency in rural transport service provision

Rural areas generally have lower and more dispersed demands for travel which cannot sustain conventional public transport services and consequently have a greater number of flexible and demand responsive transport services operating. These services usually operate on a stand-alone basis, are often subsidized and are typically only accessible by certain passenger types or for specific trip purposes. This generally results in uncoordinated and inefficient transport provision overall. The Flexible integrated transport services (FITS) system featured in this paper has been designed to address this problem. FITS can be used as a planning tool to assess potential benefits from relaxing operating constraints (e.g., a service's operating boundaries), which can potentially suggest service redesign. It also includes the capacity to assign subsidy payments on a trip by trip basis to increase cost efficiency whilst meeting a greater proportion of transport needs. The case study in the paper focusses on transport to health in the Aberdeenshire and Morayshire areas of Scotland in the UK. Despite flexible transport operators receiving public funds to meet passenger needs, this is currently being supplemented by public bodies paying large amounts in taxi fares in instances where there is a statutory obligation to provide travel but where no other suitable transport service exists. The results demonstrate the potential substantial savings which could be realized by allowing transport operators to redesign their services by relaxing constraints and by the reassignment of subsidies: resulting in more passenger demands being met and a reduction in public spending on taxi fares.     

基于多维网络的增开列车条件下高速铁路列车运行图调整

研究增开列车条件下高速铁路列车运行图的调整问题,并综合考虑列车车站进路的影响。通过构建Time-Station-Track三维时空扩展网络,刻画列车对铁路时空资源的占用。将原多目标优化问题转化为求解列车占用网络弧段最小费用单目标问题,并构建基于Time-Station-Track网络的0-1整数规划模型。针对模型特点,设计拉格朗日松弛算法,将问题进一步分解为求解单列车网络最短路径子问题,由于问题被松弛后求得的解可能不可行。因此,提出基于列车优先序列的启发式策略对对偶解进行可行化。最后以宝兰客运专线为例,验证模型的正确性和算法的可行性。     

跨境供应链网络海外仓的鲁棒性选址模型及算法

新经济形态下，全球政治、经济形势瞬息万变，多种人为和自然因素导致商业供应链的生存环境日益严峻. 跨境供应链网络作为典型的时效性和运营环境等都具有极大不确定性的复杂网络，研究其鲁棒性问题具有一定的理论意义和实际应用场景. 首先阐明了跨境供应链网络的内涵，认为海外仓的选址优化是控制网络鲁棒性的重要手段；随后基于最小最大后悔值构建了海外仓的鲁棒性选址模型，利用情景松弛算法对模型进行求解. 算例分析结果证明，所构建的海外仓鲁棒性选址模型及算法适用于跨境供应链网络情景.     

交叉迭代算法求解车辆-轨道非线性耦合方程的收敛性讨论

运用有限元法建立车辆-轨道非线性耦合系统动力分析模型,该模型将车辆-轨道系统以轮轨接触为界限分成车辆,轨道两个子系统并通过轮轨接触力的平衡和位移协调条件耦合在一起。通过交叉迭代算法分别求解车辆,轨道系统的运动方程,此时每一步都需要判断使之满足轮轨几何相容条件和相互作用力平衡条件,这样对时间步长的选取要求较高,但是如果时间步长超过某一限值,易于导致迭代失败。引入了修正因子对轮轨接触力进行修正,这不仅可以放宽对时间步长的选取,还能加速收敛,提高计算效率。为验证算法的正确性,不仅进行了算例验证,还给出了引入修正因子的交叉迭代算法求解车辆-轨道非线性耦合系统动力学方程的算例,算例中考虑了不同的时间步长和不同的修正因子对交叉迭代算法收敛速度的影响。计算结果表明引入修正因子的交叉迭代算法具有程序编制简单、收敛速度快、用时少、精度高的优点。     

Scheduling of Intelligent and Autonomous Vehicles under pairing/unpairing collaboration strategy in container terminals

A new class of Intelligent and Autonomous Vehicles (IAVs) has been designed in the framework of Intelligent Transportation for Dynamic Environment (InTraDE) project funded by European Union. This type of vehicles is technologically superior to the existing Automated Guided Vehicles (AGVs), in many respects. They offer more flexibility and intelligence in maneuvering within confined spaces where the logistic operations take place. This includes the ability of pairing/unpairing enabling a pair of 1-TEU (20-foot Equivalent Unit) IAVs dynamically to join, transport containers of any size between 1-TEU and 1-FFE (40-foot Equivalent) and disjoin again. Deploying IAVs helps port operators to remain efficient in coping with the ever increasing volume of container traffic at ports and eliminate the need for deploying more 40-ft transporters in the very confined area of ports. In order to accommodate this new feature of IAVs, we review and extend one of the existing mixed integer programming models of AGV scheduling in order to minimize the makespan of operations for transporting a set of containers of different sizes between quay cranes and yard cranes. In particular, we study the case of Dublin Ferryport Terminal. In order to deal with the complexity of the scheduling model, we develop a Lagrangian relaxation-based decomposition approach equipped with a variable fixing procedure and a primal heuristics to obtain high-quality solution of instances of the problem.     

基于拉格朗日松弛的高速铁路列车运行图新增运行线局部调整模型

给定新增列车理想始发时刻及初始利润,考虑始发时刻调整及全程停时延长造成的罚数,基于时空网络构建以全图运行线总利润最大为目标的整数规划模型,进行拉格朗日松弛,根据松弛解对偶信息设计启发式算法求解各运行线可行解,并通过更新拉格朗日乘子进行迭代优化.以京沪高铁为例进行了验证,结果表明：在算例条件下,相较以理想始发时刻推线求解,该方法能够多增铺6条运行线;随着始发时刻可调整度由10min增加至60min,CPLEX的求解时间快速增长,而拉格朗日松弛启发式算法能快速求得高质量的解,除始发时刻可调整度10min情景,求解效率均高于CPLEX;延长始发时刻可调整度至4h,最多增铺18条运行线,说明现有框架下京沪高铁能力已接近饱和.     

约束可松弛的网络绿波模型

为解决区域交通信号协调控制领域中常规网络绿波模型可行域窄或无解的问题，提出了约束可松弛的网络绿波模型。应用混合整数线性规划方法构建模型，以所有路段双向绿波带宽加权和最大为优化目标，利用约束松弛方法，将干线约束和网络外圈闭环约束转变为可松弛的不等式约束。模型针对每条路段引入了0~1二元变量，表示路段的绿波是否被打断。通过模型求解，获得网络中必要的松弛路段，并打断相应的路段绿波，去除外圈闭环约束，以扩大可行域并找到最优解。算例对不同控制方案下提出的模型和其他绿波模型的绿波优化结果进行比较分析。算例显示，当网络各个交叉口采用同一化控制方案时，易于在不打断任何路段绿波的条件下找到最优解。此时，所提出的模型的解和常规网络绿波模型的解等价。当网络各交叉口采取差异化控制方案时，常规网络绿波模型无可行解，Gartner网络绿波模型仅获得非最优的可行解，而所提出的模型能够获得全局最优解。算例中只有1条路段的绿波被打断，而网络的其他路段均获得有效绿波带，且任意相交的干线绿波能够合理协调。算例优化结果表明：所提出的模型优于常规网络绿波模型和Gartner网络绿波模型，更适合复杂的城市交通网络信号优化设计。     

Reliable sensor deployment for network traffic surveillance

New sensor technologies enable synthesis of disaggregated vehicle information from multiple locations. This paper proposes a reliable facility location model to optimize traffic surveillance benefit from synthesized sensor pairs (e.g., for travel time estimation) in addition to individual sensor flow coverage (e.g., for traffic volume statistics), while considering probabilistic sensor failures. Customized greedy and Lagrangian relaxation algorithms are proposed to solve this problem, and their performance is discussed. Numerical results show that the proposed algorithms solve the problem efficiently. We also discuss managerial insights on how optimal sensor deployment and surveillance benefits vary with surveillance objective and system parameters (such as sensor failure probabilities).     

LINEARIZATION RELAXATION PROCEDURE FOR A KIND OF N-DIMENSIONAL NONLINEAR OPTIMIZATION PROBLEM

Ｄ ＯＦ Ｎ－ＤＩＭＥＮＳＩＯＮＡＬ ＮＯＮＬＩＮＥＡＲ ＯＰＴＩＭＩＺＡＴＩＯＮ ＰＲＯＢＬＥＭTX＠徐飞＠王浣尘ＩｎｔｒｏｄｕｃｔｉｏｎＩｔｉｓｄｅｓｉｒａｂｌｅｔｏｒｅｐｌａｃｅｎｏｎｌｉｎｅａｒｐｒｏｂｌｅｍｓｗｉｔｈｌｉｎｅａｒａｐｐｒｏｘｉｍａｔ...