多目标同时取送货车辆路径问题的改进蚁群算法
An improved ant colony algorithm for multi-objective vehicle routing problem with simultaneous pickup and delivery
摘要点击 39  全文点击 32  投稿时间:2018-01-29  修订日期:2018-06-04
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/CTA.2018.80085
  2018,35(9):1347-1356
中文关键词  综合交通运输,物流工程,蚁群算法,同时取送货车辆路径问题,多目标局部搜索,贪婪搜索
英文关键词  Transportation, Logistics network optimization, Ant colony algorithm, Vehicle routing problem with simultaneous pickup and delivery, Multi-objective local search, Greedy search
基金项目  国家自然科学基金项目(61503043), 中央高校基本科研业务费专项资金项目(310822150020, 300102228402)资助
学科分类代码  
作者单位E-mail
陈希琼 长安大学 chenxiqiong123@163.com 
胡大伟 长安大学 dwhu@chd.edu.cn 
杨倩倩 长安大学  
胡卉 长安大学  
高扬 长安大学  
中文摘要
      为使同时取送货的车辆路径问题(Vehicle Routing Problem with Simultaneous Pickup and Delivery, VRPSPD)的运输成本和各路径间最大长度差最小化,建立同时考虑车辆容量和距离约束的VRPSPD双目标模型,通过软件测试验证了模型准确性。针对问题的特点构造一个嵌入禁忌表、且具有贪婪转移准则的多目标蚁群算法,对蚂蚁产生的解执行多目标迭代局部搜索程序,以在多个邻域上优化该解或产生新的Pareto解。采用响应曲面法拟合算法参数对目标值影响的数学关系,确定最优参数组合。用该算法求得文献中12组Solomon算例的Pareto解集,并以绝对偏向最小化总成本的解与文献中仅最小化总成本的几种算法的计算结果进行比较,结果表明算法可求得权衡各目标且使单一目标近似最优的Pareto解。
英文摘要
      In order to minimize the total cost and maximum gap among each tour in Vehicle routing problems with simultaneous pickup and delivery (VRPSPD), a VRPSPD bi-objective model which considers the vehicle capacity and distance constrain simultaneously was established. The accuracy of the model was verified by testing in a commercial software. Then a specific Multi Objective Ant Colony Optimization algorithm with a tabu list embedded and a greedy transfer rule was designed based on the definition of the problem. To optimize the solutions or generate new Pareto solutions in various neighborhoods, a multi-objective iterated local search procedure was executed on solutions obtained by ants. Response surface methodology was used to fit the mathematical relation of parameters and the objective functions in order to determine the best parameter combination. 12 sets of Solomon benchmark instances from literature were solved and Pareto solutions were obtained by the algorithm. The solutions with lowest cost (absolute preference to minimize the costs) from Pareto solutions were compared with previous results by several algorithms from literature which minimize the total costs only. The results indicate that the Pareto solutions acquired by the proposed algorithm provide good tradeoff between two objectives and yield approximate optimal of each single objective.