孙启,金燕,何琨,徐凌轩.用于求解混合车辆路径问题的混合进化算法[J].计算机科学,2018,45(4):76-82
用于求解混合车辆路径问题的混合进化算法
Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem
投稿时间:2017-05-21  修订日期:2017-07-06
DOI:10.11896/j.issn.1002-137X.2018.04.011
中文关键词:  元启发式,车辆路径问题,禁忌搜索,混合进化算法
英文关键词:Metaheuristic,Vehicle routing problem,Tabu search,Hybrid evolutionary algorithm
基金项目:本文受国家自然科学基金项目(61602196,7,61772219,61270183),深圳市科技计划项目(JCYJ20170307154749425)资助
作者单位E-mail
孙启 华中科技大学计算机科学与技术学院 武汉430074
莱斯大学计算机科学系 休斯敦77005 
 
金燕 华中科技大学计算机科学与技术学院 武汉430074 jinyan@mail.hust.edu.cn 
何琨 华中科技大学计算机科学与技术学院 武汉430074
深圳华中科技大学研究院 广东 深圳518057 
 
徐凌轩 华中科技大学计算机科学与技术学院 武汉430074  
摘要点击次数: 291
全文下载次数: 217
中文摘要:
      文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的。给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点;规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次。MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小。混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法。该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛。在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的。
英文摘要:
      This paper studied an NP-hard mixed capacitated general routing problem(MCGRP),which is derived from the classical vehicle routing problem(VRP) by adding the capacitated constraints and the demands on the arcs.Given a vehicle team with unlimited number,the vehicles serve the customers from the depot and need to return to the depot after completing service.The constraints are that the total load of each vehicle cannot exceed its capacity and each demand can only be served by one vehicle once.This paper aimed to provide a plan of the service route for each vehicle,so that the total travel expenses of all vehicles are minimized when the constraints are satisfied.The MCGRP has a relatively high theoretical value as well as application value.An efficient hybrid evolutionary algorithm was proposed for MCGRP.It applies a variable neighborhood tabu search with five neighborhood operators to improve the quality of solutions,and designs a route-based crossover operator to inherit the high-quality solutions so that the search efficiency can be improved.Experimental results on 23 well-known benchmark instances show that the proposed algorithm is effective for solving the MCGRP.
查看全文  查看/发表评论  下载PDF阅读器