A PRIORI OPTIMIZATION

• 成果类型: Article
• 署名作者: BERTSIMAS, DJ; JAILLET, P; ODONI, AR
• 署名单位: Institut Polytechnique de Paris; Ecole des Ponts ParisTech
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.38.6.1019
• 发表日期: 1990
• 页码: 1019-1033
• 关键词: NETWORKS GRAPHS; STOCHASTIC HEURISTICS; TRAVELING SALESMAN; probability; stochastic model applications; transportation; Vehicle Routing

摘要

Consider a complete graph G = (V, E) in which each node is present with probability p(i). We are interested in solving combinatorial optimization problems on subsets of nodes which are present with a certain probability. We introduce the idea of a priori optimization as a strategy competitive to the strategy of reoptimization, under which the combinatorial optimization problem is solved optimally for every instance. We consider four problems: the traveling salesman problem (TSP), the minimum spanning tree, vehicle routing, and traveling salesman facility location. We discuss the applicability of a priori optimization strategies in several areas and show that if the nodes are randomly distributed in the plane the a priori and reoptimization strategies are very close in terms of performance. We characterize the complexity of a priori optimization and address the question of approximating the optimal a priori solutions with polynomial time heuristics with provable worst-case guarantees. Finally, we use the TSP as an example to find practical solutions based on ideas of local optimality.