مسئله مسیریابی وسیله نقلیه وابسته به زمان با محدودیت‌های بارگیری دوبعدی: مدل‌سازی و حل

نوع مقاله: مقاله پژوهشی

نویسندگان

1 دانشگاه صنعتی اصفهان

2 دانشکده مهندسی صنایع دانشگاه صنعتی اصفهان

چکیده

این مقاله در ارتباط با معرفی، مدل­سازی و حل مسئله مسیریابی وسیله نقلیه وابسته به زمان با محدودیت‌های بارگیری دوبعدی است. این مسئله درصدد تحویل اقلام مستطیلی شکل با استفاده از یک ناوگان همگن از وسایط نقلیه است. در این مسئله، زمان طی کردن مسیر بین دو گره نه‌تنها به فاصله آن دو گره از همدیگر، بلکه به زمان خروج از گره مبدأ نیز بستگی دارد. در نظر گرفتن چنین فرضی برای طراحی مسیر در محیط­های شهری ضروری به نظر می‌رسد؛ چراکه ازدحام ناشی از ترافیک در ابتدا و انتهای زمان کاری، زمان طی مسیر را تغییر خواهد داد. با وجود کاربردی بودن چنین مسئله‌ای، پژوهشی که به بررسی آن پرداخته باشد، وجود ندارد. در این مقاله، یک مدل جدید برای مسئله مسیریابی وسیله نقلیه وابسته به زمان با محدودیت­های بارگیری دوبعدی ارائه شده است. پس از معرفی و مدل­سازی مسئله مذکور، به منظور بررسی و صحه­گذاری بر مدل ارائه­شده، مسائلی با ابعاد کوچک حل گردیده و برای حل مسئله در ابعاد بزرگ، از الگوریتم­های ژنتیک بهبودیافته و شبیه­سازی تبرید استفاده شده است که در روش­های مذکور برای بررسی امکان­پذیری بارگیری اقلام در درون وسایط نقلیه، مجموعه­ای از روش­های ابتکاری به کار گرفته می­شود. نتایج محاسباتی نشان می­دهد که الگوریتم­های ارائه­شده نتایج مناسبی ارائه می­دهند.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Two-dimensional loading time-dependent vehicle routing problem: mathematical modeling and solving approaches

نویسندگان [English]

  • Mohammad Said Sabbagh 1
  • Mehdi Alinaghian 2
  • Komail Zamanloo 1
1 Isfahan university of Technology
2 Isfahan University of Technology
چکیده [English]

This paper is dealing with Two-dimensional loading time-dependent vehicle routing problem. A new mathematical model is proposed and solved. Aforementioned problem is about delivering rectangular items to customers. In the problem that we considered, travel time between two nodes depends not only on their distance, but also depends on departure time from origin node. Such an assumption seems to be important for route design in urban areas, because traffic jam changes travel time on beginning and ending of work time. Despite applicability of such an issue, there is not any research considering this problem. In this paper, we proposed a new mathematical model. For evaluating and validating this model, some small-scale problems solved and for large-scale problems, a simulated annealing and an improved genetic algorithm are proposed. For checking feasibility of loading of assigned items to a vehicle, a collection of heuristic algorithms is used. Computational results confirm the effectiveness of the solving approaches.

کلیدواژه‌ها [English]

  • Vehicle routing problem
  • Two-dimensional loading
  • Time-dependent
  • Genetic Algorithm
  • Simulated annealing algorithm