Uncertainty and imprecision modeling for the mobile robot localization problem

This article deals with uncertainty and imprecision treatment during the mobile robot localization process. The imprecision determination is based on the use of the interval formalism. Indeed, the mobile robot is equipped with an exteroceptive sensor and odometers. The imprecise data given by these two sensors are fused by constraint propagation on intervals. At the end of the algorithm, we get 3D localization subpaving which is supposed to contain the robot’s position in a guaranteed way. Concerning the uncertainty, it is managed through a propagation architecture based on the use of the Transferable Belief Model of Smets. This architecture enables to propagate uncertainty from low level data (sensor data) in order to quantify the global uncertainty of the robot localization estimation.

Fix-and-Relax-Coordination for a multi-period location–allocation problem under uncertainty

A multi-period discrete facility location problem is introduced for a risk neutral strategy with uncertainty in the costs and some of the requirements along the planning horizon. A compact 0–1 formulation for the Deterministic Equivalent Model of the problem under two alternative strategies for the location decisions is presented. Furthermore, a new algorithmic matheuristic, Fix-and-Relax-Coordination, is introduced. This solution scheme is based on a specialization of the Branch-and-Fix Coordination methodology, which exploits the Nonanticipativity Constraints and uses the Twin Node Family concept. The results of an extensive computational experience allow to compare the alternative modeling strategies and assess the effectiveness of the proposed approach versus the plain use of a state-of-the-art MIP solver.     

Legendre–Galerkin spectral approximation for a nonlocal elliptic Kirchhof-type problem

We propose a numerical scheme to obtain an approximate solution of a nonlocal elliptic Kirchhof-type problem. We first reduce the problem to a nonlinear finite dimensional system by a Legendre–Galerkin spectral method and then solve it by an iterative process. Convergence of the iterative process and an error estimation of the approximate solution is provided. Numerical experiments are conducted to illustrate the performance of the proposed method.     

Formulations and relaxations for a multi-echelon capacitated location–distribution problem

We consider a multi-echelon location–distribution problem arising from an actual application in fast delivery service. We present and compare two formulations for this problem: an arc-based model and a path-based model. We show that the linear programming (LP) relaxation of the path-based model provides a better bound than the LP relaxation of the arc-based model. We also compare the so-called binary relaxations of the models, which are obtained by relaxing the integrality constraints for the general integer variables, but not for the 0–1 variables. We show that the binary relaxations of the two models always provide the same bound, but that the path-based binary relaxation appears preferable from a computational point of view, since it can be reformulated as an equivalent simple plant location problem (SPLP), for which several efficient algorithms exist. We also show that the LP relaxation of this SPLP reformulation provides a better bound than the LP relaxation of the path-based model.     

Optimal allocation–consumption problem for a portfolio with an illiquid asset

During financial crises investors manage portfolios with low liquidity, where the paper-value of an asset differs from the price proposed by the buyer. We consider an optimization problem for a portfolio with an illiquid, a risky and a risk-free asset. We work in the Merton's optimal consumption framework with continuous time. The liquid part of the investment is described by a standard Black–Scholes market. The illiquid asset is sold at a random moment with prescribed distribution and generates additional liquid wealth dependent on its paper-value. The investor has a hyperbolic absolute risk aversion also denoted as HARA-type utility function, in particular, the logarithmic utility function as a limit case. We study two different distributions of the liquidation time of the illiquid asset – a classical exponential distribution and a more practically relevant Weibull distribution. Under certain conditions we show the smoothness of the viscosity solution and obtain closed formulae relevant for numerics.     

Continuous localization and mapping of a pan–tilt–zoom camera for wide area tracking

Pan–tilt–zoom (PTZ) cameras are well suited for object identification and recognition in far-field scenes. However, the effective use of PTZ cameras is complicated by the fact that a continuous online camera calibration is needed and the absolute pan, tilt and zoom values provided by the camera actuators cannot be used because they are not synchronized with the video stream. So, accurate calibration must be directly extracted from the visual content of the frames. Moreover, the large and abrupt scale changes, the scene background changes due to the camera operation and the need of camera motion compensation make target tracking with these cameras extremely challenging. In this paper, we present a solution that provides continuous online calibration of PTZ cameras which is robust to rapid camera motion, changes of the environment due to varying illumination or moving objects. The approach also scales beyond thousands of scene landmarks extracted with the SURF keypoint detector. The method directly derives the relationship between the position of a target in the ground plane and the corresponding scale and position in the image and allows real-time tracking of multiple targets with high and stable degree of accuracy even at far distances and any zoom level.     

Tabu search and lower bounds for a combined production–transportation problem

In this paper we consider a combined production–transportation problem, where n jobs have to be processed on a single machine at a production site before they are delivered to a customer. At the production stage, for each job a release date is given; at the transportation stage, job delivery should be completed not later than a given due date. The transportation is done by m identical vehicles with limited capacity. It takes a constant time to deliver a batch of jobs to the customer. The objective is to find a feasible schedule minimizing the maximum lateness.     

Family of quadratic spline difference schemes for a convection–diffusion problem

We consider the finite difference approximation of a singularly perturbed one-dimensional convection–diffusion two-point boundary value problem. It is discretized using quadratic splines as approximation functions, equations with various piecewise constant coefficients as collocation equations and a piecewise uniform mesh of Shishkin type. The family of schemes is derived using the collocation method. The numerical methods developed here are non-monotone and therefore apart from the consistency error we use Green's grid function analysis to prove uniform convergence. We prove the almost first order of convergence and furthermore show that some of the schemes have almost second-order convergence. Numerical experiments presented in the paper confirm our theoretical results.     

FA–QABC–MRTA: a solution for solving the multi-robot task allocation problem

Intelligent Service Robotics - The problem of task allocation in a multi-robot system is the situation where we have a set of tasks and a number of robots; then each task is assigned to the...     

Modular design of a hybrid genetic algorithm for a flexible job–shop scheduling problem

The aim of the job–shop scheduling problem is to optimize the task planning in an industrial plant satisfying time and technological constraints. The existing algorithmic and mathematical methods for solving this problem usually have high computational complexities making them intractable. Flexible job–shop scheduling becomes even more complex, since it allows one to assign each operation to a resource from a set of suitable ones. Alternative heuristic methods are only able to satisfy part of the constraints applicable to the problem. Moreover, these solutions usually offer little flexibility to adapt them to new requirements. This paper describes research within heuristic methods that combines genetic algorithms with repair heuristics. Firstly, it uses a genetic algorithm to provide a non-optimal solution for the problem, which does not satisfy all its constraints. Then, it applies repair heuristics to refine this solution. There are different types of heuristics, which correspond to the different types of constraints. A heuristic is intended to evaluate and slightly modify a solution that violates a constraint in a way that avoids or mitigates such violation. This approach improves the adaptability of the solution to a problem, as some changes can be addressed just modifying the considered chromosome or heuristics. The proposed solution has been tested in order to analyse its level of constraint satisfaction and its makespan, which are two of the main parameters considered in these types of problems. The paper discusses this experimentation showing the improvements over existing methods.     

A reactive GRASP and path relinking for a combined production–distribution problem

An NP-hard production–distribution problem for one product over a multi-period horizon is investigated. The aim is to minimize total cost taking production setups, inventory levels and distribution into account. An integer linear model is proposed as a compact problem specification but it cannot be solved to optimality for large instances. Instead of using a classical two-phase approach (production planning and then route construction for each day), metaheuristics that simultaneously tackle production and routing decisions are developed: a GRASP (greedy randomized adaptive search procedure) and two improved versions using either a reactive mechanism or a path-relinking process. These algorithms are evaluated on 90 randomly generated instances with 50, 100 and 200 customers and 20 periods. The results confirm the interest of integrating production and distribution decisions, compared to classical two-phase methods. Moreover, reaction and path-relinking give better results than the GRASP alone.     

A preference ordered classification for a multi-objective max–min redundancy allocation problem

In this study, we consider a bi-objective redundancy allocation problem on a series–parallel system with component level redundancy strategy. Our aim is to maximize the minimum subsystem reliability, while minimizing the overall system cost. The Pareto solutions of this problem are found by the augmented ε-constraint approach for small and moderate sized instances. After finding the Pareto solutions, we apply a well known sorting procedure, UTADIS, to categorize the solutions into preference ordered classes, such as A, B, and C. In this procedure, consecutive classes are separated by thresholds determined according to the utility function constructed from reference sets of classes. In redundancy allocation problems, reference sets may contain a small number of solutions (even a single solution). We propose the τ-neighborhood approach to increase the number of references. We perform experiments on some reliability optimization test problems and general test problems.     

Genotype–phenotype heuristic approaches for a cutting stock problem with circular patterns

The cutting stock problem has been studied in the context of different industrial applications inducing NP-hard problems in most instances. However, the application in sawmill has not received the same attention. In this paper, we deal with the problem of determining the number of logs to cut over a period of several days and the geometry of sawmill patterns in order to satisfy the demand while minimizing the loss of material. First, the problem is formulated as an integer programming problem of the form of a constrained set covering problem where the knowledge of a priori cutting patterns is necessary to generate its columns. In our implementation, these patterns are obtained using a genetic algorithm (GA) or a simulated annealing method (SA). Then, two different approaches are introduced to solve the problem. The first approach includes two methods that combine a metaheuristic to generate the number of logs and a constructive heuristic to generate the cutting patterns for each of the logs. In the second approach, we use an exact procedure CPLEX to solve the integer programming model where the cutting patterns are generated with the GA method (GA+CPLEX) or the SA method (SA+CPLEX). These four methods are compared numerically on 11 semi-randomly generated problems similar to those found in real life. The best results for the loss are obtained with the two-stage GA+CPLEX approach that finds the best values for 7 problems.     

Heuristic and exact algorithms for a min–max selective vehicle routing problem

In this work, we investigate a vehicle routing problem where not all clients need to be visited and the goal is to minimize the longest vehicle route. We propose two exact solution approaches for solving the problem: a Branch-and-cut (BC) algorithm and a Local Branching (LB) method that uses BC as its inner solver. Our computational experience indicates that, in practice, the problem is difficult to solve, mainly when the number of vehicles grows. In addition to the exact methods, we present a heuristic that relies on GRASP and on the resolution of a restricted integer program based on a set covering reformulation for the problem. The heuristic was capable of significantly improving the best solutions provided by BC and LB, in one tenth of the times taken by them to achieve their best upper bounds.     

What is a good evaluation protocol for text localization systems? Concerns,arguments, comparisons and solutions

A trustworthy protocol is essential to evaluate a text detection algorithm in order to, first measure its efficiency and adjust its parameters and, second to compare its performances with those of other algorithms. However, current protocols do not give precise enough evaluations because they use coarse evaluation metrics, and deal with inconsistent matchings between the output of detection algorithms and the ground truth, both often limited to rectangular shapes. In this paper, we propose a new evaluation protocol, named EvaLTex, that solves some of the current problems associated with classical metrics and matching strategies. Our system deals with different kinds of annotations and detection shapes. It also considers different kinds of granularity between detections and ground truth objects and hence provides more realistic and accurate evaluation measures. We use this protocol to evaluate text detection algorithms and highlight some key examples that show that the provided scores are more relevant than those of currently used evaluation protocols.     

Global optima for the Zhou–Rozvany problem

We consider the minimum compliance topology design problem with a volume constraint and discrete design variables. In particular, our interest is to provide global optimal designs to a challenging benchmark example proposed by Zhou and Rozvany. Global optimality is achieved by an implementation of a local branching method in which the subproblems are solved by a special purpose nonlinear branch-and-cut algorithm. The convergence rate of the branch-and-cut method is improved by strengthening the problem formulation with valid linear inequalities and variable fixing techniques. With the proposed algorithms, we find global optimal designs for several values on the available volume. These designs can be used to validate other methods and heuristics for the considered class of problems.     

Worker’s knowledge evaluation with single-player Monte Carlo tree search for a practical reentrant scheduling problem

This paper shows the application results of single-player Monte Carlo tree search (SP-MCTS), an alternative of MCTS, for a practical reentrant scheduling problem addressed by our previous works. Especially in this paper, worker’s IF-THEN knowledge evaluation method with SP-MCTS is proposed. SP-MCTS is thought to be a meta-heuristic algorithm for NP-completeness problems, because SP-MCTS is applicable for any types of problems, where the problem’s state changes determinately in each discrete time. Therefore, SP-MCTS might be useful for not only perfect-information one-player games, but also other problems, as long as search spaces are describable as a tree structure, and the solution is stoppable with the termination determinably. The authors have considered that SP-MCTS is useful for obtaining/evaluating knowledge. This paper first describes the basic idea of SP-MCTS, and second shows the detail of the scheduling problem, including formulation. After, this paper examines the availability of SP-MCTS for a practical problem. Especially, the potentiality of SP-MCTS for knowledge evaluation is discussed from the experimental results.     

Virtuality as a basis for problem solving?

This paper is an attempt to develop a paradigm in problem solving where the notion of virtuality plays a central role. Following a brief discussion on virtual simulation, the paper attempts to identify a notion of virtuality based on the identification of the self (man or computer) with the problem solver. It is shown that such an identification/distinction possibly violates some general principle of the problem environment.To deal with this violation, a new problem is generated and a new virtualization act is required, in order to attain a correspondence between virtuality and reality. A better understanding of this approach requires a combination of analog and digital reasoning: the analog being related to the environment in which the problem solving is required, and the digital to the problem solver's mental activities.We will briefly analyze the recursive approach to problem solving and suggest a possible problem solving methodology based on virtuality. The paper concludes with comments on the relation between etnology and virtual reality.     

A residual-based a posteriori error estimator for a fully-mixed formulation of the Stokes–Darcy coupled problem

In this paper we develop an a posteriori error analysis of a new fully mixed finite element method for the coupling of fluid flow with porous media flow in 2D. Flows are governed by the Stokes and Darcy equations, respectively, and the corresponding transmission conditions are given by mass conservation, balance of normal forces, and the Beavers–Joseph–Saffman law. We consider dual-mixed formulations in both media, which yields the pseudostress and the velocity in the fluid, together with the velocity and the pressure in the porous medium, and the traces of the porous media pressure and the fluid velocity on the interface, as the resulting unknowns. The set of feasible finite element subspaces includes Raviart–Thomas elements of lowest order and piecewise constants for the velocities and pressures, respectively, in both domains, together with continuous piecewise linear elements for the traces. We derive a reliable and efficient residual-based a posteriori error estimator for the coupled problem. The proof of reliability makes use of the global inf–sup condition, Helmholtz decompositions in both media, and local approximation properties of the Clément interpolant and Raviart–Thomas operator. On the other hand, inverse inequalities, the localization technique based on element-bubble and edge-bubble functions, and known results from previous works, are the main tools for proving the efficiency of the estimator. Finally, some numerical results confirming the theoretical properties of this estimator, and illustrating the capability of the corresponding adaptive algorithm to localize the singularities of the solution, are reported.     

A posteriori error analysis of a fully-mixed formulation for the Brinkman–Darcy problem

We develop the a posteriori error analysis for a mixed finite element method applied to the coupling of Brinkman and Darcy equations in 3D, modelling the interaction of viscous and non-viscous flow effects across a given interface. The system is formulated in terms of velocity and pressure within the Darcy subdomain, together with vorticity, velocity and pressure of the fluid in the Brinkman region, and a Lagrange multiplier enforcing pressure continuity across the interface. The solvability of a fully-mixed formulation along with a priori error bounds for a finite element method have been recently established in Álvarez et al. ( Comput Methods Appl Mech Eng 307:68–95, 2016). Here we derive a residual-based a posteriori error estimator for such a scheme, and prove its reliability exploiting a global inf-sup condition in combination with suitable Helmholtz decompositions, and interpolation properties of Clément and Raviart–Thomas operators. The estimator is also shown to be efficient, following a localisation strategy and appropriate inverse inequalities. We present numerical tests to confirm the features of the estimator and to illustrate the performance of the method in academic and application-oriented problems.