Nesta pesquisa cartografamos as experiências de trabalhadores da saúde em seus deslocamentos cotidianos em transporte público para o trabalho e investigamos a possível relação da experiência do percurso cotidiano com a produção de saúdes e subjetividades destes transeuntes da cidade de São Paulo: uma pequena parcela da população, que diz da experiência cotidiana vivida por um coletivo de milhões de pessoas. Com orientação transdisciplinar, a pesquisa parte da interlocução da Psicologia com saberes da Filosofia e Ciências Sociais; uma bricolagem de conceitos, perceptos e afetos experienciados no trânsito da cidade, empregando o método cartográfico e perspectivas do paradigma ético-estético-político advindo da Filosofia da Diferença. Afirmamos o pensamento a partir da indissociabilidade entre individual e coletivo, interior e exterior, dentro e fora, indivíduo e sociedade - o rompimento com as dicotomias e maniqueísmos que tradicionalmente marcaram a história científico-paradigmática. Os conceitos de saúde e subjetividade passam a ser dispositivos analisadores de investigação dos modos de vida contemporâneos e dos efeitos imprimidos nos corpos pela experiência cotidiana de deslocamento na cidade. A problematização dos conceitos e de nossas práticas de todos os dias implica em pensarmos nas possibilidades de novas territorializações, novas maneiras de compreender saúdes e subjetividades, novas políticas da narratividade. Saúde que não é só cura ou ausência de doenças, mas produção e afirmação de diferença e vida. Subjetividades que são constantemente as possibilidades de diferir-se, a invenção e criação de si e do mundo. Acompanhados dos acontecimentos afirmativos que tomaram as ruas da cidade em manifestações, construímos, pesquisadora e participantes-colaboradores, um bordado em linhas sobre as condições do transporte público na cidade de São Paulo e os efeitos dessa qualidade de deslocamento na vida da população. Uma conversação entre macropolíticas do Estado e micropolíticas do cotidiano, a complexificação da velocidade avassaladora e dos espaços comprimidos, a vontade de ser gente numa cidade. / In this research we cartograph the experiences of health workers in their daily movements by public transport to work and investigate the possible relationship of the route everyday experience with the production of subjectivities and health of these passers of the city of São Paulo: a small portion of the population, which tells of everyday experience lived by a collective of millions of people. Transdisciplinary oriented, the research starts from the dialogue between psychology and knowledge of Philosophy and Social Sciences, a bricolage of concepts, percepts and affects experienced in city traffic, placing the method of cartography and prospects of the ethical-aesthetic-political paradigm from the Philosophy of Difference. We affirm the thinking of the inseparability between individual and collective, interior and exterior, inside and outside, self and society - a disruption with the dichotomies and manichaeism that traditionally branded the scientific-paradigmatic\'s history. The concepts of health and subjectivity become devices of analysis in the investigation of contemporary lifestyles and the effects imprinted on the bodies by everyday experience of displacement in the city. The questioning of the concepts and practices of our everyday imply the thinking of the possibilities of new territorializations, new ways of understanding healths and subjectivities, new policies of the narrative. This health is not just absence of disease or cure, but production and affirmation of difference and life. Subjectivities that are constantly possibilities to differ from yourself, to the invention and creation of self and the world. With the companionship of the affirmative events that took the streets in insurrection, we built, researcher and participants-colaborator, an embroidered in lines on the conditions of public transport in the city of São Paulo and the effects of displacement quality in the life of the population. A conversation between macropolitics of the state and the micropolitics of everyday life, the complexity of the overwhelming speed and compressed spaces, the willing to exist in a city.

Nesta pesquisa cartografamos as experiências de trabalhadores da saúde em seus deslocamentos cotidianos em transporte público para o trabalho e investigamos a possível relação da experiência do percurso cotidiano com a produção de saúdes e subjetividades destes transeuntes da cidade de São Paulo: uma pequena parcela da população, que diz da experiência cotidiana vivida por um coletivo de milhões de pessoas. Com orientação transdisciplinar, a pesquisa parte da interlocução da Psicologia com saberes da Filosofia e Ciências Sociais; uma bricolagem de conceitos, perceptos e afetos experienciados no trânsito da cidade, empregando o método cartográfico e perspectivas do paradigma ético-estético-político advindo da Filosofia da Diferença. Afirmamos o pensamento a partir da indissociabilidade entre individual e coletivo, interior e exterior, dentro e fora, indivíduo e sociedade - o rompimento com as dicotomias e maniqueísmos que tradicionalmente marcaram a história científico-paradigmática. Os conceitos de saúde e subjetividade passam a ser dispositivos analisadores de investigação dos modos de vida contemporâneos e dos efeitos imprimidos nos corpos pela experiência cotidiana de deslocamento na cidade. A problematização dos conceitos e de nossas práticas de todos os dias implica em pensarmos nas possibilidades de novas territorializações, novas maneiras de compreender saúdes e subjetividades, novas políticas da narratividade. Saúde que não é só cura ou ausência de doenças, mas produção e afirmação de diferença e vida. Subjetividades que são constantemente as possibilidades de diferir-se, a invenção e criação de si e do mundo. Acompanhados dos acontecimentos afirmativos que tomaram as ruas da cidade em manifestações, construímos, pesquisadora e participantes-colaboradores, um bordado em linhas sobre as condições do transporte público na cidade de São Paulo e os efeitos dessa qualidade de deslocamento na vida da população. Uma conversação entre macropolíticas do Estado e micropolíticas do cotidiano, a complexificação da velocidade avassaladora e dos espaços comprimidos, a vontade de ser gente numa cidade. / In this research we cartograph the experiences of health workers in their daily movements by public transport to work and investigate the possible relationship of the route everyday experience with the production of subjectivities and health of these passers of the city of São Paulo: a small portion of the population, which tells of everyday experience lived by a collective of millions of people. Transdisciplinary oriented, the research starts from the dialogue between psychology and knowledge of Philosophy and Social Sciences, a bricolage of concepts, percepts and affects experienced in city traffic, placing the method of cartography and prospects of the ethical-aesthetic-political paradigm from the Philosophy of Difference. We affirm the thinking of the inseparability between individual and collective, interior and exterior, inside and outside, self and society - a disruption with the dichotomies and manichaeism that traditionally branded the scientific-paradigmatic\'s history. The concepts of health and subjectivity become devices of analysis in the investigation of contemporary lifestyles and the effects imprinted on the bodies by everyday experience of displacement in the city. The questioning of the concepts and practices of our everyday imply the thinking of the possibilities of new territorializations, new ways of understanding healths and subjectivities, new policies of the narrative. This health is not just absence of disease or cure, but production and affirmation of difference and life. Subjectivities that are constantly possibilities to differ from yourself, to the invention and creation of self and the world. With the companionship of the affirmative events that took the streets in insurrection, we built, researcher and participants-colaborator, an embroidered in lines on the conditions of public transport in the city of São Paulo and the effects of displacement quality in the life of the population. A conversation between macropolitics of the state and the micropolitics of everyday life, the complexity of the overwhelming speed and compressed spaces, the willing to exist in a city.

The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved in polynomial time; with them, the CSPP is NP-hard and thus far no polynomial-time algorithms exist for solving it optimally. The problem arises in a number of practical situations. In the case of vehicle path planning, the vehicle may be an aircraft flying through a region with obstacles such as mountains or radar detectors, with an upper bound on the fuel consumption, the travel time or the risk of attack. The vehicle may be a submarine travelling through a region with sonar detectors, with a time or risk budget. These problems all involve a network which is a discrete model of the physical domain. Another example would be the routing of voice and data information in a communications network such as a mobile phone network, where the constraints may include maximum call delays or relay node capacities. This is a problem of current economic importance, and one for which time-sensitive solutions are not always available, especially if the networks are large. We consider the simplest form of the problem, large grid networks with a single side constraint, which have been studied in the literature. This thesis explores the application of Constraint Programming combined with Lagrange Relaxation to achieve optimal or near-optimal solutions of the CSPP. The following is a brief outline of the contribution of this thesis. Lagrange Relaxation may or may not achieve optimal or near-optimal results on its own. Often, large duality gaps are present. We make a simple modification to Dijkstra’s algorithm that does not involve any additional computational work in order to generate an estimate of path time at every node. / We then use this information to constrain the network along a bisecting meridian. The combination of Lagrange Relaxation (LR) and a heuristic for filtering along the meridian provide an aggressive method for finding near-optimal solutions in a short time. Two network problems are studied in this work. The first is a Submarine Transit Path problem in which the transit field contains four sonar detectors at known locations, each with the same detection profile. The side constraint is the total transit time, with the submarine capable of 2 speeds. For the single-speed case, the initial LR duality gap may be as high as 30%. The first hybrid method uses a single centre meridian to constrain the network based on the unused time resource, and is able to produce solutions that are generally within 1% of optimal and always below 3%. Using the computation time for the initial Lagrange Relaxation as a baseline, the average computation time for the first hybrid method is about 30% to 50% higher, and the worst case CPU times are 2 to 4 times higher. The second problem is a random valued network from the literature. Edge costs, times, and lengths are uniform, randomly generated integers in a given range. Since the values given in the literature problems do not yield problems with a high duality gap, the values are varied and from a population of approximately 100,000 problems only the worst 200 from each set are chosen for study. These problems have an initial LR duality gap as high as 40%. A second hybrid method is developed, using values for the unused time resource and the lower bound values computed by Dijkstra’s algorithm as part of the LR method. The computed values are then used to position multiple constraining meridians in order to allow LR to find better solutions. / This second hybrid method is able to produce solutions that are generally within 0.1% of optimal, with computation times that are on average 2 times the initial Lagrange Relaxation time, and in the worst case only about 5 times higher. The best method for solving the Constrained Shortest Path Problem reported in the literature thus far is the LRE-A method of Carlyle et al. (2007), which uses Lagrange Relaxation for preprocessing followed by a bounded search using aggregate constraints. We replace Lagrange Relaxation with the second hybrid method and show that optimal solutions are produced for both network problems with computation times that are between one and two orders of magnitude faster than LRE-A. In addition, these hybrid methods combined with the bounded search are up to 2 orders of magnitude faster than the commercial CPlex package using a straightforward MILP formulation of the problem. Finally, the second hybrid method is used as a preprocessing step on both network problems, prior to running CPlex. This preprocessing reduces the network size sufficiently to allow CPlex to solve all cases to optimality up to 3 orders of magnitude faster than without this preprocessing, and up to an order of magnitude faster than using Lagrange Relaxation for preprocessing. Chapter 1 provides a review of the thesis and some terminology used. Chapter 2 reviews previous approaches to the CSPP, in particular the two current best methods. Chapter 3 applies Lagrange Relaxation to the Submarine Transit Path problem with 2 speeds, to provide a baseline for comparison. The problem is reduced to a single speed, which demonstrates the large duality gap problem possible with Lagrange Relaxation, and the first hybrid method is introduced. / Chapter 4 examines a grid network problem using randomly generated edge costs and weights, and introduces the second hybrid method. Chapter 5 then applies the second hybrid method to both network problems as a preprocessing step, using both CPlex and a bounded search method from the literature to solve to optimality. The conclusion of this thesis and directions for future work are discussed in Chapter 6.