روش آزاد سازی لاگرانژ برای مساله حمل و نقل با هزینه ثابت مرحلهای
محورهای موضوعی : آمارعلی محمودی‌راد 1 , صادق نیرومند 2 , مسعود صانعی 3 , عبدالرحمان ساجدی نژاد 4
1 - استادیار، دانشگاه آزاد اسلامی واحد مسجد سلیمان، گروه ریاضی، مسجدسلیمان، ایران
2 - استادیار، موسسه آموزش عالی فیروزآباد، گروه مهندسی صنایع، فیروزآباد، فارس، ایران
3 - دانشیار، دانشگاه آزاد اسلامی واحد تهران مرکزی، گروه ریاضی، تهران، ایران
4 - استادیار، دانشگاه آزاد اسلامی واحد مسجد سلیمان، گروه ریاضی، مسجدسلیمان، ایران
کلید واژه: Step fixed-charge, Transportation problem, Lagrangian relaxation,
چکیده مقاله :
در این مقاله مساله حمل و نقل با هزینه ی ثابت مرحلهای توسعه داده شده است که محصولات از مبداها با هزینه مستقیم و ثابت مرحلهای به مقصدها فرستاده میشوند. مدل پیشنهادی، مقدار حمل کالاها در آن مسیرها را با هدف مینیمم نمودن هزینهها (مجموع هزینههای مستقیم و ثابت مرحلهای) طوری تعیین مینماید که تقاضای هر مشتری نیز برآورده شود. چون این مساله از نوع مسائل چند جمله ای سخت است، نرمافزارهای بهینهسازی قادر به حل این مسأله در اندازههای کوچک و متوسط هستند. به منظور حل مسأله در اندازهای بزرگ، روش آزادسازی لاگرانژ را پیشنهاد میکنیم. نتایج محاسباتی نشان میدهد که روش آزادسازی لاگرانژ با شکاف بهینگی قادر به حل مسایلی با ابعاد بالاتر در مقایسه با نرم افزارهای بهینه سازی است.
In this paper, a step fixed charge transportation problem is developed where the products are sent from the sources to the destinations in existence of both unit and step fixed-charges. The proposed model determines the amount of products in the existing routes with the aim of minimizing the total cost (sum of unit and step fixed-charges) to satisfy the demand of each customer. As the problem is NP-hard, a moderate sized instance of this problem becomes intractable for general-purpose solvers. In order to overcome this difficulty, a Lagrangian relaxation approach is proposed. The computational experiments show that the Lagrangian relaxation algorithm isable to solve large sized problems with optimality gap compared togeneral-purpose solvers.