Problemes de tournees multicriteres dans des graphes

This thesis studies various multiple objective routing problems. As opposed to classical monocriterion optimization, where an optimal solution exists, multicriteria optimization problems usually involve a trade-off among conflicting objectives. The decision maker must therefore formulate his preferred objectives, a concept introduced several decades ago in utility theory developed in economics. The way those preferences are revealed directly impacts the way a problem is tackled. When the preferences are known before the optimization process, one may reformulate the original multicriteria problem into a monocriterion one. For example, the objectives might be aggregated into a generalized cost function. Clearly, this is impossible if the preferences are known only at the end of the optimization process. In this case, the optimal solution concept is replaced by an efficiency concept that allows one to identify a set of equally desirable solutions, whatever the preferences of the decision maker are. These solutions are represented by the Pareto front in the objective space.;Our second problem is the Traveling Salesman Problem with Profits (TSPP) a variant of the Traveling Salesman Problem in which a profit or prize value is associated with each vertex. The goal here is to visit a subset of vertices while addressing two conflicting objectives: maximize the collected prize and minimize the travel costs. We first consider a variant of the TSPP in which a minimum amount of profit must be collected by a minimum cost elementary cycle. As for our travel planning problem, this monocriterion variant of the TSPP assumes that the decision maker's preferences are known a priori. We have developed a branch-and-cut algorithm based on valid inequalities from cuts designed for the Orienteering Problem and from existing polyhedral results. Computational results on instances with more than 500 vertices are reported.;We also address the TSPP in a context where the decision maker's preferences remain unknown until the end of the optimization process. We describe an exact &epsis;-constraint method for bi-objective combinatorial optimization problems with integer objective values. This method tackles multicriteria optimization problems by solving a series of single objective subproblems, where all but one objectives are transformed into constraints. We show that the Pareto front of bi-objective problems can be efficiently generated with the &epsis;-constraint method. Furthermore, we describe heuristics based on information gathered from previous subproblems that significantly speed up the method. We report the first exact results for the TSPP on instances derived from classical vehicle routing and traveling salesman problem instances. Results on approximations of the Pareto front obtained from a variant of our exact algorithm are also reported.;Key words: Multicriteria optimization, Time-dependant shortest paths, Traveling Salesman Problem with Profits, Branch-and-cut, Pareto Front, &epsis;-constraint problem.;Two multicriteria routing problems are addressed in this thesis and we consider situations where the decision maker's preferences are known before or after the optimization process. The first problem cornes from the travel industry where an optimal travel plan must be found according to the traveler's preferences. Given a predetermined itinerary, the problem consists in finding the best travel plan, involving planes and hotels, based on the traveler's preferences. Our time-dependent framework models plane flights, hotels, stays in each city as well as global time constraints. The travel planning problem is solved by computing time-dependent shortest paths through a fixed sequence of nodes. Given the large size of time-dependent networks, an exact decomposition algorithm is devised to solve instances of realistic size in reasonable computation times.