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

《基于分支定价算法的电动汽车车辆路径问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、anCh-and—PrjCeAIgOrithmJIEWan-chen，YANGJun，LUJian-yi(Sc危ooZ矿肘Ⅱnc曙e，，le乃f，日uc‘蔬D，谬芒，ni口e，s面y驴Sc如ncP口ndzoc矗nDZDgy，T矿M五口n430074，C危i，五口)AbStract：Atpresent，greenlogisticsissuesareeme唱ingasthenewagendaitemandgaininginterestinsupplychainmanagement．The妇ditionalobjectiveofdistributionmanagementhasbeendevelop

4、edintominimizingsys—tem·widecostswhichconsidereconomicandenVimnmentalissues．Withthepopularityofelectricvehicles，logis—ticsenterprisesarestartingtopayattentiontotheapplicationofthem．Inthispaper，westudytheelectricvehicleroutingproblemwithtimewindows，andtakethelimitedbatterycapacitiesandtherechargingti

5、meofelectricVehiclesofthepracticalapplicationintoaccount，thenestablishthecorrespondingmixedintegerprogrammingmodel．FunhenIlore，Weputforwardamodifiedbranch—and·pricealgorithmfortheproblem，andobtaintheop—timalsolution．Firstly，thealgorithmdecomposetheoriginalproblemintoamainproblem(MP)basedonpathandash

6、onestpathproblemwithresourceconstraints(SPPRC)，thenusecolumngenerationmethodanddynamicpmgrammingalgorithmtocalculatebetweenthelinearrelaxationofthemainproblemandthesubproblemtoseektheoptimalsolutioniteratiVely．Atlast，weusethebranchingstmtegywhichisbasedonthearcforintegersolu—tionsofthemodel．Weusethe

7、improVedSolomoninstancesastheexperimentaldata．TheaccuracyofthemodelandalgorithmarevalidatedbyCPLEX，andthesensitivityanalysisoflargerinstancesdemonstratesthatthepIDposedalgorithmhasacertainapplicationv