The Orienteering Problem (OP) is defined on a graph in which scores are assigned to the nodes and a travel time is assigned to each edge linking two nodes (Verbeeck et al., 2014). The main objective of the OP is to determine a single route by visiting as many nodes as possible that maximizes the total collected score subject to a given time budget frame. Several variants of the OP include: 1)Team Orienteering Problem (TOP), 2) Orienteering Problem with Time Windows (OPTW), 3) Team Orienteering Problem with Time Windows (TOPTW), 4) Time Dependent Orienteering Problem (TDOP) and so on.
A comprehensive survey about the OP can be found in Vansteenwegen et al. (2011) which focuses on the developments up to 2009. In recent years, other variants of the OP, such as Stochastic OP, Generalized OP and others, have been proposed. Many practical applications in crowdsourcing, tourism and other fields have also been modelled as the OP. A more recent survey is found in Gunawan, Lau and Vansteenwegen (2016) which summarizes recent literature and cover these variants and applications. This website is a companion of the latter survey paper aimed at providing a quick recap to the standard problems and (more importantly) annotations to variants and applications within in our group.
References
The Orienteering Problem with Time Windows (OPTW) considers the time window constraints that arise in the context when the service at a particular node has to start within a predefined time window specified by an earliest and a latest time (Labadie et al.,2012). An early arrival to a particular node leads to waiting times, while a late arrival causes an infeasibility issue. Let consider a set of routes M = {1, 2, ..., m}. The OPTW assumes m = 1. The OPTW can be extended to the Team Orienteering Problem with Time Windows (TOPTW) when m > 1 (Vansteenwegen et al., 2009).
Gunawan et al. (2015a) proposed an Iterated Local Search (ILS) algorithm to solve the OPTW, which is based on several LOCALSEARCH operations, such as SWAP, 2-OPT, INSERT and REPLACE. The combination between ACCEPTANCECRITERION and PERTURBATION mechanisms to control the balance between diversification and intensification of the search is also implemented. The computational results obtained by our proposed algorithm are compared against optimal solutions or best known solution values obtained by state-of-the-art algorithms. It is shown experimentally that the proposed algorithm is effective on well-known benchmark instances available in the literature. It is also able to improve the best known solution of some benchmark instances.
Gunawan et al. (2015b) introduced a mathematical model for the Generalized TOPTW, which incorporates some additional real-world constraints, such as the maximum total travel time may differ for each route, and the start and end nodes for each route may differ. An Iterated Local Search (ILS) algorithm is proposed to solve this TOPTW. The numerical results obtained by the proposed algorithm are compared against optimal solutions or best known solution values obtained by state-of-the-art algorithms. We show that our algorithm is able to improve several best known solution values on benchmark TOPTW instances. The proposed algorithm is also applied to solve real-world problems related to the Tourist Trip Design Problem (TTDP) which can be considered as an example of the Generalized Team Orienteering Problem with Time Windows (GTOPTW). It is shown experimentally that the proposed algorithm is effective on real-world problems.
A hybridization of Simulated Annealing and Iterated Local Search (SAILS) is proposed to solve the TOPTW (Gunawan et al., 2015c). The efficacy of the proposed algorithm is tested using benchmark instances. The results show that the proposed algorithm is competitive with the state-of-the-art algorithms in the literature. SAILS is also able to provide some new best known solutions for some instances.
Gunawan et al. (2017) introduce well-tuned ILS and SAILS to solve the TOPTW. As indicated in multiple research works on algorithms for the OP and its variants, determining appropriate parameter values in a statistical way, remains a challenge. Design of Experiments (DOE), namely factorial experimental design, is applied to screen and rank all the parameters thereby allowing us to focus on the parameter search space of the important parameters. The proposed algorithms are tested on benchmark TOPTW instances. It is demonstrated that well-tuned ILS and SAILS lead to improvements in terms of the quality of the solutions. More precisely, 50 best known solution values on the available benchmark instances are improved.
Benchmark Instances:
The description of data sets can be accessed via http://www.mech.kuleuven.be/en/cib/op
1. Solomon's instances (Montemanni and Gambardella, 2009) - c10* and c20* instances Solomon(c instances).zip - r10* and r20* instances Solomon(r instances).zip - rc10* and rc20* instances Solomon(rc instances).zip 2. Cordeau's instances (Montemanni and Gambardella, 2009) - pr01-pr10 instances Cordeau1.zip - pr11-pr20 instances Cordeau2.zip 3. Difficult instances (Vansteenwegen et al., 2009) - Solomon's instances Difficult(Solomon) instances.zip - Cordeau's instances Difficult(Cordeau) instances.zip
References
The Time Dependent Orienteering Problem (TDOP) is a generalization of the Orienteering Problem (OP). The travel time between two nodes depends on the departure time at the first node. The route between two nodes is affected by some factors, such as congestion levels, construction zone on certain segments, multiple transportation modes, etc. If each node has its opening hour, the problem is extended to the Time Dependent Orienteering Problem with Time Windows (TDOPTW).
Gunawan et al. (2014) presented a generalization of the Orienteering Problem, the Time-Dependent Orienteering Problem (TDOP) which is based on the real-life application of providing automatic tour guidance to theme park visitors. In this problem, the travel time between two nodes depends on the time when the trip starts. The problem is formulated as an integer linear programming (ILP) model and solved by the commercial ILP solver. Due to the computational difficulty with the commercial ILP solver, four heuristics are developed in a step by step fashion: greedy construction, local search and variable neighborhood descent, and two versions of iterated local search. The proposed metaheuristics were tested on modified benchmark instances, randomly generated problem instances, and two real world problem instances extracted from two popular theme parks in Asia. Experimental results confirm the effectiveness of the developed metaheuristic approaches, especially an iterated local search with adaptive perturbation size and probabilistic intensified restart mechanism. It finds within an acceptably short computation time, the optimal or near optimal solutions for TDOP problem instances of realistic size as in our target application.
Gunawan et al. (2016) introduced two heuristics, Adaptive ILS and Adaptive SAILS for solving the benchmark TDOP instances. Both include a mechanism of the reinforcement learning, called Learning Automata, to calculate the probability of selecting the operators of local search. It is concluded that the adaptive learning mechanism outperforms the state-of-the-art algorithm for some instances.
Benchmark Instances
1. Verbeeck's instances (Verbeeck et al., 2013) Verbeeck.zip 2. Modified Verbeeck's instances (Gunawan et al., 2014a) ModifiedVerbeeck.zip 3. Random instances (Gunawan et al., 2014a) Random.zip 4. Real world instances (Gunawan et al., 2014a) RealWorld.zip
References
Chen et al. (2013) formulated and studied the Multi-agent Orienteering Problem with Time-dependent Capacity Constraints (MOPTCC). MOPTCC is similar to the classical orienteering problem at the single-agent level: given a limited time budget, an agent travels around the network and collects rewards by visiting different nodes, with the objective of maximizing the sum of his collected rewards. The most important feature in MOPTCC is the inclusion of multiple competing and interacting agents. All agents in MOPTCC are assumed to be self-interested, and they interact with each other when arrive at the same nodes simultaneously. As all nodes are capacitated, if a particular node receives more agents than its capacity, all agents at that node will be made to wait and agents suffer collectively as a result (in terms of extra time needed for queueing). Due to the decentralized nature of the problem, MOPTCC cannot be solved in a centralized manner; instead, equilibrium solutions are needed; and if this is not possible, at least approximated equilibrium solutions.
Chen et al. (2014) proposed a variant of the sampled fictitious play algorithm that can efficiently identify equilibrium solutions. The major contribution of this paper is the formulation of the problem, and the first attempt in identifying an efficient and effective equilibrium-seeking procedure for MOPTCC.
References
Orienteering problems (OPs) are a variant of the well-known prize-collecting travelling salesman problem, where the salesman needs to choose a subset of cities to visit within a given deadline. OPs and their extensions with stochastic travel times (SOPs) have been used to model vehicle routing problems and tourist trip design problems. However, they suffer from two limitations- travel times between cities are assumed to be time independent and the route provided is independent of the risk preference (with respect to violating the deadline) of the user. To address these issues, Lau et al. (2012) made the following contributions: (1) a dynamic SOP (DSOP) model is introduced, which is an extension of SOPs with dynamic (time-dependent) travel times; (2) a risk-sensitive criterion to allow for different risk preferences; and (3) a local search algorithm to solve DSOPs with this risk-sensitive criterion. The proposed algorithms on a real-world dataset for a theme park navigation problem as well as synthetic datasets employed in the literature are investigated. Varakantham and Kumar (2013) addressed the lack of a priori or posteriori guarantees with respect to optimal solutions by providing a principled optimization based approach tha imploys ideas from sample average approximation technique to solve SOPs.
References
The problem of crowd congestion at venues like theme parks, museums and world expos by providing route guidance to multiple selfish users (with budget constraints) moving through the venue simultaneously is addressed (Varakantham et al., 2015). The Selfish Orienteering Problem (SeOP) that combines Orienteering Problem (OP) and Selfish Routing (SR) is introduced to represent these settings. SR is a game between selfish agents looking for minimum latency routes from source to destination along edges of a network available to all agents. Thus, SeOP is a multi-agent planning problem where agents have selfish interests and individual budget constraints.
As with Selfish Routing, Nash Equilibrium as the solution concept in solving SeOP is employed. A direct mathematical program formulation to find a Nash equilibrium in SeOP cannot scale because the number of constraints is quadratic in the number of paths, which itself is an exponential quantity. To address scalability issues, Varakantham et al. (2015) make two key contributions. First, a compact non-pairwise formulation with linear number of constraints in the number of paths to enforce the equilibrium condition is provided. Second, DIRECT, an incremental and iterative master-slave decomposition approach to compute an approximate equilibrium solution, is introduced. Similar to existing flow based approaches, DIRECT is scale invariant in the number of agents. A theoretical discussion of the approximation quality and present experimental results clearly showing that 1) the non-pairwise formulation achieves the same solution quality as the pairwise one using a fraction of the number of constraints; and 2) the master-slave decomposition achieves solutions with adjustable approximation gap using a fraction of the full path set.
References
The problem of mobile crowd-tasking, where a pool of crowd-workers are used to perform a variety of location-specific urban logistics tasks was investigated (Chen et al., 2014) as an OP. Most existing approaches for mobile crowd-tasking are myopic, i.e. they provide each worker a set of available tasks close to the worker’s current location; each worker then independently chooses which tasks she wants to accept and perform. In contrast, the Trajectory-Aware Centrally-coordinated Crowd-Sourcing (TRACCS) framework is a more coordinated approach taking into account workers’ expected location trajectories over a time horizon, as opposed to just instantaneous location.
The task assignment is formulated as an optimization problem, that seeks to maximize the total payoff from all assigned tasks, subject to a maximum bound on the detour (from the expected path) that a worker will experience to complete her assigned tasks. Heuristics are proposed to address this optimization problem.
The TRACCS framework has since been superceded by the TA$KER framework and the underlying engine for crowd-tasking was proposed in Chen et al. (2015a and b) where the uncertainty of workers’ historical trajectories is considered, since no one will take exactly the same route every day. In their work, the stochastic task recommendation problem where each worker is associated with several predicted routine routes with probabilities is studied and the goal is to maximize the expected total utility achieved by all workers. The separable structure of the formulation and apply the Lagrangian relaxation technique to scale up the solution approach are further exploited. Experiments have been performed over the instances generated using the real Singapore transportation network. The results are significantly better solutions than deterministic approaches.
References
The Tourist Trip Design Problem (TTDP) is defined as a route-planning problem for tourists interested in visiting multiple Points Of Interest (POIs) (Vansteenwegen and Van Oudheusden, 2007). The most basic version of the TTDP corresponds to the OP. In the context of the TTDP, the utility score for a particular node can be treated as the user's preference on a POI.
Lau et al. (2012) model a dynamic theme park navigation problem as the Stochastic OP. Information such as current queuing times at various attractions and ride status affect the itinerary. A real-world theme park data set from Singapore is considered. A comprehensive study is done by considering non-peak and peak days.
Varakantham et al. (2016) generalizes the work of Lau et al. (2012) to a Dynamic Stochastic OP that allows for time-dependent travel times. They provide non-linear optimization formulations along with their linear equivalents for modeling the risk-sensitive version of DSOP and provide a local search mechanism for solving it. They apply their approach to solve a real-world theme park trip planning problem.
Gunawan et al. (2014) focus on the problem of providing automatic tour guidance to a large leisure facility. This problem is treated as a variant of the TDOP. The travel time between two nodes depends on the time when the trip starts. Two real case studies from two theme parks in Asia are solved by the proposed algorithm.
Varakantham et al. (2015) address the problem of crowd congestion at certain venues like theme parks, museums and world expos as a variant of the Multi-agent OP. Multiple users are assumed to be selfish and move through the venue simultaneously considering each other's plans. This problem is modelled as a Selfish OP. The study is again applied to a theme park in Singapore.
Gunawan et al.(2016) propose a mathematical model for the TTDP that extends the TOPTW constraints by incorporating more real-world constraints, such as different total travel time budgets, different start and end nodes for routes. An Iterated Local Search (ILS) algorithm is proposed in order to solve the TTDP. The algorithm is implemented to provide tour guidance in the Singapore context. It is shown experimentally that ILS is able to solving real-world problem instances within a few seconds.
References