الگوریتم جستجوی انطباقی محله بزرگ برای مسئله جهت یابی
ترجمه نشده

الگوریتم جستجوی انطباقی محله بزرگ برای مسئله جهت یابی

عنوان فارسی مقاله: یک الگوریتم جستجوی انطباقی محله بزرگ برای مسئله جهت یابی
عنوان انگلیسی مقاله: An adaptive large neighbourhood search algorithm for the orienteering problem
مجله/کنفرانس: سیستم های خبره با برنامه های کاربردی - Expert Systems with Applications
رشته های تحصیلی مرتبط: مهندسی کامپیوتر
گرایش های تحصیلی مرتبط: مهندسی الگوریتم ها و محاسبات
کلمات کلیدی فارسی: مسئله جهت یابی، فراابتکاری، خوشه بندی، جستجوی انطباقی محله های بزرگ
کلمات کلیدی انگلیسی: Orienteering problem، Metaheuristics، Clustering، Adaptive large neighbourhood search
نوع نگارش مقاله: مقاله پژوهشی (Research Article)
نمایه: Scopus - Master Journals List - JCR
شناسه دیجیتال (DOI): https://doi.org/10.1016/j.eswa.2018.12.050
دانشگاه: Departament d’Economia i Empresa, Universitat Pompeu Fabra and Barcelona GSE, Barcelona 08005, Spain
ناشر: الزویر - Elsevier
نوع ارائه مقاله: ژورنال
نوع مقاله: ISI
سال انتشار مقاله: 2019
ایمپکت فاکتور: 5/891 در سال 2018
شاخص H_index: 162 در سال 2019
شاخص SJR: 1/190 در سال 2018
شناسه ISSN: 0957-4174
شاخص Quartile (چارک): Q1 در سال 2018
فرمت مقاله انگلیسی: PDF
تعداد صفحات مقاله انگلیسی: 23
وضعیت ترجمه: ترجمه نشده است
قیمت مقاله انگلیسی: رایگان
آیا این مقاله بیس است: خیر
آیا این مقاله مدل مفهومی دارد: ندارد
آیا این مقاله پرسشنامه دارد: ندارد
آیا این مقاله متغیر دارد: ندارد
کد محصول: E11588
رفرنس: دارای رفرنس در داخل متن و انتهای مقاله
فهرست انگلیسی مطالب

Abstract


1- Introduction


2- Existing algorithms for the OP


3- Clustering and the OP


4- An ALNS-based heuristic for the OP


5- Results


6- Conclusions


References

نمونه متن انگلیسی مقاله

Abstract


We propose a new heuristic algorithm for the well-known Orienteering Problem, which aims at maximising the prize collected at vertices of a graph, visiting them through a simple closed tour whose length (also known as travel time) is limited by an upper bound. The algorithm is based on the Adaptive Large Neighbourhood Search metaheuristic paradigm, and uses a clustering of the graph to operate on groups of nearby vertices. Extensive computational results show that the proposed algorithm is able to find very good solutions (it produced 27 new best known solutions on a set of benchmark instances) and that it fares favourably compared with other state-of-the-art heuristics when tested with both long and short computation time budgets.


Introduction


The Orienteering Problem (OP) was introduced by Golden et al. (1987) and combines the selection of a set of customers to visit with the determination of the shortest tour to visit them. Imagine a tour operator who has to design a walking tour of a city. He has a vast set of possible interest points and associates a score to each of them, based on their desirability. Because the tour time is limited, he has to operate a selection of points to visit and decide the visit order, with the objective of maximising the scores of the visited points. Besides applications in tourist trip design (Borràs et al., 2014; Souffriau et al., 2008; Vansteenwegen and Van Oudheusden, 2007; Wang et al., 2008), the OP has been considered as a generalisation of the classical Travelling Salesman Problem when the salesman does not have enough time to visit all the cities (Tsiligirides, 1984). In this case, the prizes reflect the expected profit that the salesman can earn in each city. Tsiligirides (1984) also mentions an application in sporting events, which actually gave the name to the OP: an orienteering event is a competition usually held in forests where participants start from and come back to a basecamp within a time limit; during their tour they visit intermediate locations where they are awarded points. The participant who returns to the basecamp with the highest number of points wins. The survey by Vansteenwegen et al. (2011) also mentions applications to the home fuel delivery problem (Golden et al., 1987), where customers need to be resupplied with fuel. The lower is the level of fuel at the customer, the higher the urgency of visiting them during the current day; we can then model this problem as an OP where the prizes are inversely proportional to the fuel level. Another application arises in telecommunication network design (Thomadsen and Stidsen, 2003). The ring topology is often used to build wired networks, since it is resistent to single-failure disruptions. The length of the ring is constrained since noise is proportional to the total length and because a ring too long would increase the probability of double-failure disruptions. If the operator assigns a level of importance to each node, for example proportional to the amount of traffic it is expected to route, the problem of linking the most important nodes with a ring network can be modelled as an OP. A general history of the problem, a description of its many variants, and an overview of exact and heuristic algorithms developed to solve them, can be found in the two surveys by Vansteenwegen et al. (2011) and Gunawan et al. (2016).

  • اشتراک گذاری در

دیدگاه خود را بنویسید:

تاکنون دیدگاهی برای این نوشته ارسال نشده است

الگوریتم جستجوی انطباقی محله بزرگ برای مسئله جهت یابی
نوشته های مرتبط
مقالات جدید
لوگوی رسانه های برخط

logo-samandehi

پیوندها