基于分支定价算法的电动汽车车辆路径问题-揭婉晨.pdf

《基于分支定价算法的电动汽车车辆路径问题-揭婉晨.pdf》由会员分享，可在线阅读，更多相关《基于分支定价算法的电动汽车车辆路径问题-揭婉晨.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第25卷 第4期2016年8月运 筹 与 管 理 V0125，N。40PERATl0NS RESEARCH AND MANACEMENT SCIENCE Aug2016基于分支定价算法的电动汽车车辆路径问题揭婉晨， 杨琚， 陆坚毅(华中科技大学管理学院，湖北武汉430074)摘要：目前，随着电动汽车的普及，物流企业逐渐重视电动汽车的应用。本文考虑到电动汽车在实际应用中的行驶里程、充电耗时以及配送时间等因素，研究含时间窗的电动汽车车辆路径问题，建立了相应的混合整数规划模型，然后改进分支定价算法以求得其最优解。改进的分支定价算法首先根据Dantzigwolfe分解原理将原问题分解为基于路径的主问题

2、(MP)和求最短路径的子问题，然后用列生成和动态规划算法在主问题和子问题之间进行迭代以求得主问题线性松弛后的最优解，最后采用基于弧的分支策略求得其整数解。通过用改进的S6lomon算例的实验数据，与cPLEx比较验证了模型和算法结果的准确性，并对该问题进行了灵敏度分析，证明了本文提出的算法具有一定的应用价值。关键词：车辆路径问题；分支定价算法；列生成算法；电动汽车；电量约束中图分类号：u116。2。0221 文章标识码：A文章编号：100r7-3221【20161040093-08 doi：1012005omB20160128EIeCt rC VehiCle ROUting PrObIem B

3、aSed On A BranCh-andP rjCe AIgO rithmJIE Wan-chen，YANG Jun，LU Jian-yi(Sc危ooZ矿肘nc曙e，le乃f，日uc蔬D，谬芒，ni口e，s面y驴Sc如ncP口nd zoc矗nDZDgy，T矿M五口n 430074，C危i，五口)AbStract：At present，green logistics issues are eme唱ing as the new agenda item and gaining interest in supplychain management The妇ditional objective of d

4、istribution management has been developed into minimizing systemwide costs which consider economic and enVimnmental issues With the popularity of electric vehicles，logistics enterprises are starting to pay attention to the application of them In this paper，we study the electric vehiclerouting proble

5、m with time windows，and take the limited battery capacities and the recharging time of electricVehicles of the practical application into account，then establish the corresponding mixed integer programmingmodel FunhenIlore，We put forward a modified branchandprice algorithm for the problem，and obtain

6、the optimal solution Firstly，the algorithm decompose the original problem into a main problem(MP)based on pathand a shonest path problem with resource constraints(SPPRC)，then use column generation method and dynamicpmgramming algorithm to calculate between the linear relaxation of the main problem a

7、nd the sub problem to seekthe optimal solution iteratiVely At last，we use the branching stmtegy which is based on the arc for integer solutions of the model We use the improVed Solomon instances as the experimental data The accuracy of the modeland algorithm are validated by CPLEX， and the sensitivi

8、ty analysis of larger instances demonstrates that thepIDposed algorithm has a certain application valueKey wOrdS：Vehicle routing problem；branchandprice algorithm；column generation；electric vehicle；baneryconstI_aintsO 引言传统物流系统优化的目标中大都没有考虑社会和环境成本。电动汽车作为新一代的交通运输工具，不仅在节能减排方面具有传统汽油汽车不可比拟的优势，也减少了人们对传统石油能源

9、的依赖引。我国目前进入了电动汽车的快速发展阶收稿日期：20141013基金项目：国家自然科学基金重大项目资助(71320107001)；中央高校基本科研业务费专项资金资助(HusT：2013QNl01)；武汉市黄鹤英才(现代服务)计划资助项目作者简介：揭婉晨(199l一)，女，江西抚州人，博士研究生，研究方向：物流网络优化；杨瑭(1976)，女，湖北武汉人，博士，副教授研究方向：网络优化，供应链管理。万方数据运 筹 与 管 理 2016年第25卷段，国务院于2012年和2014年分别出台了关于印发节能与新能源汽车产业发展规划(20122020年)的通知(国发201222号)和关于加快新能源汽车

10、推广应用的指导意见(国办发201435号)，文件以2020年纯电动汽车和插电式混合动力汽车的累计销量超过500万辆为目标，并且提出了加快建设相应规模的充电设施，使其满足重点区域以及城际间电动汽车的行驶需要p4。为了减少温室气体的排放和响应国家的政策号召，车辆路径问题应该整合环境影响约束，这就使得电动汽车的车辆路径问题的研究显得尤为重要。VRP最初是由Dantzig和Ramser提出的3，Toth and Vigo【61和Lapone【_7，81也对该问题做了比较详尽的介绍，对于目前VRPTw的大致研究情况，则可以通过阅读Gendreau and Tarantilis一3，Kalle-hauge

11、【1叫的文献来加以了解。然而，电动汽车的车辆路径问题(E-VRP)与传统汽车的车辆路径问题(VRP)不同。这是因为电动汽车在行驶的过程含中有电量约束。电动汽车在电量不足的情况下需要选择它可到达的充电站充电，电动汽车的充电时间取决于它到达充电站时的电量剩余情况和设备的充电率，这使得在含有时间窗的车辆路径问题中，如何给物流企业制定一个最优的电动汽车充电和配送计划显得十分必要。Erdo g锄和Miuer-Hooksu研究了绿色车辆路径问题。考虑了替代燃料车在燃料不足的情况下需在替代燃料站补充燃料的情况，并建立了相应的车辆路径问题的模型，最后用改进的Clarke and Wrigm节约启发式算法(MC

12、ws)和基于密度的聚类算法(DBcA)对模型进行求解。但是，他们的研究中没有考虑替代燃料车补充燃料的时间成本。Comd和FigliozzPl首次提出了充电车辆路径问题的模型，通过迭代路线建设和改进的启发式算法对模型求解。他们利用了经典的CVRP数据对其做了初步的灵敏度分析，得到了直观行为对结果特征如车辆数量，总行驶里程的影响，并且发现在车辆续航里程缩短和增加充电时问的情况下，客户点的时间窗对结果的影响十分显著。Schneider和stenger等H31研究了电动汽车的车辆路径问题，建立了在配送车辆总数最少的前提下，使得配送总距离最短的混合整数规划模型，并运用变领域搜索和禁忌搜索相结合的混合启发

13、式算法求得了模型的近似解。以上文献可以看出，现有的文章都是利用启发式算法求得模型的近似解，不能保证解的质量。本文将在现有相关文献的基础上，对原有模型进行一定的改进，以最小化配送总距离为目标，建立一个包含时间窗的电动汽车车辆路径问题的混合整数规划模型，并运用基于列生成方法的分支定价算法求得其最优解。最后，通过改进的Solomon实验数据验证本文模型和算法的有效性。1 问题描述与数学模型11 问题描述假设某物流企业拥有一个配送中心和一批装载容量相同且数量足够的电动汽车，该企业利用这些电动汽车对它的各个客户点配送货物，配送任务完成之后电动汽车需要回到这个配送中心。已知各个客户的订货量，充电站的位置和

14、各节点之间的距离。此外，从配送中心出发的电动汽车的电量是满的，电动汽车一旦充电就必须充满且同一电动汽车只能经过同一个充电站最多一次。客户点的配送含有时间窗的限制，车辆到达客户点的时间必须在时间窗内。每位客户的需求均要被满足，仅配送一次。本文需要解决的问题是如何合理地规划各个电动车的配送路径，部署其充电规划，以满足客户需求及时间窗限制，并使系统总配送距离最小。12 EVRPTW的混合整数规划模型121 符号说明1)标号：0代表配送中心(起点)，n+l代表虚拟配送中心(终点)；J江1，2，I，|为客户集合；KI|I尼=1，2，II|I|为配送的电动汽车车辆集合；F表示充电站集合，R=Fu0；，：，

15、uF，玎=，u0，+l=，un+1。2)参数：d“节点i与节点之间的距离，Vi，_几!F；C：车辆最大载重；譬i：客户的需求量；Ei，t：客户i的时间窗口；s；：在客户i所需的服务时间；“车辆从i点到歹点所花费的时间；Q：电动汽车电池的最大容量；r：电动汽车电池的充电率；危：行驶每单位距离电池电量的消耗率。3)变量：r“车辆后到达点i的时间；戈“电动汽车|经过弧(i，_)时为1，否则为0；万方数据第4期 揭婉晨，等：基于分支定价算法的电动汽车车辆路径问题 956“电动汽车|在i点的剩余电量。122混合整数规划模型min z=，d严班 (1)tEIE0 JE Jn+1I产，st髫班=1，V i，

16、 (2)tEK，E J；+1I手，茗班l，V IiK，iF (3)JE；+IfJ算计=菇V_，|K (4)鬻 j身1劬石毋c，V I|K (5)JJIJ 15峋r让+(si+)石啦一Lo(1一并洳)s z雄，V i厶，_，二+，i，I|K (6)丁址+i，z种+r(Q一6诸)一(Lo+rQ)(1一z毋)s瓦，ViF，：+。，iJ，_|K (7)EistsLf，i， (8)o s6雄茎Q一九d城，V iR，C+l，i，后E K(9)0 s 6业6业一d“菇叶+Q(1一菇僻)，V i，J髟+1，i歹，蠡K (10)并诚0，1 (11)其中，目标函数(1)表示最小化物流系统总配送距离；约束(2)表示

17、每个客户_必须配送一次，并且由一辆电动汽车配送；约束(3)表示同一电动汽车只能经过同一个充电站最多一次；约束(4)表示到达和离开同一点的弧的数量必须相等；约束(5)表示电动汽车五的装载容量不能超过其最大装载容量；约束(6)表示电动汽车不充电时从i点到歹点的时间约束；约束(7)表示电动汽车充满电后到达_点的时间约束；约束(8)表示电动汽车到达客户点的时间要在时间窗之内；约束(9)表示电动汽车在充电站i充满电或从配送中心出发到达_点的电量约束；约束(10)表示电动汽车从客户i点到达-点的电量约束；约束(11)表示。一l变量约束。2模型分解Dantzig和woe于1960年根据凸规划理论对一种具有角

18、形结构的线性规划问题给出了一种分解策略，这就是著名的Dantzig_wolfe分解4|。为求得上述混合整数规划问题的最优解，本文从基本的Dantzigwo分解原理5161出发，对该模型进行分解，得到一个结构较为简单但列变量数目非常大的主问题和一个含有资源约束的最短路径子问题。21 E-VRPTW的主问题假设能得到所有满足约束条件的可行路径集力。力为从配送中心出发，经过若干客户点或充电站，最后又回到配送中心的所有可行路径集合。本文所求解的问题则转化为从力中选择若干条路径组成一个可行解并且使模型的目标函数值最小。211 符号说明力：满足模型(1)(11)的可行的路线集合。r力，r表示-f2中的第r

19、条路径；d，：路线r的总行驶里程，d，=d；口一当r经过点i时等，6，E J；+1于1，否则等于o，则有茗“=口“6驴：当r经过弧(i，J)时等于1，否则等于0；口，：当解中包含r时等于l，否则等于0。通过上面的定义，可以得到：d，=6驴d，口。=6驴l e，6 JE J；+1 E J：+1i ，212主问题模型模型(1)(11)可以转化为下面的集合覆盖模型(set Covering Model)，称它为主问题(MasterPmblem)：mind，p， (12)，Enst口。9，1，i， (13)rEnp，0，1，r力 (14)式(12)和(13)与式(1)和(2)一致，保证系统总配送距离最

20、短且每个客户点都被服务一次。由于几乎不可能枚举出主问题模型的所有可行路径，这就需要用列生成法迭代地为求解主问题的松弛问题加入有效列(路径)。22满足资源约束的最短路径问题(SPPRC)从21的主问题的松弛问题可得到其对偶模型为：max仃 (15)一 、 st。仃id，jR (16)仃i0，i， (17)设7r为对偶问题的最优解，那么主问题的对偶模型的检验数(reduced cost)则为：a，=d，一口i砬 (18)式(18)可以化为：刁，=(d口一仃；)算口 (19)6垴JEl；+1根据改进单纯型法原理，把使得检验数趸o的这一列(路径)带入到主模型中迭代，能优化当前最优解。那么子问题就转化为

21、寻找辽o的路径。万方数据运 筹 与 管 理 2016年第25卷子问题模型则是：min(d口一仃；)茗u (20)IE，6J E J；+1st约束(3)一(11) (21)由(20)一(21)可知，子问题是含有资源约束的最短路径问题(shortest Path Problem with Resource Constrained，SPPRc)，每一条最短路径都必须满足电量约束，容量约束和时间窗约束。只有当目标函数(20)的值小于零时，才能把结果作为新的列加入到主问题中进行迭代，以使主问题的目标函数值更优。其中定价操作则是根据丌。修改d得到新的花费值di，一仃i。3用分支定价法求解模型Desmsie

22、璐等3提出了分支定价算法，即把列生成方法(Column Generation)与分支定界算法相结合，对车辆路径问题求解。在其基础上，本文从包含部分列的主问题出发，用动态规划算法求得使子问题目标函数值(对偶模型的检验数)小于0的解，并把它们作为新的列带入主问题的求解过程中，在主问题和子问题之间不断迭代，为主问题的松弛问题提供更紧的上界，直到子问题的目标函数再也无法产生小于0的解，以获得主问题的线性松弛问题的最优解。最后，利用基于弧的分支策略求得最优整数解。图1给出了分支定价算法的主要流程。一“。一。堂一，i下五而丽蠡藤丽翮。，!，。一韧始化搜索树r加入帐节点，。!，一兰塑!竺!兰!皇塑!竺!堡型

23、tn丽丽函函面西两磊鬲西；砷，!一rjL1I用动态规铷算法搜素短路径(趼PRc)*r舔面画磊丙订图l EVRP的分支定价算法流程图31动态规划算法子问题SPPRC中给定一个有向图G=(I，E)，其中顶点集合y由顾客点集合，充电站集合F，起始配送中心s和虚拟配送中心t(与s表示同一个配送中心)组成，边集合E是图G中所有弧的集合。根据式(20)对子问题进行重新定价后，弧可能存在负的费用值。Handler和zang，Beasley和Christofides819 o曾通过对资源约束进行拉格朗日松弛求解最短路径问题。然而，当有向图中存在负费用时，SPPRc是一个强NP-hard问题，难以用拉格朗日松弛

24、来求解2引。Feillet等211于2004年运用动态规划算法对含负费用的SPPRC进行求解。本文将在此基础上改进动态规划算法，以求解含有容量，时间窗和电量约束的最短路径问题。311 状态量与状态的加速扩展在动态规划算法中，每访问一个节点需用一个对应的状态量表示其状态(Label)，定义其为(i，p，R，C，r，Q，D，s)，各部分的含义如下：1)i表示正在访问的节点(配送中心、顾客点、充电站)。2)p表示前一个访问的节点的状态量的索引，可以通过它得到前一个状态量。3)尺表示该路径访问i点后的剩余容量。4)C表示该路径访问i点后的总距离或费用。5)丁表示该路径访问i点后的时间。6)Q表示该路径

25、访问i点后的剩余电量。7)D表示该路径访问i点后的统治状态。8)s用来记录该路径在访问i点后的已访问节点信息集合，|s=hI_y。其中，影，=o表示节点歹未被访问；t，j=1表示该路径已访问点，无需再次访问。当前状态需根据访问记录s向其他节点遍历。新生成的状态将继承前面状态的访问记录s，并更新R、c、r、Q和s，只有当剩余容量满足车辆的负载限制，访问时间在时间窗内且剩余电量大于或等于零时，状态才被标记为可行，并继续向其他节点遍历，否则丢弃。为了加速状态的扩展，Feillet心在生成可行的新状态时，通过提前判断新状态向后面的节点扩展是否满足资源约束，来更新其访问记录s。由于电动汽车可能经过充电站

26、充电，所以加速过程中不考虑电量约束，只考虑剩余容量和时间窗约束。312统治规则节点的访问过程中，一些状态不会产生最优解，不应在下次迭代中继续扩展，需被可能产生最优解蕊兰|妻蠢|嘲二型一峭慨埔赫一磊型|l翌：皇：一万方数据第4期 揭婉晨，等：基于分支定价算法的电动汽车车辆路径问题 97的状态统治。统治规则(Dominance Rule)是用来判断这些需要被统治的状态。其主要定义如下：访问同一个节点的两个状态。和L：，若满足如下5个式子：1)1y三2y；2)L1RsL2R；3)厶CsL2C；4)1r2r；5)三，Q三2Q。则称厶。统治：，L。能扩展出优于后者所能扩展的解，将在下一次迭代中继续扩展，

27、：D标记为tnle。其中，1)表L：示已访问的节点集合包含所有已访问的节点集合。313动态规划算法的流程设u代表当前需要向后扩展的状态集合，p代表满足资源约束的可行路径对应的最后一个状态的集合，动态数组存储所有遍历的状态。动态规划算法的流程可描述为：Step 1 初始化：令U=Z，p=，=fl，其中为起始配送中心s的状态。Step 2若u勿且s洳(p)小于阈值，则从u中选出总距离最小的状态z，否则转step 7。Step 3找到状态z所代表的节点i，用统治规则对该状态z和中所有代表i的状态进行判断。Step 4若状态z被统治，则转step 6。Step 5若状态z所代表的节点i为虚拟配送中心，

28、则从这个状态向前遍历得到路径R，若R满足目标函数小于零，则把R加入到集合p中。否则，从这个节点i开始向所有未被访问的节点扩展，并把满足资源约束的状态加入集合。Step 6 从U中删除当前状态f，转Step 2。Step 7根据集合p，生成主问题所需的最短路径集合r。32列生成法根据以上所述，有效路径(列)的搜索空间是非常巨大的。为此，本文设定一个阈值，当搜索到的有效路径条数大于或等于阈值时则停止搜索。然后，将子问题求得的路径集作为新的列加入到原有路径集中，再用改进单纯形法对主问题求解，得到新的仃后对子问题重新定价，并继续寻找有效路径集，如此迭代，直至无法找到有效路径为止。这个阈值设为节点总数的

29、两倍。其主要过程如下：Step 1初始化主问题，生成主问题所需的初始路径集合R。Step 2 用单纯型法求解主问题，得到子问题模型所需的丌，进行重新定价。step 3用动态规划算法求解子问题，搜索满足条件的最短路径集合T。Step 4如果r，则将r中所有的路径加入到R中，并且在主模型中生成对应的新列，转Step 2，否则，转Step 5。Step 5用分支策略求主问题的整数解。33分支策略与整数解常用的基于变量的分支策略会使问题陷入死循环。对此，本文采用Ryan和Foster提出了基于弧的分支策略心21。首先，把基于路径的浮点数解转化为与其对应弧的浮点数值。当存在浮点数解时，可以找到两条路径r

30、，和r：满足：路径r。经过弧(i，_)访问，点，路经r2则经过弧(m，_)访问_点(im)。然后，对浮点数的弧值四舍五入取整，优先选择使弧值改变最大的那条弧。假设选择弧(f，)，那么就存在两个分支，即最优解中是否包含这条弧。当最优解中存在弧(i，)时，只需将其他所有到达_点的弧的花费和其他所有离开i点的弧的花费设为足够大的值，重新计算；反之，只需设弧(i，_)的花费为足够大的值，再重新计算。求整数解的流程与传统的分支定界算法流程大致相同，其主要求解步骤如下：Step 1初始化搜索树s，加入根节点。Step 2在搜索树5中选取一个节点，用节点的信息初始化脚模型。Step 3求解肿模型，得到解X。

31、Step 4如果x为整数解，则转step 5，否则，转Step 6。Step 5与当前的上界进行比较，如果小于上界，则更新上界值，并且根据新的上界值，对搜索树进行剪支，转Step 7。Step 6如果浮点数解小于当前的上界，则根据上述分支策略选择一条弧进行分支，删除当前节点，将分支节点加入搜索树，否则无需进行分支操作。Step 7如果搜索树s，则转step 2，否则，转St印8。Step 8当前的上界值即为最优整数解。4实验结果与分析本实验的计算机参数配置为Intel(R)Core(TM)i5-2450M CPU250GHz 250GHz。改进的分支定价算法在JAVA中的实现为单线程代码。万方

32、数据98 运 筹 与 管 理 2016年第25卷41 实例数据实验利用Schneider等川所提供的数据进行测试。这份数据是在原始Solomon算例上加入了充电站的坐标信息、电动汽车电池的最大容量、电动汽车电池的充电率和行驶每单位距离电池电量的消耗率，且在各项参数的设定上都比较合理，比如电动汽车电池的最大容量，Schneider等是根据以下两种情况的最大值设定的：1)较著名的VRPrIw实例的解的平均路径长度的60所需的电量。2)客户点与充电站之间最长的距离所需要电量的2倍。充电率r则是通过完全充电的时间来设定。一次完全充电的时间设为客户点服务时间平均值的3倍。由于电动汽车在充电站充电需要一定

33、的时间，这使得现有模型几乎不可能遵守原始solomon实例中的时间窗，Schneider等也根据了Solomon于1987年设定时间窗相似的步骤心纠设定了EVRPTW的时间窗。42实验结果与对比分析421 模型及算法的验证分析为了评估最优解的准确性，将模型(1)(11)转化为cPLEx程序，使用能被IBM ILOG CPLExl25求解的小规模实例，设置其在2个小时内如果没有得到全局最优解，则给出当前最优解，然后与分支定价算法的计算结果比较。为了保证实验的普遍性，从改进的Solomon算例中选取10组不同规模的小实例数据进行测试，测试结果整理如表1所示。通过表1可以看出两者的结果是吻合的，验证

34、了本文模型和改进的分支定价算法的正确性。表1 CPLEx和分支定价算法求解小型算例的结果对比问题规模，FcPLEx 分支定价算法m d3 165682 2362ll 179042 22827l 239132 243212 300563 369553 356222 3105521 262842165682362l1790422827239132432l3005636955372533lO55264473163l01631注：m代表所需电动汽车的数量，d代表配送总距离，代表程序运行总时间。用下划线标出的为当前最优解。422较大规模算例的结果电动汽车VRP的研究需要具有一定的实用性，并且能够促进电动

35、汽车在物流企业中的推广和使用。为了验证本文提出的分支定价算法在求解电动汽车VRP问题具有一定的应用价值，从改进的Solomon算例中选取5组不同规模的较大实例数据进行计算。实例数据规模与实验结果如表2所示。图2表示的是60ll规模算例的线路图，空心点表示顾客点，实心点表示充电站，用颜色区分不同电动汽车车的路线。表2较大规模算例结果问题规模，F基本信息和计算结果d 42893 276979952 1494987 68 6636102882 14885125399 17716601l70l】802l902l1002l683l27313207861878621104注：q代表电动汽车最大行驶里程r代

36、表充电率。辱1成p2图2 6011的算例线路图实验结果表明本文改进的分支定价算法能适应于较大规模的电动汽车车辆路径问题，并且能在不同规模数据集下和可接受的时间范围内求得最优解。虽然求解时间随着问题规模增大而增加，但一SSSS；。一“hhh钆h挑孤弘弘孙hhh|曼佩一耋薹慨32l2122332圯蝎“蝎“虾“砖拍灯啪，mmm博：2”：2刊万方数据第4期 揭婉晨，等：基于分支定价算法的电动汽车车辆路径问题 99这与数据本身和问题复杂度有一定关系，不影响本文提出算法的一般实用性。423 相关因素灵敏度分析电动汽车的充电时间由充电率的大小和其到达充电站的剩余电量决定，它会直接影响本文模型的计算结果。因此

37、，本文分析电动汽车的最大行驶里程和充电率的变化对结果的影响。为了保证实验的一般性，从改进的Solomon算例中选取5组同规模的中等实例进行测试，分别命名为A，日，c，D和E，其中顾客点数量为50，充电站数量为21，电池的最大行驶里程为6214，充电率为048。1)电池的最大行驶里程为了研究电动汽车电池的最大行驶里程对结果的影响，将其设为相对初始值逐渐增加0，25。50，75和100，即6214，7768，9321，10875和12428。实验结果如表3所示。表3 电池最大行驶里程的灵敏度分析注：n代表充电站的个数。实验结果表明：当电池的最大行驶里程逐渐增加时，所需电动汽车的数量呈减少的趋势，且

38、电动汽车经过充电站的数量和配送总距离也逐渐减少。当其最大行驶里程增加到一定程度后，车辆不需要经过充电站便可完成配送任务，问题转化为传统的带时间窗的VRP问题。电池的最大行驶里程的增加将导致一辆电动汽车可以服务更多的顾客点，那么物流企业所需的配送车辆数将可能相应地减少，物流企业配送距离也将逐渐变短，但由于顾客点时间窗的限制可能导致多个顾客点之间不能被同一辆电动汽车访问，配送车辆将减少到一定值后保持不变，电动汽车有可能不需要经过充电站。2)充电率为了研究电动汽车的充电率对计算结果的影响，将充电率设为相对初始值逐渐增加0，100，200，300和400，即048，096，144，192和24。实验结

39、果如表4中所示。表4充电率的灵敏度分析从表4中，可以看出随着充电率的递增，该物流企业所需的配送车辆总数和配送总距离呈减少的趋势，而电动汽车经过充电站的数量是波动的。由于充电率会影响电动汽车的充电时间，且充电时间的长短与电动汽车能否在规定的时间窗内到达相应的顾客点直接相关，充电时间的减少有可能会使一辆电动汽车对更多的顾客点进行配送，所以物流企业所需的配送车辆数和配送总距离将可能相应地减少。与最大行驶里程不同，充电率是通过改变充电时间来间接地影响电动汽车的行驶路线，因此电动汽车经过充电站的数量是浮动的。实例C中实验的结果保持不变，是因为充电率的增加已不能使一辆电动汽车配送更多的顾客点，但可以通过增

40、加最大行驶里程离来优化结果。从上面实验可以看出，在电动汽车发展的初期，特别是在充电站数量有限，考虑充电站建设成本的情况下，增加电动汽车的行驶里程较增大电池的充电率更能节省系统配送的总成本。5 结束语本文研究了在充电站位置已知的情况下，含有时间窗的电动汽车车辆路径问题，并建立了其相应的混合整数规划模型，设计了适合电动汽车的基于万方数据运 筹 与 管 理 2016年第25卷列生成的分支定价算法。然后，在cPLEx上运行了一系列的小型算例，验证了本文模型与算法的正确性。最后，通过改进的S010mon算例证明了本文的分支定价算法能有效地减小问题规模，求得较大规模的电动汽车车辆路径问题的最优解，并对电动

41、汽车的最大行驶里程和充电率做了灵敏度分析，发现若考虑充电站的建站成本，增加电动汽车的行驶里程较提高电池的充电率更能节省系统配送的总成本。下一步的研究将从两方面出发：一方面，改进子问题的动态规划搜索策略，以提高其求解速度；另一方面，改进本文的模型，研究含有多配送点和最大行驶里程不同的多类型电动汽车的车辆路径问题。参考文献：1中国气候变化信息网全球交通工具碳排放增幅惊人2008-01-16Available fmm：hnp：wwwccchinagovcncIlNewsInf0asp?NewsId=105032chella8w肌y c，Ramesh R，Rau c Y VA super、，isory

42、contIDl of a fuel free electric vehicle for green environmentc In：Proceedings of Intemational conference，Emerging Trends in Electrical Engineering and EnergyManagement(ICETEEEM)，IEEE20123中华人民共和国国务院国务院关于印发节能与新能源汽车产业发展规划(20122020年)的通知z20124中华人民共和国国务院关于加快新能源汽车推广应用的指导意见z20145 Dantzig G B，Ramser J HThe t

43、nlck dispatching problemJManagement science，1959，6(1)：80-916Toth P，Vigo DThe vehicle muting problemMSiam20017 L印one G The vehicle muting problem：an ovenriew ofexact and印pmximate algorithmsJ Eumpean Joumalof Opemtional Research，1992，59(3)：3453588 Lapone G what you should know about the vehicle routin

44、g P阳blemJ Naval Research Logistics(NRL)，2007，54(8)：811-8199Gend陀au M，Tamntilis c Ds01ving large-scale Vehiclemuting problems with time windows：the state-oft|le-arcMcIRRELT，201010Kallehauge BFo珊ulations and exact algorithms for thevehicle muting pmblem with time windowsJcomputersOpemtions Research，20

45、08，35(7)：2307233011Erdo gan s，MillerHooks EA green vehicle routingproblemJ Tmnsponation Research Part E：Logisticsand Transportation Review，2012，48(1)：100-1 1412Conmd R G，Figliozzi M AThe recharging vehicle muting problemc In：Proceedings Industrial Engineer-ing Research Conf毫rence，Reno：20l 113schneid

46、er M，stenger A，Goeke DThe electric vehiclerouting problem witlI time windows and舱ch盯gingstationsJTransportation science，2014，48(4)：500-52014 Dantzig G B，wolfe P Decomposition pri且ciple forlinear pmgmmsJ0perations I它search，1960，8(1)：10111115 Lnbbecke M E，Desmsiers JSelected topics in columngeneration

47、J0perations Research，2005，53(6)：1007102316 Desaulniers G，Desrosiers J，solomon M M columngenerationMspringer，200517 Desmsiers J，Soumis F，Desmchers M Routing withtime windows by column genemtionJ Nenvorks，1984，14(4)：545-56518Handler G Y，zang IA dual algorithm for the constI谊ined shortest path pmblemJNetworks，1 980，10(4)：293-30919Beasley J，christ06des NAn algorithm for the resourceconstmined short