Motivated by a real-world vehicle routing application, we consider the
maximum-weight independent set problem: Given a node-weighted graph, find a set
of independent (mutually nonadjacent) nodes whose node-weight sum is maximum.
Some of the graphs airsing in this application are large, having hundreds of
thousands of nodes and hundreds of millions of edges. To solve instances of
this size, we develop a new local search algorithm, which is a metaheuristic in
the greedy randomized adaptive search (GRASP) framework. This algorithm, which
we call METAMIS, uses a wider range of simple local search operations than
previously described in the literature. We introduce data structures that make
these operations efficient. A new variant of path-relinking is introduced to
escape local optima and so is a new alternating augmenting-path local search
move that improves algorithm performance. We compare an implementation of our
algorithm with a state-of-the-art openly available code on public benchmark
sets, including some large instances with hundreds of millions of vertices. Our
algorithm is, in general, competitive and outperforms this openly available
code on large vehicle routing instances. We hope that our results will lead to
even better MWIS algorithms.

针对实际的车辆路径问题，研究了最大权独立集问题，通过开发一个新的本地搜索算法，该算法使用了先前文献中未描述的更广泛的简单局部搜索运算和数据结构，引入了路径重新链接的新变体来避免局部最优解以及一种新的交替增广路径局部搜索移动来提高算法性能。