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.     

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.     

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.     

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.     

IDENTIFYING SYSTEM FUNCTIONS

This article provides certain fairly rigorous, although still heuristic, methods for identifying the functional components of systems in such a way as to facilitate making relationships between the components and the overall system. Based on the definitions of function commonly used, making such a relationship is not always as easy as it could be made. Specific matters discussed herein include the following: functions and objectives-oriented thinking; logical versus physical thinking; functional outputs versus functional objectives; functional objectives versus system mission; directness of relationship to an objective; relationships between multiple functional objectives; distinguishing specific objectives within more general ones; the need to develop a consistent set of terms; etc.     

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.     

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.     

A decision support system for the bimodal dial-a-ride problem

A bimodal dial-a-ride problem (BDARP) considered in this paper is a dial-a-ride problem that involves two transportation modes: paratransit vehicles and fixed route buses. Riders in such a system might be transferred between different transportation modes during the service process. The motivation of this research is that by efficiently coordinating paratransit vehicles with fixed route buses we can improve the accessibility and efficiency of a dial-a-ride system. In this paper, we design a decision support system (DSS) which automatically constructs efficient paratransit vehicle routes and schedules for the BDARP. This DSS has been tested using actual data from the Ann Arbor Transportation Authority (AATA) in Ann Arbor, MI. The results show that this DSS produces an average increase of 10% in the number of requests that can be accommodated and an average decrease of 10% in the number of paratransit vehicles required, as compared to the manual results where no fixed route buses are involved     

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.     

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.     

Optimal scheduling of homogeneous job systems

Homogeneous job systems are systems in which all of a finite set of jobs to be processed by the system have exactly the same processing requirements. This paper assumes that each job first executes an input task requiring an input unit (channel or controller) for some amount of time T_c along with a memory unit. Then it executes a computational task requiring a processing unit and the memory for some amount of time T_p. Under these assumptions, it is possible to derive some inequalities concerning the relative number of memory, input, and processor units which can be efficiently used by the system as a function of T_c and T_p. The scheduling problem is to order tasks and assign resources to them in such a way as to minimize some cost function. The cost functions considered in this paper are job set finishing time and dwell time. Some theorems are stated and proved which yield closed form expressions for the minimum finishing time in batch and in time-shared systems as a function of the number of jobs, memories, processors, input units, and T_c and T_p. The purpose of this study is to derive some general results which aid in the efficient utilization of multiprocessor computer systems. Although this study is directed toward a specific type of homogeneous system, it is shown that the results are applicable to other systems (e.g., systems with output).     

Hybrid column generation and large neighborhood search for the dial-a-ride problem

Demographic change towards an ever aging population entails an increasing demand for specialized transportation systems to complement the traditional public means of transportation. Typically, users place transportation requests, specifying a pickup and a drop off location and a fleet of minibuses or taxis is used to serve these requests. The underlying optimization problem can be modeled as a dial-a-ride problem. In the dial-a-ride problem considered in this paper, total routing costs are minimized while respecting time window, maximum user ride time, maximum route duration, and vehicle capacity restrictions. We propose a hybrid column generation and large neighborhood search algorithm and compare different hybridization strategies on a set of benchmark instances from the literature.     

A simulating annealing algorithm to solve the green vehicle routing & scheduling problem with hierarchical objectives and weighted tardiness

We present a green vehicle routing and scheduling problem (GVRSP) considering general time-dependent traffic conditions with the primary objective of minimizing CO₂ emissions and weighted tardiness. A new mathematical formulation is proposed to describe the GVRSP with hierarchical objectives and weighted tardiness. The proposed formulation is an alternative formulation of the GVRSP in the way that a vehicle is allowed to travel an arc in multiple time periods. The schedule of a vehicle is determined based on the actual distance that the vehicle travels each arc in each time period instead of the time point when the vehicle departs from each node. Thereby, more general time dependent traffic patterns can be considered in the model. The proposed formulation is studied using various objectives functions, such as minimizing the total CO₂ emissions, the total travel distance, and the total travel time. Computational results show that up to 50% reduction in CO₂ emissions can be achieved with average reductions of 12% and 28% compared to distance-oriented solutions and travel-time-oriented solutions, respectively. In addition, a simulated annealing (SA) algorithm is introduced to solve large-sized problem instances. To reduce the search space, the SA algorithm searches only for vehicle routes and rough schedules, and a straightforward heuristic procedure is used to determine near-optimal detailed schedules for a given set of routes. The performance of the SA algorithm is tested on large-sized problems with up to 100 nodes and 10 time periods.     

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.     

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.     

Optimal sequencing of warm standby elements

Warm standby redundancy has been used as an effective design technique for improving the reliability of a system while achieving the compromise between restoration cost and operation cost of standby elements. This paper considers the optimal standby element sequencing problem (SESP) for 1-out-of-N: G heterogeneous warm-standby systems. Given the desired redundancy level and a fixed set of element choices, the objective of the optimal system design is to select the initiation sequence of the system elements so as to minimize the expected mission cost of the system while providing a certain level of system reliability. Based on a discrete approximation of time-to-failure distributions of the system elements, the system reliability and expected mission cost are evaluated using an iterative procedure. A genetic algorithm is used as an optimization tool for solving the formulated SESP problem for 1-out-of-N: G warm-standby systems with non-identical elements. As illustrated through examples, results generated using the suggested methodology can facilitate the system reliability versus cost trade-off study, which can further assist in the decision making about the best standby policy for fault-tolerant system designs.     

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.     

Dynamic multicast routing algorithm for delay and delay variation-bounded Steiner tree problem

The delay and delay variation-bounded Steiner tree problem is an important problem in real-time multimedia networks, and is known to be NP-complete. In this paper, we propose an efficient heuristic multicast routing algorithm based on simulated annealing named SADDVMA to construct the constrained Steiner tree. To avoid enlargement of search area and increase of computing time, the proposed heuristic algorithm uses a procedure called Paths-switching to construct neighbors in feasible region according to the relationship between delay and delay variation. We also give a method to dynamically reorganize the multicast tree in response to changes for the destinations. Simulations demonstrate that our algorithm is better in terms of tree cost as compared to the existing algorithms. Further, it performs excellent performance of delay and delay variation, rapid convergence and better real-time property.