فرمول های جدید برای مشکل جهت یابی
ترجمه نشده

فرمول های جدید برای مشکل جهت یابی

عنوان فارسی مقاله: فرمول های جدید برای مشکل جهت یابی
عنوان انگلیسی مقاله: New Formulations for the Orienteering Problem
مجله/کنفرانس: پروسیدیای مالی و اقتصاد – Procedia Economics and Finance
رشته های تحصیلی مرتبط: ریاضی
کلمات کلیدی فارسی: مسئله فروشنده دوره گرد، مشکل جهت یابی، فرمول ریاضی
کلمات کلیدی انگلیسی: Travelling Salesman Problem; Orienteering Problem; Mathematical Formulation
نوع نگارش مقاله: مقاله پژوهشی (Research Article)
شناسه دیجیتال (DOI): https://doi.org/10.1016/S2212-5671(16)30252-0
دانشگاه: Baskent University, Faculty of Engineering, Department of Industrial Engineering, Baglica Campus, Ankara 06530, Turkey
صفحات مقاله انگلیسی: 6
ناشر: الزویر - Elsevier
نوع ارائه مقاله: ژورنال
نوع مقاله: ISI
سال انتشار مقاله: 2016
شناسه ISSN: 2212-5671
فرمت مقاله انگلیسی: PDF
وضعیت ترجمه: ترجمه نشده است
قیمت مقاله انگلیسی: رایگان
آیا این مقاله بیس است: خیر
آیا این مقاله مدل مفهومی دارد: ندارد
آیا این مقاله پرسشنامه دارد: ندارد
آیا این مقاله متغیر دارد: ندارد
کد محصول: E13838
رفرنس: دارای رفرنس در داخل متن و انتهای مقاله
فهرست مطالب (انگلیسی)

Abstract

1-Introduction

2-Problem Identification and General Formulation

3-New Formulations

4-Computational Analysis

5-Conclusions

References

بخشی از مقاله (انگلیسی)

Abstract

Problems associated with determining optimal routes from one or several depots (origin, home city) to a set of nodes (vertices, cities, customers, locations) are known as routing problems. The Traveling Salesman Problem (TSP) lies at the heart of routing problems. One of the new variants of the TSP is named as TSP with Profits where the traveler must finish its journey within a predetermined time (cost, distance), by optimizing given objective. In this variant of TSP, all cities ought to not to be visited. The Orienteering Problem (OP) is the most studied case of TSP with Profits which comes from an outdoor sport played on mountains. In OP, traveler gets a gain (profit, reward) from the visited node and the objective is to maximize the total gain that the traveler collects during the predetermined time. The OP is also named as selective TSP. In this paper, we present two polynomial size formulations for OP. The performance of our proposed formulations is tested on benchmark instances. We solved the benchmark problems from the literature via CPLEX 12.5 by using the proposed formulations and existing formulation. The computational experiments demonstrate that; (1) both of the new formulations over estimates the existing one; and (2) the proposed formulations are capable of solving all the benchmark instances that were solved by using special heuristics so far.

Introduction

Travelling Salesman Problem (TSP) has many applications in vehicle routing, scheduling, cellular manufacturing, frequency assignment and etc. The TSP lies at the heart of routing and logistics problems. In recent years, a new variant of the TSP is seem to be an attractive research area where the objective focus on maximizing the profit (gains, rewards) obtained from the visited nodes. Those types of the TSP’s are called as TSP with Profits (Feillet et al., 2005). The Orienteering Problem (OP) is the most studied case of the TSP with Profits which comes from an outdoor sport played on mountains. This problem with an application is defined by Tsiligirides (1984). Golden et al. (1987) handled home fuel delivery problems as the OP. Tourist tour problems are the most attractive applications of the OP. In OP, traveler gets a gain (profit, reward) from the visited node and the objective is to maximize the total gain that the traveler collects during the predetermined time. The OP is also known as the Selective TSP (Laporte and Martello, 1990). In OP, the journey starts at the depot and ends at a given terminal node and all the nodes may not be visited because of the time or distance restriction. While solving OP, we look for finding a path rather than a circuit between specified two points. The OP is NP-hard; therefore solution approaches are concentrated on developing exact procedure and/or heuristics (Vansteenwegen et al., 2011). Laporte and Martello (1990) and Ramesh et al. (1992) presented procedures to find optimal solutions within a branch and bound methods.