Abstract
This paper introduces a Path Relinking metaheuristic approach for solving the Team Orienteering Problem (TOP), a particular routing problem in which a score is earned for visiting a location. The objective is to maximise the sum of the scores, while not exceeding a time budget Tmax for travelling to the selected locations. In the case of the simple Orienteering Problem (OP), a single route connecting all selected locations should be followed; in TOP m routes are required and the length of each route is restricted to Tmax. A fast and a slow variant of the approach are tested using a large set of test instances from the literature; they are compared to other state-of-the-art approaches. The fast variant achieves an average gap of 0.39% to the best known solutions in 5.0 s of calculation time, while the slow variant achieves a 0.04% gap within 272.8 s. Moreover, next to achieving most of the best known solutions for many test problems, the slow variant improved the best known results in five instances
چکیده
این مقاله ره یافت ابتکاری «باز اتصال مسیر» را برای حل مساله مسیریابی تیمی (TOP)، که مسأله ای خاص در زمینه مسیریابی است و در آن برای رسیدن به مکان های خاصی امتیاز کسب می شود، معرفی می کند. هدف، بیشینه سازی مجموع امتیازات کسب شده ضمن عدم تجاوز از زمان در نظر گرفته شده برای طی مسیر به مکان های تعیین شده (Tmax) می باشد. در مورد مسأله ساده مسیریابی تکی (OP)، مسیر واحدی که تمام نقاط را به هم متصل می کند، می بایست دنبال شود؛ در TOP تعداد m مسیر مورد نیاز است و طول هر مسیر محدود به Tmax است. یک نوع تند و یک نوع کند از ره یافت معرفی شده در این مقاله روی مجموعه بزرگی از نمونه ها آزمایش شده اند؛ سپس نتایج آنها با نتایج سایر ره یافت های جدید رایانه ای مقایسه شده است. نوع تند به فاصله 04/0 درصد در بازه زمانی 8/272 ثانیه دست پیدا کرد. علاوه بر این، نوع کند هم ضمن دستیابی به بهترین نتایج شناخته شده قبلی روی تعداد زیادی از نمونه مسأله ها، در 5 نمونه، نتایج کسب شده را بهبود بخشید.
کلمات کلیدی: مسأله مسیریابی تیمی، فوق ابتکاری، بازاتصال مسیر
1- مقدمه
در مسأله مسیریابی (OP)، مجموعه ای از n مکان های i، با امتیاز Si داده شده اند. نقطه آغاز (مکان 1) و نقطه پایان (مکان n) ثابت هستند. زمان مورد نیاز برای طی مسیر از مکان i به مکان j با نام tij شناخته شده و برای هر جفت مکان، معلوم است. مدت زمان Tmax داده شده و زمان بازدید از نقاط را محدود می کند. هدف OP تعیین مسیری واحد و محدود به بازه زمانی Tmax است که مجموع تمام امتیازات کسب شده را بیشینه سازی می کند. هر مکان حداکثر یک بار قابل عبور است. مسأله مسیریابی تیمی (TOP) یک مسأله OP است که امتیازات کسب شده m مسیر را که هر یک به بازه زمانی Tmax محدود می باشند، بیشینه می کند...