The orienteering problem is one of the newer problems in the field of discrete programming. The formulation of this problem originates from a sport discipline, called orienteering. In the beginning of this thesis a formulation and mathematical model for this problem are introduced. The extension of the problem is the team orienteering problem, described in the next chapters of theoretical part. Many heuristics were published for this problem. While the heuristic of Chao et al. and a path relinking approach are described in detail in this thesis. Practical part deals with the team orienteering problem applied to a real task, specifically a visiting of 23 attractions in the New York in different number of days. The solution is found by optimization program Lingo 90 and by heuristic of Chao el al. Heuristic algorithm was implemented in programming language Visual Basic for Application. A comparison of the results is described at the end of the practical part.

Motivated by the management of sales representatives who visit customers to develop customer relationships, we present a stochastic orienteering problem on a network of queues, in which a hard time window is associated with each customer and the representative may experience uncertain wait time resulting from a queueing process at the customer. In general, given a list of potential customers and a time horizon consisting of several periods, the sales representative needs to decide which customers to visit in each period and how to visit customers within the period, with an objective to maximize the total reward collected by the end of the horizon. We start our study with a daily orienteering problem, which is a subproblem of the general problem. We focus on developing a priori and dynamic routing strategies for the salesperson to implement during a day. In the a priori routing case, the salesperson visits customers in a pre-planned order, and we seek to construct a static sequence of customers that maximizes the expected value collected. We consider two types of recourse actions. One is to skip a customer specified by an a priori route if the representative will arrive late in the customer's time window. The other type is to leave a customer immediately after arriving if observing a sufficiently long queue (balking) or to leave after waiting in queue for a period of time without meeting with the customer (reneging). We propose customer-specific decision rules to facilitate the execution of recourse actions and derive an analytical formula to compute the expected sales from the a priori route. We tailor a variable neighborhood search (VNS) heuristic to find a priori routes. In the dynamic routing case, the salesperson decides which customer to visit and how long to wait at each customer based on realized events. To seek dynamic routing policies, we propose an approximate dynamic programming approach based on rollout algorithms. The method introduces a two-stage heuristic estimation that we refer to as compound rollout. In the first stage, the algorithm decides whether to stay at the current customer or go to another customer. If departing the current customer, it chooses the customer to whom to go in the second stage. We demonstrate the value of our modeling and solution approaches by comparing the dynamic policies to a priori solutions with recourse actions. Finally, we address the multi-period orienteering problem. We consider that each customer's likelihood of adopting the representative's product stochastically evolves over time and is not fully observed by the representative. The representative can only estimate the adoption likelihood by meeting with the customer and the estimation may not be accurate. We model the problem as a partially observed Markov decision process with an objective to maximize the expected sales at the end of the horizon. We propose a heuristic that decomposes the problem into an assignment problem to schedule customers for a period and a routing problem to decide how to visit the scheduled customers within the period.

This dissertation details an algorithm to solve the Intratheater Airlift Operations Problem (IAOP) using advanced tabu search. A solution to the IAOP determines the routes and assignment of customer requests to a fleet of aircraft over a given time horizon. This problem and other variants comprise an ongoing challenge for United States Air Force (USAF) planners who manage detailed logistics throughout many theaters of operations. Attributes of the IAOP include cargo time windows, multiple cargo types, multiple vehicle cargo bay configurations, vehicle capacity, route duration limits, and port capacities. The IAOP multi-criteria objective embraces several components with the primary goal of satisfying as much of the demand as possible while minimizing cost. The algorithm is extended to allow split load deliveries of customer requests, allowing a shipment to be split into two or more sub-loads which are delivered separately to the customer. The split load relaxation, while significantly increasing the complexity of the problem, allows for possible improvement in the solution. The necessary changes to the model and algorithm are detailed, providing a foundation to extend any local search algorithm solving a vehicle routing problem to allow split loading. Results allowing split loading are presented and compared with results without split loading. The algorithm is also extended to include a rolling time horizon. Starting from a solution found at a previous time step, the algorithm is limited on how the solution can be modified. This reflects the reality of operations in which near-term plans are locked as they approach and enter execution while longer-term plans are continually updated as new information arrives. / text

Le problème de tournées de véhicules (Vehicle Routing Problem - VRP) est un problème d'optimisation combinatoire utilisé généralement pour modéliser et résoudre des différents problèmes rencontrés dans les systèmes logistiques et de transport. Dans cette thèse, nous nous sommes intéressés à l'étude et la résolution d'une classe de problèmes du VRP appelée les problèmes de courses d'orientation (Team Orienteering Problem - TOP). Dans cette catégorie de problèmes, il est a priori impossible de visiter tous les clients en raison de ressources limitées. On associe plutôt un profit à chaque client qui représente sa valeur. Ce profit est collecté lorsque le client est visité par l'un des véhicules disponibles. L'objectif est donc de sélectionner un sous ensemble de clients à servir tout en maximisant le profit total collecté. Dans un premier temps, nous avons introduit une nouvelle généralisation pour le TOP que nous avons appelé le Clustered TOP ou CluTOP. Dans cette variante, les clients sont regroupés en sous-ensembles appelés clusters auxquels nous associons des profits. Pour résoudre cette variante, nous avons proposé un schéma exact basé sur l'approche des plans sécants avec des inégalités valides supplémentaires et des pré-traitements. Nous avons également conçu une méthode heuristique basée sur l'approche order first-cluster second. Cette heuristique hybride combine une heuristique de type Adaptive Large Neighborhood Search qui explore l'espace des solutions et une procédure de découpage qui explore l'espace de recherche des tours géants. De plus, la procédure de découpage est renforcée par une recherche locale afin de mieux explorer l'espace de recherche. Le deuxième problème traité dans ce travail s'appelle le Synchronized Team Orienteering Problem with Time Windows (STOPTW). Cette variante avait été initialement proposée afin de modéliser des scénarios liés à la protection des infrastructures stratégiques menacées par l'avancée des feux de forêts. En plus des contraintes de fenêtres de temps et des visites synchronisées, cette variante considère le cas d'une flotte de véhicules hétérogène. Pour résoudre ce problème, nous avons proposé une méthode heuristique basée sur l'approche GRASP×ILS qui est parvenue à dominer la seule approche existante dans la littérature. La dernière variante du TOP abordée dans cette thèse s'appelle le Set Orienteering Problem (SOP). Les clients dans cette variante sont regroupés en sous-ensembles appelés clusters. Un profit est associé à chaque groupe qui n'est obtenu que si au moins un client est desservi par le véhicule disponible. Nous avons proposé une méthode de coupes avec deux procédures de séparation pour séparer les contraintes d'élimination des sous-tours. Nous avons également proposé un algorithme Mémétique avec une procédure de découpage optimale calculée à l'aide de la programmation dynamique. / The Vehicle Routing Problem (VRP) is a family of Combinatorial Optimization Problems generally used to solve different issues related to transportation systems and logistics. In this thesis, we focused our attention on a variant of the VRP called the Team Orienteering Problem (TOP). In this family of problems, it is a priory impossible to visit all the customers due to travel time limitation on vehicles. Instead, a profit is associated with each customer to represent its value and it is collected once the customer is visited by one of the available vehicles. The objective function is then to maximize the total collected profit with respect to the maximum travel time. Firstly, we introduced a new generalization for the TOP that we called the Clustered TOP (CluTOP). In this variant, the customers are grouped into subsets called clusters to which we associate profits. To solve this variant, we proposed an exact scheme based on the cutting plane approach with additional valid inequalities and pre-processing techniques. We also designed a heuristic method based on the order first-cluster second approach for the CluTOP. This Hybrid Heuristic combines between an ANLS heuristic that explores the solutions space and a splitting procedure that explores the giant tours search space. In addition, the splitting procedure is enhanced by local search procedure in order to enhance its coverage of search space. The second problem treated in this work is called the Synchronized Team Orienteering Problem with Time Windows (STOPTW). This variant was initially proposed in order to model scenarios related to asset protection during escaped wildfires. It considers the case of a heterogeneous fleet of vehicles along with time windows and synchronized visits. To solve this problem, we proposed a heuristic method based on the GRASP×ILS approach that led to a very outstanding results compared to the literature. The last variant of the TOP tackled in this thesis called the Set Orienteering Problem (SOP). Customers in this variant are grouped into subsets called clusters. Each cluster is associated with a profit which is gained if at least one customer is served by the single available vehicle. We proposed a Branch-and-Cut with two separation procedures to separate subtours elimination constraints. We also proposed a Memetic Algorithm with an optimal splitting procedure based on dynamic programming.

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2015-10-19T19:19:50Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Approved for entry into archive by Elizabete Silva (elizabete.silva@ufes.br) on 2015-11-03T19:59:38Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Made available in DSpace on 2015-11-03T19:59:38Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) Previous issue date: 2015 / O turismo é um importante setor para economia mundial e vem crescendo consistentemente nos últimos anos. Porém, um fator determinante para escolha do destino de um turista é a existência de pontos de interesse que ele deseja visitar na região e, para tanto, as informações dos pontos de interesse de uma região devem estar disponíveis. Dada às limitações de tempo do turista, não é possível para ele visitar todos os atrativos e, por essa razão, se faz necessário a criação de roteiros turísticos. Muito embora existam diversos pacotes de viagens com destinos predefinidos, contemplando locais mais populares, nos últimos anos tem crescido a procura por soluções que criem roteiros personalizados voltados às necessidades de cada turista. Para suprir essa nova demanda, Van Oudheusden e Vansteenwegen (2007) propuseram o Tourist Trip Design Problem (TTDP) e sugeriram o uso do Orienteering Problem (OP) e suas extensões para resolução do TTDP. Esta dissertação tem por objetivo o desenvolvimento de um modelo matemático e de uma meta-heurística Simulated Annealing (SA) para resolução do TTDP. O objetivo considerado consiste em gerar roteiros que maximizem a soma das notas atribuídas aos atrativos em função do grau de interesse do turista, levando em conta o período que ele tem disponível na localidade e o horário que cada atrativo está disponível para ser visitado. / Tourism is an important sector for the world economy and has been growing steadily over recent years. However, a decisive factor for the choice of a tourist destination is the existence of points of interest in the region he wants to visit and, therefore, the information from points of interest in a region should be available. Given the tourist time constraints, it is not possible for him to visit all the attractions and, therefore, it is necessary the creation of tourist routes. Although there are several packages with predefined destinations contemplating most popular locations in recent years has increased the demand for solutions that create custom tours for the needs of each tourist. To meet this new demand Van Oudheusden and Vansteenwegen (2007) proposed the Tourist Trip Design Problem (TTDP) and they suggested that the use of the Orienteering Problem (OP) and its extensions is the best approach to the TTDP. This thesis proposes the development of a mathematical model and a Simulated Annealing (SA) metaheuristic to solve the TTDP. The objective considered is to generate routes that maximize the sum of scores awarded to the attractions based on the degree of interest of the tourist taking into account the time that he has in the locality and the time that each attraction is available to be visited.

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2015-10-19T19:19:50Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Approved for entry into archive by Elizabete Silva (elizabete.silva@ufes.br) on 2015-11-03T19:59:38Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Made available in DSpace on 2015-11-03T19:59:38Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) Previous issue date: 2015 / Modelo Matemático e Meta-Heurística Simulated Annealing para Elaboração de Roteiros Turísticos com base no Tourist Trip Design Problem / Modelo Matemático e Meta-Heurística Simulated Annealing para Elaboração de Roteiros Turísticos com base no Tourist Trip Design Problem

近年來隨著全球化的發展，自助旅行的風氣蔚為風潮。背包客可以根據自己的喜好與條件，自己規劃旅遊路線與行程。一般規劃旅遊行程的過程費時而繁瑣，除了必須決定旅遊景點，還必須將景點開放時間、景點停留時間、交通方式、旅遊順序與路線、時間限制、住宿地點、經費等列入考量。 針對旅遊行程規劃，除了參考網友的行程規劃，目前已普遍有景點推薦、行程編輯系統，協助使用者規劃行程。但少有旅遊行程自動規劃系統。因此，本論文研發實作旅遊行程的自動規劃系統MyTripPlan。MyTripPlan具備景點推薦、景點停留與拜訪時間預估、路線規劃、行程規劃及行程調整的功能。 本系統MyTripPlan在離線時，先透過爬蟲程式由景點推薦網站取得熱門景點資訊、由相片分享網站取得景點相片時間以推估景點停留及拜訪時間、由交通查詢網站取得任兩景點間的推估交通時間。在線上時，當使用者輸入旅遊天數等時間限制、並由系統推薦景點勾選有興趣拜訪的景點及餐廳後，系統將運用定向排程演算法推論出符合時間限制的旅遊行程，呈現在地圖上，並結合交通網站，產生行程表。 經實驗效能驗證，以安排旅遊天數七天，五十六個景點所需要的行程規劃時間約為一秒鐘；使用者對於實作完畢的MyTripPlan系統與功能也都有滿意以上的評分。 / Travel planning process is time-consuming and tedious. To plan a trip, not only the attractions, but opening hours, timing cost, travel route, transportation, lodge, budget control and so on also need to be considered. While there are widespread attraction recommendation and itinerary editing systems to assist people to plan their trip, only few trip automated planning systems are developed. In this thesis, MyTripPlan, an automatic trip planning system, is designed and developed. MyTripPlan The system provides users the capability of attraction recommendation, visiting and stay time estimation, route planning, trip planning and itinerary adjustments. In offline process, MyTripPlan collects popular attraction information from web content for attraction recommendation, gets the timestamp of attractions from photo-sharing websites to estimate visiting and stay time, and crawls traffic information from public transportation query site to estimate the travel time between attractions. Given the trip duration, MyTripPlan recommends attractions and restaurants, schedules and produces the trip itinerary automatically based on the team orienteering scheduling algorithm. The generated itinerary takes the user-preferred attractions, visiting and stay time constraints, and transportation information into consideration. MyTripPlan presents the trip itinerary both in map and schedule list. The experiments show that the execution time for trip plan with fifty-six attractions in seven days requires about one second. Moreover, nineteen subjects were invited to evaluate the effectiveness of MyTripPlan. Most users were satisfied and gave excellent rating on the system performance.

Metrogaining is an urban outdoor navigational sport that uses a street map to which scored control points have been added. The objective is to collect maximum score points within a set time by visiting a subset of the scored control points. There is currently no metrogaining scoring standard, only guidelines on how to allocate scores. Accordingly, scoring approaches were explored to create new score sets by using scoring algorithms based on a simple relationship between the score of, and the number of visits to a control point. A spread model, which was developed to evaluate the score sets, generated a range of routes by solving a range of orienteering problems, which belongs to the class of NP-hard combinatorial optimisation problems. From these generated routes, the control point visit frequencies of each control point were determined. Using the visit frequencies, test statistics were subsequently adapted to test the goodness of scoring for each score set. The ndings indicate that the score-visits relationship is not a simple one, as the number of visits to a control point is not only dependent on its score, but also on the scores of the surrounding control points. As a result, the scoring algorithms explored were unable to cope with the complex scoring process uncovered. / Decision Sciences / M. Sc. (Operations Research)