基于时间窗约束的纯电动汽车路径规划模型分析

刘颖鑫 （渤海大学 管理学院，辽宁 锦州 121000）

基于时间窗约束的纯电动汽车路径规划模型分析

刘颖鑫 （渤海大学 管理学院，辽宁 锦州 121000）

随着环境污染和资源的日益枯竭，发展低碳经济是我国实现可持续发展的必然之路。物流配送行业作为我国能源消耗和温室气体的主要排放来源，备受人们关注。文章采用纯电动汽车代替传统车辆进行物流配送。通过对纯电动汽车的优点和配送特征的分析，以及对车辆路径问题的分类，提出纯电动汽车路径问题。最后，在考虑传统车辆路径规划问题中的货物装载量、节点访问以及时间等约束，结合电动汽车的电池容量、充电设施、充电时间等特点，构建具有时间窗的纯电动汽车路径规划模型。

纯电动汽车；时间窗约束；路径规划；物流配送

近年来，电子商务的快速发展极大促进了物流快递行业的发展，使得多频次、强时效性的物流配送需求日益增长。电动汽车具有节能环保、噪声小、能源利用率高等优点，因此更加符合社会的发展需求。和传统燃油车辆相比，电动汽车可以改善环境质量、减少对石油能源的消耗，从而实现节能减排的目的，因此引起了国内外的广泛关注，许多物流公司已经开始建立“绿色物流”项目，来减少车辆配送过程中二氧化碳的排放量。采用纯电动汽车进行物流的配送活动，有利于降低物流活动对生态环境的不良影响，同时也有利于实现社会利益和环境利益的统一。因此，伴随着电动汽车的发展，将其应用在城市配送领域已经成为社会发展的趋势。

1 纯电动汽车路径规划问题研究现状分析

1.1 纯电动汽车的优点

纯电动汽车是由可充电电池提供动力，且符合安全法规和道路交通各项要求的汽车[1]。突出的优势在于它对环境的污染小，并减少对石油等不可再生资源的消耗。

（1）节能环保、污染小、噪声小

传统机动车辆的尾气排放是大气污染的主要原因之一，而电能是一种清洁能源，电动汽车以电代油，可以达到改善空气质量的效果。纯电动汽车使用电机驱动，电机工作时产生的噪音远小于传统的内燃机，从而降低了噪声对居民的影响[2]。

（2）降低对石油资源的消耗

电动汽车电量的再次补充，可以通过多种形式获得，例如风能、核能、太阳能等多种可再生能源，从而可以有效降低对化石能源的依赖，减少传统汽车能源短缺之忧。

1.2 纯电动汽车路径问题的分类

纯电动汽车路径规划问题与传统车辆路径规划问题相似。传统车辆路径问题（Vehicle Routing Problem，VRP）的构成要素通常包括配送车辆、顾客节点、货物需求、目标函数和约束条件等。而电动汽车路径问题还包含充电服务设施、以及行驶里程和充电时间的约束，根据研究的侧重点不同，EVRP可以分为不同的类型[3]。具体分类如下所示：

（1）配送车辆属性。根据车辆的种类分为单车型和多车型车辆路径问题；根据车辆的货物装载量分为满载和非满载车辆路径问题；根据车辆的能力限制分为有容积限制和有载重限制的车辆路径问题；按照车辆的类型分为传统燃油机动车和新能源汽车以及混合车辆路径问题。

（2）客户属性。根据客户需求性质分为确定性需求和随机需求车辆路径问题；而根据客户对配送时间的要求可分为有时间窗和无时间窗限制，有时间窗可以分为：软时间窗和硬时间窗以及混合时间窗。软时间窗表示若配送车辆没有将货物在顾客要求的时间窗范围内送达，则将会受到相应的惩罚；而硬时间窗则要求配送车辆必须在客户要求的时间窗范围之内到达。

（3）需求属性。根据需求是否可被拆分，可分为需求可拆分和需求不可拆分车辆路径问题；根据需求服务的种类，分为纯送货车辆路径问题，即车辆将货物送到客户点；纯取货车辆路径问题，车辆对客户点的货物进行收集；以及同时取送货的车辆路径问题，表示为车辆在访问顾客点时，不仅包含装货任务还包括卸货任务。

（4）网络属性。根据网络的不确定性划分，可以分为静态车辆路径问题：在进行车辆路径优化之前，所有与配送车辆相关的信息已经确定，并不会随着时间变化而变化；动态车辆路径问题，进行路径优化之前，所有和车辆相关的信息并不是全部确定而且部分信息会随着时间的变化而变化。

（5）目标函数。根据研究问题的不同，需要构建不同的约束条件和目标函数。从优化目标函数的个数可分为单目标和多目标车辆路径问题，常构建的目标函数包括车辆的行驶距离最短、行驶时间最少、运输车辆的成本最低以及客户的满意度最大化等。

1.3 纯电动汽车路径规划模型约束条件描述

本文将假设一个网络模型，即找到从给定原点到给定目的地的“最佳”路线，中途可能经过充电站进行电量的补充，但规定行驶里程不超过规定的范围d。令网络图G=V,（）E ，V为客户节点集合，E为弧集合。令节点s,t∈V代表电动汽车的起始点和终点。令dij表示每条弧i,j∈E的长度，让F⊆V代表电动汽车充电站的集合。所以将电动汽车最短路径问题定义为在网络图G中，规定电动汽车在行驶距离小于d的情况下，找到从节点s开始并在节点t结束的最短路线。如图1所示，为求解原始车辆路径问题从节点s开始到节点t的最短路线最短的行驶距离为39，途中有颜色的节点5、9、11和13分别代表充电服务设施。

图1 VRP最短行驶路线

（1） 续航能力的约束

电动汽车由于受到自身电池技术的限制，因此行驶的距离相对于较短。目前，我国应用于物流行业配送的电动汽车的续驶里程在200公里左右，虽然可以满足同城配送的需求，但是配送的半径范围远小于传统燃油车辆。如果图1中的d=20，则电动车在行驶过程中为了能到达目的地，即完成配送任务，则车辆至少要到达充电站一次。在限制的范围内，车辆可以到达节点5和节点9这两个充电站进行充电。然后再选择其中一个节点作为起始点，继续完成配送任务。在行驶里程为d的约束下，从节点s开始可以到达所有节点的最短路径如图2所示，蓝色方框代表从s开始所能到达节点的距离。

（2） 充电服务设施

传统的VRP，访问的顶点为服务的对象或者是配送中心，每两个顶点之间恰好连接一次，行驶的过程中没有回路，即为完整的图。但EVRP访问的顶点还包括可能经过的充电站。近几年，我国极大地鼓励电动汽车的发展，并且出台了很多优惠政策，使其市场占有率逐年增加。但电动汽车充电服务设施还处于初期建设阶段，充电服务不能满足发展需要。传统燃油汽车的加油站相对较多，配送车辆在行驶的过程中寻找加油站的耗费时间较小。因此，研究电动汽车配送路径更加重要。电动汽车因为续航能力的约束，在行驶过程中当剩余的电量不足以继续配送时，需要进入充电站进行电量的补充。由于目前充电站的布局并不完善，因此在配送路径中，有的充电站可能不被访问或者不止一次被访问，导致配送距离大幅度的增加，从而增加物流的配送成本。如图3所示为电动车在配送过程中可能的行驶路线。

图2 行驶里程约束下可到达节点的最短路径

图3 电动汽车可能的行驶路线

因为在配送过程中增加了对充电站的访问，可能会造成行驶线路的迂回，因此可以考虑电动车从起始点到达目的地经过加油站的最短行驶距离，此时把充电站看成访问的坐标点。行驶的路线如图4所示，图中数值代表最短可行驶路径的距离。此时该网络图中最短的行驶路径为s-5（充电站） -13（充电站）-t，行驶距离为43。对应原网络图中电动车的行驶路线为s-1-4-5（充电站） -4-7-13（充电站） -14-t。与图1中的最短行驶路段7-12-14相比，包括了迂回路线4-5-4和绕行路线7-13-14。具体如图5所示。

图4 配送车辆访问加油站的最短行驶路线

图5 电动汽车的最短行驶路线

对于以电动汽车为主的物流企业，电动汽车前去充电的行驶路程较长，所以在车辆路径问题中要考虑充电服务设施的位置。因此对电动汽车充电服务设施进行合理的规划，不仅能加快电动汽车的普及，降低温室气体的排放和改善环境质量，而且有利于电动汽车进行电量的补充。

（3） 充电方式

电动汽车的充电模式有三种：可以分为快速充电、慢速充电和机械充电[4]。快速充电模式也称作应急充电，短时间内为电池提供大电流的充电服务，这种充电模式可以满足顾客在短时间内的用电需求，充电时间大概在20分钟左右。因为对电池进行大功率的充电，所以加速缩短了电池的使用寿命。但目前，我国在建设大型充电服务设施的时候，多采用此种充电方式。配送车辆在行驶的过程中可以采取快速充电方式，为了提高配送过程中顾客的满意度，所以应该把行驶过程中的充电时间考虑在规划模型中。

而慢速充电模式也称为普通充电，该充电过程的电流较小，可在家中或停车场等地方对车辆进行充电。但充电的时间相对较长，一般在6到8小时之间，会给电动汽车用户的出行带来不便，有时会难以满足电动汽车用户紧急出行的需求。慢充适合用于每日行驶里程较短的用户，对于电池续航里程较大的电动汽车而言，可以利用晚间停运的时候进行电量的补充，因此注重时效的物流配送车辆在行驶过程中不适合选用此种充电方式。

机械充电模式即更换电动汽车的电池组，该方式是在充电服务设施处由专业人员将快要耗尽电量的电池组取下，然后更换充满电的电池组。更换电池组消耗的时间大约和传统汽车加油的时间相同，一般为5到10分钟，然后将换下的电池组送达到指定的地点完成充电。这种充电方式不仅可以有效减少对电池的损害，延长使用寿命，而且降低了电池的使用成本。

2 纯电动汽车路径规划模型的构建

2.1 纯电动汽车路径问题概述

车辆路径问题（Vehicle Routing Problem，VRP），其目的是尽量减少配送车辆访问客户的运输成本。车辆从配送中心开始进行配送，每个客户只被访问一次，访问全部的客户后再返回到配送中心。目前，已经提出了VRP许多扩展形式，以符合现实世界的约束和条件。车辆路径问题是由学者G.Dantzig和J.Ramser在1959年首先提出的，是物流配送中组合优化领域的热点问题，并广泛地应用于现实生活中。电动汽车路径问题（Electric Vehicle Routing Problem，EVRP）为车辆路径问题的拓展，具体可以描述电动汽车从配送中心出发（已经充满电），依次访问一系列给定的具有不同货物需求的顾客点，运输车辆负责配送货物的同时并规划出适当的行车路线，来满足客户的需求。如果配送过程中超过车辆的货物装载量约束，则车辆将返回配送中心进行装货，如果超过行驶里程的约束，则到最近的充电服务设施去充电。然后配送车辆继续访问客户点，直至访问完所有的客户点，完成配送任务后再返回到配送中心。

2.2 建立模型

随着对电动汽车路径问题的不断研究，根据约束条件的不同，可以构建出不同的模型。如下是在传统车辆路径问题研究的基础上，针对单车型、具有电池容量和货物装载量约束，构建的具有三下标的数学模型[5-10]。模型参数描述如表1所示：

表1 模型参数描述

目标函数：

节点访问约束：

货物装载量约束：

时间约束：

电池容量约束：

0-1决策变量：

基于EVRP问题的基本含义可归纳为如下所示的基本模型结构：

基于纯电动汽车的配送特征，通过电池容量约束、货物装载量约束、节点约束和时间约束，其中时间约束包括对客户的服务时间、车辆的充电时间以及行驶时间，构建目标函数为配送距离最小化的规划模型，即在满足顾客需求的情况下，尽可能做到能源消耗和成本的最小化。

3 总结与展望

随着纯电动汽车的大力推广使用，越来越多的企业采用纯电动汽车进行物流的配送活动。通过上述对纯电动汽车的续航里程、充电服务设施以及充电时间的分析，可以看出纯电动汽车路径问题与传统的车辆路径问题大不相同。本文研究带有时间窗的纯电动汽车路径规划问题，综合考虑节点约束、货物容量约束、时间约束以及电池容量约束，构建行驶距离最小化的车辆路径规划模型，从而减少纯电动汽车在配送过程中的迂回距离。合理的配送路径，能够有效提高客户的满意度，降低车辆在行驶过程中的配送成本，并对纯电动汽车的推广应用起到积极的作用。

近几年，电动汽车已经成为一种发展趋势，目前大多数学者研究的是静态车辆路径规划，而在实际的物流配送过程中，存在很多动态因素，如客户需求量的不确定性等，所以需要针对电动汽车自身的特点建立更加符合实际的多约束条件的数学模型，更好地应用于实际配送过程中。

[1]麻友良，严云兵.电动汽车概论[M].北京：机械工业出版社，2012.

[2]欧雯要，叶瑞克，鲍健强.电动汽车的节能减碳价值研究[J].未来与发展，2012,2(5):36-40.

[3]柳开济.纯电动物流配送车运营调度模型设计与实现[D].成都：电子科技大学（硕士学位论文），2016.

[4]刘华旭.基于电动汽车技术特征的共同配送调度优化研究[D].北京：北京交通大学（硕士学位论文），2012.

[5]Narath Bhusiri,Ali Gul Qureshi,Eiichi Taniguchi.Application of the Just-In-Time Concept in Urban Freight Transport[J].Procedia-Social and Behavioral Sciences,2014,125(3):171-185.

[6]Michael Schneider,Andreas Stenger,Dominik Goeke.The Electric Vehicle Routing Problem with Time Windows and Recharging Stations[J].Institute for Operations Research and the Management Sciences,2014,14(2):1-22.

[7]Alejandro Montoya,Christelle Guéret,Jorge E.Mendoza,et al.A modified multi-space sampling heuristic for the green vehicle routing problem[J].Transportation Research Part C Emerging Technologies,2016,70:113-128.

[8]A Afroditi,M Boile,S Theofanis,et al.Electric Vehicle Routing Problem with industry constraints:trends and insights for future research[J].Transportation Research Procedia,2014(3):452-459.

[9]邢芳芳，贾永基，蒋琪,等.带充电设施的电动班车路径规划问题研究[J].中国管理科学与工程，2016,5(4):149-156.

[10]杨裙，冯鹏祥.电动汽车物流配送系统的换电站选址与路径优化问题研究[J].中国管理科学，2015,23(9):87-96.

Analysis of Pure Electric Vehicle Path Planning Model Based on Time Window Constraint

LIU Yingxin (School of Management,Bohai University,Jinzhou 121000,China)

With the environmental pollution and the depletion of resources,the development of low-carbon economy is the inevitable way to achieve sustainable development in China.As the main source of energy consumption and greenhouse gas emissions,logistics and distribution industry has attracted much attention.Therefore,this paper uses pure electric vehicles instead of traditional vehicles for logistics and distribution.Through the analysis of the advantages and distribution characteristics of pure electric vehicles,and the classification of vehicle routing problems,the paper proposes the pure electric vehicle routing problem.Finally,considering the characteristics of cargo loading,node access and time constraints in the traditional vehicle routing problem,a pure electric vehicle path planning model with time window is constructed according to the characteristics of electric vehicle battery capacity,charging facilities and charging time.

pure electric vehicle;time window constraint;path planning;logistics distribution

U116.2

A

1002-3100（2017）12-0083-05

2017-10-21

辽宁省社科规划基金重点项目，项目编号：L16AGL002。

刘颖鑫（1993-），女，辽宁瓦房店人，渤海大学管理学院物流工程专业硕士研究生，研究方向：物流工程与管理。