چکیده: در این پایان نامه ابتدا به معرفی مفاهیم اساسی مورد نیاز و مقدمه ای بر مسائل مکانیابی می پردازیم. در ادامه، مکانیابی خط در صفحه را بیان کرده سپس به بیان خواص این مساله با استفاده از نرم های مختلف می پردازیم و قضایای مربوط به آن را بررسی می کنیم. همچنین مکانیابی خط در فضای سه بعدی را بیان می کنیم و حالات مختلف این مساله را مورد بررسی قرار داده، به معرفی الگوریتم های ارائه شده برای این مسائل می پردازیم. در ادامه، مکانیابی خط نیمه ناخوشایند را معرفی کرده و با استفاده از الگوریتم بهینه سازی پرندگان(PSO) و خواص مسائل مکانیابی خط نیمه ناخوشایند یک الگوریتم برای مکانیابی خط میانه نیمه ناخوشایند ارائه می کنیم و نتایج محاسباتی آن را بدست می-آوریم و نشان می دهیم می توان این الگوریتم را به عنوان یک الگوریتم کارا برای مسائل مکانیابی خط میانه نیمه ناخوشایند در نظر گرفت.