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 بیشترین تأثیر را روی تابع هدف دارد. کلمات کلیدی: مسیریابی، دریافت و تحویل، بارگذاری سهبعدی، محدودیتهای بارگذاری، الگوریتم جستجوی همسایگی وسیع.