A multi-depot travelling salesman problem and its iterative and integrated approaches

This paper formulates a logistics distribution problem as the multi-depot travelling salesman problem (MDTSP). The decision makers not only have to determine the travelling sequence of the salesman for delivering finished products from a warehouse or depot to a customer, but also need to determine which depot stores which type of products so that the total travelling distance is minimised. The MDTSP is similar to the combination of the travelling salesman and quadratic assignment problems. In this paper, the two individual hard problems or models are formulated first. Then, the problems are integrated together, that is, the MDTSP. The MDTSP is constructed as both integer nonlinear and linear programming models. After formulating the models, we verify the integrated models using commercial packages, and most importantly, investigate whether an iterative approach, that is, solving the individual models repeatedly, can generate an optimal solution to the MDTSP. Copyright © 2006 Inderscience Enterprises Ltd.

The Synthesis and properties of functionalised polymers

The aim of this project was to synthesise fluorinated polymers that might act as hot material in a guest-host system for use in non-linear optical applications. These polymers would be expected to have the advantage over materials such as poly(vinylidene fluoride) which is known to be incompatible with many nlo active materials. A series of bicyclic fluorinated monomers was prepared by the reaction of fluorinated dienophiles with cyclopentadiene in a series of Diels-Alder reactions. The monomers were purified and then used in ring opening metathesis polymerisation. The materials were then characterised by gel permeation chromatography and nuclear magnetic resonance spectroscopy and cast as films for determination of their activities as nlo materials using a Nd/YAG laser system. The second harmonic intensity of each was measured relative to quartz. However no materials of significant activity were produced. In an attempt to produce polymers that might subsequently be functionalised the polymerisation of 1,2-methylenedioxybenzene and 1,4-benzodioxane was investigated.

On the solution of a class of capital investment problems

In this work the solution of a class of capital investment problems is considered within the framework of mathematical programming. Upon the basis of the net present value criterion, the problems in question are mainly characterized by the fact that the cost of capital is defined as a non-decreasing function of the investment requirements. Capital rationing and some cases of technological dependence are also included, this approach leading to zero-one non-linear programming problems, for which specifically designed solution procedures supported by a general branch and bound development are presented. In the context of both this development and the relevant mathematical properties of the previously mentioned zero-one programs, a generalized zero-one model is also discussed. Finally,a variant of the scheme, connected with the search sequencing of optimal solutions, is presented as an alternative in which reduced storage limitations are encountered.

The development of a solid waste management strategy

This research is concerned with the application of operational research techniques in the development of a long- term waste management policy by an English waste disposal authority. The main aspects which have been considered are the estimation of future waste production and the assessment of the effects of proposed systems. Only household and commercial wastes have been dealt with in detail, though suggestions are made for the extension of the effect assessment to cover industrial and other wastes. Similarly, the only effects considered in detail have been costs, but possible extensions are discussed. An important feature of the study is that it was conducted in close collaboration with a waste disposal authority, and so pays more attention to the actual needs of the authority than is usual in such research. A critical examination of previous waste forecasting work leads to the use of simple trend extrapolation methods, with some consideration of seasonal effects. The possibility of relating waste production to other social and economic indicators is discussed. It is concluded that, at present, large uncertainties in predictions are inevitable; waste management systems must therefore be designed to cope with this uncertainty. Linear programming is used to assess the overall costs of proposals. Two alternative linear programming formulations of this problem are used and discussed. The first is a straightforward approach, which has been .implemented as an interactive computer program. The second is more sophisticated and represents the behaviour of incineration plants more realistically. Careful attention is paid to the choice of appropriate data and the interpretation of the results. Recommendations are made on methods for immediate use, on the choice of data to be collected for future plans, and on the most useful lines for further research and development.

Microcomputers for civil engineering consultancy in developing countries

The civil engineering industry generally regards new methods and technology with a high amount of scepticism, preferring to use traditional and trusted methods. During the 1980s competition for civil engineering consultancy work in the world has become fierce. Halcrow recognised the need to maintain and improve their competitive edge over other consultants. The use of new technology in the form of microcomputers was seen to be one method to maintain and improve their repuation in the world. This thesis examines the role of microcomputers in civil engineering consultancy with particular reference to overseas projects. The involvement of civil engineers with computers, both past and present, has been investigated and a survey of the use of microcomputers by consultancies was carried out, the results are presented and analysed. A resume of the state-of-the-art of microcomputer technology was made. Various case studies were carried out in order to examine the feasibility of using microcomputers on overseas projects. One case study involved the examination of two projects in Bangladesh and is used to illustrate the requirements and problems encountered in such situations. Two programming applications were undertaken, a dynamic programming model of a single site reservoir and the simulation of the Bangladesh gas grid system. A cost-benefit analysis of a water resources project using microcomputers in the Aguan Valley, Honduras was carried out. Although the initial cost of microcomputers is often small, the overall costs can prove to be very high and are likely to exceed the costs of traditional computer methods. A planned approach for the use of microcomputers is essential in order to reap the expected benefits and recommendations for the implementation of such an approach are presented.

Aircraft rotable inventory optimisation: development of a new solution

Analysis of the use of ICT in the aerospace industry has prompted the detailed investigation of an inventory-planning problem. There is a special class of inventory, consisting of expensive repairable spares for use in support of aircraft operations. These items, called rotables, are not well served by conventional theory and systems for inventory management. The context of the problem, the aircraft maintenance industry sector, is described in order to convey some of its special characteristics in the context of operations management. A literature review is carried out to seek existing theory that can be applied to rotable inventory and to identify a potential gap into which newly developed theory could contribute. Current techniques for rotable planning are identified in industry and the literature: these methods are modelled and tested using inventory and operational data obtained in the field. In the expectation that current practice leaves much scope for improvement, several new models are proposed. These are developed and tested on the field data for comparison with current practice. The new models are revised following testing to give improved versions. The best model developed and tested here comprises a linear programming optimisation, which finds an optimal level of inventory for multiple test cases, reflecting changing operating conditions. The new model offers an inventory plan that is up to 40% less expensive than that determined by current practice, while maintaining required performance.

Applied operational research with SAS

Using a wide range of operational research (OR) optimization examples, Applied Operational Research with SAS demonstrates how the OR procedures in SAS work. The book is one of the first to extensively cover the application of SAS procedures to OR problems, such as single criterion optimization, project management decisions, printed circuit board assembly, and multiple criteria decision making. The text begins with the algorithms and methods for linear programming, integer linear programming, and goal programming models. It then describes the principles of several OR procedures in SAS. Subsequent chapters explain how to use these procedures to solve various types of OR problems. Each of these chapters describes the concept of an OR problem, presents an example of the problem, and discusses the specific procedure and its macros for the optimal solution of the problem. The macros include data handling, model building, and report writing. While primarily designed for SAS users in OR and marketing analytics, the book can also be used by readers interested in mathematical modeling techniques. By formulating the OR problems as mathematical models, the authors show how SAS can solve a variety of optimization problems.

An aggregate measure of financial ratios using a multiplicative DEA model

This paper examines the problems in the definition of the General Non-Parametric Corporate Performance (GNCP) and introduces a multiplicative linear programming as an alternative model for corporate performance. We verified and tested a statistically significant difference between the two models based on the application of 27 UK industries using six performance ratios. Our new model is found to be a more robust performance model than the previous standard Data Envelopment Analysis (DEA) model.

Structural optimization

The non-linear programming algorithms for the minimum weight design of structural frames are presented in this thesis. The first, which is applied to rigidly jointed and pin jointed plane frames subject to deflexion constraints, consists of a search in a feasible design space. Successive trial designs are developed so that the feasibility and the optimality of the designs are improved simultaneously. It is found that this method is restricted lo the design of structures with few unknown variables. The second non-linear programming algorithm is presented .in a general form. This consists of two types of search, one improving feasibility and the other optimality. The method speeds up the 'feasible direction' approach by obtaining a constant weight direction vector that is influenced by dominating constraints. For pin jointed plane and space frames this method is used to obtain a 'minimum weight' design which satisfies restrictions on stresses and deflexions. The matrix force method enables the design requirements to be expressed in a general form and the design problem is automatically formulated within the computer. Examples are given to explain the method and the design criteria are extended to include member buckling. Fundamental theorems are proposed and proved to confirm that structures are inter-related. These theorems are applicable to linear elastic structures and facilitate the prediction of the behaviour of one structure from the results of analysing another, more general, or related structure. It becomes possible to evaluate the significance of each member in the behaviour of a structure and the problem of minimum weight design is extended to include shape. A method is proposed to design structures of optimum shape with stress and deflexion limitations. Finally a detailed investigation is carried out into the design of structures to study the factors that influence their shape.

Benefits of retailer-supplier partnership initiatives under time-varying demand:a comparative analytical study

This paper aims to help supply chain managers to determine the value of retailer-supplier partnership initiatives beyond information sharing (IS) according to their specific business environment under time-varying demand conditions. For this purpose, we use integer linear programming models to quantify the benefits that can be accrued by a retailer, a supplier and system as a whole from shift in inventory ownership and shift in decision-making power with that of IS. The results of a detailed numerical study pertaining to static time horizon reveal that the shift in inventory ownership provides system-wide cost benefits in specific settings. Particularly, when it induces the retailer to order larger quantities and the supplier also prefers such orders due to significantly high setup and shipment costs. We observe that the relative benefits of shift in decision-making power are always higher than the shift in inventory ownership under all the conditions. The value of the shift in decision-making power is greater than IS particularly when the variability of underlying demand is low and time-dependent variation in production cost is high. However, when the shipment cost is negligible and order issuing efficiency of the supplier is low, the cost benefits of shift in decision-making power beyond IS are not significant. © 2012 Taylor & Francis.

Multiple criteria optimization of contemporary logistics distribution network problems

In the contemporary customer-driven supply chain, maximization of customer service plays an equally important role as minimization of costs for a company to retain and increase its competitiveness. This article develops a multiple-criteria optimization approach, combining the analytic hierarchy process (AHP) and an integer linear programming (ILP) model, to aid the design of an optimal logistics distribution network. The proposed approach outperforms traditional cost-based optimization techniques because it considers both quantitative and qualitative factors and also aims at maximizing the benefits of deliverer and customers. In the approach, the AHP is used to determine the relative importance weightings or priorities of alternative warehouses with respect to some critical customer-oriented criteria. The results of AHP prioritization are utilized as the input of the ILP model, the objective of which is to select the best warehouses at the lowest possible cost. In this article, two commercial packages are used: including Expert Choice and LINDO.

CAPS in Z(2,n)

We consider point sets in (Z^2,n) where no three points are on a line – also called caps or arcs. For the determination of caps with maximum cardinality and complete caps with minimum cardinality we provide integer linear programming formulations and identify some values for small n.

New Upper Bounds for Some Spherical Codes

The maximal cardinality of a code W on the unit sphere in n dimensions with (x, y) ≤ s whenever x, y ∈ W, x 6= y, is denoted by A(n, s). We use two methods for obtaining new upper bounds on A(n, s) for some values of n and s. We find new linear programming bounds by suitable polynomials of degrees which are higher than the degrees of the previously known good polynomials due to Levenshtein [11, 12]. Also we investigate the possibilities for attaining the Levenshtein bounds [11, 12]. In such cases we find the distance distributions of the corresponding feasible maximal spherical codes. Usually this leads to a contradiction showing that such codes do not exist.

On the k-anonymization of time-varying and multi-layer social graphs

The popularity of online social media platforms provides an unprecedented opportunity to study real-world complex networks of interactions. However, releasing this data to researchers and the public comes at the cost of potentially exposing private and sensitive user information. It has been shown that a naive anonymization of a network by removing the identity of the nodes is not sufficient to preserve users’ privacy. In order to deal with malicious attacks, k -anonymity solutions have been proposed to partially obfuscate topological information that can be used to infer nodes’ identity. In this paper, we study the problem of ensuring k anonymity in time-varying graphs, i.e., graphs with a structure that changes over time, and multi-layer graphs, i.e., graphs with multiple types of links. More specifically, we examine the case in which the attacker has access to the degree of the nodes. The goal is to generate a new graph where, given the degree of a node in each (temporal) layer of the graph, such a node remains indistinguishable from other k-1 nodes in the graph. In order to achieve this, we find the optimal partitioning of the graph nodes such that the cost of anonymizing the degree information within each group is minimum. We show that this reduces to a special case of a Generalized Assignment Problem, and we propose a simple yet effective algorithm to solve it. Finally, we introduce an iterated linear programming approach to enforce the realizability of the anonymized degree sequences. The efficacy of the method is assessed through an extensive set of experiments on synthetic and real-world graphs.

A spatiotemporal Data Envelopment Analysis (S-T DEA) approach:the need to assess evolving units

One of the major challenges in measuring efficiency in terms of resources and outcomes is the assessment of the evolution of units over time. Although Data Envelopment Analysis (DEA) has been applied for time series datasets, DEA models, by construction, form the reference set for inefficient units (lambda values) based on their distance from the efficient frontier, that is, in a spatial manner. However, when dealing with temporal datasets, the proximity in time between units should also be taken into account, since it reflects the structural resemblance among time periods of a unit that evolves. In this paper, we propose a two-stage spatiotemporal DEA approach, which captures both the spatial and temporal dimension through a multi-objective programming model. In the first stage, DEA is solved iteratively extracting for each unit only previous DMUs as peers in its reference set. In the second stage, the lambda values derived from the first stage are fed to a Multiobjective Mixed Integer Linear Programming model, which filters peers in the reference set based on weights assigned to the spatial and temporal dimension. The approach is demonstrated on a real-world example drawn from software development.