With rapidly growing sizes of online social networks, computational challenges arise in analyzing the diffusion process over networks. Sampling methods are commonly used to study the cascade effect and estimate users' influence. In this paper, we propose a brand-new sampling method, called 2-hop+ sampling for quickly and accurately estimating the cascade size generated by a set of seed users under the independent cascade model. Our method generates only samples with at least one 2-hop live path from the source to reduce the number of samples. We further enhance the sampling efficiency of our method by a SkipEdge technique. Moreover, we improve the generalized stopping rule algorithm to obtain an (,)-estimate of the mean of random variables with fewer samples needed. Extensive experiments with real-world datasets show that our techniques can significantly improve the estimation efficiency compared to the state-of-the-art methods.

Existing deep reinforcement learning (DRL)-based methods for solving the capacitated vehicle routing problem (CVRP) intrinsically cope with a homogeneous vehicle fleet, in which the fleet is assumed as repetitions of a single vehicle. Hence, their key to construct a solution solely lies in the selection of the next node (customer) to visit excluding the selection of vehicle. However, vehicles in real-world scenarios are likely to be heterogeneous with different characteristics that affect their capacity (or travel speed), rendering existing DRL methods less effective. In this article, we tackle heterogeneous CVRP (HCVRP), where vehicles are mainly characterized by different capacities. We consider both min-max and min-sum objectives for HCVRP, which aim to minimize the longest or total travel time of the vehicle(s) in the fleet. To solve those problems, we propose a DRL method based on the attention mechanism with a vehicle selection decoder accounting for the heterogeneous fleet constraint and a node selection decoder accounting for the route construction, which learns to construct a solution by automatically selecting both a vehicle and a node for this vehicle at each step. Experimental results based on randomly generated instances show that, with desirable generalization to various problem sizes, our method outperforms the state-of-the-art DRL method and most of the conventional heuristics, and also delivers competitive performance against the state-of-the-art heuristic method, that is, slack induction by string removal. In addition, the results of extended experiments demonstrate that our method is also able to solve CVRPLib instances with satisfactory performance.

Recently, there is an emerging trend to apply deep reinforcement learning to solve the vehicle routing problem (VRP), where a learnt policy governs the selection of next node for visiting. However, existing methods could not handle well the pairing and precedence relationships in the pickup and delivery problem (PDP), which is a representative variant of VRP. To address this challenging issue, we leverage a novel neural network integrated with a heterogeneous attention mechanism to empower the policy in deep reinforcement learning to automatically select the nodes. In particular, the heterogeneous attention mechanism specifically prescribes attentions for each role of the nodes while taking into account the precedence constraint, i.e., the pickup node must precede the pairing delivery node. Further integrated with a masking scheme, the learnt policy is expected to find higher-quality solutions for solving PDP. Extensive experimental results show that our method outperforms the state-of-the-art heuristic and deep learning model, respectively, and generalizes well to different distributions and problem sizes.

Tracking ground support equipment (GSE) in a high accuracy manner is crucial for both airport safety and optimal management of airport assets but the related researches and products are scarce. Tracking a multi-carriage logistics train is obviously most challenging compared with other single-carriage GSE. In this paper, we design a real-time on-board positioning and heading system (ROPHS) to obtain the real-time status of a multi-carriage logistics train which consists of a powered leading vehicle and one or several non-powered trailing vehicles. The status includes: (a) the accurate positions and velocities of any points on this train, and (b) the alterable number and linking sequence of trailing vehicles at any time of a trip. Technically, the hardware of the system relies on real-time kinematic (RTK) to obtain geolocation of the leading vehicle, and on gyroscopes, magnetometers and accelerometers to obtain headings of all vehicles. A geometry based recurrence algorithm is afterwards presented to calculate the positions of any trailing vehicles. In the end, the multiple model based tracking algorithm is proposed to compute the precision-improved locations and real-time velocities of the whole train. Different from existing traditional GPS or RFID based positioning techniques, the proposed system can reach centimeter-level accuracy, which enables collisions detection, especially those latent collisions that cannot be easily monitored or foreseen by crews’ visual inspection.

Recent studies in using deep learning (DL) to solve routing problems focus on construction heuristics, whose solutions are still far from optimality. Improvement heuristics have great potential to narrow this gap by iteratively refining a solution. However, classic improvement heuristics are all guided by handcrafted rules that may limit their performance. In this article, we propose a deep reinforcement learning framework to learn the improvement heuristics for routing problems. We design a self-attention-based deep architecture as the policy network to guide the selection of the next solution. We apply our method to two important routing problems, i.e., the traveling salesman problem (TSP) and the capacitated vehicle routing problem (CVRP). Experiments show that our method outperforms state-of-the-art DL-based approaches. The learned policies are more effective than the traditional handcrafted ones and can be further enhanced by simple diversifying strategies. Moreover, the policies generalize well to different problem sizes, initial solutions, and even real-world data set.

3D deep learning has been increasingly more popular for a variety of tasks including many safety-critical applications. However, recently several works raise the security issues of 3D deep models. Although most of them consider adversarial attacks, we identify that backdoor attack is indeed a more serious threat to 3D deep learning systems but remains unexplored. We present the backdoor attacks in 3D point cloud with a unified framework that exploits the unique properties of 3D data and networks. In particular, we design two attack approaches on point cloud: the poison-label backdoor attack (PointPBA) and the clean- label backdoor attack (PointCBA). The first one is straight-forward and effective in practice, while the latter is more sophisticated assuming there are certain data inspections. The attack algorithms are mainly motivated and developed by 1) the recent discovery of 3D adversarial samples suggesting the vulnerability of deep models under spatial transformation; 2) the proposed feature disentanglement technique that manipulates the feature of the data through optimization methods and its potential to embed a new task. Extensive experiments show the efficacy of the PointPBA with over 95% success rate across various 3D datasets and models, and the more stealthy PointCBA with around 50% success rate. Our proposed backdoor attack in 3D point cloud is expected to perform as a baseline for improving the robustness of 3D deep models.

This companion paper is to support the replication of paper "Campus3D: A Photogrammetry Point Cloud Benchmark for Outdoor Scene Hierarchical Understanding", which was presented at ACM Multimedia 2020. The supported paper's main purpose was to provide a photogrammetry point cloud-based dataset with hierarchical multilabels to facilitate the area of 3D deep learning. Based on this provided dataset and source code, in this work, we build a complete package to reimplement the proposed methods and experiments (i.e., the hierarchical learning framework and the benchmarks of the hierarchical semantic segmentation task). Specifically, this paper contains the technical details of the package, including file structure, dataset preparation, installation package, and the conduction of the experiment. We also present the replicated experiment results and indicate our contributions to the original implementation.

Proof-of-Work (PoW) is the most widely adopted incentive model in current blockchain systems, which unfortunately is energy inefficient. Proof-of-Stake (PoS) is then proposed to tackle the energy issue. The rich-get-richer concern of PoS has been heavily debated in the blockchain community. The debate is centered around the argument that whether rich miners possessing more stakes will obtain higher staking rewards and further increase their potential income in the future. In this paper, we define two types of fairness, i.e., expectational fairness and robust fairness, that are useful for answering this question. In particular, expectational fairness illustrates that the expected income of a miner is proportional to her initial investment, indicating that the expected return on investment is a constant. To better capture the uncertainty of mining outcomes, robust fairness is proposed to characterize whether the return on investment concentrates to a constant with high probability as time evolves. Our analysis shows that the classical PoW mechanism can always preserve both types of fairness as long as the mining game runs for a sufficiently long time. Furthermore, we observe that current PoS blockchains implement various incentive models and discuss three representatives, namely ML-PoS, SL-PoS and C-PoS. We find that (i) ML-PoS (e.g., Qtum and Blackcoin) preserves expectational fairness but may not achieve robust fairness, (ii) SL-PoS (e.g., NXT) does not protect any type of fairness, and (iii) C-PoS (e.g., Ethereum 2.0) outperforms ML-PoS in terms of robust fairness while still maintaining expectational fairness. Finally, massive experiments on real blockchain systems and extensive numerical simulations are performed to validate our analysis.

A solar power plant is a large-scale photovoltaic (PV) system designed to supply usable solar power to the electricity grid. Building a solar power plant needs consideration of arrangements of several important components, such as PV arrays, solar inverters, combiner boxes, cables, and other electrical accessories. The design of solar power plants is very complex because of various optimization parameters and design regulations. In this study, we address the cable-routing problem arising in the planning of large-scale solar power plants, which aims to determine the partition of the PV arrays, the location of combiner boxes, and cable routing such that the installation cost of the cables connecting the components is minimized. We formulate the problem as a mathematical programming problem, which can be viewed as a generalized capacitated minimum spanning tree (CMST) problem, and then devise a branch-and-price-and-cut (BPC) algorithm to solve it. The BPC algorithm uses two important valid inequalities, namely the capacity inequalities and the subset-row inequalities, to tighten the lower bounds. We also adopt several acceleration strategies to speed up the algorithm. Using real-world data sets, we show by numerical experiments that our BPC algorithm is superior to the typical manual-based planning approach used by many electric power planning companies. In addition, when solving the CMST problem with unitary demands, our algorithm is highly competitive compared with the best exact algorithm in the literature.

In order to lower the ramp risk and improve the aircraft ground handling efficiency, we aim to: 1) track ground support equipment (GSE) in a real-time and high-accuracy manner so that we can not only conveniently obtain the positions and velocities of them but also reliably report latent collisions among aircraft and GSE. As a result, corresponding ramp risks could be detected and handled in advance and 2) schedule the GSE in an optimal manner based on the real-time data gathered in advance to make efficient use of GSE so that we can smoothly serve the annually increasing air traffic while controlling the ramp area congestion and GSE overheads. In detail, first, we develop a real-time and high-accuracy tracking device consisting of one real-time kinematic (RTK) unit and heading unit(s), for GSE including not only those which have only one carriage, such as tractors, shutters, and so forth but also baggage transit trains that contain one tug plus multiple dollies. The tracking accuracy for GSE could be limited within centimeters so that the monitor, avoidance, and fixation of unaware ramp risks become possible. Second, for optimal scheduling of GSE, a mixed-integer linear programming model and an efficient heuristic algorithm are proposed to minimize the total cost of equipment’s rental and travel consumption while respecting the constraints, such as flights timetables, GSE moving speeds limit, the total number of GSE available in stock, the maximum number of dollies allowed to attach to each baggage transit train, and so on.

This article proposes a new approach to sales forecasting for new products (stock-keeping units [SKUs]) with long lead time but short product life cycle. These SKUs are usually sold for one season only, without any replenishments. An exponential factorization machine (EFM) sales forecast model is developed to solve this problem which not only takes into account SKU attributes, but also pairwise interactions. The EFM model is significantly different from the original Factorization Machines (FM) from two fold: (1) the attribute-level formulation for explanatory/input variables; and (2) exponential formulation for the positive response/output/target variable. The attribute-level formation excludes infeasible intra-attribute interactions and results in more efficient feature engineering comparing with the conventional one-hot encoding, while the exponential formulation is demonstrated more effective than the log-transformation for the positive but not skewed distributed responses. In order to estimate the parameters, percentage error squares (PES) and error squares (ES) are minimized by a proposed adaptive batch gradient descent method over the training set. To overcome the over-fitting problem, a greedy forward stepwise feature selection method is proposed to select the most useful attributes and interactions. Real-world data provided by a footwear retailer in Singapore are used for testing the proposed approach. The forecasting performance in terms of both mean absolute percentage error (MAPE) and mean absolute error (MAE) compares favorably with not only off-the-shelf models but also results reported by extant sales and demand forecasting studies. The effectiveness of the proposed approach is also demonstrated by two external public datasets. Moreover, we prove the theoretical relationships between PES and ES minimization, and present an important property of the PES minimization for regression models; that it trains models to underestimate data. This property fits the situation of sales forecasting where unit-holding cost is much greater than the unit-shortage cost (e.g., perishable products).

While deep learning in 3D domain has achieved revolutionary performance in many tasks, the robustness of these models has not been sufficiently studied or explored. Regarding the 3D adversarial samples, most existing works focus on manipulation of local points, which may fail to invoke the global geometry properties, like robustness under linear projection that preserves the Euclidean distance, i.e., isometry. In this work, we show that existing state-of-the-art deep 3D models are extremely vulnerable to isometry transformations. Armed with the Thompson Sampling, we develop a black-box attack with success rate over 95% on ModelNet40 data set. Incorporating with the Restricted Isometry Property, we propose a novel framework of white-box attack on top of spectral norm based perturbation. In contrast to previous works, our adversarial samples are experimentally shown to be strongly transferable. Evaluated on a sequence of prevailing 3D models, our white-box attack achieves success rates from 98.88% to 100%. It maintains a successful attack rate over 95% even within an imperceptible rotation range [±2.81◦].

Given a social network G, the profit maximization (PM) problem asks for a set of seed nodes to maximize the profit, i.e., revenue of influence spread less the cost of seed selection. The target profit maximization (TPM) problem, which generalizes the PM problem, aims to select a subset of seed nodes from a target user set T to maximize the profit. Existing algorithms for PM mostly consider the nonadaptive setting, where all seed nodes are selected in one batch without any knowledge on how they may influence other users. In this paper, we study TPM in adaptive setting, where the seed users are selected through multiple batches, such that the selection of a batch exploits the knowledge of actual influence in the previous batches. To acquire an overall understanding, we study the adaptive TPM problem under both the oracle model and the noise model, and propose ADG and AddATP algorithms to address them with strong theoretical guarantees, respectively. In addition, to better handle the sampling errors under the noise model, we propose the idea of hybrid error based on which we design a novel algorithm HATP that boosts the efficiency of AddATP significantly. We conduct extensive experiments on real social networks to evaluate the performance, and the experimental results strongly confirm the superiorities and effectiveness of our solutions.

Learning on 3D scene-based point cloud has received extensive attention as its promising application in many fields, and well-annotated and multisource datasets can catalyze the development of those data-driven approaches. To facilitate the research of this area, we present a richly-annotated 3D point cloud dataset for multiple outdoor scene understanding tasks and also an effective learning framework for its hierarchical segmentation task. The dataset was generated via the photogrammetric processing on unmanned aerial vehicle (UAV) images of the National University of Singapore (NUS) campus, and has been point-wisely annotated with both hierarchical and instance-based labels. Based on it, we formulate a hierarchical learning problem for 3D point cloud segmentation and propose a measurement evaluating consistency across various hierarchies. To solve this problem, a two-stage method including multi-task (MT) learning and hierarchical ensemble (HE) with consistency consideration is proposed. Experimental results demonstrate the superiority of the proposed method and potential advantages of our hierarchical annotations. In addition, we benchmark results of semantic and instance segmentation, which is accessible online at https://3d.dataset.site with the dataset and all source codes.

Graph Convolutional Networks (GCNs) have shown promising results in modeling graph-structured data. However, they have difficulty with processing digraphs because of two reasons: 1) transforming directed to undirected graph to guarantee the symmetry of graph Laplacian is not reasonable since it not only misleads message passing scheme to aggregate incorrect weights but also deprives the unique characteristics of digraph structure; 2) due to the fixed receptive field in each layer, GCNs fail to obtain multi-scale features that can boost their performance. In this paper, we theoretically extend spectral-based graph convolution to digraphs and derive a simplified form using personalized PageRank. Specifically, we present the Digraph Inception Convolutional Networks (DiGCN) which utilizes digraph convolution and kth-order proximity to achieve larger receptive fields and learn multi-scale features in digraphs. We empirically show that DiGCN can encode more structural information from digraphs than GCNs and help achieve better performance when generalized to other models. Moreover, experiments on various benchmarks demonstrate its superiority against the state-of-the-art methods.

In this paper, a new branch-and-price-and-cut algorithm is proposed to solve the one-dimensional bin-packing problem (1D-BPP). The 1D-BPP is one of the most fundamental problems in combinatorial optimization and has been extensively studied for decades. Recently, a set of new 500 test instances were proposed for the 1D-BPP, and the best exact algorithm proposed in the literature can optimally solve 167 of these new instances, with a time limit of 1 hour imposed on each execution of the algorithm. The exact algorithm proposed in this paper is based on the classical set-partitioning model for the 1DBPPs and the subset row inequalities. We describe an ad hoc label-setting algorithm to solve the pricing problem, dominance, and fathoming rules to speed up its computation and a new primal heuristic. The exact algorithm can easily handle some practical constraints, such as the incompatibility between the items, and therefore, we also apply it to solve the one-dimensional bin-packing problem with conflicts (1D-BPPC). The proposed method is tested on a large family of 1D-BPP and 1D-BPPC classes of instances. For the 1D-BPP, the proposed method can optimally solve 237 instances of the new set of difficult instances; the largest instance involves 1,003 items and bins of capacity 80,000. For the 1D-BPPC, the experiments show that the method is highly competitive with state-of-the-art methods and that it successfully closed several open 1D-BPPC instances.

As a dual problem of influence maximization, the seed minimization problem asks for the minimum number of seed nodes to influence a required number η of users in a given social network G. Existing algorithms for seed minimization mostly consider the non-adaptive setting, where all seed nodes are selected in one batch without observing how they may influence other users. In this paper, we study seed minimization in the adaptive setting, where the seed nodes are selected in several batches, such that the choice of a batch may exploit information about the actual influence of the previous batches. We propose a novel algorithm, ASTI, which addresses the adaptive seed minimization problem in $O\Big(\fracη \cdot (m+n) \varepsilon^2 łn n \Big)$ expected time and offers an approximation guarantee of $\frac(łn η+1)^2 (1 - (1-1/b)^b) (1-1/e)(1-\varepsilon) $ in expectation, where η is the targeted number of influenced nodes, b is size of each seed node batch, and $\varepsilon \in (0, 1)$ is a user-specified parameter. To the best of our knowledge, ASTI is the first algorithm that provides such an approximation guarantee without incurring prohibitive computation overhead. With extensive experiments on a variety of datasets, we demonstrate the effectiveness and efficiency of ASTI over competing methods.

In this article, the authors introduce two citation‐based approaches to facilitate a multidimensional evaluation of 39 selected management journals. The first is a refined application of PageRank via the differentiation of citation types. The second is a form of mathematical manipulation to identify the roles that the selected management journals play. Their findings reveal that Academy of Management Journal, Academy of Management Review, and Administrative Science Quarterly are the top three management journals, respectively. They also discovered that these three journals play the role of a knowledge hub in the domain. Finally, when compared with Journal Citation Reports (Thomson Reuters, Philadelphia, PA), their results closely match expert opinions.

Abstract In this research, we study the capacitated traveling salesman problem with pickup and delivery (CTSPPD) on a tree, which aims to determine the best route for a vehicle with a finite capacity to transport amounts of a product from pickup points to delivery points on a tree network, such that the vehicle's total travel distance is kept to a minimum. It has several applications in logistics and is known to be NP‐hard. We develop a 2‐approximation algorithm that is a significant improvement over the best constant approximation ratio of 5 derived from existing CTSPPD literature. Computational results show that the proposed algorithm also achieves good average performance over randomly generated instances. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 179–195 2014

The container relocation problem, where containers that are stored in bays are retrieved in a fixed sequence, is a crucial port operation. Existing approaches using branch and bound algorithms are only able to optimally solve small cases in a practical time frame. In this paper, we investigate iterative deepening A* algorithms (rather than branch and bound) using new lower bound measures and heuristics, and show that this approach is able to solve much larger instances of the problem in a time frame that is suitable for practical application. We also examine a more difficult variant of the problem that has been largely ignored in existing literature.

In today's global free market, third-party logistics providers (3PLs) are becoming increasingly important. This paper studies a problem faced by a 3PL operating a warehouse in Shanghai, China, under contract with a major company for children's clothing based in the United States. The problem involves the allocation of textile parcel shipments at the warehouse to shipping routes with different destination ports, where the shipments are destined for different retail stores. The shipments must be loaded into containers of varying sizes and costs, and the objective is to find an allocation that minimizes the total container transportation and parcel delivery costs. We formulate the problem into an integer linear programming model, and also propose a genetic algorithm approach to solve the problem practically. A demonstration of a good solution to this problem was a decisive factor in the awarding of the contract to the 3PL in question.

The feasible solutions of the traveling salesman problem with pickup and delivery (TSPPD) are represented by vertex lists in existing literature. However, when the TSPPD requires that the loading and unloading operations must be performed in a last-in-first-out (LIFO) manner, we show that its feasible solutions can be represented by trees. Consequently, we develop a variable neighbourhood search (VNS) heuristic for the TSPPD with last-in-first-out loading (TSPPDL) involving several search operators based on the tree data structure. Experiments show that our VNS heuristic is superior to the current best heuristics for TSPPDL in terms of both solution quality and computing time.

We study a freight proportion allocation problem (FPAP), which is a kind of transportation problem faced by MG, one of the worldpsilas leading grocery retailers. MG has a large quantity of freight for carriers to ship to Europe. During the process of freight allocation, the shipper must consider three constraints, which are minimum quantity commitment (MQC), quantity limit per carrier and cost balance among sales divisions. With these constraints,the FPAP becomes computationally intractable. By incorporating random move subroutine, we devised a special Tabu search procedure to solve this problem. Different from classical Tabu search who usually runs in the feasible regions, random move Tabu search enables the search process to enter into infeasible regions and visit disjointed feasible regions. Extensive experiments have been conducted to measure the performance of our proposed Tabu search and CPLEX solver and have shown that the random move Tabu search behaves better.

Rather than dealing with the traditional one-dimension bin packing problem to minimize the cost in demand assignments, the flexible demand assignment (FDA) problem studied in this paper considers the balance between revenue and cost. Compared with a number of solution methods in operations research, we solve the FDA problem by three specially designed operators of neighborhood construction for search space-namely, One Bin Repack, Two Bins Repack, and Unpack. Extensive computational results clearly show the superiority of the three proposed operators based on simple local search over the best published results.

The vehicle routing problem with time windows (VRPTW) is an important problem in logistics. The problem is to serve a number of customers at minimum cost without violating the customers’ time-window constraints or the vehicle-capacity constraint. In this paper, we propose a two-stage algorithm for the VRPTW. The algorithm first minimizes the number of vehicles with an ejection pool to hold temporarily unserved customers, which enables the algorithm to go through the infeasible solution space. Then it minimizes the total travel distance using a multi-start iterated hill-climbing algorithm with classical and new operators including generalized ejection chains, which enable the algorithm to search a larger neighborhood. We applied the algorithm to Solomon’s 56 VRPTW instances and Gehring and Homberger’s 300 extended instances. The experimental results showed that the algorithm is effective and efficient in reducing the number of vehicles and is also very competitive in terms of distance minimization. The m-VRPTW is a variant of the VRPTW in which a limited number of vehicles is available. A feasible solution to m-VRPTW may contain some unserved customers due to the insufficiency of vehicles. The primary objective of m-VRPTW is to maximize the number of customers served. We extended our VRPTW algorithm to solve m-VRPTW and the experimental results showed consistently good performance of the algorithm when compared with other methods.

Abstract 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

Warehouse management is an important issue in supply chain management. Among all warehouse operations, "order-picking" is the most expensive one and its cost is mainly due to the travelling expenses. In this paper, we study the capacitated warehouse routing problem (CWRP) so as to save the travelling cost, i.e., travelling distance in order-picking. The problem is shown to be strongly NP-hard. However, by noting that the unconstrained routing problem can be tackled by a dynamic programming method, a search heuristic, which is based on the very large-scale neighborhood (VLSN) technique, was designed to solve the capacity-constrained version. We compared the computational results with solutions obtained from branch-and-price method, which are within 1% error bound and identified that our heuristic is efficient in getting high quality solutions of CWRP

In this paper, a combinatorial auction problem is modeled as a NP-complete set packing problem and a Lagrangian relaxation based heuristic algorithm is proposed. Extensive experiments are conducted using benchmark CATS test sets and more complex test sets. The algorithm provides optimal solutions for most test sets and is always 1%from the optimal solutions for all CATS test sets. Comparisons with CPLEX 8.0 are also provided, which show that the algorithm provides good solutions

In this paper, we propose a new strategy for the robust constraint resource assignment problem and apply it to solve the robust airport gate assignment (RAGA). RAGA attempts to accurately build an evaluation criteria for the ability of an aircraft-to-gate assignment to handle uncertainty on aircraft schedule; and to accurately and effectively search the most robust airport gate assignment. We model the RAGA by a stochastic programming model and transform it into a binary programming model by introducing the unsupervised estimation functions without knowing any information on the real-time arrival and departure time of aircrafts in advance. Moreover, a partition-based search space encoding, two neighborhood operators for single or multiple aircrafts reassignment, and a hybrid meta-heuristic combining a tabu search and a local search are proposed to solve RAGA efficiently. Experimental results on the real-life test data from Hong Kong International Airport demonstrate that the proposed RAGA model provides a valuable tool for the airport to improve its robustness in uncertain operations

In this paper, we have solved the resequencing and feature assignment problem (RFAP) by an iterative search scheme, which can obtain optimum solutions for instances sized as large as that in reality. The search scheme is based on a beam search heuristic, which outperform other heuristics in previous literature. The algorithms proposed can therefore be utilized to improve the vehicle manufacturing and to benchmark the optimum or near-optimum solutions for future research

This paper introduces multi-depot vehicle routing problem with fixed distribution of vehicles (MDVRPFD) which is one important and useful variant of the traditional multi-depot vehicle routing problem (MDVRP) in the supply chain management and transportation studies. After modeling the MDVRPFD as a binary programming problem, we propose two solution methodologies: two-stage and one-stage approaches. The two-stage approach decomposes the MDVRPFD into two independent subproblems, assignment and routing, and solves them separately. In contrast, the one-stage approach integrates the assignment with the routing where there are two kinds of routing methods-draft routing and detail routing. Experimental results show that our new one-stage algorithm outperforms the published methods. Note to Practitioners-This work is based on several consultancy work that we have done for transportation companies in Hong Kong. The multi-depot vehicle routing problem (MDVRP) is one of the core optimization problems in transportation, logistics, and supply chain management, which minimizes the total travel distance (the major factor of total transportation cost) among a number of given depots. However, in real practice, the MDVRP is not reliable because of the assumption that there have unlimited number of vehicles available in each depot. In this paper, we propose a new useful variant of the MDVRP, namely multi-depot vehicle routing problem with fixed distribution of vehicles (MDVRPFD), to model the practicable cases in applications. Two-stage and one-stage solution algorithms are also proposed. The industry participators can apply our new one-stage algorithm to solve the MDVRPFD directly and efficiently. Moreover, our one-stage solution framework allows users to smoothly add new specified constraints or variants.

We propose a new approach to solve combinatorial optimization problems. Our approach is simple to implement but powerful in terms of performance and speed. We combine the strengths of a meta-heuristic approach with the integer programming method by partitioning the problem into two interrelated subproblems, where the higher level problem is solved by the metahueristic and the lower level problem is solved by integer programming. We discuss the selection of key variables to facilitate an effective partitioning, and test our approach on two real world crossdocking problems, which is very popular in this part of the world. Our experimental results indicate that our new approach is very promising.

In This work, the robust graph coloring problem (RGCP), an extension of the classical graph coloring, is solved by various meta-heuristics. After discussing the search space encoding and neighborhood structure, several meta-heuristics including genetic algorithm, simulated annealing and tabu search are developed to solve RGCP. The experimental results on various sizes of input graph provide the performance of these meta-heuristics in terms of accuracy and run time.

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.

The port yard storage optimization problem (PYSOP) originates from space allocation needs at the Port of Singapore. Space allocated to cargo is to be minimized in a designated yard within a time interval. The problem is akin to a packing problem in space and time, but where shapes packed and constraints are particular to port operations. Further, space requests can change within the time interval in which it is requested. This basic problem is generic to port operations and may find applications elsewhere. The PYSOP is NP-hard, but we propose a number of metaheuristics. Extensive experiments were conducted and good results obtained.Note to Practitioners-The Port of Singapore is one of the busiest ports in the world where competing pressures for land use and competition from other regional and international ports force port planners to make best use of available land. Factors that impact storage capacity include stacking heights, net storage area available, storage density (containers per acre), dwell times for empty containers and breakbulk cargo. In studying its operations to find better ways to utilize storage space within the dynamic environment of the port, we narrowed storage problems down and focused on the central allocation process in storage-operations improvement which would allow for better utilization of space. In this process, requests are made from an operations unit which coordinates ship berthing and ship-to-apron loading as well as apron-to-yard transportation. Each request is for a set of spaces within a yard required in a single time interval. If any space is allocated to the request, this space cannot be freed (released) until the request is completed, that is, until the end time point of the time interval. The problem is akin to a packing problem in space and time, but where shapes packed and constraints are particular to port operations. Further, space requests can change within the time interval in which it is requested. This basic problem is generic to port operations and may find applications elsewhere. The PYSOP is NP-hard for which we propose a number of metaheuristics. Extensive experiments were conducted and good results obtained.

Here, we are motivated by the problem of finding the shortest path in a network when traversing Web pages where cache size determines path length. The shortest path problem with cache-dependent path lengths is shown to be NP-complete. It is a new problem for which we propose several effective heuristics, including a Dijkstra heuristic, genetic algorithms and tabu search.

Three-index assignment problem (AP3) is well-known problem which has been shown to be NP-hard. This problem has been studied extensively, and many exact and heuristic methods have been proposed to solve it. Inspired by the classical assignment problem, we propose a new iterative heuristic, called fragmental optimization (FO), which solves the problem by simplifying it to the assignment problem. We further hybridize our heuristic with the genetic algorithm (GA). Extensive experimental results indicate that our hybrid method to be superior to all previous heuristic methods including those proposed by Balas and Saltzman(1991), Crama and Spieksma(1992), Burkard et al(1996), and Aiex et al(2003).

In this paper, we present a machine scheduling problem with resource constraints which is popular in manufacturing engineering. A genetic algorithm based approach is put forward and illustrated, including a special encoding and two kinds of decoding greedy schemes. Compared with both several kinds of lower bounds we present in the paper and the results from ILOG OPL software package, it is shown that our rapid genetic algorithm achieved significant results with stable and near-optimal performance.

In this paper, we propose an integrated genetic algorithm with hill climbing to solve the matrix bandwidth minimization problem, which is to reduce bandwidth by permuting rows and columns resulting in the nonzero elements residing in a band as close as possible to the diagonal. Many algorithms for this problem have been developed, including the well-known CM and GPS algorithms. Recently, Marti et al., (2001) used tabu search and Pinana et al. (2002) used GRASP with path relinking, separately, where both approaches outperformed the GPS algorithm. In this work, our approach is to exploit the genetic algorithm technique in global search while using hill climbing for local search. Experiments show that this approach achieves the best solution quality when compared with the GPS algorithm, tabu search, and the GRASP with path relinking methods, while being faster than the latter two newly-developed heuristics.

This paper extends carrier assignment models used in bid analysis for transportation procurement to incorporate shipper business considerations. These include restricting carrier numbers, favoring incumbents and performance considerations. We provide representative models and develop solutions for these which include the use of metaheuristics. Experimentation shows that our algorithms work well.

The 2-machine bicriteria flowshop scheduling problem F2/spl par/(/spl Sigma/C/sub i//C/sub max/) is studied in this paper, which minimizes the total flow time subject to the makespan of the schedule being minimum. This problem is known to be strongly NP-hard, and several heuristic algorithms have been proposed to solve it. In this paper, we present a new approach, which we named fragmental optimization (FO), that combines the dynamic programming and local search strategies. Extensive experimentation shows that our FO algorithm outperforms existing heuristics and provides solutions that are very close to the optimal.

In contrast to the existing airport gate assignment studies where flight have fixed schedules, we consider the more realistic situation where flight arrival and departure times can change. Our objectives are achieved through gate assignments where time slots alloted to aircraft at gates deviate from scheduled slots minimally. The solution approach uses insert and interval exchange moves together with a time shift algorithm. We then use these neighborhood moves in tabu search and memetic algorithms. Computational results are provided and verify that our heuristics work well in small cases and much better in large cases when compared with CPLEX solver.

To facilitate queries over semi-structured data, various structural summaries have been proposed. Structural summaries are derived directly from the data and serve as indices for evaluating path expressions on semi-structured or XML data. We introduce the D(k) index, an adaptive structural summary for general graph structured documents. Building on previous work, 1-index and A(k) index, the D(k)-index is also based on the concept of bisimilarity. However, as a generalization of the 1-index and A(k)-index, the D(k) index possesses the adaptive ability to adjust its structure according to the current query load. This dynamism also facilitates efficient update algorithms, which are crucial to practical applications of structural indices, but have not been adequately addressed in previous index proposals. Our experiments show that the D(k) index is a more effective structural summary than previous static ones, as a result of its query load sensitivity. In addition, update operations on the D(k) index can be performed more efficiently than on its predecessors.

We examine crane scheduling for ports. This important component of port operations management is studied when certain spatial constraints, which are common to crane operations, are considered. Although there has been some work on crane scheduling, such spatial constraints have not been previously developed. We assume that ships can be divided into holds and that cranes can move from hold to hold but that only one crane can work on one hold or job at any one time. The objective is to find a crane-to-job matching which will maximize throughput for such operations under these basic spatial constraints. We propose two dynamic programming algorithms, prove NP-completeness of the problem and provide heuristics to solve the crane scheduling problem with spatial constraints. We develop probabilistic tabu search techniques for application to the problem which are easy to implement. In experiments, we compare the performance of tabu search with other algorithms applied to the crane scheduling problem.

In this paper, we study shelf space allocation optimization which is important to retail operations management. Our approach is to formulate a model that is applicable to operational realities and to seek solutions with realistic test data. This model is linked to the multidimensional knapsack problem. We first solve a simplified version of the problem to achieve maximum profit by transforming it into a network flow problem. Then, with simple adaptations we solve the general shelf space allocation problem with the help of the network flow model. The approach is simple and direct while experimental results improve on recent findings significantly and are very close to the optimal.

One of the desirable attributes of real-life examination timetabling solutions is the maximization of paper spread, which is a measure of the amount of study time that each student has between examinations. We make use of the push-forward insertion heuristic (PFIH), a technique commonly employed in the vehicle routing problem, to find timetable solutions that maximize paper spread. This is done by including PFIH as part of a hybrid exam-timetablmg framework known as the Combined Method.

In this paper, we propose a metaheuristic to solve the pickup and delivery problem with time windows. Our approach is a tabu-embedded simulated annealing algorithm which restarts a search procedure from the current best solution after several non-improving search iterations. The computational experiments on the six newly-generated different data sets marked our algorithm as the first approach to solve large multiple-vehicle PDPTW problem instances with various distribution properties.

The minimum area joining of k compacted cells problem is an open problem that is not known whether to be polynomial-time solvable or NP-hard. In this paper we derive a divide-and-conquer approach for determining a lower-bound on the optimal cost of large problems. We also devise a taboo search algorithm whose performance can be measured and evaluated for large cases by using the derived lower bounds. Experimental results suggest that the algorithm performs reasonably well.

As part of the process of creating a campus-wide timetabling system for the National University of Singapore, the authors investigated examination-scheduling algorithms. The challenge in exam scheduling is to draw up the final examination timetable, taking into account a number of different constraints. The authors propose a different approach when the interexamination gaps (termed paper spread) of each student should be maximized. The results compare favorably against the actual timetable produced by the current manual system.

The Ship Berthing Problem (SBP) belongs to the category of NP-complete problems. In this paper we discuss the methods of representing the SBP with the use of a directed acyclic graph and the use of a acyclic list to represent valid solutions for the SBP. We then propose and investigate the performance of several variants of the randomized local search, Tabu search and genetic algorithm for solving the SBP.

It is observed that a better approach to Web information understanding is to base on its document framework, which is mainly consisted of (i) the title and the URL name of the page, (ii) the titles and the URL names of the Web pages that it points to, (iii) the alternative information source for the embedded Web objects, and (iv) its linkage to other Web pages of the same document. Investigation reveals that a high percentage of words inside the document framework are “compound words” which cannot be understood by ordinary dictionaries. They might be abbreviations or acronyms, or concatenations of several (partial) words. To recover the content hierarchy of Web documents, we propose a new word segmentation and recognition mechanism to understand the information derived from the Web document framework. A maximal bi-directional matching algorithm with heuristic rules is used to resolve ambiguous segmentation and meaning in compound words. An adaptive training process is further employed to build a dictionary of recognisable abbreviations and acronyms. Empirical results show that over 75% of the compound words found in the Web document framework can be understood by our mechanism. With the training process, the success rate of recognising compound words can be increased to about 90%.

The join relational operation is one of the most expensive among database operations. In this study, we consider the problem of scheduling page accesses in join processing. This raises two interesting problems: 1) determining a page access sequence that uses the minimum number of buffer pages without any page reaccesses, and 2) determining a page access sequence that minimizes the number of page reaccesses for a given buffer size. We use a graph model to represent the pages from the relations that contain tuples to be joined, and present new heuristics for the two problems based on the sort-merge join and the simple TID algorithm. Our experimental results show that the new heuristics perform well.

This paper focuses on the study of a hybrid of two search heuristics, tabu search (TS) and genetic algorithms (GA) in the vehicle routing problem with time-windows (VRPTW). TS is a local search technique that has been successfully applied to many NP-complete problems. On the other hand, a GA which is capable of searching multiple search areas in a search space is good for diversification. We investigate whether a hybrid of the two heuristics outperforms the individual heuristics.

We develop a simple linear time algorithm to determine if a collection of two-pin nets can be routed, topologically, in a plane (i.e., single layer). Experiments indicate that this algorithm is faster than the linear time algorithm of Marek-Sadowska and Tarng. Topological routability testing of a collection of multipin nets is shown to be equivalent to planarity testing, and a simple linear time algorithm is developed for the case when the collection of modules remains connected following the deletion of all nets with more than two pins.

Traditionally, design for assembly is done during the detailed design phase. A designer first maps a set of design requirements into a set of components or subassemblies that can satisfy the given set of requirements. The components and subassemblies are then examined individually to determine whether they conform to the principles of design for assembly. Usually, local changes are performed so that the resultant components/subassemblies are better for assembly. In this paper, we propose to bring the design for assembly analysis into an even earlier phase-that of the conceptual design phase. We argue that by incorporating the design for assembly analysis at the conceptual design phase, we can achieve a more substantial savings as compared to the savings obtained when the design for assembly analysis is only performed as late as the detailed design phase. The basic idea is to select a combination of design concepts (previously stored in a library) such that together they can achieve the stated functional requirements (in the form of state transitional graph) at the minimum cost for assembly. This problem of selecting the right combination of design concepts is reduced to the well-known set covering problem. With this reduction, many existing graph algorithms can be applied to aid in the design for assembly analysis.

In this paper, we consider the problem of determining the smallest clock period for a combinational circuit. By considering both the long and short paths, we derive three independent bounds on the clock period. The first bound is the difference between the longest path delay and the shortest path delay. The other two take the functionality of the circuit into consideration and, therefore, are usually smaller than the first one. To bring in the functionality of the circuit, we make use of a new class of paths-called the shortest destabilizing paths-as well as the longest sensitizable paths. We also show that considering both the longest sensitizable path and the shortest destabilizing path together does not always give a valid bound. The bounds on the clock period can be alternatively viewed as optimization objectives. At the physical level, the complexity of optimization very much depends on the number of long and short paths present and the number of gates shared by them. We conducted preliminary experiments to study this.>

We formulate the performance oriented minimum rectilinear Steiner tree problem (POMRST) which is useful in the case of net connection high performance circuits. Since the POMRST problem is NP-hard, we provide an effective heuristic for it. When we apply our POMRST heuristic to solve the rectilinear Steiner tree problem, our experimental results compare favorably with the existing techniques cited in [11]. In the context of the POMRST problem, our experimental results indicate that a small increase in the total interconnection length can greatly enhance the circuit performance. A related but less general problem has been addressed in [1].

Three algorithms to join two compacted cells by using a combination of stretching and river routing are developed. Each of these obtains the minimum area joining. One algorithm obtains a minimum area joining that also minimizes the length of the longest wire. Another obtains a minimum area joining that has the least possible total wire length. The simplest of the algorithms guarantees only a minimum are joining. All algorithms have a low-order polynomial complexity. Experimental results indicate that the algorithms obtain joinings that are significantly superior to those obtained using the heuristic of G. Cheng and A. Despain (1989).>

The authors consider the problem of selecting an implementation of each circuit module from a cell library so as to satisfy overall delay and area (or delay and power) requirements. Two versions of the circuit implementation problem, the basic circuit implementation problem and the general circuit implementation problem, are shown to be NP-hard. A pseudo-polynomial-time algorithm for the basic circuits is developed, and heuristics for the basic circuit implementation problem on general circuits are formulated and experimented with.>

The authors present an effective performance driven placement with global routing algorithm for macro cells. Their algorithm is a hierarchical, divide and conquer, quad-partitioning approach. The quad-partitioning routine uses the Tabu search technique. Their algorithm uses the concept of proximity of regions to approximate the interconnection delays during the placement process. In addition, their algorithm can handle modules whose positions are fixed or are restricted to a particular subregion on the layout frame. The experimental results indicate the superiority of their placement in terms of quality of solutions and run times when compared to those by I. Lin and D. Du (1990).>

The authors formulate and classify the various models of the wafer packing problem for the full mask exposure technique. Since the wafer packing problem is NP-hard, the authors propose a good heuristic for it. Their experiments, on real test data, indicate that this heuristic is very effective as it provides considerable cost reduction when compared with the traditional way of producing chips.>