We consider an orienteering problem (OP) where an agent needs to visit a series (possibly a subset) of depots, from which the maximal accumulated profits are desired within given limited time budget. Different from most existing works where the profits are assumed to be static, in this work we investigate a variant that has arbitrary time-dependent profits. Specifically, the profits to be collected change over time and they follow different (e.g., independent) time-varying functions. The problem is of inherent nonlinearity and difficult to solve by existing methods. To tackle the challenge, we present a simple and effective framework that incorporates time-variations into the fundamental planning process. Specifically, we propose a deterministic spatio-temporal representation where both spatial description and temporal logic are unified into one routing topology. By employing existing basic sorting and searching algorithms, the routing solutions can be computed in an extremely efficient way. The proposed method is easy to implement and extensive numerical results show that our approach is time efficient and generates near-optimal solutions.
Although in general OPs have been well researched, the time-dependent OPs (TOPs) have received relatively less attention comparing with other variants @cite_8 @cite_15 . Even so, most of existing TOPs discuss the time-varying properties that are associated with the real travel time between pairwise nodes, and assume that travel time between two nodes depends on the departure time at the first (or an earlier) node @cite_24 @cite_7 @cite_5 @cite_4 . Very rarely we could find the works that discuss about time-varying scores of OPs. One work that share certain similarity with this proposed problem is @cite_9 , where multiple vehicles need to serve a number of clients and the profit of each client follows a decreasing function of time. The work analyzed a lower bound and upper bound based on a classic MIP formulation.
@cite_4 @cite_7 @cite_8 @cite_9 @cite_24 @cite_5 @cite_15
2059762964 2039097929 1679712078 2073588680 2346699423
This paper introduces a fast solution procedure to solve 100-node instances of the time-dependent orienteering problem (TD-OP) within a few seconds of computation time. Orienteering problems occur in logistic situations were an optimal combination of locations needs to be selected and the routing between the selected locations needs to be optimized. In the time-dependent variant, the travel time between two locations depends on the departure time at the first location. Next to a mathematical formulation of the TD-OP, the main contribution of this paper is the design of a fast and effective algorithm to tackle this problem. This algorithm combines the principles of an ant colony system (ACS) with a time-dependent local search procedure equipped with a local evaluation metric. Additionally, realistic benchmark instances with varying size and properties are constructed. The average score gap with the known optimal solution on these test instances is only 1.4 with an average computation time of 0.5seconds. An extensive sensitivity analysis shows that the performance of the algorithm is insensitive to small changes in its parameter settings. The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time.For any ɛ > 0, we provide a (2 + ɛ)-approximation algorithm for the time-dependent orienteering problem which runs in polynomial time if the ratio between the maximum and minimum traveling time between any two sites is constant. No prior upper approximation bounds were known for this time-dependent problem. The Time Dependent Orienteering Problem with Time Windows (TDOPTW) consists of a set of locations with associated time windows and scores Visiting a location allows to collect its score as a reward Traveling time between locations varies depending on the leave time The objective is to obtain a route that maximizes the obtained score within a limited amount of time In this paper we target the use of public transportation in a city, where users may move on foot or by public transportation The approach can also be applied to the logistic sector, for example to the multimodal freight transportation We apply an hybrid approach to tackle the problem Experimental results for the city of San Sebastian show we are able to obtain valid routes in real-time. Vehicle Routing Problems have been extensively analyzed to reduce transportation costs. More particularly, the Vehicle Routing Problem with Time Windows (VRPTW) imposes the period of time of customer availability as a constraint, a common characteristic in real world situations. Using minimization of the total distance as the main objective to be fulfilled, this work implements an efficient algorithm which associates non-monotonic Simulated Annealing to Hill-Climbing and Random Restart. The algorithm is compared to the best results published in the literature for the 56 Solomon instances and it is shown how statistical methods can be used to boost the performance of the method. The Orienteering Problem (OP) has received a lot of attention in the past few decades. The OP is a routing problem in which the goal is to determine a subset of nodes to visit, and in which order, so that the total collected score is maximized and a given time budget is not exceeded. A number of typical variants has been studied, such as the Team OP, the (Team) OP with Time Windows and the Time Dependent OP. Recently, a number of new variants of the OP was introduced, such as the Stochastic OP, the Generalized OP, the Arc OP, the Multi-agent OP, the Clustered OP and others. This paper focuses on a comprehensive and thorough survey of recent variants of the OP, including the proposed solution approaches. Moreover, the OP has been used as a model in many different practical applications. The most recent applications of the OP, such as the Tourist Trip Design Problem and the mobile-crowdsourcing problem are discussed. Finally, we also present some promising topics for future research.