Design and development of interactive trip planning for web-based transit information systems

This article presents a Web-based transit information system design that uses Internet Geographic Information Systems (GIS) technologies to integrate Web serving, GIS processing, network analysis and database management. A path finding algorithm for transit network is proposed to handle the special characteristics of transit networks, e.g., time-dependent services, common bus lines on the same street, and non-symmetric routing with respect to an origin/destination pair. The algorithm takes into account the overall level of services and service schedule on a route to determine the shortest path and transfer points. A framework is created to categorize the development of transit information systems on the basis of content and functionality, from simple static schedule display to more sophisticated real time transit information systems. A unique feature of the reported Web-based transit information system is the Internet-GIS based system with an interactive map interface. This enables the user to interact with information on transit routes, schedules, and trip itinerary planning. Some map rendering, querying, and network analysis functions are also provided.     

Accommodating user preferences in ad hoc shared ride trip planning using GIS

Ad hoc shared ride trip planning (SRTP) utilizes mobile devices, geo-sensors and wireless networks to match on-the-fly individual travel demand with transport supply. It represents one of many alternatives to single occupancy vehicle use. This paper outlines a SRTP approach via a two-phase algorithm based on user preferences in a time-dependent routing. Whereas current algorithms use minimization of travel time as the only optimization criterion in trip planning, in the framework presented here, the user can specify multiple trip preferences including travel time, walking time, number of transfers between cars and trip length. Various scenarios are simulated in the city of Tehran (Iran) to demonstrate how preference settings affect the routes of ad hoc shared journeys.     

Travel itinerary problem

In this study, we propose a travel itinerary problem (TIP) which aims to find itineraries with the lowest cost for travelers visiting multiple cities, under the constraints of time horizon, stop times at cities and transport alternatives with fixed departure times, arrival times, and ticket prices. First, we formulate the TIP into a 0–1 integer programming model. Then, we decompose the itinerary optimization into a macroscopic tour (i.e., visiting sequence between cities) selection process and a microscopic number (i.e., flight number, train number for each piece of movement) selection process, and use an implicit enumeration algorithm to solve the optimal combination of tour and numbers. By integrating the itinerary optimization approach and Web crawler technology, we develop a smart travel system that is able to capture online transport data and recommend the optimal itinerary that satisfies travelers’ preferences in departure time, arrival time, cabin class, and transport mode. Finally, we present case studies based on real-life transport data to illustrate the usefulness of itinerary optimization for minimizing travel cost, the computational efficiency of the implicit enumeration algorithm, and the feasibility of the smart travel system.     

A computer model for finding the time-dependent minimum path in a transit system with fixed schedules

This paper describes the development of a computer model and algorithms for finding the time-dependent minimum path between two stations in a multi-route, multi-mode transit system running to fixed schedules. Selection of the minimum path can be based either on journey time or on weighted time. A worked example using a simple transit network is given to illustrate how the model works. The model has several applications in transport planning: it can be used for generating route schedule information to guide transit users, for assisting in route schedule coordination, and for analyzing transit system accessibility.     

Bi-level GA and GIS for Multi-objective TSP Route Planning

Abstract

Route planning is usually carried out to achieve a single objective such as to minimize transport cost, distance traveled or travel time. This article explores an approach to multi-objective route planning using a genetic algorithm (GA) and geographical information system (GIS) approach. The method is applied to the case of a tourist sight-seeing itinerary, where a route is planned by a tour operator to cover a set of places of interest within a given area. The route planning takes into account four criteria including travel time, vehicle operating cost, safety and surrounding scenic view quality. The multi-objective route planning in this paper can be viewed as an extension of the traditional traveling salesman problem (TSP) since a tourist needs to pass through a number of sight points. The four criteria are quantified using the spatial analytic functions of GIS and a generalized cost for each link is calculated. As different criteria play different roles in the route selection process, and the best order of the multiple points needs to be determined, a bi-level GA has been devised. The upper level aims to determine the weights of each criterion, while the lower level attempts to determine the best order of the sights to be visited based on the new generalized cost that is derived from the weights at the upper level. Both levels collaborate during the iterations and the route with the minimal generalized cost is thus determined. The above sight-seeing route planning methodology has been examined in a region within the central area of Singapore covering 19 places of interest.     

The effect of crowding on public transit user travel behavior in a large-scale public transportation system through modeling daily variations

In this paper, the crowding effect in a transit vehicle is modeled in a time-expanded network that considers the daily variation in passenger flows. The study models the daily variation of in-vehicle crowding in a real large-scale transit system. A transit assignment for this real network is modeled and implemented by constructing a crowding cost function that follows the valuation of crowding and by using the reliable shortest path finding method. The direct application of the crowding model to a real network for the Utah Transit Authority indicates that crowd modeling with multi-user classes could influence public transportation system planning and affect the revenues of transit agencies. Moreover, the addition of the disutility factor, crowding, does not always appear to cause an increase in disutility for transit users.     

The dynamic shortest path problem with time-dependent stochastic disruptions

The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.     

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.     

A simulation‐based reliability assessment approach for congested transit network

This paper is an attempt to develop a generic simulation‐based approach to assess transit service reliability, taking into account interaction between network performance and passengers' route choice behaviour. Three types of reliability, say, system wide travel time reliability, schedule reliability and direct boarding waiting‐time reliability are defined from perspectives of the community or transit administration, the operator and passengers. A Monte Carlo simulation approach with a stochastic user equilibrium transit assignment model embedded is proposed to quantify these three reliability measures of transit service. A simple transit network with a bus rapid transit (BRT) corridor is analysed as a case study where the impacts of BRT components on transit service reliability are evaluated preliminarily.     

Modeling a rail transit alignment considering different objectives

An optimization model for station locations for an on-ground rail transit line is developed using different objective functions of demand and cost as both influence the planning of a rail transit alignment. A microscopic analysis is performed to develop a rail transit alignment in a given corridor considering a many-to-one travel demand pattern. A variable demand case is considered as it replicates a realistic scenario for planning a rail transit line. A Genetic Algorithm (GA) based on a Geographical Information System (GIS) database is developed to optimize the station locations for a rail transit alignment. The first objective is to minimize the total system cost per person, which is a function of user cost, operator cost, and location cost. The second objective is to maximize the ridership or the service coverage of the rail transit alignment. The user cost per person is minimized separately as the third objective because the user cost is one of the most important decision-making factors for planning a transit system from the users’ perspective. A transit planner can make an informed decision between various alternatives based on the results obtained using different objective functions. The model is applied in a case study in the Washington, DC area. The optimal locations and sequence of stations obtained using the three objective functions are presented and a comparative study between the results obtained is shown in the paper. In future works we will develop a combinatorial optimization problem using the aforementioned objectives for the rail transit alignment planning and design problem.     

An eco-routing model considering microscopic vehicle operating conditions

The eco-routing problem concerned in this paper addresses the optimal route choice of eco-drivers who aim to meet an emission standard imposed by regulators, while trying to find the path with the minimum total operating cost, which consists of both travel time and fuel costs. The paper first develops fuel consumption and greenhouse gas emissions estimation models that link emission rates to a vehicle’s physical and operational properties. Unlike most studies in the literature, the emission model developed in this paper retains as many microscopic characteristics as feasible in the context of route planning. Specifically, it is able to approximate the impacts of major acceleration events associated with link changes and intersection idling, and yet does not require detailed acceleration data as inputs. The proposed eco-routing model also explicitly captures delays at intersections and the emissions associated with them. Using a simple probabilistic model, the impacts of different turning movements on eco-routing are incorporated. The proposed model is formulated as a constrained shortest path problem and solved by off-the-shelf solvers. Numerical experiments confirm that vehicle characteristics, especially weight and engine displacement, may influence eco-routing. The results also suggest that ignoring the effects of turning movements and acceleration may lead to sub-optimal routes for eco-drivers.     

Planning of integrated transit network for bus and LRT

An integrated approach is suggested for the planning and evaluation of mass transport systems which includes a bus network and LRT/RTS in urban areas. This approach involves a simplified procedure for determining mass transit demand, bus route network generation and evaluation, light or rapid transit corridor identification and its patronage determination in the presence of bus networks. Scheduling of a mass transportation system based on marginal ridership concept is also suggested for a given fleet size. All the three major components (demand estimation, route network generation and scheduling) iterate and interact each other with a feedback mechanism for the desired optimal solution in terms of performance indicators. Necessary interactive software packages for all the above subsystems have been developed.     

A simultaneous route-level transit patronage model: demand,supply, and inter-route relationship

In this paper we present a route-level patronage model that incorporates transit demand, supply and inter-route effects in a simultaneous system. The model is estimated at the route-segment level by time of day and direction. The results show strong simultaneity among transit demand, supply and competing routes. Transit ridership is affected by the level of service, which in turn is determined by current demand and ridership in the previous year. The model demonstrates that a service improvement has a twofold impact on ridership; it increases ridership on the route with service changes, but it also reduces the ridership on competing routes so that the net ridership change is small. The model is thus useful for both system-level analysis and route-level service planning.     

Itinerary choice and advance ticket booking for high-speed-railway network services

This paper formulates and examines the passenger flow assignment (itinerary choice) problem in high-speed railway (HSR) systems with multiple-class users and multiple-class seats, given the train schedules and time-varying travel demand. In particular, we take into account advance booking cost of travelers in the itinerary choice problem. Rather than a direct approach to model advance booking cost with an explicit cost function, we consider advance booking cost endogenously, which is determined as a part of the passenger choice equilibrium. We show that this equilibrium problem can be formulated as a linear programming (LP) model based on a three-dimension network representation of time, space, and seat class. At the equilibrium solution, a set of Lagrange multipliers for the LP model are obtained, which are associated with the rigid in-train passenger capacity constraints (limited numbers of seats). We found that the sum of the Lagrange multipliers along a path in the three-dimension network reflects the advance booking cost of tickets (due to advance/early booking to guarantee availability) perceived by the passengers. Numerical examples are presented to demonstrate and illustrate the proposed model for the passenger assignment problem.     

Long-term planning for ring-radial urban rail transit networks

Extensive work exists on regular rail network planning. However, few studies exist on the planning and design of ring-radial rail transit systems. With more ring transit lines being planned and built in Asia, Europe and the America's, a detailed study on ring transit lines is timely. An analytical model to find the optimal number of radial lines in a city for any demand distribution is first introduced. Secondly, passenger route choice for different rail networks is analyzed, for a many-to-many Origin-Destination (OD) demand distribution, based on a total travel time cost per passenger basis. The routes considered are: (1) radial lines only; (2) ring line only or radial lines and ring line combined; or (3) direct access to a destination without using the rail system. Mathematica and Matlab are used to code the route choice model. A cost-benefit optimization model to identify the feasibility and optimality of a ring line is proposed. Unlike simulations and agent-based models, this model is shown to be easily transferable to many ring-radial transit networks. The City of Calgary is used as an example to illustrate the applicability of each model. The existing urban rail network and trip distribution are major influencing factors in judging the feasibility and optimal location of the ring line. This study shows the potential net benefit of introducing a ring line by assessing changes in passengers’ costs. The changes in passenger cost parameters, such as ride cost and access cost, are shown to greatly influence the feasibility of a ring line.     

Estimating the most likely space–time paths,dwell times and path uncertainties from vehicle trajectory data: A time geographic method

Global Positioning System and other location-based services record vehicles’ spatial locations at discrete time stamps. Considering these recorded locations in space with given specific time stamps, this paper proposes a novel time-dependent graph model to estimate their likely space–time paths and their uncertainties within a transportation network. The proposed model adopts theories in time geography and produces the feasible network–time paths, the expected link travel times and dwell times at possible intermediate stops. A dynamic programming algorithm implements the model for both offline and real-time applications. To estimate the uncertainty, this paper also develops a method based on the potential path area for all feasible network–time paths. This paper uses a set of real-world trajectory data to illustrate the proposed model, prove the accuracy of estimated results and demonstrate the computational efficiency of the estimation algorithm.     

User perspectives in public transport timetable optimisation

The present paper deals with timetable optimisation from the perspective of minimising the waiting time experienced by passengers when transferring either to or from a bus. Due to its inherent complexity, this bi-level minimisation problem is extremely difficult to solve mathematically, since timetable optimisation is a non-linear non-convex mixed integer problem, with passenger flows defined by the route choice model, whereas the route choice model is a non-linear non-continuous mapping of the timetable. Therefore, a heuristic solution approach is developed in this paper, based on the idea of varying and optimising the offset of the bus lines. Varying the offset for a bus line impacts the waiting time passengers experience at any transfer stop on the bus line.In the bi-level timetable optimisation problem, the lower level is a transit assignment calculation yielding passengers’ route choice. This is used as weight when minimising waiting time by applying a Tabu Search algorithm to adapt the offset values for bus lines. The updated timetable then serves as input in the following transit assignment calculation. The process continues until convergence.The heuristic solution approach was applied on the large-scale public transport network in Denmark. The timetable optimisation approach yielded a yearly reduction in weighted waiting time equivalent to approximately 45 million Danish kroner (9 million USD).     

Two-phase stochastic program for transit network design under demand uncertainty

This paper develops a reliability-based formulation for rapid transit network design under demand uncertainty. We use the notion of service reliability to confine the stochastic demand into a bounded uncertainty set that the rapid transit network is designed to cover. To evaluate the outcome of the service reliability chosen, flexible services are introduced to carry the demand overflow that exceeds the capacity of the rapid transit network such designed. A two-phase stochastic program is formulated, in which the transit line alignments and frequencies are determined in phase 1 for a specified level of service reliability; whereas in phase 2, flexible services are determined depending on the demand realization to capture the cost of demand overflow. Then the service reliability is optimized to minimize the combined rapid transit network cost obtained in phase 1, and the flexible services cost and passenger cost obtained in phase 2. The transit line alignments and passenger flows are studied under the principles of system optimal (SO) and user equilibrium (UE). We then develop a two-phase solution algorithm that combines the gradient method and neighborhood search and apply it to a series of networks. The results demonstrate the advantages of utilizing the two-phase formulation to determine the service reliability as compared with the traditional robust formulation that pre-specifies a robustness level.     

An algorithm for finding reasonable paths in transit networks

In this paper, reasonable paths in transit networks are defined as possible paths that satisfy the acceptable time criterion and transfer‐walk criterion. A recursive algorithm for finding all of the reasonable paths in a transit network that does not involve a rapid increase in program run‐time with network size is presented. Realistic transit networks in Hong Kong and Guangzhou were selected as case studies of the different phases of the development of a trip planning system. Transport planning practitioners and potential users were invited to test the system to evaluate its performance. The results of the prototype evaluation were satisfactory, and the viability of the system as a useful tool for supporting decision‐making has been confirmed by the positive feedback that was obtained from survey questionnaires.     

Optimal stop spacing and headway of congested transit system considering realistic wait times

Abstract

This paper revisits the classical transit scheduling problem and investigates the relationship between stop spacing and headway, considering realistic wait time and operable transit capacity. Headway and stop spacing are important determinants for planning a transit system, which influence the service level as well as the cost of operation. A mathematical model is developed, and the objective function is user travel time which is minimized by the optimized stop spacing and headway, subject to the constraints of operable fleet size and route capacity. Optimal stop spacing and headway solutions are obtained in a numerical example. Sensitivity analysis is conducted, and the effect of model parameters on user travel time is explored.