电动汽车质保服务与充电设施建设水平对销量影响的有效性研究

通过构建电动汽车和燃油汽车的微分博弈模型，分析电动汽车质保服务与充电设施建设水平对电动汽车销量的影响。研究结果表明：存在质保服务临界点，只有超过临界点情况下，电动汽车厂商才能有效利用增加质保服务投入策略或延长质保期策略促进电动汽车市场销量，并且增加质保服务投入和延长质保期对促进电动汽车市场销量才具有交互正效应；电动汽车厂商无法在较低质保投入水平下通过降低电动汽车故障率实现提高质保服务投入策略有效性，但在质保期内故障次数大于1情况下，可以在较低质保投入水平下通过降低电动汽车故障率实现延长质保期策略有效性；在充电设施建设水平较低时期，电动汽车厂商合作参与充电设施建设比利用质保服务策略能更有效促进电动汽车销量，当充电设施达到一定水平后，再有效利用质保服务策略提高市场销量。     

基于分支定价算法的电动汽车车辆路径问题

目前,随着电动汽车的普及,物流企业逐渐重视电动汽车的应用。本文考虑到电动汽车在实际应用中的行驶里程、充电耗时以及配送时间等因素,研究含时间窗的电动汽车车辆路径问题,建立了相应的混合整数规划模型,然后改进分支定价算法以求得其最优解。改进的分支定价算法首先根据Dantzig-Wolfe分解原理将原问题分解为基于路径的主问题(MP)和求最短路径的子问题,然后用列生成和动态规划算法在主问题和子问题之间进行迭代以求得主问题线性松弛后的最优解,最后采用基于弧的分支策略求得其整数解。通过用改进的Solomon算例的实验数据,与CPLEX比较验证了模型和算法结果的准确性,并对该问题进行了灵敏度分析,证明了本文提出的算法具有一定的应用价值。     

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

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

考虑多行程与同时取送货的电动车路径问题研究

针对城市物流配送中的电动车辆路径优化问题,考虑电动汽车的充电特性以及车辆多行程和需求点的双向货流,以最小化车辆成本、行驶成本和充电成本为目标,建立考虑多行程与同时取送货的电动车辆路径问题(EVRPMTSPD)模型,并采用列生成算法进行求解.为提高子问题求解速度,提出了基于蚁群算法的启发式寻路算法用以处理较大规模问题,数值实验验证了模型与算法的有效性,表明了考虑多行程和同时取送货能有效降低成本和提高效率.     

基于Hall定理的电动汽车充电服务匹配机制研究

立足未来,大规模电动汽车形成的庞大充电服务市场的有效运行,有赖于电能供求双方匹配交易的顺利完成.基于二分图匹配Hall定理,提出了一种考虑电动汽车、充电设施和电网三方优化的整体框架,并给出了一轮充电服务市场化运行下饱和电动汽车集合的最优匹配方案,算例仿真演示了该机制下的充电匹配交易过程,最后指出了充电服务市场化运行机制下仍待进一步研究的系列重要科学问题,可为未来充电服务平台构建及相关研究提供参考.     

带重入的单台机排序问题

本文考虑带重入的单台机排序问题,重入是指每个工件在机器上加工不止一次.通过把重入模型转化为带平行链约束的排序问题,我们成功地获得了单机重入问题的两个目标函数的多项式时间最优算法,一个是总带权完工时间∑ωjCj,另一个是最大费用函数hmax.     

基于遗传算法的快慢充充电站综合布局优化研究

随着能源和环境问题的日益加剧,电动汽车产业逐渐兴起.作为其运营所必须的基础配套服务设施,充电站的布局优化对于处在发展初期的电动汽车大规模推广应用具有重要意义.兼顾建设运营方和电动汽车用户方综合利益,以目标区域内建设快速充电站和慢速充电站综合费用最小化为目标,以满足电动汽车用户最大充电需求,保证用户充电便利性为约束条件,综合考虑地理位置、充电需求等因素建立了多等级电动汽车充电设施选址模型,并利用遗传算法求解模型.最后,算例表明所提出的方法和模型对目标区域电动汽车充电站的优化布局具有一定可行性和合理性.     

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

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

新能源移动充电车路径优化问题研究

在绿色城市背景下,新能源汽车的数量快速增长,现有公共充电设施的不完善使得移动充电服务应运而生。投入运营成本较高而利润低成为阻碍移动充电业务运营的瓶颈之一,如何通过科学合理的调度提高平台利润成为重要问题。本文研究了移动充电车队的调度和路径优化问题,以平台最大收益为目标,综合考虑顾客软时间窗、移动电池容量以及充电车续航里程等约束,建立数学规划模型;设计了一种最大最小蚁群算法,并通过数值实验验证了模型的合理性和算法的有效性,为移动充电企业运营提供决策参考。     

基于模拟退火算法的充电路径规划

主要利用模拟退火算法解决针对无线传感器网络的充电器路径规划问题,并求得网络中每个传感器对应的最小电池容量.该实际问题可抽象为经典旅行商问题(TSP)以及多旅行商问题(MTSP).针对中小规模的TSP问题,以总路程最小为优化目标,利用模拟退火算法搜索全局最优解;针对MTSP问题,以多条路径中最长的路程和每条支路平均路程的加权之和为优化目标,利用模拟退火算法进行求解.本文将最小电池容量模型简化为线性函数进行求解,并按照实际情况设计部分参数数值和部分参数取值范围,得到每个传感器最小电池容量的具体数值.     

Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem

The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) combines the Generalized Traveling Salesman Problem (GTSP) and the Sequential Ordering Problem (SOP). We present a novel branching technique for the GTSP which enables the extension of a powerful pruning technique. This is combined with some modifications of known bounding methods for related problems. The algorithm manages to solve problem instances with 12–26 groups within a minute, and instances with around 50 groups which are denser with precedence constraints within 24 h.     

Locating replenishment stations for electric vehicles: application to Danish traffic data

Environment-friendly electric vehicles have gained popularity and increased attention in recent years. The deployment of a network of recharging stations is essential given their limited travel range. This paper considers the problem of locating electronic replenishment stations for electric vehicles on a traffic network with flow-based demand. The objective is to optimize the network performance, for example to maximize the flow covered by a prefixed number of stations or to minimize the number of stations needed to cover traffic flows. Two integer linear programming formulations are proposed to model the problem. These models are tested on real-life traffic data collected in Denmark.     

The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra

In this paper we study the polyhedron associated with the General Routing Problem (GRP). This problem, first introduced by Orloff in 1974, is a generalization of both the Rural Postman Problem (RPP) and the Graphical Traveling Salesman Problem (GTSP) and, thus, is NP -hard. We describe a formulation of the problem such that from every non-trivial facet-inducing inequality for the RPP and GTSP polyhedra, we obtain facet-inducing inequalities for the GRP polyhedron. We describe a new family of facet-inducing inequalities for the GRP, the honeycomb constraints, which seem to be very useful for solving GRP and RPP instances. Finally, new classes of facets obtained by composition of facet-inducing inequalities are presented.     

An APF and MPC combined collaborative driving controller using vehicular communication technologies

Collaborative driving is a growing domain of Intelligent Transportation Systems (ITS) which aim to navigate traffic both efficiently and safely. Cooperation between vehicles heavily rely on the comprehensive information collected. With the development of vehicular communication technologies, information can be shared between vehicles or infrastructures through Vehicle-to-Vehicle (V2V)/Vehicle-to-Infrastructure (V2I) data exchange. By taking advantage of data sharing between vehicles, this paper proposes an Artificial Potential Field (APF) and Model Predictive Control (MPC) combined controller to implement collaborative driving in complex environments. Firstly, an APF model ​containing three components is developed to describe the mutual effect and collaboration properties between vehicles and surrounding environments. Afterwards, a MPC cost function for optimized control, considering both kinematic characteristics and environmental effect conveyed by APF, is presented to address the problem of collaborative driving. Such controller is designed from the perspective of multi-objective and multi-constraint optimization which takes the vehicle motion constraints, safety and comfort requirements into consideration. The prominent advantage of the proposed approach is that it can deal with the problems of route planning and manipulating simultaneously. To validate the proposed approach, a variety of scenario simulations are conducted in MATLAB, and the performance of the proposed method are verified.     

A distributed exact algorithm for the multiple resource constrained sequencing problem

Sequencing problems arise in the context of process scheduling both in isolation and as subproblems for general scenarios. Such sequencing problems can often be posed as an extension of the Traveling Salesman Problem. We present an exact parallel branch and bound algorithm for solving the Multiple Resource Constrained Traveling Salesman Problem (MRCTSP), which provides a platform for addressing a variety of process sequencing problems. The algorithm is based on a linear programming relaxation that incorporates two families of inequalities via cutting plane techniques. Computational results show that the lower bounds provided by this method are strong for the types of problem generators that we considered as well as for some industrially derived sequencing instances. The branch and bound algorithm is parallelized using the processor workshop model on a network of workstations connected via Ethernet. Results are presented for instances with up to 75 cities, 3 resource constraints, and 8 workstations.     

Exact algorithms for the traveling salesman problem with draft limits

This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance compared through extensive computational experiments. Optimal solutions are reported for open instances of benchmark problems available in the literature.     

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.     

Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.