[pt] Uma generalização do problema de roteamento de veículos (VRP) presente em aplicações práticas em portos e operações em minas é o objeto desta dissertação. Nesta variante do VRP cada cliente pode demandar diferentes tipos de veículos para cumprir tarefas colaborativamente. Nesta atividade, os veículos podem aguardar o início da operação no local porém, devem iniciar as tarefas ao mesmo tempo. O objetivo é determinar as rotas dos veículos disponíveis de modo a maximizar a soma (ponderada) dos clientes atendidos enquanto a distância total percorrida é minimizada. O caso específico onde todos os clientes são atendidos e a distância total percorrida é minimizada determina o problema central estudado nessa dissertação. Este caso particular pode ser visto como uma generalização direta do, muito estudado e conhecido problema de roteamento, VRP com janelas de tempo (VRPTW) onde a capacidade dos veículos é suficientemente grande. Esta escolha de um problema mais restrito é justificada por permitir uma clara comparação de sua dificuldade através da sua relação com o VRPTW. A partir da classificação dos casos de sincronização em problemas de roteamento proposta por (DREXL, 2012), denominamos o problema aqui estudado de Problema de Roteamento de Veículos com Janelas de Tempo e Sincronização exata da Operação (VRPTWEOS). Neste trabalho damos uma definição formal ao VRPTWEOS. Modelos de programação inteira são propostos e analisados. Também apressentamos métodos de resolução baseados na decomposição Dantzig-Wolfe, dos quais são derivados algoritmos exatos e aproximados. Com o propósito de avaliar a eficiencia desses algoritmos, foi criado um grupo de instancias de teste baseado no benchmark do Solomon para o VRPTW. O método usado para criar o conjunto de instancias de teste é descrito em detalhe. Experimentos computacionais sobre este conjunto de instancias mostraram que o método de resolução proposto é promissor para a resolução do VRPTWEOS. / [en] This dissertation addresses a generalization of the vehicle routing problem (VRP) that arises in real life applications in ports and mine operations. In this VRP variant, each customer may demand different types of vehicles to perform a task collaboratively. Vehicles are allowed to wait at the locations but they must start operating at the same time. The objective is to route the available vehicles while maximizing the (weighted) sum of served customers and minimizing the total distance traveled. The specific case where all customers must be served while minimizing the total distance traveled is the central problem here studied. This special case can be viewed as a straightforward generalization of, a well known and more specific routing problem, the VRP with time windows (VRTPTW) where the capacity of the vehicles is sufficiently large. We support this narrower scope by stating that it allows a clear comparison of the problem hardness by its relation to the VRPTW. Sticking to the classification of synchronization in vehicle routing proposed by (DREXL, 2012) we named this problem as the Vehicle Routing Problem with Time Windows and Exact Operation Synchronization (VRPTWEOS). In this work, a formal definition for the VRPTWEOS is provided. Integer programming models for this problem are proposed and analyzed. Furthermore, we propose a solution method based on the Dantzig-Wolfe decomposition for which exact and aproximated resolution algorithms are described. In order to test the performance of those algorithms, a group of benchmark instances for the VRPTWEOS was created on top of the Solomon benchmark for the VRPTW. The method used to create the benchmark instances is described in detail. Computational experiments over the mentioned set of instances showed that the proposed solution approach is a promising alternative for solving the VRPTWEOS.

No description available.

Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-01-24T10:38:55Z No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:50:29Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:51:23Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Made available in DSpace on 2017-02-08T10:51:33Z (GMT). No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) Previous issue date: 2016-04-01 / Outra / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / The object of this study is the routing and scheduling problem of vessels with pickup and delivery and time windows in the oil industry. A case study was performed in a Brazilian oil industry that produces crude oil in o shore platforms, that is, located in the ocean, and transports to the terminals located in the Brazilian coast. Then, it was proposed a mixed integer model to represent the problem adequately and for this, a detailed analysis of the real problem in order to know all its characteristics and consider some simplifying assumptions. Therefore, to the pickup and delivery problem with time windows present in the literature were aggregated other speci c restrictions of the case study, for example, multiple depots, ship mooring restrictions, exible draft and dynamic positioning. Besides that, the eet is heterogeneous related to capacity, LOA (length overall), dynamic positioning and velocity. In practice, in general there are no identical vessels. This problem can be represented as a combinatorial optimization model, which belongs to the NP-hard class and its solution is a challenging in practice depending on the size of the real problems. Then, were proposed several exact branch-and-cut methods based on models with 2 and 3-index variables for routing problems with pickup and delivery and time windows to solve speci cally the Brazilian oil industry problem. Finally, we proposed a branch-and-price method, which includes all characteristics of the problem in oil industry. In summary, the main contributions of this thesis are related to the study and modeling of this problem in practice, and the proposal and development of exact solution methods to solve it, based on branch-and-cut and branch-and-price. The performance of the mathematical model in optimization software and the exact methods were veri ed using a real data set provided by the company. Results show that these approaches may be e ective to solve problems of moderate size in real situations. / O objeto de estudo deste trabalho é o problema de roteamento e programação de navios com coleta e entrega e janelas de tempo na indústria petrolífera. Foi realizado um estudo de caso com uma empresa petrolífera brasileira que produz óleo cru em plataformas o shore, isto é, localizadas no oceano e os transporta até os terminais localizados na costa brasileira. Então, foi proposto um modelo de programação inteira mista para representar o problema adequadamente e para isso, foi necessária uma análise detalhada do problema real, com o intuito de conhecer todas as suas características e considerar hipóteses simpli cadoras. Desta maneira, ao problema de coleta e entrega e janelas de tempo da literatura foram agregadas outras restrições especí cas do problema do estudo de caso como, por exemplo, múltiplos depósitos, restrições de atracação dos navios, calado exível e posicionamento dinâmico. Além disso, a frota de navios é heterogênea em relação à capacidade, LOA (length overall ), posicionamento dinâmico e velocidade. Na prática, em geral não existem navios iguais. Este problema pode ser representado como um modelo de otimização combinatória que pertence à classe NP-difícil e sua solução é bastante desa adora na prática em função do tamanho dos problemas reais. Depois, foram propostos vários métodos do tipo branch-and-cut baseados em modelos com variáveis de 2 e 3-índices para problemas de roteamento com coleta e entrega e janelas de tempo para resolver especi camente o problema da empresa brasileira. E por m, foi proposto um método do tipo branch-and-price, o qual abrange todas as características do problema da indústria petrolífera. Em síntese, as principais contribuições desta tese referem-se ao estudo e modelagem deste problema na prática, e a proposta e desenvolvimento de métodos de solução exatos para resolvê-lo, baseados em branch-and-cut e branch-and-price. O desempenho do modelo matemático em softwares de otimização e também dos métodos exatos propostos foi veri cado usando-se exemplares reais fornecidos pela empresa. Os resultados mostram que essas abordagens podem ser efetivas para resolver problemas de tamanho moderado em situações reais.

We define an order cutoff for a retailer as a time in the day such that orders sent to the depot before this point will be delivered by tomorrow, and orders submitted after will be delivered by the day after tomorrow. The later a retailer’s cutoff, the sooner it receives its orders which helps it to maintain ideal inventory levels. Generally, not all retailers in a supply chain can have the latest cutoff since transportation takes a significant amount of time. This thesis tries to assign optimal order cutoffs to retailers. We call this an order cutoff assignment problem and we solve it using three different mathematical programming approaches. The approaches are exhaustive route generation and selection, a series of mixed integer programs, and branch-and-price. 60 sample problems were solved and results showed that branch-and-price is often the most effective method.

We define an order cutoff for a retailer as a time in the day such that orders sent to the depot before this point will be delivered by tomorrow, and orders submitted after will be delivered by the day after tomorrow. The later a retailer’s cutoff, the sooner it receives its orders which helps it to maintain ideal inventory levels. Generally, not all retailers in a supply chain can have the latest cutoff since transportation takes a significant amount of time. This thesis tries to assign optimal order cutoffs to retailers. We call this an order cutoff assignment problem and we solve it using three different mathematical programming approaches. The approaches are exhaustive route generation and selection, a series of mixed integer programs, and branch-and-price. 60 sample problems were solved and results showed that branch-and-price is often the most effective method.

This dissertation discusses two independent topics. The first part of the dissertation relates three theories of international economics (comparative advantage, competitive advantage, and competitiveness), and formulates the thesis that incorporating them in the form of readily available individual competitiveness indicators in OR/MS models offers promise to enhance decision-support for the strategic planning of global supply chains in general, and for locating facilities in particular. The objectives of this research were to relate each of these theories and to describe their interrelationships; to describe measures provided by two well-known annual competitiveness reports; and to illustrate application of the theories as a means of supporting the thesis of the research, and justifying the research questions we pose for future research. While this research discusses topics relative to the broader background of global supply chain design, it illustrates applications associated with facility location, a component of the global supply chain design. In the last chapter of the first part of the dissertation, we provide a vision to foster future research that will enhance the profitability of international enterprises under NAFTA. The second part of the dissertation deals with the DSCR model with capacity expansion and contraction. The strategic dynamic supply chain reconfiguration (DSCR) problem is to prescribe the location and capacity of each facility, select links used for transportation, and plan material flows through the supply chain, including production, inventory, backorder, and outsourcing levels. The objective is to minimize total cost. The configuration must be dynamically redesigned over time to accommodate changing trends in demand and/or costs by opening facilities, expanding and/or contracting their capacities, and closing facilities. The problem involves a multi-period, multi-product, multi-echelon supply chain. Research objectives are alternative formulations of DSCR and tests that identify the computational characteristics of each model to determine if one offers superior solvability in comparison with the others. To achieve the first objective, we present an initial MIP model, a refined model that relates decision variables according to a convenient structure, and branch and price (B&P) schemes for the refined model. We found that the network-based formulation offered superior solvability compared to the traditional formulation.

Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2016-02-17T11:41:50Z No. of bitstreams: 1 arquivototal.pdf: 1276201 bytes, checksum: 9dd8fad80c483276a40101ee6a782d5b (MD5) / Made available in DSpace on 2016-02-17T11:41:50Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1276201 bytes, checksum: 9dd8fad80c483276a40101ee6a782d5b (MD5) Previous issue date: 2015-07-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work deals with the p-Cluster Editing Problem (p-CEP), which consists in performing a minimum number of editions (additions or removals of edges) in a graph G in order to transform it in a disjoint union of p cliques (clusters), where G and p are input data. p-CEP is a NP-Hard problem with applications in areas such as computational biology and machine learning. To solve this problem, we propose two new mathematical formulations and improvements in a formulation from the literature, as well as new valid inequalities. The three formulations were studied both theoretically, by comparing their linear relaxations, and practically, by implementing three exact algorithms: two based on Branch-and-Cut (BC) and one based on Branch-and-Price (BP). The proposed algorithms were tested in instances with up to 211 vertices. The results show the performance of the algorithms according to the graph density and the ratio between p and the number of vertices. Overall, the BC algorithms were superior to the BP algorithm. However, the latter obtained the best dual bounds in some instances. / Este trabalho trata do Problema de Edi¸c˜ao de p-Clusters (p-PEC), o qual consiste em realizar um n´umero m´ınimo de edi¸c˜oes (adi¸c˜oes ou remo¸c˜oes de arestas) em um grafo G de modo a transform´a-lo em uma uni˜ao disjunta de p cliques (ou clusters), sendo G e p dados de entrada. O p-PEC ´e um problema NP-Dif´ıcil que possui aplica¸c˜oes em ´areas como biologia computacional e aprendizagem de m´aquina. Para resolvˆe-lo, foram propostas duas novas formula¸c˜oes matem´aticas e melhorias em uma formula¸c˜ao proveniente da literatura, bem como novas desigualdades v´alidas. As trˆes formula¸c˜oes consideradas foram estudadas tanto teoricamente, atrav´es da compara¸c˜ao entre as relaxa¸c˜oes lineares, quanto empiricamente, atrav´es do desenvolvimento de trˆes algoritmos exatos: dois baseados em Branch-and-Cut (BC) e um baseado em Branch-and-Price (BP). Os algoritmos foram testados em instˆancias com at´e 211 v´ertices. Os resultados mostram o impacto da raz˜ao entre p e o n´umero de v´ertices, da densidade do grafo e das desigualdades nos desempenhos dos algoritmos. No geral, os algoritmos BC foram superiores ao algoritmo BP. Por´em, em algumas instˆancias, os melhores limites duais foram obtidos pelo algoritmo BP.

The increasing emphasis on mass customization, shortened product lifecycles, synchronized supply chains, when coupled with advances in information system, is driving most firms towards make-to-order (MTO) operations. Increasing global competition, lower profit margins, and higher customer expectations force the MTO firms to plan its capacity by managing the effective demand. The goal of this research was to maximize the operational profits of a make-to-order operation by selectively accepting incoming customer orders and simultaneously allocating capacity for them at the sales stage. For integrating the two decisions, a Mixed-Integer Linear Program (MILP) was formulated which can aid an operations manager in an MTO environment to select a set of potential customer orders such that all the selected orders are fulfilled by their deadline. The proposed model combines order acceptance/rejection decision with detailed scheduling. Experiments with the formulation indicate that for larger problem sizes, the computational time required to determine an optimal solution is prohibitive. This formulation inherits a block diagonal structure, and can be decomposed into one or more sub-problems (i.e. one sub-problem for each customer order) and a master problem by applying Dantzig-Wolfe’s decomposition principles. To efficiently solve the original MILP, an exact Branch-and-Price algorithm was successfully developed. Various approximation algorithms were developed to further improve the runtime. Experiments conducted unequivocally show the efficiency of these algorithms compared to a commercial optimization solver. The existing literature addresses the static order acceptance problem for a single machine environment having regular capacity with an objective to maximize profits and a penalty for tardiness. This dissertation has solved the order acceptance and capacity planning problem for a job shop environment with multiple resources. Both regular and overtime resources is considered. The Branch-and-Price algorithms developed in this dissertation are faster and can be incorporated in a decision support system which can be used on a daily basis to help make intelligent decisions in a MTO operation.

京都大学 / 新制・課程博士 / 博士(工学) / 甲第24219号 / 工博第5047号 / 新制||工||1788(附属図書館) / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 藤井 聡, 教授 山田 忠史, 准教授 QURESHI Ali Gul / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DGAM

Governments in many counties are taking measures to promote electric vehicles. An important strategy is to build enough charging infrastructures so as to alleviate drivers’ range anxieties. To help the governments make plans about the public charging network, we propose a multi-stage stochastic integer programming model to determine the locations and capacities of charging facilities over finite planning horizons. We use the logit choice model to estimate drivers’ random choices towards different charging stations nearby. The objective of the model is to minimize the expected total cost of installing and operating the charging facilities. Two simple algorithms are designed to solve this model, an approximation algorithm and a heuristic algorithm. A branch-and-price algorithm is also designed for this model, and some implementation details and improvement methods are explained. We do some numerical experiments to test the efficiency of these algorithms. Each algorithm has advantages over the CPLEX MIP solver in terms of solution time or solution quality. A case study of Oakville is presented to demonstrate the process of designing an electric vehicle public charging network using this model in Canada. / Thesis / Master of Science (MSc)