یکی از مسائل مهم در حوزه برنامه ریزی حمل و نقل مسافر در راه آهن، بهینه سازی مسیرها یا خطوط مسافری است که یک تصمیم استراتژیک و بلند مدت محسوب می شود. تاکنون مدل های ریاضی و روش های حل گوناگونی برای مسئله برنامه ریزی خطوط ارائه شده است. در این مقاله یک روش حل جدید بر پایه الگوریتم ایجاد ستون پیشنهاد شده که برای اولین بار، مسئله برنامه ریزی خطوط مسافری به صورت یک مسئله اصلی و دو زیر مسئله تعریف شده است. از آنجایی که جواب حاصل از روش ایجاد ستون غیر عدد صحیح است، برای تبدیل جواب های حاصل به مقادیر صحیح یک الگوریتم ابتکاری پیشنهاد شده است. هدف مسئله برنامه ریزی خطوط مسافری در این مقاله، بیشینه سازی تعداد مسافرین مستقیم است. ارزیابی روش حل پیشنهادی با استفاده از شانزده مسئله نمونه و مقایسه جواب های بدست آمده از روش پیشنهادی با روش حل مبتنی بر شاخه و حد و نرم افزار بهینه سازی CPLEX انجام شده است. نتایج بدست آمده نشان دهنده کارایی و دقت بالای روش حل پیشنهادی است.
