A survey on algorithmic approaches for solving tourist trip design problems
---
paper_title: The team orienteering problem

paper_content:

In the team orienteering problem, start and end points are specified along with other locations which have associated scores. Given a fixed amount of time for each of the M members of the team, the goal is to determine M paths from the start point to the end point through a subset of locations in order to maximize the total score. In this paper, a fast and effective heuristic is presented and tested on 353 problems ranging in size from 21 to 102 points. The computational results are presented in detail.
---
paper_title: Personalized Location-Based Recommendation Services for Tour Planning in Mobile Tourism Applications

paper_content:

Travel and tour planning is a process of searching, selecting, grouping and sequencing destination related products and services including attractions, accommodations, restaurants, and activities. Personalized recommendation services aim at suggesting products and services to meet users' preferences and needs, while location-based services focus on providing information based on users' current positions. Due to the fast growing of user needs in the mobile tourism domain, how to provide personalized location-based tour recommendation services becomes a critical research and practical issue. The objective of this paper is to propose a system architecture and design methods for facilitating the delivery of location-based recommendation services to support personalized tour planning. Based on tourists' current location and time, as well as personal preferences and needs, various recommendations regarding sightseeing spots, hotels, restaurants, and packaged tour plans can be generated efficiently. An application prototype is also implemented to illustrate and test the system feasibility and effectiveness.
---
paper_title: Evaluation of Intelligent Routes for Personalised Electronic Tourist Guides

paper_content:

Personalised Electronic Tourist Guides (PETs) provide an integrated solution for route generation based on the profiles and constraints of tourists, up-to-date Points Of Interest (POIs) and destination information. In this paper we present the result of an evaluation of a PET prototype that applies an advanced algorithm to generate personalised tourists routes including public transportation. The prototype has three main functionalities: recommendation, personalised route generation and route customisation. The validation scenario of the prototype has been the city of San Sebastian. The result of the validation has been positive and it showed that PETs are perceived as interesting tools by tourists. Moreover, both the personalised route generation and the inclusion of public transportation are perceived as valuable functionalities.
---
paper_title: The Mobile Tourist Guide: An OR Opportunity

paper_content:

Nowadays, an average tourist plans a vacation using web sites, magazine articles and guidebooks. The inability to modify this holiday plan in real-time motivates the need for a Next Generation Mobile Tourist Guide (MTG). The MTG, a handheld embedded device, is aware of the tourist's preferences, attraction values and trip information. Based on real-time and reliable data, the device can immediately suggest new integrated holiday plans. To develop these holiday plans, additional OR research and very specific decision models are required. In this paper, the Tourist Trip Design Problem (TTDP) is defined as an extension of the Orienteering Problem (OP).
---
paper_title: Integrating public transportation in personalised electronic tourist guides

paper_content:

Personalised electronic tourist guides (PETs) are mobile hand-held devices able to create tourist routes matching tourists' preferences. Transportation information has been identified as one of the most appreciated functionalities of a PET. We model the tourist planning problem, integrating public transportation, as the time-dependent team orienteering problem with time windows (TD-TOPTW) in order to allow PETs to create personalised tourist routes in real-time. We develop and compare two different approaches to solve the TD-TOPTW. Experimental results for the city of San Sebastian show that both approaches are able to obtain routes in real-time.
---
paper_title: ROSE: assisting pedestrians to find preferred events and comfortable public transport connections

paper_content:

In this paper, we describe ROSE (Routing Service), a mobile application which combines pedestrian navigation with event recommendation and live public transport support. It determines the best possible transport link and accompanies passengers throughout their entire journey. Our motivation is to free the passenger from as many tedious tasks as possible in finding an interesting event and on the way to it. Further, it reacts in real time to delays in the public transport system and calculates alternative routes when necessary. For route planning in this context, we will propose a two step algorithm for incorporating non monotone and non optimistic multi dimensional user preferences in an A*-like algorithm. We also present an assignment of theoretical foundations to real world route planning problems.
---
paper_title: Personalized tourist route generation

paper_content:

When tourists are at a destination, they typically search for information in the Local Tourist Organizations. There, the staff determines the profile of the tourists and their restrictions. Combining this information with their up-to-date knowledge about the local attractions and public transportation, they suggest a personalized route for the tourist agenda. Finally, they fine tune up this route to better fit tourists' needs. We present an intelligent routing system to fulfil the same task. We divide this process in three steps: recommendation, route generation and route customization. We focus on the last two steps and analyze them. We model the tourist planning problem, integrating public transportation, as the Time Dependent Team Orienteering Problem with Time Windows (TDTOPTW) and we present an heuristic able to solve it on real-time. Finally, we show the prototype which generates and customizes routes in real-time.
---
paper_title: Deep Map - challenging IT research in the framework of a tourist information system

paper_content:

Deep Map is a research framework that aims at building the prototype of an intelligent next generation spatial information system. Deep Map realizes the vision of a future tourist guidance system that works as a mobile guide and as a web-based planning tool. This long term research project addresses several challenging research aspects covering intelligent integration of information from different data sources and services including geographical information systems, multi-media databases, and interactive internet data sources such as reservation systems. On the basis of this complex information system the European Media Laboratory plans to build user interfaces that allow intuitive and easy access to information. Such a user interface including visual and natural language processing will be included into a mobile device that navigates the user through a city. Also virtual tours in a 3D-reconstructed city will be possible. In this paper, we present the current system that already covers a number of these aspects and demonstrates how tourists may be guided in the future.
---
paper_title: Intelligent Routing System for a Personalised Electronic Tourist Guide

paper_content:

When tourists are at a destination, they typically search for information Organizations. There, the staff categorizes tourists’ profile and restrictions. Combining this information with their up-to-date knowledge about the local attractions, weather and public transportation, they suggest a personalised route for the tourist agenda. This paper presents. an intelligent routing system for a Personalised Electronic Tourist Guide to fulfil the same task. This system improves the automatic route creation functionality of existing PETs to solve better the needs of tourists in several aspects: i) it includes public transportation, ii) it takes varying travelling times into account, adapting to real circumstances as rush-hours, iii) it calculates routes in real time to react to unexpected events, iv) it applies last generation heuristics from Operations Research to create routes efficiently, even in destinations with a large number of point of interests and a dense public transportation network.
---
paper_title: Web application for recommending personalised mobile tourist routes

paper_content:

This study deals with the problem of deriving personalised recommendations for daily sightseeing itineraries for tourists visiting any destination. The authors' approach considers selected places of interest that a traveller would potentially wish to visit and derives a near-optimal itinerary for each day of visit; the places of potential interest are selected based on stated or implied user preferences. The authors' method enables the planning of customised daily personalised tourist itineraries considering user preferences, time available for visiting sights on a daily basis, opening days of sights and average visiting times for these sights. Herein, the authors propose a heuristic solution to this problem addressed to both web and mobile web users. Evaluation and simulation results verify the competence of the authors' approach against an alternative method.
---
paper_title: Heuristic Methods Applied to Orienteering

paper_content:

A general description of the sport of orienteering in its two forms known as orienteering event and score orienteering event is given. The similarities between the latter and the generalized travelling salesman problem are underlined, and a common mathematical model is deduced. A ‘good’, if not ‘optimal’ solution of the corresponding problem by means of an efficient and computationally feasible method is derived and discussed. This solution is obtained by the use of either of two algorithms based on approximate methods. The two algorithms are given, and their efficiency is tested on a number of illustrative problems. Finally, a comparison between the two forms of the sport of orienteering is made.
---
paper_title: Iterated local search for the team orienteering problem with time windows

paper_content:

A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a team orienteering problem with time windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximise the sum of the collected scores by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.
---
paper_title: Multi-objective Meta-heuristics for the Traveling Salesman Problem with Profits

paper_content:

We introduce and test a new approach for the bi-objective routing problem known as the traveling salesman problem with profits. This problem deals with the optimization of two conflicting objectives: the minimization of the tour length and the maximization of the collected profits. This problem has been studied in the form of a single objective problem, where either the two objectives have been combined or one of the objectives has been treated as a constraint. The purpose of our study is to find solutions to this problem using the notion of Pareto optimality, i.e. by searching for efficient solutions and constructing an efficient frontier. We have developed an ejection chain local search and combined it with a multi-objective evolutionary algorithm which is used to generate diversified starting solutions in the objective space. We apply our hybrid meta-heuristic to synthetic data sets and demonstrate its effectiveness by comparing our results with a procedure that employs one of the best single-objective approaches.
---
paper_title: The prize collecting traveling salesman problem

paper_content:

The following is a valid model for an important class of scheduling and routing problems. A salesman who travels between pairs of cities at a cost depending only on the pair, gets a prize in every city that he vitis and pays a penalty to every city that he fails to visit, wishes to minimize his travel costs and net penalties, while visiting enough cities to collect a prescribed amount of prize money. We call this problem the Prize Collecting Traveling Salesman Problem (PCTSP). This paper discusses structural properties of the PCTS polytope, the convex hull of solutions to the PCTSP. In particular, it identifies several families of facet defining inequalities for this polytope. Some of these inequalities are related to facets of the ordinary TS polytope, others to facets of the knapsack polytope. They can be used in algorithms for the PCTSP either as cutting planes or as ingredients of a Lagrangean optimand.
---
paper_title: New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen

paper_content:

We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the number of brushes that can be sold in that city. What is the best route to take to sell the quota while traveling the least distance possible? Notice that unlike the standard traveling salesman problem, not only do we need to figure out the order in which to visit the cities, but we must decide the more fundamental question: which cities do we want to visit? ::: In this paper we give the first approximation algorithm having a polylogarithmic performance guarantee for this problem, as well as for the slightly more general "prize-collecting traveling salesman problem" (PCTSP) of Balas, and a variation we call the "bank robber problem" (also called the "orienteering problem" by Golden, Levi, and Vohra). We do this by providing an O(log2 k) approximation to the somewhat cleaner k-MST problem which is defined as follows. Given an undirected graph on n nodes with nonnegative edge weights and an integer $k \leq n$, find the tree of least weight that spans k vertices. (If desired, one may specify in the problem a "root vertex" that must be in the tree as well.) Our result improves on the previous best bound of $O(\sqrt{k})$ of Ravi et al.
---
paper_title: Traveling salesman problems with profits

paper_content:

Traveling salesman problems with profits (TSPs with profits) are a generalization of the traveling salesman problem (TSP), where it is not necessary to visit all vertices. A profit is associated with each vertex. The overall goal is the simultaneous optimization of the collected profit and the travel costs. These two optimization criteria appear either in the objective function or as a constraint. In this paper, a classification of TSPs with profits is proposed, and the existing literature is surveyed. Different classes of applications, modeling approaches, and exact or heuristic solution techniques are identified and compared. Conclusions emphasize the interest of this class of problems, with respect to applications as well as theoretical results.
---
paper_title: An exact epsilon-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits

paper_content:

This paper describes an exact [epsilon]-constraint method for bi-objective combinatorial optimization problems with integer objective values. This method tackles multi-objective optimization problems by solving a series of single objective subproblems, where all but one objectives are transformed into constraints. We show in this paper that the Pareto front of bi-objective problems can be efficiently generated with the [epsilon]-constraint method. Furthermore, we describe heuristics based on information gathered from previous subproblems that significantly speed up the method. This approach is used to find the exact Pareto front of the Traveling Salesman Problem with Profits, a variant of the Traveling Salesman Problem in which a profit or prize value is associated with each vertex. The goal here is to visit a subset of vertices while addressing two conflicting objectives: maximize the collected prize and minimize the travel costs. We report the first exact results for this problem on instances derived from classical Vehicle Routing and Traveling Salesman Problem instances with up to 150 vertices. Results on approximations of the Pareto front obtained from a variant of our exact algorithm are also reported.
---
paper_title: On prize-collecting tours and the asymmetric travelling salesman problem

paper_content:

We consider a variant of the Travelling Salesman Problem which is to determine a tour visiting each vertex in the graph at most at one time; if a vertex is left unrouted a given penalty has to be paid. The objective function is to find a balance between these penalities and the cost of the tour. We call this problem the Profitable Tour Problem (PTP). If, in addition, each vertex is associated with a prize and there is a knapsack constraint which guarantees that a sufficiently large prize is collected, we have the well-known Prize-collecting Travelling Salesman Problem (PCTSP). In this paper we summarize the main results presented in the literature, then we give lower bounds for the asymmetric version of PTP and PCTSP. Moreover, we show, through computational experiments, that large size instances of the asymmetric PTP can be solved exactly.
---
paper_title: A 2 + ε approximation algorithm for the k-MST problem

paper_content:

For any ɛ > 0 we give a (2 + ɛ)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [10] the algorithm extends to a (2 + ɛ)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality.
---
paper_title: A general approximation technique for constrained forest problems

paper_content:

We present a general approximation technique for a large class of graph problems. Our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum spanning tree, minimum-weight perfect matching, traveling salesman and Steiner tree problems. Our technique produces approximation algorithms that run in O ( n 2 log n ) time and come within a factor of 2 of optimal for most of these problems. For instance, we obtain a 2-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. Our running time of O ( n 2 log n ) time compares favorably with the best strongly polynomial exact algorithms running in O ( n 3 ) time for dense graphs. A similar result is obtained for the 2-matching problem and its variants.We also derive the first approximation algorithms for many NP-complete problems, including the non-fixed point-to-point connection problem, the exact path partitioning problem and complex location-design problems. Moreover, for the prize-collecting traveling salesman or Steiner tree problems, we obtain 2-approximation algorithms, therefore improving the previously best-known performance guarantees of 2.5 and 3, respectively [4].
---
paper_title: A note on the prize collecting traveling salesman problem

paper_content:

We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.
---
paper_title: TSPLIB—A Traveling Salesman Problem Library

paper_content:

This paper contains the description of a traveling salesman problem library (TSPLIB) which is meant to provide researchers with a broad set of test problems from various sources and with various properties. For every problem a short description is given along with known lower and upper bounds. Several references to computational tests on some of the problems are given. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
---
paper_title: A recursive greedy algorithm for walks in directed graphs

paper_content:

Given an arc-weighted directed graph G = (V, A, /spl lscr/) and a pair of nodes s, t, we seek to find an s-t walk of length at most B that maximizes some given function f of the set of nodes visited by the walk. The simplest case is when we seek to maximize the number of nodes visited: this is called the orienteering problem. Our main result is a quasi-polynomial time algorithm that yields an O(log OPT) approximation for this problem when f is a given submodular set function. We then extend it to the case when a node v is counted as visited only if the walk reaches v in its time window [R(v), D(v)]. We apply the algorithm to obtain several new results. First, we obtain an O(log OPT) approximation for a generalization of the orienteering problem in which the profit for visiting each node may vary arbitrarily with time. This captures the time window problem considered earlier for which, even in undirected graphs, the best approximation ratio known [Bansal, N et al. (2004)] is O(log/sup 2/ OPT). The second application is an O(log/sup 2/ k) approximation for the k-TSP problem in directed graphs (satisfying asymmetric triangle inequality). This is the first non-trivial approximation algorithm for this problem. The third application is an O(log/sup 2/ k) approximation (in quasi-poly time) for the group Steiner problem in undirected graphs where k is the number of groups. This improves earlier ratios (Garg, N et al.) by a logarithmic factor and almost matches the inapproximability threshold on trees (Halperin and Krauthgamer, 2003). This connection to group Steiner trees also enables us to prove that the problem we consider is hard to approximate to a ratio better than /spl Omega/(log/sup 1-/spl epsi// OPT), even in undirected graphs. Even though our algorithm runs in quasi-poly time, we believe that the implications for the approximability of several basic optimization problems are interesting.
---
paper_title: Privatized rural postman problems

paper_content:

In this work we analyze the privatized rural postman problem which is the edge version of the traveling salesman problems with profits.The problem is defined on a undirected graph G(V, E) with a distinguished vertex d, called the Depot. There are two non-negative real functions on the edge set E, which define the value of a cycle in G: one is the profit function, b, and the other one is the cost function, c. They have different meanings when a cycle C traverses an edge e (possibly more than once), because we pay a cost ce every time e is traversed, but we collect the profit be only the first time e is traversed. The privatized rural postman problem is to find a cycle C*, passing through d and not necessarily simple, which maximizes the sum of the values of the edges traversed in C*. That is, maxC {Σe∈C (be - teCe)} where te is the number of times that edge e is traversed in C.We study some properties of the problem: we show that it is NP-hard, its relation with known and new problems, and special cases with good algorithms. We also analyze several integer linear systems of inequalities, which define the polyhedral structure of the problem, and we give dominance and preprocessing conditions. We finish with some remarks and comments about future research.
---
paper_title: An Optimal Algorithm for the Orienteering Tour Problem

paper_content:

Orienteering is a sport in which a competitor selects a path from a start to a destination, visiting control points along the path. Each control point has an associated score, and the travel between control points involves a certain cost. The problem is to select a set of control points to visit, so that the total score is maximized subject to a budget constraint on total cost. Several versions of this problem exist. In the version considered in this research, the start and the destination are the same, and the problem is to construct a subtour of the set of control points. The orienteering problem is a variant of the traveling salesman problem, and arises in vehicle routing and production scheduling situations. This problem has been shown to be NP-hard in the literature. We develop an optimal algorithm to solve this problem, using Lagrangean relaxation within a branch-and-bound framework. The Lagrangean relaxation is solved by a degree-constrained spanning tree procedure. Characteristics of the Lagrangea...
---
paper_title: The orienteering problem in the plane revisited

paper_content:

We consider the orienteering problem: Given a set P of n points in the plane, a starting point r ∈ P, and a length constraint B, one needs to find a tour starting at r that visits as many points of P as possible and of length not exceeding B. We present a (1−e)-approximation algorithm for this problem that runs in nO(1/e) time, and visits at least (1−e)kopt points of P, where kopt is the number of points visited by the optimal solution. This is the first polynomial time approximation scheme (PTAS) for this problem. The algorithm also works in higher dimensions.
---
paper_title: New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen

paper_content:

We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the number of brushes that can be sold in that city. What is the best route to take to sell the quota while traveling the least distance possible? Notice that unlike the standard traveling salesman problem, not only do we need to figure out the order in which to visit the cities, but we must decide the more fundamental question: which cities do we want to visit? ::: In this paper we give the first approximation algorithm having a polylogarithmic performance guarantee for this problem, as well as for the slightly more general "prize-collecting traveling salesman problem" (PCTSP) of Balas, and a variation we call the "bank robber problem" (also called the "orienteering problem" by Golden, Levi, and Vohra). We do this by providing an O(log2 k) approximation to the somewhat cleaner k-MST problem which is defined as follows. Given an undirected graph on n nodes with nonnegative edge weights and an integer $k \leq n$, find the tree of least weight that spans k vertices. (If desired, one may specify in the problem a "root vertex" that must be in the tree as well.) Our result improves on the previous best bound of $O(\sqrt{k})$ of Ravi et al.
---
paper_title: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

paper_content:

We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed <italic>c</italic> > 1 and given any <italic>n</italic> nodes in <inline-equation><f><sc>R</sc></f> </inline-equation><supscrpt>2</supscrpt>, a randomized version of the scheme finds a (1 + 1/<italic>c</italic>)-approximation to the optimum traveling salesman tour in <italic>O(n</italic>(log <italic>n</italic>)<supscrpt><italic>O(c)</italic>)</supscrpt> time. When the nodes are in <inline-equation><f><sc>R</sc></f> </inline-equation><italic>d</italic>, the running time increases to <italic>O(n</italic>(log <italic>n</italic>)<supscrpt>(O(<inline-equation><f><rad><rcd>d</rcd></rad></f> </inline-equation></supscrpt>c))<supscrpt>d-1</supscrpt>). For every fixed <italic>c, d</italic> the running time is <italic>n</italic> • poly(log<italic>n</italic>), that is <italic>nearly linear</italic> in <italic>n</italic>. The algorithmm can be derandomized, but this increases the running time by a factor <italic>O(n<supscrpt>d</supscrpt></italic>). The previous best approximation algorithm for the problem (due to Christofides) achieves a 3/2-aproximation in polynomial time. ::: We also give similar approximation schemes for some other NP-hard Euclidean problems: Minimum Steiner Tree, <italic>k</italic>-TSP, and <italic>k</italic>-MST. (The running times of the algorithm for <italic>k</italic>-TSP and <italic>k</italic>-MST involve an additional multiplicative factor <italic>k</italic>.) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. We also give efficient approximation schemes for Euclidean Min-Cost Matching, a problem that can be solved exactly in polynomial time. ::: All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as <inline-equation><f>ℓ</f> </inline-equation><subscrpt><italic>p</italic></subscrpt> for <italic>p</italic> ≥ 1 or other Minkowski norms). They also have simple parallel (i.e., NC) implementations.
---
paper_title: A tabu search heuristic for the undirected selective travelling salesman problem

paper_content:

The undirected Selective Travelling Salesman Problem (STSP) is defined on a graph G=(V, E) with positive profits associated with vertices, and distances associated with edges. The STSP consists of determining a maximal profit Hamiltonian cycle over a subset of V whose length does not exceed a preset limit L. We describe a tabu search (TS) heuristic for this problem. The algorithm iteratively inserts clusters of vertices in the current tour or removes a chain of vertices. Tests performed on randomly generated instances with up to 300 vertices show that the algorithm consistently yields near-optimal solutions.
---
paper_title: The orienteering problem: A survey

paper_content:

During the last decade, a number of challenging applications in logistics, tourism and other fields were modelled as orienteering problems (OP). In the orienteering problem, a set of vertices is given, each with a score. The goal is to determine a path, limited in length, that visits some vertices and maximises the sum of the collected scores. In this paper, the literature about the orienteering problem and its applications is reviewed. The OP is formally described and many relevant variants are presented. All published exact solution approaches and (meta) heuristics are discussed and compared. Interesting open research questions concerning the OP conclude this paper.
---
paper_title: A multifaceted heuristic for the orienteering problem

paper_content:

The orienteering problem involves the selection of a path between an origin and a destination which maximizes total score subject to a time restriction. In previous work we presented an effective heuristic for this NP-hard problem that outperformed other heuristics from the literature. In this article we describe and test a significantly improved procedure. The new procedure is based on four concepts—center of gravity, randomness, subgravity, and learning. These concepts combine to yield a procedure which is much faster and which results in more nearly optimal solutions than previous procedures.
---
paper_title: An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem

paper_content:

We present a randomized O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem (ATSP). This provides the first asymptotic improvement over the long-standing Θ(log n)-approximation bound stemming from the work of Frieze et al. (1982) [Frieze AM, Galbiati G, Maffioki F (1982) On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12(1):23–39]. The key ingredient of our approach is a new connection between the approximability of the ATSP and the notion of so-called thin trees. To exploit this connection, we employ maximum entropy rounding—a novel method of randomized rounding of LP relaxations of optimization problems. We believe that this method might be of independent interest.
---
paper_title: Approximation algorithms for deadline-TSP and vehicle routing with time-windows

paper_content:

Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible by their deadlines. We also consider the more general Vehicle Routing with Time-Windows problem, in which each node v also has a release-time R(v) and the goal is to visit as many nodes as possible within their "time-windows" [R(v),D(v)]. No good approximations were known previously for these problems on general metric spaces. We give an O(logn) approximation algorithm for Deadline-TSP, and extend this algorithm to an O(log2n) approximation for the Time-Window problem. We also give a bicriteria approximation algorithm for both problems: Given an e>0, our algorithm produces a (1/e) approximation, while exceeding the deadlines by a factor of 1+e. We use as a subroutine for these results a constant-factor approximation that we develop for a generalization of the orienteering problem in which both the start and the end nodes of the path are fixed. In the process, we give a 3-approximation to the orienteering problem, improving on the previously best known 4-approximation of [6].
---
paper_title: Customer Selection and Profit Maximization in Vehicle Routing Problems

paper_content:

An article of manufacture comprising a pharmaceutical radioactive capsule formed essentially of a non-toxic, water soluble material adapted to being ingested and rapidly disintegrating on contact with fluids of the gastro-intestinal tract, and having a filler material supporting a pharmaceutically useful radioactive compound absorbable from the gastro-intestinal tract said filler material being supported by said capsule. And a method of filling a pharmaceutical radioactive capsule comprising providing filler material supporting a pharmaceutically useful radioactive compound and transporting said filler material carrying a pharmaceutically useful radioactive compound into the chamber of said capsule.
---
paper_title: Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems

paper_content:

We show that any polygonal subdivision in the plane can be converted into an "m-guillotine" subdivision whose length is at most $(1+{c\over m})$ times that of the original subdivision, for a small constant c. "m-Guillotine" subdivisions have a simple recursive structure that allows one to search for the shortest of such subdivisions in polynomial time, using dynamic programming. In particular, a consequence of our main theorem is a simple polynomial-time approximation scheme for geometric instances of several network optimization problems, including the Steiner minimum spanning tree, the traveling salesperson problem (TSP), and the k-MST problem.
---
paper_title: The Directed Orienteering Problem

paper_content:

This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directed k-TSP problem: given an asymmetric metric (V,d), a root r∈V and a target k≤|V|, compute the minimum length tour that contains r and at least k other vertices. We present a polynomial time $O(\frac{\log^{2} n}{\log\log n}\cdot\log k)$ -approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an $O(\frac{\log^{2} n}{\log\log n})$ -approximation algorithm for the directed orienteering problem. This answers positively, the question of poly-logarithmic approximability of directed orienteering, an open problem from Blum et al. (SIAM J. Comput. 37(2):653–670, 2007). The previously best known results were quasi-polynomial time algorithms with approximation guarantees of O(log 2 k) for directed k-TSP, and O(log n) for directed orienteering (Chekuri and Pal in IEEE Symposium on Foundations in Computer Science, pp. 245–253, 2005). Using the algorithm for directed orienteering within the framework of Blum et al. (SIAM J. Comput. 37(2):653–670, 2007) and Bansal et al. (ACM Symposium on Theory of Computing, pp. 166–174, 2004), we also obtain poly-logarithmic approximation algorithms for the directed versions of discounted-reward TSP and vehicle routing problem with time-windows.
---
paper_title: The Orienteering Problem

paper_content:

Orienteering is a sport in which start and end points are specified along with other locations. These other locations have associated scores. Competitors seek to visit, in a fixed amount of time, a subset of these locations on the way from the start point to the end point in order to maximize the total score. An effective center-of-gravity heuristic is presented that outperforms heuristics from the literature.
---
paper_title: Approximation algorithms for orienteering and discounted-reward TSP

paper_content:

In this paper, we give the first constant-factor approximation algorithm for the rooted orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot navigation. In both problems, we are given a graph with lengths on edges and prizes (rewards) on nodes, and a start node s. In the orienteering problem, the goal is to find a path that maximizes the reward collected, subject to a hard limit on the total length of the path. In the Discounted-Reward TSP, instead of a length limit we are given a discount factor /spl gamma/, and the goal is to maximize total discounted reward collected, where reward for a node reached at time t is discounted by /spl gamma//sup t/. This is similar to the objective considered in Markov decision processes (MDPs) except we only receive a reward the first time a node is visited. We also consider tree and multiple-path variants of these problems and provide approximations for those as well. Although the unrooted orienteering problem, where there is no fixed start node s, has been known to be approximable using algorithms for related problems such as k-TSP (in which the amount of reward to be collected is fixed and the total length is approximately minimized), ours is the first to approximate the rooted question, solving an open problem based on B. Awerbuch et al. (1999) and E.M. Arkin (1998).
---
paper_title: An efficient four-phase heuristic for the generalized orienteering problem

paper_content:

Orienteering is a sport in which a competitor constructs a path from a start to a destination, visiting control points along the path. Each control point has a score (prize) associated with it, and there is a known amount of time (cost) for travel between control points. The problem is to select a path from the origin to the destination that maximizes the total prize such that the total cost of the path is less than a prescribed value. Applications of this problem are several, and arise in vehicle routing and production scheduling situations. This problem has been shown to be NP-hard, and several heuristics have been proposed in the literature. All these heuristics assume the cost function to be Euclidean, and exploit the underlying geometry. In this research, we consider general cost functions, and develop an efficient four-phase heuristic to solve the problem. The four phases are termed vertex insertion, cost improvement, vertex deletion and maximal insertions, respectively. The four phases are integrated within an algorithmic framework with five control parameters to guide the search process. The algorithm has been tested extensively, and has been evaluated against the heuristics from the literature for Euclidean cost functions and an exact procedure for general cost functions. The computational results show that the algorithm results in near-optimal solutions, and its computational requirements are minimal. We conclude from this research that the proposed algorithm is viable and efficient for solving practical problems with arbitrary cost functions.
---
paper_title: Improved algorithms for orienteering and related problems

paper_content:

In this article, we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. The point to point-orienteering problem is the following: Given an edge-weighted graph <i>G</i>=(<i>V, E</i>) (directed or undirected), two nodes <i>s, t</i> ∈ <i>V</i> and a time limit <i>B</i>, find an <i>s</i>-<i>t</i> <i>walk</i> in <i>G</i> of total length at most <i>B</i> that maximizes the number of distinct nodes visited by the walk. This problem is closely related to tour problems such as TSP as well as network design problems such as <i>k</i>-MST. Orienteering with <i>time-windows</i> is the more general problem in which each node <i>v</i> has a specified time-window [<i>R</i>(<i>v</i>), <i>D</i>(<i>v</i>)] and a node <i>v</i> is counted as visited by the walk only if <i>v</i> is visited during its time-window. We design new and improved algorithms for the orienteering problem and orienteering with time-windows. Our main results are the following: ::: — A (2+ε) approximation for orienteering in undirected graphs, improving upon the 3-approximation of Bansal et al. [2004]. ::: — An <i>O</i>(log<sup>2</sup> OPT) approximation for orienteering in directed graphs, where OPT ≤ <i>n</i> is the number of vertices visited by an optimal solution. Previously, only a quasipolynomial-time algorithm due to Chekuri and Pál [2005] achieved a polylogarithmic approximation (a ratio of <i>O</i>(log OPT)). ::: — Given an α approximation for orienteering, we show an <i>O</i>(α ċ max{log OPT, log <i>l</i><sub>max</sub>/<i>l</i><sub>min</sub>}) approximation for orienteering with time-windows, where <i>l</i><sub>max</sub> and <i>l</i><sub>min</sub> are the lengths of the longest and shortest time-windows respectively.
---
paper_title: Heuristic Methods Applied to Orienteering

paper_content:

A general description of the sport of orienteering in its two forms known as orienteering event and score orienteering event is given. The similarities between the latter and the generalized travelling salesman problem are underlined, and a common mathematical model is deduced. A ‘good’, if not ‘optimal’ solution of the corresponding problem by means of an efficient and computationally feasible method is derived and discussed. This solution is obtained by the use of either of two algorithms based on approximate methods. The two algorithms are given, and their efficiency is tested on a number of illustrative problems. Finally, a comparison between the two forms of the sport of orienteering is made.
---
paper_title: A fast and effective heuristic for the orienteering problem

paper_content:

Abstract In the orienteering problem, start and end points are specified along with other locations which have associated scores. Given a fixed amount of time, the goal is to determine a path from the start point to the end point through a subset of locations in order to maximize the total path score. In this paper, a fast and extremely effective heuristic is presented and tested on 67 problems taken from the literature and 40 new test problems. The computational results are presented in detail.
---
paper_title: Using artificial neural networks to solve the orienteering problem

paper_content:

In the orienteering problem, we are given a transportation network in which a start point and an end point are specified. Other points have associated scores. Given a fixed amount of time, the goal is to determine a path from start to end through a subset of locations in order to maximize the total path score. This problem has received a considerable amount of attention in the last ten years. The traveling salesman problem is a variant of the orienteering problem. This paper applies a modified, continuous Hopfield neural network to attack this NP-hard optimization problem. In it, we design an effective energy function and learning algorithm. Unlike some applications of neural networks to optimization problems, this approach is shown to perform quite well.
---
paper_title: The selective travelling salesman problem

paper_content:

Abstract Given a weighted graph with profits associated with the vertices, the selective travelling salesman problem (or orienteering problem) consists of selecting a simple circuit of maximal total profit, whose length does not exceed a prespecified bound. This paper provides integer linear programming formulations for the problem. Upper and lower bounds are then derived and embedded in exact enumerative algorithms. Computational results are reported.
---
paper_title: A recursive greedy algorithm for walks in directed graphs

paper_content:

Given an arc-weighted directed graph G = (V, A, /spl lscr/) and a pair of nodes s, t, we seek to find an s-t walk of length at most B that maximizes some given function f of the set of nodes visited by the walk. The simplest case is when we seek to maximize the number of nodes visited: this is called the orienteering problem. Our main result is a quasi-polynomial time algorithm that yields an O(log OPT) approximation for this problem when f is a given submodular set function. We then extend it to the case when a node v is counted as visited only if the walk reaches v in its time window [R(v), D(v)]. We apply the algorithm to obtain several new results. First, we obtain an O(log OPT) approximation for a generalization of the orienteering problem in which the profit for visiting each node may vary arbitrarily with time. This captures the time window problem considered earlier for which, even in undirected graphs, the best approximation ratio known [Bansal, N et al. (2004)] is O(log/sup 2/ OPT). The second application is an O(log/sup 2/ k) approximation for the k-TSP problem in directed graphs (satisfying asymmetric triangle inequality). This is the first non-trivial approximation algorithm for this problem. The third application is an O(log/sup 2/ k) approximation (in quasi-poly time) for the group Steiner problem in undirected graphs where k is the number of groups. This improves earlier ratios (Garg, N et al.) by a logarithmic factor and almost matches the inapproximability threshold on trees (Halperin and Krauthgamer, 2003). This connection to group Steiner trees also enables us to prove that the problem we consider is hard to approximate to a ratio better than /spl Omega/(log/sup 1-/spl epsi// OPT), even in undirected graphs. Even though our algorithm runs in quasi-poly time, we believe that the implications for the approximability of several basic optimization problems are interesting.
---
paper_title: Maximum coverage problem with group budget constraints and applications

paper_content:

We study a variant of the maximum coverage problem which we label the maximum coverage problem with group budget constraints (MCG). We are given a collection of sets \({\cal S} = \{S_1, S_2, \ldots, S_m\}\) where each set S i is a subset of a given ground set X. In the maximum coverage problem the goal is to pick k sets from \({\cal S}\) to maximize the cardinality of their union. In the MCG problem \({\cal S}\) is partitioned into groupsG 1, G 2, ..., G l. The goal is to pick k sets from \({\cal S}\) to maximize the cardinality of their union but with the additional restriction that at most one set be picked from each group. We motivate the study of MCG by pointing out a variety of applications. We show that the greedy algorithm gives a 2-approximation algorithm for this problem which is tight in the oracle model. We also obtain a constant factor approximation algorithm for the cost version of the problem. We then use MCG to obtain the first constant factor approximation algorithms for the following problems: (i) multiple depot k-traveling repairmen problem with covering constraints and (ii) orienteering problem with time windows when the number of time windows is a constant.
---
paper_title: Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems

paper_content:

Constant-factor, polynomial-time approximation algorithms are presented for two variations of the traveling salesman problem with time windows. In the first variation, the traveling repairman problem, the goal is to find a tour that visits the maximum possible number of locations during their time windows. In the second variation, the speeding deliveryman problem, the goal is to find a tour that uses the minimum possible speedup to visit all locations during their time windows. For both variations, the time windows are of unit length, and the distance metric is based on a weighted, undirected graph. Algorithms with improved approximation ratios are given for the case when the input is defined on a tree rather than a general graph. The algorithms are also extended to handle time windows whose lengths fall in any bounded range.
---
paper_title: New dynamic programming algorithms for the resource constrained elementary shortest path problem

paper_content:

The resource constrained elementary shortest path problem (RCESPP) arises as a pricing subproblem in branch-and-price algorithms for vehicle-routing problems with additional constraints. We address the optimization of the RCESPP and we present and compare three methods. The first method is a well-known exact dynamic-programming algorithm improved by new ideas, such as bidirectional search with resource-based bounding. The second method consists in a branch-and-bound algorithm, where lower bounds are computed by dynamic-programming with state-space relaxation; we show how bounded bidirectional search can be adapted to state-space relaxation and we present different branching strategies and their hybridization. The third method, called decremental state-space relaxation, is a new one; exact dynamic-programming and state-space relaxation are two special cases of this new method. The experimental comparison of the three methods is definitely favorable to decrement state-space relaxation. Computational results are given for different kinds of resources, arising from the capacitated vehicle-routing problem, the vehicle-routing problem with distribution and collection, and the vehicle-routing problem with capacities and time windows. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008
---
paper_title: Relationships between nondeterministic and deterministic tape complexities

paper_content:

The amount of storage needed to simulate a nondeterministic tape bounded Turingmachine on a deterministic Turing machine is investigated. Results include the following: Theorem. A nondeterministic L(n)-tape bounded Turing machine can be simulated by a deterministic [L(n)]^2-tape bounded Turing machine, provided L(n)>=log"2n. Computations of nondeterministic machines are shown to correspond to threadings of certain mazes. This correspondence is used to produce a specific set, namely the set of all codings of threadable mazes, such that, if there is any set which distinguishes nondeterministic tape complexity classes from deterministic tape complexity classes, then this is one such set.
---
paper_title: Special cases of traveling salesman and repairman problems with time windows

paper_content:

Consider a complete directed graph in which each arc has a given length. There is a set ofjobs, each job i located at some node of the graph, with an associated processing time hi, and whose execution has to start within a prespecified time window [r;, di]. We have a single server that can move on the arcs of the graph, at unit speed, and that has to execute all of the jobs within their respective time windows. We consider the following two problems: (a) minimize the time by which all jobs are executed (traveling salesman problem) and (b) minimize the sum of the waiting times of the jobs (traveling repairman problem). We focus on the following two special cases: (a) The jobs are located on a line and (b) the number of nodes of the graph is bounded by some integer constant B. Furthermore, we consider in detail the special cases where (a) all of the processing times are 0, (b) all of the release times ri are 0, and (c) all of the deadlines di are infinite. For many of the resulting problem combinations, we settle their complexity either by establishing NP-completeness or by presenting polynomial (or pseudopolynomial) time algorithms. Finally, we derive algorithms for the case where, for any time t, the number of jobs that can be executed at that time is bounded.
---
paper_title: The orienteering problem: A survey

paper_content:

During the last decade, a number of challenging applications in logistics, tourism and other fields were modelled as orienteering problems (OP). In the orienteering problem, a set of vertices is given, each with a score. The goal is to determine a path, limited in length, that visits some vertices and maximises the sum of the collected scores. In this paper, the literature about the orienteering problem and its applications is reviewed. The OP is formally described and many relevant variants are presented. All published exact solution approaches and (meta) heuristics are discussed and compared. Interesting open research questions concerning the OP conclude this paper.
---
paper_title: The Orienteering Problem with Time Windows

paper_content:

The orienteering problem with time windows, denoted by OPTW, belongs to a class of routeing and scheduling problems that arise in physical distribution. It may be modelled as a problem on a graph. It considers a set of nodes (customers), each with an associated profit and service duration (time window), and a set of arcs, each with an associated travel time. The objective of the problem is to construct an acyclic path beginning at a specified origin and ending at a specified destination that maximizes the total profit while observing time window constraints on all nodes and not exceeding a designated time limit. The problem is classified as NP-hard and, thus, an exact algorithm that executes in reasonable computational time is unlikely to exist. Since the problem is highly-constrained, we were able to develop a heuristic (referred to as the ‘tree’ heuristic) based upon an exhaustive search of the feasible solution space. The tree heuristic systematically generates a list of feasible paths and then selects the most profitable path from the list. In comparison with an insertion heuristic, the tree heuristic was found to produce improved values of total profit for heavily-constrained, modest-sized problems with reasonable computational effort.
---
paper_title: Approximation algorithms for deadline-TSP and vehicle routing with time-windows

paper_content:

Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible by their deadlines. We also consider the more general Vehicle Routing with Time-Windows problem, in which each node v also has a release-time R(v) and the goal is to visit as many nodes as possible within their "time-windows" [R(v),D(v)]. No good approximations were known previously for these problems on general metric spaces. We give an O(logn) approximation algorithm for Deadline-TSP, and extend this algorithm to an O(log2n) approximation for the Time-Window problem. We also give a bicriteria approximation algorithm for both problems: Given an e>0, our algorithm produces a (1/e) approximation, while exceeding the deadlines by a factor of 1+e. We use as a subroutine for these results a constant-factor approximation that we develop for a generalization of the orienteering problem in which both the start and the end nodes of the path are fixed. In the process, we give a 3-approximation to the orienteering problem, improving on the previously best known 4-approximation of [6].
---
paper_title: State-space relaxation procedures for the computation of bounds to routing problems

paper_content:

An RC active filter circuit wherein the active elements of the circuit are realized by controllable transconductance amplifiers. The transfer response of the filter circuit is readily variable by altering signals applied to the control terminals of the transconductance amplifiers.
---
paper_title: Improved algorithms for orienteering and related problems

paper_content:

In this article, we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. The point to point-orienteering problem is the following: Given an edge-weighted graph <i>G</i>=(<i>V, E</i>) (directed or undirected), two nodes <i>s, t</i> ∈ <i>V</i> and a time limit <i>B</i>, find an <i>s</i>-<i>t</i> <i>walk</i> in <i>G</i> of total length at most <i>B</i> that maximizes the number of distinct nodes visited by the walk. This problem is closely related to tour problems such as TSP as well as network design problems such as <i>k</i>-MST. Orienteering with <i>time-windows</i> is the more general problem in which each node <i>v</i> has a specified time-window [<i>R</i>(<i>v</i>), <i>D</i>(<i>v</i>)] and a node <i>v</i> is counted as visited by the walk only if <i>v</i> is visited during its time-window. We design new and improved algorithms for the orienteering problem and orienteering with time-windows. Our main results are the following: ::: — A (2+ε) approximation for orienteering in undirected graphs, improving upon the 3-approximation of Bansal et al. [2004]. ::: — An <i>O</i>(log<sup>2</sup> OPT) approximation for orienteering in directed graphs, where OPT ≤ <i>n</i> is the number of vertices visited by an optimal solution. Previously, only a quasipolynomial-time algorithm due to Chekuri and Pál [2005] achieved a polylogarithmic approximation (a ratio of <i>O</i>(log OPT)). ::: — Given an α approximation for orienteering, we show an <i>O</i>(α ċ max{log OPT, log <i>l</i><sub>max</sub>/<i>l</i><sub>min</sub>}) approximation for orienteering with time-windows, where <i>l</i><sub>max</sub> and <i>l</i><sub>min</sub> are the lengths of the longest and shortest time-windows respectively.
---
paper_title: Decremental state space relaxation strategies and initialization heuristics for solving the Orienteering Problem with Time Windows with dynamic programming

paper_content:

We present an exact optimization algorithm for the Orienteering Problem with Time Windows (OPTW). The algorithm is based on bi-directional and bounded dynamic programming with decremental state space relaxation. We compare different strategies proposed in the literature to guide decremental state space relaxation: our experiments on instances derived from the literature show that there is no dominance between these strategies. We also propose a new heuristic technique to initialize the critical vertex set and we provide experimental evidence of its effectiveness.
---
paper_title: Approximation Algorithms for Time-Dependent Orienteering

paper_content:

The time-dependent orienteering problem is dual to the timedependent traveling salesman problem. It consists in visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time. ::: ::: 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.
---
paper_title: Model and Algorithm for Time-Dependent Team Orienteering Problem

paper_content:

In the team orienteering problem (TOP) a set of locations is given, each with a score. The goal is to determine a fixed number of routes, limited in length, that visit some locations and maximize the sum of the collected scores. The team orienteering problem is often used as a starting point for modeling many combinatorial optimization problems. This paper studies the time-dependent team orienteering problem considering the travel cost varying with time and visiting time constraints. After a mixed integer programming model is proposed, a novel optimal dynamic labeling algorithm is designed based on the idea of network planning and dynamic programming. Finally, a numerical example is presented to show the validity and feasibility of this algorithm.
---
paper_title: Study on the Time-Dependent Orienteering Problem

paper_content:

In the orienteering problem (OP) a set of locations is given, each with a score. The goal is to determine a route, limited in length, that visits some locations and maximize the sum of the collected scores. The orienteering problem is often used as a starting point for modeling many combinatorial optimization problems. This paper studies the time-dependent orienteering problem taking into account the travel cost varying with time and stay time constraints. After a mixed integer programming model is proposed, a novel optimal pre-node labeling algorithm is designed based on the idea of network planning and dynamic programming. Finally, a numerical example is presented to show the validity and feasibility of this algorithm.
---
paper_title: On the approximability of an interval scheduling problem

paper_content:

In this paper we consider a general interval scheduling problem. The problem is a natural generalization of finding a maximum independent set in an interval graph. We show that, unless =, this maximization problem cannot be approximated in polynomial time within arbitrarily good precision. On the other hand, we present a simple greedy algorithm that delivers a solution with a value of at least 1/2 times the value of an optimal solution. Finally, we investigate the quality of an LP-relaxation of a formulation for the problem, by establishing an upper bound on the ratio between the value of the LP-relaxation and the value of an optimal solution. Copyright © 1999 John Wiley & Sons, Ltd.
---
paper_title: On the approximability of an interval scheduling problem

paper_content:

In this paper we consider a general interval scheduling problem. The problem is a natural generalization of finding a maximum independent set in an interval graph. We show that, unless =, this maximization problem cannot be approximated in polynomial time within arbitrarily good precision. On the other hand, we present a simple greedy algorithm that delivers a solution with a value of at least 1/2 times the value of an optimal solution. Finally, we investigate the quality of an LP-relaxation of a formulation for the problem, by establishing an upper bound on the ratio between the value of the LP-relaxation and the value of an optimal solution. Copyright © 1999 John Wiley & Sons, Ltd.
---
paper_title: Time-dependent personal tour planning and scheduling in metropolises

paper_content:

This paper addresses the problem of time-dependent tour planning in complex and large urban areas that may be of importance for different groups of people. The problem is determination of chronological sequences of attractive points during a specific period via several modes of transportation system. The proposed approach adopted a nested architecture in which tour planning routine calls multimodal shortest path subroutine to generate an itinerary based on user preferences and restrictions of interesting points. Two adapted genetic algorithms were employed in the engine of both blocks. In these algorithms, chromosomes with variable lengths and particularly defined evolutionary stages are used. The proposed process has been tested over the dataset of city of Tehran. The evaluation consists of preparation of 400 tours with different initial points, start time, and tour durations. It was assumed that just three modes of walking, bus, and subway are used to travel between points of interest. Moreover, some tests are applied to dataset to illustrate the adaptability and time-dependency nature of method. The experimental results and related indices such as optimality ratios show that the proposed algorithm can find optimum tour according to introduced constraints.
---
paper_title: The orienteering problem with variable profits

paper_content:

This article introduces, models, and solves a generalization of the orienteering problem, called the the orienteering problem with variable profits (OPVP). The OPVP is defined on a complete undirected graph G = (V,E), with a depot at vertex 0. Every vertex i∈V \{0} has a profit pi to be collected, and an associated collection parameter αi∈[0, 1]. The vehicle may make a number of “passes,” collecting 100αi percent of the remaining profit at each pass. In an alternative model, the vehicle may spend a continuous amount of time at every vertex, collecting a percentage of the profit given by a function of the time spent. The objective is to determine a maximal profit tour for the vehicle, starting and ending at the depot, and not exceeding a travel time limit. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013
---
paper_title: The orienteering problem with stochastic travel and service times

paper_content:

In this paper, we introduce a variant of the orienteering problem in which travel and service times are stochastic. If a delivery commitment is made to a customer and is completed by the end of the day, a reward is received, but if a commitment is made and not completed, a penalty is incurred. This problem reflects the challenges of a company who, on a given day, may have more customers than it can serve. In this paper, we discuss special cases of the problem that we can solve exactly and heuristics for general problem instances. We present computational results for a variety of parameter settings and discuss characteristics of the solution structure.
---
paper_title: Approximation algorithms for stochastic orienteering

paper_content:

In the Stochastic Orienteering problem, we are given a metric, where each node also has a job located there with some deterministic reward and a random size. (Think of the jobs as being chores one needs to run, and the sizes as the amount of time it takes to do the chore.) The goal is to adaptively decide which nodes to visit to maximize total expected reward, subject to the constraint that the total distance traveled plus the total size of jobs processed is at most a given budget of B. (I.e., we get reward for all those chores we finish by the end of the day). The (random) size of a job is not known until it is completely processed. Hence the problem combines aspects of both the stochastic knapsack problem with uncertain item sizes and the deterministic orienteering problem of using a limited travel time to maximize gathered rewards located at nodes. ::: ::: In this paper, we present a constant-factor approximation algorithm for the best non-adaptive policy for the Stochastic Orienteering problem. We also show a small adaptivity gap---i.e., the existence of a non-adaptive policy whose reward is at least an Ω(1/log log B) fraction of the optimal expected reward---and hence we also get an O(log log B)-approximation algorithm for the adaptive problem. Finally we address the case when the node rewards are also random and could be correlated with the waiting time, and give a non-adaptive policy which is an O(log n logB)-approximation to the best adaptive policy on n-node metrics with budget B.
---
paper_title: Metaheuristics for the bi-objective orienteering problem

paper_content:

In this paper, heuristic solution techniques for the multi-objective orienteering problem are developed. The motivation stems from the problem of planning individual tourist routes in a city. Each point of interest in a city provides different benefits for different categories (e.g., culture, shopping). Each tourist has different preferences for the different categories when selecting and visiting the points of interests (e.g., museums, churches). Hence, a multi-objective decision situation arises. To determine all the Pareto optimal solutions, two metaheuristic search techniques are developed and applied. We use the Pareto ant colony optimization algorithm and extend the design of the variable neighborhood search method to the multi-objective case. Both methods are hybridized with path relinking procedures. The performances of the two algorithms are tested on several benchmark instances as well as on real world instances from different Austrian regions and the cities of Vienna and Padua. The computational results show that both implemented methods are well performing algorithms to solve the multi-objective orienteering problem.
---
paper_title: The orienteering problem with stochastic profits

paper_content:

Given a graph G = (N, E), N representing the set of nodes associated with Normally distributed random profits and E representing the set of edges with associated travel times, we define the Orienteering Problem with Stochastic Profits (OPSP) as the problem of finding a tour that visits a subset of N within a prespecified time limit and maximizes the probability of collecting more than a prespecified target profit level. We develop an exact solution scheme based on a parametric formulation of the problem and present a bi-objective genetic algorithm. We also analyze the characteristics of the problem and test the algorithms computationally. The experimental results identify conditions under which the OPSP results in significant improvements in reaching the target profit when compared with the solution from the deterministic variant of the problem.
---
paper_title: The Effective Application of a New Approach to the Generalized Orienteering Problem

paper_content:

The Orienteering Problem (OP) is an important problem in network optimization in which each city in a network is assigned a score and a maximum-score path from a designated start city to a designated end city is sought that is shorter than a pre-specified length limit. The Generalized Orienteering Problem (GOP) is a generalized version of the OP in which each city is assigned a number of scores for different attributes and the overall function to optimize is a function of these attribute scores. In this paper, the function used was a non-linear combination of attribute scores, making the problem difficult to solve. The GOP has a number of applications, largely in the field of routing. We designed a two-parameter iterative algorithm for the GOP, and computational experiments suggest that this algorithm performs as well as or better than other heuristics for the GOP in terms of solution quality while running faster. Further computational experiments suggest that our algorithm also outperforms the leading algorithm for solving the OP in terms of solution quality while maintaining a comparable solution speed.
---
paper_title: Using artificial neural networks to solve the orienteering problem

paper_content:

In the orienteering problem, we are given a transportation network in which a start point and an end point are specified. Other points have associated scores. Given a fixed amount of time, the goal is to determine a path from start to end through a subset of locations in order to maximize the total path score. This problem has received a considerable amount of attention in the last ten years. The traveling salesman problem is a variant of the orienteering problem. This paper applies a modified, continuous Hopfield neural network to attack this NP-hard optimization problem. In it, we design an effective energy function and learning algorithm. Unlike some applications of neural networks to optimization problems, this approach is shown to perform quite well.
---
paper_title: Using a Genetic Algorithm to Solve the Generalized Orienteering Problem

paper_content:

In this chapter, we use genetic algorithms (GAs) to solve the generalized orienteering problem (GOP). In the orienteering problem (OP), we are given a transportation network in which a start point and an end point are specified, and other points have associated scores. Given a fixed amount of time, the goal is to determine a path from start to end through a subset of the other locations in order to maximize the total path score. In the GOP, each point has a score with respect to a number of attributes (e.g., natural beauty, historical significance, cultural and educational attractions, and business opportunities) and the overall objective function is nonlinear. The GOP is more difficult than the OP, which is itself NP-hard. An effective heuristic using artificial neural networks (ANNs), however, has been designed to solve the GOP. In this chapter, we show that a straightforward GA can yield comparable results.
---
paper_title: A variable neighborhood search method for the orienteering problem with hotel selection

paper_content:

In this paper, we present the orienteering problem with hotel selection (OPHS), an extension of the orienteering problem (OP). In the OPHS, a set of vertices with a score and a set of hotels are given. The goal is to determine a fixed number of connected trips that visits some vertices and maximizes the sum of the collected scores. Each trip is limited in length and should start and end in one of the hotels. We formulate the problem mathematically, explain the differences with related optimization problems and indicate what makes this problem inherently more difficult.
---
paper_title: The Capacitated Team Orienteering and Profitable Tour Problems

paper_content:

In this paper, we study the capacitated team orienteering and profitable tour problems (CTOP and CPTP). The interest in these problems comes from recent developments in the use of the Internet for a better matching of demand and offer of transportation services. We propose exact and heuristic procedures for the CTOP and the CPTP. The computational results show that the heuristic procedures often find the optimal solution and in general cause very limited errors.
---
paper_title: Customer Selection and Profit Maximization in Vehicle Routing Problems

paper_content:

An article of manufacture comprising a pharmaceutical radioactive capsule formed essentially of a non-toxic, water soluble material adapted to being ingested and rapidly disintegrating on contact with fluids of the gastro-intestinal tract, and having a filler material supporting a pharmaceutically useful radioactive compound absorbable from the gastro-intestinal tract said filler material being supported by said capsule. And a method of filling a pharmaceutical radioactive capsule comprising providing filler material supporting a pharmaceutically useful radioactive compound and transporting said filler material carrying a pharmaceutically useful radioactive compound into the chamber of said capsule.
---
paper_title: Iterated local search algorithm based on very large-scale neighborhood for prize-collecting vehicle routing problem

paper_content:

This paper presents a new variant of the vehicle routing problem (VRP), the prize-collecting vehicle routing problem (PCVRP), which is derived from the hot rolling production of the iron and steel industry. One major characteristic of the PCVRP is that the customers need not be visited compulsorily but a prize can be collected from each customer when visited. Besides the capacity constraint, a task completion constraint is introduced and requires that the total demand of the visited customers should be no less than a predetermined amount. The main objective is a linear combination of three objectives: minimization of total distance traveled, minimization of vehicles used, and maximization of prizes collected. An iterated local search algorithm (ILS) based on very large-scale neighborhood (VLSN) using cyclic transfer is proposed for the PCVRP. Computational results of problem instances with up to 100 customers show the algorithm is efficient and effective.
---
paper_title: A Path Relinking approach for the Team Orienteering Problem

paper_content:

This paper introduces a Path Relinking metaheuristic approach for solving the Team Orienteering Problem (TOP), a particular routing problem in which a score is earned for visiting a location. The objective is to maximise the sum of the scores, while not exceeding a time budget T"m"a"x for travelling to the selected locations. In the case of the simple Orienteering Problem (OP), a single route connecting all selected locations should be followed; in TOP m routes are required and the length of each route is restricted to T"m"a"x. A fast and a slow variant of the approach are tested using a large set of test instances from the literature; they are compared to other state-of-the-art approaches. The fast variant achieves an average gap of 0.39% to the best known solutions in 5.0s of calculation time, while the slow variant achieves a 0.04% gap within 272.8s. Moreover, next to achieving most of the best known solutions for many testproblems, the slow variant improved the best known results in five instances.
---
paper_title: Guided local search and its application to the traveling salesman problem

paper_content:

Abstract The Traveling Salesman Problem (TSP) is one of the most famous problems in combinatorial optimization. In this paper, we are going to examine how the techniques of Guided Local Search (GLS) and Fast Local Search (FLS) can be applied to the problem. GLS sits on top of local search heuristics and has as a main aim to guide these procedures in exploring efficiently and effectively the vast search spaces of combinatorial optimization problems. GLS can be combined with the neighborhood reduction scheme of FLS which significantly speeds up the operations of the algorithm. The combination of GLS and FLS with TSP local search heuristics of different eiciency and effectiveness is studied in an effort to determine the dependence of GLS on the underlying local search heuristic used. Comparisons are made with some of the best TSP heuristic algorithms and general optimization techniques which demonstrate the advantages of GLS over alternative heuristic approaches suggested for the problem.
---
paper_title: The team orienteering problem

paper_content:

In the team orienteering problem, start and end points are specified along with other locations which have associated scores. Given a fixed amount of time for each of the M members of the team, the goal is to determine M paths from the start point to the end point through a subset of locations in order to maximize the total score. In this paper, a fast and effective heuristic is presented and tested on 353 problems ranging in size from 21 to 102 points. The computational results are presented in detail.
---
paper_title: Metaheuristics for Tourist Trip Planning

paper_content:

The aim of this paper is to present an overview of metaheuristics used in tourism and to introduce Skewed VNS to solve the team orienteering problem (TOP). Selecting the most interesting points of interest and designing a personalised tourist trip, can be modelled as a TOP with time windows (TOPTW). Guided local search (GLS) and variable neighbourhood search (VNS) are applied to efficiently solve the TOP. Iterated local search (ILS) is implemented to solve the TOPTW. The GLS and VNS algorithms are compared with the best known heuristics and applied on large problem sets. The obtained results are almost of the same quality as the results of these heuristics but the computational time is reduced significantly. For some of the problems VNS calculates new best solutions. The results of the ILS algorithm, applied to large problem sets, have an average gap with the optimal solution of only 2.7%, with much less computational effort.
---
paper_title: A heuristic for the multiple tour maximum collection problem

paper_content:

Abstract The multiple tour maximum collection problem (MTMCP) consists of determining the m optimal time constrained tours which visit a subset of weighted nodes in a graph such that the total weight collected from the subset of nodes is maximized. In this paper, a heuristic for the MTMCP is developed. The results of computational testing reveal that the heuristic has three very attractive features. First, the heuristic will always produce a feasible solution if one exists. Second, the heuristic produces very good solutions. In most cases where the exact solution is known, it produces the optimal solution. And finally, the heuristic has the ability to handle large problems in a very short amount of computation time.
---
paper_title: Discrete particle swarm optimization for the team orienteering problem

paper_content:

Orienteering problem is a well researched routing problem which is a generalization of the traveling salesman problem. Team orienteering problem (TOP) is the extended version of the orienteering problem with more than one member in the team. In this paper the first known discrete particle swarm optimization (DPSO) algorithm has been developed for 2, 3 and 4-member TOP. In the DPSO meta-heuristic novel methods have been introduced for the initial particle generation process. Reduced variable neighborhood search and 2-opt were applied as the local search tools. The efficacy of the algorithm was tested using seven commonly used benchmark problem sets ranging in size from 21 to 102 nodes. The results of the DPSO algorithm were compared against seven other heuristic algorithms that have been developed for TOP. It was concluded that the developed DPSO algorithm for the TOP is competitive and robust across the benchmark problem sets.
---
paper_title: A probabilistic heuristic for a computationally difficult set covering problem

paper_content:

An efficient probabilistic set covering heuristic is presented. The heuristic is evaluated on empirically difficult to solve set covering problems that arise from Steiner triple systems. The optimal solution to only a few of these instances is known. The heuristic provides these solutions as well as the best known solutions to all other instances attempted.
---
paper_title: Approximations for minimum and min-max vehicle routing problems

paper_content:

We consider a variety of vehicle routing problems. The input to a problem consists of a graph G = (N, E) and edge lengths l(e), e ∈ E. Customers located at the vertices have to be visited by a set of vehicles. Two important parameters are k the number of vehicles, and λ the longest distance traveled by a vehicle. We consider two types of problems. (1) Given a bound λ on the length of each path, find a minimum sized collection of paths that cover all the vertices of the graph, or all the edges from a given subset of edges of the input graph. We also consider a variation where it is desired to cover N by a minimum number of stars of length bounded by λ. (2) Given a number k find a collection of k paths that cover either the vertex set of the graph or a given subset of edges. The goal here is to minimize λ, the maximum travel distance. For all these problems we provide constant ratio approximation algorithms and prove their NP-hardness.
---
paper_title: A memetic algorithm for the team orienteering problem

paper_content:

The Team Orienteering Problem (TOP) is a generalization of the Orienteering Problem (OP). A limited number of vehicles is available to visit customers from a potential set. Each vehicle has a predefined running-time limit, and each customer has a fixed associated profit. The aim of the TOP is to maximize the total collected profit. In this paper we propose a simple hybrid Genetic Algorithm (GA) using new algorithms dedicated to the specific scope of the TOP: an Optimal Split procedure for chromosome evaluation and Local Search techniques for mutation. We have called this hybrid method a Memetic Algorithm (MA) for the TOP. Computational experiments conducted on standard benchmark instances clearly show our method to be highly competitive with existing ones, yielding new improved solutions in at least 11 instances.
---
paper_title: An exact algorithm for team orienteering problems

paper_content:

Optimising routing of vehicles constitutes a major logistic stake in many industrial contexts. We are interested here in the optimal resolution of special cases of vehicle routing problems, known as team orienteering problems. In these problems, vehicles are guided by a reward that can be collected from customers, while the length of routes is limited. The main difference with classical vehicle routing problems is that not all customers have to be visited. The solution method we propose here is based on a Branch & Price algorithm. It is, as far as we know, the first exact method proposed for such problems, except for a preliminary work from Gueguen (Methodes de résolution exacte pour problémes de tournées de véhicules. Thése de doctorat, école Centrale Paris 1999) and a work from Butt and Ryan (Comput Oper Res 26(4):427–441 1999). It permits to solve instances with up to 100 customers.
---
paper_title: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

paper_content:

We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed <italic>c</italic> > 1 and given any <italic>n</italic> nodes in <inline-equation><f><sc>R</sc></f> </inline-equation><supscrpt>2</supscrpt>, a randomized version of the scheme finds a (1 + 1/<italic>c</italic>)-approximation to the optimum traveling salesman tour in <italic>O(n</italic>(log <italic>n</italic>)<supscrpt><italic>O(c)</italic>)</supscrpt> time. When the nodes are in <inline-equation><f><sc>R</sc></f> </inline-equation><italic>d</italic>, the running time increases to <italic>O(n</italic>(log <italic>n</italic>)<supscrpt>(O(<inline-equation><f><rad><rcd>d</rcd></rad></f> </inline-equation></supscrpt>c))<supscrpt>d-1</supscrpt>). For every fixed <italic>c, d</italic> the running time is <italic>n</italic> • poly(log<italic>n</italic>), that is <italic>nearly linear</italic> in <italic>n</italic>. The algorithmm can be derandomized, but this increases the running time by a factor <italic>O(n<supscrpt>d</supscrpt></italic>). The previous best approximation algorithm for the problem (due to Christofides) achieves a 3/2-aproximation in polynomial time. ::: We also give similar approximation schemes for some other NP-hard Euclidean problems: Minimum Steiner Tree, <italic>k</italic>-TSP, and <italic>k</italic>-MST. (The running times of the algorithm for <italic>k</italic>-TSP and <italic>k</italic>-MST involve an additional multiplicative factor <italic>k</italic>.) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. We also give efficient approximation schemes for Euclidean Min-Cost Matching, a problem that can be solved exactly in polynomial time. ::: All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as <inline-equation><f>ℓ</f> </inline-equation><subscrpt><italic>p</italic></subscrpt> for <italic>p</italic> ≥ 1 or other Minkowski norms). They also have simple parallel (i.e., NC) implementations.
---
paper_title: The orienteering problem: A survey

paper_content:

During the last decade, a number of challenging applications in logistics, tourism and other fields were modelled as orienteering problems (OP). In the orienteering problem, a set of vertices is given, each with a score. The goal is to determine a path, limited in length, that visits some vertices and maximises the sum of the collected scores. In this paper, the literature about the orienteering problem and its applications is reviewed. The OP is formally described and many relevant variants are presented. All published exact solution approaches and (meta) heuristics are discussed and compared. Interesting open research questions concerning the OP conclude this paper.
---
paper_title: A Greedy Randomised Adaptive Search Procedure for the Team Orienteering Problem

paper_content:

This paper introduces a Greedy Randomised Adaptive Search Procedure (GRASP) for solving the Team Orienteering Problem (TOP). That is a particular routing problem in which a score is earned for visiting a location. The objective is to maximise the sum of the scores of a xed number of routes, while not exceeding a given time budget for each route. The memoryless GRASP approach is extended by adding a long term adaptive memory component, namely a path relinking procedure. Both versions of the approach are tested using a large set of test instances from the literature.
---
paper_title: A guided local search metaheuristic for the team orienteering problem

paper_content:

In the team orienteering problem (TOP) a set of locations is given, each with a score. The goal is to determine a fixed number of routes, limited in length, that visit some locations and maximise the sum of the collected scores. This paper describes an algorithm that combines different local search heuristics to solve the TOP. Guided local search (GLS) is used to improve two of the proposed heuristics. An extra heuristic is added to regularly diversify the search in order to explore more areas of the solution space. The algorithm is compared with the best known heuristics of the literature and applied on a large problem set. The obtained results are almost of the same quality as the results of these heuristics but the computational time is reduced significantly. Applying GLS to solve the TOP appears to be a very promising technique. Furthermore, the usefulness of exploring more areas of the solution space is clearly demonstrated.
---
paper_title: Approximation algorithms for orienteering and discounted-reward TSP

paper_content:

In this paper, we give the first constant-factor approximation algorithm for the rooted orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot navigation. In both problems, we are given a graph with lengths on edges and prizes (rewards) on nodes, and a start node s. In the orienteering problem, the goal is to find a path that maximizes the reward collected, subject to a hard limit on the total length of the path. In the Discounted-Reward TSP, instead of a length limit we are given a discount factor /spl gamma/, and the goal is to maximize total discounted reward collected, where reward for a node reached at time t is discounted by /spl gamma//sup t/. This is similar to the objective considered in Markov decision processes (MDPs) except we only receive a reward the first time a node is visited. We also consider tree and multiple-path variants of these problems and provide approximations for those as well. Although the unrooted orienteering problem, where there is no fixed start node s, has been known to be approximable using algorithms for related problems such as k-TSP (in which the amount of reward to be collected is fixed and the total length is approximately minimized), ours is the first to approximate the rooted question, solving an open problem based on B. Awerbuch et al. (1999) and E.M. Arkin (1998).
---
paper_title: Ants can solve the team orienteering problem

paper_content:

The team orienteering problem (TOP) involves finding a set of paths from the starting point to the ending point such that the total collected reward received from visiting a subset of locations is maximized and the length of each path is restricted by a pre-specified limit. In this paper, an ant colony optimization (ACO) approach is proposed for the team orienteering problem. Four methods, i.e., the sequential, deterministic-concurrent and random-concurrent and simultaneous methods, are proposed to construct candidate solutions in the framework of ACO. We compare these methods according to the results obtained on well-known problems from the literature. Finally, we compare the algorithm with several existing algorithms. The results show that our algorithm is promising.
---
paper_title: A TABU search heuristic for the team orienteering problem

paper_content:

This paper describes a tabu search heuristic for the Team Orienteering Problem (TOP). The TOP is a variant of the well-known Vehicle Routing Problem in which a set of vehicle tours are constructed such that the total collected reward received from visiting a subset of customers is maximized and the length of each vehicle tour is restricted by a pre-specified limit. The tabu search heuristic is embedded in an adaptive memory procedure that alternates between small and large neighborhood stages during the solution improvement phase. Both random and greedy procedures for neighborhood solution generation are employed and infeasible, as well as feasible, solutions are explored in the process. Results from computational experiments conducted on a set of published test problems show that the proposed technique consistently produces high-quality solutions and outperforms other published heuristics tbr the TOP.
---
paper_title: An effective PSO-inspired algorithm for the team orienteering problem

paper_content:

The Team Orienteering Problem (TOP) is a particular vehicle routing problem in which the aim is to maximize the profit gained from visiting customers without exceeding a travel cost/time limit. This paper proposes a new and fast evaluation process for TOP based on an interval graph model and a Particle Swarm Optimization inspired Algorithm (PSOiA) to solve the problem. Experiments conducted on the standard benchmark of TOP clearly show that our algorithm outperforms the existing solving methods. PSOiA reached a relative error of 0.0005% whereas the best known relative error in the literature is 0.0394%. Our algorithm detects all but one of the best known solutions. Moreover, a strict improvement was found for one instance of the benchmark and a new set of larger instances was introduced.
---
paper_title: A fast and effective heuristic for the orienteering problem

paper_content:

Abstract In the orienteering problem, start and end points are specified along with other locations which have associated scores. Given a fixed amount of time, the goal is to determine a path from the start point to the end point through a subset of locations in order to maximize the total path score. In this paper, a fast and extremely effective heuristic is presented and tested on 67 problems taken from the literature and 40 new test problems. The computational results are presented in detail.
---
paper_title: An optimal solution procedure for the multiple tour maximum collection problem using column generation

paper_content:

The Multiple Tour Maximum Collection Problem (MTMCP) is closely related to the classical Traveling Salesman and Vehicle Routing Problems. One major difference with the MTMCP is that it is not possible to visit all of the nodes in the graph in the total time allocated on a given set of tours. However, with the MTMCP, a reward is collected from each node that is visited. The objective of the MTMCP is to determine which nodes to visit on m time-constrained tours for which the total reward collected is maximized. It is assumed that each tour begins and ends at a central depot and that each node can be visited no more than one time, on at most one tour. In this paper, an optimal solution procedure is presented for the MTMCP. This procedure is based on a set-partitioning formulation and makes efficient use of both column generation and constraint branching. Numerical results are presented which show that this optimal procedure can be used to solve problems of realistic size in a reasonable amount of time. ::: ::: Scope and purpose ::: ::: A common assumption of many vehicle routing and scheduling problems is that each customer is to be visited exactly once, on exactly one route (tour). In this paper, we consider a problem where this is not possible. We assume that the routes are constrained in such a way that all of the customers cannot be visited. For example, suppose that we have five 8 hour days to visit customers, but too many customers to visit in this amount of time. ::: ::: In problems where it is possible to visit all customers, the typical objective is to determine the minimum amount of time (or distance) needed to make all of the visits. Conversely, if all of the customers cannot be visited, the main objective is to determine the optimal subset of customers to visit in the time allotted. In this paper we assume that there is a reward which is collected when visiting a customer, and that the problem objective is to maximize the total reward collected.
---
paper_title: Heuristics for the multi-period orienteering problem with multiple time windows

paper_content:

We present the multi-period orienteering problem with multiple time windows (MuPOPTW), a new routing problem combining objective and constraints of the orienteering problem (OP) and team orienteering problem (TOP), constraints from standard vehicle routing problems, and original constraints from a real-world application. The problem itself comes from a real industrial case. Specific route duration constraints result in a route feasibility subproblem. We propose an exact algorithm for this subproblem, and we embed it in a variable neighborhood search method to solve the whole routing problem. We then provide experimental results for this method. We compare them to a commercial solver. We also adapt our method to standard benchmark OP and TOP instances, and provide comparative tables with state-of-the-art algorithms.
---
paper_title: Hybridized evolutionary local search algorithm for the team orienteering problem with time windows

paper_content:

The orienteering problem (OP) consists in finding an elementary path over a subset of vertices. Each vertex is associated with a profit that is collected on the visitor’s first visit. The objective is to maximize the collected profit with respect to a limit on the path’s length. The team orienteering problem (TOP) is an extension of the OP where a fixed number m of paths must be determined. This paper presents an effective hybrid metaheuristic to solve both the OP and the TOP with time windows. The method combines the greedy randomized adaptive search procedure (GRASP) with the evolutionary local search (ELS). ELS generates multiple distinct child solutions using a mutation mechanism. Each child solution is further improved by a local search procedure. GRASP provides multiple starting solutions to the ELS. The method is able to improve several best known results on available benchmark instances.
---
paper_title: The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search

paper_content:

The Team Orienteering Problem (TOP) is a known NP-hard problem that typically arises in vehicle routing and production scheduling contexts. In this paper we introduce a new solution method to solve the TOP with hard Time Window constraints (TOPTW). We propose a Variable Neighborhood Search (VNS) procedure based on the idea of exploring, most of the time, granular instead of complete neighborhoods in order to improve the algorithm’s efficiency without loosing effectiveness. The method provides a general way to deal with granularity for those routing problems based on profits and complicated by time constraints. Extensive computational results are reported on standard benchmark instances. Performance of the proposed algorithm is compared to optimal solution values, when available, or to best known solution values obtained by state-of-the-art algorithms. The method comes out to be, on average, quite effective allowing to improve the best know values for 25 test instances.
---
paper_title: The orienteering problem: A survey

paper_content:

During the last decade, a number of challenging applications in logistics, tourism and other fields were modelled as orienteering problems (OP). In the orienteering problem, a set of vertices is given, each with a score. The goal is to determine a path, limited in length, that visits some vertices and maximises the sum of the collected scores. In this paper, the literature about the orienteering problem and its applications is reviewed. The OP is formally described and many relevant variants are presented. All published exact solution approaches and (meta) heuristics are discussed and compared. Interesting open research questions concerning the OP conclude this paper.
---
paper_title: A simulated annealing heuristic for the team orienteering problem with time windows

paper_content:

This paper presents a simulated annealing based heuristic approach for the team orienteering problem with time windows (TOPTW). Given a set of known locations, each with a score, a service time, and a time window, the TOPTW finds a set of vehicle tours that maximizes the total collected scores. Each tour is limited in length and a visit to a location must start within the location’s service time window. The proposed heuristic is applied to benchmark instances. Computational results indicate that the proposed heuristic is competitive with other solution approaches in the literature.
---
paper_title: Cluster-Based Heuristics for the Team Orienteering Problem with Time Windows

paper_content:

The Team Orienteering Problem with Time Windows (TOPTW) deals with deriving a number of tours comprising a subset of candidate nodes (each associated with a “profit” value and a visiting time window) so as to maximize the overall “profit”, while respecting a specified time span. TOPTW has been used as a reference model for the Tourist Trip Design Problem (TTDP) in order to derive near-optimal multiple-day tours for tourists visiting a destination featuring several points of interest (POIs), taking into account a multitude of POI attributes. TOPTW is an NP-hard problem and the most efficient known heuristic is based on Iterated Local Search (ILS). However, ILS treats each POI separately; hence it tends to overlook highly profitable areas of POIs situated far from the current location, considering them too time-expensive to visit. We propose two cluster-based extensions to ILS addressing the aforementioned weakness by grouping POIs on disjoint clusters (based on geographical criteria), thereby making visits to such POIs more attractive. Our approaches improve on ILS with respect to solutions quality, while executing at comparable time and reducing the frequency of overly long transfers among POIs.
---
paper_title: An iterative three-component heuristic for the team orienteering problem with time windows

paper_content:

This paper studies the team orienteering problem with time windows, the aim of which is to maximize the total profit collected by visiting a set of customers with a limited number of vehicles. Each customer has a profit, a service time and a time window. A service provided to any customer must begin in his or her time window. We propose an iterative framework incorporating three components to solve this problem. The first two components are a local search procedure and a simulated annealing procedure. They explore the solution space and discover a set of routes. The third component recombines the routes to identify high quality solutions. Our computational results indicate that this heuristic outperforms the existing approaches in the literature in average performance by at least 0.41%. In addition, 35 new best solutions are found.
---
paper_title: An effective hybrid evolutionary local search for orienteering and team orienteering problems with time windows

paper_content:

The orienteering problem (OP) consists in finding an elementary path over a subset of vertices. Each vertex has associated a profit that is collected on the visitor's first visit. The objective is to maximize the collected profit with respect to a limit on the path's length. The team orienteering problem (TOP) is an extension of the OP where a fixed number m of paths must be determined. This paper presents an effective hybrid metaheuristic to solve both the OP and the TOP with time windows. The method combines the greedy randomized adaptive search procedure (GRASP) with the evolutionary local search (ELS). The ELS generates multiple distinct child solutions using a mutation mechanism and a local search. The GRASP provides multiple starting solutions to the ELS. The method is able to improve several best known results on available benchmark instances.
---
paper_title: Iterated local search for the team orienteering problem with time windows

paper_content:

A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a team orienteering problem with time windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximise the sum of the collected scores by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.
---
paper_title: Efficient Heuristics for the Time Dependent Team Orienteering Problem with Time Windows

paper_content:

The Time Dependent Team Orienteering Problem with Time Windows (TDTOPTW) can be used to model several real life problems. Among them, the route planning problem for tourists interested in visiting multiple points of interest (POIs) using public transport. The main objective of this problem is to select POIs that match tourist preferences, while taking into account a multitude of parameters and constraints and respecting the time available for sightseeing in a daily basis. TDTOPTW is NP-hard while almost the whole body of the related literature addresses the non time dependent version of the problem. The only TDTOPTW heuristic proposed so far is based on the assumption of periodic service schedules. Herein, we propose two efficient cluster-based heuristics for the TDTOPTW which yield high quality solutions, take into account time dependency in calculating travel times between POIs and make no assumption on periodic service schedules. The validation scenario for our prototyped algorithms included the metropolitan transit network and real POI sets compiled from Athens (Greece).
---
paper_title: Integrating public transportation in personalised electronic tourist guides

paper_content:

Personalised electronic tourist guides (PETs) are mobile hand-held devices able to create tourist routes matching tourists' preferences. Transportation information has been identified as one of the most appreciated functionalities of a PET. We model the tourist planning problem, integrating public transportation, as the time-dependent team orienteering problem with time windows (TD-TOPTW) in order to allow PETs to create personalised tourist routes in real-time. We develop and compare two different approaches to solve the TD-TOPTW. Experimental results for the city of San Sebastian show that both approaches are able to obtain routes in real-time.
---
paper_title: ROSE: assisting pedestrians to find preferred events and comfortable public transport connections

paper_content:

In this paper, we describe ROSE (Routing Service), a mobile application which combines pedestrian navigation with event recommendation and live public transport support. It determines the best possible transport link and accompanies passengers throughout their entire journey. Our motivation is to free the passenger from as many tedious tasks as possible in finding an interesting event and on the way to it. Further, it reacts in real time to delays in the public transport system and calculates alternative routes when necessary. For route planning in this context, we will propose a two step algorithm for incorporating non monotone and non optimistic multi dimensional user preferences in an A*-like algorithm. We also present an assignment of theoretical foundations to real world route planning problems.
---
paper_title: Cluster-Based Heuristics for the Team Orienteering Problem with Time Windows

paper_content:

The Team Orienteering Problem with Time Windows (TOPTW) deals with deriving a number of tours comprising a subset of candidate nodes (each associated with a “profit” value and a visiting time window) so as to maximize the overall “profit”, while respecting a specified time span. TOPTW has been used as a reference model for the Tourist Trip Design Problem (TTDP) in order to derive near-optimal multiple-day tours for tourists visiting a destination featuring several points of interest (POIs), taking into account a multitude of POI attributes. TOPTW is an NP-hard problem and the most efficient known heuristic is based on Iterated Local Search (ILS). However, ILS treats each POI separately; hence it tends to overlook highly profitable areas of POIs situated far from the current location, considering them too time-expensive to visit. We propose two cluster-based extensions to ILS addressing the aforementioned weakness by grouping POIs on disjoint clusters (based on geographical criteria), thereby making visits to such POIs more attractive. Our approaches improve on ILS with respect to solutions quality, while executing at comparable time and reducing the frequency of overly long transfers among POIs.
---
paper_title: Intelligent Routing System for a Personalised Electronic Tourist Guide

paper_content:

When tourists are at a destination, they typically search for information Organizations. There, the staff categorizes tourists’ profile and restrictions. Combining this information with their up-to-date knowledge about the local attractions, weather and public transportation, they suggest a personalised route for the tourist agenda. This paper presents. an intelligent routing system for a Personalised Electronic Tourist Guide to fulfil the same task. This system improves the automatic route creation functionality of existing PETs to solve better the needs of tourists in several aspects: i) it includes public transportation, ii) it takes varying travelling times into account, adapting to real circumstances as rush-hours, iii) it calculates routes in real time to react to unexpected events, iv) it applies last generation heuristics from Operations Research to create routes efficiently, even in destinations with a large number of point of interests and a dense public transportation network.
---
paper_title: Iterated local search for the team orienteering problem with time windows

paper_content:

A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a team orienteering problem with time windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximise the sum of the collected scores by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.
---
paper_title: The team orienteering problem

paper_content:

In the team orienteering problem, start and end points are specified along with other locations which have associated scores. Given a fixed amount of time for each of the M members of the team, the goal is to determine M paths from the start point to the end point through a subset of locations in order to maximize the total score. In this paper, a fast and effective heuristic is presented and tested on 353 problems ranging in size from 21 to 102 points. The computational results are presented in detail.
---
paper_title: The Capacitated Team Orienteering and Profitable Tour Problems

paper_content:

In this paper, we study the capacitated team orienteering and profitable tour problems (CTOP and CPTP). The interest in these problems comes from recent developments in the use of the Internet for a better matching of demand and offer of transportation services. We propose exact and heuristic procedures for the CTOP and the CPTP. The computational results show that the heuristic procedures often find the optimal solution and in general cause very limited errors.
---
paper_title: Multiple agents maximum collection problem with time dependent rewards

paper_content:

In this paper, we study Multiple Agents Maximum Collection Problem with Time Dependent Rewards (MAMCP-TDR) which is a variant of Multiple Tour Maximum Collection Problem (MTMCP) (Butt & Cavalier, 1994). In MAMCP-TDR, there are multiple agents to collect linearly decreasing rewards over time. The objective is to maximize total surplus (total reward collected minus total travel cost) by routing multiple agents from a central depot. We propose a mathematical formulation for the problem. Since the problem is strongly NP-hard, we develop a heuristic algorithm, called Cluster-and-Route Algorithm (CRA), to find near-optimal solutions. In CRA, first we cluster the targets/rewards using the well-known k-means clustering algorithm. Then, we find tours by solving a single agent problem for each cluster. To solve the single agent problem, we propose several routing algorithms. Finally, we implement several improvement ideas to improve the final solution. We conduct computational experiments on randomly generated instances and instances of a related problem in the literature to test the performance of routing algorithms for single agent case and the CRA for MAMCP-TDR in terms of solution time and solution quality. Compared to the mathematical formulation, we conclude that CRA provides solutions with similar quality for small instances and performs significantly better both in terms of solution time and solution quality on medium and large instances.
---
paper_title: A Tabu Search approach for Multi Constrained Team Orienteering Problem and its application in touristic trip planning

paper_content:

The touristic trip planning problem can be considered as a Multi Constrained Team Orienteering Problem with Time Windows (MCTOPTW). The MCTOPTW is characterized with a set of points of interest (POI), each having a score, a time window and some attributes such as the type or entry fee. The maximum number of POIs of certain types that can be included into the itinerary is limited. A tourist can visit the POIs during their respective time windows. The objective is to visit the points that have the highest scores during specified periods of time. This paper proposes a Tabu Search approach for solving the MCTOPTW problem. To explore the neighborhood the moves Insert, Replace and Swap are applied. Additionally, the algorithm employs a tabu list, a perturbation and a diversification mechanism. The algorithm is evaluated on benchmark instances from the literature and its performance is compared to the state of the art results.
---
paper_title: An exact algorithm for team orienteering problems

paper_content:

Optimising routing of vehicles constitutes a major logistic stake in many industrial contexts. We are interested here in the optimal resolution of special cases of vehicle routing problems, known as team orienteering problems. In these problems, vehicles are guided by a reward that can be collected from customers, while the length of routes is limited. The main difference with classical vehicle routing problems is that not all customers have to be visited. The solution method we propose here is based on a Branch & Price algorithm. It is, as far as we know, the first exact method proposed for such problems, except for a preliminary work from Gueguen (Methodes de résolution exacte pour problémes de tournées de véhicules. Thése de doctorat, école Centrale Paris 1999) and a work from Butt and Ryan (Comput Oper Res 26(4):427–441 1999). It permits to solve instances with up to 100 customers.
---
paper_title: An adaptive ejection pool with toggle-rule diversification approach for the capacitated team orienteering problem

paper_content:

In the capacitated team orienteering problem (CTOP), we are given a set of homogeneous vehicles and a set of customers each with a service demand value and a profit value. A vehicle can get the profit of a customer by satisfying its demand, but the total demand of all customers in its route cannot exceed the vehicle capacity and the length of the route must be within a specified maximum. The problem is to design a set of routes that maximizes the total profit collected by the vehicles. In this article, we propose a new heuristic algorithm for the CTOP using the ejection pool framework with an adaptive strategy and a diversification mechanism based on toggling between two priority rules. Experimental results show that our algorithm can match or improve all the best known results on the standard CTOP benchmark instances proposed by Archetti et al. (2008).
---
paper_title: Optimal solutions for routing problems with profits

paper_content:

In this paper, we present a branch-and-price algorithm to solve two well-known vehicle routing problems with profits, the Capacitated Team Orienteering Problem and the Capacitated Profitable Tour Problem. A restricted master heuristic is applied at each node of the branch-and-bound tree in order to obtain primal bound values. In spite of its simplicity, the heuristic computes high quality solutions. Several unsolved benchmark instances have been solved to optimality.
---
paper_title: Intelligent Routing System for a Personalised Electronic Tourist Guide

paper_content:

When tourists are at a destination, they typically search for information Organizations. There, the staff categorizes tourists’ profile and restrictions. Combining this information with their up-to-date knowledge about the local attractions, weather and public transportation, they suggest a personalised route for the tourist agenda. This paper presents. an intelligent routing system for a Personalised Electronic Tourist Guide to fulfil the same task. This system improves the automatic route creation functionality of existing PETs to solve better the needs of tourists in several aspects: i) it includes public transportation, ii) it takes varying travelling times into account, adapting to real circumstances as rush-hours, iii) it calculates routes in real time to react to unexpected events, iv) it applies last generation heuristics from Operations Research to create routes efficiently, even in destinations with a large number of point of interests and a dense public transportation network.
---
paper_title: Iterated local search for the team orienteering problem with time windows

paper_content:

A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a team orienteering problem with time windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximise the sum of the collected scores by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.
---
paper_title: Privatized rural postman problems

paper_content:

In this work we analyze the privatized rural postman problem which is the edge version of the traveling salesman problems with profits.The problem is defined on a undirected graph G(V, E) with a distinguished vertex d, called the Depot. There are two non-negative real functions on the edge set E, which define the value of a cycle in G: one is the profit function, b, and the other one is the cost function, c. They have different meanings when a cycle C traverses an edge e (possibly more than once), because we pay a cost ce every time e is traversed, but we collect the profit be only the first time e is traversed. The privatized rural postman problem is to find a cycle C*, passing through d and not necessarily simple, which maximizes the sum of the values of the edges traversed in C*. That is, maxC {Σe∈C (be - teCe)} where te is the number of times that edge e is traversed in C.We study some properties of the problem: we show that it is NP-hard, its relation with known and new problems, and special cases with good algorithms. We also analyze several integer linear systems of inequalities, which define the polyhedral structure of the problem, and we give dominance and preprocessing conditions. We finish with some remarks and comments about future research.
---
paper_title: Approximation Algorithms for Distance Constrained Vehicle Routing Problems

paper_content:

We study the distance constrained vehicle routing problem (DVRP) (Laporte et al., Networks 14 (1984), 47–61, Li et al., Oper Res 40 (1992), 790–799): given a set of vertices in a metric space, a specified depot, and a distance bound D, find a minimum cardinality set of tours originating at the depot that covers all vertices, such that each tour has length at most D. This problem is NP-complete, even when the underlying metric is induced by a weighted star. Our main result is a 2-approximation algorithm for DVRP on tree metrics; we also show that no approximation factor better than 1.5 is possible unless P = NP. For the problem on general metrics, we present a $(O(\log {1 \over \varepsilon }),1 + \varepsilon )$ **image** -bicriteria approximation algorithm: i.e., for any e > 0, it obtains a solution violating the length bound by a 1 + e factor while using at most $O(\log {1 \over \varepsilon })$ **image** times the optimal number of vehicles. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012 © 2012 Wiley Periodicals, Inc.
---
paper_title: On the Distance Constrained Vehicle Routing Problem

paper_content:

We analyze the vehicle routing problem with constraints on the total distance traveled by each vehicle. Two objective functions are considered: minimize the total distance traveled by vehicles and minimize the number of vehicles used. We demonstrate a close relationship between the optimal solutions for the two objective functions and perform a worst case analysis for a class of heuristics. We present a heuristic that provides a good worst case result when the number of vehicles used is relatively small.
---
paper_title: The undirected capacitated arc routing problem with profits

paper_content:

A profit and a demand are associated with each edge of a set of profitable edges of a given graph. A travel time is associated with each edge of the graph. A fleet of capacitated vehicles is given to serve the profitable edges. A maximum duration of the route of each vehicle is also given. The profit of an edge can be collected by one vehicle only that also serves the demand of the edge. The objective of this problem, which is called the undirected capacitated arc routing problem with profits (UCARPP), is to find a set of routes that satisfy the constraints on the duration of the route and on the capacity of the vehicle and maximize the total collected profit. We propose a branch-and-price algorithm and several heuristics. We can solve exactly instances with up to 97 profitable edges. The best heuristics find the optimal solution on most of instances where it is available.
---
paper_title: Approximations for minimum and min-max vehicle routing problems

paper_content:

We consider a variety of vehicle routing problems. The input to a problem consists of a graph G = (N, E) and edge lengths l(e), e ∈ E. Customers located at the vertices have to be visited by a set of vehicles. Two important parameters are k the number of vehicles, and λ the longest distance traveled by a vehicle. We consider two types of problems. (1) Given a bound λ on the length of each path, find a minimum sized collection of paths that cover all the vertices of the graph, or all the edges from a given subset of edges of the input graph. We also consider a variation where it is desired to cover N by a minimum number of stars of length bounded by λ. (2) Given a number k find a collection of k paths that cover either the vertex set of the graph or a given subset of edges. The goal here is to minimize λ, the maximum travel distance. For all these problems we provide constant ratio approximation algorithms and prove their NP-hardness.
---
paper_title: Two exact algorithms for the distance-constrained vehicle routing problem

paper_content:

This paper considers a version of the vehicle routing problem in which all vehicles are identical and where the distance travelled by any vehicle may not exceed A prespecified upper bound. The problem is first formulated as an integer program which is solved by means of a constraint relaxation procedure. Two exact algorithms are developed: one based on Gomory cutting planes and one on branch and bound. Numerical results are reported. (Author/TRRL)
---
paper_title: The orienteering problem: A survey

paper_content:

During the last decade, a number of challenging applications in logistics, tourism and other fields were modelled as orienteering problems (OP). In the orienteering problem, a set of vertices is given, each with a score. The goal is to determine a path, limited in length, that visits some vertices and maximises the sum of the collected scores. In this paper, the literature about the orienteering problem and its applications is reviewed. The OP is formally described and many relevant variants are presented. All published exact solution approaches and (meta) heuristics are discussed and compared. Interesting open research questions concerning the OP conclude this paper.
---
paper_title: The one-period bus touring problem: Solved by an effective heuristic for the orienteering tour problem and improvement algorithm

paper_content:

Abstract The one-period bus touring problem – also referred to as simply the bus touring problem (BTP) – objective is to maximize the total attractiveness of the tour by selecting a subset of sites to be visited and scenic routes to be traveled – both having associated non-negative attractivity values – given the geographic frame considerations and constraints on touring time, cost and/or total distance. The integer linear-programming model developed to derive an optimal bus touring solution for the BTP is not practical for such a NP-complete problem. A similar NP-hard problem is the orienteering tour problem (OTP) in which the identical start and end point is specified along with other locations having associated scores. Competitors seek to visit in a fixed amount of time, a subset of locations in order to maximize the total score. This paper presents a transformation from the BTP to the OTP and illustrates the use of an effective heuristic for the OTP together with an improvement process, aimed at generating a fast near-optimal BTP solution. The results of 11 bus touring problems are presented.
---
paper_title: The Profitable Arc Tour Problem: Solution with a Branch-and-Price Algorithm

paper_content:

In this article, we introduce a new arc routing problem that we call the profitable arc tour problem. This problem is defined on a graph in which profits and travel costs are associated with the arcs. The objective is to find a set of cycles in the graph that maximizes the collection of profit minus travel costs, subject to constraints limiting the number of times that profit is available on arcs and the maximal length of cycles. The problem is related both to constrained flow problems and to vehicle-routing problems. We tackle it from this standpoint and propose a branch-and-price algorithm for its solution. In the column-generation phase, the issue of the collection decisions while traveling through the arcs is addressed. In the branching phase, the fact that viewing solutions in terms of flow variables regularly induces an integer flow matrix leads us to introduce a branching method called the flow-splitting method. Finally, the relationships of this problem with constrained flow optimization are taken into account in an initial phase of the algorithm.
---
paper_title: The Team Orienteering Arc Routing Problem

paper_content:

The team orienteering arc routing problem (TOARP) is the extension to the arc routing setting of the team orienteering problem. In the TOARP, in addition to a possible set of regular customers that have to be serviced, another set of potential customers is available. Each customer is associated with an arc of a directed graph. Each potential customer has a profit that is collected when it is serviced, that is, when the associated arc is traversed. A fleet of vehicles with a given maximum traveling time is available. The profit from a customer can be collected by one vehicle at most. The objective is to identify the customers that maximize the total profit collected while satisfying the given time limit for each vehicle.In this paper we propose a formulation for this problem and study a relaxation of its associated polyhedron. We present some families of valid and facet-inducing inequalities that we use in the implementation of a branch-and-cut algorithm for the resolution of the problem. Computational experiments are run on a large set of benchmark instances.
---
paper_title: Solving the Prize-collecting Rural Postman Problem

paper_content:

In this work we present an algorithm for solving the Prize-collecting Rural Postman Problem. This problem was recently defined and is a generalization of other arc routing problems like, for instance, the Rural Postman Problem. The main difference is that there are no required edges. Instead, there is a profit function on the edges that must be taken into account only the first time that an edge is traversed. The problem is modeled as a linear integer program where the system has an exponential number of inequalities. We propose a solution algorithm where iteratively we solve relaxed models with a small number of inequalities, that provide upper bounds, and we propose exact separation procedures for generating violated cuts when possible. We also propose a simple heuristic to generate feasible solutions that provide lower bounds at each iteration. We use a two-phase method with different solvers at each phase. Despite the difficulty of the problem, the numerical results from a series of computational experiments with various types of instances assess the good behavior of the algorithm. In particular, 75% of the instances were optimally solved with the LP relaxation of the model. The remaining instances were optimally solved on a second phase, most of them in small computation times.
---
paper_title: Heuristic Methods Applied to Orienteering

paper_content:

A general description of the sport of orienteering in its two forms known as orienteering event and score orienteering event is given. The similarities between the latter and the generalized travelling salesman problem are underlined, and a common mathematical model is deduced. A ‘good’, if not ‘optimal’ solution of the corresponding problem by means of an efficient and computationally feasible method is derived and discussed. This solution is obtained by the use of either of two algorithms based on approximate methods. The two algorithms are given, and their efficiency is tested on a number of illustrative problems. Finally, a comparison between the two forms of the sport of orienteering is made.
---
paper_title: Local search for the undirected capacitated arc routing problem with profits

paper_content:

This paper deals with a recently introduced routing problem variant called the undirected capacitated arc routing problem with profits (UCARPP). The UCARPP model considered in the present study is primarily aimed at generating the route set which maximizes the profit collected from a set of potential customers, represented by edges of the examined transportation network. The secondary objective is to minimize the total route travel time. The generated routes are subject both to capacity and travel time constraints. To tackle the examined problem, we propose a local search metaheuristic development which explores two solution neighborhood structures. The conducted search is effectively diversified by means of the promises concept which is based on the aspiration criteria used in tabu search approaches. The proposed algorithm was tested on UCARPP benchmark instances taken from the literature. It efficiently produced high-quality results, improving several previously best known solutions.
---
paper_title: Tourist Trip Planning Functionalities: State–of–the–Art and Future

paper_content:

When tourists visit a city or region, they cannot visit every point of interest available, as they are constrained in time and budget. Tourist recommender applications help tourists by presenting a personal selection. Providing adequate tour scheduling support for these kinds of applications is a daunting task for the application developer. The objective of this paper is to demonstrate how existing models from the field of Operations Research (OR) fit this scheduling problem, and enable a wide range of tourist trip planning functionalities. Using the Orienteering Problem (OP) and its extensions to model the tourist trip planning problem, allows to deal with a vast number of practical planning problems.
---
paper_title: The travelling salesperson problem with hotel selection

paper_content:

In this paper, we present the travelling salesperson problem with hotel selection (TSPHS), an extension of the TSP with a number of interesting applications. We present a mathematical formulation, explain the difference with related optimization problems and indicate what makes this problem inherently more difficult. We develop a simple but efficient heuristic that uses two constructive initialization procedures and an improvement procedure consisting of several neighbourhood search operators designed specifically for this problem, as well as some typical neighbourhoods from the literature. We generate several benchmark instances of varying sizes and compare the performance of our heuristic with CPLEX (10.0). We also generate some problems with known optimal solutions and use these to further demonstrate that our heuristic achieves good results in very limited computation times.
---
paper_title: Parallel Meta-heuristics

paper_content:

We present a state-of-the-art survey of parallel meta-heuristic strategies, developments, and results. We discuss general design and implementation principles that apply to most meta-heuristic classes and instantiate these principles for neighborhood and population-based meta-heuristics. We also identify a number of trends and promising research directions.
---
paper_title: An adaptive parallel route construction heuristic for the vehicle routing problem with time windows constraints

paper_content:

Vehicle routing problem with time windows (VRPTW) is a generalisation of the classical vehicle routing problem, where a group of customers with given capacity demand are required to be serviced, and the servicing of the customer demands has to be started within a restricted available time window at the customer locations. This class of routing problems can be used to solve many practical problems such as container truck routing, delivery service scheduling and many logistics system problems. In this paper, we present a route construction heuristic with an adaptive parallel scheme. The result from extensive computation experiments shows the proposed parallel route construction heuristic is efficient and effective for routes construction, which is particularly useful for generation of the initial solutions for many metaheuristic approaches with improved solution quality and convergence of the solution process.
---
paper_title: A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery

paper_content:

This paper presents a parallel approach for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). The parallel algorithm is embedded with a multi-start heuristic which consists of a variable neighborhood descent procedure, with a random neighborhood ordering (RVND), integrated in an iterated local search (ILS) framework. The experiments were performed in a cluster with a multi-core architecture using up to 256 cores. The results obtained on the benchmark problems, available in the literature, show that the proposed algorithm not only improved several of the known solutions, but also presented a very satisfying scalability.
---
paper_title: A parallel ant colony algorithm on massively parallel processors and its convergence analysis for the travelling salesman problem

paper_content:

An adaptive parallel ant colony optimisation (PACO) algorithm on massively parallel processors (MPPs) is presented. In the algorithm, we propose a strategy for information exchange between processors that makes each processor choose a partner to communicate with and update their pheromone adaptively. We also propose a method of adaptively adjusting the time interval for the exchange of information according to the diversity of the solutions, to increase the quality of the optimisation results and to avoid early convergence. The analysis and proof of the convergence of the PACO algorithm is presented. Experimental results of the TSP confirm our theoretical conclusions and show that our PACO algorithm has a high convergence speed, high speedup and high efficiency.
---
paper_title: A parallel iterated tabu search heuristic for vehicle routing problems

paper_content:

This paper introduces a parallel iterated tabu search heuristic for solving four different routing problems: the classical vehicle routing problem (VRP), the periodic VRP, the multi-depot VRP, and the site-dependent VRP. In addition, it is applicable to the time-window constrained variant of these problems. Using the iterated local search framework, the heuristic combines tabu search with a simple perturbation mechanism to ensure a broad exploration of the search space. We also describe a parallel implementation of the heuristic to take advantage of multiple-core processors. Extensive computational results show that the proposed heuristic outperforms tabu search alone and is competitive with recent heuristics designed for each particular problem.
---
paper_title: Parallel Solution Methods for Vehicle Routing Problems

paper_content:

Parallel solution methods contribute to efficiently address large and complex combinatorial optimization problems, vehicle routing problems in particular. Parallel exact and heuristic methods for VRP variants are increasingly being proposed, and the pace seems to increase in recent years. “New” strategies have been proposed and many of the best known solutions to classical formulations have thus been obtained. This chapter describes and discusses the main strategies used to parallelize exact and metaheuristic solution methods for vehicle routing problems. It also provides an up-to-date survey of contributions to this rapidly evolving field and points to a number of promising research directions.
---

Title: A Survey on Algorithmic Approaches for Solving Tourist Trip Design Problems

Section 1: Introduction
Description 1: Introduce the concept of the Tourist Trip Design Problem (TTDP), its challenges, and its significance in the context of personalized electronic tourist guides (PETs).

Section 2: Single Tour TTDP Solution Approaches
Description 2: Discuss algorithmic approaches for solving single tour variants of the TTDP such as the Orienteering Problem (OP), OP with Time Windows (OPTW), and Time-Dependent OP (TDOP).

Section 3: Multiple Tour TTDP Solution Approaches
Description 3: Survey algorithmic approaches for solving multiple tour variants of the TTDP such as the Team Orienteering Problem (TOP), TOP with Time Windows (TOPTW), and Time-Dependent Team Orienteering Problem with Time Windows (TDTOPTW).

Section 4: Variants of OP
Description 4: Address different variants of the Orienteering Problem, including the Generalized Orienteering Problem (GOP), Multi-Objective Orienteering Problem (MOOP), and stochastic variants of the OP.

Section 5: Variants of TOP
Description 5: Discuss different variants of the Team Orienteering Problem, including the Capacitated Team Orienteering Problem (CTOP), Team Orienteering Problem with Capacity Constraint and Time Window (TOPCTW), and the Multi-Constrained Team Orienteering Problem with Time Windows (MCTOPTW).

Section 6: Further Algorithmic Approaches for Modeling TTDP Variants
Description 6: Explore additional optimization problems related to TTDP, such as the Distance Constrained Vehicle Routing Problem (DVRP) and the Arc Orienteering Problem (AOP), along with relevant approaches for solving these problems.

Section 7: New Prospects in Tourist Route Planning Problems
Description 7: Highlight new and emerging aspects in tourist route planning research, such as arbitrary start/end tour locations, realistic TTDP formulations, fast route updates, and the utilization of parallel computing.

Section 8: Conclusions
Description 8: Summarize the key findings of the survey, discuss the quality improvements upon existing solution approaches, and suggest promising directions for future research in tourist route planning.