Tesi sul tema "Routing with profits"

Nous nous intéressons dans cette thèse à la résolution du problème de tournées sélectives (Team Orienteering Problem - TOP) et ses variantes. Ce problème est une extension du problème de tournées de véhicules en imposan tcertaines limitations de ressources. Nous proposons un algorithme de résolution exacte basé sur la programmation linéaire en nombres entiers (PLNE) en ajoutant plusieurs inégalités valides capables d’accélérer la résolution. D’autre part, en considérant des périodes de travail strictes pour chaque véhicule durant sa tournée, nous traitons une des variantes du TOP qui est le problème de tournées sélectives multipériodique (multiperiod TOP - mTOP) pour lequel nous développons une métaheuristique basée sur l’optimisation par essaim pour le résoudre. Un découpage optimal est proposé pour extraire la solution optimale de chaque particule en considérant les tournées saturées et pseudo saturées .Finalement, afin de prendre en considération la disponibilité des clients, une fenêtre de temps est associée à chacun d’entre eux, durant laquelle ils doivent être servis. La variante qui en résulte est le problème de tournées sélectives avec fenêtres de temps (TOP with Time Windows - TOPTW). Deux algorithmes exacts sont proposés pour résoudre ce problème. Le premier est basé sur la génération de colonnes et le deuxième sur la PLNE à laquelle nous ajoutons plusieurs coupes spécifiques à ce problème
We focus in this thesis on developing new algorithms to solve the Team Orienteering Problem (TOP) and two of its variants. This problem derives from the well-known vehicle routing problem by imposing some resource limitations .We propose an exact method based on Mixed Integer Linear Programming (MILP) to solve this problem by adding valid inequalities to speed up its solution process. Then, by considering strict working periods for each vehicle during its route, we treat one of the variants of TOP, which is the multi-period TOP (mTOP) for which we develop a metaheuristic based on the particle swarm optimization approach to solve it. An optimal split procedure is proposed to extract the optimal solution from each particle by considering saturated and pseudo-saturated routes. Finally, in order to take into consideration the availability of customers, a time window is associated with each of them, during which they must be served. The resulting variant is the TOP with Time Windows (TOPTW). Two exact algorithms are proposed to solve this problem. The first algorithm is based on column generation approach and the second one on the MILP to which we add additional cuts specific for this problem. The comparison between our exact and heuristic methods with the existing one in the literature shows the effectiveness of our approaches

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2008.
Includes bibliographical references (p. 143-149).
As the scale of space exploration gets larger, planning of planetary surface exploration becomes more complex and campaign-level optimization becomes necessary. This is a challenging profit maximization problem whose decisions encompass selection of bases, technological options, routes, and excursion methods under constraints on a route, a mission, and a whole campaign. The Generalized Location Routing Problem with Profits (GLRPP) is developed in this thesis as a framework to solve this campaign optimization problem. A mathematical formulation for the GLRPP is developed and two solution methods to solve the GLRPP - a single phase method and a three-phase method - are presented. Numerical experiments for these two solution methods are carried out and their performance in terms of efficiency and effectiveness are analyzed. Two case studies are carried out. The first case study is a global Mars surface exploration campaign optimization. Problem instances for 100 potential bases and 1000 potential exploration sites are successfully solved using a three-phase solution method. A methodology to express the incremental value of a technology using exploration profits is demonstrated to evaluate an orbiting depot and in-situ resource utilization (ISRU). The second case study is a college football recruiting problem. A GLRPP instance is created out of the NCAA football division I-A schools and airports from which the schools can be reached. The problem is successfully solved using the three-phase solution method within a very small optimality gap.
by Jaemyung Ahn.
Ph.D.

In this study, our aim is to determine the locations of bottle banks used in collecting recycled glass. The collection of recycled glass is done by a fleet of vehicles that visit some predetermined collection points, like restaurants and hospitals. The location of bottle banks depends on the closeness of the banks to the population zones where the recycled class is generated, and to the closeness of the banks to the predetermined collection points. A mathematical model, which combines the maximal covering problem in the presence of partial coverage and vehicle routing problem with profits, is presented. Heuristic procedures are proposed for the solution of the problem. Computational results based on generated test problems are provided. We also discuss a case study, where bottle banks are located in Yenimahalle, a district of Ankara

L'optimisation combinatoire est une branche de l'optimisation mathématique qui se concentre sur la recherche de solutions optimales parmi un ensemble fini de combinaisons possibles, tout en respectant un ensemble de contraintes et en maximisant ou minimisant une fonction objectif. Pour résoudre ces problèmes, les méthodes incomplètes sont souvent utilisées en pratique, car ces dernières peuvent produire rapidement des solutions de haute qualité, ce qui est un point critique dans de nombreuses applications. Dans cette thèse, nous nous intéressons au développement d'approches hybrides qui permettent d'améliorer la recherche incomplète en exploitant les méthodes complètes. Pour traiter en cas pratique, nous considérons ici le problème de tournées de véhicules avec profits, dont l'objectif est de sélectionner un sous-ensemble de clients à visiter par des véhicules de manière à maximiser la somme des profits associés aux clients visités. Plus précisément, nous visons tout d'abord à améliorer les algorithmes de recherche incomplets en exploitant les connaissances acquises dans le passé. L'idée centrale est de: (i) apprendre des conflits (combinaisons de décisions qui conduisent à une violation de certaines contraintes ou à une sous-optimalité des solutions) et les utiliser pour éviter de réexaminer les mêmes solutions et guider la recherche, et (ii) exploiter les bonnes caractéristiques de solutions élites afin de produire de nouvelles solutions ayant une meilleure qualité. En outre, nous étudions le développement d'un solveur générique pour des problèmes de routage complexes pouvant impliquer des clients optionnels, des véhicules multiples, des fenêtres temporelles multiples, des contraintes supplémentaires, et/ou des temps de transition dépendant du temps. Le solveur générique proposé exploite des sous-problèmes pour lesquels des méthodes de raisonnement dédiées sont disponibles. L'efficacité des approches proposées est évaluée par diverses expérimentations sur des instances classiques et sur des données réelles liées à un problème d'ordonnancement pour des satellites d'observation de la Terre, qui inclut éventuellement des profits incertains
Combinatorial optimization is an essential branch of computer science and mathematical optimization that deals with problems involving a discrete and finite set of decision variables. In such problems, the main objective is to find an assignment that satisfies a set of specific constraints and optimizes a given objective function. One of the main challenges is that these problems can be hard to solve in practice. In many cases, incomplete methods are preferred to complete methods since the latter may have difficulties in solving large-scale problems within a limited amount of time. On the other hand, incomplete methods can quickly produce high-quality solutions, which is a critical point in numerous applications. In this thesis, we investigate hybrid approaches that enhance incomplete search by exploiting complete search techniques. For this, we deal with a concrete case study, which is the vehicle routing problem with profits. In particular, we aim to boost incomplete search algorithms by extracting some knowledge during the search process and reasoning with the knowledge acquired in the past. The core idea is two-fold: (i) to learn conflicting solutions (that violate some constraints or that are suboptimal) and exploit them to avoid reconsidering the same solutions and guide search, and (ii) to exploit good features of elite solutions in order to hopefully generate new solutions having a higher quality. Furthermore, we investigate the development of a generic framework by decomposing and exchanging information between sub-modules to efficiently solve complex routing problems possibly involving optional customers, multiple vehicles, multiple time windows, multiple side constraints, and/or time-dependent transition times. The effectiveness of the approaches proposed is shown by various experiments on both standard benchmarks (e.g., the Orienteering Problem and its variants) and real-life datasets from the aerospace domain (e.g., the Earth Observation Satellite scheduling problem), and possibly involving uncertain profits

Mestrado em Decisão Económica e Empresarial
Através da parceria entre o ISEG e a EMEL - Empresa Municipal de Mobilidade e Estacionamento de Lisboa, foi realizado um estágio profissional, tendo como objetivo otimizar as rotas dos operadores de coleta da EMEL. Foi assim definido o objetivo de identificar, de forma automática, rotas que permitam coletar mais dinheiro no fim de cada turno, reduzindo e homogeneizando os montantes de dinheiro que ficam na rua e, por consequência, o risco de roubo. O problema enquadrado no Vehicle Routing Problem with Profits, identifica rotas que, partindo e regressando de/a um ponto fixo (a base), visitam um certo conjunto de nodos (parquímetros), compatíveis com a capacidade do veículo e com a duração dos turnos dos operadores de coleta. Não se exige que todos os nodos sejam visitados diariamente, sendo apenas visitados os que garantem maior retorno. Foi construída uma função para estimar o valor depositado em cada parquímetro, por hora, sendo assim possível estimar o seu valor no momento da coleta. De seguida, desenvolveu-se e programou-se (em VBA) uma heurística construtiva para a geração de rotas.
Through the partnership between ISEG and EMEL - Empresa Municipal de Mobilidade e Estacionamento de Lisboa, the traineeship has been proposed aiming to optimize the routes made by the EMEL's coin collection operators. The scope is to automatically identify routes that allow the coin collection of more parking meters at the end of each working shift, reducing the amount of money left on the street. The problem was interpreted as a Vehicle Routing Problem with Profits. The routes start and end at a fixed point (the base), and the vehicles must visit a certain set of nodes (metered), within the crew time limit. In this problem there is no need to visit every node daily but to visit those that guarantee a higher return, provided that both the vehicles' capacity and the time limits are satisfied. A valuation function was built to estimate the value deposited in each parking meter per hour. Then, a constructive heuristic was developed and programmed (VBA) to generate routes.
info:eu-repo/semantics/publishedVersion

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2001.
Includes bibliographical references (p. 77-78).
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
by Terran Melconian.
S.M.

Motivated by collaborative recycling efforts for non-profit agencies, we study a variant of the periodic location routing problem, in which one decides the set of open depots from the customer set, the capacity of open depots, and the visit frequency to nodes, in an effort to design networks for collaborative pickup activities. We formulate this problem, highlighting the challenges introduced by these decisions. We examine the relative dfficulty introduced with each decision through exact solutions and a heuristic approach which can incorporate extensions of model constraints and solve larger instances. The work is motivated by a project with a network of hunger relief agencies (e.g., food pantries, soup kitchens and shelters) focusing on collaborative approaches to address their cardboard recycling challenges collectively. We present a case study based on data from the network. In this novel setting, we evaluate collaboration in terms of participation levels and cost impact. These insights can be generalized to other networks of organizations that may consider pooling resources.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
PROGRAMA DE EXCELENCIA ACADEMICA
A indústria de transporte marítimo é essencial para o comércio internacional. No entanto, no despertar da crise financeira de 2008, essa indústria foi severamente atingida. Nessas ocasiões, empresas de transporte só são capazes de obter lucro se suas frotas forem roteadas de forma eficaz. Neste trabalho, nós estudamos uma classe de problemas de roteamento de navios relacionados ao Pickup and Delivery Problem with Time Windows. Para resolver esses problemas, nós introduzimos um método heurístico e um exato. O método heurístico é uma meta-heurística híbrida com uma vizinhança larga baseada em set partitioning, enquanto o método exato é um algoritmo de branch-and-price. Nós conduzimos experimentos em um conjunto de instâncias baseadas em rotas de navios reais. Os resultados obtidos mostram que nossos algoritmos superam as metodologias estado da arte. Em seguida, nós adaptamos o conjunto de instâncias para modelar um problema de roteamento de navios no qual a velocidade em cada segmento de rota é uma variável de decisão, e o consumo de combustível por unidade de tempo é uma função convexa da velocidade e carga do navio. A fim de resolver esse novo problema de roteamento de navios com otimização de velocidade, nós estendemos nossa meta-heurística para encontrar decisões de velocidade ótimas em toda avaliação de solução vizinha de uma busca local. Nossos experimentos demonstram que essa abordagem pode ser altamente rentável, e que requer apenas um aumento moderado de recursos computacionais.
The shipping industry is essential for international trade. However, in the wake of the 2008 financial crisis, this industry was severely hit. In these times, transportation companies can only obtain profit if their fleet is routed effectively. In this work, we study a class of ship routing problems related to the Pickup and Delivery Problem with Time Windows. To solve these problems, we introduce a heuristic and an exact method. The heuristic method is a hybrid metaheuristic with a set-partitioning-based large neighborhood, while the exact method is a branch-and-price algorithm. We conduct experiments on a benchmark suite based on real-life shipping segments. The results obtained show that our algorithms largely outperform the state-of-the-art methodologies. Next, we adapt the benchmark suite to model a ship routing problem where the speed on each sailing leg is a decision variable, and fuel consumption per time unit is a convex function of the ship speed and payload. To solve this new ship routing problem with speed optimization, we extend our metaheuristic to find optimal speed decisions on every local search move evaluation. Our computational experiments demonstrate that such approach can be highly profitable, with only a moderate increase in computational effort.

Thesis (M.S.) -- University of Maryland, College Park, 2004.
Thesis research directed by: Dept. of Electrical and Computer Engineering. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

While numerous studies have linked family routines to pediatric asthma outcomes, it remains unclear how family routines come to be associated with these outcomes on a biological level. The current study investigated whether longitudinal trajectories of inflammatory markers of asthma could be predicted by levels of family routines in youth with asthma. Family routines were assessed at baseline through parent questionnaires and peripheral blood samples obtained from youth every 6 months (total number of assessments = 4) over the course of an 18 month study period. Youth with more family routines in their home environment showed decreases in mitogen-stimulated production of a cytokine implicated in asthma, IL-13, over the course of the study period. In turn, within-person analyses indicated that at times when stimulated production of IL-13 was high, asthma symptoms were also high, pointing to the clinical relevance of changes in IL-13 over time. A variety of potential explanations for this effect were probed. Parental depression, stress, and general family functioning could not explain these effects, suggesting that family routines are not just a proxy for parent psychological traits or family relationship quality. However, medication use eliminated the relationship between family routines and stimulated production of IL-13. This suggests that family routines do impact asthma outcomes at the biological level, possibly through influencing medication adherence. Considering daily family behaviors when treating asthma may help improve both biological and clinical profiles in youth with asthma.

Manufacturers of passenger vehicles are experiencing increased pressure from consumers and legislators due to the impact of transportation on the environment. Automotive manufacturers are responding by designing more sustainable forms of transportation through a variety of efforts, including increased vehicle efficiency and the electrification of vehicle powertrains (plug in hybrid electric vehicles (PHEV) and battery electric vehicles (BEV)). An additional method for reducing the environmental impact of personal transport is eco-routing, a methodology which selects routes on the basis of energy consumption. Standard navigation systems offer route alternatives between a user clarified origin and destination when there are multiple paths available. These alternatives are commonly weighted on the basis of minimizing either total travel time (TTT) or trip distance. Eco-routing offers an alternative criterion – minimizing route energy consumption. Calculation of the energy consumption of a route necessitates the creation of a velocity profile which models how the route will be driven and a powertrain model which relates energy consumption to the constructed velocity profile. Existing research efforts related to both of these aspects typically require complex analysis and proprietary vehicle properties. A new approach to weighting the energy consumption of different routes is presented within this paper. The process of synthesizing velocity profiles is an improvement upon simpler models while requiring fewer variables as compared to more complex models. A single input, the maximum acceleration, is required to tune driver aggressiveness throughout an entire route. Additionally, powertrain results are simplified through the application of a new parameter, predictive terminal energy. The parameter uses only glider properties as inputs, as compared to dedicated powertrain models which use proprietary vehicle information as inputs which are not readily available from manufacturers. Application of this research reduces computation time and increases the number of vehicles for which this analysis can be applied. An example routing scenario is presented, demonstrating the capability of the velocity synthesis and predictive terminal energy methodologies.
Master of Science

Ce document synthétise mes travaux de thèse de doctorat en Automatique Productiqueà Grenoble INP (Institut National Polytechnique), thèse préparée au sein dudépartement automatique du laboratoire GIPSA-lab (Grenoble Image Parole Signal etAutomatique). Ce travail s’inscrit dans le cadre du contrôle local et de la supervisiondes systèmes de trafic routier. Les principales contributions portent sur la modélisation,la supervision et la commande locale des systèmes de trafic routier.La contribution apportée à la modélisation du trafic est l’ajout d’un modèle d’incertitudesur le modèle CTM (Cell Transmission Model [Daganzo, 1994]). Ce nouveaumodèle permet de prendre en compte les incertitudes sur différents paramètres dumodèle pour in-fine proposer de nouvelles stratégies de commandes commutées robustes.Outre cette approche de modélisation, nous proposons un niveau de supervisionpermettant d’une part d’estimer en temps réel le mode de fonctionnement et d’autrepart de détecter, localiser et estimer certaines fautes sur le système. L’estimation dynamiquede mode de fonctionnement nous permet de connaître l’état de congestion (ou denon-congestion) de l’aménagement routier considéré. Nous sommes en mesure de détecterdes fautes telles que des chutes de vitesse ou des chutes de capacité survenant sur la route.Enfin, nous proposons deux lois de commandes locales basées sur la théorie dessystèmes à commutations. Ainsi, le schéma de contrôle s’adaptera dynamiquementaux changements de propriétés du système. Ces lois de commande ont pour objet des’insérer dans un schéma de régulation hiérarchique
This document synthesizes my Phd thesis work in Automatic Control in Grenoble-INP. This thesis has been prepared in the automatic control department of thelaboratory GIPSA-lab. This work is situated in the area of traffic systems control andsupervision. Our contributions are about modeling, supervision and local traffic control.The CTM traffic model has been extended with a model of uncertainties. Thisnews model allows us to take into account the uncertain parameters of the model, topropose new robust switched control law.In addition to this modeling approach, we propose some developments on supervisionof trafic systems. On one hand, we can estimate the operating mode of thesystem in real time and on the other hand to estimate some faults on the system. Thedynamical estimation of the operating mode allows us to know the state of congestion(or non congestion) of the road. We are able to estimate faults such as speed fall andcapacities drop that may appear.Finally, we propose two control laws based on switching systems control. The developedcontrollers adapt their geometry to the properties of the system. The purposeof these controllers is to be inserted in a hierarchic control scheme

This thesis presents two new routing problems, both with objective functions focused on relative positioning of teams during the routing horizon. The relative positioning results in temporal and spatial dependencies among routes and is quantified with a nonlinear dispersion metric, designed to evaluate the instantaneous distances among teams over a time interval. This metric allows the design of objective functions to approximate teams during routes execution, when minimized, or disperse them, when maximized. Both approximation and dispersion are important routing characteristics in some practical applications, and two new optimization problems are proposed with these opposite objectives. The first one is a variation of the Multiple Traveling Salesman Problem, and its goal is to find a set of tours where the salesmen travel close to each other, minimizing dispersion. A Local Search Genetic Algorithm is proposed to solve the problem. It includes specialized genetic operators and neighborhoods. A new set of benchmark instances is proposed, adapted for the new problem from literature instances. Computational results show that the proposed approach provides solutions with the desired characteristics of minimal dispersion. The second problem is a bi-objective arc routing problem in which routes must be constructed in order to maximize collected profit and dispersion of teams. The maximization of the dispersion metric fosters the scattering of the teams during routing procedure. Usually, profit and dispersion objectives are conflicting, and by using a bi-objective approach the decision maker is able to choose a trade-off between collecting profits and scattering teams. Two solution methods are proposed, a Multi-objective Genetic Algorithm and a Multi-objective Genetic Local Search Algorithm, both specialized in order to exploit the characteristics of the problem. It is demonstrated, by means of computational experiments on a new set of benchmark instances, that the proposed approach provides approximation sets with the desired characteristics.
Esta tese apresenta dois novos problemas de roteamento, ambos com funções objetivo voltadas para o posicionamento relativo das equipes durante o horizonte de roteamento. O posicionamento relativo resulta em uma dependência temporal e espacial entre rotas e é quantificado com uma métrica de dispersão não-linear, projetada para avaliar as distâncias instantâneas entre as equipes ao longo de um intervalo de tempo. Esta métrica permite a concepção de funções objetivo para aproximar as equipes durante a execução das rotas, quando minimizada, ou para dispersá-las, quando maximizada. Tanto a aproximação quanto a dispersão são características importantes de roteamento em algumas aplicações práticas, e dois novos problemas de otimização são propostos com esses objetivos opostos. O primeiro é uma variação do Problema de Múltiplos Caixeiros Viajantes, e seu objetivo é encontrar um conjunto de rotas em que os caixeiros viajam próximos uns dos outros, minimizando a dispersão. Um Algoritmo Genético com Busca Local é proposto para resolver o problema. Ele inclui operadores genéticos e vizinhanças especializados. Um novo conjunto de instâncias é proposto, adaptado para o novo problema de instâncias da literatura. Resultados computacionais mostram que a abordagem proposta proporciona soluções com as características desejadas de dispersão mínima. O segundo problema é um problema de roteamento de arcos biobjetivo em que as rotas devem ser construídas de modo a maximizar o lucro recolhido e o distanciamento entre as equipes. A maximização da métrica promove a dispersão das equipes durante a execução das rotas. Normalmente, os objetivos de lucro e dispersão são conflitantes, e com uma abordagem biobjetivo o tomador de decisão é capaz de avaliar a troca entre a coleta de lucros e a dispersão de equipes. Dois métodos de solução são propostos, um Algoritmo Genético Multiobjetivo e um Algoritmo Genético Multiobjetivo com Busca Local, ambos especializados para explorar as características do problema. É demonstrado, por meio de experimentos computacionais sobre um novo conjunto de instâncias, que a abordagem proposta fornece conjuntos de aproximação com as características desejadas.

碩士
國立交通大學
運輸科技與管理學系
90
In recent years, transoceanic containerships are built larger and larger so as to lead to the formation of marine hub-and-spoke network. In the networks, large ships run between hub ports, while small ships are used as feeders between feeder ports. In the networks, the factor for the liner to operate depends on the ability to produce the profit. A containership berths more ports will not only increase the operation costs, but also generate the revenue. The critical point is the effect of trade off (revenue - cost) will benefit for the containership routing. However, the previous models were unable to provide the liner with the selection of the hubs in order to seed maximum profit. The main purpose of this paper is, therefore, to propose a hub-and-spoke model of routing containerships to solve the problem. The model consists of two parts. One, Model 1 decides the location of hub ports. The other, Model 2 assigns adequate feeders on the branch network. The total sum of two objective values in models is the maximum profit. The concept of HEUR 1 which O’Kelly proposed in 1987 is used to solve the function of Model 1. Model 2 decides the number of feeders on branch network, given the loop type routing to match with the traffic flow. This paper ends with an application of the real Trans-Pacific routing and the sensitivity analysis.

The astronomical increase in the number of wireless devices such as smart phones in 21th century has revolutionized the way people communicate with one another and share information. The new wireless technologies have also enabled researchers to collect real data about how people move and meet one another in different social settings. Understanding human mobility has many applications in different areas such as traffic planning in cities and public health studies of epidemic diseases. In this thesis, we study the fundamental properties of human contact graphs in order to characterize how people meet one another in different social environments. Understanding human contact patterns in return allows us to propose a cost-effective routing algorithm for spreading information in Delay Tolerant Networks. Furthermore, we propose several contact predictors to predict the unobserved parts of contact graphs when only partial observations are available. Our results show that we are able to infer hidden contacts of real contact traces by exploiting the underlying properties of contact graphs. In the last few years, we have also witnessed an explosion in the number of people who use social media to share information with their friends. In the last part of this thesis, we study the running times of several information spreading algorithms in social networks in order to find the fastest strategy. Fast information spreading has an obvious application in advertising a product to a large number of people in a short amount of time. We prove that a fast information spreading algorithm should efficiently identify communication bottlenecks in order to speed up the running time. Finally, we show that sparsifying large social graphs by exploiting the edge-betweenness centrality measure can also speed up the information spreading rate.
Graduate