Correspondence of projected 3‐D points and lines using a continuous GRASP

The field of computer vision has experienced rapid growth over the past 50 years. Many computer vision problems have been solved using theory and ideas from algebraic projective geometry. In this paper, we look at a previously unsolved problem from object recognition, namely object recognition when the correspondences between the object and image data are not known a priori. We formulate this problem as a mixed‐integer non‐linear optimization problem in terms of the unknown projection relating the object and image, as well as the unknown assignments of object points and lines to those in the image. The global optimum of this problem recovers the relationship between the object points and lines with those in the image. When certain assumptions are enforced on the allowable projections mapping the object into the image, a proof is provided which permits one to solve the optimization problem via a simple decomposition. We illustrate this decomposition approach on some example scenarios.     

The constrained shortest path tour problem

In this paper, we study the constrained shortest path tour problem. Given a directed graph with non-negative arc lengths, the aim is to find a single-origin single-destination shortest path, which needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be of different size. In addition, it is required that the path does not include repeated arcs.Theoretical properties of the problem are studied, proving that it belongs to the complexity class NP-complete. To exactly solve it, a Branch & Bound method is proposed. Given the problem hardness, a Greedy Randomized Adaptive Search Procedure is also developed to find near-optimal solutions for medium to large scale instances.Extensive computational experiments, on a significant set of test problems, are carried out in order to empirically evaluate the performance of the proposed approaches. The computational results show that the Greedy Randomized Adaptive Search Procedure is effective in finding optimal or near optimal solutions in very limited computational time.     

A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints

This paper addresses the maximum network lifetime problem in wireless sensor networks with connectivity and coverage constraints. In this problem, the purpose is to schedule the activity of a set of wireless sensors, keeping them connected while network lifetime is maximized. Two cases are considered. First, the full coverage of the targets is required, and second only a fraction of the targets has to be covered at any instant of time. An exact approach based on column generation and boosted by GRASP and VNS is proposed to address both of these problems. Finally, a multiphase framework combining these two approaches is built by sequentially using these two heuristics at each iteration of the column generation algorithm. The results show that our proposals are able to tackle the problem efficiently and that combining the two heuristic approaches improves the results significantly.     

Workspace Generation for Multifingered Manipulation

In this paper, we propose a novel numerical approach and algorithm to compute and visualize the workspace of a multifingered hand manipulating an object. Based on feasibility analysis of grasps, the proposed approach uses an optimization technique to first compute discretely the position boundary of the grasped object and then calculate the rotation ranges of the object at specified positions within the boundary. In other words, workspace generation with the approach is fulfilled by obtaining reachable boundaries of the grasped object in the sense of both position and orientation, and the discrete boundary points are computed by a series of optimization models. Unlike in workspace generation of other robotic systems where only geometric and kinematic parameters of the robots are considered, all factors including geometric, kinematic and force-related factors that affect the workspace of a hand–object system can be taken into account in our approach to generate the workspace of multifingered manipulation. Since various constraints can be integrated into the optimization models, our method is general and complete, with adaptability to various grasps and manipulations. Workspace generation with the approach in both planar and spatial cases are illustrated with examples. The approach provides an effective and general solution to the long-term open and challenging problem of workspace generation of multifingered manipulation. Part of the work has been published in the Proceedings of IEEE/RSJ IROS2008 and IEEE/ASME AIM2008.     

Community detection by modularity maximization using GRASP with path relinking

Complex systems in diverse areas such as biology, sociology and physics are frequently being modelled as graphs, that provide the mathematical framework upon which small scale dynamics between the fundamental elements of the system can reveal large scale system behavior. Community structure in a graph is an important large scale characteristic, and can be described as a natural division of the vertices into densely connected groups, or clusters. Detection of community structure remains up to this date a computationally challenging problem despite the efforts of many researchers from various scientific fields in the past few years. The modularity value of a set of vertex clusters in a graph is a widely used quality measure for community structure, and the relating problem of finding a partition of the vertices into clusters such that the corresponding modularity is maximized is an NP-Hard problem.     

GRASP and path relinking for the equitable dispersion problem

The equitable dispersion problem consists in selecting a subset of elements from a given set in such a way that a measure of dispersion is maximized. In particular, we target the Max-Mean dispersion model in which the average distance between the selected elements is maximized. We first review previous methods and mathematical formulations for this and related dispersion problems and then propose a GRASP with a Path Relinking in which the local search is based on the Variable Neighborhood methodology. Our method is specially suited for instances in which the distances represent affinity and are not restricted to take non-negative values. The computational experience with 120 instances shows the merit of the proposed procedures compared to previous methods.     

A GRASP×ELS for the vehicle routing problem with basic three-dimensional loading constraints

This paper addresses an extension of the capacitated vehicle routing problem where the client demand consists of three-dimensional weighted items (3L-CVRP). The objective is to design a set of trips for a homogeneous fleet of vehicles based at a depot node which minimizes the total transportation cost. Items in each vehicle trip must satisfy the three-dimensional orthogonal packing constraints. This problem is strongly connected to real-life transportation systems where the packing of items to be delivered by each vehicle can have a significant impact on the routes. We propose a new way to solve the packing sub-problem. It consists of a two-step procedure in which the z-constraints are first relaxed to get a (x,y) positioning of the items. Then, a compatible z-coordinate is computed to get a packing solution. Items can be rotated but additional constraints such as item fragility, support and LIFO are not considered. This method is included in a GRASP×ELS hybrid algorithm dedicated to the computation of VRP routes. The route optimization alternates between two search spaces: the space of VRP routes and the space of giant trips. The projection from one to the other is done by dedicated procedures (namely the Split and the concatenation algorithms). Moreover, a Local Search is defined on each search space. Furthermore, hash tables are used to store the result of the packing checks and thus save a substantial amount of CPU time. The effectiveness of our approach is illustrated by computational experiments on 3L-CVRP instances from the literature. A new set of realistic instances based on the 96 French districts are also proposed. They range from 19 nodes for the small instances to 255 nodes for the large instances and they can be stated as realistic since they are based on true travel distances in kilometers between French cities. The impact of the hash tables is illustrated as well.     

A population-based metaheuristic for the pickup and delivery problem with time windows and LIFO loading

In this paper, we solve the pickup and delivery problem with time windows and last-in-first-out (LIFO) loading. LIFO loading minimizes handling while unloading items from the vehicle: the items are loaded according to a linear stack structure, and an item can only be delivered if it is the one on top of the stack. Three exact branch-price-and-cut algorithms are available for this problem. These can solve instances with up to 75 requests within one hour. We propose a population-based metaheuristic capable of handling larger instances much faster. First, a set of initial solutions is generated with a greedy randomized adaptive search procedure. For each of these solutions, local search is applied in order to first decrease the total number of vehicles and then the total traveled distance. Two different strategies are used to create offspring. The first selects vehicle routes from the solution pool. The second selects two parents to create an offspring with a crossover operator. For both strategies, local search is then performed on the child solution. Finally, the offspring is added to the population and the best survivors are kept. The population is managed so as to maintain good quality solutions with respect to total cost and population diversity. Computational results on medium to large instances confirm the effectiveness of the proposed metaheuristic.     

A GRASP algorithm for flexible job-shop scheduling with maintenance constraints

In most realistic situations, machines may be unavailable due to maintenance, pre-schedules and so on. The availability constraints are non-fixed in that the completion time of the maintenance task is not fixed and has to be determined during the scheduling procedure. In this paper a greedy randomised adaptive search procedure (GRASP) algorithm is presented to solve the flexible job-shop scheduling problem with non-fixed availability constraints (FJSSP-nfa). The GRASP algorithm is a metaheuristic algorithm which is characterised by multiple initialisations. Basically, it operates in the following manner: first a feasible solution is obtained, which is then further improved by a local search technique. The main objective is to repeat these two phases in an iterative manner and to preserve the best found solution. Representative FJSSP-nfa benchmark problems are solved in order to test the effectiveness and efficiency of the proposed algorithm.     

Simulated annealing for improving the solution of the response time variability problem

The response time variability problem (RTVP) is a scheduling problem that has a wide range of real-world applications in mixed-model assembly lines, multi-threaded computer systems, machine maintenance, waste collection and others. The RTVP arises whenever products, clients or jobs need to be sequenced in such a way that the variability in the time between the points at which they receive the necessary resources is minimised. The RTVP has been demonstrated to be NP-hard and heuristic and metaheuristic techniques are needed to solve large, real-life instances. The best results, on average, in the literature for the RTVP were obtained with variable neighbourhood search hybidised with multi-start. Several algorithms based on simulated annealing are proposed to solve the RTVP. An extensive computational experiment is carried out and it is shown that the solution of the RTVP is clearly improved.