基于单车场多车型车辆路径问题的混合求解算法  

Hybrid Algorithms for Single-depot and Heterogeneous-vehicle Vehicle Routing Problems

作　　者：郭海湘[1,2,3] 潘雯雯[1] 周欣然[1] 李冰毅[1] GUO Haixiang PAN Wenwen ZHOU Xinran LI Bingyi(School of Economics and Management Center for Digital Business and Intelligent Management, China University of Geosciences, Wuhan 430074, China School of Business, Central South University, Changsha 410083, China)

机构地区：[1]中国地质大学(武汉)经济管理学院,武汉430074 [2]中国地质大学(武汉)数字化商务与智能管理研究中心,武汉430074 [3]中南大学商学院,长沙410083

出　　处：《系统管理学报》2017年第5期824-834,共11页Journal of Systems & Management

基　　金：国家自然科学基金资助项目(71103163;71573237);教育部人文社会科学研究规划基金资助项目(15YJA630019);教育部新世纪优秀人才支持计划资助项目(NCET-13-1012);中央高校基本科研业务费专项资金资助项目(CUG120111;CUG110411;G2012002A;CUG140604)

摘　　要：为降低华北石油局大牛地气田采气过程中的车辆运输成本和车辆碳排放量,建立了单车场多车型车辆路径问题(SHVRP)数学模型,将扫描法、插入法、邻近法、两阶段法、遗传算法和蚁群算法等启发式算法作为求解SHVRP模型的基本算法,在分析算法原理、性能和适用环境等差异的基础上,提出了3种混合算法:混合启发式算法HHA(两阶段法+最远插入法+2-OPT)、混合遗传算法HGA(最邻近法+2-OPT+遗传算法)以及混合蚁群算法HACO(遗传算法+蚁群算法)。进而,列出了HA、HHA、GA、HGA、ACO、HACO等6种算法求解同一算例的10次运行结果的平均值,混合后算法的运行结果对比混合前算法的优势说明了混合算法的优越性。综合总配送成本、总碳排放量、配送车辆数和首次搜索到最优解的迭代数及计算时间等对3种混合算法进行比较,得出HACO最优,HGA次之,HHA最差。最后,将基于混合算法的智能运输方案与大牛地气田现有的基于经验法则的运输模式作对比,进一步说明了所提混合算法的可行性和有效性。In this paper,a SHVRP（single-depot and heterogeneous-vehicle vehicle routing problem）model is developed to reduce the transport cost and the carbon emissions produced by the vehicles.Based on that,heuristic algorithms that include scanning,insertion method,nearest neighbor algorithm,twophase method,genetic algorithm（GA）and ant colony algorithm（ACO）are used as the basic approach to solving the proposed model.Then,three hybrid algorithms,namely,the hybrid heuristic algorithm（HHA,i.e.,two-phase method＋the farthest insertion method＋2-OPT）,the hybrid genetic algorithm（HGA,i.e.,the nearest neighbor algorithm ＋ 2-OPT ＋ genetic algorithm）and the hybrid ant colony algorithm（HACO,i.e.,genetic algorithm ＋ ant colony algorithm）were developed after analyzing the underlying principles,performances and suitable application conditions.In addition,the performances of HA、HHA、GA、HGA、ACO and HACO have been tested on a real case study,from which we find that the three hybrid algorithms can easily dominate other heuristic algorithms. Moreover,after taking the following variables,such as distribution costs,carbon emissions,delivery vehicles,iterations of the firsttime to search the optimal solution,computing time into consideration,we find that HACO is the best,followed by the HGA,and then HHA.Finally,compare the intelligence transportation scheme based on the proposed hybrid algorithms with the existing mode currently used in the real case,we further show the feasibility and effectiveness of our proposed methods.

关 键 词：启发式算法 碳排放量 车辆路径问题 单车场多车型 

分 类 号：U116.2[交通运输工程]