论文部分内容阅读
摘要：近年來，电动汽车得到了广泛的关注，但无论是上班族还是服务车队，都没没有广泛的接受对它们的使用。这主要是因为缺乏充电基础设施，阻碍了电动汽车的大范围使用。使用电动汽车的问题在长途旅行或城际旅行中尤为明显。汽车驾驶员会担心在到达目的地之前车辆就没电了，因此里程焦虑是阻碍电动汽车市场普及的主要障碍。在充电站稀少且相距较远的情况下，当车辆在出发点到目的地的过程中中途如何选择一条最短的充电路径就显得尤为重要了。本文将对近年来电车路径领域的相关研究进行总结，进而为自己的研究打下基础并提供一些研究思路。
关键词：时间窗；约束最短路径；充电钻定位；路径选择
一、绪论
由于汽油和柴油动力车辆的大量增加而引起的对石油依赖，能源安全和城市环境质量的担忧导致了研究替代能源车辆的动机（Inês等，2011； Hamu等，2013）。 由于在使用过程中污染少，噪音低，能源利用效率高，电动汽车（BEV）越来越受到研究人员，政策制定者，消费者和工业界的关注（Jung和Jayakrishnan，2012）。
随着电池技术的不断创新和政府政策的支持，电动汽车已经从概念转变为现实。 在中国，政府最近宣布了推广使用电力作为交通运输替代石油的战略计划。 在北京，到2017年，BEV相关的发展目标是发布17万多个BEV和1万个充电点，并且各种财政和机构政策也被国家和地方政府提出并实施，以鼓励建设充电基础设施和居民购买BEV。一般来说，BEV已逐渐进入人们的日常生活。
考虑底层的情况。特别是通过人口稀少地区的旅行，需要驾驶员计划什么时候需要加油。由于标准车辆的加油站数量很多，这些车辆的驾驶员通常只有在油箱低时才考虑加油。寻找一个好的加油点可以通过导航系统和智能手机应用程序得到进一步的帮助，如谷歌地图，为驾车者提供附近加油站的位置。寻找一个好的加油点可以通过导航系统和智能手机应用程序得到进一步的帮助，如谷歌地图，为驾车者提供附近加油站的位置。因此，车辆可能不得不从最直接的路线绕道。同样，理解路径对于电池交换设施来说更为重要，因为基础设施将逐渐涉及普及，至少在初期，电池交换站的密度将非常低。因此，需要开发模型，寻找从起点到目的地的最短路线，包括在整个过程中的必要的充电绕行。
二、电车路径问题相关研究综述
（一）带有时间窗的电车路径相关研究
EVRPTW和一些其他的VRP问题在结构上是相似的，都需要中途停下来加油。Crevier，Cordeau，Laporte提出了多配送中心的VRP。这个模型考虑车辆可以在途中前往配送中心进行补货重装。作者发展了一种启发式算法，它收到适应性记性规划的启发，包括Rochat，Taillard，TS，以及整数规划。尽管多配送中心的例子被提出，但是所有提出实例标准的模型只考虑一个配送中心。因此，Tarantilis，Zachariadis，Kiranoudis重新命名了在中途有重装设施的VRP问题（VRPIRF）。他们提出一种混合导向的局部搜索启发式算法，它具有三步，第一，初始解通过cost-savings启发式算法获得。第二，一种VNS算法通过使用TS在局部搜索的部分中来被应用。第三，结果通过有导向的局部搜索被大大优化。
Michael Schneider，Andreas Stenger提出两个启发式算法来解决带有时间窗和充电站的电车路径问题（EVRPTW），VNS/TS启发式算法，其中，VNS算法的功能为使得搜索多样化，而TS的功能是对经过VNS步骤后随机生成的解在解域中进行高效的搜索。Davis和Figliozzi在2013提出的能量消耗的综合模型可以看作是这个方向的第一步。此外，硬时间窗的限制能明显的增加对车辆的需求以满足顾客需求。这推动了对带有软时间窗的EVRPTW问题的研究，因为购置电车的费用非常的高。
（二）充电站定位问题
加油站的定位由于车辆使用被压缩的天然气或者是电力已经被讨论过了。Mak，Rong，Shen研究电池换电站的位置优化以及研究在优化后的换电设施的电池标准化和技术过程。当然，有一个位置补充的问题没有解决，我们希望在当前没有加油站的地区建立加油站（电池充电，电池交换，其他替代加油选项都可以类似地处理）几位研究人员（Kuby 2005； Kuby和Lim 2007； Upchurch等人2009； Capar等人2012）研究了优化定位这种加油站的问题。通常情况下，他们使用流量捕获或流量拦截模型（Hodgson 1990； Berman et al.1992； Rebello et al.1995）的变体来尽可能多地覆盖给定数量的站点的起点-终点路线。驾驶员在路程中什么时候选择绕道去加油的研究已经被广泛的提出了。另一个位置问题涉及驾驶人口的起讫点交通模式下的电站定位的影响。如果从出发地到目的地的旅客不选择最短路线，而是选择最小化由于加油引起的绕行成本的路线，则增加BE站将使交通模式改变成新的均衡。最近有人对电动汽车对交通分配和交通平衡的影响进行了研究，但研究仅限于电动汽车在不途中充电的行驶距离的假设。（江等人，2012）。也有人研究如何通过改变公共电动车充电站的价格来管理电动汽车充电引起的电力负荷（He et al，2013）。
三、总结
综上本文从带时间窗的电车路径问题，电车约束最短路径问题，两个方面，总结了近年来在电车路径领域的研究成果，并提出了自己的看法，为自己以后的研究方向提供了思路。
（作者单位：重庆交通大学经济与管理学院）
作者简介：竹自强，1994年生，男，研究生。
参考文献
[1]Baldacci R， Mingozzi A， & Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J]. European Journal of Operational Research， 2012（218）：1–6.
[2]Barth M， & Boriboonsomsin K. Energy and emissions impacts of a freeway-based dynamic ecodriving system[J]. Transportation Research. Part D， 2009（14）： 400–410.
[3]Bektas T，Laporte G.The pollution-routing problem. Transportation Research[J].Part B， 2011（45）：1232–1250.
[4]Demir E， Bektas T， & Laporte G. An adaptive large neighborhood search heuristic for thepollution-routing problem[J]. European Journal of Operational Research， 2012（223）：346–359.
[5]Drexl M.Synchronization in vehicle routing—a survey of VRPs with multiple synchronization constraints[J]. Transportation Science，2012（46）：297–316.
关键词：时间窗；约束最短路径；充电钻定位；路径选择
一、绪论
由于汽油和柴油动力车辆的大量增加而引起的对石油依赖，能源安全和城市环境质量的担忧导致了研究替代能源车辆的动机（Inês等，2011； Hamu等，2013）。 由于在使用过程中污染少，噪音低，能源利用效率高，电动汽车（BEV）越来越受到研究人员，政策制定者，消费者和工业界的关注（Jung和Jayakrishnan，2012）。
随着电池技术的不断创新和政府政策的支持，电动汽车已经从概念转变为现实。 在中国，政府最近宣布了推广使用电力作为交通运输替代石油的战略计划。 在北京，到2017年，BEV相关的发展目标是发布17万多个BEV和1万个充电点，并且各种财政和机构政策也被国家和地方政府提出并实施，以鼓励建设充电基础设施和居民购买BEV。一般来说，BEV已逐渐进入人们的日常生活。
考虑底层的情况。特别是通过人口稀少地区的旅行，需要驾驶员计划什么时候需要加油。由于标准车辆的加油站数量很多，这些车辆的驾驶员通常只有在油箱低时才考虑加油。寻找一个好的加油点可以通过导航系统和智能手机应用程序得到进一步的帮助，如谷歌地图，为驾车者提供附近加油站的位置。寻找一个好的加油点可以通过导航系统和智能手机应用程序得到进一步的帮助，如谷歌地图，为驾车者提供附近加油站的位置。因此，车辆可能不得不从最直接的路线绕道。同样，理解路径对于电池交换设施来说更为重要，因为基础设施将逐渐涉及普及，至少在初期，电池交换站的密度将非常低。因此，需要开发模型，寻找从起点到目的地的最短路线，包括在整个过程中的必要的充电绕行。
二、电车路径问题相关研究综述
（一）带有时间窗的电车路径相关研究
EVRPTW和一些其他的VRP问题在结构上是相似的，都需要中途停下来加油。Crevier，Cordeau，Laporte提出了多配送中心的VRP。这个模型考虑车辆可以在途中前往配送中心进行补货重装。作者发展了一种启发式算法，它收到适应性记性规划的启发，包括Rochat，Taillard，TS，以及整数规划。尽管多配送中心的例子被提出，但是所有提出实例标准的模型只考虑一个配送中心。因此，Tarantilis，Zachariadis，Kiranoudis重新命名了在中途有重装设施的VRP问题（VRPIRF）。他们提出一种混合导向的局部搜索启发式算法，它具有三步，第一，初始解通过cost-savings启发式算法获得。第二，一种VNS算法通过使用TS在局部搜索的部分中来被应用。第三，结果通过有导向的局部搜索被大大优化。
Michael Schneider，Andreas Stenger提出两个启发式算法来解决带有时间窗和充电站的电车路径问题（EVRPTW），VNS/TS启发式算法，其中，VNS算法的功能为使得搜索多样化，而TS的功能是对经过VNS步骤后随机生成的解在解域中进行高效的搜索。Davis和Figliozzi在2013提出的能量消耗的综合模型可以看作是这个方向的第一步。此外，硬时间窗的限制能明显的增加对车辆的需求以满足顾客需求。这推动了对带有软时间窗的EVRPTW问题的研究，因为购置电车的费用非常的高。
（二）充电站定位问题
加油站的定位由于车辆使用被压缩的天然气或者是电力已经被讨论过了。Mak，Rong，Shen研究电池换电站的位置优化以及研究在优化后的换电设施的电池标准化和技术过程。当然，有一个位置补充的问题没有解决，我们希望在当前没有加油站的地区建立加油站（电池充电，电池交换，其他替代加油选项都可以类似地处理）几位研究人员（Kuby 2005； Kuby和Lim 2007； Upchurch等人2009； Capar等人2012）研究了优化定位这种加油站的问题。通常情况下，他们使用流量捕获或流量拦截模型（Hodgson 1990； Berman et al.1992； Rebello et al.1995）的变体来尽可能多地覆盖给定数量的站点的起点-终点路线。驾驶员在路程中什么时候选择绕道去加油的研究已经被广泛的提出了。另一个位置问题涉及驾驶人口的起讫点交通模式下的电站定位的影响。如果从出发地到目的地的旅客不选择最短路线，而是选择最小化由于加油引起的绕行成本的路线，则增加BE站将使交通模式改变成新的均衡。最近有人对电动汽车对交通分配和交通平衡的影响进行了研究，但研究仅限于电动汽车在不途中充电的行驶距离的假设。（江等人，2012）。也有人研究如何通过改变公共电动车充电站的价格来管理电动汽车充电引起的电力负荷（He et al，2013）。
三、总结
综上本文从带时间窗的电车路径问题，电车约束最短路径问题，两个方面，总结了近年来在电车路径领域的研究成果，并提出了自己的看法，为自己以后的研究方向提供了思路。
（作者单位：重庆交通大学经济与管理学院）
作者简介：竹自强，1994年生，男，研究生。
参考文献
[1]Baldacci R， Mingozzi A， & Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J]. European Journal of Operational Research， 2012（218）：1–6.
[2]Barth M， & Boriboonsomsin K. Energy and emissions impacts of a freeway-based dynamic ecodriving system[J]. Transportation Research. Part D， 2009（14）： 400–410.
[3]Bektas T，Laporte G.The pollution-routing problem. Transportation Research[J].Part B， 2011（45）：1232–1250.
[4]Demir E， Bektas T， & Laporte G. An adaptive large neighborhood search heuristic for thepollution-routing problem[J]. European Journal of Operational Research， 2012（223）：346–359.
[5]Drexl M.Synchronization in vehicle routing—a survey of VRPs with multiple synchronization constraints[J]. Transportation Science，2012（46）：297–316.