收益随服务时长变化定向问题的混合算法
首发时间:2017-04-26
摘要:定向问题是一类特殊的路径优化问题,本文在此基础上,研究收益随服务时间变化的定向问题,建立了以最大化总收益为目标的混合整数模型。该模型不仅决策访问哪些节点及其访问路径,而且决策在每个访问节点的服务时长。为求解该模型,提出一种禁忌搜索与精确算法混合的启发式算法,该算法将问题分解成路径优化子问题与服务时长分配子问题,通过精确求解服务时长分配问题为路径优化子问题提供,从而增强禁忌搜索的性能。实验结果表明,与精确性算法相比,所提出的混合算法能在1s内求解节点数量在66个以内的15个算例,并且其中13个算例中所得最好解优于精确算法的解;当问题规模扩大时,该算法也能在1min内提供高质量的解。
For information in English, please click here
A MATHEURISTIC FOR THE ORIENTEERING PROBLEM WITH VARIABLE PROFITS
Abstract:This paper addresses the Orienteering Problem with Service Time dependent Profits (OPSTP) which is a variant of the Orienteering Problem(OP). In the OPSTP, the profit collected at a customer is characterized by a reward function of service time. The task of the OPSTP is to route a set of vertices and assign service time to visited vertices respecting to a time budget such that the total pro?ts collected at these vertices are maximized. A mixed-integer linear programming(MIP) model is formulated for this OPSTP. A two-phase matheuristic that consists tabu search and a linear programming(LP) is developed for solving the problem. Extensive numerical experiments are conducted for instances from OP benchmark for small size and TSPLIB for large size. The results show that the proposed matheuristic is highly effective in finding good-quality solutions.
Keywords: orienteering problem matheuristic tabu search
论文图表:
引用
No.4725774119355214****
同行评议
勘误表
收益随服务时长变化定向问题的混合算法
评论
全部评论0/1000