Optimal recharging strategies for electric vehicle fleets with duration constraints

Electrical vehicles (EVs) have become a popular green transportation means recently because they have lower energy consumption costs and produce less pollution. The success of EVs relies on technologies to extend their driving range, which can be achieved by the good deployment of EV recharging stations. This paper considers a special EV network composed of fixed routes for an EV fleet, where each EV moves along its own cyclic tour of depots. By setting up a recharging station on a depot, an EV can recharge its battery for no longer than a pre-specified duration constraint. We seek an optimal deployment of recharging stations and an optimal recharging schedule for each EV such that all EVs can continue their tours in the planning horizon with minimum total costs. To solve this difficult location problem, we first propose a mixed integer program (MIP) formulation and then derive four new valid inequalities to shorten the solution time. Eight MIP models, which were created by adding different combinations of the four valid inequalities to the basic model, have been implemented to test their individual effectiveness and synergy over twelve randomly generated EV networks. Valuable managerial insights into the usage of valid inequalities and the relations between the battery capacity and the total costs, number of recharging facilities to be installed, and running time are analyzed.     

Locating rental stations and bikeways in a public bike system

To determine the spatial distribution of rental stations and bikeways in a public bike system, this paper proposes a facility location and network design model. The model is developed as a multi-objective programing problem that considers four objectives (minimizing cyclist risk, maximizing cyclist comfort, minimizing adverse impacts on traffic and maximizing service coverage) and multiple constraints (monetary budget, network connectivity, station spacing, bikeway types, station number and value ranges of decision variables). The ε-constraint method solves the programing problem for the public bike system in Daan District, Taipei City, Taiwan. The nine non-dominated alternatives generated are all markedly better than existing locations of rental stations and bikeways. Scenario analysis results indicate that increasing the construction budget for bikeways significantly improves cyclist safety and comfort whilst increasing the adverse impact on traffic. Planners can use this model to develop public bike systems that spatially integrate rental stations and bikeway networks.     

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.     

Network equilibrium models with battery electric vehicles

The limited driving ranges, the scarcity of recharging stations and potentially long battery recharging or swapping time inevitably affect route choices of drivers of battery electric vehicles (BEVs). When traveling between their origins and destinations, this paper assumes that BEV drivers select routes and decide battery recharging plans to minimize their trip times or costs while making sure to complete their trips without running out of charge. With different considerations of flow dependency of energy consumption of BEVs and recharging time, three mathematical models are formulated to describe the resulting network equilibrium flow distributions on regional or metropolitan road networks. Solution algorithms are proposed to solve these models efficiently. Numerical examples are presented to demonstrate the models and solution algorithms.     

Determining locations of charging stations for electric taxis using taxi operation data

The adequate provision of charging infrastructure is critical for the effective deployment of electric taxis. This study attempts to locate charging stations for electric taxis reflecting real-world taxi travel patterns identified from taxis equipped with digital tachographs. Data for one week are processed in order to estimate their charge demand. The estimated temporal distribution of charge demand indicates that it varies day-by-day and hour-by-hour. The maximum set covering model is applied for determining the locations of charging stations. The results show that the pre-specified service distance and service coverage rate (defined by the proportion of total demand served) can be critical factors for determining the number and location of charging stations. These factors should be carefully specified by considering the tradeoff between operational efficiency of charging facilities and user convenience.     

An optimal location choice model for recreation-oriented scooter recharge stations

To minimize air pollution from scooters in Taiwan, the government has promoted electric scooters. However, their range limits these vehicles and the establishment of recharge facilities is important for fostering their use. Short distance recreational trips are the most common use for electric scooters, because their limited. Locating recharging stations is thus important if their use is to be widened. A model is developed and the locations of recharging stations determined using an integer program with a case study offering validation. Sensitivity analyses is performed seeking the minimum recharge time and the length of stay at each site. It is found that the speedy charge method for recharging the battery would significantly reduce the number of recharge stations.     

Deploying public charging stations for electric vehicles on urban road networks

This paper explores how to optimally locate public charging stations for electric vehicles on a road network, considering drivers’ spontaneous adjustments and interactions of travel and recharging decisions. The proposed approach captures the interdependency of different trips conducted by the same driver by examining the complete tour of the driver. Given the limited driving range and recharging needs of battery electric vehicles, drivers of electric vehicles are assumed to simultaneously determine tour paths and recharging plans to minimize their travel and recharging time while guaranteeing not running out of charge before completing their tours. Moreover, different initial states of charge of batteries and risk-taking attitudes of drivers toward the uncertainty of energy consumption are considered. The resulting multi-class network equilibrium flow pattern is described by a mathematical program, which is solved by an iterative procedure. Based on the proposed equilibrium framework, the charging station location problem is then formulated as a bi-level mathematical program and solved by a genetic-algorithm-based procedure. Numerical examples are presented to demonstrate the models and provide insights on public charging infrastructure deployment and behaviors of electric vehicles.     

Lifecycle modeling and assessment of unmanned aerial vehicles (Drones) CO2e emissions

There are no studies that model the potential effectiveness of Unmanned Aerial Vehicles (UAVs) or drones to reduce CO₂e lifecycle (including both utilization and vehicle phase) emissions when compared to conventional diesel vans, electric trucks, electric vans, and tricycles. This study presents a novel analysis of lifecycle UAV and ground commercial vehicles CO₂e emissions. Different route and customer configurations are modeled analytically. Utilizing real-word data, tradeoffs and comparative advantages of UAVs are discussed. Breakeven points for operational emissions are obtained and the results clearly indicate that UAVs are more CO₂e efficient, for small payloads, than conventional diesel vans in a per-distance basis. Drastically different results are obtained when customers can be grouped in a delivery route. UAV deliveries are not more CO₂e efficient than tricycle or electric van delivery services if a few customers can be grouped in a route. Vehicle phase CO₂e emissions for UAVs are significant and must be taken into account. Ground vehicles are more efficient when comparing vehicles production and disposal emissions per delivery.     

Predicting market potential and environmental benefits of deploying electric taxis in Nanjing,China

This paper investigates the market potential and environmental benefits of replacing internal combustion engine (ICE) vehicles with battery electric vehicles (BEVs) in the taxi fleet in Nanjing, China. Vehicle trajectory data collected by onboard global positioning system (GPS) units are used to study the travel patterns of taxis. The impacts of charger power, charging infrastructure coverage, and taxi apps on the feasibility of electric taxis are quantified, considering taxi drivers’ recharging behavior and operating activities. It is found that (1) depending on the charger power and coverage, 19% (with AC Level 2 chargers and 20% charger network coverage) to 56% (with DC chargers and 100% charger network coverage) of the ICE vehicles can be replaced by electric taxis without driving pattern changes; (2) by using taxi apps to find nearby passengers and charging stations, drivers could utilize the empty cruising time to charge the battery, which may increase the acceptance of BEVs by up to 82.6% compared to the scenario without taxi apps; and (3) tailpipe emissions in urban areas could be significantly reduced with taxi electrification: a mixed taxi fleet with 46% compressed-natural-gas-powered (CNG) and 54% electricity-powered vehicles can reduce the tailpipe emissions by 48% in comparison with the fleet of 100% CNG taxis.     

Partial recharge strategies for the electric vehicle routing problem with time windows

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension to the well-known Vehicle Routing Problem with Time Windows (VRPTW) where the fleet consists of electric vehicles (EVs). Since EVs have limited driving range due to their battery capacities they may need to visit recharging stations while servicing the customers along their route. The recharging may take place at any battery level and after the recharging the battery is assumed to be full. In this paper, we relax the full recharge restriction and allow partial recharging (EVRPTW-PR), which is more practical in the real world due to shorter recharging duration. We formulate this problem as a 0–1 mixed integer linear program and develop an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it efficiently. We apply several removal and insertion mechanisms by selecting them dynamically and adaptively based on their past performances, including new mechanisms specifically designed for EVRPTW and EVRPTW-PR. These new mechanisms include the removal of the stations independently or along with the preceding or succeeding customers and the insertion of the stations with determining the charge amount based on the recharging decisions. We test the performance of ALNS by using benchmark instances from the recent literature. The computational results show that the proposed method is effective in finding high quality solutions and the partial recharging option may significantly improve the routing decisions.     

Joint deployment of charging stations and photovoltaic power plants for electric vehicles

The focus of this study is to jointly design charging stations and photovoltaic (PV) power plants with time-dependent charging fee, to improve the management of the coupled transportation and power systems. We first propose an efficient and extended label-setting algorithm to solve the EV joint routing and charging problem that considers recharging amount choices at different stations and loop movement cases. Then, a variational inequality problem is formulated to model the equilibrium of EV traffic on transportation networks, and an optimal power flow model is proposed to model the power network flow with PV power plants and optimally serve the EV charging requirements. Based on the above models for describing system states, we then formulate a model to simultaneously design charging stations, PV plants, and time-dependent charging fee. A surrogate-based optimization (SBO) algorithm is adopted to solve the model. Numerical examples demonstrate that the proposed SBO algorithm performs well. Additionally, important insights concerning the infrastructure design and price management of the coupled transportation and power networks are derived accordingly.     

Predicting disruptions and their passenger delay impacts for public transport stops

Disruptions in public transport can have major implications for passengers and service providers. Our study objective is to develop a generic approach to predict how often different disruption types occur at different stations of a public transport network, and to predict the impact related to these disruptions as measured in terms of passenger delays. We propose a supervised learning approach to perform these predictions, as this allows for predictions for individual stations for each time period, without the requirement of having sufficient empirical disruption observations available for each location and time period. This approach also enables a fast prediction of disruption impacts for a large number of disruption instances, hence addressing the computational challenges that rise when typical public transport assignment or simulation models would be used for real-world public transport networks. To improve transferability of our study results, we cluster stations based on their contribution to network vulnerability using unsupervised learning. This supports public transport agencies to apply the appropriate type of measure aimed to reduce disruptions or to mitigate disruption impacts for each station type. Applied to the Washington metro network, we predict a yearly passenger delay of 5.9 million hours for the total metro network. Based on the clustering, five different types of station are distinguished. Stations with high train frequencies and high passenger volumes located at central trunk sections of the network show to be most critical, along with start/terminal and transfer stations. Intermediate stations located at branches of a line are least critical.

     

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.     

Commuter rail accessibility and house values: The case of the Montreal South Shore,Canada, 1992–2009

While public transportation (PT) plays a crucial role in the social and environmental dimensions, its impacts on the location rent remain poorly known. However, there is a strong connection between PT infrastructures and real estate markets since the former may generate externalities that can influence sales prices. This paper aims at estimating the actual effect of implementing a commuter train service between a major city (Montreal, Canada) and its southern periphery occurring in 2000–2003. Using a difference-in-differences (DID) estimator in the hedonic price model for single-family house sales between 1992 and 2009, the paper estimates the direct marginal price impact of a new commuter train service following changes in access to stations. Results suggest that the opening of a new commuter train service on the Montreal South Shore generates a location premium for houses located in the stations’ vicinity (as measured through walking distance and car driving time) as opposed to houses that do not experience any improvement in accessibility to the commuter train service, either in space or in time. In addition, the new service raises property tax income for involved municipalities by several million dollars a year through enhanced property values.     

Designing an integrated distribution system for catering services for high-speed railways: A three-echelon location routing model with tight time windows and time deadlines

An emerging task in catering services for high-speed railways (CSHR) is to design a distribution system for the delivery of high-quality perishable food products to trains in need. This paper proposes a novel model for integrating location decision making with daily rail catering operations, which are affected by various aspects of rail planning, to meet time-sensitive passenger demands. A three-echelon location routing problem with time windows and time budget constraints (3E-LRPTWTBC) is thus proposed toward formulating this integrated distribution system design problem. This model attempts to determine the capacities/locations of distribution centers and to optimize the number of meals delivered to stations. The model also attempts to generate a schedule for refrigerated cars traveling from distribution centers to rail stations for train loading whereby meals can be catered to trains within tight time windows and sold before a specified time deadline. By relaxing the time-window constraints, a relaxation model that can be solved using an off-the-shelf mixed integer programming (MIP) solver is obtained to provide a lower bound on the 3E-LRPTWTBC. A hybrid cross entropy algorithm (HCEA) is proposed to solve the 3E-LRPTWTBC. A small-scale case study is implemented, which reveals a 9.3% gap between the solution obtained using the HCEA and that obtained using the relaxation model (RM). A comparative analysis of the HCEA and an exhaustive enumeration algorithm indicates that the HCEA shows good performance in terms of computation time. Finally, a case study considering 156 trains on the Beijing-Shanghai high-speed corridor and a large-scale case study considering 1130 trains on the Chinese railway network are addressed in a comprehensive study to demonstrate the applicability of the proposed models and algorithm.     

A multiobjective hierarchical model for locating public facilities on a transportation network: A goal programming approach

This paper introduces a Multiobjective Hierarchical Model (MOHLM) for locating public facilities on a transportation network. The proposed model combines the multiobjective nature of the location-allocation problem with the hierarchical character of some public service systems, such as health care delivery. The model examines both maximum and total weighted travel time, facility utilization, and total travel time from the master facility to the attached subordinate facilities. An iterative goal programing algorithm is used to solve the problem. An example related to the location of health care facilities in a rural area of Greece is used to illustrate the application of the proposed model.     

Optimal deployment of charging lanes for electric vehicles in transportation networks

Given the rapid development of charging-while-driving technology, we envision that charging lanes for electric vehicles can be deployed in regional or even urban road networks in the future and thus attempt to optimize their deployment in this paper. We first develop a new user equilibrium model to describe the equilibrium flow distribution across a road network where charging lanes are deployed. Drivers of electric vehicles, when traveling between their origins and destinations, are assumed to select routes and decide battery recharging plans to minimize their trip times while ensuring to complete their trips without running out of charge. The battery recharging plan will dictate which charging lane to use, how long to charge and at what speed to operate an electric vehicle. The speed will affect the amount of energy recharged as well as travel time. With the established user equilibrium conditions, we further formulate the deployment of charging lanes as a mathematical program with complementarity constraints. Both the network equilibrium and design models are solved by effective solution algorithms and demonstrated with numerical examples.     

Analysis of timer-based message dissemination protocols for inter-vehicle communications

Message dissemination protocols are a key component of the communication infrastructure of the Intelligent Transportation System. They have been targeted by several research and standardization efforts. An especially interesting class of dissemination protocols are so called timer (or delay) based ones. The recently standardized GeoBroadcast service of the GeoNetworking protocol of ETSI falls into this category. This work lays out an analytical model of message coverage distance and delivery delay with timer-based dissemination protocols in a highway environment. The model is based on the assumption of (possibly non homogeneous) Poisson vehicle spatial distribution. The model results are compared with computer simulations and measured data driven experiments, including scenarios with traffic discontinuities (signalized intersections). The limits of applicability of the proposed model are assessed, showing that it provides accurate predictions with a wide range of system parameters for highway scenarios. It is also shown that one of the most popular timer-based dissemination protocols achieves the same connectivity and coverage performance of the ideal message flooding.     

Charging infrastructure demands of shared-use autonomous electric vehicles in urban areas

Ride-hailing is a clear initial market for autonomous electric vehicles (AEVs) because it features high vehicle utilization levels and strong incentive to cut down labor costs. An extensive and reliable network of recharging infrastructure is the prerequisite to launch a lucrative AEV ride-hailing fleet. Hence, it is necessary to estimate the charging infrastructure demands for an AEV fleet in advance. This study proposes a charging system planning framework for a shared-use AEV fleet providing ride-hailing services in urban area. We first adopt an agent-based simulation model, called BEAM, to describe the complex behaviors of both passengers and transportation systems in urban cities. BEAM simulates the driving, parking and charging behaviors of the AEV fleet with range constraints and identifies times and locations of their charging demands. Then, based on BEAM simulation outputs, we adopt a hybrid algorithm to site and size charging stations to satisfy the charging demands subject to quality of service requirements. Based on the proposed framework, we estimate the charging infrastructure demands and calculate the corresponding economics and carbon emission impacts of electrifying a ride-hailing AEV fleet in the San Francisco Bay Area. We also investigate the impacts of various AEV and charging system parameters, e.g., fleet size, vehicle battery capacity and rated power of chargers, on the ride-hailing system’s overall costs.     

Stochastic dynamic itinerary interception refueling location problem with queue delay for electric taxi charging stations

A new facility location model and a solution algorithm are proposed that feature (1) itinerary-interception instead of flow-interception; (2) stochastic demand as dynamic service requests; and (3) queueing delay. These features are essential to analyze battery-powered electric shared-ride taxis operating in a connected, centralized dispatch manner. The model and solution method are based on a bi-level, simulation–optimization framework that combines an upper level multiple-server allocation model with queueing delay and a lower level dispatch simulation based on earlier work by Jung and Jayakrishnan. The solution algorithm is tested on a fleet of 600 shared-taxis in Seoul, Korea, spanning 603 km², a budget of 100 charging stations, and up to 22 candidate charging locations, against a benchmark “naïve” genetic algorithm that does not consider cyclic interactions between the taxi charging demand and the charger allocations with queue delay. Results show not only that the proposed model is capable of locating charging stations with stochastic dynamic itinerary-interception and queue delay, but that the bi-level solution method improves upon the benchmark algorithm in terms of realized queue delay, total time of operation of taxi service, and service request rejections. Furthermore, we show how much additional benefit in level of service is possible in the upper-bound scenario when the number of charging stations is unbounded.