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
32718924
k-Center Problems with Minimum Coverage
The k-center problem is a well-known facility location problem and can be described as follows: Given a complete undirected graph G=(V,E), a metric d:V×V→ℝ + and a positive integer k, we seek a subset U ⊆ V of at most k centers which minimizes the maximum distances from points in V to U. Formally, the objective function is given by: 
 
$$ \textstyle\min_{U\subseteq V,|U|\leq k}\max_{v\in V}\min_{r\in U}d(v,r).$$ 
 
As a typical example, we may want to set up k service centers (e.g., police stations, fire stations, hospitals, polling centers) and minimize the maximum distances between each client and these centers. The problem is known to be \(\mathcal{NP}\)-hard [2].
44734123
Meta-heuristic Algorithm for the Transshipment Problem with Fixed Transportation Schedules
In this work, we develop an efficient meta-heuristic genetic algorithm for a different type of transshipment problem with supplier and customer time windows, where flow through the crossdock (a kind of transshipment center) is constrained by fixed transportation schedules and crossdocks capacities, and which was proved to be NP -complete in the strong sense. And computational experiments are conducted to show the proposed heuristic outperforms CPLEX.
39897206
A Compromised Large-Scale Neighborhood Search Heuristic for Cargo Loading Planning
In this work, we propose a compromised large-scale neighborhood, which is embedded in simulated annealing to solve a cargo loading planning problem arising in logistics industry. It is "compromised" because it makes a tradeoff between the extensive backward checking work incurred in traditional subset-disjoint restriction and the possible infeasibility resulting from the relaxing the restriction. Extensive experiments have shown the competitive advantages of the heuristic approach. The proposed neighborhood search method is generally applicable.
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.
23454249
A compromised large-scale neighborhood search heuristic for capacitated air cargo loading planning
Cost effectiveness is central to the air freight forwarders. In this work, we study how an air freight forwarder should plan its cargo loading in order to minimize the total freight cost given a limited number of rented containers. To solve the problem efficiently for practical implementation, we propose a new large-scale neighborhood search heuristic. The proposed large-scale neighborhood relaxes the subset-disjoint restriction made in the existing literature; the relaxation risks a possibility of infeasible exchanges while at the same time it avoids the potentially large amount of checking effort required to enforce the subset-disjoint restriction. An efficient procedure is then used to search for improvement in the neighborhood. We have also proposed a subproblem to address the difficulties caused by the fixed charges. The compromised large-scale neighborhood (CLSN) search heuristic has shown stably superior performance when compared with the traditional large-scale neighborhood search and the mixed integer programming model.
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.
5431189
Failure probability of wire bonding packages
This paper presents a methodology/model for elastro-plastic analysis of the wire bonding packages. The methodology is based on finite element method for rate sensitive materials and applicable to very large deformation processes. Ultrasonic power is simulated as displacement boundary condition. Stress induced by the mismatch of the coefficient of thermal expansion (CTE) in the system because of temperature increase due to application of the ultrasonic or the reflow process is considered. The effect of temperature increase on material property is also accounted for. Nonlinear spring elements are adopted to simulate the gradual formation of intermetallic bonding layer between the ball and the electric pad. With these spring elements, the effect of stress and strain relaxation of the ball in the subsequent procedures such as reflow process is taken into account. The mechanical behavior of the silicon chip during the wire bonding with the ultrasonic irradiation and reflow process is thus revealed. Failure probability with reference to the stress distribution is discussed. The developed FE methodology is simple but effective to evaluate the failure probability of wire-bonding packages.
21384001
Numerical examination of performance of some exchange-correlation functionals for molecules containing heavy elements
The performance of 17 exchange-correlation functionals for molecules containing heavy elements are numerically examined through four-component relativistic density DFT calculations. The examined functionals show the similar accuracy as they do for the molecules containing light elements only except for bond lengths. LDA and OP86 produce good results for bond lengths and frequencies but bad bond energies. Different functionals do not show much different performance for bond energies except LDA. BP86 and GP86 produce results with average accuracy while LYP does not perform well. Although encouraging results are obtained with functional B97GGA-1, other heavily parameterized and meta-GGA functionals do not produce impressive results.
15217028
On scheduling concurrent multicast sessions over resource reserved network
Resource reserved network can provide guaranteed quality of service to end users, especially those services requiring high bandwidth and short delay, such as video conferencing, video on demand, etc. In this paper, we consider the multicast packing problem, where multiple multicast sessions request network services simultaneously. To maximize the profit, network service provider need to carefully schedule these multicast sessions under the capacity constraint. We first formulate the problem as an integer programming problem and propose an optimization algorithm using branch-and-bound technique. A valid upper bound and a lower bound are then derived by using a statistical method and a greedy heuristic, respectively. The simulation results illustrate that our optimization algorithm performs effectively within the two boundaries.
26734510
Estimate Test Execution Effort at an Early Stage: An Empirical Study
Software testing is becoming more and more important as it is a widely used activity to ensure software quality. Test execution becomes an activity in the critical path of a project. In this case, early estimation of test execution effort can benefit both tester managers and software projects. This paper reports an empirical study on early test execution effort estimation. In the study, we propose an approach which mainly consists of two parts: test case number prediction from use cases and test effort estimation based on the test suite execution vector model which combines test case number, test execution complexity and its tester together. For each part, we evaluate it with the data of real projects from a financial software company.