Convoy movement problem: a civilian perspective

We study the convoy movement problem in peacetime from a civilian perspective by seeking to minimize civilian traffic disruptions. We develop an exact hybrid algorithm that combines the k-shortest path algorithm along with finding a minimum weighted k-clique in a k-partite graph. Through this coupling scheme, we are able to exactly solve large instances of the convoy movement problem without relaxing many of its complicating constraints. An experimental study is performed based on pseudo-transportation networks to illustrate the computational viability of the method as well as policy implications.     

Computational complexity of convoy movement planning problems

Convoy movement planning problems arise in a number of important logistical contexts, including military planning, railroad optimization and automated guided vehicle routing. In the convoy movement problem (CMP), a set of convoys, with specified origins and destinations, are to be routed with the objective of minimizing either makespan or total flow time, while observing a number of side constraints. This paper characterizes the computational complexity of several restricted classes of CMPs. The principal objective is to identify the most parsimonious set of problem features that make the CMP intractable. A polynomial-time algorithm is provided for the single criterion two-convoy movement problem. The performance of a simple prioritization–idling approximation algorithm is also analyzed for the K-convoy movement problem. Error bounds are developed for the makespan and flow time objectives.     

On the usage of Lagrangean Relaxation for the convoy movement problem

The problem of routing military convoys between specific origin and destination pairs is known as convoy movement problem (CMP). In this study, we consider an existing mathematical model of CMP and propose a lower bounding procedure based on Lagrangean Relaxation. The robustness of the proposed procedure is evaluated on a variety of test problem instances. Encouraging results are obtained.     

A simple model of optimal clearance of improvised explosive devices

Motivated by experiences of coalition military forces in Iraq and Afghanistan, we analyze the allocation of route clearance teams (RCTs) to search for and neutralize improvised explosive devices (IEDs) on roadways traveled by military convoys. We model the interaction of a single RCT and a single convoy operating over a given roadway. Our goal is to reduce IED risk by improving coordination between the RCT and the convoy. We treat the distribution of IEDs along the road prior to the passage of the RCT as a non-homogeneous Poisson process. The RCT finds and clears IEDs according to a Bernoulli process. Enemy forces may emplace (reseed) additional IEDs in the temporal gap between the RCT clearance sweep and the arrival of the convoy. IED risk is defined as the expected number of IEDs encountered by the convoy. We identify certain characteristics of optimal RCT schedules including: the shape of the IED intensity function and the speed of reseeding substantially dictate the RCT schedule that minimizes IED risk; the more rapid the IED reseeding, the more critical is conformance to the optimal RCT schedule; an RCT having inferior detection probability, by employing superior scheduling can sometimes reduce convoy risk more than a less well scheduled RCT with superior detection probability; a discretized highway version of the problem can be efficiently optimized. We also briefly discuss applications of this model to the more complex problem of allocating several RCTs to protect a number of convoys scheduled to travel on a network of highways.     

Memetic cooperative models for the tool switching problem

This work deals with memetic-computing agent-models based on the cooperative integration of search agents endowed with (possibly different) optimization strategies, in particular memetic algorithms. As a proof-of-concept of the model, we deploy it on the tool switching problem (ToSP), a hard combinatorial optimization problem that arises in the area of flexible manufacturing. The ToSP has been tackled by different algorithmic methods ranging from exact to heuristic methods (including local search meta-heuristics, population-based techniques and hybrids thereof, i.e., memetic algorithms). Here we consider an ample number of instances of this cooperative memetic model, whose agents are adapted to cope with this problem. A detailed experimental analysis shows that the meta-models promoting the cooperation among memetic algorithms provide the best overall results compared with their constituent parts (i.e., memetic algorithms and local search approaches). In addition, a parameter sensitivity analysis of the meta-models is developed in order to understand the interplay among the elements of the proposed topologies.     

The linear ordering problem: Instances,search space analysis and algorithms

The linear ordering problem is an NP-hard problem that arises in a variety of applications. Due to its interest in practice, it has received considerable attention and a variety of algorithmic approaches to its solution have been proposed. In this paper we give a detailed search space analysis of available benchmark instance classes that have been used in various researches. The large fitness-distance correlations observed for many of these instances suggest that adaptive restart algorithms like iterated local search or memetic algorithms, which iteratively generate new starting solutions for a local search based on previous search experience, are promising candidates for obtaining high performing algorithms. We therefore experimentally compared two such algorithms and the final experimental results suggest that, in particular, the memetic algorithm is a new state-of-the-art approach to the linear ordering problem.     

Estimating common principal components in high dimensions

We consider the problem of minimizing an objective function that depends on an orthonormal matrix. This situation is encountered, for example, when looking for common principal components. The Flury method is a popular approach but is not effective for higher dimensional problems. We obtain several simple majorization–minimization (MM) algorithms that provide solutions to this problem and are effective in higher dimensions. We use mixture model-based clustering applications to illustrate our MM algorithms. We then use simulated data to compare them with other approaches, with comparisons drawn with respect to convergence and computational time.     

LP-based online scheduling: from single to parallel machines

We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-preemptive version of the problem, improving upon the 3.28-competitive algorithm of Megow and Schulz. Additionally, we show how to combine randomization techniques with the linear programming approach to obtain randomized algorithms for both versions of the problem with competitive ratio strictly smaller than 2 for any number of machines (but approaching two as the number of machines grows). Our algorithms naturally extend several approaches for single and parallel machine scheduling. We also present a brief computational study, for randomly generated problem instances, which suggests that our algorithms perform very well in practice. A preliminary version of this work appears in the Proceedings of the 11th conference on integer programming and combinatorial optimization (IPCO), Berlin, 8–10 June 2005.     

A fixed-point iteration approach for multibody dynamics with contact and small friction

Acceleration–force setups for multi-rigid-body dynamics are known to be inconsistent for some configurations and sufficiently large friction coefficients (a Painleve paradox). This difficulty is circumvented by time-stepping methods using impulse-velocity approaches, which solve complementarity problems with possibly nonconvex solution sets. We show that very simple configurations involving two bodies may have a nonconvex solution set for any nonzero value of the friction coefficient. We construct two fixed-point iteration algorithms that solve convex subproblems and that are guaranteed, for sufficiently small friction coefficients, to retrieve, at a linear convergence rate, the unique velocity solution of the nonconvex linear complementarity problem whenever the frictionless configuration can be disassembled. In addition, we show that one step of one of the iterative algorithms provides an excellent approximation to the velocity solution of the original, possibly nonconvex, problem if for all contacts we have that either the friction coefficient is small or the slip velocity is small.Subject Index. 70E55, 75M10, 75M15, 90C33A partial version of this work has appeared in the proceedings of the NATO Advanced Studies Institute on Virtual Nonlinear Multibody Systems, Prague, 2002.     

Average-optimal string matching

The exact string matching problem is to find the occurrences of a pattern of length m from a text of length n symbols. We develop a novel and unorthodox filtering technique for this problem. Our method is based on transforming the problem into multiple matching of carefully chosen pattern subsequences. While this is seemingly more difficult than the original problem, we show that the idea leads to very simple algorithms that are optimal on average. We then show how our basic method can be used to solve multiple string matching as well as several approximate matching problems in average optimal time. The general method can be applied to many existing string matching algorithms. Our experimental results show that the algorithms perform very well in practice.     

Analysis of algorithms for an online version of the convoy movement problem

In the convoy movement problem (CMP), a set of convoys must be routed from specified origins to destinations in a transportation network, represented by an undirected graph. Two convoys may not cross each other on the same edge while travelling in opposing directions, a restriction referred to as blocking. However, convoys are permitted to follow each other on the same edge, with a specified headway separating them, but no overtaking is permitted. Further, the convoys to be routed are distinguished based on their length. Particle convoys have zero length and are permitted to traverse an edge simultaneously, whereas convoys with non-zero length have to follow each other, observing a headway. The objective is to minimize the total time taken by convoys to travel from their origins to their destinations, given the travel constraints on the edges. We consider an online version of the CMP where convoy demands arise dynamically over time. For the special case of particle convoys, we present an algorithm that has a competitive ratio of 3 in the worst case and (5/2) on average. For the particle convoy problem, we also present an alternate, randomized algorithm that provides a competitive ratio of (√13?1). We then extend the results to the case of convoys with length, which leads to an algorithm with an O(T+CL) competitive ratio, where T={Max _e t(e)}/{Min _e t(e)}, C is the maximum congestion (the number of distinct convoy origin–destination pairs that use any edge e) and L={Max _c L(c)}/{Min _c L(c)}; here L(c)>0 represents the time-headway to be observed by any convoy that follows c and t(e) represents the travel time for a convoy c on edge e.     

Multi-objective sequence dependent setup times permutation flowshop: A new algorithm and a comprehensive study

The permutation flowshop scheduling problem has been thoroughly studied in recent decades, both from single objective as well as from multi-objective perspectives. To the best of our knowledge, little has been done regarding the multi-objective flowshop with Pareto approach when sequence dependent setup times are considered. As setup times and multi-criteria problems are important in industry, we must focus on this area. We propose a simple, yet powerful algorithm for the sequence dependent setup times flowshop problem with several criteria. The presented method is referred to as Restarted Iterated Pareto Greedy or RIPG and is compared against the best performing approaches from the relevant literature. Comprehensive computational and statistical analyses are carried out in order to demonstrate that the proposed RIPG method clearly outperforms all other algorithms and, as a consequence, it is a state-of-art method for this important and practical scheduling problem.     

A shortest path-based approach to the multileaf collimator sequencing problem

The multileaf collimator sequencing problem is an important component in effective cancer treatment delivery. The problem can be formulated as finding a decomposition of an integer matrix into a weighted sequence of binary matrices whose rows satisfy a consecutive ones property. Minimising the cardinality of the decomposition is an important objective and has been shown to be strongly NP-hard, even for a matrix restricted to a single column or row. We show that in this latter case it can be solved efficiently as a shortest path problem, giving a simple proof that the one-row problem is fixed-parameter tractable in the maximum intensity. We develop new linear and constraint programming models exploiting this result. Our approaches significantly improve the best known for the problem, bringing real-world sized problem instances within reach of exact algorithms.     

Regularization of the backward-in-time Kuramoto-Sivashinsky equation

We are interested in solution techniques for backward-in-time evolutionary PDE problems arising in fluid mechanics. In addition to their intrinsic interest, such techniques have applications in the recently proposed retrograde data assimilation. As our model system we consider the terminal value problem for the Kuramoto-Sivashinsky equation in a 1D periodic domain. Such backward problems are typical examples of ill-posed problems, where any disturbances are amplified exponentially during the backward march. Hence, regularization is required in order to solve such a problem efficiently in practice. We consider regularization approaches in which the original ill-posed problem is approximated with a less ill-posed problem obtained by adding a regularization term to the original equation. While such techniques are relatively well understood for simple linear problems, in this work we investigate them carefully in the nonlinear setting and report on some interesting universal behavior. In addition to considering regularization terms with fixed magnitudes, we also mention briefly a novel approach in which these magnitudes are adapted dynamically using simple concepts from the Control Theory.     

Genetic learning of accurate and compact fuzzy rule based systems based on the 2-tuples linguistic representation

One of the problems that focus the research in the linguistic fuzzy modeling area is the trade-off between interpretability and accuracy. To deal with this problem, different approaches can be found in the literature. Recently, a new linguistic rule representation model was presented to perform a genetic lateral tuning of membership functions. It is based on the linguistic 2-tuples representation that allows the lateral displacement of a label considering an unique parameter. This way to work involves a reduction of the search space that eases the derivation of optimal models and therefore, improves the mentioned trade-off.Based on the 2-tuples rule representation, this work proposes a new method to obtain linguistic fuzzy systems by means of an evolutionary learning of the data base a priori (number of labels and lateral displacements) and a simple rule generation method to quickly learn the associated rule base. Since this rule generation method is run from each data base definition generated by the evolutionary algorithm, its selection is an important aspect. In this work, we also propose two new ad hoc data-driven rule generation methods, analyzing the influence of them and other rule generation methods in the proposed learning approach. The developed algorithms will be tested considering two different real-world problems.     

Limit cycles analysis of reset control systems with reset band

The reset band is a simple idea, and a must in practice, to improve reset compensation by adding extra phase lead in a feedback loop. However, a formal treatment of how the reset band can affect stability and performance of a reset control system is still an open issue. This work approaches the problem of the existence and stability of limit cycles of reset control systems with reset band. A frequency domain approach is given by using standard methods based on the describing function. In addition, closed-form expressions have been obtained for the describing function of arbitrary order full reset compensators with and without reset band.     

A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP

The difficulty to solve multiple objective combinatorial optimization problems with traditional techniques has urged researchers to look for alternative, better performing approaches for them. Recently, several algorithms have been proposed which are based on the ant colony optimization metaheuristic. In this contribution, the existing algorithms of this kind are reviewed and a proposal of a taxonomy for them is presented. In addition, an empirical analysis is developed by analyzing their performance on several instances of the bi-criteria traveling salesman problem in comparison with two well-known multi-objective genetic algorithms.     

Algorithms for solving matrix polynomial equations of special form

In this paper we consider a series of algorithms for calculating radicals of matrix polynomial equations. A particular aspect of this problem arise in author’s work, concerning parameter identification of linear dynamic stochastic system. Special attention is given to searching the solution of an equation in a neighbourhood of some initial approximation. The offered approaches and algorithms allow us to receive fast and quite exact solution. We give some recommendations for application of given algorithms.     

Probabilistic analysis of optimization algorithms-some aspects from a practical point of view

In this paper the utility and the difficulties of probabilistic analysis for optimization algorithms are discussed. Such an analysis is expected to deliver valuable criteria-better than the worst-case complexity-for the efficiency of an algorithm in practice. The author has done much work of that kind in the field of linear programming. Based on that experience he gives some insight into the general principles for such an approach. He reports on some typical and representative attempts to analyze algorithms, resp. problems, of linear and combinatorial optimization. For each case he describes the problem, the stochastic model under consideration, the algorithm, the results, and tries to give a brief idea of the way these results could be obtained. He concludes with a discussion of some drawbacks and difficulties in that field of research. Among these are the strong sensibility with respect to the chosen model, the restriction of results to the asymptotic case, the restriction to somehow inefficient algorithms, etc. These points are the reasons why probabilistic analysis is of limited value for practice today. On the other hand, they show which principal problems should be attacked in the future to obtain the desired utility.     

The asymptotic probabilistic behaviour of quadratic sum assignment problems

In this paper a surprising probabilistic behaviour of quadratic sum assignment problems is shown. The relative difference between worst and optimal solution value tends to zero with probability tending to one as the size of the problem goes to infinity. This result suggests that for high dimensional quadratic assignment problems even very simple approximation algorithms can in practice yield good suboptimal solutions.