计算机科学 ›› 2018, Vol. 45 ›› Issue (4): 76-82.doi: 10.11896/j.issn.1002-137X.2018.04.011

• 2017年全国理论计算机科学学术年会 • 上一篇    下一篇

用于求解混合车辆路径问题的混合进化算法

孙启,金燕,何琨,徐凌轩   

  1. 华中科技大学计算机科学与技术学院 武汉430074;莱斯大学计算机科学系 休斯敦77005,华中科技大学计算机科学与技术学院 武汉430074,华中科技大学计算机科学与技术学院 武汉430074;深圳华中科技大学研究院 广东 深圳518057,华中科技大学计算机科学与技术学院 武汉430074
  • 出版日期:2018-04-15 发布日期:2018-05-11
  • 基金资助:
    本文受国家自然科学基金项目(61602196,7,61772219,61270183),深圳市科技计划项目(JCYJ20170307154749425)资助

Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem

SUN Qi, JIN Yan, HE Kun and XU Ling-xuan   

  • Online:2018-04-15 Published:2018-05-11

摘要: 文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的。给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点;规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次。MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小。混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法。该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛。在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的。

关键词: 元启发式,车辆路径问题,禁忌搜索,混合进化算法

Abstract: 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.

Key words: Metaheuristic,Vehicle routing problem,Tabu search,Hybrid evolutionary algorithm

[1] GOLDEN B,RAGHAVAN S,WASIL E.The Vehicle Routing Problem:Latest Advances and New Challenges [M].Springer US,2008.
[2] CORBERN A,PRINS C.Recent results on arc routing problems:An annotated bibliography[J].Networks,2010,56(1):50-69.
[3] PRINS C,BOUCHENOUA S.A memetic algorithm solving the vrp,the carp and general routing problems with nodes,edges and arcs[M]∥Recent Advances in Memetic Algorithms.Springer Berlin Heidelberg,2005,166:65-85.
[4] PANDI R,MURALIDHARAN B.A capacitated general routing problem on mixed networks [J].Computers & Operations Research,1995,22:465-478.
[5] DELL’AMICO M,HASLE G,CARLOS J,et al.An AdaptiveIterated Local Search for the Mixed Capacitated General Routing Problem [J].Transportation Science,2014,50(4):1223-1238.
[6] KOKUBUGATA H,MORIYAMA A,KAWASHIMA H.Apractical solution using simulated annealing for general routing problems with nodes,edges,and arcs[M]∥Engineering Stochastic Local Search Algorithms :Designing,Implementing and Analyzing Effective Heuristics.Springer Berlin Heidelberg,2007.
[7] BRANDIO J,EGLESE R.A deterministic tabu search algorithm for the capacitated arc routing problem [J].Computers & Ope-rations Research,2008,35(4):1112-1126.
[8] PRINS C,BOUCHENOUA S.A memetic algorithm solving the vrp,the carp and general routing problems with nodes,edges and arcs[M]∥Recent Advances in Memetic Algorithms.Springer Berlin Heidelberg,2005.
[9] BOSCO A,LAGANA D,MUSMANNO R,et al.Modeling andsolving the mixed capacitated general routing problem [J].Optimization Letters,2013,7(7):1451-1469.
[10] POTVIN J Y,BENGIO S.The vehicle routing problem withtime windows part II:genetic search [J].INFORMS Journal on Computing,1996,8(2):165-172.
[11] CHEN Y,HAO J K,GLOVER F.A hybrid metaheuristic approach for the capacitated arc routing problem[J].European Journal of Operational Research,2016,253(1):25-39.
[12] BACH L,HASLE G,WHLK S.A lower bound for the node,edge,and arc routing problem [J].Computers & Operations Research,2013,40(4):943-952.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!