امیرعلی زرین مهر - دانشجوی دکتری راه و ترابری دانشگاه تربیت مدرس، تهران، ایران
محمود صفارزاده - استاد گروه برنامه ریزی حمل و نقل دانشگاه تربیت مدرس، تهران، ایران

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

زمان بندی ناوگان، مدل ریاضی، الگوریتم شاخه و کرانه، شمارش کامل