5216004
Flexible Demand Assignment Problem
This paper proposed a state-of-the-art local search for solving Flexible Demand Assignment problem (FDA) which considers the balance between revenue and cost in demand assignment. Different than the published studies, our research splits the FDA problem into three core subproblems as operators for neighborhood construction. The three specified subproblems One Bin Repack, Two Bins Repack and Unpack are proposed completely based on mathematical modelling, computational complexity, executive conditions and greedy solving methods. Benchmark experimental results have shown that the proposed local search improved to the best published heuristics by 2.34%.
15711911
A stochastic beam search for the berth allocation problem
In this paper, the optimization of the Berth Allocation Problem (BAP) is transformed into a multiple stage decision making procedure and a new multiple stage search method, namely stochastic beam search algorithm, is proposed to solve it. New techniques such as an improved beam search scheme, a two-phase node goodness estimation, and a stochastic node selection criteria are proposed. Real-life information provided by Singapore Port was collected as our test data. Experimental results show that the proposed stochastic beam search is more accurate and efficient than both the state-of-the-art meta-heuristic and the traditional determinist beam search.
31981115
The Capacitated Traveling Salesman Problem with Pickups and Deliveries on a Tree
The Capacitated Traveling Salesman Problem with Pickups and Deliveries (CTSP-PD)[1] can be defined on an undirected graph T=(V,E), where V is a set of n vertices and E is a set of edges. A nonnegative weight d(e) is associated with each edge e∈ E to indicate its length. Each vertex is either a pickup point, a delivery point, or a transient point. At each pickup point is a load of unit size that can be shipped to any delivery point which requests a load of unit size. Hence we can use a(v)=1,0,–1 to indicate v to be a pickup, a transient, or a delivery point, and a(v) is referred to as the volume of v. The total volumes for pickups and for deliveries are usually assumed to be balanced, i.e., $\sum_{v\in {\it V}}{\it a}({\it v})=0$, which implies that all loads in pickup points must be shipped to delivery points [1]. Among V, one particular vertex r ∈ V is designated as a depot, at which a vehicle of limited capacity of k ≥ 1 starts and ends. The problem aims to determine a minimum length feasible route that picks up and delivers all loads without violating the vehicle capacity.
46289731
A Survey on Reviewer Assignment Problem
Research into Reviewer Assignment Problem (RAP) is still in its early stage but there is great world-wide interest, as the foregoing process of peer-review which is the brickwork of science authentication. The RAP approach can be divided into three phases: identifying assignment procedure, computing the matching degree between manuscripts and reviewers, and optimizing the assignment so as to achieve the given objectives. Methodologies for addressing the above three phases have been developed from a variety of research disciplines, including information retrieval, artificial intelligent, operations research, etc. This survey is not only to cover variations of RAP that have appeared in the literature, but also to identify the practical challenge and current progress for developing intelligent RAP systems.
42343733
On the Selection and Assignment with Minimum Quantity Commitments
Traditional selection and assignment problems analyze how to select and assign the suppliers to meet demands within minimum total costs. The maximum capacity and the fixed selection costs are two major restrictions imposed on suppliers, and extensively studied in literature.
40343100
The one-commodity pickup and delivery travelling salesman problem on a path or a tree
Optimization algorithms for both path and tree topology classes of the one-commodity pickup and delivery travelling salesman problem (1-PDTSP) are proposed in this article, which focus on minimizing the route distance to transport products among pickup and delivery customers by a single vehicle with a limited capacity of k . Each pickup customer provides one unit volume of the product while each delivery customer requires one unit volume of the product. For the path case, we propose an O(n2/ min (k , n)) algorithm for any arbitrary k , and two O(n) algorithms for k = 1 and k = ∞. For the tree case, O(n2) and O(n) algorithms are proposed for k = 1 and k = ∞, respectively. Moreover, when k is arbitrary, the problem becomes NP-hard in the strong sense. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 24–35 2006
39708575
A New Multi-view Learning Algorithm Based on ICA Feature for Image Retrieval
In content-based image retrieval (CBIR), most techniques involve an important issue of how to efficiently bridge the gap between the high-level concepts and low-level visual features. We propose a novel semi-supervised learning method for image retrieval, which makes full use of both ICA feature and general low-level feature. Our approach can be characterized by the following three aspects: (1) The ICA feature, as proved to be representative of human vision, is adopted as a view to describe human perception; (2) A multi-view learning algorithm is introduced to make the most use of different features and dramatically reduce human relevance feedback needed to achieve a satisfactory result; (3) A new semi-supervised learning algorithm is proposed to adapt to the small sample problem and other special constrains of our multi-view learning algorithm. Our experimental results and comparisons are presented to demonstrate the effectiveness of the proposed approach.
37403540
Analytical energy gradient evaluation in relativistic and nonrelativistic density functional calculations
The expressions of analytical energy gradients in density functional theory and their implementation in programs are reported. The evaluation of analytical energy gradients can be carried out in the fully 4-component relativistic, approximate relativistic, and nonrelativistic density functional calculations under local density approximation or general gradient approximation with or without frozen core approximation using different basis sets in our programs. The translational invariance condition and the fact that the one-center terms do not contribute to the energy gradients are utilized to improve the calculation accuracy and to reduce the computational effort. The calculated results of energy gradients and optimized geometry as well as atomization energies of some molecules by the analytical gradient method are in very good agreement with results obtained by the numerical derivative method.
8682866
Soft Error Rates with Inertial and Logical Masking
We analyze the neutron induced soft error rate (SER). An induced error pulse is modeled by two parameters, probability of occurrence and probability density function of the pulse width. We calculate failures in time (FIT) rates for ISCAS85 benchmark circuits. A comparison with measured SER for SRAMs shows better relevance of our work over other published work. Our CPU times are reasonable; benchmark circuit C1908 with 880 gates requires only 1.14seconds. Further, we study the influence of circuit topology on SER. We find that for some circuits with many levels of logic there exists a critical single event transient (SET) width. For smaller induced pulse width the SER depends not on the size of the circuit but only on the gates near the output, and only those need to be protected. For an inverter chain in TMSC035 technology, the critical width is between 25ps and 50ps. For a shallow circuit, e.g., a ripple-carry adder, the critical SET width may not exist.
6262582
On the construction of stable virtual backbones in mobile ad-hoc networks
In mobile ad-hoc networks, hosts communicate with each other without the help of any physical infrastructure. Inevitably, the communication tends to be less efficient in terms of computational and communicational overhead. Recent studies have shown that virtual backbone can help reduce the communication overhead. However, the backbone structure is very vulnerable due to several reasons, e.g., node mobility and unstable links, etc. In this paper, we introduce a localized virtual backbone construction scheme, connected maximal independent set with multiple initiators (MCMIS), which takes node stability into consideration and can construct the backbone quickly. We design MCMIS aiming at three goals: small backbone size, fast construction, stable backbone. Through extensive simulations, we find that our scheme could obtain a better performance on stability and backbone size than other localized schemes.
14622522
Short-Term Traffic Flow Prediction Based on Parallel Quasi-Newton Neural Network
Identifying and predicting the situation of traffic flow play an important role in traveler information broadcast and real-time traffic control. In this paper, a short-term traffic flow prediction model based on the parallel self-scaling quasi-Newton (SSPQN) neural network is presented. In this method, a set of parallel search directions are generated at the beginning of each iteration. Each of these directions is selectively chosen from a representative class of quasi-Newton (QN) methods. Inexact line searches are then carried out to estimate the minimum point along each search direction. Experimental and analytical results demonstrate the feasibility of applying SSPQN to traffic flow prediction and prove that it can better satisfy real-time demand of traffic flow prediction.