Back مسألة البائع المتجول Arabic Problema del viaxeru AST Səyahət edən tacir (alqoritm) Azerbaijani Problema del viatjant de comerç Catalan Problém obchodního cestujícího Czech Traveling salesman problem Danish Problem des Handlungsreisenden German Πρόβλημα του πλανόδιου πωλητή Greek Travelling salesman problem English Problema del viajante Spanish
Saltzaile ibiltariaren problema edo Bidaiariaren problema (ingelesez, Travelling Salesperson Problem, TSP), honakoa da: "hirien multzo bat izanik eta haien arteko distantziak ezagunak izanik, zein da hiri guztiak behin bakarrik bisitatu eta hasierako hirian amaitzen den ibilbiderik laburrena?". Ikerketa operatiboan eta konputazioaren zientzian garrantzia handia duen optimizazio konbinatorioko problema da. "Erosle Ibiltariaren Problema"-ren (Travelling Purchaser Problem, TPP) eta "Ibilgailuak Bideratzearen Problema"-ren (Vehicle Routing Problem, VRP) kasu partikularra da.
Problema 1930ean planteatu zen lehen aldiz eta optimizazio-problema konbinatorioen artean gehien aztertua izan denetako bat da. Haren ebazpenak duen konplexutasun konputazional altuagatik NP-Hard moduan sailkatua izan da. Hori dela eta, optimizazio-konbinatorioko problemen ebazpenerako sortzen diren metodo berrien eraginkortasuna neurtzeko erabiltzen da. Hain aztertua izan denez, ebazpen-metodo (zehatz eta heuristiko) asko ezagutzen dira. Horri esker, gaur egun tamaina handiko Bidaiariaren Problemak ebaztea posiblea da, milaka hirikoak barne. Problemaren bertsio hau NP-osoa da: "hirien multzo bat, haien arteko distantziak eta L luzera jakin bat emanik, hiri guztiak behin bakarrik bisitatu eta hasierako hirian amaitzen den ibilbiderik existitzen al da, gehienez L luzerakoa dena?".
Problemak aplikazio ugari ditu: plangintza-problemak, logistikako problemak, zirkuitu elektrikoen fabrikazioan agertzen direnak, etab. Gainera, problemaren planteamendua pixka bat aldatuta, jakintza-eremu askotan azpiproblema gisa agertu ohi da: DNAren sekuentziazioan, etab. Aplikazio horietan, “hiria” bezeroa izan daiteke, adibidez, edo soldadura-puntua, DNA zatia, etab. eta ibilbiderik laburrena aurkitzeko neurtu beharreko “distantzia” bidaia egiteko behar den denbora, ekoizpenaren kostua, DNA zatien arteko antzekotasuna, etab. Aplikazio askotan, problemaren ohiko murrizketez gain murrizketa gehigarriak egoten dira (mugatuta dauden baliabideak, kontuan hartu beharreko denbora-leihoak, etab.). Halakoetan, berez zaila den problemaren ebazpena are zailagoa gertatzen da.