We present a natural probabilistic variation of the multi-depot vehicle routing problem with pickup and delivery (MDVRPPD).In this paper, we present a variation of this deterministic problem, where each pair of pickup and delivery points are present with some probability, and their realization are only known after the routes are computed.We denote this stochastic version by S-MDVRPPD.One route for each depot must be computed satisfying precedence constraints, where each pickup point must appear before its delivery pair in the route.The objective is to find a solution with minimum expected traveling distance.We present a closed-form expression to compute the expected length of an a priori route under general probabilistic assumptions.To solve the S-MDVRPPD we propose an Iterated Local Search (ILS) that uses the Variable Neighborhood Descent (VND) as local search procedure.The proposed heuristic was compared with a Tabu Search (TS) algorithm based on a previous work.We evaluate the performance of these heuristics on a data set adapted from TSPLIB instances.The results show that the ILS proposed is efficient and effective to solve S-MDVRPPD.

In this paper we consider the Online Bin Packing Problem in three variants: Circles in Squares, Circles in Isosceles Right Triangles, and Spheres in Cubes. The two first ones receive an online sequence of circles (items) of different radii while the third one receive an online sequence of spheres (items) of different radii, and they want to pack the items into the minimum number of unit squares, isosceles right triangles of leg length one, and unit cubes, respectively. For Online Circle Packing in Squares, we improve the previous best-known competitive ratio for the bounded space version, when at most a constant number of bins can be open at any given time, from 2.439 to 2.3536. For Online Circle Packing in Isosceles Right Triangles and Online Sphere Packing in Cubes we show bounded space algorithms of asymptotic competitive ratios 2.5490 and 3.5316, respectively, as well as lower bounds of 2.1193 and 2.7707 on the competitive ratio of any online bounded space algorithm for these two problems. We also considered the online unbounded space variant of these three problems which admits a small reorganization of the items inside the bin after their packing, and we present algorithms of competitive ratios 2.3105, 2.5094, and 3.5146 for Circles in Squares, Circles in Isosceles Right Triangles, and Spheres in Cubes, respectively.

Wireless sensor networks consist of hundreds or thousands of nodes with limited energy resources. Due to the high density of nodes in this kind of network, redundant data will be detected by nearby nodes. Since the network lifetime is a key issue in wireless sensor networks, in-network data aggregation can be exploited in order to reduce the number of messages exchanged and consequently reduce the energy consumption. Although there are many data aggregation solutions in wireless sensor networks, most of them leads to low quality routing trees and does not address the load balancing problem, since the same tree is used throughout the network life. To tackle these challenges we propose a Continuous Enhancement Routing Solution named as CER, an approach for computing increasingly better routing trees. CER was extensively compared to three other known solutions: the Shortest Path Tree (SPT), Data Aggregation Aware Routing Protocol (DAARP) and Dynamic Data Aggregation Aware Routing Protocol (DDAARP). The obtained results show that CER outperforms these solutions in all evaluations performed.

We investigate a variant of the many‐to‐many hub location‐routing problem which consists in partitioning the set of nodes of a graph into routes containing exactly one hub each, and determining an extra route interconnecting all hubs. A variable neighborhood descent with neighborhood structures based on remove/add, swap and exchange moves nested with routing and location operations is used as a local search procedure in a multistart algorithm. We also consider a sequential version of this local search in the multistart. In addition, a biased random‐key genetic algorithm working with a local search routine, which also considers routing and location operations, is applied to the problem. To compare the heuristic solutions, we develop an integer programming formulation which is solved with a branch‐and‐cut algorithm. Capacity and path elimination constraints are added in a cutting plane fashion. The separation algorithms are based on the computation of min‐cut trees and on the connected components of a support graph. Computational experiments were conducted on several benchmark instances of routing problems and show that the heuristics are effective on medium to large‐sized instances, while the branch‐and‐cut algorithm solves small to medium sized problems to optimality. These algorithms were also compared with a commercial hybrid solver showing that the heuristics are quite competitive. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(1), 54–90 2016

In this paper we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to be paid. We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer linear programming model as initial chromosomes of the population. An experimental evaluation compares the effectiveness of the proposed algorithms with the standard mixed linear integer programming formulation, a specialized exact algorithm, and the best-performing heuristics proposed for this problem. The proposed algorithms are competitive and offer strong results, mainly for large-scale auctions.

In Overlapping Correlation Clustering (OCC), a number of objects are assigned to clusters. Two objects in the same cluster have correlated characteristics. As opposed to traditional clustering where objects are assigned to a single cluster, in OCC objects may be assigned to one or more clusters. In this paper, we present Biased Random-Key Genetic Algorithms for OCC. We present computational experiments such results outperformed the state of art methods for OCC.

This work deals with the 0-1 knapsack problem in its two-dimensional variant, when there is a conflict graph related to pairs of conflicting items. Conflicting items must not be packed together in a same bin. This problem also arises as a subproblem in the bin packing problem and in supply chain scenarios. We propose a heuristic that generates iteratively a solution using a so called greedy randomized procedure. In order to avoid local optima solutions, a penalization memory list is used, and several packing strategies under a two-dimensional grid of points are considered. The heuristic solutions are compared with those ones computed by means of an integer programming model, also proposed in this work and solved with CPLEX solver. The heuristic got optimal solutions for 75% of the instances in a lower CPU time compared with that to solve the integer model.

We introduce the $k$-Interconnected Multi-Depot Multi-Traveling Salesmen Problem, a new problem that resembles some network design and location routing problems but carries the inherent difficulty of not having a fixed set of depots or terminals. We propose a heuristic based on a biased random-key genetic algorithm to solve it. This heuristic uses local search procedures to best choose the terminal vertices and improve the tours of a given solution. We compare our heuristic with a multi-start procedure using the same local improvements and we show that the proposed algorithm is competitive.

We consider a game-theoretic bin packing problem with identical items, and we study the convergence time to a Nash equilibrium. In the model proposed, users choose their strategy simultaneously. We deal with two bins and multiple bins cases. We consider the case when users know the load of all bins and a case with less information. We consider two approaches, depending if the system can undo movements that lead to infeasible states. In the two bins case, we show an O (log log n) bound when undo movements are allowed. In multiple bins case, we show an O (log n) and an O (nm) bounds when undo movements are allowed and when they are not allowed, respectively. In the case with less information, we show an O (m log n) and an O (n3m) bounds when undo movements are allowed and when they are not allowed, respectively.

We have been developing general user steered image segmentation strategies for routine use in applications involving a large number of data sets. In the past, we have presented three segmentation paradigms: live wire, live lane, and a three-dimensional (3-D) extension of the live-wire method. In this paper, we introduce an ultra-fast live-wire method, referred to as live wire on the fly, for further reducing user's time compared to the basic live-wire method. In live wire, 3-D/four-dimensional (4-D) object boundaries are segmented in a slice-by-slice fashion. To segment a two-dimensional (2-D) boundary, the user initially picks a point on the boundary and all possible minimum-cost paths from this point to all other points in the image are computed via Dijkstra's algorithm. Subsequently, a live wire is displayed in real time from the initial point to any subsequent position taken by the cursor. If the cursor is close to the desired boundary, the live wire snaps on to the boundary. The cursor is then deposited and a new live-wire segment is found next. The entire 2-D boundary is specified via a set of live-wire segments in this fashion. A drawback of this method is that the speed of optimal path computation depends on image size. On modestly powered computers, for images of even modest size, some sluggishness appears in user interaction, which reduces the overall segmentation efficiency. In this work, we solve this problem by exploiting some known properties of graphs to avoid unnecessary minimum-cost path computation during segmentation. In live wire on the fly, when the user selects a point on the boundary the live-wire segment is computed and displayed in real time from the selected point to any subsequent position of the cursor in the image, even for large images and even on low-powered computers. Based on 492 tracing experiments from an actual medical application, we demonstrate that live wire on the fly is 1.3-31 times faster than live wire for actual segmentation for varying image sizes, although the pure computational part alone is found to be about 120 times faster.

We present approximation algorithms for the orthogonal z-oriented three-dimensional packing problem (TPP z ) and analyze their asymptotic performance bound. This problem consists in packing a list of rectangular boxes L=(b 1 ,b 2 ,. . . ,b n ) into a rectangular box B=(l,w,\infty)$, orthogonally and oriented in the z-axis, in such a way that the height of thepacking is minimized. We say that a packing is oriented in the z-axis when the boxes in L are allowed to be rotated (by ninety degrees) around the z-axis. This problem has some nice applications but has been less investigated than the well-known variant of it---denoted by TPP (three-dimensional orthogonal packing problem)---in which rotations of the boxes are not allowed. The problem TPP can be reduced to TPP z . Given an algorithm for TPP z , we can obtain an algorithm for TPP with the same asymptotic bound. We present an algorithm for TPP z , called R, and three other algorithms, called LS, BS, and SS, for special cases of this problem in which the instances are more restricted. The algorithm LS is for the case in which all boxes in L have square bottoms; BS is for the case in which the box B has a square bottom, and SS is for the case in which the box B and all boxes in L have square bottoms. For an algorithm $\wa$, we denote by $r(\wa)$ the asymptotic performance bound of $\wa$. We show that $2.5\leq r(R) < 2.67$, $\ 2.5\leq r(LS)\leq 2.528$,$\ 2.5\leq r(BS)\leq 2.543$, and $\ 2.333\leq r(SS)\leq 2.361$. The algorithms presented here have the same complexity ${\cal O}(n\log n)$ as the other known algorithms for these problems, but they have better asymptotic performance bounds.