Vehicle scheduling under stochastic trip times: An approximate dynamic programming approach

Due to unexpected demand surge and supply disruptions, road traffic conditions could exhibit substantial uncertainty, which often makes bus travelers encounter start delays of service trips and substantially degrades the performance of an urban transit system. Meanwhile, rapid advances of information and communication technologies have presented tremendous opportunities for intelligently scheduling a bus fleet. With the full consideration of delay propagation effects, this paper is devoted to formulating the stochastic dynamic vehicle scheduling problem, which dynamically schedules an urban bus fleet to tackle the trip time stochasticity, reduce the delay and minimize the total costs of a transit system. To address the challenge of “curse of dimensionality”, we adopt an approximate dynamic programming approach (ADP) where the value function is approximated through a three-layer feed-forward neural network so that we are capable of stepping forward to make decisions and solving the Bellman’s equation through sequentially solving multiple mixed integer linear programs. Numerical examples based on the realistic operations dataset of bus lines in Beijing have demonstrated that the proposed neural-network-based ADP approach not only exhibits a good learning behavior but also significantly outperforms both myopic and static polices, especially when trip time stochasticity is high.     

Scheduling of airport runway operations using stochastic branch and bound methods

In this paper we present a solution methodology based on the stochastic branch and bound algorithm to find optimal, or close to optimal, solutions to the stochastic airport runway scheduling problem. The objective of the scheduling problem is to find a sequence of aircraft operations on one or several runways that minimizes the total makespan, given uncertain aircraft availability at the runway. Enhancements to the general stochastic branch and bound algorithm are proposed and we give the specific details pertaining to runway scheduling. We show how the algorithm can be terminated early with solutions that are close to optimal, and investigate the impact of the uncertainty level. The computational experiment indicates that the sequences obtained using the stochastic branch and bound algorithm have, on average, 5–7% shorter makespans than sequences obtained using deterministic sequencing models. In addition, the proposed algorithm is able to solve instances with 14 aircraft using less than 1 min of computation time.     

Adding a new station and a road link to a road–rail network in the presence of modal competition

In this paper we study the problem of locating a new station on an existing rail corridor and a new junction on an existing road network, and connecting them with a new road segment under a budget constraint. We consider three objective functions and the corresponding optimization problems, which are modeled by means of mixed integer non-linear programs. For small instances, the models can be solved directly by a standard solver. For large instances, an enumerative algorithm based on a discretization of the problem is proposed. Computational experiments show that the latter approach yields high quality solutions within short computing times.     

��������·��·����ά�޼ƻ��Ż�ģ��

制定铁路线路养护维修计划既要保证线路充分维修,又要兼顾经济效益.为此,以区域路网为研究对象,建立了基于整数规划的铁路线路养护维修计划优化模型.模型考虑了路网中线路之间维修资源的约束,以维修时间和股道占用状态为决策变量,以股道占用费用、维修费用及惩罚费用总和最小化为目标,通过集中安排线路中各项养护维修活动节省维修支出,减少维修活动对股道的占用时间进而达到优化目的.基于启发式算法设计了模型求解方法,仿真实验结果表明,模型具有较好的实用性,能够为编制铁路线路年度养护维修计划提供决策支持.     

用户均衡条件下3类停车设施收费定价模型

为了模拟多类停车设施运营(收费定价)竞争以及出行者的反馈行为,建立了基于用户均衡条件的路外、路内停车场和停车换乘设施等3类停车设施的收费定价模型.上层优化模型模拟停车运营者以利润最大为目标的停车费定价决策,下层用户均衡条件描述出行者以个人出行成本最小为原则的旅行选择行为,包括方式、路径和停车设施的选择.采用基于灵敏度分析的算法来求解该非线性规划问题.设计算例对模型和算法的有效性进行验证,结果表明:考虑多类停车设施运营竞争对停车收费定价最优解有显著影响,并且可能导致较低的停车收费水平和较好的交通需求管理效果,如人均出行的交通拥挤成本降低,停车换乘方式分担率提高等.     

A continuous berth template design model with multiple wharfs

ABSTRACT

Berth planning plays an important role in improving the efficiency of a container terminal. This study focuses on the berth template problem (BTP), which determines the berthing windows of the calling ships within a planning horizon (e.g. a week) in a cyclical way. As a mid-term tactical decision problem, BTP provides the decision support for a terminal operator to negotiate the contracts with the shipping lines. This study develops an integer programming (IP) model aiming to minimize the total deviation, given the ship-dependent target times preferred by the shipping lines. To validate the model and illustrate the benefits of its use, we perform a numerical experiment based on operational data of a specific container terminal in Southeast Asia. Two IP-based heuristic methods are developed to take into account the decision framework of terminal operators in reaction to demand increases. The experiment results indicate that the model and the solution approaches can enhance the resource utilization and operational efficiency of container terminals.     

动态规划理论的天文选星配组

针对海上天文定位在选星配组上面临的实际问题,把天文定位原理和运筹学优化理论进行有机结合,给出了误差判断标准并以此作为指标函数.建立了天文选星配组的运筹学模型,并以实例验证了模型的可行性.实践教学统计数据表明,此模型对于提高海上天文定位的精度和效率有积极意义.     

基于双层规划的城市交通拥塞疏导优化研究

为研究城市路网区域信号控制下的交通子区划分及交通拥塞疏导优化问题,明确交通拥 塞控制子区划分影响因素并建立相邻交叉口关联度模型,将拥塞控制区域划分为“疏散区”“平衡 区”。考虑“疏散区”“平衡区”不同的优化目标构建城市路网交通拥塞疏导优化双层规划模型,并 以昆明市部分城市路网作为实验对象,通过仿真将实际控制方案与本文模型计算方案的控制效 果进行对比,以此验证模型的适用性和有效性。仿真结果表明：除两个方案的平均停车次数优化 效果一般以外,其他控制效果指标均具有很大的优化提升,其中车辆平均延误时间降低了7.7 s, 重度拥塞里程比例下降了10.1%,路网车辆占有率下降了14.1%。综上可知,本文的疏导优化模 型控制可快速疏导和有效缓解交通拥塞,模型具有良好的有效性,可为路网交通拥塞分区治理及 疏导控制提供参考。     

疲劳载荷随机应力功率谱优化设计

针对高加速寿命试验中的随机振动环境应力,以频谱不规则因子为目标,优化设计出一种能高效激发试件疲劳缺陷的随机应力载荷功率谱。首先通过分析频谱不规则因子对载荷应力疲劳激发效能的影响,确定频谱不规则因子的优化方向。然后通过变换将该优化等价成为一个二次规划问题,但是该二次规划的系数矩阵非定,算法不能收敛。于是利用泛函理论中的有限维空间的泛数等价理论和关于谱半径的Perron-Frobenius定理,推导得到一种较优的随机应力功率谱,优化结果与工程实际经验相符。该分析方法可为工程中类似的泛函极值和优化问题提供借鉴。     

粮食码头卸船机配置优化

合理配置粮食码头卸船机是为粮食码头创造最大收益的关键.针对该问题,对比不同粮食卸船机的性能,从经济性分析的角度,以最小成本完成港口生产任务为目标,提出应用多目标规划模型进行粮食码头卸船机的配置优化.以天津港粮食码头为例,对其现有卸船机进行优化,得出结论:天津粮食码头仍采用两台夹皮带卸船机,能以最小成本完成2020年的粮食生产任务,且该结论符合天津港实际情况.