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

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

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

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 confirms the effectiveness of the solving approaches.