考虑交通流量和总成本的电动汽车充电站规划研究

针对目标区域充电桩规划需求问题,在对区域充电需求分析和充电站数量估算的基础上,利用以同心圆的圆周和圆心为站址的充电站选址方法,构建以俘获的车流量与充电站所有成本之比最大的数学规划模型.在此基础上,根据南昌市某区电动汽车数量,确定所需要的充电站数量为4~9个,并规划出六种方案,然后对每一种方案的规划目标值进行计算和比较,得出第三种方案即建设6个充电站为最优方案.研究结果有利于完善城市的交通网络,提升城市电动汽车的运营能力.     

基于两阶段求解策略的动态电动车辆路径优化研究

由于政府对新能源汽车的补贴政策和市区对燃油车限行政策的实时,越来越多的物流公司在城市配送中广泛采用电动汽车。然而,电动车续航里程受限,需要在途充电或者换电,同时客户需求的动态性以及充/换电设施的排队等现实因素也应该被考虑。为此,提出了分阶段策略求解动态电动车辆路径优化问题,并建立了两阶段的EVRP模型。其中第一阶段针对静态客户建立了静态EVRP模型,第二阶段在设计了换电站及动态客户插入策略的基础上,建立了动态EVRP模型以路径更新策略。最后,设计改进的CW-TS混合启发式算法来求解静态模型,设计贪婪算法求解动态模型。实验结果表明,模型与算法具有较好的适用性和有效性。     

Minimizing grid capacity in preemptive electric vehicle charging orchestration: Complexity,exact and heuristic approaches

Unlike refueling an internal combustion engine vehicle, charging electric vehicles is time-consuming and results in higher energy consumption. Hence, charging stations will face several challenges in providing high-quality charging services when the adoption of electric vehicles increases. These charging infrastructures must satisfy charging demands without overloading the power grid. In this work, we investigate the problem of scheduling the charging of electric vehicles to reduce the maximum peak power while satisfying all charging demands. We consider a charging station where the installed chargers deliver a preemptive constant charging power. These chargers can either be identical or non-identical. For both cases, we address two optimization problems. First, we study the problem of finding the minimum number of chargers needed to plug a set of electric vehicles giving different arrival and departure times and required energies. We prove that this problem belongs to the complexity class P, and we provide polynomial-time algorithms. Then, we study the problem of minimizing the power grid capacity. For identical chargers, we prove that the problem is polynomial, whereas it is NP-hard in the case of non-identical chargers. We formulate these problems as a mixed-integer linear programming model for both cases. To obtain near-optimal solutions for the NP-hard problem, we propose a heuristic and an iterated local search metaheuristic. Through computational results, we demonstrate the effectiveness of the proposed approaches in terms of reducing the grid capacity.     

Locating Active Sensors on Traffic Networks

Sensors are used to monitor traffic in networks. For example, in transportation networks, they may be used to measure traffic volumes on given arcs and paths of the network. This paper refers to an active sensor when it reads identifications of vehicles, including their routes in the network, that the vehicles actively provide when they use the network. On the other hand, the conventional inductance loop detectors are passive sensors that mostly count vehicles at points in a network to obtain traffic volumes (e.g., vehicles per hour) on a lane or road of the network.This paper introduces a new set of network location problems that determine where to locate active sensors in order to monitor or manage particular classes of identified traffic streams. In particular, it focuses on the development of two generic locational decision models for active sensors, which seek to answer these questions: (1) “How many and where should such sensors be located to obtain sufficient information on flow volumes on specified paths?”, and (2) “Given that the traffic management planners have already located count detectors on some network arcs, how many and where should active sensors be located to get the maximum information on flow volumes on specified paths?”The problem is formulated and analyzed for three different scenarios depending on whether there are already count detectors on arcs and if so, whether all the arcs or a fraction of them have them. Location of an active sensor results in a set of linear equations in path flow variables, whose solution provide the path flows. The general problem, which is related to the set-covering problem, is shown to be NP-Hard, but special cases are devised, where an arc may carry only two routes, that are shown to be polynomially solvable. New graph theoretic models and theorems are obtained for the latter cases, including the introduction of the generalized edge-covering by nodes problem on the path intersection graph for these special cases. An exact algorithm for the special cases and an approximate one for the general case are presented.     

考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法

快速充电站选址是电动汽车运营的重要内容之一。本文考虑电动汽车用户会通过绕行一定距离对车辆进行充电这一特征,建立了一个以电动汽车快速充电站建站成本和旅客整体绕行成本之和最小的双层整数规划模型。本文首先给出了用于生成绕行路径集合的A^*算法,然后设计了一种包含局部迭代搜索的自适应遗传算法对该模型进行求解。为了测试算法性能,通过两个不同规模的算例图与已有求解FPLM问题的遗传算法进行了比较,数值试验部分证明了算法的正确性和有效性。最后引入浙江省的高速路网图,从建站成本和截流量两方面对电池续航里程带来的影响进行了相关的灵敏度分析。     

A general model of road traffic accidents

A general model that relates road traffic accidents to the number of vehicles involved, and the number of primary causes of such accidents, is presented. The model considers traffic accidents as failures of a road traffic network system to meet social and economic constraints, and therefore as a measure of the unreliability of such a system. The equations apply to accidents in the real time domain as well as to mean values per unit of vehicle exposure time or vehicle distance. They also apply to single vehicles and drivers, groups of drivers and fleets of vehicles, and the entire vehicle and driving population. They can be used for sections of a network or for a whole network.The equations used have a large number of terms, hence bias errors are common in road accident investigations.     

Randomized heuristics for handover minimization in mobility networks

A mobile device connects to the cell tower (base station) from which it receives the strongest signal. As the device moves it may connect to a series of towers. The process in which the device changes the base station it is connected to is called handover. A cell tower is connected to a radio network controller (RNC) which controls many of its operations, including handover. Each cell tower handles an amount of traffic and each radio network controller has capacity to handle a maximum amount of traffic from all base stations connected to it. Handovers between base stations connected to different RNCs tend to fail more often than handovers between base stations connected to the same RNC. Handover failures result in dropped connections and therefore should be minimized. The Handover Minimization Problem is to assign towers to RNCs such that RNC capacity is not violated and the number of handovers between base stations connected to different RNCs is minimized. We describe an integer programming formulation for the handover minimization problem and show that state-of-the-art integer programming solvers can solve only very small instances of the problem. We propose several randomized heuristics for finding approximate solutions of this problem, including a GRASP with path-relinking for the generalized quadratic assignment problem, a GRASP with evolutionary path-relinking, and a biased random-key genetic algorithm. Computational results are presented.     

A continuous whole-link travel time model with occupancy constraint

The continuous dynamic network loading problem (CDNLP) aims to compute link travel times and path travel times on a congested network, given time-dependent path flow rates for a given time period. A crucial element of CDNLP is a model of the link performance. Two main modeling frameworks have been used in link loading models: The so-called whole-link travel time (WTT) models and the kinematic wave model of Lighthill–Whitham–Richards (LWR) for traffic flow.In this paper, we reformulate a well-known whole-link model in which the link travel time, for traffic entering a time t, is a function of the number of vehicles on link. This formulation does not require the satisfying of the FIFO (first in, first out) condition. An extension of the basic WTT model is proposed in order to take explicitly into account the maximum number of vehicles that the link can accommodate (occupancy constraint). A solution scheme for the proposed WTT model is derived.Several numerical examples are given to illustrate that the FIFO condition is not respected for the WTT model and to compare the travel time predictions effected by LWR and WTT models.     

Routing a mix of conventional,plug-in hybrid,and electric vehicles

We introduce an electric vehicle routing problem combining conventional, plug-in hybrid, and electric vehicles. Electric vehicles are constrained in their service range by their battery capacity, and may require time-consuming recharging operations at some specific locations. Plug-in hybrid vehicles have two engines, an internal combustion engine and an electric engine using a built-in rechargeable battery. These vehicles can avoid visits to recharging stations by switching to fossil fuel. However, this flexibility comes at the price of a generally higher consumption rate and utility cost.To solve this complex problem variant, we design a sophisticated metaheuristic which combines a genetic algorithm with local and large neighborhood search. All route evaluations, within the approach, are based on a layered optimization algorithm which combines labeling techniques and greedy evaluation policies to insert recharging stations visits in a fixed trip and select the fuel types. The metaheuristic is finally hybridized with an integer programming solver, over a set partitioning formulation, so as to recombine high-quality routes from the search history into better solutions. Extensive experimental analyses are conducted, highlighting the good performance of the algorithm and the contribution of each of its main components. Finally, we investigate the impact of fuel and energy cost on fleet composition decisions. Our experiments show that a careful use of a mixed fleet can significantly reduce operational costs in a large variety of price scenarios, in comparison with the use of a fleet composed of a single vehicle class.     

计及多重阻塞的电动汽车移动储能特性建模

为实现城市交通电力耦合系统在城市道路、充电设施、输电线路阻塞环境下的优化运行,提出了计及多重阻塞的动态交通电力流联合优化方法。首先,基于时空网络模型,提出了计及电动汽车移动、静止、充电、排队模式的队列时空网络模型,构建了适用于电动汽车的车辆调度模型,进而形成动态交通分配模型,以减少交通出行损失。其次,通过优化发电机组、储能等的出力和备用计划,计及城市电网安全、备用约束,构建了安全约束动态经济调度模型,以降低碳排放及发电成本。随后,形成多目标动态优化模型,并将其转换为混合整数凸二次规划问题。最后,在耦合IEEE-30、Sioux Falls系统中验证了所提模型的有效性。     

Equilibrium network design of shared-vehicle systems

An equilibrium network design model is formulated to determine the optimal configuration of a vehicle sharing program (VSP). A VSP involves a fleet of vehicles (bicycles, cars, or electric vehicles) positioned strategically across a network. In a flexible VSP, users are permitted to check out vehicles to perform trips and return the vehicles to stations close to their destinations. VSP operators need to determine an optimal configuration in terms of station locations, vehicle inventories, and station capacities, that maximizes revenue. Since users are likely to use the VSP resources only if their travel utilities improve, a generalized equilibrium based approach is adopted to design the system. The model takes the form of a bi-level, mixed-integer program. Model properties of uniqueness, inefficiency of equilibrium, and transformations that lead to an exact solution approach are presented. Computational tests on several synthetic instances demonstrate the nature of the equilibrium configuration, the trade-offs between operator and user objectives, and insights for deploying such systems.     

Fast paths in large-scale dynamic road networks

Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger part of the road network. We provide computational results that show the efficacy of our approach.     

The static bike relocation problem with multiple vehicles and visits

This paper introduces the static bike relocation problem with multiple vehicles and visits, the objective of which is to rebalance at minimum cost the stations of a bike sharing system using a fleet of vehicles. The vehicles have identical capacities and service time limits, and are allowed to visit the stations multiple times. We present an integer programming formulation, implemented under a branch-and-cut scheme, in addition to an iterated local search metaheuristic that employs efficient move evaluation procedures. Results of computational experiments on instances ranging from 10 to 200 vertices are provided and analyzed. We also examine the impact of the vehicle capacity and of the number of visits and vehicles on the performance of the proposed algorithms.     

Heuristic algorithms for siting alternative-fuel stations using the Flow-Refueling Location Model

This paper presents three heuristic algorithms that solve for the optimal locations for refueling stations for alternative-fuels, such as hydrogen, ethanol, biodiesel, natural gas, or electricity. The Flow-Refueling Location Model (FRLM) locates refueling stations to maximize the flow that can be refueled with a given number of facilities. The FRLM uses path-based demands, and because of the limitations imposed by the driving range of vehicles, longer paths require combinations of more than one station to refuel round-trip travel. A mixed-integer linear programming (MILP) version of the model has been formulated and published and could be used to obtain an optimal solution. However, because of the need for combinations of stations to satisfy demands, a realistic problem with a moderate size network and a reasonable number of candidate sites would be impractical to generate and solve with MILP methods. In this research, heuristic algorithms—specifically the greedy-adding, greedy-adding with substitution and genetic algorithm—are developed and applied to solve the FRLM problem. These algorithms are shown to be effective and efficient in solving complex FRLM problems. For case study purposes, the heuristic algorithms are applied to locate hydrogen-refueling stations in the state of Florida.     

Scheduling networks of queues: Heavy traffic analysis of a simple open network

We consider a queueing network with two single-server stations and two types of customers. Customers of type A require service only at station 1 and customers of type B require service first at station 1 and then at station 2. Each server has a different general service time distribution, and each customer type has a different general interarrival time distribution. The problem is to find a dynamic sequencing policy at station 1 that minimizes the long-run average expected number of customers in the system.The scheduling problem is approximated by a dynamic control problem involving Brownian motion. A reformulation of this control problem is solved, and the solution is interpreted in terms of the queueing system in order to obtain an effective sequencing policy. Also, a pathwise lower bound (for any sequencing policy) is obtained for the total number of customers in the network. We show via simulation that the relative difference between the performance of the proposed policy and the pathwise lower bound becomes small as the load on the network is increased toward the heavy traffic limit.     

Mathematical modelling for optimized control of Moscow's sewer network

An algorithm for the optimized control of a branching urban head-and-gravity sewer network is proposed. The control consists in redistribution of the sewage flows between the network structural components. The algorithm is based on a mathematical model and presupposes the use of a computer. The mathematical model consists of a set of algebraic equations with the structure transporting capacities captured as constraints. The mathematical task of control is stated and solved as an optimization problem. The objective function is the minimization of total electric energy consumption over all the network pumping stations. The assumptions substantiated by practice would reduce the problem to the known problem of linear programming. The discharge through each pumping station of the considered subnetwork of Moscow's sewer network was computed using a mathematical model and was compared to the value observed under the same actual conditions. From this comparison, it was concluded that the proposed algorithm was more successful in controlling the network than was the traditional operation. The correction of the working conditions of some pumping stations of the Moscow sewer subnetwork in accordance with the precalculated time schedule, has allowed a significant decrease in the electric energy consumption for conveyance of the sewage through the network.     

Bottleneck analysis in multiclass closed queueing networks and its application

Asymptotic behavior of queues is studied for large closed multi-class queueing networks consisting of one infinite server station with K classes and M processor sharing (PS) stations. A simple numerical procedure is derived that allows us to identify all bottleneck PS stations. The bottleneck station is defined asymptotically as the station where the number of customers grows proportionally to the total number of customers in the network, as the latter increases simultaneously with service rates at PS stations. For the case when K=M=2, the set of network parameters is identified that corresponds to each of the three possible types of behavior in heavy traffic: both PS stations are bottlenecks, only one PS station is a bottleneck, and a group of two PS stations is a bottleneck while neither PS station forms a bottleneck by itself. In the last case both PS stations are equally loaded by each customer class and their individual queue lengths, normalized by the large parameter, converge to uniformly distributed random variables. These results are directly generalized for arbitrary K=M. Generalizations for K≠M are also indicated. The case of two bottlenecks is illustrated by its application to the problem of dimensioning bandwidth for different data sources in packet-switched communication networks. An engineering rule is provided for determining the link rates such that a service objective on a per-class throughput is satisfied. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于路网的电动汽车快速充电站布局决策研究

大力发展和推广纯电动汽车已成为全世界众多国家的共同选择。但电动汽车有限的续航能力及公共快速充电设施的缺乏,制约着人们的使用和长途出行。本研究针对我国公共快速充电网络建设亟待完善的问题,基于我国主干高速公路网络,对服务途中充电需求的快速充电站科学分布问题建立分布决策模型。研究表明,对续航能力低于200公里的电动汽车,应用最优策略分布的快速充电站数量从50座增加到250座时,可将途中充电需求覆盖率从50%左右提高到90%以上,而对续航能力超过250公里的电动汽车,150座按最优策略分布的快速充电站即能覆盖至少96.49%的途中充电需求。通过对不同续航能力和不同充电站数量约束下共30种情形的分析,本研究不仅能为多情形下充电站分布问题提供最优选址和数量组合决策方案,也为我国充电基础设施的完善及电动汽车产业可持续发展提供有力的理论支持和政策建议。     

A column generation approach for an emission-oriented vehicle routing problem on a multigraph

In this work, an emission-minimizing vehicle routing problem with heterogeneous vehicles and a heterogeneous road and traffic network is considered as it is typical in urban areas. Depending on the load of the vehicle, there exist multiple emission-minimal arcs for traveling between two locations. To solve the vehicle routing problem efficiently, a column generation approach is presented. At the core of the procedure an emission-oriented elementary shortest path problem on a multigraph is solved by a backward labeling algorithm. It is shown that the labeling algorithm can be sped up by adjusting the dual master program and by restricting the number of labels propagated in the sub-problem. The column generation technique is used to setup a fast heuristic as well as a branch-and-price algorithm. Both procedures are evaluated based on test instances with up to 100 customers. It turns out that the heuristic approach is very effective and generates near-optimal solutions with gaps below 0.1% on average while only requiring a fraction of the runtime of the exact approach.     

Discrete time dynamic traffic assignment models and solution algorithm for managed lanes

“Managed” lanes of highways usually refer to lanes that are not open to all types of vehicles, such as “High Occupancy Vehicles” (HOV) lanes and “High Occupancy Toll” (HOT) lanes, etc. The HOV lanes of highways are reserved only for vehicles with a driver and one or more passengers. Whereas, HOT lanes allow all vehicles but require tolls from the vehicles with no passenger except the driver. In this paper, we present a discrete-time traffic assignment system optimum model to predict the optimal traffic flows on managed lanes at various times in the entire planning horizon. This model minimizes the overall delay (travel time) and belongs to the class of dynamic traffic assignment (DTA) problems. When applied to general networks, DTA problems can be large and difficult to solve, but the problem is manageable when it is applied to a network with managed lanes. In particular, the DTA model in this paper for managed lanes is reduced to a mixed integer program for which several efficient heuristic algorithms exist. This paper also discusses the special properties of the discrete-time DTA model, based upon which a heuristic algorithm is proposed. Numerical results show that this algorithm is efficient for many cases of the managed lane problems.