Track: Logistics Management

Abstract

Routing problems have many practical applications in distribution and logistic management. The Traveling Salesman Problem (TSP) and its variants lie at the heart of routing problems. The Orienteering Problem (OP) is a new variant of the TSP which comes from an outdoor sport played on mountains.  In OP, the traveler must finish its journey within a predetermined time (cost, distance), and 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 the selective TSP since all cities do not ought to be visited. If there exist more than one traveler, OP is called Team Orienteering Problem (TOP).  TOP has special applications in vehicle routing, logistics and production scheduling problems and has new extensions. As far as we are aware, there exist a few formulations for TOP. In this paper we present two new integer linear programming formulations for TOP with O(n²) binary variables and O(n²) constraints, where n is the number of the nodes of the underlying graph. Proposed formulations can be used directly for OP when we get the number of the traveler as one. The performance of our formulations is tested on benchmark instances. We solved the benchmark instances from the literature via CPLEX12.5 by using the proposed formulation and existing formulation. The computational experiments demonstrate that both of the new formulations over estimate the existing one and our formulations are capable of solving most of the benchmark instances to optimally that were solved by using special heuristics so far. We demonstrate that, additional restrictions and/or side conditions can be easily imported to the both of the formulations. As a result, proposed formulations can be used to find optimal solution of the small and moderate real life OP and TOP by using an optimizer.