Optimization of a feeder-bus route design by using a multiobjective programming approach

This paper presents a feeder-bus route design model, capable of minimizing route length, minimizing maximum route travel time of planned routes, and maximizing service coverage for trip generation. The proposed model considers constraints of route connectivity, subtour prevention, travel time upper bound of a route, relationships between route layout and service coverage, and value ranges of decision variables. Parameter uncertainties are dealt with using fuzzy numbers, and the model is developed as a multiobjective programming problem. A case study of a metro station in Taichung City, Taiwan is then conducted. Next, the programming problem in the case study is solved, based on the technique for order preference by similarity to ideal solution approach to obtain the compromise route design. Results of the case study confirm that the routes of the proposed model perform better than existing routes in terms of network length and service coverage. Additionally, increasing the number of feeder-bus routes decreases maximum route travel time, increases service coverage, and increases network length. To our knowledge, the proposed model is the first bus route design model in the literature to consider simultaneously various stakeholder needs and support for bus route planners in developing alternatives for further evaluation efficiently and systematically.     

Analogy of fixed route shared taxi (taxi khattee) and bus services under various demand density and economical conditions

Taxi khattee is a fixed route unregulated shared taxi. It is a very common mode of transportation in Iran. Fixed route, unscheduled operation, open, unlimited pick‐up and drop‐off locations, and share ride are common features of taxi khattees. Low passenger capacity and working in high demand corridors provides for the possibility of high service frequencies any time of the day. Taxi khattees are similar to jitneys, which are obsolete or illegal in many countries. The aim of this research is to design transit network of an area using taxi khattees in addition to buses. The methodology employed in this paper simultaneously considers the costs to the users and operators on the one hand, and those of the public non‐users on the other hand. Taxi khattees are used in the design of a multimodal network along with buses to characterize the appropriate economic domain for their use. Moreover, their operation indices are compared against those of buses. A sensitivity analysis is carried out on various performance measures. Results show taxi khattees should be used in areas where population density is low, work force is inexpensive, social costs are not considered in fare calculation, and users' value of time is high. The study contradicts the common belief that since taxi khattees provide a high frequency compared to buses, they are economically plausible to use in a transit fleet. Copyright © 2011 John Wiley & Sons, Ltd.     

Proactive route guidance to avoid congestion

We propose a proactive route guidance approach that integrates a system perspective: minimizing congestion, and a user perspective: minimizing travel inconvenience. The approach assigns paths to users so as to minimize congestion while not increasing their travel inconvenience too much. A maximum level of travel inconvenience is ensured and a certain level of fairness is maintained by limiting the set of considered paths for each Origin-Destination pair to those whose relative difference with respect to the shortest (least-duration) path, called travel inconvenience, is below a given threshold. The approach hierarchically minimizes the maximum arc utilization and the weighted average experienced travel inconvenience. Minimizing the maximum arc utilization in the network, i.e., the ratio of the number of vehicles entering an arc per time unit and the maximum number of vehicles per time unit at which vehicles can enter the arc and experience no slowdown due to congestion effects, is a system-oriented objective, while minimizing the weighted average experienced travel inconvenience, i.e., the average travel inconvenience over all eligible paths weighted by the number of vehicles per time unit that traverse the path, is a user-oriented objective. By design, to ensure computational efficiency, the approach only solves linear programming models. In a computational study using benchmark instances reflecting a road infrastructure encountered in many cities, we analyze, for different levels of maximum travel inconvenience and, the minimum maximum arc utilization and the weighted average experienced travel inconvenience. We find that accepting relatively small levels of maximum travel inconvenience can result in a significant reduction, or avoiding, of congestion.     

Finding time‐robust fuel‐efficient paths for a call‐taxi in a stochastic city road network

Intra‐city commuting is being revolutionized by call‐taxi services in many developing countries such as India. A customer requests a taxi via phone, and it arrives at the right time and at the right location for the pick‐up. This mode of intra‐city travel has become one of the most reliable and convenient modes of transportation for customers traveling for business and non‐business purposes. The increased number of vehicles on city roads and raising fuel costs has prompted a new type of transportation logistics problem of finding a fuel‐efficient and quickest path for a call‐taxi through a city road network, where the travel times are stochastic. The stochastic travel time of the road network is induced by obstacles such as the traffic signals and intersections. The delay and additional fuel consumption at each of these obstacles are calculated that are later imputed to the total travel time and fuel consumption of a path. A Monte‐Carlo simulation‐based approach is proposed to identify unique fuel‐efficient paths between two locations in a city road network where each obstacle has a delay distribution. A multi‐criteria score is then assigned to each unique path based on the probability that the path is fuel efficient, the average travel time of the path and the coefficient of variation of the travel times of the path. Copyright © 2016 John Wiley & Sons, Ltd.     

Congestion-aware system optimal route choice for shared autonomous vehicles

We study the shared autonomous vehicle (SAV) routing problem while considering congestion. SAVs essentially provide a dial-a-ride service to travelers, but the large number of vehicles involved (tens of thousands of SAVs to replace personal vehicles) results in SAV routing causing significant congestion. We combine the dial-a-ride service constraints with the linear program for system optimal dynamic traffic assignment, resulting in a congestion-aware formulation of the SAV routing problem. Traffic flow is modeled through the link transmission model, an approximate solution to the kinematic wave theory of traffic flow. SAVs interact with travelers at origins and destinations. Due to the large number of vehicles involved, we use a continuous approximation of flow to formulate a linear program. Optimal solutions demonstrate that peak hour demand is likely to have greater waiting and in-vehicle travel times than off-peak demand due to congestion. SAV travel times were only slightly greater than system optimal personal vehicle route choice. In addition, solutions can determine the optimal fleet size to minimize congestion or maximize service.     

Dynamic system-optimal traffic assignment using a state space model

We propose a new mathematical formulation for the problem of optimal traffic assignment in dynamic networks with multiple origins and destinations. This problem is motivated by route guidance issues that arise in an Intelligent Vehicle-Highway Systems (IVHS) environment. We assume that the network is subject to known time-varying demands for travel between its origins and destinations during a given time horizon. The objective is to assign the vehicles to links over time so as to minimize the total travel time experienced by all the vehicles using the network. We model the traffic network over the time horizon as a discrete-time dynamical system. The system state at each time instant is defined in a way that, without loss of optimality, avoids complete microscopic detail by grouping vehicles into platoons irrespective of origin node and time of entry to network. Moreover, the formulation contains no explicit path enumeration. The state transition function can model link travel times by either impedance functions, link outflow functions, or by a combination of both. Two versions (with different boundary conditions) of the problem of optimal traffic assignment are studied in the context of this model. These optimization problems are optimal control problems for nonlinear discrete-time dynamical systems, and thus they are amenable to algorithmic solutions based on dynamic programming. The computational challenges associated with the exact solution of these problems are discussed and some heuristics are proposed.     

Network design for a grid hybrid transit service

In this paper, we develop an analytical model that aids decision-makers in designing a hybrid grid network that integrates a flexible demand responsive service with a fixed route service. The objective of the model is to determine the optimal number of zones in an area where each zone is served by a number of on-demand vehicles. The function of the on-demand vehicles is to transfer passengers to a fixed route line if the destination is to a different zone or to its final destination if it is within the same zone.     

Simulation of fixed route bus travel time

Travel time on fixed route urban bus route is discussed. Given that the travel time is a function of three basic variables, Monte Carlo procedure is used to simulate trips during a specific time interval. Each variable is assumed to have a specific probability distribution with known or estimatable parameters. It is shown that this micro-computer simulation model can be used for examining the effects of traffic management schemes, number of stops and passenger demand on travel time, and subsequently fleet size and level of service.     

A stochastic multimodal reliable network design problem under adverse weather conditions

This paper formulates a network design problem (NDP) for finding the optimal public transport service frequencies and link capacity expansions in a multimodal network with consideration of impacts from adverse weather conditions. The proposed NDP aims to minimize the sum of expected total travel time, operational cost of transit services, and construction cost of link capacity expansions under an acceptable level of variance of total travel time. Auto, transit, bus, and walking modes are considered in the multimodal network model for finding the equilibrium flows and travel times. In the proposed network model, demands are assumed to follow Poisson distribution, and weather‐dependent link travel time functions are adopted. A probit‐based stochastic user equilibrium, which is based on the perceived expected travel disutility, is used to determine the multimodal route of the travelers. This model also considers the strategic behavior of the public transport travelers in choosing their routes, that is, common‐line network. Based on the stochastic multimodal model, the mean and variance of total travel time are analytical estimated for setting up the NDP. A sensitivity‐based solution algorithm is proposed for solving the NDP, and two numerical examples are adopted to demonstrate the characteristics of the proposed model. Copyright © 2014 John Wiley & Sons, Ltd.     

Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations

This study addresses the problem of scheduling a fleet of taxis that are appointed to solely service customers with advance reservations. In contrast to previous studies that have dealt with the planning and operations of a taxi fleet with only electric vehicles (EVs), we consider that most taxi companies may have to operate with fleets comprised of both gasoline vehicles (GVs) and plug-in EVs during the transition from GV to (complete) EV taxi fleets. This paper presents an innovative multi-layer taxi-flow time-space network which effectively describes the movements of the taxis in the dimensions of space and time. An optimization model is then developed based on the time-space network to determine an optimal schedule for the taxi fleet. The objective is to minimize the total operating cost of the fleet, with a set of operating constraints for the EVs and GVs included in the model. Given that the model is formulated as an integer multi-commodity network flow problem, which is characterized as NP-hard, we propose two simple but effective decomposition-based heuristics to efficiently solve the problem with practical sizes. Test instances generated based on the data provided by a Taiwan taxi company are solved to evaluate the solution algorithms. The results show that the gaps between the objective values of the heuristic solutions and those of the optimal solutions are less than 3%, and the heuristics require much less time to obtain the good quality solutions. As a result, it is shown that the model, coupled with the algorithms, can be an effective planning tool to assist the company in routing and scheduling its fleet to service reservation customers.     

Investigating the effect of travel time variability on drivers' route choice decisions in Shanghai,China

Abstract

This paper investigates the effect of travel time variability on drivers' route choice behavior in the context of Shanghai, China. A stated preference survey is conducted to collect drivers' hypothetical choice between two alternative routes with designated unequal travel time and travel time variability. A binary choice model is developed to quantify trade-offs between travel time and travel time variability across various types of drivers. In the model, travel time and travel time variability are, respectively, measured by expectation and standard deviation of random travel time. The model shows that travel time and travel time variability on a route exert similarly negative effects on drivers' route choice behavior. In particular, it is found that middle-age drivers are more sensitive to travel time variability and less likely to choose a route with travel time uncertainty than younger and elder drivers. In addition, it is shown that taxi drivers are more sensitive to travel time and more inclined to choose a route with less travel time. Drivers with rich driving experience are less likely to choose a route with travel time uncertainty.     

An optimization method for sustainable traffic control in urban areas

The optimization of traffic signalization in urban areas is formulated as a problem of finding the cycle length, the green times and the offset of traffic signals that minimize an objective function of performance indices. Typical approaches to this optimization problem include the maximization of traffic throughput or the minimization of vehicles’ delays, number of stops, fuel consumption, etc. Dynamic Traffic Assignment (DTA) models are widely used for online and offline applications for efficient deployment of traffic control strategies and the evaluation of traffic management schemes and policies. We propose an optimization method for combining dynamic traffic assignment and network control by minimizing the risk of potential loss induced to travelers by exceeding their budgeted travel time as a result of deployed traffic signal settings, using the Conditional Value-at-Risk model. The proposed methodology can be easily implemented by researchers or practitioners to evaluate their alternative strategies and aid them to choose the alternative with less potential risk. The traffic signal optimization procedure is implemented in TRANSYT-7F and the dynamic propagation and route choice of vehicles is simulated with a mesoscopic dynamic traffic assignment tool (DTALite) with fixed temporal demand and network characteristics. The proposed approach is applied to a reference test network used by many researchers for verification purposes. Numerical experiments provide evidence of the advantages of this optimization method with respect to conventional optimization techniques. The overall benefit to the performance of the network is evaluated with a Conditional Value-at-Risk Analysis where the optimal solution is the one presenting the least risk for ‘guaranteed’ total travel times.     

A structured flexible transit system for low demand areas

Public transit structure is traditionally designed to contain fixed bus routes and predetermined bus stations. This paper presents an alternative flexible-route transit system, in which each bus is allowed to travel across a predetermined area to serve passengers, while these bus service areas collectively form a hybrid “grand” structure that resembles hub-and-spoke and grid networks. We analyze the agency and user cost components of this proposed system in idealized square cities and seek the optimum network layout, service area of each bus, and bus headway, to minimize the total system cost. We compare the performance of the proposed transit system with those of comparable systems (e.g., fixed-route transit network and taxi service), and show how each system is advantageous under certain passenger demand levels. It is found out that under low-to-moderate demand levels, the proposed flexible-route system tends to have the lowest system cost.     

Routing aspects of electric vehicle drivers and their effects on network performance

This study investigates the routing aspects of battery electric vehicle (BEV) drivers and their effects on the overall traffic network performance. BEVs have unique characteristics such as range limitation, long battery recharging time, and recuperation of energy lost during the deceleration phase if equipped with regenerative braking system (RBS). In addition, the energy consumption rate per unit distance traveled is lower at moderate speed than at higher speed. This raises two interesting questions: (i) whether these characteristics of BEVs will lead to different route selection compared to conventional internal combustion engine vehicles (ICEVs), and (ii) whether such route selection implications of BEVs will affect the network performance. With the increasing market penetration of BEVs, these questions are becoming more important. This study formulates a multi-class dynamic user equilibrium (MCDUE) model to determine the equilibrium flows for mixed traffic consisting of BEVs and ICEVs. A simulation-based solution procedure is proposed for the MCDUE model. In the MCDUE model, BEVs select routes to minimize the generalized cost which includes route travel time, energy related costs and range anxiety cost, and ICEVs to minimize route travel time. Results from numerical experiments illustrate that BEV drivers select routes with lower speed to conserve and recuperate battery energy while ICEV drivers select shortest travel time routes. They also illustrate that the differences in route choice behavior of BEV and ICEV drivers can synergistically lead to reduction in total travel time and the network performance towards system optimum under certain conditions.     

Optimizing the locations of electric taxi charging stations: A spatial–temporal demand coverage approach

Vehicle electrification is a promising approach towards attaining green transportation. However, the absence of charging stations limits the penetration of electric vehicles. Current approaches for optimizing the locations of charging stations suffer from challenges associated with spatial–temporal dynamic travel demands and the lengthy period required for the charging process. The present article uses the electric taxi (ET) as an example to develop a spatial–temporal demand coverage approach for optimizing the placement of ET charging stations in the space–time context. To this end, public taxi demands with spatial and temporal attributes are extracted from massive taxi GPS data. The cyclical interactions between taxi demands, ETs, and charging stations are modeled with a spatial–temporal path tool. A location model is developed to maximize the level of ET service on the road network and the level of charging service at the stations under spatial and temporal constraints such as the ET range, the charging time, and the capacity of charging stations. The reduced carbon emission generated by used ETs with located charging stations is also evaluated. An experiment conducted in Shenzhen, China demonstrates that the proposed approach not only exhibits good performance in determining ET charging station locations by considering temporal attributes, but also achieves a high quality trade-off between the levels of ET service and charging service. The proposed approach and obtained results help the decision-making of urban ET charging station siting.     

Flexible feeder transit route design to enhance service accessibility in urban area

To improve the accessibility of transit system in urban areas, this paper presents a flexible feeder transit routing model that can serve irregular‐shaped networks. By integrating the cost efficiency of fixed‐route transit system and the flexibility of demand responsive transit system, the proposed model is capable of letting operating feeder busses temporarily deviate from their current route so as to serve the reported demand locations. With an objective of minimizing total bus travel time, a new operational mode is then proposed to allow busses to serve passengers on both street sides. In addition, when multiple feeder busses are operating in the target service area, the proposed model can provide an optimal plan to locate the nearest one to response to the demands. A three‐stage solution algorithm is also developed to yield meta‐optimal solutions to the problem in a reasonable amount of time by transforming the problem into a traveling salesman problem. Numerical studies have demonstrated the effectiveness of the proposed model as well as the heuristic solution approach. Copyright © 2015 John Wiley & Sons, Ltd.     

Travel time estimation from sparse floating car data with consistent path inference: A fixed point approach

Estimation of urban network link travel times from sparse floating car data (FCD) usually needs pre-processing, mainly map-matching and path inference for finding the most likely vehicle paths that are consistent with reported locations. Path inference requires a priori assumptions about link travel times; using unrealistic initial link travel times can bias the travel time estimation and subsequent identification of shortest paths. Thus, the combination of path inference and travel time estimation is a joint problem. This paper investigates the sensitivity of estimated travel times, and proposes a fixed point formulation of the simultaneous path inference and travel time estimation problem. The methodology is applied in a case study to estimate travel times from taxi FCD in Stockholm, Sweden. The results show that standard fixed point iterations converge quickly to a solution where input and output travel times are consistent. The solution is robust under different initial travel times assumptions and data sizes. Validation against actual path travel time measurements from the Google API and an instrumented vehicle deployed for this purpose shows that the fixed point algorithm improves shortest path finding. The results highlight the importance of the joint solution of the path inference and travel time estimation problem, in particular for accurate path finding and route optimization.     

Global optimization methods for the discrete network design problem

This paper addresses the discrete network design problem (DNDP) with multiple capacity levels, or multi-capacity DNDP for short, which determines the optimal number of lanes to add to each candidate link in a road network. We formulate the problem as a bi-level programming model, where the upper level aims to minimize the total travel time via adding new lanes to candidate links and the lower level is a traditional Wardrop user equilibrium (UE) problem. We propose two global optimization methods by taking advantage of the relationship between UE and system optimal (SO) traffic assignment principles. The first method, termed as SO-relaxation, exploits the property that an optimal network design solution under SO principle can be a good approximate solution under UE principle, and successively sorts the solutions in the order of increasing total travel time under SO principle. Optimality is guaranteed when the lower bound of the total travel time of the unexplored solutions under UE principle is not less than the total travel time of a known solution under UE principle. The second method, termed as UE-reduction, adds the objective function of the Beckmann-McGuire-Winsten transformation of UE traffic assignment to the constraints of the SO-relaxation formulation of the multi-capacity DNDP. This constraint is convex and strengthens the SO-relaxation formulation. We also develop a dynamic outer-approximation scheme to make use of the state-of-the-art mixed-integer linear programming solvers to solve the SO-relaxation formulation. Numerical experiments based on a two-link network and the Sioux-Falls network are conducted.     

A stochastic optimization model for transit network timetable design to mitigate the randomness of traveling time by adding slack time

Transit network timetabling aims at determining the departure time of each trip of all lines in order to facilitate passengers transferring either to or from a bus. In this paper, we consider a bus timetabling problem with stochastic travel times (BTP-STT). Slack time is added into timetable to mitigate the randomness in bus travel times. We then develop a stochastic integer programming model for the BTP-STT to minimize the total waiting time cost for three types of passengers (i.e., transferring passengers, boarding passengers and through passengers). The mathematical properties of the model are characterized. Due to its computational complexity, a genetic algorithm with local search (GALS) is designed to solve our proposed model (OPM). The numerical results based on a small bus network show that the timetable obtained from OPM reduces the total waiting time cost by an average of 9.5%, when it is tested in different scenarios. OPM is relatively effective if the ratio of the number of through passengers to the number of transferring passengers is not larger than a threshold (e.g., 10 in our case). In addition, we test different scale instances randomly generated in a practical setting to further verify the effectiveness of OPM and GALS. We also find that adding slack time into timetable greatly benefits transferring passengers by reducing the rate of transferring failure.     

Estimating freeway route travel time distributions with consideration to time‐of‐day,inclement weather,and traffic incidents

This paper develops an efficient probabilistic model for estimating route travel time variability, incorporating factors of time‐of‐day, inclement weather, and traffic incidents. Estimating the route travel time distribution from historical link travel time data is challenging owing to the interactions among upstream and downstream links. Upon creating conditional probability function for each link travel time, we applied Monte Carlo simulation to estimate the total travel time from origin to destination. A numerical example of three alternative routes in the City of Buffalo shows several implications. The study found that weather conditions, except for snow, incur minor impact on off‐peak and weekend travel time, whereas peak travel times suffer great variations under different weather conditions. On top of that, inclement weather exacerbates route travel time reliability, even when mean travel time increases moderately. The computation time of the proposed model is linearly correlated to the number of links in a route. Therefore, this model can be used to obtain all the origin to destination travel time distributions in an urban region. Further, this study also validates the well‐known near‐linear relation between the standard deviation of travel time per unit distance and the corresponding mean value under different weather conditions. Copyright © 2016 John Wiley & Sons, Ltd.