系统工程理论与实践
繫統工程理論與實踐
계통공정이론여실천
Systems Engineering—Theory & Practice
2014年
8期
2092~2105
,共null页
饶卫振 金淳 王新华 刘锋
饒衛振 金淳 王新華 劉鋒
요위진 금순 왕신화 류봉
低碳物流 车辆路径问题 道路坡度 车辆能耗
低碳物流 車輛路徑問題 道路坡度 車輛能耗
저탄물류 차량로경문제 도로파도 차량능모
low-carbon logistics; vehicle routing problem; road gradient; energy consumption of vehicle
经典车辆路径问题(vehicleroutingproblem,VRP)模型不考虑道路的坡度,通常以最小化车辆行驶总距离、总耗时或派送车辆数为目标函数.在考虑道路坡度因素的基础上,提出了以配送车辆总能耗最小为目标的低碳车辆路径问题模型(energyconsumptionminimizinglow—carbonVRP,ECM—LCVRP);然后,以带能力约束的车辆路径问题(capacitatedVRP,CVRP)为参照,分析了ECM—LCVRP的解空间大小及基本算法改进法则在ECM—LCVRP中的执行复杂度,发现ECM—LCVRP较CVRP更加难以求解,并且分析了不同坡度下ECM—LCVRP和CVR,P的区别与联系;另外,基于配送方案的能耗值与行驶距离正相关的规律,提出了求解不同道路坡度环境下ECM—LCVR,P的双目标策略(twoobjectivestrategy,TOS);最后,设计了40个ECM—LCVRP算例,并采用综合了算法基本改进规则的混合局部搜索算法(hybridlocalsearch,HLS)和HLS+TOS两种方式求解,求解结果表明:在不同的运算时间内,TOS策略均能够有效地提高HLS的求解质量,且求解时间越短,TOS的效果越明显.
經典車輛路徑問題(vehicleroutingproblem,VRP)模型不攷慮道路的坡度,通常以最小化車輛行駛總距離、總耗時或派送車輛數為目標函數.在攷慮道路坡度因素的基礎上,提齣瞭以配送車輛總能耗最小為目標的低碳車輛路徑問題模型(energyconsumptionminimizinglow—carbonVRP,ECM—LCVRP);然後,以帶能力約束的車輛路徑問題(capacitatedVRP,CVRP)為參照,分析瞭ECM—LCVRP的解空間大小及基本算法改進法則在ECM—LCVRP中的執行複雜度,髮現ECM—LCVRP較CVRP更加難以求解,併且分析瞭不同坡度下ECM—LCVRP和CVR,P的區彆與聯繫;另外,基于配送方案的能耗值與行駛距離正相關的規律,提齣瞭求解不同道路坡度環境下ECM—LCVR,P的雙目標策略(twoobjectivestrategy,TOS);最後,設計瞭40箇ECM—LCVRP算例,併採用綜閤瞭算法基本改進規則的混閤跼部搜索算法(hybridlocalsearch,HLS)和HLS+TOS兩種方式求解,求解結果錶明:在不同的運算時間內,TOS策略均能夠有效地提高HLS的求解質量,且求解時間越短,TOS的效果越明顯.
경전차량로경문제(vehicleroutingproblem,VRP)모형불고필도로적파도,통상이최소화차량행사총거리、총모시혹파송차량수위목표함수.재고필도로파도인소적기출상,제출료이배송차량총능모최소위목표적저탄차량로경문제모형(energyconsumptionminimizinglow—carbonVRP,ECM—LCVRP);연후,이대능력약속적차량로경문제(capacitatedVRP,CVRP)위삼조,분석료ECM—LCVRP적해공간대소급기본산법개진법칙재ECM—LCVRP중적집행복잡도,발현ECM—LCVRP교CVRP경가난이구해,병차분석료불동파도하ECM—LCVRP화CVR,P적구별여련계;령외,기우배송방안적능모치여행사거리정상관적규률,제출료구해불동도로파도배경하ECM—LCVR,P적쌍목표책략(twoobjectivestrategy,TOS);최후,설계료40개ECM—LCVRP산례,병채용종합료산법기본개진규칙적혼합국부수색산법(hybridlocalsearch,HLS)화HLS+TOS량충방식구해,구해결과표명:재불동적운산시간내,TOS책략균능구유효지제고HLS적구해질량,차구해시간월단,TOS적효과월명현.
The classical model of vehicle routing problem (VRP) generally minimizes the distance covered by vehicles, the sum of traveling time or the number of vehicle dispatched, without considering the degree of road gradient. This paper firstly presents a model of energy consumption minimizing low-carbon VRP (ECM-LCVRP) in which road gradient is considered; and secondly the solving complexity of ECM-LCV1RP model is analyzed based on classical capacitated vehicle routing problem (CVRP). It is found that ECM- LCVRP is more difficult to solve than CVRP by comparing their solution space and the complexity of 2-opt, or-opt, exchange and swap in their solutions. In order to solve efficiently ECM-LCVRP, a two objective strategy (TOS) is proposed in this paper by summarizing the relation and difference between ECM-LCVRP and CVRP under environment with different degree of road gradient. Finally, 40 ECM- LCVRP instances are devised. Then we use hybrid local search algorithm (HLS) with and without TOS to solve the 40 instances. The experimental results indicate that the TOS can significantly improve the quality of solutions generated by HLS and the performance of TOS is better when the running time is shorter.