16656616
A smoothed dynamic tabu search embedded GRASP for m-VRPTW
Vehicle routing problem with both time window and limited number of vehicles (m-VRPTW) is an useful extension of VRPTW problem in real applications. We propose an improved greedy randomized adaptive search procedure (GRASP) framework by techniques including multiple initialization and solution reuse. Furthermore, a new technique of smoothed dynamic tabu search is embedded into the GRASP to improve the performance. The experimental results for benchmark data show that the new algorithm can solve the m-VRPTW problem better than the published algorithm in accuracy.
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.
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.
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.
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].
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.
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.
15143128
Multi-channel spectrum-agile MAC protocol with adaptive load control
Spectrum-agile radios, also known as cognitive radios, have a great potential to improve spectrum utilization by enabling dynamic access to the spectrum. A key challenge in operating these radios is how to implement an efficient medium access control (MAC) mechanism that adaptively and efficiently allocates transmission powers and spectrum according to the surrounding environment. In this work, we propose a distributed MAC protocol for operating spectrum-agile radios in a multihop ad hoc network. Our protocol differs from previous designs in that it exploits the “dual-receive” capability of radios, thus overcoming various channel access problems that are common to multi-channel designs. We conduct theoretical analysis of the protocol, and study its performance via simulations. We show significant improvement in the system throughput under the proposed MAC design. To maximize this throughput, we propose a cross-layer framework for joint adaptive load and medium access controls. In this framework, the loads of individual nodes are adapted based on the values of local MAC parameters. Simulation results show that the proposed scheme achieves more than 90% of the maximum (global) system throughput that is achieved at saturation, while guaranteeing low collision rates.
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.
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.
140126379
A Study on the Application of GA-BP Neural Network in the Bridge Reliability Assessment