An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a variation of the classical capacitated vehicle routing problem in which the objective is the minimization of the sum of arrival times at customers, instead of the total routing cost. This paper presents an adaptive large neighborhood search heuristic for the CCVRP. This algorithm is applied to a set of benchmark instances and compared with two recently published memetic algorithms.     

Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix

For scheduling flexible manufacturing systems efficiently, we propose new heuristic functions for A^* algorithm that is based on the T-timed Petri net. In minimizing makespan, the proposed heuristic functions are usually more efficient than the previous functions in the required number of states and computation time. We prove that these heuristic functions are all admissible and one of them is more informed than that using resource cost reachability matrix. We also propose improved versions of these heuristic functions that find a first near-optimal solution faster. In addition, we modify the heuristic function of Yu, Reyes, Cang, and Lloyd (2003b) and propose an admissible version in all states. The experimental results using a random problem generator show that the proposed heuristic functions perform better as we expected.     

Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix

For scheduling flexible manufacturing systems efficiently, we propose new heuristic functions for A^* algorithm that is based on the T-timed Petri net. In minimizing makespan, the proposed heuristic functions are usually more efficient than the previous functions in the required number of states and computation time. We prove that these heuristic functions are all admissible and one of them is more informed than that using resource cost reachability matrix. We also propose improved versions of these heuristic functions that find a first near-optimal solution faster. In addition, we modify the heuristic function of Yu, Reyes, Cang, and Lloyd (2003b) and propose an admissible version in all states. The experimental results using a random problem generator show that the proposed heuristic functions perform better as we expected.     

Breadth-first search: Some surprising results

Although breadth-first search procedures cannot explore truly large search spaces, actual implementations of such procedures can result in surprisingly powerful problem-solvers that outperform more sophisticated heuristic search procedures. We describe two breadth-first search procedures. The first one, S&R, proves theorems from Principia of Whitehead and Russell, and is compared to two versions of the Logic Theorist. Previous estimates of the size of the search space are significantly reduced. When theorems are proved in an optimal order, this order differs markedly from that found in Principia, while more general theorems than those of Principia are often found.The second system, S&M, adapts breadth-first search to locally infinite search spaces in systems of rewriting rules. S&M is compared extensively to the heuristic theorem-prover of Quinlan and Hunt, and to some other theorem provers.     

Approximate robust dynamic programming and robustly stable MPC

We present a technique for approximate robust dynamic programming that is suitable for linearly constrained polytopic systems with piecewise affine cost functions. The approximation method uses polyhedral representations of the cost-to-go function and feasible set, and can considerably reduce the computational burden compared to recently proposed methods for exact robust dynamic programming [Bemporad, A., Borrelli, F., & Morari, M. (2003). Min-max control of constrained uncertain discrete-time linear systems. IEEE Transactions on Automatic Control, 48(9), 1600-1606; Diehl, M., & Björnberg, J. (2004). Robust dynamic programming for min-max model predictive control of constrained uncertain systems. IEEE Transactions on Automatic Control, 49(12), 2253-2257]. We show how to apply the method to robust MPC, and give conditions that guarantee closed-loop stability. We finish by applying the method to a state constrained tutorial example, a parking car with uncertain mass.     

Optimal information retrieval when queries are not random

We consider the complexity of the general information retrieval system design problem and multiattribute file systems based upon the multiple key hashing (MKH) design problem. We first show that the problem of designing an optimal multiattribute file system is NP-hard. The performance formula for multiattribute file systems based upon the MKH method is derived. We also show that the design problem for a multiattribute file system based upon the MKH method is related to the prime number problem. We show that the problem of designing optimal multiattribute files based upon the MKH method can be reduced to finding minimal N-tuples, which was discussed by Chang, Lee and Du. We further present a very efficient method for designing good multiple key hashing functions in the case where the number of buckets is a power of a prime number. We also propose a heuristic algorithm to design good multiple key hashing functions in general.     

Optimal management for infinite capacity N-policy M/G/1 queue with a removable service station

In this article, we consider an infinite capacity N-policy M/G/1 queueing system with a single removable server. Poisson arrivals and general distribution service times are assumed. The server is controllable that may be turned on at arrival epochs or off at service completion epochs. We apply a differential technique to study system sensitivity, which examines the effect of different system input parameters on the system. A cost model for infinite capacity queueing system under steady-state condition is developed, to determine the optimal management policy at minimum cost. Analytical results for sensitivity analysis are derived. We also provide extensive numerical computations to illustrate the analytical sensitivity properties obtained. Finally, an application example is presented to demonstrate how the model could be used in real applications to obtain the optimal management policy.     

Variable neighborhood search for the dial-a-ride problem

In dial-a-ride problems passengers have to be transported between pre-specified pickup and delivery locations under user inconvenience considerations. The problem variant considered in this paper aims at minimizing total routing costs while respecting maximum route duration limits, time windows, and maximum user ride time limits. We propose a competitive variable neighborhood search-based heuristic, using three classes of neighborhoods. The first neighborhood class uses simple swap operations tailored to the dial-a-ride problem; the second neighborhood class is based on the ejection chain idea; and the third neighborhood class exploits the existence of arcs where the vehicle load is zero, giving rise to natural sequences of requests. We report new best results for 16 out of 20 benchmark instances.     

Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem

The paper addresses the problem of multi-depot vehicle routing in order to minimize the delivery time of vehicle objective. Three hybrid heuristics are presented to solve the multi-depot vehicle routing problem. Each hybrid heuristic combines elements from both constructive heuristic search and improvement techniques. The improvement techniques are deterministic, stochastic and simulated annealing (SA) methods. Experiments are run on a number of randomly generated test problems of varying depots and customer sizes. Our heuristics are shown to outperform one of the best-known existing heuristic. Statistical tests of significance are performed to substantiate the claims of improvement.     

On heuristics for minimum length rectilinear partitions

The problem of partitioning a rectilinear figure into rectangles with minimum length is NP-hard and has bounded heuristics. In this paper we study a related problem,Elimination Problem (EP), in which a rectilinear figure is partitioned into a set of rectilinear figures containing no concave vertices of a fixed direction with minimum length. We show that a heuristic for EP within a factor of 4 from optimal can be computed in timeO(n ²), wheren is the number of vertices of the input figure, and a variant of this heuristic, within a factor of 6 from optimal, can be computed in timeO(n logn). As an application, we give a bounded heuristic for the problem of partitioning a rectilinear figure into histograms of a fixed direction with minimum length. An auxiliary result is that an optimal rectangular partition of a monotonic histogram can be computed in timeO(n ²), using a known speed-up technique in dynamic programming.     

Supplier selection and purchase problem for multi-echelon defective supply chain system with stochastic demand

In the real production process, some members in the supply chain system sometimes cannot effectively complete their production task because of defects involving the production or purchasing of components. A supply chain system that has defects in at least one echelon is called a multi-echelon defective supply chain (MDSC) system. Most supply chain systems are MDSC systems. Determining parts or components supply quota from different suppliers with limited suppliers, factories and distribution centers capacities in the supply chain system are becoming an important issue for businesses. In this study, we propose a new heuristic (H2) which is an extension of H1 heuristic that was previously presented. The MDSC system was formed with the mixed integer linear programming by LINDO software for calculation of the lower bound. The heuristics and MDSC system were modeled by using ProModel software. The heuristics were applied to a case from the Turkish furniture industry. The heuristics were compared with each other by considering different coefficients of variation, service levels, and deviation from lower bound. Simulation experiments showed that the proposed H2 heuristic outperformed the H1 heuristic.     

The capacitated vehicle routing problem with stochastic demands and time windows

The capacitated vehicle routing problem with stochastic demands and time windows is an extension of the capacitated vehicle routing problem with stochastic demands, in which demands are stochastic and a time window is imposed on each vertex. A vertex failure occurring when the realized demand exceeds the vehicle capacity may trigger a chain reaction of failures on the remaining vertices in the same route, as a result of time windows. This paper models this problem as a stochastic program with recourse, and proposes an adaptive large neighborhood search heuristic for its solution. Modified Solomon benchmark instances are used in the experiments. Computational results clearly show the superiority of the proposed heuristic over an alternative solution approach.     

Unbounded parallel-batch scheduling with family jobs and delivery coordination

We study a scheduling problem that integrates parallel-batch production with family jobs and job delivery at the same time. The jobs are first processed on an unbounded parallel-batch machine and then delivered in batches to their specified customers by a transportation vehicle. We assume that jobs from different families (customers) cannot be processed together by the batch machine and also transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We first show that the problem is NP-hard, and then propose for it a heuristic algorithm with a worst-case performance ratio of 3/2.     

Test-cost-sensitive attribute reduction

In many data mining and machine learning applications, there are two objectives in the task of classification; one is decreasing the test cost, the other is improving the classification accuracy. Most existing research work focuses on the latter, with attribute reduction serving as an optional pre-processing stage to remove redundant attributes. In this paper, we point out that when tests must be undertaken in parallel, attribute reduction is mandatory in dealing with the former objective. With this in mind, we posit the minimal test cost reduct problem which constitutes a new, but more general, difficulty than the classical reduct problem. We also define three metrics to evaluate the performance of reduction algorithms from a statistical viewpoint. A framework for a heuristic algorithm is proposed to deal with the new problem; specifically, an information gain-based λ-weighted reduction algorithm is designed, where weights are decided by test costs and a non-positive exponent λ, which is the only parameter set by the user. The algorithm is tested with three representative test cost distributions on four UCI (University of California - Irvine) datasets. Experimental results show that there is a trade-off while setting λ, and a competition approach can improve the quality of the result significantly. This study suggests potential application areas and new research trends concerning attribute reduction.     

A simple effective heuristic for embedded mixed-integer quadratic programming

ABSTRACT

In this paper, we propose a fast optimisation algorithm for approximately minimising convex quadratic functions over the intersection of affine and separable constraints (i.e. the Cartesian product of possibly nonconvex real sets). This problem class contains many NP-hard problems such as mixed-integer quadratic programming. Our heuristic is based on a variation of the alternating direction method of multipliers (ADMM), an algorithm for solving convex optimisation problems. We discuss the favourable computational aspects of our algorithm, which allow it to run quickly even on very modest computational platforms such as embedded processors. We give several examples for which an approximate solution should be found very quickly, such as management of a hybrid-electric vehicle drivetrain and control of switched-mode power converters. Our numerical experiments suggest that our method is very effective in finding a feasible point with small objective value; indeed, we see that in many cases, it finds the global solution.     

Decision on the memory size of embedded information systems in an ubiquitous maintenance environment

Over the last decade, emerging information communication technologies have changed our stereotype of manufacturing and service companies. Now products equipped with embedded systems can be wirelessly networked, which leads to gathering and analyzing product status, and taking appropriate actions for maintenance operations during product lifecycle in an ubiquitous way. In this environment, it is necessary to determine the appropriate memory size of embedded systems for minimizing total maintenance system costs because the memory cost is a main cost factor for implementing the ubiquitous maintenance environment. We call it memory size decision problem in this study. We have formulated this problem with a non-linear model having constraints. The decision variable is the memory size of each embedded system. To solve this problem, we have proposed a meta heuristic search method based on genetic algorithms. To show the usefulness of the proposed heuristic, we have carried out computational experiments.     

Partitioning functions for stateful data parallelism in stream processing

In this paper, we study partitioning functions for stream processing systems that employ stateful data parallelism to improve application throughput. In particular, we develop partitioning functions that are effective under workloads where the domain of the partitioning key is large and its value distribution is skewed. We define various desirable properties for partitioning functions, ranging from balance properties such as memory, processing, and communication balance, structural properties such as compactness and fast lookup, and adaptation properties such as fast computation and minimal migration. We introduce a partitioning function structure that is compact and develop several associated heuristic construction techniques that exhibit good balance and low migration cost under skewed workloads. We provide experimental results that compare our partitioning functions to more traditional approaches such as uniform and consistent hashing, under different workload and application characteristics, and show superior performance.     

Extension of unbiased minimum-variance input and state estimation for systems with unknown inputs

This paper extends the existing results on joint input and state estimation to systems with arbitrary unknown inputs. The objective is to derive an optimal filter in the general case where not only unknown inputs affect both the system state and the output, but also the direct feedthrough matrix has arbitrary rank. The paper extends both the results of Gillijns and De Moor [Gillijns, S., & De Moor, B. (2007b). Unbiased minimum-variance input and state estimation for linear discrete-time systems with direct feedthrough. Automatica, 43, 934–937] and Darouach, Zasadzinski, and Boutayeb [Darouach, M., Zasadzinski, M., & Boutayeb, M. (2003). Extension of minimum variance estimation for systems with unknown inputs. Automatica, 39, 867–876]. The resulting filter is an extension of the recursive three-step filter (ERTSF) and serves as a unified solution to the addressed unknown input filtering problem. The relationship between the ERTSF and the existing literature results is also addressed.     

Antagonistic control

In antagonistic control we find an input sequence that maximizes (or at least makes large) an objective that is minimized in typical control. Applications include designing inputs to attack a control system, worst-case analysis of a control system, and security assessment of a control system. The antagonistic control problem is not convex, and so cannot be efficiently solved. We present here a powerful convex-optimization-based heuristic for antagonistic control, based on the convex–concave procedure, which can be used to find bad, if not the global worst-case, inputs. We also give an S-procedure-based upper bound for antagonistic control, applicable in cases when the objective and constraints can be described by quadratic inequalities, and use this to verify on examples that our method yields inputs very close to the (global) worst-case.     

On the Huffman and Alphabetic Tree Problem with General Cost Functions

We address generalized versions of the Huffman and Alphabetic Tree Problem where the cost caused by each individual leaf i, instead of being linear, depends on its depth in the tree by an arbitrary function. The objective is to minimize either the total cost or the maximum cost among all leaves. We review and extend the known results in this direction and devise a number of new algorithms and hardness proofs. It turns out that the Dynamic Programming approach for the Alphabetic Tree Problem can be extended to arbitrary cost functions, resulting in a time O(n ⁴) optimal algorithm using space O(n ³). We identify classes of cost functions where the well-known trick to reduce the runtime by a factor of n via a “monotonicity” property can be applied. For the generalized Huffman Tree Problem we show that even the k-ary version can be solved by a generalized version of the Coin Collector Algorithm of Larmore and Hirschberg (in Proc. SODA’90, pp. 310–318, 1990) when the cost functions are nondecreasing and convex. Furthermore, we give an O(n ²logn) algorithm for the worst case minimization variants of both the Huffman and Alphabetic Tree Problem with nondecreasing cost functions. Investigating the limits of computational tractability, we show that the Huffman Tree Problem in its full generality is inapproximable unless P = NP, no matter if the objective function is the sum of leaf costs or their maximum. The alphabetic version becomes NP-hard when the leaf costs are interdependent.