Digitized by Kansas Correctional Industries

In this research, we investigate and propose new operators to improve Genetic Algorithm’s performance to solve the multi-stop routing problem. In a multi-stop route, a user starts at point x, visits all destinations exactly once, and then return to the same starting point. In this thesis, we are interested in two types of this problem. The first type is when the distance among destinations is fixed. In this case, it is called static traveling salesman problem. The second type is when the cost among destinations is affected by traffic congestion. Thus, the time among destinations changes during the day. In this case, it is called time-dependent traveling salesman problem. This research proposes new improvements on genetic algorithm to solve each of these two optimization problems. First, the Travelling Salesman Problem (TSP) is one of the most important and attractive combinatorial optimization problems. There are many meta-heuristic algorithms that can solve this problem. In this paper, we use a Genetic Algorithm (GA) to solve it. GA uses different operators: selection, crossover, and mutation. Sequential Constructive Crossover (SCX) and Bidirectional Circular Constructive Crossover (BCSCX) are efficient to solve TSP. Here, we propose a modification to these crossovers. The experimental results show that our proposed adjustment is superior to SCX and BCSCX as well as to other conventional crossovers (e.g. Order Crossover (OX), Cycle Crossover (CX), and Partially Mapped Crossover (PMX)) in term of solution quality and convergence speed. Furthermore, the GA solver, that is improved by applying inexpensive local search operators, can produce solutions that have much better quality within reasonable computational time. Second, the Time-Dependent Traveling Salesman Problem (TDTSP) is an interesting problem and has an impact on real-life applications such as a delivery system. In this problem, time among destinations fluctuates during the day due to traffic, weather, accidents, or other events. Thus, it is important to recommend a tour that can save driver’s time and resources. In this research, we propose a Multi-Population Genetic Algorithm (MGA) where each population has different crossovers. We compare the proposed MG against Single-Population Genetic Algorithm (SGA) in terms of tour time solution quality. Our finding is that MGA outperforms SGA. Our method is tested against real-world traffic data [1] where there are 200 different instances with different numbers of destinations. For all tested instances, MGA is superior on average by at least 10% (for instances with size less than 50) and 20% (for instances of size 50) better tour time solution compared to SGA with OX and SGA with PMX operators, and at least 4% better tour time compared toga with SCX operator.

In this thesis we address three related topic in the field of Operations Research. Firstly we discuss the problems and limitation of most common solvers for linear programming, precision. We then present a solver that generate rational optimal solutions to linear programming problems by solving a succession of (increasingly more precise) floating point approximations of the original rational problem until the rational optimality conditions are achieved. This method is shown to be (on average) only 20% slower than the common pure floating point approach, while returning true optimal solutions to the problems. Secondly we present an extension of the Local Cut procedure introduced by Applegate et al, 2001, for the Symmetric Traveling Salesman Problem (STSP), to the general setting of MIP problems. This extension also proves finiteness of the separation, facet and tilting procedures in the general MIP setting, and also provides conditions under which the separation procedure is guaranteed to generate cuts that separate the current fractional solution from the convex hull of the mixed-integer polyhedron. We then move on to explore some configurations for local cuts, realizing extensive testing on the instances from MIPLIB. Those results show that this technique may be useful in general MIP problems, while the experience of Applegate et al, shows that the ideas can be successfully applied to structures problems as well. Thirdly we present an extensive computational experiment on the TSP and Domino Parity inequalities as introduced by Letchford, 2000. This work also include a safe-shrinking theorem for domino parity inequalities, heuristics to apply the planar separation algorithm introduced by Letchford to instances where the planarity requirement does not hold, and several practical speed-ups. Our computational experience showed that this class of inequalities effectively improve the lower bounds from the best relaxations obtained with Concorde, which is one of the state of the art solvers for the STSP. As part of these experience, we solved to optimality the (up to now) largest two STSP instances, both of them belong to the TSPLIB set of instances and they have 18,520 and 33,810 cities respectively.

In this thesis I focus on cutting planes for large Mixed Integer Programming (MIP) problems. More specifically, I focus on two independent cutting planes studies. The first of these deals with cutting planes for the Traveling Salesman Problem (TSP), and the second with cutting planes for general MIPs. In the first study I introduce a new class of cutting planes which I call the Generalized Domino Parity (GDP) inequalities. My main achievements with regard to these are: (1) I show that these are valid for the TSP and for the graphical TSP. (2) I show that they generalize most well-known TSP inequalities (including combs, domino-parity constraints, clique-trees, bipartitions, paths and stars). (3) I show that a sub-class of these (which contains all clique-tree inequalities w/ a fixed number of handles) can be separated in polynomial time, on planar graphs. My second study can be subdivided in two parts. In the first of these I study the Mixed Integer Knapsack Problem (MIKP) and develop a branch-and-bound based algorithm for solving it. The novelty of the approach is that it exploits the notion of "dominance" in order to effectively prune solutions in the branch-and-bound tree. In the second part, I develop a Mixed Integer Rounding (MIR) cut separation heuristic, and embed the MIKP solver in a column generation algorithm in order to assess the performance of said heuristic. The goal of this study is to understand why no other class of inequalities derived from single-row systems has been able to outperform the MIR. Computational results are presented.

This study deals with chocolate production line scheduling. The particular production line allows producing multiple items at the same time. Another distinguishing property affecting the planning methodology is that an item can have different production capacities when produced in different product combinations which are called production patterns in this study. Planning is done on a 12 weeks rolling horizon. There are 21 products and 103 production patterns covering all the production possibilities. The subject of the study is to construct an algorithm that gives 12 weeks&rsquo / production values of each product and to construct the shift based scheduling of the first week of the planning horizon. The first part is Master Production Scheduling (MPS) and the objective is minimizing the shortage and overage costs. A mathematical modeling approach is used to solve the MPS problem. The second part is the scheduling part which aims to arrange the production patterns obtained from the MPS module within the shifts for the first week of the planning horizon considering the setup times. The MPS module is a large integer programming model. The challenge is finding a reasonable lower bound whenever possible. If it is not possible, finding a reasonable upper bound and seeking solutions better than that is the main approach. The scheduling part, after solving MPS, becomes a TSP and the setup times are sequence independent. In this part, the challenge is solving TSP with an appropriate objective function.

In this study, a new selective and time-window routing problem is defined for the first time in the literature, which is called the campaign routing problem (CRP). The two special cases of the CRP correspond to the two real-life problems, namely political campaign routing problem (PCRP) and the experiments on wheels routing problem (EWRP). The PCRP is based on two main decision levels. In the first level, a set of campaign regions is selected according to a given criteria subject to the special time-window constraints. In the second level, a pair of selected regions or a single region is assigned to a campaign day. In the EWRP, a single selected region (school) is assigned to a campaign day. These two problems are modeled using classical mathematical programming and bi-level programming methods, and a two-step heuristic approach is developed for the solution of the problems. Implementation of the solution methods is done using the test instances that are compiled from the real-life data. Computational results show that the solution methods developed generate good solutions in reasonable time.

Thesis (Ph. D.)--Missouri University of Science and Technology, 2009. / Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed January 5, 2010) Includes bibliographical references (p. 152-159).

Darbo tikslas yra išanalizuoti keliaujančio pirklio algoritmo realizacijos galimybes egzistuojančiose navigacinėse sistemose, bei išanalizavus pasirinktus algoritmus keliaujančio pirklio problemai spręsti, parinkti tinkamiausią algoritmą pagal turimus atminties ir skaičiavimo resursus bei problemos sudėtingumą. Tyrimo rezultatai parodė, jog nėra tinkamiausio algoritmo visiems atvejams, nes skirtingose situacijose skirtingi algoritmai rodo geriausius rezultatus. / The investigation had a list of objectives: analyze the capabilities and resources of a range of chosen GPS navigation devices; analyze the needs and requirements of traveling salesman related GPS navigator functions for regular users; analyze what types of TSP algorithms are used in existing navigation software products; analyze the capabilities of various TSP algorithms with regard to used resources and speed of calculations; determine which algorithms are optimal for a range of specific situations. Research of different algorithms led to a conclusion that there is no single algorithm that is always better than the rest. Under different circumstances, different algorithms showed different results. Some were clearly optimal in some situations, while others competed with each other in other situations. The key element to success of an algorithm was how much time it got to do it's calculations. The amount of the input data changed the duration of the calculations but the algorithm function declination rate remained mostly the same with different sets of input data.

The traveling salesperson or salesman problem (TSP) is a well known and important combinatorial optimization problem. The goal is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Despite this simple problem statement, solving the TSP is difficult since it belongs to the class of NP-complete problems. The importance of the TSP arises besides from its theoretical appeal from the variety of its applications. In addition to vehicle routing, many other applications, e.g., computer wiring, cutting wallpaper, job sequencing or several data visualization techniques, require the solution of a TSP. In this paper we introduce the R package TSP which provides a basic infrastructure for handling and solving the traveling salesperson problem. The package features S3 classes for specifying a TSP and its (possibly optimal) solution as well as several heuristics to find good solutions. In addition, it provides an interface to Concorde, one of the best exact TSP solvers currently available. (author's abstract) / Series: Research Report Series / Department of Statistics and Mathematics

Thesis (Ph. D.)--Mathematics, Georgia Institute of Technology, 2008. / Committee Chair: Thomas, Robin; Committee Co-Chair: Cook, William J.; Committee Member: Dvorak, Zdenek; Committee Member: Parker, Robert G.; Committee Member: Yu, Xingxing.