The electric vehicle touring problem

The increasing concern over global warming has led to the rapid development of the electric vehicle industry. Electric vehicles (EVs) have the potential to reduce the greenhouse effect and facilitate more efficient use of energy resources. In this paper, we study several EV route planning problems that take into consideration possible battery charging or swapping operations. Given a road network, the objective is to determine the shortest (travel time) route that a vehicle with a given battery capacity can take to travel between a pair of vertices or to visit a set of vertices with several stops, if necessary, at battery switch stations. We present polynomial time algorithms for the EV shortest travel time path problem and the fixed tour EV touring problem, where the fixed tour problem requires visiting a set of vertices in a given order. Based on the result, we also propose constant factor approximation algorithms for the EV touring problem, which is a generalization of the traveling salesman problem.     

Stochastic optimal path problem with relays

This paper studies the optimal path problem for travelers driving with vehicles of a limited range, such as most battery electric vehicles currently available in the market. The optimal path in this problem often consists of several relay points, where the vehicles can be refueled to extend its range. We propose a stochastic optimal path problem with relays (SOPPR), which aims at minimizing a general expected cost while maintaining a reasonable arrival probability. To account for uncertainty in the road network, the travel speed on a road segment is treated as a discrete random variable, which determines the total energy required to traverse the segment. SOPPR is formulated in two stages in this paper. In the first stage, an optimal routing problem is solved repeatedly to obtain the expected costs and arrival probabilities from any node to all refueling nodes and the destination. With this information, the second stage constructs an auxiliary network, on which the sequence of refueling decisions can be obtained by solving another optimal path problem. Label-correcting algorithms are developed to solve the routing problems in both stages. Numerical experiments are conducted to compare the stochastic and deterministic models, to examine the impact of different parameters on the routing results, and to evaluate the computational performance of the proposed algorithms.     

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.     

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.     

A systematic review of route optimisation and pre-emption methods for emergency vehicles

ABSTRACT

Reducing the travel time of emergency vehicles (EVs) is an effective way to improve critical services such as ambulance, fire, and police. Route optimisation and pre-emption are powerful techniques used to reduce EV travel time. This paper presents a systematic literature review of optimisation and pre-emption techniques for routing EVs. A detailed classification of existing techniques is presented along with critical analysis and discussion. The study observes the limitations of existing routing systems and lack of real-world applications of the proposed pre-emption systems, leading to several interesting and important knowledge and implementation gaps that require further investigation. These gaps include optimisations using real-time dynamic traffic data, considering time to travel as a critical parameter within dynamic route planning algorithms, considering advanced algorithms, assessing and minimising the effects of EV routing on other traffic, and addressing safety concerns in traffic networks containing multiple EVs at the same time.     

A computationally efficient simulation model for estimating energy consumption of electric vehicles in the context of route planning applications

The fact that electric vehicles (EVs) are characterized by relatively short driving range not only signifies the importance of routing applications to compute energy efficient or optimal paths, but also underlines the necessity for realistic simulation models to estimate the energy consumption of EVs. To this end, the present paper introduces an accurate yet computationally efficient energy consumption model for EVs, based on generic high-level specifications and technical characteristics. The proposed model employs a dynamic approach to simulate the energy recuperation capability of the EV and takes into account motor overload conditions to represent the vehicle performance over highly demanding route sections. To validate the simulation model developed in this work, its output over nine typical driving cycles is compared to that of the Future Automotive Systems Technology Simulator (FASTSim), which is a simulation tool tested on the basis of real-world data from existing vehicles. The validation results show that the mean absolute error (MAE) of cumulative energy consumption is less than 45 W h on average, while the computation time to perform each driving cycle is of the order of tens of milliseconds, indicating that the developed model strikes a reasonable balance between efficacy of representation and computational efficiency. Comprehensive simulation results are presented in order to exemplify the key features of the model and analyze its output under specific highly aggressive driving cycles for road gradients ranging from −6% to 6%, in support of its usability as a practical solution for estimating the energy consumption in EV routing applications.     

Solving the bicriterion routing and scheduling problem for hazardous materials distribution

Hazardous materials routing and scheduling decisions involve the determination of the minimum cost and/or risk routes for servicing the demand of a given set of customers. This paper addresses the bicriterion routing and scheduling problem arising in hazardous materials distribution planning. Under the assumption that the cost and risk attributes of each arc of the underlying transportation network are time-dependent, the proposed routing and scheduling problem pertains to the determination of the non-dominated time-dependent paths for servicing a given and fixed sequence of customers (intermediate stops) within specified time windows. Due to the heavy computational burden for solving this bicriterion problem, an alternative algorithm is proposed that determines the k-shortest time-dependent paths. Moreover an algorithm is provided for solving the bicriterion problem. The proximity of the solutions of the k-shortest time-dependent path problem with the non-dominated solutions is assessed on a set of problems developed by the authors.     

Ferry service network design: optimal fleet size,routing, and scheduling

The study formulated a ferry network design problem by considering the optimal fleet size, routing, and scheduling for both direct and multi-stop services. The objective function combines both the operator and passengers’ performance measures. Mathematically, the model is formulated as a mixed integer multiple origin–destination network flow problem with ferry capacity constraints. To solve this problem of practical size, this study developed a heuristic algorithm that exploits the polynomial-time performance of shortest path algorithms. Two scenarios of ferry services in Hong Kong were solved to demonstrate the performance of the heuristic algorithm. The results showed that the heuristic produced solutions that were within 1.3% from the CPLEX optimal solutions. The computational time is within tens of seconds even for problem size that is beyond the capability of CPLEX.     

On the degradation of performance for traffic networks with oblivious users

We consider the problem of characterizing user equilibria and optimal solutions for routing in a given network. We extend the known models by considering users oblivious to congestion in the following sense: While in the typical user equilibrium setting the users follow a strategy that minimizes their individual cost by taking into account the (dynamic) congestion due to the current routing pattern, an oblivious user ignores congestion altogether; instead, he or she decides his routing on the basis of cheapest routes on a network without any flow whatsoever. These cheapest routes can be, for example, the shortest paths in the network without any flow. This model tries to capture the fact that a certain percentage of travelers base their route simply on the distances they observe on a map, without thinking (or knowing, or caring) about the delays experienced on this route due to their fellow travelers. In this work we study the effect of such users using as the measure of network performance its price of anarchy, i.e., the ratio of the total latency experienced by the users (oblivious or not) at equilibrium over the social optimum.     

Parametric search for the bi-attribute concave shortest path problem

A bi-attribute concave shortest path (BC-SP) problem seeks to find an optimal path in a bi-attribute network that minimizes a linear combination of two path costs, one of which is evaluated by a nondecreasing concave function. Due to the nonadditivity of its objective function, Bellman’s principle of optimality does not hold. This paper proposes a parametric search method to solve the BC-SP problem, which only needs to solve a series of shortest path problems, i.e., the parameterized subproblems (PSPs). Several techniques are developed to reduce both the number of PSPs and the computation time for these PSPs. Specifically, we first identify two properties of the BC-SP problem to guide the parametric search using the gradient and concavity of its objective function. Based on the properties, a monotonic descent search (MDS) and an intersection point search (IPS) are proposed. Second, we design a speedup label correcting (LC) algorithm, which uses optimal solutions of previously solved PSPs to reduce the number of labeling operations for subsequent PSPs. The MDS, IPS and speedup LC techniques are embedded into a branch-and-bound based interval search to guarantee optimality. The performance of the proposed method is tested on the mean-standard deviation shortest path problem and the route choice problem with a quadratic disutility function. Experiments on both real transportation networks and grid networks show that the proposed method reduces the computation time of existing algorithms by one to two orders of magnitude.     

Survey of the operation and system study on wireless charging electric vehicle systems

This survey investigates the state-of-the-art in operations and systems-related studies of wireless charging electric vehicles (EVs). The wireless charging EV is one of emerging transportation systems in which the EV’s battery is charged via wireless power transfer (WPT) technology. The system makes use of charging infrastructure embedded under the surface of the road that transfers electric power to the vehicle while it is in transit. The survey focuses on studies related to both dynamic and quasi-dynamic types of wireless charging EV – charging while in motion and while temporarily stopped during a trip, respectively. The ability to charge EVs while in transit has raised numerous operations and systems issues that had not been observed in conventional EVs. This paper surveys the current research on such issues, including decisions on the allocation of charging infrastructure; cost and benefit analyses; billing and pricing; and other supporting operations and facilities. This survey consists of three parts. The first provides an orienting review of terminology specific to wireless charging EVs; it also reviews some past and ongoing developments and implementations of wireless charging EVs. The second part surveys the research on the operations and systems issues prompted by wireless charging EVs. The third part proposes future research directions. The goal of the survey is to provide researchers and practitioners with an overview of research trends and to provide a guide to promising future research directions.     

Statistical modeling of Electric Vehicle electricity consumption in the Victorian EV Trial,Australia

The market share of Electric Vehicles (EVs), an attractive alternative to conventional vehicles, is expected to exceed 30% of all vehicles by 2033 in Australia. Although the expected EV uptake may place greater burdens on electricity networks, the potential impacts contributed by different EV user categories and vehicle models to peak loads at different times during the day are not well understood. This paper addresses the issue through statistical analysis of the charge events in the Victorian EV Trial in Australia as well as modeling the charging behaviors according to participant categories and vehicle models. The analysis was performed on 4933 charge events that were recorded by both private and public Electric Vehicle Supply Equipment. In total, these events consumed over 33 MW h of energy over 12,170 h by the 178 trial participants, out of which about 70% were household participants while the others were fleet participants. Based on a range of EV uptake scenarios and modeled charging behaviors from the trial, the power demand in the summer of 2032/33 was estimated for all of Victoria. The results of the simulations show that the broad scale uptake of EVs produces a relatively small increase in overall power demand (estimated to be between 5.72% and 9.79% in 2032/33).     

Reverse time-restricted shortest paths: Application to air traffic management

In this paper, we consider a particular class of network flow problems that seeks a shortest path, if it exists, between a source node s and a destination node d in a connected digraph, such that we arrive at node d at a specified time τ while leaving node s no earlier than a lower-bounding time LB, and where the availability of each network link is time-dependent in the sense that it can be traversed only during specified intervals of time. We refer to this problem as the reverse time-restricted shortest path problem (RTSP), and it arises, for example, in the context of generating flight plans within air traffic management approaches under severe convective weather conditions. We show that this problem is NP-hard in general, but is polynomially solvable under a special regularity condition. A pseudo-polynomial time dynamic programming algorithm is developed to solve Problem RTSP, along with an effective heap implementation strategy. Computational results using real flight generation test cases as well as random simulated problems are presented.     

Electric vehicles’ energy consumption measurement and estimation

Use of electric vehicles (EVs) has been viewed by many as a way to significantly reduce oil dependence, operate vehicles more efficiently, and reduce carbon emissions. Due to the potential benefits of EVs, the federal and local governments have allocated considerable funding and taken a number of legislative and regulatory steps to promote EV deployment and adoption. With this momentum, it is not difficult to see that in the near future EVs could gain a significant market penetration, particularly in densely populated urban areas with systemic air quality problems. We will soon face one of the biggest challenges: how to improve efficiency for EV transportation system? This research takes the first step in tackling this challenge by addressing a fundamental issue, i.e. how to measure and estimate EVs’ energy consumption. In detail, this paper first presents a system which can collect in-use EV data and vehicle driving data. This system then has been installed in an EV conversion vehicle built in this research as a test vehicle. Approximately 5 months of EV data have been collected and these data have been used to analyze both EV performance and driver behaviors. The analysis shows that the EV is more efficient when driving on in-city routes than driving on freeway routes. Further investigation of this particular EV driver’s route choice behavior indicates that the EV user tries to balance the trade-off between travel time and energy consumption. Although more data are needed in order to generalize this finding, this observation could be important and might bring changes to the traffic assignment for future transportation system with a significant share of EVs. Additionally, this research analyzes the relationships among the EV’s power, the vehicle’s velocity, acceleration, and the roadway grade. Based on the analysis results, this paper further proposes an analytical EV power estimation model. The evaluation results using the test vehicle show that the proposed model can successfully estimate EV’s instantaneous power and trip energy consumption. Future research will focus on applying the proposed EV power estimation model to improve EVs’ energy efficiency.     

Multi-state supernetwork framework for the two-person joint travel problem

Most travel behavior studies on route and mode choice focus only on an individual level. This paper adopts the concept of multi-state supernetworks to model the two-person joint travel problem (JTP). Travel is differentiated in terms of activity-vehicle-joint states, i.e. travel separately or jointly with which transport mode and with which activities conducted. In each state, route choice can be addressed given the state information and travel preference parameters. The joint travel pattern space is represented as a multi-state supernetwork, which is constructed by assigning the individual and joint networks to all possible states and connecting them via transfer links at joints where individuals can meet or depart. Besides route choice, the choices of where and when to meet, and which transport mode(s) to use can all be explicitly represented in a consistent fashion. A joint path through the supernetwork corresponds to a specific joint travel pattern. Then, JTP is reduced to an optimization problem to find the joint path with the minimum disutility. Three standard shortest path algorithm variants are proposed to find the optimal under different scenarios. The proposed framework further indicates the feasibility of multi-state supernetworks for addressing high dimensional problems and contributes to the design of a next generation of joint routing systems.     

An eco-driving system for electric vehicles with signal control under V2X environment

The benefit of eco-driving of electric vehicles (EVs) has been studied with the promising connected vehicle (i.e. V2X) technology in recent years. Whereas, it is still in doubt that how traffic signal control affects EV energy consumption. Therefore, it is necessary to explore the interactions between the traffic signal control and EV energy consumption. This research aims at studying the energy efficiency and traffic mobility of the EV system under V2X environment. An optimization model is proposed to meet both operation and energy efficiency for an EV transportation system with both connected EVs (CEVs) and non-CEVs. For CEVs, a stage-wise approximation model is implemented to provide an optimal speed control strategy. Non-CEVs obey a car-following rule suggested by the well-known Intelligent Driver Model (IDM) to achieve eco-driving. The eco-driving EV system is then integrated with signal control and a bi-objective and multi-stage optimization problem is formulated. For such a large-scale problem, a hybrid intelligent algorithm merging genetic algorithm (GA) and particle swarm optimization (PSO) is implemented. At last, a validation case is performed on an arterial with four intersections with different traffic demands. Results show that cycle-based signal control could improve both traffic mobility and energy saving of the EV system with eco-driving compared to a fixed signal timing plan. The total consumed energy decreases as the CEV penetration rate augments in general.     

Design framework of large-scale one-way electric vehicle sharing systems: A continuum approximation model

This paper proposes a Continuum Approximation (CA) model for design of a one-way Electrical Vehicle (EV) sharing system that serves a metropolitan area. This model determines the optimal EV sharing station locations and the corresponding EV fleet sizes to minimize the comprehensive system cost, including station construction investment, vehicle charging, transportation and vehicle balancing, under stochastic and dynamic trip demands. This is a very complex problem due to the NP-hard nature of location design, the large number of individual users, and the stochasticity and dynamics of generated trips. Further, the considerable charging time required by EVs distinguishes this problem from traditional car sharing problems where a vehicle is immediately available for pickup after being dropped at a station. We find that the CA approach can overcome these modeling challenges by decomposing the studied area into a number of small neighborhoods that each can be approximated by an Infinite Homogeneous Plane (IHP). We find that the system cost of an IHP is a unimodal function of the station service area size and can be efficiently solved in a sub-linear time by the bisection algorithm. Then integrating the solutions of all IHPs yields an approximate solution to the original heterogeneous area. With numerical experiments, we show that the CA solution is able to estimate the total system cost of the discrete counterpart solution efficiently with good accuracy, even for large-scale heterogeneous problems. This implies that the proposed CA approach is capable of providing a near-optimum solution to the comprehensive design of a practical large-scale EV sharing system. With this model, we also conduct sensitivity analysis to reveal insights into how cost components and system design vary with key parameter values. As far as the author’s knowledge, this study is the first work that addresses design of an EV sharing system considering both longer-term location and fleet size planning and daily vehicle operations. The proposed CA model also extends the CA methodology literature from traditional location problems with stationary demand, single-facility based service to EV sharing problems considering dynamic demands, OD trips, and nonlinear vehicle charging times.     

An integrated modelling approach for the bicriterion vehicle routing and scheduling problem with environmental considerations

The consideration of pollution in routing decisions gives rise to a new routing framework where measures of the environmental implications are traded off with business performance measures. To address this type of routing decisions, we formulate and solve a bi-objective time, load and path-dependent vehicle routing problem with time windows (BTL-VRPTW). The proposed formulation incorporates a travel time model representing realistically time varying traffic conditions. A key feature of the problem under consideration is the need to address simultaneously routing and path finding decisions. To cope with the computational burden arising from this property of the problem we propose a network reduction approach. Computational tests on the effect of the network reduction approach on determining non-dominated solutions are reported. A generic solution framework is proposed to address the BTL-VRPTW. The proposed framework combines any technique that creates capacity-feasible routes with a routing and scheduling method that aims to convert the identified routes to problem solutions. We show that transforming a set of routes to BTL-VRPTW solutions is equivalent to solving a bi-objective time dependent shortest path problem on a specially structured graph. We propose a backward label setting technique to solve the emerging problem that takes advantage of the special structure of the graph. The proposed generic solution framework is implemented by integrating the routing and scheduling method into an Ant Colony System algorithm. The accuracy of the proposed algorithm was assessed on the basis of its capability to determine minimum travel time and fuel consumption solutions. Although the computational results are encouraging, there is ample room for future research in algorithmic advances on addressing the proposed problem.     

Simulation of electric vehicle driver behaviour in road transport and electric power networks

The integration of electric vehicles (EVs) will affect both electricity and transport systems and research is needed on finding possible ways to make a smooth transition to the electrification of the road transport. To fully understand the EV integration consequences, the behaviour of the EV drivers and its impact on these two systems should be studied. This paper describes an integrated simulation-based approach, modelling the EV and its interactions in both road transport and electric power systems. The main components of both systems have been considered, and the EV driver behaviour was modelled using a multi-agent simulation platform. Considering a fleet of 1000 EV agents, two behavioural profiles were studied (Unaware/Aware) to model EV driver behaviour. The two behavioural profiles represent the EV driver in different stages of EV adoption starting with Unaware EV drivers when the public acceptance of EVs is limited, and developing to Aware EV drivers as the electrification of road transport is promoted in an overall context. The EV agents were modelled to follow a realistic activity-based trip pattern, and the impact of EV driver behaviour was simulated on a road transport and electricity grid. It was found that the EV agents’ behaviour has direct and indirect impact on both the road transport network and the electricity grid, affecting the traffic of the roads, the stress of the distribution network and the utilization of the charging infrastructure.     

Critical Review of Time-Dependent Shortest Path Algorithms: A Multimodal Trip Planner Perspective

Abstract

A multimodal trip planner that produces optimal journeys involving both public transport and private vehicle legs has to solve a number of shortest path problems, both on the road network and the public transport network. The algorithms that are used to solve these shortest path problems have been researched since the late 1950s. However, in order to provide accurate journey plans that can be trusted by the user, the variability of travel times caused by traffic congestion must be taken into consideration. This requires the use of more sophisticated time-dependent shortest path algorithms, which have only been researched in depth over the last two decades, from the mid-1990s. This paper will review and compare nine algorithms that have been proposed in the literature, discussing the advantages and disadvantages of each algorithm on the basis of five important criteria that must be considered when choosing one or more of them to implement in a multimodal trip planner.