SUPERVISOR
Ghasem Moslehi,Mohammad ReisiNafchi
قاسم مصلحي (استاد راهنما) محمد رئيسي نافچي (استاد مشاور)
STUDENT
Samane Hasanabadi
سمانه حسن آبادي
FACULTY - DEPARTMENT
دانشکده مهندسی صنایع
DEGREE
Master of Science (MSc)
YEAR
1392
TITLE
Pickup and delivery routing problem with three dimensional loading constraints and time window
As the number of traortation goods as well as traortation cost has increased, the owners of the industry are motivated to seek for methods that reduce the costs and subsequently, increase the profit. Therefore, vehicle routing and loading problems have become two major issues for reducing traortation costs recently. one-to-one pickup and delivery problem is one among the pickup and delivery problem groups, in which goods are traorted between pickup and delivery nodes by available vehicles. For the first time, one-to-one pickup and delivery problem with three dimensional loading constraints and time window are considered in this thesis for hetergenous fleet of vehicles. To this end, an adaptive large neighbourhood search algorithm is developed for the routing problem. This algorithm achieves acceptble results for small size problems and it could also yield optimal objective for all problems. In addition, this algorithm showed also a good performance for large size problems, improving 76% of benchmark instances up to 2.66%. Also, we formulated two mathematical models for the integrated pikcup and delivery along with loading problems based on two approaches. In the first approach, stage indices were used as variables to integrate pickup and delivry problem with loading ones. In the second approach, a binery variable is used that defines the stage of visiting a node. Using this binery variable, the number of variables order is decreased. The two proposed models are assessed and it is revealed that the model using the second approach could solve larger size problems faster comparing with the model using the first approach. In both models, LIFO, stability and fragility constraints are formulated differently than the existing formulation. A heuristic based on the extreme points is used to solve the loading problem. To improving the performance of heuristic, order of boxes of each customer varied, in case the loading of boxes become infeasible during the first iteration. The number of order variations of each customer depends on the number of boxes. The proposed method could search more loading patterns and consequently, the quality of heuristic is increased. The loading heuristic is then integrated within the routing algorithm and the acquired results for small size problems were compared with mathematical model results. Intergrated algorithm yielded the optimal objective in 99% of the problems without stability and fragility constrains. Also, in case of considering all the constraints, the mathematical model without stability and fragility constraints is used as the lower bound. In this case, integrated algorithm achieved 0.11% difference with the optimal value. Comparing the acquired results with mathematical model results approved high performance of the inegrated algorithm. Finally, the acquired results for benchmark instances in large sizes are reported and the sensivity of each loading constarint to the objective is examined. Experiments showed that LIFO constraint has the highest infulence on objective increasing it by 16%.
چکيده: با توجه به افزايش حمل و نقل کالا و افزايش هزينههاي حمل و نقل، صاحبان اين صنعت به دنبال روشهايي براي کاهش هزينهها و در نتيجه افزايش سود هستند. لذا مسيريابي وسايل نقليه و بارگذاري آنها دو مسئله مهم در جهت کاهش هزينههاي حمل و نقل به شمار ميرود. مسائل دريافت و تحويل «يک به يک» يک گروه از مسائل مسيريابي با دريافت و تحويل است که در آن کالاها بين نقاط دريافت و تحويل مشخص توسط وسايل نقليه در دسترس جابجا ميشوند. در اين پاياننامه براي اولين بار مسئله دريافت و تحويل «يک به يک» با محدوديتهاي بارگذاري سهبعدي و وسايل نقليه ناهمگون به همراه پنجره زماني براي گرهها در نظر گرفته شده است. براي قسمت مسيريابي مسئله يک الگوريتم جستجوي همسايگي وسيع سازگار شده ارائه شد. اين الگوريتم توانست در ابعاد کوچک مسئله عملکرد خوبي را از خود نشان دهد و براي تمامي مسائل به جواب بهينه دست يابد. علاوه بر اين الگوريتم توانست در ابعاد بزرگ مسئله، 76% از مسائل نمونه موجود در ادبيات را تا 66/2 درصد بهبود دهد و براي ابعاد بزرگ نيز کارايي خوبي را از خود نشان دهد. علاوه بر اين براي مسئله يکپارچه شده دريافت و تحويل و بارگذاري دو مدل رياضي بر مبناي دو رويکرد ارائه شد. در رويکرد اول از انديس مرحله براي يکپارچهسازي دو مسئله دريافت و تحويل و بارگذاري استفاده شد. در رويکرد دوم متغيري صفر و يکي براي نشان دادن مرحله بازديد هر گره تعريف شد. استفاده از اين متغير صفر و يک توانست مرتبه تعداد متغيرها را از n 3 به n 2 کاهش دهد. صحت دو مدل مورد بررسي و تاييد گرفتند. در ارزيابي توان دو مدل، مدل با رويکرد دوم توانست مسائل تا ابعاد بيشتر و در زمان کمتري نسبت به مدل با رويکرد اول حل کند. علاوه بر اين محدوديتهاي LIFO ، پايداري و شکنندگي متفاوت از آنچه تاکنون در ادبيات موضوع وجود داشت، فرمولبندي شدند. براي حل مسئله بارگذاري از يک روش ابتکاري مبتني بر نقاط گوشهاي استفاده شد. براي افزايش کارايي الگوريتم، در صورت امکانناپذير شدن الگوريتم در اولين تکرار، تعويض ترتيب جعبههاي هر مشتري با توجه به تعداد جعبهها آن در نظر گرفته شد. استفاده از اين ايده باعث بررسي تعداد حالات بيشتر و افزايش کيفيت الگوريتم ابتکاري شد. الگوريتم ابتکاري ارائه شده براي مسئله بارگذاري درون الگوريتم مسيريابي ادغام شد و در ابعاد کوچک مسئله با نتايج مدل رياضي مورد ارزيابي قرار گرفت. الگوريتم يکپارچه شده توانست در حالتي که فرضيات مدل رياضي براي آن در نظر گرفته شده است، براي 99% مسائل به جواب بهينه دست يابد. همچنين در حالتي که تمام محدوديتها براي الگوريتم در نظر گرفته شد، از مدل رياضي بدون محدوديت پايداري و شکنندگي به عنوان حد پايين استفاده شد. در اين حالت، درصد خطا 19/0% به دست آمد. نتايج به دست آمده در مقايسه الگوريتم با مدل رياضي، کارايي بالاي الگوريتم را تأييد کرد. در نهايت نتايج الگوريتم براي مسائل نمونه جديد ايجاد شده گزارش شد و ميزان تأثيرگذاري هر يک از محدوديتهاي بارگذاري روي تابع هدف مورد بررسي واقع گرديد. بررسيهاي انجام شده نشان داد، محدوديت LIFO بيشترين تأثير را روي تابع هدف دارد. کلمات کليدي: مسيريابي، دريافت و تحويل، بارگذاري سهبعدي، محدوديتهاي بارگذاري، الگوريتم جستجوي همسايگي وسيع.