6895

6438

كارشناسي ارشد

مهندسي صنايع

اصفهان: دانشگاه صنعتي اصفهان، دانشكده صنايع و سيستم ها

1390

چهارده، 143ص.: مصور، جدول، نمودار

ص.ع. به فارسي و انگليسي

محمدسعيد صباغ

نادر شتاب بوشهري

11/5/91

رضا حجازي، حميد مير محمدي

1396/09/14

كتابنامه

صنايع و سيستم ها

مهندسي صنايع و سيستم ها

ID6438

به فارسي و انگليسي: قابل رويت در نسخه ديجيتالي

Generalized Traveling Salesman Problem with Cluster Demand Mohammad Reihaneh M Reihaneh@in iut ac ir Date of Submission 2012 02 29 Department of Industrial Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language FarsiSupervisor Mohammad S Sabbagh Sabbagh@cc iut ac irAbstractThe generalized traveling salesman problem GTSP is a variation of the well known travelingsalesman problem TSP Given a graph G in which each of its n nodes belongs to at least one ofthe m clusters m n the GTSP seeks a minimum cost simple cycle which passes through eachcluster exactly once GTSP is useful for modeling the problems which need simultaneousselecting and sequencing Some of these applications are routing through welfare agencies designing material flow systems postal activities and covering tour problem The first work that is presented in this thesis is a new version of GTSP called the GTSP withcluster demand GTSP CD In GTSP CD a specific demand is associated with each cluster andeach node has a supply of its own while in the GTSP the demand of each cluster is one unit andsupply of each node is also one unit With some examples we will show that in some real worldapplications these assumptions don t apply In GTSP CD the objective is to find a minimum costSimple cycle that satisfies demand of all the clusters An exact branch and bound method is presented as a solution method for the asymmetric versionof this problem Computational results demonstrate the ability of the proposed algorithm to solvesmall and moderate size problems Due to the inability of this method to solve large scale GTSP CD problems we need to use heuristic and metaheuristic algorithms Hence two heuristic and onemetaheuristic algorithm are also proposed One of the heuristic algorithms is called ST CD whichobtains by performing some modifications on a GTSP specific heuristic called shortest tour ST Another proposed heuristic algorithm is called ST GNNCD which is an adaptation of nearestneighbor algorithm specific to TSP The metaheuristic algorithm that is proposed for GTSP CD is an ant colony system ACS algorithm which is called ST GACSCD Several local search algorithms are proposed in

محمدسعيد صباغ

نادر شتاب بوشهري

رضا حجازي، حميد مير محمدي