General routing problems deal with transporting some commodities and/or travelling along the axes of a given network in some optimal manner. In the modern world such problems arise in several contexts such as distribution of goods, transportation of commodities and/or people etc.In this thesis we focus on two classical routing problems, namely the Travelling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP). The TSP can be described as a salesman travels from his home city, visits each of the other ( n - 1) cities exactly once and returns back to the home city such that the total distance travelled by him is minimised. The VRP may be stated as follows: A set of n customers (with known locations and demands for some commodity) is to be supplied from a single depot using a set of delivery vehicles each with a prescribed capacity. A delivery route starts from the depot, visits some customers and returns back to the depot. The VRP is to determine the delivery routes for each vehicle such that the total distance travelled by all the vehicles is minimised.These routing problems are simple to state in terms of describing them in words. But they are very complex in terms of providing a suitable mathematical formulation and a valid procedure to solve them. These routing problems are simple to state in terms of describing them in words. But they are very complex in terms of providing a suitable mathematical formulation and a valid procedure to solve them. These problems belong to the class of NP-hard (Non- deterministic Polynomial) problems. With the present knowledge, it is believed that the problems in NP-hard are unlikely to have any good algorithms to arrive at optimal solutions to a general problem. Hence researchers have focused their effort on; (i) developing exact algorithms to solve as large size problems as possible; (ii) developing heuristics to produce ++ / near optimal solutions.The exact algorithms for such problems have not performed satisfactorily as they need an enormous amount of computational time to solve moderate size problems. For instance, in the literature, TSP of size 225-city, 4461-city and 7397-city were solved using computational time of 1 year, 1.9 years and 4 years respectively (Junger et al., 1995). Thus heuristics, in particular the probabilistic methods such as tabu search, play a significant role in obtaining near optimal solutions. In the literature there is very little comparison between the various exact algorithms and heuristics. (Very often the real-life problems are too large and no optimal solution can be found in a reasonable time.)One of the problems with a probabilistic heuristic is that different implementations (runs) of the same probabilistic heuristic on a given problem may produce distinct solutions of different quality. Thus the desired quality and reproducibility of the solution cannot be ensured. Furthermore, the performance of the heuristics on the benchmark problems provide no Guarantee of the quality of solutions that can be obtained for the problem faced by a researcher. Most of the documentation on the performance of heuristics in literature problems provides no information regarding the computational effort (CPU time) spent in obtaining the claimed solution, reproducibility of the claimed solution and the hardware environment of the implementation. This thesis focuses on some of these deficiencies.Most of the heuristics for general combinatorial optimisation problems are based on neighbourhood search methods. This thesis explores and provides a formal setup for defining neighbourhood structures, definitions of local optimum and global optimum. Furthermore it highlights the dependence and drawbacks of such methods on the neighbourhood structure.It is necessary to emphasise ++ / the need for a statistical analysis of the output to be part of any such probabilistic heuristic. Some of the statistical tools used for the two probabilistic heuristics for TSP and VRP are developed. Furthermore, these heuristics axe part of a bigger class called tabu search heuristics for combinatorial optimisation problems. Hence it includes an overview of the TSP, VRP and tabu search methods in Chapters 2, 3 and 4 respectively. Subsequently in Chapters 5, 6, 7 and 8 ideas of neighbourhood structure, local optimum etc. are developed and the required statistical analysis for some heuristics on the TSP and VRP is demonstrated. In Chapter 9, the conclusion of this thesis is drawn and the direction of future work is outlined. The following is a brief outline of the contribution of this thesis.In Chapter 5, the ideas of neighbourhood structure, local optimum, global optimum and probabilistic heuristics for any combinatorial optimisation problem sare developed. The drawbacks of the probabilistic heuristics for such problems axe highlighted. Furthermore, the need to select the best heuristic on the basis of testing a statistical hypothesis and related statistical analysis is emphasised.Chapter 6 illustrates some of the ideas presented in Chapter 5 using the GENIUS algorithm proposed for the TSP. Statistical analysis is performed for 36 variations of GENIUS algorithm based on different neighbourhood parameters, different types of insertion methods used and two types of constructions of starting solutions. The analysis is performed on 27 literature problems with size ranging from 100 cities to 532 cities and 20 randomly generated problems with size ranging from 100 cities to 480 cities. In both cases the best heuristic is selected. Furthermore, the fitting of the Weibull Distribution to the objective function values of the heuristic solutions provides an estimate of the ++ / optimal objective function value and a corresponding confidence interval for both the literature and randomly generated problems. In both cases the estimate of the optimal objective function values are within 8.2% of the best objective function value known.Since the GENIUS algorithm proved to be efficient, a hybrid heuristic for the TSP combining the branch and bound method and GENIUS algorithm to solve large dimensional problems is proposed. The algorithm is tested on both the literature problems with sizes ranging from 575 cities to 724 cities and randomly generated problems with sizes ranging from 500 cities to 700 cities. Though problems could not be solved to optimality within the 10 hours time limit, solutions were found within 2.4% of the best known objective function value in the literature.In Chapter 7, a similar statistical analysis for the TABUROUTE algorithm proposed for the VRP is conducted. The analysis is carried out based on the different neighbourhood parameters and tested using 14 literature problems with sizes ranging from 50 cities to 199 cities and 49 randomly generated problems with sizes ranging from 60 cities to 120 cities. In both sets of the problems, the statistical tests accepted the hypothesis that there is no significant difference in the solution produced between the various parameters used for the TABUROUTE algorithm. By fitting the Weibull distribution to the objective function values of the local optimal solutions, the optimal objective function value and a corresponding confidence intervals for each problem is estimated. These estimates give values that are to within 6.1% and 18.3% of the best known values for the literature problems and randomly generated problems respectively.In Chapter 8, the general neighbourhood search method for a general combinatorial optimisation problem is presented. Very often, the neighbourhood structure ++ / can be defined suitably only on a superset S of the set of feasible solutions S. Thus the solutions in SS are infeasible. Several questions axe posed regarding the computational complexity of the solution space of a problem. These concepts are illustrated on the 199-city CDVRP, using the TABUROUTE algorithm.In addition, the idea of complexity of the solution space based on the samples collected over the 140 runs is explored. Some of the data collected include the number of solutions with distance and/or capacity feasible, the number of feasible neighbourhood solutions encountered for one run, etc. Questions such asHow many solutions are there for the 199-city problem ?How many numbers of local minima solutions are there for the 199-city problem?What is the size of the feasible region for the 199-city problem?are answered. Finally, the conclusion is drawn that this problem cannot be used as a benchmark based on the size of the feasible region and too many local minima.The conclusion of this thesis and directions of future work are discussed in Chapter 9. There are two appendices presented at the end of the thesis. Appendix A presents the details of the Friedman test, the expected utility function test and the estimation of the optimal objective function value based on the Weibull distribution. Appendix B presents a list of tables from Chapters 6, 7 and 8.

Thesis (M.S.)--State University of New York at Binghamton, Watson School of Engineering and Applied Science (Computer Science), 2006. / Includes bibliographical references.

This dissertation investigates the different organizational structures of paratransit services that cover large regions. A paratransit service is demand-responsive, shared-ride transit service using vans or small buses. It is characterized by the use of vehicles that do not operate on a fixed route or a fixed schedule. The paratransit route and schedule are arranged from a user-specified origin to a user-specified destination, and at a user-specified time. To retain productivity by focusing on shorter trips within a denser area, some larger systems have outsourced operations to more than one contractor, with each contractor responsible for the service zone to which their vehicles have been assigned. This service design is called a "zonal structure" or a "zoning approach." The zoning with transfer system coordinates vehicles' schedules at various transfer locations. The schedule coordination of inter-zonal mechanisms of transportation likely reduces trip costs by increasing the ridesharing rate and lowering the number of empty return miles. This study first presents the exact formulation for a coordinated decentralized paratransit system in order to compare its productivity and service quality with independent decentralized and centralized strategies. The formulation is then proven to work correctly, and the results of the computational experiments of small scale instances are shown to demonstrate that the proposed coordinated system is superior to independent decentralized systems in terms of passenger miles per vehicle revenue mile. In the second section, this study develops an insertion-based heuristic method in order to compare the performances of different operational designs when applied to a large-scale system. In an experiment utilizing Houston's demand-responsive service data, we compare the productivity and service levels among three organizational structures: zoning with transfer, zoning without transfer, and no-zoning designs. The results indicate that zoning with transfer can provide significant benefits to paratransit operations that manage zoning structure; however, the no-zoning strategy used by Houston METRO (a relatively low-density region) performs better on average in terms of efficiency. This study concludes that the zoning with transfer method can be proven to be a productive organizational structure.

Thesis (M.S.)--West Virginia University, 2002. / Title from document title page. Document formatted into pages; contains vii, 76 p. : ill. Includes abstract. Includes bibliographical references (p. 72-76).

Thesis--Auburn University, 2010. / Abstract. Includes bibliographic references (p.28).

To get the distribution network to operate at its optimum performance in an automated distribution system reconfiguration was been proposed and researched. Considering, however, that optimum performance implies minimum loss, no overloading of transformers and cables, correct voltage profile, and absence of phase voltage and current imbalances, network reconfiguration alone is insufficient. It has to be complemented with techniques for phase rearrangement between the distribution transformer banks and the specific primary feeder with a radial structure and dynamic phase and load balancing along a feeder with a radial structure. This paper contributes such a technique at the low-voltage and medium-voltage levels of a distribution network simultaneously with reconfiguration at both levels. While the neural network is adopted for the network reconfiguration problem, this paper introduces a heuristic method for the phase balancing/loss minimization problem. A comparison of the heuristic algorithm with that of the neural network shows the former to be more robust. The approach proposed here, therefore for the combined problem, uses the neural network in conjunction with a heuristic method which enables different reconfiguration switches to be turned on/off and connected consumers to be switched between different phases to keep the phases balanced. An application example of the proposed method using real data is presented.

No description available.

No description available.

No description available.

No description available.