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

第2 5 卷第4 期 2 0 1 6 年8 月 运筹与管理 V 0 1 2 5 ，N 。4 0 P E R A T l 0 N SR E S E A R C HA N DM A N A C E M E N TS C I E N C EA u g 2 0 1 6 基于分支定价算法的电动汽车车辆路径问题 揭婉晨，杨琚，陆坚毅 ( 华中科技大学管理学院，湖北武汉4 3 0 0 7 4 ) 摘要：目前，随着电动汽车的普及，物流企业逐渐重视电动汽车的应用。本文考虑到电动汽车在实际应用中的 行驶里程、充电耗时以及配送时间等因素，研究含时间窗的电动汽车车辆路径问题，建立了相应的混合整数规划 模型，然后改进分支定价算法以求得其最优解。改进的分支定价算法首先根据D a n t z i g w o l f e 分解原理将原问题 分解为基于路径的主问题( M P ) 和求最短路径的子问题，然后用列生成和动态规划算法在主问题和子问题之间 进行迭代以求得主问题线性松弛后的最优解，最后采用基于弧的分支策略求得其整数解。通过用改进的S 6 l o m o n 算例的实验数据，与c P L E x 比较验证了模型和算法结果的准确性，并对该问题进行了灵敏度分析，证明了 本文提出的算法具有一定的应用价值。 关键词：车辆路径问题；分支定价算法；列生成算法；电动汽车；电量约束 中图分类号：u 1 1 6 。2 。0 2 2 1文章标识码：A 文章编号：1 0 0 r 7 - 3 2 2 1 【2 0 1 6 1 0 4 0 0 9 3 - 0 8 d o i ：1 0 1 2 0 0 5 o m B 2 0 1 6 0 1 2 8 E I e C tr CV e h i C l eR O U t i n gP r O b I e mB a S e dO nAB r a n C h - a n d Pr j C eA I g Or i t h m J I EW a n - c h e n ，Y A N GJ u n ，L UJ i a n - y i ( S c 危o o Z 矿肘n c 曙e ，l e 乃f ，日u c 蔬D ，谬芒，n i 口e ，s 面y 驴S c 如n c P 口n dz o c 矗n D Z D g y ，T 矿M 五口n4 3 0 0 7 4 ，C 危i ，五口) A b S t r a c t ：A tp r e s e n t ，g r e e nl o g i s t i c si s s u e sa r ee m e 唱i n ga st h en e wa g e n d ai t e ma n dg a i n i n gi n t e r e s ti ns u p p l y c h a i nm a n a g e m e n t T h e 妇d i t i o n a lo b j e c t i v eo fd i s t r i b u t i o nm a n a g e m e n th a sb e e nd e v e l o p e di n t om i n i m i z i n gs y s t e m w i d ec o s t sw h i c hc o n s i d e re c o n o m i ca n de n V i m n m e n t a li s s u e s W i t ht h ep o p u l a r i t yo fe l e c t r i cv e h i c l e s ，l o g i s t i c se n t e r p r i s e sa r es t a r t i n gt op a ya t t e n t i o nt ot h ea p p l i c a t i o no ft h e m I n t h i sp a p e r ，w es t u d yt h ee l e c t r i cv e h i c l e r o u t i n gp r o b l e mw i t ht i m ew i n d o w s ，a n dt a k et h el i m i t e db a t t e r yc a p a c i t i e sa n dt h er e c h a r g i n gt i m eo fe l e c t r i c V e h i c l e so ft h ep r a c t i c a la p p l i c a t i o ni n t oa c c o u n t ，t h e ne s t a b l i s ht h ec o r r e s p o n d i n gm i x e di n t e g e rp r o g r a m m i n g m o d e l F u n h e n I l o r e ，W ep u tf o r w a r dam o d i f i e db r a n c h a n d p r i c ea l g o r i t h mf o rt h ep r o b l e m ，a n do b t a i nt h eo p t i m a ls o l u t i o n F i r s t l y ，t h ea l g o r i t h md e c o m p o s et h eo r i g i n a lp r o b l e mi n t oam a i np r o b l e m ( M P ) b a s e do np a t h a n das h o n e s tp a t hp r o b l e mw i t hr e s o u r c ec o n s t r a i n t s ( S P P R C ) ，t h e nu s ec o l u m ng e n e r a t i o nm e t h o da n dd y n a m i c p m g r a m m i n ga l g o r i t h mt oc a l c u l a t eb e t w e e nt h el i n e a rr e l a x a t i o no ft h em a i np r o b l e ma n dt h es u bp r o b l e mt os e e k t h eo p t i m a ls o l u t i o ni t e r a t i V e l y A tl a s t ，w eu s et h eb r a n c h i n gs t m t e g yw h i c hi sb a s e do nt h ea r cf o ri n t e g e rs o l u t i o n so ft h em o d e l W eu s et h ei m p r o V e dS o l o m o ni n s t a n c e sa st h ee x p e r i m e n t a ld a t a T h ea c c u r a c yo ft h em o d e l a n da l g o r i t h ma r ev a l i d a t e db yC P L E X ， a n dt h es e n s i t i v i t y a n a l y s i so fl a r g e ri n s t a n c e sd e m o n s t r a t e st h a tt h e p I D p o s e da l g o r i t h mh a sac e r t a i na p p l i c a t i o nv a l u e K e yw O r d S ：V e h i c l er o u t i n gp r o b l e m ；b r a n c h a n d p r i c ea l g o r i t h m ；c o l u m ng e n e r a t i o n ；e l e c t r i cv e h i c l e ；b a n e r y c o n s t I _ a i n t s O 引言 传统物流系统优化的目标中大都没有考虑社 会和环境成本。电动汽车作为新一代的交通运 输工具，不仅在节能减排方面具有传统汽油汽车不 可比拟的优势，也减少了人们对传统石油能源的依 赖引。我国目前进入了电动汽车的快速发展阶 收稿日期：2 0 1 4 1 0 1 3 基金项目：国家自然科学基金重大项目资助( 7 1 3 2 0 1 0 7 0 0 1 ) ；中央高校基本科研业务费专项资金资助( H u s T ：2 0 1 3 Q N l 0 1 ) ；武汉市黄 鹤英才( 现代服务) 计划资助项目 作者简介：揭婉晨( 1 9 9 l 一) ，女，江西抚州人，博士研究生，研究方向：物流网络优化；杨瑭( 1 9 7 6 ) ，女，湖北武汉人，博士，副教授研究方 向：网络优化，供应链管理。 万方数据 运 筹 与 管 理2 0 1 6 年第2 5 卷 段，国务院于2 0 1 2 年和2 0 1 4 年分别出台了关于 印发节能与新能源汽车产业发展规划( 2 0 1 2 2 0 2 0 年) 的通知( 国发 2 0 1 2 2 2 号) 和关于加快新能 源汽车推广应用的指导意见( 国办发 2 0 1 4 3 5 号) ，文件以2 0 2 0 年纯电动汽车和插电式混合动力 汽车的累计销量超过5 0 0 万辆为目标，并且提出了 加快建设相应规模的充电设施，使其满足重点区域 以及城际间电动汽车的行驶需要p 4 。为了减少 温室气体的排放和响应国家的政策号召，车辆路径 问题应该整合环境影响约束，这就使得电动汽车的 车辆路径问题的研究显得尤为重要。 V R P 最初是由D a n t z i g 和R a m s e r 提出的3 ， T o t ha n dV i g o 【6 1 和L a p o n e 【_ 7 ，8 1 也对该问题做了比较 详尽的介绍，对于目前V R P T w 的大致研究情况， 则可以通过阅读G e n d r e a ua n dT a r a n t i l i s 一3 ，K a l l e - h a u g e 【1 叫的文献来加以了解。然而，电动汽车的车 辆路径问题( E - V R P ) 与传统汽车的车辆路径问题 ( V R P ) 不同。这是因为电动汽车在行驶的过程含 中有电量约束。电动汽车在电量不足的情况下需 要选择它可到达的充电站充电，电动汽车的充电时 间取决于它到达充电站时的电量剩余情况和设备 的充电率，这使得在含有时间窗的车辆路径问题 中，如何给物流企业制定一个最优的电动汽车充电 和配送计划显得十分必要。 E r d og 锄和M i u e r - H o o k s u 研究了绿色车辆路径 问题。考虑了替代燃料车在燃料不足的情况下需在 替代燃料站补充燃料的情况，并建立了相应的车辆路 径问题的模型，最后用改进的C l a r k ea n dW r i g m 节约 启发式算法( M C w s ) 和基于密度的聚类算法( D B c A ) 对模型进行求解。但是，他们的研究中没有考虑替代 燃料车补充燃料的时间成本。C o m d 和F i g l i o z z P l 首次提出了充电车辆路径问题的模型，通过迭代路线 建设和改进的启发式算法对模型求解。他们利用了 经典的C V R P 数据对其做了初步的灵敏度分析，得到 了直观行为对结果特征如车辆数量，总行驶里程的影 响，并且发现在车辆续航里程缩短和增加充电时问的 情况下，客户点的时间窗对结果的影响十分显著。 S c h n e i d e r 和s t e n g e r 等H 3 1 研究了电动汽车的车辆路 径问题，建立了在配送车辆总数最少的前提下，使得 配送总距离最短的混合整数规划模型，并运用变领域 搜索和禁忌搜索相结合的混合启发式算法求得了模 型的近似解。 以上文献可以看出，现有的文章都是利用启发 式算法求得模型的近似解，不能保证解的质量。本 文将在现有相关文献的基础上，对原有模型进行一 定的改进，以最小化配送总距离为目标，建立一个 包含时间窗的电动汽车车辆路径问题的混合整数 规划模型，并运用基于列生成方法的分支定价算法 求得其最优解。最后，通过改进的S o l o m o n 实验数 据验证本文模型和算法的有效性。 1 问题描述与数学模型 1 1 问题描述 假设某物流企业拥有一个配送中心和一批装载 容量相同且数量足够的电动汽车，该企业利用这些 电动汽车对它的各个客户点配送货物，配送任务完 成之后电动汽车需要回到这个配送中心。已知各个 客户的订货量，充电站的位置和各节点之间的距离。 此外，从配送中心出发的电动汽车的电量是满的，电 动汽车一旦充电就必须充满且同一电动汽车只能经 过同一个充电站最多一次。客户点的配送含有时间 窗的限制，车辆到达客户点的时间必须在时间窗内。 每位客户的需求均要被满足，仅配送一次。 本文需要解决的问题是如何合理地规划各个 电动车的配送路径，部署其充电规划，以满足客户 需求及时间窗限制，并使系统总配送距离最小。 1 2E V R P T W 的混合整数规划模型 1 2 1 符号说明 1 ) 标号： 0 代表配送中心( 起点) ，n + l 代表虚拟配送 中心( 终点) ； J 江1 ，2 ，I ，| 为客户集合； K I | I 尼= 1 ，2 ，I I | I | 为配送的电动汽车车辆 集合； F 表示充电站集合，R = F u 0 ； ，：，u F ，玎= ，u 0 ，+ l = ，u n + 1 。 2 ) 参数： d “节点i 与节点之间的距离，V i ，_ 几! F ； C ：车辆最大载重； 譬i ：客户的需求量； E i ，t ：客户i 的时间窗口； s ；：在客户i 所需的服务时间； “车辆从i 点到歹点所花费的时间； Q ：电动汽车电池的最大容量； r ：电动汽车电池的充电率； 危：行驶每单位距离电池电量的消耗率。 3 ) 变量： r “车辆后到达点i 的时间； 戈“电动汽车| | 经过弧( i ，_ ) 时为1 ，否则为0 ； 万方数据 第4 期揭婉晨，等：基于分支定价算法的电动汽车车辆路径问题 9 5 6 “电动汽车| | 在i 点的剩余电量。 1 2 2 混合整数规划模型 m i nz = ，d 严班( 1 ) t E I E 0J EJ n + 1 I 产， s t 髫班= 1 ，Vi ， ( 2 ) t E K ，EJ ；+ 1 I 手， 茗班l ，VI i K ，i F ( 3 ) J E ；+ I f J 算计= 菇V _ ，| | K ( 4 ) 鬻j 身1 劬石毋c ，V I | K ( 5 ) J J I J 1 5 峋 r 让+ ( s i + ) 石啦一L o ( 1 一并洳) sz 雄，Vi 厶，_ ， ，二+ ，i ，I | K ( 6 ) 丁址+ i ，z 种+ r ( Q 一6 诸) 一( L o + r Q ) ( 1 一z 毋) s 瓦，V i F ，：+ 。，i J ，_ | K ( 7 ) E i s t s L f ，i ， ( 8 ) os 6 雄茎Q 一九d 城，Vi R ，C + l ，i ，后EK ( 9 ) 0s6 业6 业一 d “菇叶+ Q ( 1 一菇僻) ，Vi ， J 髟+ 1 ，i 歹，蠡K( 1 0 ) 并诚 0 ，1 ( 1 1 ) 其中，目标函数( 1 ) 表示最小化物流系统总配送距 离；约束( 2 ) 表示每个客户_ 必须配送一次，并且由 一辆电动汽车配送；约束( 3 ) 表示同一电动汽车只 能经过同一个充电站最多一次；约束( 4 ) 表示到达 和离开同一点的弧的数量必须相等；约束( 5 ) 表示 电动汽车五的装载容量不能超过其最大装载容量； 约束( 6 ) 表示电动汽车不充电时从i 点到歹点的时 间约束；约束( 7 ) 表示电动汽车充满电后到达_ 点 的时间约束；约束( 8 ) 表示电动汽车到达客户点的 时间要在时间窗之内；约束( 9 ) 表示电动汽车在充 电站i 充满电或从配送中心出发到达_ 点的电量约 束；约束( 1 0 ) 表示电动汽车从客户i 点到达- 点的 电量约束；约束( 1 1 ) 表示。一l 变量约束。 2 模型分解 D a n t z i g 和w o e 于1 9 6 0 年根据凸规划理论对 一种具有角形结构的线性规划问题给出了一种分解 策略，这就是著名的D a n t z i g _ w o l f e 分解4 | 。为求得 上述混合整数规划问题的最优解，本文从基本的 D a n t z i g w o 分解原理5 1 6 1 出发，对该模型进行分 解，得到一个结构较为简单但列变量数目非常大的 主问题和一个含有资源约束的最短路径子问题。 2 1E - V R P T W 的主问题 假设能得到所有满足约束条件的可行路径集 力。力为从配送中心出发，经过若干客户点或充电 站，最后又回到配送中心的所有可行路径集合。本 文所求解的问题则转化为从力中选择若干条路径 组成一个可行解并且使模型的目标函数值最小。 2 1 1 符号说明 力：满足模型( 1 ) ( 1 1 ) 的可行的路线集合。 r 力，r 表示- f 2 中的第r 条路径；d ，：路线r 的总行 驶里程，d ，= d ；口一当r 经过点i 时等 ，6 ，EJ ；+ 1 于1 ，否则等于o ，则有茗“= 口“6 驴： 当r 经过弧( i ，J ) 时等于1 ，否则等于0 ；口，：当解中 包含r 时等于l ，否则等于0 。 通过上面的定义，可以得到： d ，= 6 驴d ，口。= 6 驴 le ，6J EJ ；+ 1 EJ ：+ 1 i ， 2 1 2 主问题模型 模型( 1 ) ( 1 1 ) 可以转化为下面的集合覆盖 模型( s e tC o v e r i n gM o d e l ) ，称它为主问题( M a s t e r P m b l e m ) ： m i n d ，p ， ( 1 2 ) ，E n s t 口。9 ，1 ，i ， ( 1 3 ) r E n p ， 0 ，1 ，r 力( 1 4 ) 式( 1 2 ) 和( 1 3 ) 与式( 1 ) 和( 2 ) 一致，保证系统 总配送距离最短且每个客户点都被服务一次。由 于几乎不可能枚举出主问题模型的所有可行路径， 这就需要用列生成法迭代地为求解主问题的松弛 问题加入有效列( 路径) 。 2 2 满足资源约束的最短路径问题( S P P R C ) 从2 1 的主问题的松弛问题可得到其对偶模型为： m a x 仃 ( 1 5 ) 一 、 s t 。仃i d ，j R ( 1 6 ) 仃i 0 ，i ，( 1 7 ) 设7 r 为对偶问题的最优解，那么主问题的对偶模 型的检验数( r e d u c e dc o s t ) 则为： a ，= d ，一口i 砬 ( 1 8 ) 式( 1 8 ) 可以化为： 刁，= ( d 口一仃；) 算口 ( 1 9 ) 6 垴J E l ；+ 1 根据改进单纯型法原理，把使得检验数趸 o 的 这一列( 路径) 带入到主模型中迭代，能优化当前最优 解。那么子问题就转化为寻找辽 o 的路径。 万方数据 运 筹 与 管 理 2 0 1 6 年第2 5 卷 子问题模型则是： m i n ( d 口一仃；) 茗u ( 2 0 ) I E ，6 JEJ ；+ 1 s t 约束( 3 ) 一( 1 1 )( 2 1 ) 由( 2 0 ) 一( 2 1 ) 可知，子问题是含有资源约束 的最短路径问题( s h o r t e s tP a t hP r o b l e mw i t hR e s o u r c eC o n s t r a i n e d ，S P P R c ) ，每一条最短路径都必 须满足电量约束，容量约束和时间窗约束。只有当 目标函数( 2 0 ) 的值小于零时，才能把结果作为新 的列加入到主问题中进行迭代，以使主问题的目标 函数值更优。其中定价操作则是根据丌。修改d 得到新的花费值d i ，一仃i 。 3 用分支定价法求解模型 D e s m s i e 璐等3 提出了分支定价算法，即把列 生成方法( C o l u m nG e n e r a t i o n ) 与分支定界算法相结 合，对车辆路径问题求解。在其基础上，本文从包含 部分列的主问题出发，用动态规划算法求得使子问 题目标函数值( 对偶模型的检验数) 小于0 的解，并 把它们作为新的列带入主问题的求解过程中，在主 问题和子问题之间不断迭代，为主问题的松弛问题 提供更紧的上界，直到子问题的目标函数再也无法 产生小于0 的解，以获得主问题的线性松弛问题的 最优解。最后，利用基于弧的分支策略求得最优整 数解。图1 给出了分支定价算法的主要流程。 一“。一 。堂一，i 下五而丽蠡藤丽翮 。，! ! ，。一 韧始化搜索树r 加入帐节点 ，。!，一 兰塑! 竺! 兰! ! 皇塑! ! 竺! 堡型 t n 丽丽函函面西两磊鬲西；砷 ，!一 r j L 1 I 用动态规铷算法搜素短路径( 趼P R c ) * r 舔面画磊丙订 图lE V R P 的分支定价算法流程图 3 1 动态规划算法 子问题S P P R C 中给定一个有向图G = ( I ，E ) ， 其中顶点集合y 由顾客点集合，充电站集合F ，起 始配送中心s 和虚拟配送中心t ( 与s 表示同一个 配送中心) 组成，边集合E 是图G 中所有弧的集 合。根据式( 2 0 ) 对子问题进行重新定价后，弧可 能存在负的费用值。H a n d l e r 和z a n g ，B e a s l e y 和 C h r i s t o f i d e s 8 1 9o 曾通过对资源约束进行拉格朗日 松弛求解最短路径问题。然而，当有向图中存在负 费用时，S P P R c 是一个强N P - h a r d 问题，难以用拉 格朗日松弛来求解2 引。F e i l l e t 等2 1 1 于2 0 0 4 年运 用动态规划算法对含负费用的S P P R C 进行求解。 本文将在此基础上改进动态规划算法，以求解含有 容量，时间窗和电量约束的最短路径问题。 3 1 1 状态量与状态的加速扩展 在动态规划算法中，每访问一个节点需用一个 对应的状态量表示其状态( L a b e l ) ，定义其为( i ，p ， R ，C ，r ，Q ，D ，s ) ，各部分的含义如下： 1 ) i 表示正在访问的节点( 配送中心、顾客点、 充电站) 。 2 ) p 表示前一个访问的节点的状态量的索引， 可以通过它得到前一个状态量。 3 ) 尺表示该路径访问i 点后的剩余容量。 4 ) C 表示该路径访问i 点后的总距离或费用。 5 ) 丁表示该路径访问i 点后的时间。 6 ) Q 表示该路径访问i 点后的剩余电量。 7 ) D 表示该路径访问i 点后的统治状态。 8 ) s 用来记录该路径在访问i 点后的已访问 节点信息集合，| s = h I _ y 。其中，影，= o 表示节 点歹未被访问；t ，j = 1 表示该路径已访问点，无需 再次访问。 当前状态需根据访问记录s 向其他节点遍历。 新生成的状态将继承前面状态的访问记录s ，并更 新R 、c 、r 、Q 和s ，只有当剩余容量满足车辆的负 载限制，访问时间在时间窗内且剩余电量大于或等 于零时，状态才被标记为可行，并继续向其他节点 遍历，否则丢弃。 为了加速状态的扩展，F e i l l e t 心在生成可行的 新状态时，通过提前判断新状态向后面的节点扩展 是否满足资源约束，来更新其访问记录s 。由于电 动汽车可能经过充电站充电，所以加速过程中不考 虑电量约束，只考虑剩余容量和时间窗约束。 3 1 2 统治规则 节点的访问过程中，一些状态不会产生最优解， 不应在下次迭代中继续扩展，需被可能产生最优解 蕊兰| 妻蠢|嘲二型 一峭慨 埔赫一 磊型| | l 翌 ：皇：一 万方数据 第4 期 揭婉晨，等：基于分支定价算法的电动汽车车辆路径问题 9 7 的状态统治。统治规则( D o m i n a n c eR u l e ) 是用来判 断这些需要被统治的状态。其主要定义如下： 访问同一个节点的两个状态。和L ：，若满足 如下5 个式子： 1 ) 1 y 三2 y ； 2 ) L 1 R s L 2 R ； 3 ) 厶C s L 2 C ； 4 ) 1 r 2 r ； 5 ) 三，Q 三2 Q 。 则称厶。统治：，L 。能扩展出优于后者所能扩 展的解，将在下一次迭代中继续扩展，：D 标记 为t n l e 。其中，1 ) 表L ：示已访问的节点集合包含 所有已访问的节点集合。 3 1 3 动态规划算法的流程 设u 代表当前需要向后扩展的状态集合，p 代 表满足资源约束的可行路径对应的最后一个状态 的集合，动态数组存储所有遍历的状态。 动态规划算法的流程可描述为： S t e p1初始化：令U = Z ， ，p = ，= f l ，其中为起始配送中心s 的状态。 S t e p2 若u 勿且s 洳( p ) 小于阈值，则从u 中选出总距离最小的状态z ，否则转s t e p7 。 S t e p3 找到状态z 所代表的节点i ，用统治规 则对该状态z 和中所有代表i 的状态进行判断。 S t e p4 若状态z 被统治，则转s t e p6 。 S t e p5 若状态z 所代表的节点i 为虚拟配送 中心，则从这个状态向前遍历得到路径R ，若R 满 足目标函数小于零，则把R 加入到集合p 中。否 则，从这个节点i 开始向所有未被访问的节点扩 展，并把满足资源约束的状态加入集合。 S t e p6从U 中删除当前状态f ，转S t e p2 。 S t e p7 根据集合p ，生成主问题所需的最短 路径集合r 。 3 2 列生成法 根据以上所述，有效路径( 列) 的搜索空间是 非常巨大的。为此，本文设定一个阈值，当搜索到 的有效路径条数大于或等于阈值时则停止搜索。 然后，将子问题求得的路径集作为新的列加入到原 有路径集中，再用改进单纯形法对主问题求解，得 到新的仃后对子问题重新定价，并继续寻找有效 路径集，如此迭代，直至无法找到有效路径为止。 这个阈值设为节点总数的两倍。其主要过程如下： S t e p1 初始化主问题，生成主问题所需的初 始路径集合R 。 S t e p2用单纯型法求解主问题，得到子问题 模型所需的丌，进行重新定价。 s t e p3 用动态规划算法求解子问题，搜索满 足条件的最短路径集合T 。 S t e p4 如果r ，则将r 中所有的路径加 入到R 中，并且在主模型中生成对应的新列，转 S t e p2 ，否则，转S t e p5 。 S t e p5 用分支策略求主问题的整数解。 3 3 分支策略与整数解 常用的基于变量的分支策略会使问题陷入死 循环。对此，本文采用R y a n 和F o s t e r 提出了基于 弧的分支策略心2 1 。首先，把基于路径的浮点数解 转化为与其对应弧的浮点数值。当存在浮点数解 时，可以找到两条路径r ，和r ：满足：路径r 。经过 弧( i ，_ ) 访问，点，路经r 2 则经过弧( m ，_ ) 访问_ 点 ( i m ) 。然后，对浮点数的弧值四舍五入取整，优 先选择使弧值改变最大的那条弧。假设选择弧 ( f ，) ，那么就存在两个分支，即最优解中是否包含 这条弧。当最优解中存在弧( i ，) 时，只需将其他 所有到达_ 点的弧的花费和其他所有离开i 点的弧 的花费设为足够大的值，重新计算；反之，只需设弧 ( i ，_ ) 的花费为足够大的值，再重新计算。 求整数解的流程与传统的分支定界算法流程 大致相同，其主要求解步骤如下： S t e p1 初始化搜索树s ，加入根节点。 S t e p2 在搜索树5 中选取一个节点，用节 点的信息初始化脚模型。 S t e p3 求解肿模型，得到解X 。 S t e p4 如果x 为整数解，则转s t e p5 ，否则， 转S t e p6 。 S t e p5 与当前的上界进行比较，如果小于上 界，则更新上界值，并且根据新的上界值，对搜索树 进行剪支，转S t e p7 。 S t e p6 如果浮点数解小于当前的上界，则根据 上述分支策略选择一条弧进行分支，删除当前节点， 将分支节点加入搜索树，否则无需进行分支操作。 S t e p7 如果搜索树s ，则转s t e p2 ，否则， 转S t 印8 。 S t e p8 当前的上界值即为最优整数解。 4 实验结果与分析 本实验的计算机参数配置为I n t e l ( R ) C o r e ( T M ) i 5 - 2 4 5 0 MC P U 2 5 0 G H z2 5 0 G H z 。改进的 分支定价算法在J A V A 中的实现为单线程代码。 万方数据 9 8 运 筹与管 理 2 0 1 6 年第2 5 卷 4 1 实例数据 实验利用S c h n e i d e r 等川所提供的数据进行 测试。这份数据是在原始S o l o m o n 算例上加入了 充电站的坐标信息、电动汽车电池的最大容量、电 动汽车电池的充电率和行驶每单位距离电池电量 的消耗率，且在各项参数的设定上都比较合理，比 如电动汽车电池的最大容量，S c h n e i d e r 等是根据 以下两种情况的最大值设定的： 1 ) 较著名的V R P r I w 实例的解的平均路径长 度的6 0 所需的电量。 2 ) 客户点与充电站之间最长的距离所需要电 量的2 倍。 充电率r 则是通过完全充电的时间来设定。 一次完全充电的时间设为客户点服务时间平均值 的3 倍。由于电动汽车在充电站充电需要一定的 时间，这使得现有模型几乎不可能遵守原始s o l o m o n 实例中的时间窗，S c h n e i d e r 等也根据了S o l o m o n 于1 9 8 7 年设定时间窗相似的步骤心纠设定了 E V R P T W 的时间窗。 4 2 实验结果与对比分析 4 2 1 模型及算法的验证分析 为了评估最优解的准确性，将模型( 1 ) ( 1 1 ) 转化为c P L E x 程序，使用能被I B MI L O GC P L E x l 2 5 求解的小规模实例，设置其在2 个小时内如果没 有得到全局最优解，则给出当前最优解，然后与分支 定价算法的计算结果比较。为了保证实验的普遍 性，从改进的S o l o m o n 算例中选取1 0 组不同规模的 小实例数据进行测试，测试结果整理如表1 所示。 通过表1 可以看出两者的结果是吻合的，验证了本 文模型和改进的分支定价算法的正确性。 表1C P L E x 和分支定价算法求解小型算例的结果对比 问题规模 ，F c P L E x 分支定价算法 md 31 6 5 6 8 22 3 6 2 l l1 7 9 0 4 22 2 8 2 7 l2 3 9 1 3 22 4 3 2 1 23 0 0 5 6 33 6 9 5 5 33 5 6 2 2 23 1 0 5 5 2 12 6 2 8 4 2 1 6 5 6 8 2 3 6 2 l 1 7 9 0 4 2 2 8 2 7 2 3 9 1 3 2 4 3 2 l 3 0 0 5 6 3 6 9 5 5 3 7 2 5 3 3 l O 5 5 2 6 4 4 7 3 1 6 3 l 0 1 6 3 1 注：m 代表所需电动汽车的数量，d 代表配送总距离，代表程序运行总时间。用下划线标出的为当前最优解。 4 2 2 较大规模算例的结果 电动汽车V R P 的研究需要具有一定的实用 性，并且能够促进电动汽车在物流企业中的推广和 使用。为了验证本文提出的分支定价算法在求解 电动汽车V R P 问题具有一定的应用价值，从改进 的S o l o m o n 算例中选取5 组不同规模的较大实例 数据进行计算。实例数据规模与实验结果如表2 所示。图2 表示的是6 0 l l 规模算例的线路图， 空心点表示顾客点，实心点表示充电站，用颜色区 分不同电动汽车车的路线。 表2 较大规模算例结果 问题规模 ，F 基本信息和计算结果 d 4 2 8 9 32 7 6 9 7 9 9 5 21 4 9 4 9 8 7 6 86 6 3 6 1 0 2 8 8 21 4 8 8 5 1 2 5 3 9 9 1 7 7 1 6 6 0 1 l 7 0 l 】 8 0 2 l 9 0 2 l 1 0 0 2 l 6 8 3 l 2 7 3 1 3 2 0 7 8 6 1 8 7 8 6 2 1 1 0 4 注：q 代表电动汽车最大行驶里程r 代表充电率。 辱1 成p 2 图26 0 1 1 的算例线路图 实验结果表明本文改进的分支定价算法能适 应于较大规模的电动汽车车辆路径问题，并且能在 不同规模数据集下和可接受的时间范围内求得最 优解。虽然求解时间随着问题规模增大而增加，但 一S S S S ； 。一“h h h钆h挑孤 弘弘孙h h h|曼佩一耋薹慨 3 2 l 2 1 2 2 3 3 2 圯蝎“蝎“虾“砖拍灯啪 ，m m m博：2”：2刊 万方数据 第4 期揭婉晨，等：基于分支定价算法的电动汽车车辆路径问题 9 9 这与数据本身和问题复杂度有一定关系，不影响本 文提出算法的一般实用性。 4 2 3相关因素灵敏度分析 电动汽车的充电时间由充电率的大小和其到 达充电站的剩余电量决定，它会直接影响本文模型 的计算结果。因此，本文分析电动汽车的最大行驶 里程和充电率的变化对结果的影响。 为了保证实验的一般性，从改进的S o l o m o n 算 例中选取5 组同规模的中等实例进行测试，分别命 名为A ，日，c ，D 和E ，其中顾客点数量为5 0 ，充电站 数量为2 1 ，电池的最大行驶里程为6 2 1 4 ，充电率 为0 4 8 。 1 ) 电池的最大行驶里程 为了研究电动汽车电池的最大行驶里程对结 果的影响，将其设为相对初始值逐渐增加0 ， 2 5 。5 0 ，7 5 和1 0 0 ，即6 2 1 4 ，7 7 6 8 ，9 3 2 1 ， 1 0 8 7 5 和1 2 4 2 8 。实验结果如表3 所示。 表3电池最大行驶里程的灵敏度分析 注：n 代表充电站的个数。 实验结果表明：当电池的最大行驶里程逐渐增 加时，所需电动汽车的数量呈减少的趋势，且电动 汽车经过充电站的数量和配送总距离也逐渐减少。 当其最大行驶里程增加到一定程度后，车辆不需要 经过充电站便可完成配送任务，问题转化为传统的 带时间窗的V R P 问题。电池的最大行驶里程的增 加将导致一辆电动汽车可以服务更多的顾客点，那 么物流企业所需的配送车辆数将可能相应地减少， 物流企业配送距离也将逐渐变短，但由于顾客点时 间窗的限制可能导致多个顾客点之间不能被同一 辆电动汽车访问，配送车辆将减少到一定值后保持 不变，电动汽车有可能不需要经过充电站。 2 ) 充电率 为了研究电动汽车的充电率对计算结果的影响，将 充电率设为相对初始值逐渐增加0 ，1 0 0 ， 2 0 0 ，3 0 0 和4 0 0 ，即0 4 8 ，0 9 6 ，1 4 4 ，1 9 2 和 2 4 。实验结果如表4 中所示。 表4 充电率的灵敏度分析 从表4 中，可以看出随着充电率的递增，该物 流企业所需的配送车辆总数和配送总距离呈减少 的趋势，而电动汽车经过充电站的数量是波动的。 由于充电率会影响电动汽车的充电时间，且充电时 间的长短与电动汽车能否在规定的时间窗内到达 相应的顾客点直接相关，充电时间的减少有可能会 使一辆电动汽车对更多的顾客点进行配送，所以物 流企业所需的配送车辆数和配送总距离将可能相 应地减少。与最大行驶里程不同，充电率是通过改 变充电时间来间接地影响电动汽车的行驶路线，因 此电动汽车经过充电站的数量是浮动的。实例C 中实验的结果保持不变，是因为充电率的增加已不 能使一辆电动汽车配送更多的顾客点，但可以通过 增加最大行驶里程离来优化结果。 从上面实验可以看出，在电动汽车发展的初 期，特别是在充电站数量有限，考虑充电站建设成 本的情况下，增加电动汽车的行驶里程较增大电池 的充电率更能节省系统配送的总成本。 5结束语 本文研究了在充电站位置已知的情况下，含有 时间窗的电动汽车车辆路径问题，并建立了其相应 的混合整数规划模型，设计了适合电动汽车的基于 万方数据 运 筹与管 理 2 0 1 6 年第2 5 卷 列生成的分支定价算法。然后，在c P L E x 上运行 了一系列的小型算例，验证了本文模型与算法的正 确性。最后，通过改进的S 0 1 0 m o n 算例证明了本文 的分支定价算法能有效地减小问题规模，求得较大 规模的电动汽车车辆路径问题的最优解，并对电动 汽车的最大行驶里程和充电率做了灵敏度分析，发 现若考虑充电站的建站成本，增加电动汽车的行驶 里程较提高电池的充电率更能节省系统配送的总 成本。下一步的研究将从两方面出发：一方面，改 进子问题的动态规划搜索策略，以提高其求解速 度；另一方面，改进本文的模型，研究含有多配送点 和最大行驶里程不同的多类型电动汽车的车辆路 径问题。 参考文献： 1 中国气候变化信息网全球交通工具碳排放增幅惊人 2 0 0 8 - 0 1 - 1 6 A v a i l a b l ef m m ：h n p ：w w w c c c h i n a g o v c n c I l N e w s I n f 0 a s p ? N e w s I d = 1 0 5 0 3 2 c h e l l a 8 w 肌yc ，R a m e s hR ，R a ucY V As u p e r 、，i s o r y c o n t I D lo faf u e l f r e e e l e c t r i cv e h i c l ef o rg r e e ne n v i r o n m e n t c I n ：P r o c e e d i n g so fI n t e m a t i o n a lc o n f e r e n c e ， E m e r g i n gT r e n d si n E l e c t r i c a l E n g i n e e r i n ga n dE n e r g y M a n a g e m e n t ( I C E T E E E M ) ，I E E E 2 0 1 2 3 中华人民共和国国务院国务院关于印发节能与新能源 汽车产业发展规划( 2 0 1 2 2 0 2 0 年) 的通知 z 2 0 1 2 4 中华人民共和国国务院关于加快新能源汽车推广应 用的指导意见 z 2 0 1 4 5 D a n t z i gGB ，R a m s e rJH T h et n l c kd i s p a t c h i n gp r o b l e m J M a n a g e m e n ts c i e n c e ，1 9 5 9 ，6 ( 1 ) ：8 0 - 9 1 6 T o t hP ，V i g oD T h ev e h i c l em u t i n gp r o b l e m M S i a m 2 0 0 1 7 L 印o n eG T h ev e h i c l em u t i n gp r o b l e m ：a no v e n r i e wo f e x a c ta n d 印p m x i m a t ea l g o r i t h m s J E u m p e a nJ o u m a l o fO p e m t i o n a lR e s e a r c h ，1 9 9 2 ，5 9 ( 3 ) ：3 4 5 3 5 8 8 L a p o n eG w h a ty o us h o u l dk n o wa b o u tt h ev e h i c l er o u t i n gP 阳b l e m J N a v a lR e s e a r c hL o g i s t i c s ( N R L ) ， 2 0 0 7 ，5 4 ( 8 ) ：8 1 1 - 8 1 9 9 G e n d 陀a uM ，T a m n t i l i scD s 0 1 v i n gl a r g e - s c a l eV e h i c l e m u t i n gp r o b l e m sw i t ht i m ew i n d o w s ：t h es t a t e - o f t | l e - a