توصيفگر ها :
حمل‌ونقل , مسئله مسيريابي وسايل نقليه , مسئله مسيريابي انتخابي وسايل نقليه , پنجره‌ي زماني , بارگذاري اقلام درون كانتينر , الگوريتم ابتكاري , بارگذاري دو بعدي , الگوريتم جستجوي محلي ارتقاء يافته , الگوريتم شبيه‌سازي تبريد
چكيده فارسي :
يكي از مسائل مهم مطرح در شهرها و كلان‌شهرها در عصر حاضر، مسئلۀ حمل‌ونقل است. افزايش روز افزون جمعيت شهرها، منجر به پيچيده شدن حمل‌ونقل خواهد شد. اين افزايش و پيچيدگي، رابطه مستقيمي با افزايش ترافيك و آلودگي در شهرها دارد. همچنين تأثير حمل‌ونقل بر قيمت تمام شده‌ي كالاها مسئله‌اي گريزناپذير است. به همين دليل توجه به اين مسئله مي‌تواند در افزايش رضايت مشتريان نقش به سزايي داشته باشد. از جمله مسائل مطرح در زمينه حمل‌ونقل، مسئلۀ مسيريابي وسايل نقليه است. اين مسئله توسط پژوهشگران متعددي مورد بررسي قرار گرفته است. در اين پايان¬نامه توسعه¬اي از اين مسئله تحت عنوان "مسيريابي وسايل نقليه با در نظر گرفتن مكان-زمان¬هاي پيشنهادي مشتريان با محدوديت¬هاي بارگذاري دو بعدي" بررسي مي¬شود. در اين مسئله هر مشتري براي دريافت كالاي خود چند گزينه¬ي تحويل پيشنهاد مي¬دهد. مختصات مكاني اين گزينه¬ها با توجه به زمان متغير است. اين امر مي‌تواند موجب افزايش رضايت مشتريان شود. همچنين با در نظرگرفتن گزينه¬هاي تحويل بيشتر، فضاي حل مسئله بزرگتر و احتمال يافتن جواب¬هاي بهتر افزايش مي¬يابد. از طرفي، يكي از مواردي كه در شرايط دنياي واقعي مطرح است، توجه به شكل و ابعاد كالاهاي مدنظر براي بارگيري درون كانتينرها است. در برخي از پژوهش‌هاي مطرح در حوزه مسيريابي، تقاضاي مشتريان تنها با عدد وزني مدنظر قرار مي‌گيرند؛ حال اينكه، در دنياي واقعي علاوه بر وزن، كالاها داراي شكل و ابعاد معين نيز مي‌باشند. به همين دليل علاوه بر توجه به محدوديت وزني وسايل نقليه، توجه به چگونگي جانمايي و چيدمان كالاها نيز ضروري است. از اين رو در نظرگرفتن محدوديت‌هاي بارگيري در مسائل مسيريابي، ضروري به نظر مي‌رسد.
در اين پايان¬نامه، يك مدل رياضي براي مسئله مذكور، گسترش داده شده است. تابع هدف اين مدل رياضي مينيمم‌سازي زمان خدمت‌رساني به مشتريان است. با توجه به در نظرگرفتن زمان¬هاي انتظار وسايل نقليه، اين تابع هدف نسبت به توابع هدف ديگر ارائه شده در ادبيات موضوع جامع¬تر است. در ادامه، با توجه به Np-Hard بودن مسئله مطرح شده، از الگوريتم‌هاي ابتكاري و فراابتكاري براي حل در ابعاد بالا استفاده شده است. بدين‌منظور 11 الگوريتم ابتكاري براي بارگذاري كالاها و سه الگوريتم ابتكاري مسيريابي مبتني بر: صرفه¬جويي، نزديك¬ترين مشتري ديدار نشده و بهترين قراردهي ارائه شده است. همچنين از دو الگوريتم فراابتكاري شامل الگوريتم شبيه سازي تبريد (SA) و جستجوي محلي ارتقا يافته به همراه جستجوي همسايگي وسيع (ELS-LNS) بهره گرفته شده است. كارايي الگوريتم‌هاي بارگذاري پس از رسيدن به جواب شدني در تمامي نمونه‌هاي موجود در ادبيات موضوع، تأييد شد. براي بررسي كارايي الگوريتم‌هاي فراابتكاري طراحي شده، از دو نمونه مسئله در ابعاد كوچك-متوسط و ابعاد بزرگ استفاده شد. عملكرد دو الگوريتم در نمونه¬هاي با اندازه كوچك و متوسط تقريبا مشابه و يكسان است. اما در نمونه-هاي با اندازه بزرگ الگوريتم ELS-LNS به جواب بهتري دست يافته است. در نهايت در قسمت انتهايي، با به كارگيري ابزار تحليل حساسيت، مسئله از ديدگاه‌هاي مديريتي نيز بررسي شده است.
چكيده انگليسي :
Today transportation is an important subject in cities and metropolises. The increasing population of cities will lead to the complexity of transportation and causes the increase of traffic and air pollution. Beside these, transportation has a major share on the finished cost. Because of the mentioned points, transportation should be considered as a main factor of customers' satisfaction. One of the most studied problems in the field of transportation is Vehicle Routing Problem (VRP). This dissertation examines one of the types of this problem entitled "Vehicle Routing Problem with Considering Customer's Locations Choices with Two-Dimensional Loading Constraints and Hard Time Window". In this problem, offers several delivery options to receive their goods. The spatial coordinates of these options vary with time. Considering different options for customer service will increase their relative satisfaction. On the other hand, including multiple options in the problem means expanding the solution space, which will most likely lead to better solutions. Also, one of the things that is relevant in the real world is to pay attention to the shape and dimensions of the goods to be loaded inside the containers. In some studies in the field of routing, customer demand is represented by only one number that represents the weight of the product. However, in the real world, in addition to weight, goods also have certain shapes and dimensions and it is also necessary to pay attention to the way the goods are placed and arranged. Therefore, it seems necessary to consider loading constraints in routing problems.
In this dissertation, a mathematical model is developed for the problem. The objective of this model is to minimize customers’ service time. This objective function is more comprehensive than the items discussed in the literature and, in addition to the costs of traversing, also includes waiting times. Given that the problem is Np-Hard, several heuristics and metaheuristic algorithms are used to solve the problem in large size instances. For this purpose, several algorithms for loading goods, several heuristic algorithms based on the nearest neighbor, the insertion approach and saving is designed. Two metaheuristic algorithms have also been designed. The first metaheuristic algorithm is based on simulated annealing (SA) and the second one is based on evolutionary local search with large neighbourhood search (ELS-LNS). The efficiency of the algorithms was tested on two categories of problems adapted from the literature. In small and medium instances, both algorithms provide relatively the same performance, but in large dimensions, the results show the superiority of the ELS-LNS algorithm. Finally, in the last part, by using sensitivity analysis, the problem is also examined from the management point of view.
