۱٫ Introduction

۲٫ Problem Identification and General Formulation

۳٫ New Formulations

۴٫ Computational Analysis

۵٫ Conclusions

References

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.