ABSTRACT The hazardous orienteering problem is the topic of this study. It is a variant of the well‐studied orienteering problem, where a vehicle, given a maximum mission time, has to select and visit customers out of a set of requests, aiming at maximizing the total profit associated with the customers selected. In the hazardous version of the problem we consider, the customers are associated with parcels that have to be collected, and some of them might explode during the transportation, after having been picked up. The probability of explosion depends on the characteristics of the parcel and on the time spent by the dangerous parcel itself on the vehicle. If an explosion happens, the collected profit is totally lost. The target becomes then to select the tour that maximizes the expected profit, taking into account the probability of catastrophic events happening. In this article, we propose an exact solving approach based on a mixed integer linear programming model which is dynamically modified by adding new constraints. The computational results substantially improve the state‐of‐the‐art for the problem.

Stochastic, meta-heuristic and linear construction algorithms for the design of DNA strands satisfying Hamming distance and reverse-complement constraints often use a GC-content constraint to pre-process the DNA strands. Since GC-content is a poor predictor of DNA strand hybridization strength the strands can be filtered by post-processing using thermodynamic calculations. An alternative approach is considered here, where the algorithms are modified to remove consideration of GC-content and rely on post-processing alone to obtain large sets of DNA strands with satisfactory melting temperatures. The two approaches (pre-processing GC-content and post-processing melting temperatures) are compared and are shown to be complementary when large DNA sets are desired. In particular, the second approach can give significant improvements when linear constructions are used.

In a recent paper spreading codes for CDMA systems were constructed based on Hadamard matrices and semi-bent functions. These codes were applicable to synchronous CDMA systems and to quasi-synchronous CDMA systems when a loosely-synchronized code is used. The codes consist of the union of rows of four Hadamard matrices. The codes can be assigned to a regular tessellation of hexagonal cells in such a way that the correlation between codewords assigned to adjacent cells is zero, while the correlation between codewords assigned to non-adjacent cells is small. The use of codewords from four Hadamard matrices allows greater codeword re-use distances than the use of codewords from a single Hadamard matrix. This has advantages for both satellite and terrestrial systems. These codes only support a single data rate. The current paper shows how orthogonal variable spreading factor codes can be created from them by a careful selection of the semi-bent functions used.

Spreading codes for code-division multiple-access (CDMA) systems are constructed based on Hadamard matrices and almost-bent functions. These codes can be assigned to a tessellation of hexagonal cells in such a way that codewords assigned to the same cell or to adjacent cells have zero cross-correlation. The nonzero cross-correlations in the code only apply to pairs of codewords assigned to nonadjacent cells. The codes have four times as many codewords as codes constructed from a single Hadamard matrix, which leads to significantly increased codeword re-use distances in comparison with the conventional use of a single Hadamard matrix with the same number of codewords per cell.

Variable length codes offer advantages for data compression, but are susceptible to loss of synchronization if a bit error occurs. This can be mitigated by the use of variable length codes with specific mechanisms for resynchronization. Such mechanisms exist in the codes known as Huffman Equivalent (HE) codes and T-codes. These have been extensively studied in the literature. For optimal compression a length vector is obtained from the probabilities of the symbols of the alphabet used. However, HE-codes and T-codes do not exist for all length vectors. In this paper, a new class of variable length codes with good synchronization properties is developed. These are referred to as ordered termination (OT) codes. OT-codes do exist for all length vectors. Experimental results and some theoretical support suggest that OT-codes compare favorably with HE- and T-codes.

Constant weight binary codes are used in a number of applications. Constructions based on mathematical structure are known for many codes. However, heuristic constructions unrelated to any mathematical structure can become of greater importance when the parameters of the code are larger. This paper considers the problem of finding constant weight codes with the maximum number of codewords from a purely algorithmic perspective. A set of heuristic and metaheuristic methods is presented and developed into a variable neighborhood search framework. The proposed method is applied to 383 previously studied cases with lengths between 29 and 63. For these cases it generates 153 new codes, with significantly increased numbers of codewords in comparison with existing constructions. For 10 of these new codes the number of codewords meets a known upper bound, and so these 10 codes are optimal. As well as the ability to generate new best codes, the approach has the advantage that it is a single method capable of addressing many sets of parameters in a uniform way.

The sequential ordering problem is a version of the asymmetric traveling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are respected, and the objective is to find a feasible solution with minimum cost. The sequential ordering problem models a lot of real world applications, mainly in the fields of transportation and production planning. In this paper we propose an extension of a well known ant colony system for the problem, aiming at making the approach more efficient on large problems. The extension is based on a problem manipulation technique that heuristically reduces the search space. Computational results, where the extended ant colony system is compared to the original one, are presented

A mixed code is an error-correcting code in which different entries of the codewords can be chosen from different alphabets. In this correspondence an upper bound is given for the number of codewords in a mixed code where all the entries can come from distinct alphabets. This bound improves the sphere packing bound in several directions. The result is specialized to a simpler form in the case when only two distinct alphabets are used. Numerical results are presented to show that, in various cases, two different forms of the bound and alternative choices of a parameter may give the strongest bound.

When variable length codes are used in the presence of error, slippage can occur. The number of symbols decoded before synchronization is regained can differ from the number of encoded symbols, causing misinterpretation of data. In previous work certain synchronization schemes have been shown to be satisfactory in preventing permanent loss of synchronization and slippage in the presence of random error. In this paper we demonstrate that these schemes can also be satisfactory in the presence of burst errors, and that their relative merits remain the same.

Many data compression techniques are essentially variable length codes. Such codes suffer from a vulnerability to error propagation. This occurs when an error causes the correspondence between the data stream and the stream of encoded symbols to be lost and continues until synchronization between the two is re-established. This paper compares a number of strategies for synchronization in which redundant synchronizing words are used with a mechanism for labelling or counting them. In each case the strategy is investigated for the prevention of error propagation, ensuring the re-establishment of the correspondence with the correct point in the data stream. Three classes of potential synchronization error are explored: the false recognition of spurious words, the loss of synchronizing words and synchronization misinterpretation, when one synchronizing word is confused with another. The probabilities of synchronization error are analysed. It is shown that the strategies are successful against random errors when they incorporate some mechanism for consistency checking. The relative merits of different schemes are demonstrated. The schemes are also compared with the technique known as bitstuffing. This is considered on its own and in combination with the other schemes.

Abstract We consider the reliability of regular graphs of degree k in which the vertices of the graph fail independently with probability p. The probability of disconnection is minimized for small values of p if the graph has connectivity k and has the smallest number of vertex cut sets with k vertices. In this paper, we show how to construct such graphs.