روش آزاد سازي لاگرانژ براي مساله حمل و نقل با هزينه ثابت مرحله‌اي

Lagrangian Relaxation Method for the Step Fixed-Charge Transportation Problem

در اين مقاله مساله حمل و نقل با هزينه ي ثابت مرحله­ اي توسعه داده شده است كه محصولات از مبداها با هزينه مستقيم و ثابت مرحله ­اي به مقصدها فرستاده مي ­شوند. مدل پيشنهادي، مقدار حمل كالاها در آن مسيرها را با هدف مينيمم نمودن هزينه­ ها (مجموع هزينه­ هاي مستقيم و ثابت مرحله ­اي) طوري تعيين مي ­نمايد كه تقاضاي هر مشتري نيز برآورده شود. چون اين مساله از نوع مسائل چند جمله اي سخت است، نرم ­افزارهاي بهينه ­سازي قادر به حل اين مسأله در اندازه­ هاي كوچك و متوسط هستند. به منظور حل مسأله در اندازهاي بزرگ، روش­ آزاد­سازي لاگرانژ را پيشنهاد مي­ كنيم. نتايج محاسباتي نشان مي­ دهد كه روش آزادسازي لاگرانژ با شكاف بهينگي قادر به حل مسايلي با ابعاد بالاتر در مقايسه با نرم افزارهاي بهينه سازي است.

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 fixedcharges) 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 is able to solve large sized problems with optimality gap compared to general-purpose solvers.