زمان بندی گسسته ارسال ناوگان همگانی به ایستگاه های میانی از طریق الگوریتم شاخه و کرانه

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