机场新增卫星厅对登机口影响的评估方法

为了解决航站楼客流量饱和的问题,采用一种增加卫星厅的方法,实现了旅客分流.基于单目标整数线性规划和多目标优化的方法,分别构建了登机口优化分配网络模型和多目标优化模型.利用登机口优化分配网络算法筛选出所使用的共同登机口,建立了目标函数并列出约束条件,采用目标约束法对建立的模型进行求解.在此基础上,根据目标建模的思想,建立了可供中转旅客总体流程时间最短且使用登机口数量最小的航班-登机口分配模型.利用MATLAB计算可知,利用42个登机口即可实现303架航班的正常运转.     

Comprehensive optimization of urban rail transit timetable by minimizing total travel times under time-dependent passenger demand and congested conditions

The comprehensive optimization of the timetables of urban rail transit systems under more realistic conditions is essential for their practical operation. Currently, most time-dependent timetabling models do not adequately consider train capacity and variable operation parameters. To bridge this gap, this study mainly investigates the timetable design problem of the urban rail transit system so as to adapt to time-dependent passenger demand under congested conditions by considering the variable number of trains, train running time, and train dwell time. Two nonlinear non-convex programming models are formulated to design timetables with the objective of minimizing the total passenger travel time (TTT) under the constraints of train operations, and passenger boarding and alighting processes. The difference between the two models is that one is a train-capacity unconstrained model and the other is a train-capacity constrained model. The proposed models are examined through real-world cases solved by the adaptive large neighborhood search algorithm. The results show that the first model can minimize passenger TTT under dynamic passenger demand, whereas the second can comprehensively optimize passenger TTT and meantime keep the train load factor within a reasonable level. Accordingly, it is concluded that the proposed models are more realistic.     

Extensions to online delay management on a single train line: new bounds for delay minimization and profit maximization

We present extensions to the Online Delay Management Problem on a Single Train Line. While a train travels along the line, it learns at each station how many of the passengers wanting to board the train have a delay of δ. If the train does not wait for them, they get delayed even more since they have to wait for the next train. Otherwise, the train waits and those passengers who were on time are delayed by δ. The problem consists in deciding when to wait in order to minimize the total delay of all passengers on the train line. We provide an improved lower bound on the competitive ratio of any deterministic online algorithm solving the problem using game tree evaluation. For the extension of the original model to two possible passenger delays δ ₁ and δ ₂, we present a 3-competitive deterministic online algorithm. Moreover, we study an objective function modeling the refund system of the German national railway company, which pays passengers with a delay of at least Δ a part of their ticket price back. In this setting, the aim is to maximize the profit. We show that there cannot be a deterministic competitive online algorithm for this problem and present a 2-competitive randomized algorithm.     

Passenger flow control strategies for urban rail transit networks

Urban rail traffic congestion is becoming increasingly serious due to the large traffic demands in modern cities. In order to ensure the safety and quality of station services in peak hours, it's necessary to adopt some reasonable and effective passenger flow control strategies. In this study, through considering the time-dependent passenger demands, a passenger flow control model based on the network-level system is explicitly developed. The passenger successive motion process is discretized by the modeling method. Systematically considering the coordinated relationship between traffic demands and strict capacity constraints (including station passing capacity, platform load capacity and train transport capacity), we establish a mixed integer linear programming model to minimize the total passenger waiting time (including passengers outside stations and on the platforms). The optimization software Cplex is adopted to solve the developed model, and a real network of Beijing urban railway is calibrated to verify the effectiveness of the suggested model. As a result, the proposed flow control strategies can provide detailed information about control stations, control durations and control intensities, and can effectively reduce the total waiting time and relieve the number of stranded passengers in the urban rail transit network.     

Static target search path planning optimization with heterogeneous agents

Disruptions in airline operations can result in infeasibilities in aircraft and passenger schedules. Airlines typically recover aircraft schedules and disruptions in passenger itineraries sequentially. However, passengers are severely affected by disruptions and recovery decisions. In this paper, we present a mathematical formulation for the integrated aircraft and passenger recovery problem that considers aircraft and passenger related costs simultaneously. Using the superimposition of aircraft and passenger itinerary networks, passengers are explicitly modeled in order to use realistic passenger related costs. In addition to the common routing recovery actions, we integrate several passenger recovery actions and cruise speed control in our solution approach. Cruise speed control is a very beneficial action for mitigating delays. On the other hand, it adds complexity to the problem due to the nonlinearity in fuel cost function. The problem is formulated as a mixed integer nonlinear programming (MINLP) model. We show that the problem can be reformulated as conic quadratic mixed integer programming (CQMIP) problem which can be solved with commercial optimization software such as IBM ILOG CPLEX. Our computational experiments have shown that we could handle several simultaneous disruptions optimally on a four-hub network of a major U.S. airline within less than a minute on the average. We conclude that proposed approach is able to find optimal tradeoff between operating and passenger-related costs in real time.     

Delay resistant line planning with a view towards passenger transfers

The line planning step, as part of the public transportation planning process, is an elementary problem. When generating public transportation systems in a conventional fashion, the line planning problem is one of the first to solve. Hence, subsequent problems rely on the solution of the line planning problem. Line planning has been studied from various perspectives and is understood very well. Still, the effect of this planning step on to the next ones has only received minor attention. In this paper, we study the effect of transfers on the delay resistance and propose a line planning model which provides a good basis for a delay resistant transportation system. To this end, the concept of preferable paths from the direct travelers line planning model is further extended. The model includes the routing of passengers in order to minimize passenger transfers. A column generation approach is shown to properly solve the proposed model. As such, this is the first line planning model which detailedly routes the passengers and is still tractable on realistically sized instances. Finally, it is shown that minimizing the passenger transfers at the line planning stage contributes to an increasing delay resistance in the public transportation system.     

校车站点及线路的优化设计

以高校新校区教师校车站点及线路安排为对象,首先针对乘车站点建立了双目标非线性规划模型,其中目标函数包括乘客到达站点的距离偏差最小与所有乘客到达站点的总的距离最小两个方面;站点确定后针对车辆数最少、车辆行驶的总距离最短、各辆车的运行距离均衡及各辆车的负荷均衡这4个目标建立针对线路优化的多目标非线性规划模型,并给出了解决这类问题的启发式优化算法.与目前国内外研究相比较,该模型与算法更实际,更具体的给出了问题的解答.     

乘客到达时间不确定的机场动态拼车策略与算法研究

网约车拼车服务作为共享经济领域重要应用,已成为国内外研究热点。针对机场在线拼车平台运营中乘客等待时间过长和车辆行驶成本较高的突出问题,本文提出前瞻式动态拼车匹配策略。该策略将未来随机到达乘客信息纳入当前已到达乘客的拼车匹配决策中,建立了乘客匹配与车辆路径联合优化两阶段随机规划模型。为了在动态环境中实时产生高质量的匹配与路径规划方案,首先基于贝叶斯估计压缩乘客随机到达情景空间,建立了问题的确定性近似最优模型。为了快速求解模型,提出基于订单目的地和乘客期望到达时间相似度的匹配规则,并以此开发改进的差分进化算法。最后,基于某拼车平台真实订单数据,通过对比测试验证了前瞻式匹配策略和改进差分进化算法的有效性与计算效率。     

Adjusting a railway timetable in case of partial or complete blockades

Unexpected events, such as accidents or track damages, can have a significant impact on the railway system so that trains need to be canceled and delayed. In case of a disruption it is important that dispatchers quickly present a good solution in order to minimize the nuisance for the passengers. In this paper, we focus on adjusting the timetable of a passenger railway operator in case of major disruptions. Both a partial and a complete blockade of a railway line are considered. Given a disrupted infrastructure situation and a forecast of the characteristics of the disruption, our goal is to determine a disposition timetable, specifying which trains will still be operated during the disruption and determining the timetable of these trains. Without explicitly taking the rolling stock rescheduling problem into account, we develop our models such that the probability that feasible solutions to this problem exist, is high. The main objective is to maximize the service level offered to the passengers. We present integer programming formulations and test our models using instances from Netherlands Railways.     

Locating a Central Hunter on the Plane

Protection, surveillance or other types of coverage services of mobile points call for different, asymmetric distance measures than the traditional Euclidean, rectangular or other norms used for fixed points. In this paper, the destinations are mobile points (prey) moving at fixed speeds and directions and the facility (hunter) can capture them using one of two possible strategies: either it is smart, predicting the prey’s movement in order to minimize the time needed to capture it, or it is dumb, following a pursuit curve, by moving at any moment in the direction of the prey. In either case, the hunter location in a plane is sought in order to minimize the maximum time of capture of any prey. An efficient solution algorithm is developed that uses the particular geometry that both versions of this problem possess. In the case of unpredictable movement of prey, a worst-case type solution is proposed, which reduces to the well-known weighted Euclidean minimax location problem. The work of the second and third authors was supported in part by a grant from Research Projects BFM2003-04062 and MTM2006-15054.     

The shuttle dispatch problem with compound Poisson arrivals: Controls at two terminals

We consider the control of an infinite capacity shuttle which transports passengers between two terminals. The passengers arrive at each terminal according to a compound Poisson process and the travel time from one terminal to the other is a random variable following an arbitrary distribution. The following control limit policy is considered: dispatch the shuttle at terminali, at the instant that the total number of passengers waiting at terminali reaches or exceeds a predetermined control limitm _i . The objective of this paper is to obtain the mean waiting time of an arbitrary passenger at each terminal for given control valuesm ₁ andm ₂. We also discuss a search procedure to obtain the optimal control values which minimize the total expected cost per unit time under a linear cost structure.     

Dynamic optimization of the operation of single-car elevator systems with destination hall call registration: Part I. Formulation and simulations

The purpose of this two-part study is to investigate the operation problem of single-car elevator systems with destination hall call registration. Destination hall call registration is such a system in which passengers register their destination floors at elevator halls before boarding the car, while in the ordinary systems passengers specify only the directions of their destination floors at elevator halls and register destination floors after boarding the car. In this part of the study, we formulate the operation problem as a dynamic optimization problem and demonstrate by computer simulations that dynamically optimized operation considerably improves the transportation capability compared to conventional selective collective operation. How to solve the dynamic optimization problem is given in the second part of this study.     

Virtual queuing at airport security lanes

Airports continuously seek opportunities to reduce the security costs without negatively affecting passenger satisfaction. In this paper, we investigate the possibilities of implementing virtual queuing at airport security lanes, by offering some passengers a time window during which they can arrive to enter a priority queue. This process could result in a smoother distribution of arriving passengers, such that the required security personnel (costs) can be decreased. While this concept has received attention in a number of settings, such as theme parks, virtual queuing at airports bears an additional level of complexity related to the flight schedules, i.e., passengers can only be transferred forward in time to a limited extent, which we denote by the transfer time limit. We conducted a major simulation study in collaboration with a large international airport in Western Europe to determine the potential impact of virtual queuing and find that nearly one million Euro can be saved on security personnel cost without negatively impacting the passenger waiting time.     

Minimising average passenger waiting time in personal rapid transit systems

Personal Rapid Transit (PRT) is an emerging urban transport mode. A PRT system operates much like a conventional hackney taxi system, except that the vehicles are driven by computer (no human driver) between stations in a dedicated network of guideways. The world’s first two PRT systems began operating in 2010 and 2011. In both PRT and taxi systems, passengers request immediate service; they do not book ahead. Perfect information about future requests is therefore not available, but statistical information about future requests is available from historical data. If the system does not use this statistical information to position empty vehicles in anticipation of future requests, long passenger waiting times result, which makes the system less attractive to passengers, but using it gives rise to a difficult stochastic optimisation problem. This paper develops three lower bounds on achievable mean passenger waiting time, one based on queuing theory, one based on the static problem, in which it is assumed that perfect information is available, and one based on a Markov Decision Process model. An evaluation of these lower bounds, together with a practical heuristic developed previously, in simulation shows that these lower bounds can often be nearly attained, particularly when the fleet size is large. The results also show that low waiting times and high utilisation can be simultaneously obtained when the fleet size is large, which suggests important economies of scale.     

Determination of the number and locations of time points in transit schedule design — Case of a single run

An analytical model for the determination of the number and locations of time points as well as the amount of slack times in transit schedule design is developed. The model considers a bus route with a special passenger demand pattern in which all boarding passengers coordinate their arrivals at each stop in such a way that they never miss their intended bus, and therefore designing the schedule separately a single run at a time, becomes possible. The model employs the dynamic programming method to deal with the trade-offs among various cost components associated with the schedule quantitatively, and yet is flexible enough to incorporate the existing rules of thumb as well as transit operators' policies. Numerical examples that illustrate the applications of the model are given. The model, although not quite applicable to bus routes with general passenger demand patterns, is useful in the analysis of the contributing factors to the design of an economical, reliable, and operational transit schedule, and is likely to be adaptable for more realistic cases.     

A heuristic approach based on shortest path problems for integrated flight,aircraft, and passenger rescheduling under disruptions

In this paper, we present a heuristic method to solve an airline disruption management problem arising from the ROADEF 2009 challenge. Disruptions perturb an initial flight plan such that some passengers cannot start or conclude their planned trip. The developed algorithm considers passengers and aircraft with the same priority by reassigning passengers and by creating a limited number of flights. The aim is to minimize the cost induced for the airline by the recovery from the disruptions. The algorithm is tested on real-life-based data, as well as on large-scale instances and ranks among the best methods proposed to the challenge in terms of quality, while being efficient in terms of computation time.     

Steady state results for the M/M(a,b)/c batch-service system

The transportation system considered in this paper has a number of vehicles with capacity constraint, which take passengers from a source terminal to various destinations and return to the terminal. The trip times are considered to be independent and identically distributed random variables with a common exponential distribution. Passengers arrive at the terminal in accordance with a Poisson process. The system is operated under the following policy: when a vehicle is available and there are at least ‘a’ passengers waiting for service, then a vehicle is dispatched immediately. A recursive algorithm is derived to obtain the steady-state probability P(m, j) that there are m idle vehicles and j waiting passengers in the queue. Analytical expressions have been derived for passenger queue length distribution, average passenger queue length, the r-th moment of passenger waiting time in the queue, service batch size distribution and the average service batch size, all in terms of P(0,0).     

Optimizing the release of passenger flow guidance information in urban rail transit network via agent-based simulation

The passenger flow guidance is an effective demand management strategy to alleviate the excessive congestion in the urban rail transit network. In order to determine the scope and the timing, a simulation-based optimization model is proposed to optimize the release of passenger flow guidance information in the rail transit network in this paper. In the optimization model, we mainly focus on three aspects namely; where, when and what type of the guidance information should be released to the passengers. In the simulation model, the passenger choice behavior is captured by the agent-based simulation method, which responses to the congestion and the guidance information. Based on this, the dynamic passenger flow distribution can be derived. Furthermore, the adoption rate of the displayed guidance information on passenger information system as well as its impact on passenger travel behavior are also considered in the model. A hybrid heuristic solution algorithm, integrated with passenger simulator and genetic algorithm, is developed to solve the proposed simulation-based optimization model. Finally, a case study of Beijing subway is carried out with the large-scale smart card data. The numerical study shows that the passenger flow demand affects the guidance effect significantly and the best guidance effect can be met with sufficiently high passenger flow demand. And the guidance rate is also found to affect the guidance results. The results also show that the proposed model can provide a detailed guidance scheme for every station at selected time intervals. The results show that the dynamic releasing scheme can save up to a total of 46,319 min in passenger travel time during a single guidance period.     

Fabrication scheduling on a single machine with due date constraints

There is a fabrication machine available for processing a set of jobs. Each job is associated with a due date and consists of two parts, one is common among all products and the other is unique to itself. The unique components are processed individually and the common parts are grouped into batches for processing. A constant setup time is incurred when each batch is formed. The completion time of a job is defined as the time when both of its unique and common components are completed. In this paper, we consider two different objectives. The first problem seeks to minimize the maximum tardiness, and the second problem is to minimize the number of tardy jobs. To minimize the maximum tardiness, we propose a dynamic programming algorithm that optimally solves the problem in polynomial time. Next, we show NP-hardness proof and design a pseudo-polynomial time dynamic programming algorithm for the problem of minimizing the number of tardy jobs.     

RETRACTED ARTICLE: Discrete optimization method based on grassmannian parameterization in multidimensional dichotomic data structuring

A solution of the large computational time problem arising in multidimensional data structuring is addressed by employing algebraic properties of finite geometries. A vector parameterization of the Grassmannian Gr₂(k, n) is proposed which makes it possible to minimize the amount of memory and reduce the number of operations required to solve the problem. An algorithm based on this parameterization and the Gray codes is constructed; the algorithm is suitable for parallel computation, which further reduces computation time.