General routing problems deal with transporting some commodities and/or travelling along the axes of a given network in some optimal manner. In the modern world such problems arise in several contexts such as distribution of goods, transportation of commodities and/or people etc.In this thesis we focus on two classical routing problems, namely the Travelling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP). The TSP can be described as a salesman travels from his home city, visits each of the other ( n - 1) cities exactly once and returns back to the home city such that the total distance travelled by him is minimised. The VRP may be stated as follows: A set of n customers (with known locations and demands for some commodity) is to be supplied from a single depot using a set of delivery vehicles each with a prescribed capacity. A delivery route starts from the depot, visits some customers and returns back to the depot. The VRP is to determine the delivery routes for each vehicle such that the total distance travelled by all the vehicles is minimised.These routing problems are simple to state in terms of describing them in words. But they are very complex in terms of providing a suitable mathematical formulation and a valid procedure to solve them. These routing problems are simple to state in terms of describing them in words. But they are very complex in terms of providing a suitable mathematical formulation and a valid procedure to solve them. These problems belong to the class of NP-hard (Non- deterministic Polynomial) problems. With the present knowledge, it is believed that the problems in NP-hard are unlikely to have any good algorithms to arrive at optimal solutions to a general problem. Hence researchers have focused their effort on; (i) developing exact algorithms to solve as large size problems as possible; (ii) developing heuristics to produce ++ / near optimal solutions.The exact algorithms for such problems have not performed satisfactorily as they need an enormous amount of computational time to solve moderate size problems. For instance, in the literature, TSP of size 225-city, 4461-city and 7397-city were solved using computational time of 1 year, 1.9 years and 4 years respectively (Junger et al., 1995). Thus heuristics, in particular the probabilistic methods such as tabu search, play a significant role in obtaining near optimal solutions. In the literature there is very little comparison between the various exact algorithms and heuristics. (Very often the real-life problems are too large and no optimal solution can be found in a reasonable time.)One of the problems with a probabilistic heuristic is that different implementations (runs) of the same probabilistic heuristic on a given problem may produce distinct solutions of different quality. Thus the desired quality and reproducibility of the solution cannot be ensured. Furthermore, the performance of the heuristics on the benchmark problems provide no Guarantee of the quality of solutions that can be obtained for the problem faced by a researcher. Most of the documentation on the performance of heuristics in literature problems provides no information regarding the computational effort (CPU time) spent in obtaining the claimed solution, reproducibility of the claimed solution and the hardware environment of the implementation. This thesis focuses on some of these deficiencies.Most of the heuristics for general combinatorial optimisation problems are based on neighbourhood search methods. This thesis explores and provides a formal setup for defining neighbourhood structures, definitions of local optimum and global optimum. Furthermore it highlights the dependence and drawbacks of such methods on the neighbourhood structure.It is necessary to emphasise ++ / the need for a statistical analysis of the output to be part of any such probabilistic heuristic. Some of the statistical tools used for the two probabilistic heuristics for TSP and VRP are developed. Furthermore, these heuristics axe part of a bigger class called tabu search heuristics for combinatorial optimisation problems. Hence it includes an overview of the TSP, VRP and tabu search methods in Chapters 2, 3 and 4 respectively. Subsequently in Chapters 5, 6, 7 and 8 ideas of neighbourhood structure, local optimum etc. are developed and the required statistical analysis for some heuristics on the TSP and VRP is demonstrated. In Chapter 9, the conclusion of this thesis is drawn and the direction of future work is outlined. The following is a brief outline of the contribution of this thesis.In Chapter 5, the ideas of neighbourhood structure, local optimum, global optimum and probabilistic heuristics for any combinatorial optimisation problem sare developed. The drawbacks of the probabilistic heuristics for such problems axe highlighted. Furthermore, the need to select the best heuristic on the basis of testing a statistical hypothesis and related statistical analysis is emphasised.Chapter 6 illustrates some of the ideas presented in Chapter 5 using the GENIUS algorithm proposed for the TSP. Statistical analysis is performed for 36 variations of GENIUS algorithm based on different neighbourhood parameters, different types of insertion methods used and two types of constructions of starting solutions. The analysis is performed on 27 literature problems with size ranging from 100 cities to 532 cities and 20 randomly generated problems with size ranging from 100 cities to 480 cities. In both cases the best heuristic is selected. Furthermore, the fitting of the Weibull Distribution to the objective function values of the heuristic solutions provides an estimate of the ++ / optimal objective function value and a corresponding confidence interval for both the literature and randomly generated problems. In both cases the estimate of the optimal objective function values are within 8.2% of the best objective function value known.Since the GENIUS algorithm proved to be efficient, a hybrid heuristic for the TSP combining the branch and bound method and GENIUS algorithm to solve large dimensional problems is proposed. The algorithm is tested on both the literature problems with sizes ranging from 575 cities to 724 cities and randomly generated problems with sizes ranging from 500 cities to 700 cities. Though problems could not be solved to optimality within the 10 hours time limit, solutions were found within 2.4% of the best known objective function value in the literature.In Chapter 7, a similar statistical analysis for the TABUROUTE algorithm proposed for the VRP is conducted. The analysis is carried out based on the different neighbourhood parameters and tested using 14 literature problems with sizes ranging from 50 cities to 199 cities and 49 randomly generated problems with sizes ranging from 60 cities to 120 cities. In both sets of the problems, the statistical tests accepted the hypothesis that there is no significant difference in the solution produced between the various parameters used for the TABUROUTE algorithm. By fitting the Weibull distribution to the objective function values of the local optimal solutions, the optimal objective function value and a corresponding confidence intervals for each problem is estimated. These estimates give values that are to within 6.1% and 18.3% of the best known values for the literature problems and randomly generated problems respectively.In Chapter 8, the general neighbourhood search method for a general combinatorial optimisation problem is presented. Very often, the neighbourhood structure ++ / can be defined suitably only on a superset S of the set of feasible solutions S. Thus the solutions in SS are infeasible. Several questions axe posed regarding the computational complexity of the solution space of a problem. These concepts are illustrated on the 199-city CDVRP, using the TABUROUTE algorithm.In addition, the idea of complexity of the solution space based on the samples collected over the 140 runs is explored. Some of the data collected include the number of solutions with distance and/or capacity feasible, the number of feasible neighbourhood solutions encountered for one run, etc. Questions such asHow many solutions are there for the 199-city problem ?How many numbers of local minima solutions are there for the 199-city problem?What is the size of the feasible region for the 199-city problem?are answered. Finally, the conclusion is drawn that this problem cannot be used as a benchmark based on the size of the feasible region and too many local minima.The conclusion of this thesis and directions of future work are discussed in Chapter 9. There are two appendices presented at the end of the thesis. Appendix A presents the details of the Friedman test, the expected utility function test and the estimation of the optimal objective function value based on the Weibull distribution. Appendix B presents a list of tables from Chapters 6, 7 and 8.

No description available.

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.

L'efficacité du transport des marchandises en ville est un sujet complexe préoccupant les autorités locales depuis de nombreuses années. Les enjeux sont immenses, une meilleure organisation du trafic devant permettre d'augmenter la sécurité, réduire les nuisances, minimiser les coûts. La Logistique Urbaine vise à concevoir des systèmes de distribution des marchandises en ville permettant d'acheminer les flux dans les meilleures conditions à la fois pour la communauté et les transporteurs. Cette thèse se deroule dans le cadre du projet ANR MODUM qui propose un système basé sur un anneau de Centres de Distribution Urbains (CDU) situés autour d'une ville. La première partie étudie ce système d'un point de vue stratégique et tactique. Le Multicommodity-Ring Location Routing Problem aborde les décisions concernants l'installation et la connexion en anneau des CDU en simplifiant les détails plus tactiques. Trois méthodes ont été developpées et testées sur un jeu d'instances exhaustif se révélant très efficaces. The Multicommodity-Ring Vehicle Routing Problem est le problème dérivé que l'on obtient quand l'anneau est fixé. Une approche de type Branch&Price est proposée pour ce problème. La deuxième partie porte sur le Vehicle Routing Problem with Intermediate Replenishment Facilities, un problème plus tactique qui se produit dans un système logistique lorsque les véhicules peuvent se recharger auprès des points de remplissage et effectuer plusieurs tournées lors d'une même journée. Plusieurs algorithmes exacts ont été developpés et testés. Les résultats obtenus sur des jeux d'instances tirés de la littérature sont prometteurs. / Urban freight transport is a matter of increasing concern in the economic, commercial, social and environmental operations of our cities, due to the constantly increasing growth and urbanization of the civilization. An improved managem ent of the traffic related to the freight transport can have a positive impact in many respects : security, congestion of the road network, noise and air pollution, costs. City Logistics studies the dynamic management of urban freight transport in order to deliver distribution systems solutions that may be suitable for both the community and freight carriers. This thesis originates from the ANR Project MODUM, which proposes a freight distribution system based on a ring of Urban Distribution Centers (UDCs) located in the outskirts of a city. In the first part, this system is studied from both a strategic and a tactical point of view. The Multicommodity-Ring Location Routing Problem (MRLRP) considers long-term decisions, i.e. the installation of the UDCs and the ring connection, without disregarding more tactical aspects. The MRLRP has been tackled by three solution methods, which proved effective on a large set of test instances. In the second part of the thesis, the Vehicle Routing Problem with Intermediate Replenishment Facilities (VRPIRF) is studied. The VRPIRF is a more tactical problem that arises in City Logistics each time both the multi-trip and the multi-depot features, i.e. the possibility for a vehicle to be reloaded at one of a set of facilities, are present. Several exact algorithms, namely two of type Branch&Cut and two of type Branch& Price, have been developed for this problem. computational experiments on benchmark instances taken from the literature have been conducted to assess their performance, leading to very promising results.

This paper considers a real world waste collection problem in which glass, metal, plastics, or paper is brought to certain waste collection points by the citizens of a certain region. The collection of this waste from the collection points is therefore a node routing problem. The waste is delivered to special sites, so called intermediate facilities (IF), that are typically not identical with the vehicle depot. Since most waste collection points need not be visited every day, a planning period of several days has to be considered. In this context three related planning problems are considered. First, the periodic vehicle routing problem with intermediate facilities (PVRP-IF) is considered and an exact problem formulation is proposed. A set of benchmark instances is developed and an efficient hybrid solution method based on variable neighborhood search and dynamic programming is presented. Second, in a real world application the PVRP-IF is modified by permitting the return of partly loaded vehicles to the depots and by considering capacity limits at the IF. An average improvement of 25% in the routing cost is obtained compared to the current solution. Finally, a different but related problem, the so called multi-depot vehicle routing problem with inter-depot routes (MDVRPI) is considered. In this problem class just a single day is considered and the depots can act as an intermediate facility only at the end of a tour. For this problem several instances and benchmark solutions are available. It is shown that the algorithm outperforms all previously published metaheuristics for this problem class and finds the best solutions for all available benchmark instances.

This dissertation focuses on supply chain design and logistics problems with emphasis on biomass logistics and routing problems. In biomass logistics, we have studied problems arising in a switchgrass-based bio-ethanol supply chain encountered in the Southeast, and a corn stover harvest scheduling problem faced in the Midwest Unites States, both pertaining to the production of cellulosic ethanol. The main contributions of our work have been in introducing new problems to the literature that lie at the interface of the lot-sizing and routing problems, and in developing effective exact algorithms for their solution. In the routing area, we have addressed extensions of the well-known traveling salesman and vehicle routing problems. We have proposed new formulations and have developed exact algorithms for the single and multiple asymmetric traveling salesmen problems (ATSP and mATP), the high-multiplicity asymmetric traveling salesman problem (HMATSP) and its extensions, and the fixed-destination multi-depot traveling salesman problem with load balancing (FD-MTSPB). Furthermore, we have introduced a new strategy to reduce routing cost in the classical vehicle routing problem (VRP). / Ph. D.

De nos jours, le transport joue un rôle clé dans la vie des pays modernes, en particulier pour les flux de marchandises. La logistique des flux entre régions, pays et continents a bénéficié d’innovations technologiques et organisationnelles assurant efficacité et efficience. Il n’en a pas été de même à l’échelle urbaine, plus particulièrement dans les centres-villes : la gestion des flux dans un environnement caractérisé par une forte densité démographique n’a pas encore véritablement trouvé son modèle d’organisation. Aujourd’hui, la logistique urbaine ou encore la gestion "du dernier kilomètre" constitue donc un enjeu de premier plan, tant socio politique et environnemental qu’économique. La logistique urbaine est caractérisée par la présence de plusieurs acteurs (chargeurs ou propriétaires de marchandises, clients, transporteurs, autorités publiques, …) ayant chacun des priorités différentes (réduction de la pollution, amélioration de la qualité de service, minimisation de la distance totale parcourue, …). Pour relever ces défis, un des leviers possibles consiste à optimiser les tournées de distribution et/ou collecte de marchandises, dans le contexte et sous les contraintes de la ville.Le but de ce travail de thèse réside alors dans la planification de la distribution des marchandises dans un réseau logistique, abordée sous un angle de collaboration entre les chargeurs. Cette collaboration consiste à regrouper les demandes de divers chargeurs pour optimiser le taux de chargement des camions et obtenir de meilleurs prix de transport. Ici, la gestion du « dernier kilomètre » s’apparente à ce que l’on identifie dans la littérature comme le Pickup and Delivery Problem (PDP). Dans le cadre de cette thèse, nous nous intéressons à des variantes de ce problème plus adaptées au contexte urbain. Après avoir réalisé un état de l’art sur les problèmes d’optimisation combinatoire autour du transport et les méthodes utilisées pour leur résolution, nous étudions deux nouvelles variantes du problème de collecte et de livraison : le Selective PDP with Time Windows and Paired Demands et le Multi-periods PDP with Time Windows and Paired Demands. La première permet aux transporteurs de livrer le maximum de clients dans une journée par exemple ; avec la seconde, et en cas d’impossibilité de livraison dans cette période, on détermine la meilleure date de livraison en minimisant la distance parcourue. Chacune d’elles fait l’objet d’une description formelle, d’une modélisation mathématique sous forme de programme linéaire, puis d’une résolution par des méthodes exacte, heuristiques et métaheuristiques, dans des cas mono-objectif et multi-objectifs. La performance de chaque approche a été évaluée par un nombre substantiel de tests sur des instances de différentes tailles issues de la littérature et/ou que nous avons générées. Les avantages et les inconvénients de chaque approche sont analysés, notamment dans le cadre de la collaboration entre chargeurs. / Nowadays, transportation plays a key role in our modern countries’life, in particular for the goods flows. The logistics of flows between regions, countries and continents have benefited from technological and organizational innovations ensuring efficiency and effectiveness. It has not been the same at the urban scale, especially in city centers: the management of flows in a high population density environment has not yet found its organizational model. Today, urban logistics or "last mile" management is therefore a major issue, both socio-political and environmental as well as economic. Urban logistics is characterized by several actors (shippers or owners of goods, customers, carriers, public authorities, ...) each with different priorities (reduction of pollution, improvement of service quality, minimization of total distance traveled, ...). To overcome these challenges, one possible lever is to optimize the distribution and/or collection of goods in the context and under the constraints of the city.The goal of this PhD work is then to plan the distribution of goods in a logistics network, approached from a collaboration angle between shippers. This collaboration consists in grouping the demands of several shippers to optimize the loading rate of the trucks and to obtain better transport prices. Here, managing the "last mile" is similar to what is known in the literature as the Pickup and Delivery Problem (PDP). In this thesis, we are interested in variants of this problem more adapted to the urban context. After having realized a state of the art on the combinatorial optimization problems around the transport and the methods used for their resolution, we study two new variants of the problem of collection and delivery: the Selective PDP with Windows and Paired Demands and the Multi-period PDP with Windows and Paired Demands. The first allows carriers to deliver the maximum number of customers in a day for example; with the second, and in case of impossibility of delivery in this period, we determine the best delivery date by minimizing the distance traveled. Each of them is the subject of a formal description, of a mathematical modeling in the form of a linear program, then of a resolution by exact methods, heuristics and metaheuristics, in single-objective and multi-objective cases. The performance of each approach was evaluated by a substantial number of tests on instances of different sizes from the literature and / or that we generated. The advantages and drawbacks of each approach are analyzed, in particular in the context of collaboration between shippers.

Stochastic combinatorial optimization problems are combinatorial optimization problems where part of the problem data are probabilistic. The focus of this thesis is on stochastic routing problems, a class of stochastic combinatorial optimization problems that arise in distribution management. Stochastic routing problems involve finding the best solution to distribute goods across a logistic network. In the problems we tackle, we consider a setting in which the cost of a solution is described by a random variable; the goal is to find the solution that minimizes the expected cost. Solving such stochastic routing problems is a challenging task because of two main factors. First, the number of possible solutions grows exponentially with the instance size. Second, computing the expected cost of a solution is computationally very expensive. <br> To tackle stochastic routing problems, stochastic local search algorithms such as iterative improvement algorithms and metaheuristics are quite promising because they offer effective strategies to tackle the combinatorial nature of these problems. However, a crucial factor that determines the success of these algorithms in stochastic settings is the trade-off between the computation time needed to search for high quality solutions in a large search space and the computation time spent in computing the expected cost of solutions obtained during the search. <br> To compute the expected cost of solutions in stochastic routing problems, two classes of approaches have been proposed in the literature: analytical computation and empirical estimation. The former exactly computes the expected cost using closed-form expressions; the latter estimates the expected cost through Monte Carlo simulation. <br> Many previously proposed metaheuristics for stochastic routing problems use the analytical computation approach. However, in a large number of practical stochastic routing problems, due to the presence of complex constraints, the use of the analytical computation approach is difficult, time consuming or even impossible. Even for the prototypical stochastic routing problems that we consider in this thesis, the adoption of the analytical computation approach is computationally expensive. Notwithstanding the fact that the empirical estimation approach can address the issues posed by the analytical computation approach, its adoption in metaheuristics to tackle stochastic routing problems has never been thoroughly investigated. <br> In this thesis, we study two classical stochastic routing problems: the probabilistic traveling salesman problem (PTSP) and the vehicle routing problem with stochastic demands and customers (VRPSDC). The goal of the thesis is to design, implement, and analyze effective metaheuristics that use the empirical estimation approach to tackle these two problems. The main results of this thesis are: 1) The empirical estimation approach is a viable alternative to the widely-adopted analytical computation approach for the PTSP and the VRPSDC; 2) A principled adoption of the empirical estimation approach in metaheuristics results in high performing algorithms for tackling the PTSP and the VRPSDC. The estimation-based metaheuristics developed in this thesis for these two problems define the new state-of-the-art.

A just-in-time supply pickup and delivery system (JSS) manages the logistic operations between a manufacturing plant and its suppliers by controlling the sequence, timing, and frequency of container pickups and parts deliveries, thereby coordinating internal conveyance, external conveyance, and the operation of cross-docking facilities. The system is important to just-in-time production lines that maintain small inventories. This research studies the logistics, supply chain, and production control of JSS. First, a new meta-heuristics approach (taboo search) is developed to solve a general frequency routing (GFR) problem that has been formulated in this dissertation with five types of constraints: flow, space, load, time, and heijunka. Also, a formulation for cross-dock routing (CDR) has been created and solved. Second, seven issues concerning the structure of JSS systems that employ the previously studied common frequency routing (CFR) problem (Chuah and Yingling, in press) are explored to understand their impacts on operational costs of the system. Finally, a discreteevent simulation model is developed to study JSS by looking at different types of variations in demand and studying their impacts on the stability of inventory levels in the system. The results show that GFR routes at high frequencies do not have common frequencies in the solution. There are some common frequencies at medium frequencies and none at low frequency, where effectively the problem is simply a vehicle routing problem (VRP) with time windows. CDR is an extension of VRP-type problems that can be solved quickly with meta-heuristic approaches. GFR, CDR, and CFR are practical routing strategies for JSS with taboo search or other types of meta-heuristics as solvers. By comparing GFR and CFR solutions to the same problems, it is shown that the impacts of CFR restrictions on cost are minimal and in many cases so small as to make simplier CFR routes desirable. The studies of JSS structural features on the operating costs of JSS systems under the assumption of CFR routes yielded interesting results. First, when suppliers are clustered, the routes become more efficient at mid-level, but not high or low, frequencies. Second, the cost increases with the number of suppliers. Third, negotiating broad time windows with suppliers is important for cost control in JSS systems. Fourth, an increase or decrease in production volumes uniformly shifts the solutions cost versus frequency curve. Fifth, increased vehicle capacity is important in reducing costs at low and medium frequencies but far less important at high frequencies. Lastly, load distributions among the suppliers are not important determinants of transportation costs as long as the average loads remain the same. Finally, a one-supplier, one-part-source simulation model shows that the systems inventory level tends to be sticky to the reordering level. JSS is very stable, but it requires reliable transportation to perform well. The impact to changes in kanban levels (e.g., as might occur between route planning intervals when production rates are adjusted) is relatively long term with dynamic after-effects on inventory levels that take a long time to dissapate. A gradual change in kanban levels may be introduced, prior to the changeover, to counter this effect.

L’agriculture de précision est un mode de culture qui consiste à prendre en compte la variabilité intra-parcellaire afin d'appliquer le bon traitement au bon endroit. Depuis les années 80, l’agriculture de précision s’est développée grâce à l’arrivée d’outils de géolocalisation (GPS), de matériels permettant une gestion modulée des cultures et surtout d'une multitude de données issues de prélèvements sur le terrain, d'images et de capteurs. Dans ce contexte, l’agriculture de précision a fait émerger de nouveaux problèmes à la fois combinatoires et complexes afin de répondre à des enjeux de performance économique, technique et environnementale.Cette thèse porte sur l'utilisation de la programmation par contraintes pour résoudre des problèmes de tournées dans le contexte de l’agriculture de précision et, plus précisément, en viticulture de précision.Un problème de tournées de véhicule consiste à déterminer une flotte de véhicules afin de visiter une liste de clients ou de réaliser des tournées d’interventions. Le but est de minimiser le coût total des tournées tout en respectant différentes contraintes. Ce problème est une extension classique du problème du voyageur de commerce et fait partie des problèmes NP-difficiles.La programmation par contraintes est un outil très puissant capable de résoudre des problèmes combinatoires comme les problèmes de tournées. Elle fournit des algorithmes de filtrage dédiés à des contraintes de circuits qui permettent de résoudre de façon efficace des problèmes associant ces contraintes de circuit à d'autres contraintes plus spécifiques.La première contribution de cette thèse est la formalisation du problème de la vendange sélective et sa modélisation sous la forme d’un problème d’optimisation sous contraintes. Le problème de la vendange sélective consiste à trouver la trajectoire optimale d’une machine à vendanger qui récolte et sépare deux qualités de raisins. En plus d’être un problème de tournées peu commun, la gestion du remplissage simultané des deux bacs augmente la combinatoire du problème. Plusieurs modèles sont présentés et testés sur des données réelles provenant de vignobles situés dans le sud de la France.La deuxième contribution est l’établissement d’une nouvelle contrainte globale de tournées nommée WeightedSubCircuits. Elle permet d'aborder le problème plus général de tournées multiples dans lequel on cherche à couvrir une partie du graphe par un ensemble de circuits disjoints de coût minimal. Un algorithme de filtrage partiel de cette contrainte est également présenté. Des expérimentations ont été réalisées, notamment sur un problème de planning de techniciens intervenant sur des vignobles en Californie qui a été modélisé dans le cadre de cette thèse. Ces résultats préliminaires ont montré l'intérêt du filtrage apporté par cette nouvelle contrainte. / L’agriculture de précision est un mode de culture qui consiste à prendre en compte la variabilité intra-parcellaire afin d'appliquer le bon traitement au bon endroit. Depuis les années 80, l’agriculture de précision s’est développée grâce à l’arrivée d’outils de géolocalisation (GPS), de matériels permettant une gestion modulée des cultures et surtout d'une multitude de données issues de prélèvements sur le terrain, d'images et de capteurs. Dans ce contexte, l’agriculture de précision a fait émerger de nouveaux problèmes à la fois combinatoires et complexes afin de répondre à des enjeux de performance économique, technique et environnementale.Cette thèse porte sur l'utilisation de la programmation par contraintes pour résoudre des problèmes de tournées dans le contexte de l’agriculture de précision et, plus précisément, en viticulture de précision.Un problème de tournées de véhicule consiste à déterminer une flotte de véhicules afin de visiter une liste de clients ou de réaliser des tournées d’interventions. Le but est de minimiser le coût total des tournées tout en respectant différentes contraintes. Ce problème est une extension classique du problème du voyageur de commerce et fait partie des problèmes NP-difficiles.La programmation par contraintes est un outil très puissant capable de résoudre des problèmes combinatoires comme les problèmes de tournées. Elle fournit des algorithmes de filtrage dédiés à des contraintes de circuits qui permettent de résoudre de façon efficace des problèmes associant ces contraintes de circuit à d'autres contraintes plus spécifiques.La première contribution de cette thèse est la formalisation du problème de la vendange sélective et sa modélisation sous la forme d’un problème d’optimisation sous contraintes. Le problème de la vendange sélective consiste à trouver la trajectoire optimale d’une machine à vendanger qui récolte et sépare deux qualités de raisins. En plus d’être un problème de tournées peu commun, la gestion du remplissage simultané des deux bacs augmente la combinatoire du problème. Plusieurs modèles sont présentés et testés sur des données réelles provenant de vignobles situés dans le sud de la France.La deuxième contribution est l’établissement d’une nouvelle contrainte globale de tournées nommée WeightedSubCircuits. Elle permet d'aborder le problème plus général de tournées multiples dans lequel on cherche à couvrir une partie du graphe par un ensemble de circuits disjoints de coût minimal. Un algorithme de filtrage partiel de cette contrainte est également présenté. Des expérimentations ont été réalisées, notamment sur un problème de planning de techniciens intervenant sur des vignobles en Californie qui a été modélisé dans le cadre de cette thèse. Ces résultats préliminaires ont montré l'intérêt du filtrage apporté par cette nouvelle contrainte.