A polyhedral approach to delivery man problem

Abstract

ÖZET DELIVERY MAN PROBLEMİNE POLİHEDRAL YAKLAŞIMLAR Pınar Keskinocak Endüstri Mühendisliği Bölümü Yüksek Lisans Tez Yöneticisi: Doçent Mustafa Akgül 1992 Bu tezde, Delivery Man Problemi 'ne palihedral yaklaşımlar tartışılmaktadır. Ön celikle problemin iki değişik formülasyonu verilmiş ve doğrusal programlama gevşetmesi için kombinatoryal bir çözüm yöntemi geliştirilmiştir. Daha sonra bazı geçerli eşitsizlikler belirtilerek, Lagrangean gevşetmesi ve kesen düzlemler prosedürleri tartışılmıştır. Son olarak genel graflar ve ağaçlar için sezgisel yor damlar önerilmiştir. Anahtar kelimeler : Delivery Man Problemi, Polihedral Yaklaşımlar, Kesen Düzlemler.

ABSTRACT A POLYHEDRAL APPROACH TO DELIVERY MAN PROBLEM Pmar Keskinocak M.S. in Industrial Engineering Supervisor: Assoc. Prof. Mustafa Akgül 1992 In this thesis we discuss some polyhedral approaches to the Delivery Man Prob- lem(DMP),which is a special case of the Traveling Salesman Problem(TSP). First, we look at two formulations of the problem and describe a combinatorial solu tion procedure for the linear programming relaxation. Then we give some valid inequalities and discuss a Lagrangean Relaxation procedure and a cutting plane procedure. Finally, we propose heuristics for tree graphs and general graphs and give computational results. Keywords : Delivery Man Problem, Polyhedral Approach, Cutting Plane.