期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 176, 期 1, 页码 131-144出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2005.05.027
关键词
combinatorial optimization; probabilistic traveling salesman; heuristics; local search; stochastic vehicle routing
The probabilistic traveling salesman problem is a well known problem that is quite challenging to solve. It involves finding the tour with the lowest expected cost for customers that will require a visit with a given probability. There are several proposed algorithms for the homogeneous version of the problem, where all customers have identical probability of being realized. From the literature, the most successful approaches involve local search procedures, with the most famous being the 2-p-opt and I-shift procedures proposed by Bertsimas [D.J. Bertsimas, L. Howell, Further results on the probabilistic traveling salesman problem, European Journal of Operational Research 65 (1) (1993) 68-95]. Recently, however, evidence has emerged that indicates the equations offered for these procedures are not correct, and even when corrected, the translation to the heterogeneous version of the problem is not simple. In this paper we extend the analysis and correction to the heterogeneous case. We derive new expressions for computing the cost of 2-p-opt and 1 -shift local search moves, and we show that the neighborhood of a solution may be explored in O(n(2)) time, the same as for the homogeneous case, instead of O(n(3)) as first reported in the literature. (c) 2005 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据