Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: The Hamiltonian p–median problem. | The Hamiltonian p median problem Holger Glaab Alexander Pott Institute for Mathematics Institute for Algebra and Geometry University of Augsburg University of Magdeburg 86135 Augsburg 39016 Magdeburg glaab@ Submitted February 16 1999 Accepted April 25 2000 Abstract We deal from a theoretical point of view with the asymmetric Hamiltonian p-median problem. This problem which has many applications can be viewed as a mixed routing location problem. An ILP-formulation based on a new class of inequalities subtour number constraints is presented. The associated Hamiltonian p-median polytope is examined in particular its dimension and its affine hull. We determine which of the defining inequalities induce facets. 1 Introduction In the last decade the class of so-called mixed routing location problems attracted a lot of research interest. Many different problem variants have been developed. This is due to its practical relevance in many real world situations and the breakthroughs in solving the related problem the traveling salesman problem TSP . These new methods provided the necessary framework for investigating more complicated combinatorial optimization problems. This paper deals with a special case of combined routing location problems the Hamiltonian p-median problem HpMP . This problem has been introduced by Branco and Coelho 2 . The investigation is motivated by a practical application the so-called laser multi-scanner problem LMSP see 6 and 12 which can be modelled as an asymmetric Hamiltonian p-median problem with an additional class of side constraints. The HpMP itself arises in its own or as an embedded problem in a wide range of practical Both authors thank the German Ministry for education and science for supporting this project under the name Combinatorial optimization problems in the leather industry. The content of this paper forms part of the first author s doctoral thesis. 1 THE ELECTRONIC .
