The non-emergency patient transport modelled as a team orienteering problem

This work presents an improved model to solve the non-emergency patients transport (NEPT) service issues given the new rules recently established in Portugal. The model follows the same principle of the Team Orienteering Problem by selecting the patients to be included in the routes attending the maximum reduction in costs when compared with individual transportation. This model establishes the best sets of patients to be transported together. The model was implemented in AMPL and a compact formulation was solved using NEOS Server. A heuristic procedure based on iteratively solving Orienteering Problems is presented, and this heuristic provides good results in terms of accuracy and computation time. Euclidean instances as well as asymmetric real data gathered from Google maps were used, and the model has a promising performance mainly with asymmetric cost matrices.

Para no perder el norte. Orienteering a través de Arteaga. Salidas de campo para buscar, encontrar y no perderse.

Se describe una experiencia transdisciplinar de Educación Ambiental, que hunde sus raíces en los países nórdicos, desarrollada en un pueblo de Bizkaia. Con el pretexto de proporcionar al alumnado unos conocimientos básicos de orientación, éste se implica en un proceso que le permite descubrir e identificar su entorno desarrollando actitudes de acercamiento afectivo y compromiso ético con el mismo, tomando conciencia de los problemas existentes y posibilitando una respuesta crítica y solidaria para conseguir un desarrollo sostenible.

Orienteering

Competitive orienteering is the sport of finding one’s way in unknown terrain with the help of a map and a compass; there may or may not be a time limit. Developed in Scandinavia, the sport was popularized first in Europe in the twentieth century and is now becoming popular around the world. Different disciplines include foot, ski, and bicycle orienteering, as well as trail orienteering for physically impaired persons. The sport offers different competition formats and age categories that allow participation with adapted physical and mental demands for all ages.

Approximation Algorithms for Network Design and Orienteering

This thesis presents approximation algorithms for some NP-Hard combinatorial optimization problems on graphs and networks; in particular, we study problems related to Network Design. Under the widely-believed complexity-theoretic assumption that P is not equal to NP, there are no efficient (i.e., polynomial-time) algorithms that solve these problems exactly. Hence, if one desires efficient algorithms for such problems, it is necessary to consider approximate solutions: An approximation algorithm for an NP-Hard problem is a polynomial time algorithm which, for any instance of the problem, finds a solution whose value is guaranteed to be within a multiplicative factor of the value of an optimal solution to that instance. We attempt to design algorithms for which this factor, referred to as the approximation ratio of the algorithm, is as small as possible. The field of Network Design comprises a large class of problems that deal with constructing networks of low cost and/or high capacity, routing data through existing networks, and many related issues. In this thesis, we focus chiefly on designing fault-tolerant networks. Two vertices u,v in a network are said to be k-edge-connected if deleting any set of k − 1 edges leaves u and v connected; similarly, they are k-vertex connected if deleting any set of k − 1 other vertices or edges leaves u and v connected. We focus on building networks that are highly connected, meaning that even if a small number of edges and nodes fail, the remaining nodes will still be able to communicate. A brief description of some of our results is given below. We study the problem of building 2-vertex-connected networks that are large and have low cost. Given an n-node graph with costs on its edges and any integer k, we give an O(log n log k) approximation for the problem of finding a minimum-cost 2-vertex-connected subgraph containing at least k nodes. We also give an algorithm of similar approximation ratio for maximizing the number of nodes in a 2-vertex-connected subgraph subject to a budget constraint on the total cost of its edges. Our algorithms are based on a pruning process that, given a 2-vertex-connected graph, finds a 2-vertex-connected subgraph of any desired size and of density comparable to the input graph, where the density of a graph is the ratio of its cost to the number of vertices it contains. This pruning algorithm is simple and efficient, and is likely to find additional applications. Recent breakthroughs on vertex-connectivity have made use of algorithms for element-connectivity problems. We develop an algorithm that, given a graph with some vertices marked as terminals, significantly simplifies the graph while preserving the pairwise element-connectivity of all terminals; in fact, the resulting graph is bipartite. We believe that our simplification/reduction algorithm will be a useful tool in many settings. We illustrate its applicability by giving algorithms to find many trees that each span a given terminal set, while being disjoint on edges and non-terminal vertices; such problems have applications in VLSI design and other areas. We also use this reduction algorithm to analyze simple algorithms for single-sink network design problems with high vertex-connectivity requirements; we give an O(k log n)-approximation for the problem of k-connecting a given set of terminals to a common sink. We study similar problems in which different types of links, of varying capacities and costs, can be used to connect nodes; assuming there are economies of scale, we give algorithms to construct low-cost networks with sufficient capacity or bandwidth to simultaneously support flow from each terminal to the common sink along many vertex-disjoint paths. We further investigate capacitated network design, where edges may have arbitrary costs and capacities. Given a connectivity requirement R_uv for each pair of vertices u,v, the goal is to find a low-cost network which, for each uv, can support a flow of R_uv units of traffic between u and v. We study several special cases of this problem, giving both algorithmic and hardness results. In addition to Network Design, we consider certain Traveling Salesperson-like problems, where the goal is to find short walks that visit many distinct vertices. We give a (2 + epsilon)-approximation for Orienteering in undirected graphs, achieving the best known approximation ratio, and the first approximation algorithm for Orienteering in directed graphs. We also give improved algorithms for Orienteering with time windows, in which vertices must be visited between specified release times and deadlines, and other related problems. These problems are motivated by applications in the fields of vehicle routing, delivery and transportation of goods, and robot path planning.

A multi-criteria decision support system for a routing problem in waste collection

Autor proof

Non emergency patients transport - a mixed integer linear programming

This work presents a model and a heuristic to solve the non-emergency patients transport (NEPT) service issues given the new rules recently established in Portugal. The model follows the same principle of the Team Orienteering Problem by selecting the patients to be included in the routes attending the maximum reduction in costs when compared with individual transportation. This model establishes the best sets of patients to be transported together. The model was implemented in AMPL and a compact formulation was solved using NEOS Server. A heuristic procedure based on iteratively solving problems with one vehicle was presented, and this heuristic provides good results in terms of accuracy and computation time.

Genetic algorithms for the non emergency patients transport service

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the paper. The authors would like to thank Dr. Elaine DeBock for reviewing the manuscript.

A decision support system for a waste collection vehicle routing problem

The selective collection of municipal solid waste for recycling is a very complex and expensive process, where a major issue is to perform cost-efficient waste collection routes. Despite the abundance of commercially available software for fleet management, they often lack the capability to deal properly with sequencing problems and dynamic revision of plans and schedules during process execution. Our approach to achieve better solutions for the waste collection process is to model it as a vehicle routing problem, more specifically as a team orienteering problem where capacity constraints on the vehicles are considered, as well as time windows for the waste collection points and for the vehicles. The final model is called capacitated team orienteering problem with double time windows (CTOPdTW).We developed a genetic algorithm to solve routing problems in waste collection modelled as a CTOPdTW. The results achieved suggest possible reductions of logistic costs in selective waste collection.

Optimização do processo de recolha de resíduos: desenvolvimento de ferramentas de investigação operacional para o problema de orientação de equipas com multi-restrições

Tese de Doutoramento em Engenharia Industrial e de Sistemas.

El desenvolupament curricular del bloc d’activitats al medi natural per part dels professors d’Educació Física de la ciutat de Vic i les poblacions del voltant

L’estudi que es presenta a continuació té l’objectiu d’analitzar el desenvolupament curricular del bloc de continguts d’activitats al medi natural de l’assignatura d’Educació Física de la ciutat de Vic i de les poblacions situades en un radi de 10 kilòmetres. Per tal de dur-ho a terme, primerament s’ha realitzat un procés d’aproximació a les activitats al medi natural en l’educació, aprofundint en les característiques d’aquestes activitats en els centres, en la poca pràctica i els factors de limitació que tenen. A partir d’aquí, s’ha fet l’estudi amb una mostra formada de 29 professors d’Educació Física dels diferents cursos de la ESO. Per tal de realitzar la recerca i l’anàlisi, s’ha emprat una metodologia quantitativa de caràcter explicatiu, transversal i quasi experimental, i s’ha utilitzat l’instrument corresponent al qüestionari. Aquest, ha estat elaborat prenent com a referència el de l’estudi de Peñarrubia et al.(2011). Els resultats que s’han obtingut demostren que el bloc d’activitats al medi natural és el menys treballat per part del professors d’Educació Física, que un 14% del professorat no les treballa i dels que si ho fan un 68% les realitzen només una vegada a l’any. També destacar que aquests continguts no es treballen en el 33% dels cursos de la zona estudiada. Pel què fa els continguts més treballats destaquen l’orientació seguit del senderisme. Referent als factors de limitació destaquen la responsabilitat civil del professor i l’horari de classe com els més condicionants. Pel què fa a les activitats, l’escalada esdevé l’activitat on els factors de limitació influeixen més mentre que en l’orientació i el senderisme tenen poca importància. D’aquesta manera es pot veure una estreta relació entre els factors de limitació d’aquestes activitats i la poca pràctica d’aquestes en els centres educatius estudiats.

Generant mapes d'orientació amb OSM

Aquest projecte cobreix la vessant de la construcció i/o adaptació del mapa que utilitzen els corredors de les curses d'orientació, mostrant els punts de control, avituallament, etc. Els mapes estàn creats utilitzant la tecnología GIS mitjançant capes de dades OSM i les llibreries d'OpenLayers.

Suunnistussovelluksen suunnittelu Windows Phonelle

Tässä työssä luotiin suunnistussovelluksen demo Windows Phone 8:lle. Työn tavoite oli tehdä sovellus, jonka kanssa suunnistaminen tuntuisi mahdollisimman samalta, kuin oikeakin suunnistus. Työssä kiinnitettiin huomiota lähinnä sovelluksen tekniseen toteutukseen sekä paikannuksen riittävään tarkkuuteen. Työssä vertaillaan eri mobiilialustoja, selainten tietokantaratkaisuja, erilaisia selaimen ja serverin tietokantojen synkronointimenetelmiä sekä olemassaolevia suunnistussovelluksia. Työssä käytettiin indeksitietokantaa, jQuery mobilea ja Cordovaa sekä JSON:ia tietokantojen synkronointiin. Työssä tehty demo on lupaava esitys siitä, miten suunnistustaitojaan voisi harjoittaa tekniikkaa apuna käyttäen. Lopuksi työssä käydään vielä läpi sitä, mitä tällaiseen palveluun voisi toteuttaa työssä toteutetun demon lisäksi.

Atividades físicas de aventura na escola: uma proposta nas três dimensões do conteúdo

Pós-graduação em Ciências da Motricidade - IBRC

Corrida de orientação: uma proposta metodológica para o ensino da Geografia e da Cartografia

Pós-graduação em Geografia - IGCE

Esporte orientação e formação de professores de Geografia: uma experiência como cartografia escolar

Pós-graduação em Geografia - IGCE