No description available.

The success of construction projects depends on proper use of construction equipment and machinery to a great extent. Thus, appropriate planning and control of the activities that rely on construction equipment could have significant effects on improving the efficiency of project operations. Cranes are the largest and most conspicuous construction equipment, widely used in typical construction sites. They play a major role in relocation of materials in horizontal and vertical directions on construction sites. Given the nature of activities relying on construction cranes in various stages of a project, cranes normally have control over the critical path of the project with the potential to create schedule bottlenecks and delaying the completion of the project. This dissertation intends to improve crane operations efficiency by developing a new framework for optimizing crane service sequence schedule. The crane service sequence problem is mathematically formulated as an NP-complete optimization problem based on the well-known Travel Salesman Problem (TSP) and is solved using different optimization techniques depending on the problem’s size and complexity. The proposed framework sets the basis for developing near-real time decision support tools for on-site optimization of crane operations sequence. To underline the value of the proposed crane sequence optimization methods, these methods are employed to solve several numerical examples. Results show that the proposed method can create a travel time saving of 28% on average in comparison with conventional scheduling methods such as First in First out (FIFO), Shortest Job First (SJF), and Earliest Deadline First (EDF).

No description available.

No description available.

No description available.

Generalized hill climbing (GHC) algorithms provide a framework for using local search algorithms to address intractable discrete optimization problems. Many well-known local search algorithms can be formulated as GHC algorithms, including simulated annealing, threshold accepting, Monte Carlo search, and pure local search (among others). This dissertation develops a mathematical framework for simultaneously addressing a set of related discrete optimization problems using GHC algorithms. The resulting algorithms, termed simultaneous generalized hill climbing (SGHC) algorithms, can be applied to a wide variety of sets of related discrete optimization problems. The SGHC algorithm probabilistically moves between these discrete optimization problems according to a problem generation probability function. This dissertation establishes that the problem generation probability function is a stochastic process that satisfies the Markov property. Therefore, given a SGHC algorithm, movement between these discrete optimization problems can be modeled as a Markov chain. Sufficient conditions that guarantee that this Markov chain has a uniform stationary probability distribution are presented. Moreover, sufficient conditions are obtained that guarantee that a SGHC algorithm will visit the globally optimal solution over all the problems in a set of related discrete optimization problems. Computational results are presented with SGHC algorithms for a set of traveling salesman problems. For comparison purposes, GHC algorithms are also applied individually to each traveling salesman problem. These computational results suggest that optimal/near optimal solutions can often be reached more quickly using a SGHC algorithm. / Ph. D.

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.

The rapid technological advancement in the past century resulted in a decreased life cycle of a large number of products and, consequently, increased the rate of technological obsolescence. The disposal of obsolete products has resulted in rapid landfilling and now poses a major environmental threat. The governments in many countries around the world have started imposing regulations to curb uncontrolled product disposal. The consumers, too, are now aware of adverse effects of product disposal on environment and increasingly favor environmentally benign products. In the wake of imminent stringent government regulations and the consumer awareness about ecosystem-friendly products, the manufacturers need to think about the alternatives to product disposal. One way to deal with this problem is to disassemble an obsolete product and utilize some of its components/subassemblies in the manufacturing of new products. This seems to be a promising solution because products now-a-days are made in accordance with the highest quality standards and, although an obsolete product may not be in the required functional state as a whole, it is possible that several of its components or subassemblies are still in near perfect condition. However, product disassembly is a complex task requiring human labor as well as automated processes and, consequently, a huge amount of monetary investment. This research addresses a disassembly optimization problem, which aims at minimizing the costs associated with the disassembly process (namely, the costs of breaking the joints and the sequence dependent set-up cost associated with disassembly operations), while maximizing the benefits resulting from recovery of components/subassemblies from a product. We provide a mathematical abstraction of the disassembly optimization problem in the form of integer-programming models. One of our formulations includes a new way of modeling the subtour elimination constraints (SECs), which are usually encountered in the well-known traveling salesman problems. Based on these SECs, a new valid formulation for asymmetric traveling salesman problem (ATSP) was developed. The ATSP formulation was further extended to obtain a valid formulation for the precedence constrained ATSP. A detailed experimentation was conducted to compare the performance of the proposed formulations with that of other well-known formulations discussed in the literature. Our results indicate that in comparison to other well-known formulations, the proposed formulations are quite promising in terms of the LP relaxation bounds obtained and the number of branch and bound nodes explored to reach an optimal integer solution. These new formulations along with the results of experimentation are presented in Appendix A. To solve the disassembly optimization problem, a three-phase iterative solution procedure was developed that can determine optimal or near optimal disassembly plans for complex assemblies. The first phase helps in obtaining an upper bound on our maximization problem through an application of a Lagrangian relaxation scheme. The second phase helps to further improve this bound through addition of a few valid inequalities in our models. In the third phase, we fix some of our decision variables based on the solutions obtained in the iterations of phases 1 and 2 and then implement a branch and bound scheme to obtain the final solution. We test our procedure on several randomly generated data sets and identify the factors that render a problem to be computationally difficult. Also, we establish the practical usefulness of our approach through case studies on the disassembly of a computer processor and a laser printer. / Master of Science

L'optimisation des tournées de livraison est souvent modélisée par un problème de voyageur de commerce (Traveling Salesman Problem / TSP). Pour ce problème, il est fréquent d’avoir des contraintes additionnelles telles que, par exemple, des fenêtres horaires limitant les heures de livraison chez le client ou des pauses obligatoires pour les conducteurs des camions. Le temps est une dimension importante à prendre en compte pour respecter ces contraintes. Cependant, les durées des trajets ne sont généralement pas constantes mais varient en fonction des congestions, et cette variabilité doit être intégrée au moment de l’optimisation des tournées. Ainsi, le problème du voyageur de commerce dépendant du temps (Time Dependent TSP / TD-TSP) est la version étendue du TSP où le coût d'un arc dépend de l'heure à laquelle cet arc est emprunté. Dans cet thèse nous proposons un nouveau benchmark pour le TD-TSP basé sur des données réelles de trafic (fournies par la Métropole de Lyon) et nous montrons l'intérêt de prendre en compte la variabilité des durées dans ce problème. Nous étudions comment mieux modéliser les fonctions de durée de trajet dépendantes du temps. Nous introduisons et comparons différents modèles pour résoudre le TD-TSP avec la programmation par contraintes (Constraint Programming / CP). Un premier modèle est directement dérivé du modèle CP classique pour le TSP. Nous montrons que ce modèle ne permet pas de raisonner avec des relations de précédence indirectes, ce qui pénalise sa performance sur notre benchmark. Nous introduisons une nouvelle contrainte globale qui est capable d'exploiter des relations de précédence indirectes sur des données dépendantes du temps et nous introduisons un nouveau modèle CP basé sur notre nouvelle contrainte. Nous comparons expérimentalement les deux modèles sur notre benchmark, et nous montrons que notre nouvelle contrainte permet de résoudre le TD-TSP plus efficacement. / In the context of urban deliveries, the optimization of delivery tours is usually modeled as a Traveling Salesman Problem (TSP). Side constraints like time-windows constraining the delivery times at the client or breaks for the drivers are also common in this kind of problem and time is an important dimension to take into account to respect these constraints. With travel times' variability in big cities time also tends to have a greater influence in costs and therefore it should be included in the optimization of delivery routes. The Time-Dependent Traveling Salesman Problem (TDTSP) is the extended version of the Traveling Salesman Problem (TSP) where arc costs depend on the time when the arc is traveled. In this thesis we propose a set of benchmarks for the TDTSP based on real traffic data (obtained from the city of Lyon) and show the interest of handling time dependency in the problem. A study of how to better model time-dependent travel functions in general and specifically for our approach is performed. We introduce and compare different models to solve the TDTSP with Constraint Programming (CP). A first model is derived in a straightforward way from the classical CP model for the TSP. We show that this model is not able to reason on indirect precedence relations, so that it has poor performance on our benchmark. We introduce a new global constraint which is able to exploit indirect precedence relations on time-dependent data, and we introduce a second model which is based on our new constraint. We experimentally compare the two models on our benchmark.

Dans cette thèse nous considérons deux problèmes d'optimisation combinatoire.Le premier s'appelle problème du double voyageur de commerce avec contraintes de piles. Dans ce problème, un véhicule doit ramasser un certain nombre d'objets dans une région pour les livrer à des clients situés dans une autre région. Lors du ramassage, les objets sont stockés dans les différentes piles du véhicule et la livraison des objets se fait selon une politique de type last-in-first-out. Le ramassage et la livraison consistent chacune en une tournée Hamiltonienne effectuée par le véhicule dans la région correspondante.Nous donnons une formulation linéaire en nombres entiers pour ce problème. Elle est basée sur des variables de précédence et sur des contraintes de chemins infaisables. Nous donnons par la suite des résultats polyédraux sur l'enveloppe convexe des solutions de notre formulation. En particulier, nous montrons des liens forts avec un polytope associé au problème du voyageur de commerce et des liens avec un polytope de type set covering. Cette étude polyédrale nous permet de renforcer la formulation initiale et de développer un algorithme de coupes et branchements efficace. Le deuxième problème que nous considérons consiste à trouver la description des polytopes lexicographiques. Ces derniers sont les enveloppes convexes des points entiers lexicographiquement compris entre deux points entiers fixés. Nous donnons une description complète de ces polytopes en termes d'inégalités linéaires. Nous démontrons que la famille des polytopes lexicographiques est fermée par intersection. / In this thesis we consider two problems arising in combinatorial optimization.The first one is the double traveling salesman problem with multiple stacks. In this problem a vehicle picks up a given set of items in a region and subsequently delivers them to demanding customers in another region. When an item is picked up, it is put in a stack of the vehicle. The items are delivered observing a last-in-first-out policy. The pickup phase and the delivery phase consist in two Hamiltonian circuits, each performed by the vehicle in the corresponding region. We give a new integer linear programming formulation for this problem. Its main features are the presence of precedence variables and new infeasible path constraints. We provide polyhedral results on the convex hull of the solutions to our formulation. In particular, we show strong links with a specific TSPpolytope and a specific set covering polytope. We deduce strengthening inequalities for the initial formulation, subsequently embedded in an efficient branch-and-cut algorithm. The second problem we consider consists in finding the description of the lexicographical polytopes. These are convex hulls of the integer points lexicographically between two given integer points. We give a complete description of these polytopes by means of linear inequalities. We show that the lexicographical polytope family is closed under intersection.