Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints

This paper focuses on how to minimize the total passenger waiting time at stations by computing and adjusting train timetables for a rail corridor with given time-varying origin-to-destination passenger demand matrices. Given predetermined train skip-stop patterns, a unified quadratic integer programming model with linear constraints is developed to jointly synchronize effective passenger loading time windows and train arrival and departure times at each station. A set of quadratic and quasi-quadratic objective functions are proposed to precisely formulate the total waiting time under both minute-dependent demand and hour-dependent demand volumes from different origin–destination pairs. We construct mathematically rigorous and algorithmically tractable nonlinear mixed integer programming models for both real-time scheduling and medium-term planning applications. The proposed models are implemented using general purpose high-level optimization solvers, and the model effectiveness is further examined through numerical experiments of real-world rail train timetabling test cases.     

Multi-fleet ferry service network design with passenger preferences for differential services

This paper investigates a multi-fleet ferry routing and scheduling problem that takes into account ferry services with different operation characteristics and passengers with different preferred arrival time windows. The logit model is used to represent passengers’ service choices. The full problem is formulated as a mixed integer nonlinear programming problem and solved with a heuristic procedure that first fixes the demand and then decomposes the resultant model by ferry services. At each iteration of the algorithm, the demand is updated and the relaxed problem is re-solved. Numerical results for the case of ferry service network design in Hong Kong are provided to illustrate the properties of the model and the performance of the heuristic.     

Modeling schedule recovery processes in transit operations for bus arrival time prediction

Many existing algorithms for bus arrival time prediction assume that buses travel at free‐flow speed in the absence of congestion. As a result, delay incurred at one stop would propagate to downstream stops at the same magnitude. In reality, skilled bus operators often constantly adjust their speeds to keep their bus on schedule. This paper formulates a Markov chain model for bus arrival time prediction that explicitly captures the behavior of bus operators in actively pursuing schedule recovery. The model exhibits some desirable properties in capturing the schedule recovery process. It guarantees provision of the schedule information if the probability of recovering from the current schedule deviation is sufficiently high. The proposed model can be embedded into a transit arrival time estimation model for transit information systems that use both real‐time and schedule information. It also has the potential to be used as a decision support tool to determine when dynamic or static information should be used.     

A robust optimization approach for dynamic traffic signal control with emission considerations

We consider an analytical signal control problem on a signalized network whose traffic flow dynamic is described by the Lighthill–Whitham–Richards (LWR) model (Lighthill and Whitham, 1955; Richards, 1956). This problem explicitly addresses traffic-derived emissions as constraints or objectives. We seek to tackle this problem using a mixed integer mathematical programming approach. Such class of problems, which we call LWR-Emission (LWR-E), has been analyzed before to certain extent. Since mixed integer programs are practically efficient to solve in many cases (Bertsimas et al., 2011b), the mere fact of having integer variables is not the most significant challenge to solving LWR-E problems; rather, it is the presence of the potentially nonlinear and nonconvex emission-related constraints/objectives that render the program computationally expensive.To address this computational challenge, we proposed a novel reformulation of the LWR-E problem as a mixed integer linear program (MILP). This approach relies on the existence of a statistically valid macroscopic relationship between the aggregate emission rate and the vehicle occupancy on the same link. This relationship is approximated with certain functional forms and the associated uncertainties are handled explicitly using robust optimization (RO) techniques. The RO allows emissions-related constraints and/or objectives to be reformulated as linear forms under mild conditions. To further reduce the computational cost, we employ a link-based LWR model to describe traffic dynamics with the benefit of fewer (integer) variables and less potential traffic holding. The proposed MILP explicitly captures vehicle spillback, avoids traffic holding, and simultaneously minimizes travel delay and addresses emission-related concerns.     

A data-driven approach to manpower planning at U.S.–Canada border crossings

We investigate the staffing problem at Peace Arch, one of the major U.S.–Canada border crossings, with the goal of reducing time delay without compromising the effectiveness of security screening. Our data analytics show how the arrival rates of vehicles vary by time of day and day of week, and that the service rate per booth varies considerably by the time of day and the number of active booths. We propose a time-varying queueing model to capture these dynamics and use empirical data to estimate the model parameters using a multiple linear regression. We then formulate the staffing task as an integer programming problem and derive a near-optimal workforce schedule. Simulations reveal that our proposed workforce policy improves on the existing schedule by about 18% in terms of average delay without increasing the total work hours of the border staff.     

Creating bus timetables with maximal synchronization

This paper addresses the problem of generating a timetable for a given network of buses so as to maximize their synchronization. It attempts to maximize the number of simultaneous bus arrivals at the connection (transfer) nodes of the network. Transit schedulers, taking into account the satisfaction and convenience of the system's users, appreciate the importance of creating a timetable with maximal synchronization, which enables the transfer of passengers from one route to another with minimum waiting time at the transfer nodes. In this paper, the problem is formulated as a mixed integer linear programming problem, and a heuristic algorithm is developed to solve the problem in polynomial time. The efficiency of this algorithm, compared to optimal solutions, is illustrated through a series of examples.     

Dynamic bus holding strategies for schedule reliability: Optimal linear control and performance analysis

As is well known, bus systems are naturally unstable. Without control, buses on a single line tend to bunch, reducing their punctuality in meeting a schedule. Although conventional schedule-based strategies that hold buses at control points can alleviate this problem these methods require too much slack, which slows buses. This delays on-board passengers and increases operating costs.It is shown that dynamic holding strategies based on headways alone cannot help buses adhere to a schedule. Therefore, a family of dynamic holding strategies that use bus arrival deviations from a virtual schedule at the control points is proposed. The virtual schedule is introduced whether the system is run with a published schedule or not. It is shown that with this approach, buses can both closely adhere to a published schedule and maintain regular headways without too much slack.A one-parameter version of the method can be optimized in closed form. This simple method is shown to be near-optimal. To put it in practice, the only data needed in real time are the arrival times of the current bus and the preceding bus at the control point relative to the virtual schedule. The simple method was found to require about 40% less slack than the conventional schedule-based method. When used only to regulate headways it outperforms headway-based methods.     

An online speed profile generation approach for efficient airport ground movement

The precise guidance and control of taxiing aircraft based on four-dimensional trajectories (4DTs) has been recognised as a promising means to ensure safe and efficient airport ground movement in the context of ever growing air traffic demand. In this paper, a systematic approach for online speed profile generation is proposed. The aim is to generate fuel-efficient speed profiles respecting the timing constraints imposed by routing and scheduling, which ensures conflict-free movement of aircraft in the planning stage. The problem is first formulated as a nonlinear optimisation model, which uses a more flexible edge-based speed profile definition. A decomposed solution approach (following the framework of matheuristic) is then proposed to generate feasible speed profiles in real time. The decomposed solution approach reduces the nonlinear optimisation model into three tractable constituent problems. The control point arrival time allocation problem is solved using linear programming. The control point speed allocation problem is solved using particle swarm optimisation. And the complete speed profile between control points is determined using enumeration. Finally, improved speed profiles are generated through further optimisation upon the feasible speed profiles. The effectiveness and advantages of the proposed approach are validated using datasets of real-world airports.     

Robust intermodal hub location under polyhedral demand uncertainty

In this study, we consider the robust uncapacitated multiple allocation p-hub median problem under polyhedral demand uncertainty. We model the demand uncertainty in two different ways. The hose model assumes that the only available information is the upper limit on the total flow adjacent at each node, while the hybrid model additionally imposes lower and upper bounds on each pairwise demand. We propose linear mixed integer programming formulations using a minmax criteria and devise two Benders decomposition based exact solution algorithms in order to solve large-scale problems. We report the results of our computational experiments on the effect of incorporating uncertainty and on the performance of our exact approaches.     

Pick‐up locations and bus allocation for transit‐based evacuation planning with demand uncertainty

This paper develops a decision‐support model for transit‐based evacuation planning under demand uncertainty. Demand uncertainty refers to the uncertainty associated with the number of transit‐dependent evacuees. A robust optimization model is proposed to determine the optimal pick‐up points for evacuees to assemble, and allocate available buses to transport the assembled evacuees between the pick‐up locations and different public shelters. The model is formulated as a mixed‐integer linear program and is solved via a cutting plane scheme. The numerical example based on the Sioux Falls network demonstrates that the robust plan yields lower total evacuation time and is reliable in serving the realized evacuee demand. Copyright © 2012 John Wiley & Sons, Ltd.     

Dispatching control at transfer stations in multi‐hub transit networks

Among dispatching control approaches, the holding option has attracted the most attention in bus control. However, holding a vehicle at a transfer station may exacerbate the delays because more passengers might accumulate at downstream stations and may also affect other connecting routes at other transfer stations. Our problem is to minimize the total costs of dispatching ready vehicles at each transfer station along coordinated routes in a multi‐hub transit network. The total costs include the waiting cost for on‐board passengers, the missed connection costs for late arrival passengers at the subject transfer station and possible transfer costs at downstream transfer stations. We develop a heuristic algorithm to optimize the holding times based on real time information about late vehicles. The results show that ready vehicles should be held longer when the arrival variances of late vehicles are small or when many late connecting passengers are expected.     

Passenger-demands-oriented train scheduling for an urban rail transit network

This paper considers the train scheduling problem for an urban rail transit network. We propose an event-driven model that involves three types of events, i.e., departure events, arrival events, and passenger arrival rates change events. The routing of the arriving passengers at transfer stations is also included in the train scheduling model. Moreover, the passenger transfer behavior (i.e., walking times and transfer times of passengers) is also taken into account in the model formulation. The resulting optimization problem is a real-valued nonlinear nonconvex problem. Nonlinear programming approaches (e.g., sequential quadratic programming) and evolutionary algorithms (e.g., genetic algorithms) can be used to solve this train scheduling problem. The effectiveness of the event-driven model is evaluated through a case study.     

The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems

Most of the studies address issues relating to the delivery from satellites to customers, which is throughout the end part of the linehaul-delivery system. Differing from the long-term strategic problems including the two-echelon vehicle routing problem (2E-VRP), the two-echelon location routing problem (2E-LRP) and the truck and trailer routing problem (TTRP) which make location decisions in depots or satellites, the paper introduces a short-term tactical problem named the two-echelon time-constrained vehicle routing problem in linehaul-delivery systems (2E-TVRP) that does not involve location decisions. The linehaul level and the delivery level are linked through city distribution centers (CDCs) located on the outskirts of cities. The 2E-TVRP has inter-CDC linehaul on the first level and urban delivery from CDCs to satellites on the second level. Vehicle routes on different levels are interacted by time constraints. A mixed integer nonlinear programming model for the 2E-TVRP is put forward, and a mixed integer linear programming model is used as the benchmark model. The Clarke and Wright savings heuristic algorithm (CW) improved by a local search phase is adopted. The 2E-TVRP formulations and the heuristic algorithm are tested by using 140 randomly-generated instances with up to 10 CDCs and 500 satellites. The computational results indicate that the heuristic can effectively solve various instances of the 2E-TVRP.     

Liner ship route schedule design with port time windows

This paper examines a practical tactical liner ship route schedule design problem, which is the determination of the arrival and departure time at each port of call on the ship route. When designing the schedule, the availability of each port in a week, i.e., port time window, is incorporated. As a result, the designed schedule can be applied in practice without or with only minimum revisions. This problem is formulated as a mixed-integer nonlinear nonconvex optimization model. In view of the problem structure, an efficient holistic solution approach is proposed to obtain global optimal solution. The proposed solution method is applied to a trans-Atlantic ship route. The results demonstrate that the port time windows, port handling efficiency, bunker price and unit inventory cost all affect the total cost of a ship route, the optimal number of ships to deploy, and the optimal schedule.     

A hybrid scheme for real‐time prediction of bus trajectories

The uncertainty associated with public transport services can be partially counteracted by developing real‐time models to predict downstream service conditions. In this study, a hybrid approach for predicting bus trajectories by integrating multiple predictors is proposed. The prediction model combines schedule, instantaneous and historical data. The contribution of each predictor as well as values of respective parameters is estimated by minimizing the prediction error using a linear regression heuristic. The hybrid method was applied to five bus routes in Stockholm, Sweden, and Brisbane, Australia. The results indicate that the hybrid method consistently outperforms the timetable and delay conservation prediction method for different route layouts, passenger demands and operation practices. Model validation confirms model transferability and real‐time applicability. Generating more accurate predictions can help service users adjust their travel plans and service providers to deploy proactive management and control strategies to mitigate the negative effects of service disturbances. Copyright © 2017 John Wiley & Sons, Ltd.     

Robust constrained control of uncertain macroscopic fundamental diagram networks

This paper considers modeling and control of uncertain Macroscopic Fundamental Diagram (MFD) systems for multiple-region networks. First, the nonlinear vehicle conservation equations based on MFD dynamics, presented in earlier publications, are transformed to linear equations with parameter uncertainties. The parameter uncertainties include the destination decomposition fractions, that are difficult to estimate in reality. Then, the uncertain linear model is utilized to design a robust feedback controller by an interpolation-based approach. This approach (i) guarantees robustness against all parameter uncertainties, (ii) handle control and state constraints, and (iii) present a computationally cheap solution. The main idea is to interpolate between (i) a stabilizing outer controller that respects the control and state constraints and (ii) an inner robustly stable controller designed by any method. The robust control is further challenged to deal with different relative locations of reference accumulation points on the MFD diagrams. Numerical results for a two-region system show that the uncertain linear model can replace the nonlinear model for modeling and control. Moreover, the robust control law is presented as implicit and explicit solutions, where in the implicit case one linear programming (LP) problem is solved at each time instant, while in the explicit case, the control law is shown as a piecewise affine function of state. Finally, a comparison between the interpolating controller and other controllers in the literature is carried out. The results demonstrate the performance advantages from applying the robust interpolating controller.     

Hybrid model for prediction of bus arrival times at next station

Effective prediction of bus arrival times is important to advanced traveler information systems (ATIS). Here a hybrid model, based on support vector machine (SVM) and Kalman filtering technique, is presented to predict bus arrival times. In the model, the SVM model predicts the baseline travel times on the basic of historical trips occurring data at given time‐of‐day, weather conditions, route segment, the travel times on the current segment, and the latest travel times on the predicted segment; the Kalman filtering‐based dynamic algorithm uses the latest bus arrival information, together with estimated baseline travel times, to predict arrival times at the next point. The predicted bus arrival times are examined by data of bus no. 7 in a satellite town of Dalian in China. Results show that the hybrid model proposed in this paper is feasible and applicable in bus arrival time forecasting area, and generally provides better performance than artificial neural network (ANN)–based methods. Copyright © 2010 John Wiley & Sons, Ltd.     

Optimally combined headway and timetable reliable public transport system

This paper presents a model-based multiobjective control strategy to reduce bus bunching and hence improve public transport reliability. Our goal is twofold. First, we define a proper model, consisting of multiple static and dynamic components. Bus-following model captures the longitudinal dynamics taking into account the interaction with the surrounding traffic. Furthermore, bus stop operations are modeled to estimate dwell time. Second, a shrinking horizon model predictive controller (MPC) is proposed for solving bus bunching problems. The model is able to predict short time-space behavior of public transport buses enabling constrained, finite horizon, optimal control solution to ensure homogeneity of service both in time and space. In this line, the goal with the selected rolling horizon control scheme is to choose a proper velocity profile for the public transport bus such that it keeps both timetable schedule and a desired headway from the bus in front of it (leading bus). The control strategy predicts the arrival time at a bus stop using a passenger arrival and dwell time model. In this vein, the receding horizon model predictive controller calculates an optimal velocity profile based on its current position and desired arrival time. Four different weighting strategies are proposed to test (i) timetable only, (ii) headway only, (iii) balanced timetable - headway tracking and (iv) adaptive control with varying weights. The controller is tested in a high fidelity traffic simulator with realistic scenarios. The behavior of the system is analyzed by considering extreme disturbances. Finally, the existence of a Pareto front between these two objectives is also demonstrated.     

Bus maintenance systems and maintenance scheduling: model formulations and solutions

This paper deals with the problem of scheduling bus maintenance activities. The scheduling of maintenance activities is an important component in bus transit operations planning process. The other components include network route design, setting timetables, scheduling vehicles, and assignment of drivers. This paper presents a mathematical programming approach to the problem. This approach takes as input a given daily operating schedule for all buses assigned to a depot along with available maintenance resources. It, then, attempts to design daily inspection and maintenance schedules for the buses that are due for inspection so as to minimize the interruptions in the daily bus operating schedule, and maximize the utilization of the maintenance facilities. Three integer programming formulations are presented and different properties of the problem are discussed. Several heuristic methods are presented and tested. Some of these procedures produce very close to optimal solutions very efficiently. In some cases, the computational times required to obtain these solutions are less than 1% of the computational time required for the conventional branch and bound algorithm. Several small examples are offered and the computational results of solving the problem for an actual, 181-bus transit property are reported.     

Optimizing sustainable feeder bus operation considering realistic networks and heterogeneous demand

A mathematical model is developed to optimize social and fiscal sustainable operation of a feeder bus system considering realistic network and heterogeneous demand. The objective total profit is a nonlinear, mixed integer function, which is maximized by optimizing the number of stops, headway, and fare. The stops are located which maximize the ridership. The demand elasticity for the bus service is dependent on passengers' access distance, wait time, in‐vehicle time, and fare. An optimization algorithm is developed to search for the optimal solution that maximizes the profit. The modeling approach is applied to planning a bus transit system within Woodbridge, New Jersey. Copyright © 2011 John Wiley & Sons, Ltd.