During the last half century there has been a resurgence of interest in Monge's 18th century mass transportation problem, with most of the activity limited to continuous spaces. This thesis, consequently, develops techniques based on mass transportation for the purpose of obtaining tight concentration inequalities in a discrete setting. Such inequalities on n-fold products of graphs, equipped with product measures, have been well investigated using combinatorial and probabilistic techniques, the most notable being martingale techniques. The emphasis here, is instead on the analytic viewpoint, with the precise contribution being as follows. We prove that the modified log-Sobolev inequality implies the transportation inequality in the first systematic comparison of the modified log-Sobolev inequality, the Poincar inequality, the transportation inequality, and a new variance transportation inequality. The duality shown by Bobkov and Gtze of the transportation inequality and a generating function inequality is then utilized in finding the asymptotically correct value of the subgaussian constant of a cycle, regardless of the parity of the length of the cycle. This result tensorizes to give a tight concentration inequality on the discrete torus. It is interesting in light of the fact that the corresponding vertex isoperimetric problem has remained open in the case of the odd torus for a number of years. We also show that the class of bounded degree expander graphs provides an answer, in the affirmative, to the question of whether there exists an infinite family of graphs for which the spread constant and the subgaussian constant differ by an order of magnitude. Finally, a candidate notion of a discrete Ricci curvature for finite Markov chains is given in terms of the time decay of the Wasserstein distance of the chain to its stationarity. It can be interpreted as a notion arising naturally from a standard coupling of Markov chains. Because of its natural definition, ease of calculation, and tensoring property, we conclude that it deserves further investigation and development. Overall, the thesis demonstrates the utility of using the mass transportation problem in discrete isoperimetric and functional inequalities.

Le concept de réserve voie a été présenté comme une stratégie de gestion du trafic et a de nombreuses applications dans la vie réelle. Des études antérieures dans la littérature se concentrent principalement sur l'impact de la réservation de la voie dans une région locale du réseau de transport. Dans cette thèse, les problèmes de réservation de voies sont étudiés dans le but de minimiser l'impact sur le trafic total par la réservation optimale des voies dans un réseau de transport. Nous avons d’abord se concentrer sur le problème de réservation de voie (LRP) pour le transport automatisé pour les poids lourds avec temps de déplacement statique. Ce travail est généralisé au problème de réservation voies avec une capacité limitée de la voie (CLRP) pour les grands événements spéciaux. Enfin, le problème de réservation de voies avec le temps de déplacement dépendant du temps (LRP-TT), et le problème de réservation voies avec la vitesse de déplacement dépendant du temps (LRP-TS) sont étudiés. Pour chacun des problèmes étudiés, les modèles mathématiques appropriés sont formulés, leurs complexités sont démontrées. Différentes méthodes de résolution sont explorées, y compris exacte cut-and-solve méthode, cut-and-solve et méthod de coupe combinée, et la méthode de recherche tabou. Les performances des algorithmes proposés sont évaluées par des instances générées au hasard. Les résultats numériques ont montré que les algorithmes proposés sont plus efficaces pour résoudre les problèmes étudiés que le logiciel commercial référence CPLEX / The concept of lane reservation has been introduced as a traffic management strategy and has many applications in real life. Previous studies in the literature mainly focus on the impact of lane reservation in a local region of transportation network. In this thesis optimal lane reservation problems are studied with the objective to minimize impact on total traffic by optimally setting reserved lanes in a transportation network. We firstly focus on the lane reservation problem (LRP) for automated truck freight transportation with static link travel time. This primary work has been extended to the capacitated lane reservation problem (CLRP) for large-scale special events. Finally, lane reservation problem with time-dependent travel time (TTLRP), and lane reservation problem with time-dependent travel speed (TSLRP) are studied. For each of the considered problems, appropriate mathematical models are formulated, their complexities are demonstrated. Different resolution methods are explored including exact cut-and-solve method, cut-and-solve and cutting plane combined method, and Tabu-search method. The performance of the proposed algorithms is evaluated by randomly generated instances. Numerical results have shown that the proposed algorithms are more effective to solve the considered problems than the reference commercial package CPLEX

A multi-commodity flow problem consists of moving several commodities from their respective sources to their sinks through a network where each edge has different costs and capacity constraints. This paper explores different linear programming algorithms and their performance regarding finding an optimal solution for multi-commodity flow problems. By testing several of different network constraints, we examine which algorithms are most suitable for specific network and problem structures. Furthermore, we implement our own multi-commodity solver and compare its performance against state-of-the-art linear programming solvers. The results show that for the methods we tested it is difficult to discern which class of linear programming methods are optimal solvers for multi-commodity flow problems and that their performance depends on how the network and commodities are structured.

Wong Chi Fat. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 107-115). / Abstracts in English and Chinese. / List of Tables --- p.ix / List of Figures --- p.x / Chapter 1. --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Literature Review --- p.3 / Chapter 1.2.1 --- Shortest Path Problem --- p.4 / Chapter 1.2.2 --- Vehicle Routing Problem with Time Windows --- p.6 / Chapter 1.3 --- Thesis Outline --- p.9 / Chapter 2. --- Time-varying Shortest Path with Constraints in a 2-level Network --- p.11 / Chapter 2.1 --- Introduction --- p.11 / Chapter 2.2 --- Problem Formulation of TCSP --- p.12 / Chapter 2.3 --- Arbitrary Waiting Time --- p.13 / Chapter 2.4 --- TCSP in a 2-level Network --- p.15 / Chapter 2.4.1 --- Problem Formulation of TCSP in a 2-level Network --- p.17 / Chapter 2.5 --- Algorithms Solving TCSP in a 2-level Network --- p.20 / Chapter 2.5.1 --- Exact Algorithm --- p.21 / Chapter 2.5.2 --- Heuristic Algorithm --- p.23 / Chapter 2.6 --- Concluding Remarks --- p.30 / Chapter 3. --- Vehicle Routing Problem with Time Windows and Stochastic Travel Times --- p.32 / Chapter 3.1 --- Introduction --- p.32 / Chapter 3.2 --- Problem Formulation --- p.34 / Chapter 3.3 --- General Branch-and-cut Algorithm --- p.42 / Chapter 3.4 --- Modified Branch-and-cut Algorithm --- p.44 / Chapter 3.4.1 --- Prefixing --- p.45 / Chapter 3.4.2 --- Directed Partial Path Inequalities --- p.47 / Chapter 3.4.3 --- Exponential Smoothing --- p.50 / Chapter 3.4.4 --- Fast Fathoming --- p.54 / Chapter 3.4.5 --- Modified Branch-and-cut algorithm --- p.56 / Chapter 3.5 --- Computational Analysis --- p.57 / Chapter 3.5.1 --- "Performance of Prefixing, Direct Partial Path Inequalities and Exponential Smoothing" --- p.57 / Chapter 3.5.2 --- Performance of Fast Fathoming --- p.63 / Chapter 3.5.3 --- Summary of Computational Analysis --- p.67 / Chapter 3.6 --- Concluding Remarks --- p.67 / Chapter 4. --- System Features and Implementation --- p.69 / Chapter 4.1 --- Introduction --- p.59 / Chapter 4.2 --- System Features --- p.70 / Chapter 4.2.1 --- Map-based Interface and Network Model --- p.70 / Chapter 4.2.2 --- Database Management and Query --- p.73 / Chapter 4.3 --- Decision Support Tools --- p.75 / Chapter 4.3.1 --- Route Finding --- p.75 / Chapter 4.3.2 --- Delivery Planning --- p.77 / Chapter 4.4 --- System Implementation --- p.80 / Chapter 4.5 --- Further Development --- p.82 / Chapter 5. --- Vehicle Routing Software Survey / Chapter 5.1 --- Introduction --- p.83 / Chapter 5.2 --- Essential Features in CVRS Nowadays --- p.84 / Chapter 5.2.1 --- Common Features --- p.34 / Chapter 5.2.2 --- Advanced Features --- p.90 / Chapter 5.3 --- Concluding Remarks --- p.94 / Chapter 6. --- Summary & Future Work --- p.97 / Appendix A --- p.101 / Appendix B --- p.104 / Bibliography --- p.107

Vehicle Routing Problem with Time Windows is a hard optimization problem. Even though it has numerous practical applications, the question of solving it efficiently has not been satisfyingly solved yet. This thesis studies the Vehicle Routing Problem with Time Windows and presents several new algorithms for solving it. There are two heuristics presented here, as well as several more complex algorithms which use those heuristics as their components. The efficiency of presented techniques is evaluated experimentally using a set of test samples. As a part of this thesis, I have also developed a desktop application which implements presented algorithms and provides a few additional features useful for solving routing prob-lems in practice. Among others, there is a generator of pseudo-random problem instances and several visualization methods.

Nous nous intéressons dans cette thèse aux possibilités d’hybridation entre les méthodes exactes et les méthodes heuristiques afin de pouvoir tirer avantage de chacune des deux approches : optimalité de la résolution exacte, caractère moins déterministe et rapidité de la composante heuristique. Dans l’objectif de résoudre des problèmes NPdifficiles de taille relativement importante tels que les problèmes de transports, nous nous intéressons dans les deux dernières parties de ce mémoire à la conception de méthodes incomplètes basées sur ces hybridations. Dans la première partie, nous allons nous intéresser aux méthodes de résolution par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion des décisions de branchement, que nous appelons Dynamic Learning Search (DLS). Cette méthode définit de manière dynamique des règles de priorité pour la sélection des variables à chaque noeud et l’ordre des valeurs sur lesquelles brancher. Ces règles sont conçues dans une optique de généricité, de manière à pouvoir utiliser la méthode indépendamment du problème traité. Le principe général est de tenir compte par une technique d’apprentissage de l’impact qu’ont eu les décisions de branchement dans les parties déjà explorées de l’arbre. Nous évaluons l’efficacité de la méthode proposée sur deux problèmes classiques : un problème d’optimisation combinatoire et un problème à satisfaction de contraintes. La deuxième partie de ce mémoire traite des recherches à grand voisinage. Nous présentons un nouvel opérateur de voisinage, qui détermine par un algorithme de programmation dynamique la sous-séquence optimale d’un chemin dans un graphe. Nous montrons que cet opérateur est tout particulièrement destiné à des problèmes de tournées pour lesquels tous les noeuds ne nécessitent pas d’être visités. Nous appelons cette classe de problème les Problèmes de Tournées avec Couverture Partielle et présentons quelques problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent, à travers des tests expérimentaux conséquents, l’efficacité de l’opérateur que nous proposons en appliquant cette recherche à voisinage large sur deux problèmes, respectivement le Problème de l’Acheteur Itinérant (TPP) et le Problème de Voyageur de Commerce Généralisé (GTSP). Nous montrons alors que cet opérateur peut être combiné de manière efficace avec des métaheuristiques classiques, telles que des algorithmes génétiques ou des algorithmes d’Optimisation par Colonies de Fourmis. Enfin, la troisième partie présente des méthodes heuristiques basées sur un algorithme de Génération de Colonnes. Ces méthodes sont appliquées sur un problème complexe : le problème de Tournées de Véhicules avec Contraintes de Chargement à Deux Dimensions (2L-VRP). Nous montrons une partie des possibilités qu’il existe afin de modifier une méthode a priori exacte en une méthode heuristique et nous évaluons ces possibilités à l’aide de tests expérimentaux / We are interested in this thesis in the possibilities of hybridization between the exact methods and the methods heuristics to be able to take advantage of each of both approaches: optimality of the exact resolution, the less determinist character and the speed of the constituent heuristics. In the objective to resolve problems NP-hard of relatively important size such as the transportation problems, we are interested in the last two parts of this report in the conception of incomplete methods based on these hybridizations. In the first part, we are going to be interested in the methods of resolution by tree search. We introduce a new approach for the management of the decisions of connection, which we call Dynamic Learning Search ( DLS). This method defines in a dynamic way rules of priority for the selection of variables in every knot and the order of the values on which to connect. These rules are conceived in an optics of genericity, so as to be able to use the method independently of the treated problem. The general principle is to take into account by a technique of learning of the impact which had the decisions of connection in the parts already investigated in the tree. We estimate the efficiency of the method proposed on two classic problems: a combinatorial optimization problem and a constraints satisfaction problem. The second part of this report handles large neighborhood search. We present a new operator of neighborhood, who determines by an algorithm of dynamic programming the optimal sub-sequence of a road in a graph. We show that this operator is quite particularly intended for problems of tours for which all the vertices do not require to be visited. We call this class of problem the Problems of Tours with Partial Cover and present some problems being a part of this class. Chapters 3 and 4 show, through consequent experimental tests, the efficiency of the operator which we propose by applying this search to wide neighborhood on two problems, respectively the Traveling Purchaser Problem (TPP) and Generalized Traveling Salesman Problem ( GTSP). We show while this operator can be combined in a effective way with classic metaheuristics, such as genetic algorithms or algorithms of Ant Colony Optimization