Tekijä: | Bertsimas, D. J. Jaillet, P. Odoni, A. R. |
Otsikko: | A prior optimization. |
Lehti: | Operations Research
1990 : NOV-DEC, VOL. 38:6, p. 1019-1033 |
Asiasana: | OPTIMIZATION TRAVELLING SALESMAN PROBLEM VEHICLE SCHEDULING |
Kieli: | eng |
Tiivistelmä: | A complete graph G=(V,E) is given in which each node is present with probability p1. The objective is to solve combinatorial optimization problems on subsets of nodes which are present with a certain probability. The idea of a priori optimization is introduced as a strategy competitive to the strategy of reoptimization, under which the combinatorial optimization problems is solved optimally for every instance. Four problems are considered: the travelling salesman problem /TSP/, the minimum spanning tree, vehicle routing, and travelling salesman facility location. The applicability of a priori optimization strategies in several areas is discussed. |
SCIMA