O problema de escalonamento de veículos com múltiplas garagens (MDVSP, do inglês Multi-Depot Vehicle Scheduling Problem) é um problema clássico de logística e transportes. O MDVSP também é a base para a solução de vários problemas correlatos, tais como o problema de escalonamento de veículos em tempo-real e soluções integradas com o escalonamento de veículos, tais como o escalonamento da tripulação e otimização da tabela de horários. Desta forma, aprimorar a solução deste problema pode ser considerado de grande relevância, a qual permitirá resolver grandes instâncias reais de forma eficiente, bem como permitir a solução de problemas correlatos. O objetivo desta dissertação é verificar a aplicabilidade da utilização da rede tempo-espaço e do método de geração de colunas modificado proposto, para a solução deste problema, e de sua variante com frota heterogênea, considerando grandes instâncias. Diversos testes foram realizados utilizando o gerador de instâncias aleatórias com base na distribuição de demandas proposto. Grandes instâncias, envolvendo milhares de viagens (entre 500-10.000) e dezenas de garagens (4-128) são resolvidas em tempos razoáveis. / The multiple-depot vehicle-scheduling problem (MDVSP) is a classic logistic and transportation problem. The MDVSP is also a subproblem for solving various related problems, such as the real time vehicle scheduling problem, disruption management; and integrated problems such as the vehicle and crew scheduling problems. Although several mathematical and solution method have been developed in the literature, large instances (involving thousands of trips and several depots) are still difficult to solve in a reasonable time. The objective of this research work is to verify the applicability of the use of the space-time network towards obtaining good solutions for large instances in short time. Time-space network was suggested by Kliewer et al (2006), and it is positioned with respect to two-dimensional axes, one representing time and the other one space or stations. The arcs represent deadheading movements; and waiting periods in the same station. Solution methods for the MDVS combining time space with integer linear programming solvers and column generation were developed. Extensive testing was carried out using random generated instances, based on demands distribution. Large instances, involving thousands of trips (between 1,000-10,000) and dozen (4-64) depots, are solved in reasonable times.

O presente trabalho realiza o estudo e aplicação de um algoritmo de branch-and-price para a resolução de um problema de escalonamento de compressores. O problema é ligado à produção petrolífera, o qual consiste em definir um conjunto de compressores a serem ativados para fornecer gas de elevação a um conjunto de poços, atendendo toda demanda e minimizando os custos envolvidos. O problema é caracterizado por uma função objetivo não-convexa que é linearizada por partes de forma a ser formulada como um problema de programação inteira mista. A abordagem de geração de colunas é baseada na decomposição de Dantzig-Wolfe e apresenta melhores limitantes inferiores em relação à relaxação linear da formulação compacta. O branch-and-price é comparado ao solver CPLEX, sendo capaz de encontrar a solução ótima em menor tempo para um conjunto de instâncias, bem como melhores soluções factíveis para instâncias maiores em um período de tempo limitado. / This work presents the study and application of a branch-and-price algorithm for solving a compressor scheduling problem. The problem is related to oil production and consists of defining a set of compressors to be activated, supplying the gas-lift demand of a set of wells and minimizing the associated costs. The problem has a non-convex objective function, to which a piecewise-linear formulation has been proposed. This dissertation proposes a column generation approach based on the Dantzig-Wolfe decomposition, which achieves tighter lower bounds than the straightforward linear relaxation of the piecewise-linear formulation. The column generation was embedded in a branch-and-price algorithm and further compared with CPLEX, obtaining optimal solutions in lesser time for a set of instances. Further, the branch-and-price algorithm can find better feasible solutions for large instances under a limited processing time.

Nesta tese, estudamos o problema de Empacotamento de Bicliques. Um biclique é um grafo bipartido completo. No problema de Empacotamento de Bicliques são dados um inteiro k e um grafo bipartido G e deseja-se encontrar um conjunto de k bicliques, subgrafos de G, dois a dois disjuntos nos vértices, tal que a quantidade total de arestas dos bicliques escolhidos seja máxima. No caso em que k=1, temos o problema de Biclique máximo. Esses dois problemas possuem aplicações na área de Bioinformática. Mantemos neste trabalho um enfoque prático, no sentido de que nosso interesse é resolver instâncias desses dois problemas com tamanho razoavelmente grande. Para isso, utilizamos técnicas de Programação Linear Inteira. Para avaliar os métodos propostos aqui, mostramos resultados de experimentos computacionais feitos com instâncias vindas de aplicações e também com instâncias geradas aleatoriamente. / In this thesis, we study the Biclique Packing problem. A biclique is a complete bipartite graph. In the Biclique Packing problem we are given an integer k and a bipartite graph G and we want to find a set of k vertex disjoint bicliques of G, such that the total number of biclique\'s edges is maximum. When k=1, we have the Maximum Biclique problem. These two problems have applications in Bioinformatics. In this work we keep a practical focus, in the sense that we are interested in solving large size instances of these problems. To tackle these problems, we use Integer Linear Programming techniques. In order to evaluate the methods proposed here, we show results of computational experiments carried out with practical application\'s instances and also with randomly generated ones.

As the "network of network", the Internet has been playing a central and crucial role in modern society, culture, knowledge, businesses and so on in a period of over two decades by supporting a wide variety of network technologies and applications. However, due to its popularity and multi-provider nature, the future development of the Internet is limited to simple incremental updates. To address this challenge, network virtualization has been propounded as a potential candidate to provide the essential basis for the future Internet architecture. Network virtualization is capable of providing an open and flexible networking environment in which service providers are allowed to dynamically compose multiple coexisting heterogeneous virtual networks on a shared substrate network. Such a flexible environment will foster the deployment of diversified services and applications. A major challenge in network virtualization area is the Virtual Network Embedding (VNE), which aims to statically or dynamically allocate virtual nodes and virtual links on substrate resources, physical nodes and paths. Making effective use of substrate resources requires high-efficient and survivable VNE techniques. The main contribution of this thesis is two high-performance p-Cycle-based survivable virtual network embedding approaches. These approaches take advantage of p-Cycle-based protection techniques that minimize the backup resources while providing a full VN protection scheme against link and node failures.

O problema de escalonamento de veículos com múltiplas garagens (MDVSP, do inglês Multi-Depot Vehicle Scheduling Problem) é um problema clássico de logística e transportes. O MDVSP também é a base para a solução de vários problemas correlatos, tais como o problema de escalonamento de veículos em tempo-real e soluções integradas com o escalonamento de veículos, tais como o escalonamento da tripulação e otimização da tabela de horários. Desta forma, aprimorar a solução deste problema pode ser considerado de grande relevância, a qual permitirá resolver grandes instâncias reais de forma eficiente, bem como permitir a solução de problemas correlatos. O objetivo desta dissertação é verificar a aplicabilidade da utilização da rede tempo-espaço e do método de geração de colunas modificado proposto, para a solução deste problema, e de sua variante com frota heterogênea, considerando grandes instâncias. Diversos testes foram realizados utilizando o gerador de instâncias aleatórias com base na distribuição de demandas proposto. Grandes instâncias, envolvendo milhares de viagens (entre 500-10.000) e dezenas de garagens (4-128) são resolvidas em tempos razoáveis. / The multiple-depot vehicle-scheduling problem (MDVSP) is a classic logistic and transportation problem. The MDVSP is also a subproblem for solving various related problems, such as the real time vehicle scheduling problem, disruption management; and integrated problems such as the vehicle and crew scheduling problems. Although several mathematical and solution method have been developed in the literature, large instances (involving thousands of trips and several depots) are still difficult to solve in a reasonable time. The objective of this research work is to verify the applicability of the use of the space-time network towards obtaining good solutions for large instances in short time. Time-space network was suggested by Kliewer et al (2006), and it is positioned with respect to two-dimensional axes, one representing time and the other one space or stations. The arcs represent deadheading movements; and waiting periods in the same station. Solution methods for the MDVS combining time space with integer linear programming solvers and column generation were developed. Extensive testing was carried out using random generated instances, based on demands distribution. Large instances, involving thousands of trips (between 1,000-10,000) and dozen (4-64) depots, are solved in reasonable times.

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第17871号 / 工博第3780号 / 新制||工||1578(附属図書館) / 30691 / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 谷口 栄一, 教授 藤井 聡, 准教授 宇野 伸宏 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第19287号 / 工博第4084号 / 新制||工||1630(附属図書館) / 32289 / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 谷口 栄一, 教授 藤井 聡, 准教授 宇野 伸宏 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

Since Hurricane Katrina, extensive studies have been conducted aiming to optimize the transit vehicle routing in the event of an emergency evacuation. However, the vast majority of the studies focus on solving the deterministic vehicle routing problem that all the evacuation data are known in advance. These studies are generally not practical in dealing with real-world problems which involve considerable uncertainty in the evacuation data set. In this dissertation, a SmartEvac system is developed for dynamic vehicle routing optimization in emergency evacuation. The SmartEvac system is capable of processing dynamic evacuation data in real time, such as random pickup requests, travel time change, network interruptions. The objective is to minimize the total travel time for all transit vehicles. A column generation based online optimization model is integrated into the SmartEvac system. The optimization model is based on the following structure: a master problem model and a sub-problem model. The master problem model is used for routes selection from a restricted routes set while the sub-problem model is developed to progressively add new routes into the restricted routes set. The sub-problem is formulated as a shortest path problem with capacity constraint and is solved using a cycle elimination algorithm. When the evacuation data are updated, the SmartEvac system will reformulate the optimization model and generate a new routes set based on the existing routes set. The computational results on benchmark problems are compared to other studies in the literature. The SmartEvac system outperforms other approaches on most of the benchmark problems in terms of computation time and solution quality. CORSIM simulation is used as a test bed for the SmartEvac system. CORSIM Run-Time-Extension is developed for communications between the simulation and the SmartEvac system. A case study of the Hurricane Gustav emergency evacuation is conducted. Different scenarios corresponding to different situations that presented in the Hurricane Gustav emergency evacuation are proposed to evaluate the performance of the SmartEvac system in response to real-time data. The average processing time is 28.9 seconds and the maximum processing time is 171 seconds, which demonstrate the SmartEvac system’s capability of real-time vehicle routing optimization.

This dissertation addresses the development of enhanced formulations for minimax and mixed-integer programming models for certain industrial and logistical systems, along with the design and implementation of efficient algorithmic strategies. We first examine the general class of minimax mixed-integer 0-1 problems of the type that frequently arise in decomposition approaches and in a variety of location and scheduling problems. We conduct an extensive polyhedral analysis of this problem in order to tighten its representation using the Reformulation-Linearization/Convexification Technique (RLT), and demonstrate the benefits of the resulting lifted formulations for several classes of problems. Specifically, we investigate RLT-enhanced Lagrangian dual formulations for the class of minimax mixed-integer 0-1 problems in concert with deflected/conjugate subgradient algorithms. In addition, we propose two general purpose lifting mechanisms for tightening the mathematical programming formulations associated with such minimax optimization problems. Next, we explore novel continuous nonconvex as well as lifted discrete formulations for the notoriously challenging class of job-shop scheduling problems with the objective of minimizing the maximum completion time (i.e., minimizing the makespan). In particular, we develop an RLT-enhanced continuous nonconvex model for the job-shop problem based on a quadratic formulation of the job sequencing constraints on machines. The tight linear programming relaxation that is induced by this formulation is then embedded in a globally convergent branch-and-bound algorithm. Furthermore, we design another novel formulation for the job-shop scheduling problem that possesses a tight continuous relaxation, where the non-overlapping job sequencing constraints on machines are modeled via a lifted asymmetric traveling salesman problem (ATSP) construct, and specific sets of valid inequalities and RLT-based enhancements are incorporated to further tighten the resulting mathematical program. The efficacy of our enhanced models is demonstrated by an extensive computational experiment using classical benchmark problems from the literature. Our results reveal that the LP relaxations produced by the lifted ATSP-based models provide very tight lower bounds, and directly yield a 0\% optimality gap for many benchmark problems, thereby substantially dominating other alternative mixed-integer programming models available for this class of problems. Notably, our lifted ATSP-based formulation produced a 0\% optimality gap via the root node LP relaxation for 50\% of the classical problem instances due to Lawrence. We also investigate enhanced model formulations and specialized, efficient solution methodologies for applications arising in four particular industrial and sports scheduling settings. The first of these was posed to us by a major trucking company (Volvo Logistics North America), and concerns an integrated assembly and routing problem, which is a unique study of its kind in the literature. In this context, we examine the general class of logistical systems where it is desirable to appropriately ascertain the joint composition of the sequences of vehicles that are to be physically connected along with determining their delivery routes. Such assembly-routing problems occur in the truck manufacturing industry where different models of vehicles designed for a network of customers need to be composed into compatible groups (assemblies) and subsequently dispatched via appropriately optimized delivery routes that are restricted by the particular sequence in which the trucks are connected. A similar structure is exhibited in the business of shipping goods via boat-towed barges along inland waterways, or via trains through railroad networks. We present a novel modeling framework and column generation-based optimization approach for this challenging class of joint vehicle assembly-routing problems. In addition, we suggest several extensions to accommodate particular industrial restrictions where assembly sequence-dependent delivery routes are necessary, as well as those where limited driver- and equipment-related resources are available. Computational experience is provided using large-scale realistic data to demonstrate the applicability of our suggested methodology in practice. The second application addressed pertains to a production planning problem faced by a major motorcycle manufacturing firm (Harley-Davidson Motor Company). We consider the problem of partitioning and sequencing the production of different manufactured items in mixed-model assembly lines, where each model has various specific options and designated destinations. We propose a mixed-integer programming formulation (MPSP1) for this problem that sequences the manufactured goods within production batches in order to balance the motorcycle model and destination outputs as well as the load demands on material and labor resources. An alternative (relaxed) formulation (MPSP2) is also presented to model a closely related case where all production decisions and outputs are monitored within a common sequence of batches, which permits an enhanced tighter representation via an additional set of hierarchical symmetry-defeating constraints that impart specific identities amongst batches of products under composition. The latter model inspires a third set partitioning-based formulation in concert with an efficient column generation approach that directly achieves the joint partitioning of jobs into batches along with ascertaining the sequence of jobs within each composed batch. Finally, we investigate a subgradient-based optimization strategy that exploits a non-differentiable optimization formulation, which is prompted by the flexibility in the production process as reflected in the model via several soft-constraints, thereby providing a real-time decision-making tool. Computational experience is presented to demonstrate the relative effectiveness of the different proposed formulations and the associated optimization strategies for solving a set of realistic problem instances. The third application pertains to the problem of matching or assigning subassembly parts in assembly lines, where we seek to minimize the total deviation of the resulting final assemblies from a vector of nominal and mean quality characteristic values. We introduce three symmetry-defeating enhancements for an existing assignment-based model, and highlight the critical importance of using particular types of symmetry-defeating hierarchical constraints that preserve the model structure. We also develop an alternative set partitioning-based formulation in concert with a column generation approach that efficiently exploits the structure of the problem. A special complementary column generation feature is proposed, and we provide insights into its vital role for the proposed column generation strategy, as well as highlight its benefits in the broader context of set partitioning-based formulations that are characterized by columns having relatively dense non-zero values. In addition, we develop several heuristic procedures. Computational experience is presented to demonstrate the relative effectiveness of the different adopted strategies for solving a set of realistic problem instances. Finally, we analyze a doubles tennis scheduling problem in the context of a training tournament as prompted by a tennis club in Virginia, and develop two alternative 0-1 mixed-integer programming models, each with three different objective functions that attempt to balance the partnership and the opponentship pairings among the players. Our analysis and computational experience demonstrate the superiority of one of these models over the other, and reflect the importance of model structure in formulating discrete optimization problems. Furthermore, we design effective symmetry-defeating strategies that impose certain decision hierarchies within the models, which serve to significantly enhance algorithmic performance. In particular, our study provides the insight that the special structure of the mathematical program to which specific tailored symmetry-defeating constraints are appended can greatly influence their pruning effect. We also propose a novel nonpreemptive multi-objective programming strategy in concert with decision hierarchies, and highlight its effectiveness and conceptual value in enhancing problem solvability. Finally, four specialized heuristics are devised and are computationally evaluated along with the exact solution schemes using a set of realistic practical test problems. Aside from the development of specialized effective models and algorithms for particular interesting and challenging applications arising in different assembly, routing, and scheduling contexts, this dissertation makes several broader contributions that emerge from the foregoing studies, which are generally applicable to solving formidable combinatorial optimization problems. First, we have shown that it is of utmost importance to enforce symmetry-defeating constraints that preserve the structure of mathematical programs to which they are adjoined, so that their pruning effects are most efficiently coupled with the branch-and-bound strategies that are orchestrated within mathematical programming software packages. In addition, our work provides the insight that the concept of symmetry compatible formulations plays a crucial role in the effectiveness of implementing any particular symmetry-defeating constraints. In essence, if the root node LP solution of the original formulation does not conform relatively well with the proposed symmetry-defeating hierarchical constraints, then a significant branching effort might be required to identify a good solution that is compatible with the pattern induced by the selected symmetry-defeating constraints. Therefore, it is advisable to enforce decision hierarchies that conform as much as possible with the problem structure as well as with the initial LP relaxation. Second, we have introduced an alternative concept for defeating symmetry via augmented objective functions. This concept prompts the incorporation of objective perturbation terms that discriminate amongst subsets of originally undistinguishable solution structures and, in particular, leads to the development of a nonpreemptive multiobjective programming approach based on, and combined with, symmetry-defeating constraints. Interestingly, nonpreemptive multiobjective programming approaches that accommodate symmetry-defeating hierarchical objective terms induce a root node solution that is compatible with the imposed symmetry-defeating constraints, and hence affords an automated alternative to the aforementioned concept of symmetry compatible formulations. Third, we have proposed a new idea of complementary column generation in the context of column generation approaches that generally provide a versatile framework for analyzing industrial-related, integrated problems that involve the joint optimization of multiple operational decisions, such as assembly and routing, or partitioning and scheduling. In such situations, we have reinforced the insight that assignment-related problems that involve collections of objects (production batches, final assemblies, etc.) whose permutation yields equivalent symmetric solutions may be judiciously formulated as set partitioning models. The latter can then be effectively tackled via column generation approaches, thereby implicitly obviating the foregoing combinatorial symmetric reflections through the dynamic generation of attractive patterns or columns. The complementary column generation feature we have proposed and investigated in this dissertation proves to be particularly valuable for such set partitioning formulations that involve columns having relatively dense non-zero values. The incorporation of this feature guarantees that every LP iteration (involving the solution of a restricted master program and its associated subproblem) systematically produces a consistent set of columns that collectively qualify as a feasible solution to the problem under consideration. Upon solving the problem to optimality as a linear program, the resultant formulation encompasses multiple feasible solutions that generally include optimal or near-optimal solutions to the original integer-restricted set partitioning formulation, thereby yielding a useful representation for designing heuristic methods as well as exact branch-and-price algorithms. In addition, using duality theory and considering set partitioning problems where the number of patterns needed to collectively compose a feasible solution is bounded, we have derived a lower bound on the objective value that is updated at every LP phase iteration. By virtue of this sequence of lower bounds and the availability of upper bounds via the restricted master program at every LP phase iteration, the LP relaxation of the set partitioning problem is efficiently solved as using a pre-specified optimality tolerance. This yields enhanced algorithmic performance due to early termination strategies that successfully mitigate the tailing-off effect that is commonly witnessed for simplex-based column generation approaches. / Ph. D.

Cette thèse s’intéresse à un problème de bin-packing en deux dimensions avec des défauts sur les bins rencontré dans l’industrie verrière. Les plans de découpe sont guillotine 4-stage exact, les objets à couper sans défauts.Une possible résolution utilise la décomposition de Dantzig-Wolfe puis une génération de colonnes et un branch-and-price. Cela est impossible dans notre cas du fait d’instances de trop grande taille. Nous résolvons d’abord le problème de pricing sans défauts par un algorithme incrémental de labelling basé sur un programme dynamique (DP), représenté par un problème de flot dans un hypergraphe. Notre méthode est générique pour les problèmes de sac-à-dos guillotine mais ne résout pas de larges instances en un temps de calcul raisonnable. Nous résolvons alors le problème de bin-packing sans défauts grâce à un DP et une heuristique de diving. Le DP génère des colonnes “non propres”,ne pouvant pas participer à une solution entière. Nous adaptons le diving pour ce cas sans perte d’efficacité. Nous l’étendons alors au cas avec défauts. Nous réparons d’abord heuristiquement une solution du problème sans défauts. La fixation des colonnes dans le diving sans-défaut est ensuite modifiée pour gérer les défauts. Les résultats industriels valident nos méthodes. / This thesis deals with a two-dimensional bin-packing problem with defects on bins from the glass industry. Cutting patterns have to be exact 4-stage guillotine and items defect-free. A standard way to solve it isto use Dantzig-Wolfe reformulation with column generation and branch-and price.This is impossible in our case due to large instance size. We first study and solve the defect-free pricing problem with an incremental labelling algorithm based on a dynamic program (DP), represented as a flow problem in a hypergraph. Our method is generic for guillotine knapsack problems but fails to solve large instance in a short amount of time. Instead we solve the defect freebin-packing problem with a DP and a diving heuristic. This DP generatesnon-proper columns, cutting patterns that cannot be in an integer solution.We adapt standard diving heuristic to this “non-proper” case while keeping itseffectiveness. We then extend the diving heuristic to deal with defects. Ourfirst proposal heuristically repairs a given defect-free solution. Secondly the defect-free diving heuristic is adjusted to handle defects during column fixing.Our industrial results outline the effectiveness of our methods.