23969

MAN3 186

دكتري

مديريت - تحقيق در عمليات

علوم اداري و اقتصاد

1403/06/27

134 ص.

مجيد اسماعيليان

داريوش محمدي زنجيراني

: مسأله مسيريابي وسايل نقليه , ناوگان ناهمگون , تحويل چندبخشي , چيدمان سه‌بُعدي , چندكالايي

چكيده اين پژوهش با در‌نظر گرفتن يك ناوگان محدود از وسايل نقليه ناهمگون، كه هر‌يك داراي اندازه‌ها و هزينه‌هاي ثابت، متغير سفر و توقف مختص به خود هستند؛ همچنين با تعريف محدوديت‌هاي بارگيري سه‌بُعدي طراحي چيدمان شامل جهات امكان‌پذير گردش جعبه‌ها، حداقل تكيه‌گاه پايه‌ي مورد نياز براي پايداري عمودي بار و شكنندگي يا امكان تحمّل بار توسط جعبه‌ها به بررسي و ارائه راه‌حلي براي يك مسأله‌ي تركيبي تحت عنوان 3L-HFFCVRP پرداخته است. درواقع مسأله‌ي مورد بررسي اين پژوهش، تركيبي از يك نوع مسأله مسيريابي وسايل نقليه (VRP) با يك نوع مسأله‌ي بارگيري كانتينري (CLP) است كه غالباً در آن‌دسته از شركت‌هاي توليدي مشاهده مي‌شود كه فرآورده‌هاي گوناگوني را توليد و در جعبه‌هاي مكعبي شكل با ابعاد و وزن‌هاي مختلف بسته‌بندي نموده و آنها را به‌منظور تأمين تقاضاهاي دريافت‌شده از مشتريان يا نمايندگي‌هاي فروش خود از طريق ناوگان ناهمگوني از وسايل نقليه (حامل‌هاي بار) به مقصد آنها ارسال مي‌نمايند. بديهي است كه براي چنين شركت‌هايي، علاوه بر ضرورت مسيريابي بهينه وسايل نقليه، طراحي چيدمان يا الگوهاي بارگيري مناسب كالاها نيز بسيار حائز اهميّت مي‌باشد چرا كه با توجه به هزينه‌هاي بالاي حمل و نقل، بر كاهش هزينه تمام شده آنها مؤثر خواهد بود. در‌ابتدا براي حل مسأله‌ي مسيريابي وسايل نقليه با سه ويژگي همزمان ناوگان ناهمگون ثابت، چندكالايي و تحويل چندبخشي موسوم به HFFVRP/MPSD يك مدل برنامه‌ريزي خطي عدد صحيح محض پيشنهاد شده است. اين مدل با انتخاب تعدادي از وسايل نقليه از ميان ناوگان موجود و تعيين كالاهايي كه بايد در هريك از آنها بارگيري شوند و نيز تعيين مسير حركت و ترتيب ملاقات مشتريان توسط آنها و اينكه هر وسيله نقليه چه كالاهايي را به هر مشتري تحويل مي‌دهد؛ هزينه كل حمل و نقل (مجموع هزينه‌هاي ثابت، متغير سفر و توقف در محل مشتريان) را به حداقل مي‌رساند. در اين مدل، از محدوديت‌هاي ويژه‌اي براي شكستن زيردورها استفاده شده است كه ضمن كاهش در تعداد محدوديت‌هاي نامساوي در مقايسه با روش متداول، مي‌تواند ترتيب ملاقات مشتريان را نيز مشخص نمايند. مدل دقيق ارائه شده براي تمام نمونه مسائل آزمايش شده تا 50 مشتري جواب‌هاي شدني به‌دست مي‌آورد اما از آنجايي كه در زمان مطلوب (تا 3600 ثانيه) قادر به يافتن جواب بهينه براي مسائل با بيش از 10 مشتري نبوده و براي دستيابي به جواب قابل قبول براي مسائلي با بيش از 15 مشتري، زمان زيادي صرف مي‌نمايد؛ به‌منظور بهبود سرعت ‌حل مسأله، يك مدل فراابتكاري مبتني بر الگوريتم ژنتيك هيبريد طراحي شده است. مدل فراابتكاري ارائه شده توانسته است با كاهش بيش از 95 درصدي در زمان اجرا، جواب‌هاي با كيفيت بالاتري براي مسأله HFFVRP/MPSD بدست آورد. بهبود كيفيت جوابهاي به‌دست‌آمده براي مسائل با بيش از 10 مشتري به‌طور ميانگين بيش از 45 درصد بوده است. در‌نهايت به‌منظور حل مسأله‌ي تركيبي، با وارد كردن محدوديت‌هاي بارگيري سه‌بُعدي به مدل فراابتكاري ياد‌شده، مدل كاملي مبتني بر الگوريتم ژنتيك هيبريد براي مسأله 3L-HFFCVRP توسعه يافته است.

Vehicle Routing Problem , Heterogeneous Fleet , Split Delivery , Three_Dimentional Layout Design , Multi_Product

Development of a Model for Solving the Heterogeneous Fixed Fleet Capacitated Vehicle Routing Problem with Three-Dimensional Loading Constraints (3L-HFFCVRP) in Order to Optimize Total Transportation Costs

مديريت

Abstract This research investigate a combined problem under the title of 3L-HFFCVRP problem by considering a fixed (limited) fleet of heterogeneous vehicles, each of them has its own dimensions, fixed (usage) costs, variable (travel) costs and stopping costs, and also by defining the practical constraints for three-dimensional loading, including the limitation in the possible directions of the boxes, the minimum required base support of boxes for the vertical (static) stability and the fragility of boxes (or ability of bearing the load on themselves). In fact, the problem investigated in this research is a combination of a type of vehicle routing problem (VRP) with a type of container loading problem (CLP), which is often seen in those manufacturing companies that produce various products and pack them in cubic boxes with various weights and dimensions and send them through a heterogeneous fleet of vehicles to their customer destination in order to satisfy their demands. It is obvious that due to the high cost of transportation, for such companies, in addition to the necessity of optimizing the routes of vehicles, it is very important to design the suitable layouts for loading goods in containers, At first, a pure integer linear programming model is proposed to solve the vehicle routing problem with three simultaneous characteristics of fixed heterogeneous fleet, multi-products and split delivery called HFFVRP/MPSD. This model minimizes the total cost of transportation (i.e., the sum of fixed costs, travel costs, and stopping costs) by selecting a number of vehicles from the fleet of vehicles and determines the products that should be loaded in each of them, as well as specifying the order of the customersʹ visits by each vehicle and determining which items each vehicle delivers to which customer. In this model, special constraints have been used to break the sub-tours, which, while reducing the number of inequality constraints compared to the conventional method, can also determine the order of meeting customers. The proposed exact method obtains feasible solutions for all tested sample of problems (with up to 50 customers), but since it is not able to achieve the optimal solution in an acceptable time (up to 3600 seconds) for problems with more than 10 customers, and it takes a lot of time to achieve satisfactory solutions for problems with more than 15 customers; in order to improve the speed of solving the problem and increase the efficiency of the model, a meta-heuristic model based on the hybrid genetic algorithm, has been developed. The presented meta-heuristic model has been able to obtain higher quality solutions for the problem by reducing the execution time by more than 95%. Also, the improvement of the quality of the solutions obtained for problems with more than 10 customers was more than 45% on average. Finally, in order to solve the combinatorial problem, by introducing three-dimensional loading constraints to the aforementioned meta-heuristic model, a complete model based on the hybrid genetic algorithm has been developed for the 3L-HFFCVRP problem.

5

76380