The Traveling Purchaser Problem with time-dependent quantities

The deterministic Traveling Purchaser Problem looks for a tour visiting a subset of markets in order to satisfy a positive discrete demand for some products at minimum traveling and purchasing costs. In this paper, we assume that the quantities available in the markets for all the products are time-varying decreasing at a constant rate. We propose a compact mixed integer formulation for the problem, and strengthen it with the introduction of connectivity constraints. A new branching strategy and a primal heuristic enforcing the bounding operations have been embedded into a branch-and-cut framework. The branching rule exploits a simple valid inequality and the potential presence of necessary markets. The resulting method outperforms CPLEX 12.6 when used to solve the proposed model. The algorithms have been tested on standard TSPLIB instances, modified to include products and quantities that decrease at different rates of consumption.     

The traveling purchaser problem with budget constraint

Let us consider a set of markets plus a depot and a set of products for each of which a positive demand is specified. Each product is made available in a subset of markets in each of which only a given quantity, less than or equal to the required one, can be purchased at a given unit price. The distance between each couple of markets and between each market and the depot is known. The Traveling Purchaser Problem with Budget constraint (TPP-B) looks for a simple cycle starting at and ending to the depot and visiting a subset of markets at a minimum traveling cost and such that the demand for each product is satisfied and the cost globally spent for purchasing the products does not exceed a defined budget threshold. As the TPP also this problem arises in several application domains, but while the former has been largely studied, very few contributions exist in the literature for the TPP-B. We propose and compare two solution algorithms, an enhanced local-search heuristic and a variable neighborhood search (VNS) approach also tested in a multi-start variant. The proposed algorithms have been used to solve both the capacitated and the uncapacitated version of the problem. Test problems have been obtained by adding a budget constraint to known benchmark instances for the TPP.     

Ant colony optimization for the traveling purchaser problem

The traveling purchaser problem (TPP) is a generalization of the traveling salesman problem where markets have to be visited to collect a set of commodities. Each market sells a number of commodities at a known price. The TPP consists in selecting a subset of markets purchasing every product, while minimizing the routing costs and the purchase costs. In this work, we address the solution of the TPP with an ant colony optimization procedure. We combine it with a local-search scheme exploring a new neighborhood structure. This procedure is evaluated on a set of benchmark instances from the literature and permits to improve most of the best-known solutions.     

Optimal decision making in multi-product dual sourcing procurement with demand forecast updating

In this paper, we will investigate a buyer's decision making problem in procuring multiple products, each treated as a newsvendor, from two markets. The contract market has a long lead time, a fixed wholesale price and resource constraints. While the spot market has an instant lead time and a highly volatile price. The purchasing decision at the spot market can be made near the beginning of the selling season to take the advantage of the most recent demand forecast. The buyer needs to determine the purchasing quantity for each product at the two markets to maximize the expected profit by trading off between the resource availability, demand uncertainty and price variability. The procurement decision making is modeled as a bi-level programming problem under both a single resource constraint and under multiple resource constraints. We show that this bi-level programming problem can be formulated as a single-level concave programming problem. We then develop a sequential algorithm which solves for a linear approximation of the concave programming problem in each iteration. This algorithm can be used to solve a real world problem with up to thousands of kinds of products, and is found to be highly efficient and effective.     

Coordination of purchasing and bidding activities across posted offer and auction markets

In both consumer purchasing and industrial procurement, combinatorial interdependencies among the items to be purchased are commonplace. E-commerce compounds the problem by providing more opportunities for switching suppliers at low costs, but also potentially eases the problem by enabling automated market decision-making systems, commonly referred to as trading agents, to make purchasing decisions in an integrated manner across markets. We are investigating a new approach to deal with the combinatorial interdependency challenges for online markets. This approach relies on existing commercial online market institutions such as posted-offer markets and various online auctions that sell single items. It uses trading agents to coordinate a buyer’s purchasing and bidding activities across multiple online markets simultaneously to achieve the best overall procurement effectiveness. This paper presents two sets of models related to this approach. The first set of models formalizes optimal purchasing decisions across posted-offer markets with fixed transaction costs. The second set of models is concerned with the coordination of bidding activities across multiple online auctions.Research reported in this paper was partially supported by a Proposition 301 Electronic Commerce Grant, University of Arizona Eller College of Management. The first author is also affiliated with The Key Lab of Complex Systems and Intelligence Science, Chinese Academy of Sciences (CAS), Beijing, and was supported in part by a grant for open research projects (ORP-0303) from CAS. Earlier versions of this paper have appeared in the Proceedings of the Hawai’i International Conference on System Sciences (HICSS-37) and the Proceedings of the 13th Annual Workshop on Information Technology and Systems (WITS ’03).     

A hybrid Lagrangean heuristic with GRASP and path-relinking for set k-covering

The set multicovering or set k-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least k times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set k-covering problem, as well as the template of a family of Lagrangean heuristics. The hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking heuristic using modified costs to obtain approximate solutions for the original problem. Computational experiments carried out on 135 test instances show experimentally that the Lagrangean heuristics performed consistently better than GRASP as well as GRASP with path-relinking. By properly tuning the parameters of the GRASP Lagrangean heuristic, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, the GRASP Lagrangean heuristic makes better use of the dual information provided by subgradient optimization and is able to discover better solutions and to escape from locally optimal solutions even after the stabilization of the lower bounds, when other Lagrangean strategies fail to find new improving solutions.     

Mathematical programming-based approaches for multi-facility glass container production planning

This paper introduces a mathematical model (together with a relaxed version) and solution approaches for the multi-facility glass container production planning (MF-GCPP) problem. The glass container industry covers the production of glass packaging (bottle and jars), where a glass paste is continuously distributed to a set of parallel molding machines that shape the finished products. Each facility has a set of furnaces where the glass paste is produced in order to meet the demand. Furthermore, final product transfers between facilities are allowed to face demand. The objectives include meeting demand, minimizing inventory investment and transportation costs, as well as maximizing the utilization of the production facilities. A novel mixed integer programming formulation is introduced for MF-GCPP and solution approaches applying heuristics and meta-heuristics based on mathematical programming are developed. A multi-population genetic algorithm defines for each individual the partitions of the search space to be optimized by the MIP solver. A variant of the fix-and-optimize improvement heuristic is also introduced. The computational tests are carried on instances generated from real-world data provided by a glass container company. The results show that the proposed methods return competitive results for smaller instances, comparing to an exact solver method. In larger instances, the proposed methods are able to return high quality solutions.     

Randomized heuristics for the family traveling salesperson problem

This paper introduces the family traveling salesperson problem (FTSP), a variant of the generalized traveling salesman problem. In the FTSP, a subset of nodes must be visited for each node cluster in the graph. The objective is to minimize the distance traveled. We describe an integer programming formulation for the FTSP and show that the commercial grade integer programming solver CPLEX 11 can only solve small instances of the problem in reasonable running time. We propose two randomized heuristics for finding optimal and near‐optimal solutions of this problem. These heuristics are a biased random‐key genetic algorithm and a GRASP with evolutionary path‐relinking. Computational results comparing both heuristics are presented in this study.     

Solving a generalized traveling salesperson problem with stochastic customers

In this paper, a probabilistic generalized traveling salesperson problem (PGTSP) is introduced to address several applications. In the PGTSP, each customer belongs to a cluster that consists of a set of customers. Whether or not any given customer will be present during actual operations is known a priori only probabilistically. The PGTSP seeks the minimum expected length tour to visit a subset of all customers such that the tour traverses each cluster at least once. If when implementing the tour it is revealed that there is no demand for service within the cluster to which a customer stop belongs, that stop will be skipped. An exact solution algorithm based on the integer L-shaped method and three tour construction-based heuristics for quickly solving this problem are described in the paper. Computational experiments were conducted to assess computational requirements and solution quality of the proposed solution techniques. These experiments show that the exact method is able to solve small- and moderate-size problems to optimality. In addition, one of the proposed heuristics (the MMI heuristic), in particular, gives good approximate solutions (often a few percent from optimal) in very reasonable computational time.     

Dynamic pricing of durable products with heterogeneous customers and demand interactions over time

In this study, we analyze a dynamic pricing problem in which the demand is interdependent over time and the customers are heterogeneous in their purchasing decisions. The customers are grouped into different classes depending on their purchase probabilities and the customer classes evolve over time depending on the demand realizations at every period, which are a function of the prices set by the company. To decide on the optimal prices at every period, we model this problem using a stochastic dynamic program (SDP) and we develop several approximation algorithms to solve this SDP since the size of the state space of the SDP makes the optimal solution almost impossible to find. We present the efficiencies of the heuristics and provide managerial insights through a computational study in which we compare the revenues obtained with each heuristic with an upper bound value that we find on the optimal revenues.     

Solving the traveling salesman problem with annealing-basedheuristics: a computational study

Recently, several general optimization algorithms based on the demon algorithm from statistical physics have been developed and tested on a few traveling salesman problems with encouraging results. In this paper, we conduct an extensive computational study of 11 annealing-based heuristics for the traveling salesman problem. We code versions of simulated annealing, threshold accepting, record-to-record travel and eight heuristics based on the demon algorithm. We apply each heuristic to 29 traveling salesman problems taken from a well-known online library, compare the results with respect to accuracy and running time and provide insights and suggestions for future work     

Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem

In this paper, we propose to solve the three‐dimensional single bin‐size bin packing problem (3D‐SBSBPP) using a simple strategy based on integer linear programming (ILP) heuristics, without using any improvement based on metaheuristics. We first propose an ILP that is converted into a series of three‐dimensional single knapsack problems (3D‐SKP). Then, the first tailored heuristic can be viewed as a hybrid approach in which both “selection” and “positioning” phases are combined. The first phase serves to select a subset of items where each of these items is susceptible to belonging to an active container. The positioning phase serves to pack a subset of items already preselected by the selection phase. Then, both phases cooperate till packing all items into their corresponding containers. The second heuristic can be viewed as an extended version of the first one. Indeed, before deciding whether the current container is closed or a new container is activated, “a local reoptimization phase” is considered. Finally, both proposed heuristics are evaluated on a set of random instances obtained by using the standard generator scheme of the literature. The provided results show that both proposed heuristics remain competitive when compared to the results obtained by one of the best methods of the literature.     

Modeling and heuristics for scheduling of distributed job shops

This paper deals with the problem of distributed job shop scheduling in which the classical single-facility job shop is extended to the multi-facility one. The mathematical formulation of the problem is comprehensively discussed. Two different mixed integer linear programming models in form of sequence and position based variables are proposed. Using commercial software of CPLEX, the small sized problems are optimally solved. To solve large sized problems, besides adapting three well-known heuristics, three greedy heuristics are developed. The basic idea behind the developed heuristics is to iteratively insert operations (one at each iteration) into a sequence to build up a complete permutation of operations. The permutation scheme, although having several advantages, suffers from redundancy which is having many different permutations representing the same schedule. The issue is analyzed to recognize the redundant permutation. That improves efficiency of heuristics. Comprehensive experiments are conducted to evaluate the performance of the two models and the six heuristics. The results show sequence based model and greedy heuristics equipped with redundancy exclusion are effective for the problem.     

Board-level partitioning for partial scan using fuzzy logic

We present a board-level partitioning scheme for improved partial scan on the resulting integrated circuits (IC). Fuzzy logic rules and two adaptation techniques allow us to simultaneously minimize four important independent objective functions in the examined problem formulation. The maximum among all sets in the partition are the following quantities: 1) number of scanned nodes in a set; 2) number of incident nets to a set; 3) number of inputs to any set; and finally 4) the period of the global clock. The sets must satisfy upper and lower capacity bounds. We experimented with some ISCAS'89 benchmark circuits and we compared the performance of our tool with four iterative improvement heuristics, each considering only one of the four different functions. Our experimental results indicate that the performance of the proposed tool is very effective     

有向黑白旅行商问题

黑白旅行商问题是经典旅行商问题的推广,在基于SONET技术的光纤网络设计、航线调度等领域具有广泛的应用.已有研究工作集中在无向黑白旅行商问题上.文章研究该问题的更一般形式--有向黑白旅行商问题.首先,给出了有向黑白旅行商问题的混合整数线性规划公式.与目前无向黑白旅行商问题包含指数多个约束的规划公式相比,它仅包含多项式个约束.其次,给出了一种启发式算法.实验表明,该启发式算法能够有效地求解黑白旅行商问题的实例.由于无向黑白旅行商问题是有向黑白旅行商问题的特例,故文中的结论对于求解无向黑白旅行商问题同样有效.     

Single-vendor single-buyer with integrated transport-inventory system: Models and heuristics in the case of perishable goods

We consider the problem of shipping a set of products from a single origin (the vendor) to a common destination (the buyer) with the objective of minimizing the sum of the inventory and transportation costs, when a set of shipping frequencies is given and products are assumed to be perishable. We provide a mixed integer linear programming model for the problem and propose the modification of known heuristic algorithms to solve it. Extensive computational results show how some of the modified heuristics are extremely efficient and effective.     

Hybrid heuristics based on column generation with path-relinking for clustering problems

This paper examines hybrid heuristics for solving clustering problems. The clustering problem can be defined as the process of separating a set of objects into groups such that members of a group are similar to each other. The methods are based on the application of a column generation technique for solving p-medians problems. Five heuristics are derived directly from the column generation algorithm: a solution made feasible from the master problem, the column generation solution, a heuristic with path-relinking considering the initial columns of the column generation procedure, a solution of the master problem with path-relinking and the column generation process with path-relinking. Solutions are tested with the external measure CRand and the computational results compared to recent methods in literature.     

Cost-benefit analysis of an SLA mapping approach for defining standardized Cloud computing goods

Due to the large variety in computing resources and, consequently, the large number of different types of service level agreements (SLAs), computing resource markets face the problem of a low market liquidity. Restricting the number of different resource types to a small set of standardized computing resources seems to be the appropriate solution to counteract this problem. Standardized computing resources are defined through an SLA template. An SLA template defines the structure of an SLA, the service attributes, the names of the service attributes, and the service attribute values. However, since existing research results have only introduced static SLA templates so far, the SLA templates cannot reflect changes in user needs and market structures. To address this shortcoming, we present a novel approach of adaptive SLA matching. This approach adapts SLA templates based on SLA mappings of users. It allows Cloud users to define mappings between a public SLA template, which is available in the Cloud market, and their private SLA templates, which are used for various in-house business processes of the Cloud user. Besides showing how public SLA templates are adapted to the demand of Cloud users, we also analyze the costs and benefits of this approach. Costs are incurred every time a user has to define a new SLA mapping to a public SLA template due to its adaptation. In particular, we investigate how the costs differ with respect to the public SLA template adaptation method. The simulation results show that the use of heuristics within adaptation methods allows balancing the costs and benefits of the SLA mapping approach.     

课程表问题的一种模拟退火超启发式算法

课程表问题是经典的组合优化问题,属于NP-hard问题.长期以来人们一直都在寻求快速高效的近似算法,以便在合理的计算时间内准确解决大规模课程安排问题,并提出许多有效且实用的启发式和元启发式算法.在此基础上提出了一种基于多个图染色启发式规则的模拟退火超启发式算法.在超启发式算法的框架中,用模拟退火算法作为高层搜索算法,多个图染色启发式规则为底层的构造算法.与现有的方法相比,该算法具有很好的通用性,可以很容易推广到考试时间表、会议安排.旅行商问题、背包问题等应用领域.实验表明,该算法是可行有效的,且无一例时间、空间冲突.     

Heuristic expansion of feature mappings in evolving program families

Establishing explicit mappings between features and their implementation elements in code is one of the critical factors to maintain and evolve software systems successfully. This is especially important when developers have to evolve program families, which have evolved from one single core system to similar but different systems to accommodate various requirements from customers. Many techniques and tools have emerged to assist developers in the feature mapping activity. However, existing techniques and tools for feature mapping are limited as they operate on a single program version individually. Additionally, existing approaches are limited to recover features on demand, that is, developers have to run the tools for each family member version individually. In this paper, we propose a cohesive suite of five mapping heuristics addressing those two limitations. These heuristics explore the evolution history of the family members in order to expand feature mappings in evolving program families. The expansion refers to the action of automatically generating the feature mappings for each family member version by systematically considering its previous change history. The mapping expansion starts from seed mappings and continually tracks the features of the program family, thus eliminating the need of on demand algorithms. Additionally, we present the MapHist tool that provides support to the application of the proposed heuristics. We evaluate the accuracy of our heuristics through two evolving program families from our industrial partners. Copyright © 2013 John Wiley & Sons, Ltd.