带时效性约束的配送中心多源选址问题研究

应用启发式算法求解带时效性约束的多源选址问题.分析物流配送的时效性问题,建立带时效性约束的配送中心多源选址模型.构造两步启发式算法:1)借助传统迭代算法,求解物流服务分配矩阵,把多源选址问题转化为单源选址问题;2)基于M ATLAB函数,设计优化程序,计算带时效性约束的单源选址模型.并给出算例,验证模型和算法的可行性.研究表明两步启发式算法是求解带时效性约束的物流配送中心多源连续选址问题的有效算法.     

Variable neighborhood search for the vertex weighted k-cardinality tree problem

This paper presents some new heuristics based on variable neighborhood search to solve the vertex weighted k-cardinality tree problem. An efficient local search procedure is also developed for use within these heuristics. Our computational results demonstrate that the new heuristics substantially outperform the state-of-the-art methodologies, including a tabu search and genetic algorithm recently proposed in the literature. We also show that a decomposition approach is best for larger problem sizes than previously investigated. Thus, our findings advance in a significant way the capacity to solve this important class of problems.     

A heuristic lagrangean algorithm for the capacitated plant location problem

Lagrangean techniques have been widely applied to the uncapacitated plant location problem, and in some cases they have proven to be successfull even when capacitated problems with additional constraints are taken into account. In our paper we study the application of these techniques to the capacitated plant location problem when the model considered is a pure integer one. Several lagrangean decompositions are considered and for some of them heuristic algorithms have been designed to solve the resulting lagrangean subproblems, the heuristics consisting of a two phase procedure. The first (location phase) defines a set of multipliers from the analysis of the dual LP relaxation, and makes a choice of the plants considering the resulting subproblems as a particular case of the general assignment problems. Several heuristics have been studied for this second phase, based either on a decomposition of knapsack type subproblems through a definition of a set of penalties, or of looking into the duality gap and trying to reduce it. Computational experience is reported.     

A metaheuristic approach to solving a multiproduct EOQ-based inventory problem with storage space constraints

This paper considers the well-known static time-continuous multiproduct economic order quantity (EOQ) based inventory management problem with the storage space constraints. This problem is modelled as a combinatorial optimization problem in the corresponding dynamic discrete time system control process. In order to solve this problem approximately, we developed two heuristics: a special heuristic based on a local search technique and a metaheuristic procedure based on the variable neighbourhood search principle. The efficiency of two heuristics is preliminary examined and compared on several randomly generated instances with the same number of products.     

A guided local search metaheuristic for the team orienteering problem

In the team orienteering problem (TOP) a set of locations is given, each with a score. The goal is to determine a fixed number of routes, limited in length, that visit some locations and maximise the sum of the collected scores. This paper describes an algorithm that combines different local search heuristics to solve the TOP. Guided local search (GLS) is used to improve two of the proposed heuristics. An extra heuristic is added to regularly diversify the search in order to explore more areas of the solution space. The algorithm is compared with the best known heuristics of the literature and applied on a large problem set. The obtained results are almost of the same quality as the results of these heuristics but the computational time is reduced significantly. Applying GLS to solve the TOP appears to be a very promising technique. Furthermore, the usefulness of exploring more areas of the solution space is clearly demonstrated.     

The effect of material flow and workload on the performance of machine location heuristics

Depending on the problem structure and routing strategies a machine location problem plays an important role in controlling the material flow of work-in-process in discrete product manufacturing environment. In this paper we investigate the effect of material flow and workload on the performance of heuristics for solving an important design problem for job routing and material flow in a manufacturing system. In this research we first develop a model for workload or traffic intensity between machines in a shop floor and then identify different structures of the problems, especially the data. This measure is then used to evaluate the effect of workload on efficiency of the heuristics to solve machine location problems. Some concluding remarks are made on to the effect of the workload or the traffic intensity of materials within the machine cell on the performance of some known heuristics. Conclusions are also made on the performance measures such as makespan, transporter utilization and machine utilization, depending on the problem and data structures.     

New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs

We consider the bicriteria scheduling problem of minimizing the number of tardy jobs and average flowtime on a single machine. This problem, which is known to be NP-hard, is important in practice, as the former criterion conveys the customer’s position, and the latter reflects the manufacturer’s perspective in the supply chain. We propose four new heuristics to solve this multiobjective scheduling problem. Two of these heuristics are constructive algorithms based on beam search methodology. The other two are metaheuristic approaches using a genetic algorithm and tabu-search. Our computational experiments indicate that the proposed beam search heuristics find efficient schedules optimally in most cases and perform better than the existing heuristics in the literature.     

Complete Local Search with Memory

Neighborhood search heuristics like local search and its variants are some of the most popular approaches to solve discrete optimization problems of moderate to large size. Apart from tabu search, most of these heuristics are memoryless. In this paper we introduce a new neighborhood search heuristic that makes effective use of memory structures in a way that is different from that in common implementations of tabu search. We report computational experiments with this heuristic on the traveling salesperson problem and the subset sum problem.     

A variable neighborhood search for the network design problem with relays

Given a set of commodities to be routed over a network, the network design problem with relays involves selecting a route for each commodity and determining the location of relays where the commodities must be reprocessed at certain distance intervals. We propose a hybrid approach based on variable neighborhood search. The variable neighborhood algorithm searches for the route for each commodity and the optimal relay locations for a given set of routes are determined by an implicit enumeration algorithm. We show that dynamic programming can be used to determine the optimal relay locations for a single commodity. Dynamic programming is embedded into the implicit enumeration algorithm to solve the relay location problem optimally for multiple commodities. The special structure of the problem is leveraged for computational efficiency. In the variable neighborhood search algorithm, the routes of the current solution are perturbed and reconstructed to generate neighbor solutions using random and greedy construction heuristics. Computational experiments on three sets of problems (80 instances) show that the variable neighborhood search algorithm with optimal relay allocations outperforms all existing algorithms in the literature.     

Lagrangian heuristics for the two-echelon,single-source,capacitated facility location problem

Facility location problems form an important class of integer programming problems, with application in the distribution and transportation industries. In this paper we are concerned with a particular type of facility location problem in which there exist two echelons of facilities. Each facility in the second echelon has limited capacity and can be supplied by only one facility (or depot) in the first echelon. Each customer is serviced by only one facility in the second echelon. The number and location of facilities in both echelons together with the allocation of customers to the second-echelon facilities are to be determined simultaneously. We propose a mathematical model for this problem and consider six heuristics based on Lagrangian relaxation for its solution. To solve the dual problem we make use of a subgradient optimization procedure. We present numerical results for a large suite of test problems. These indicate that the lower-bounds obtained from some relaxations have a duality gap which frequently is one third of the one obtained from traditional linear programming relaxation. Furthermore, the overall solution time for the heuristics are less than the time to solve the LP relaxation.     

Heuristics for the dynamic facility layout problem with unequal-area departments

The dynamic facility layout problem (DFLP) is the problem of finding positions of departments on the plant floor for multiple periods (material flows between departments change during the planning horizon) such that departments do not overlap, and the sum of the material handling and rearrangement costs is minimized. In this paper, the departments may have unequal-areas and free orientations, and the layout for each period is generated on the continuous plant floor. Because of the complexity of the problem, only small-size problems can be solved in reasonable time using exact techniques. As a result, a boundary search (construction) technique, which places departments along the boundaries of already placed departments, is developed for the DFLP. The solution is improved using a tabu search heuristic. The heuristics were tested on some instances from the DFLP and static facility layout problem (SFLP) literature. The results obtained demonstrate the effectiveness of the heuristics.     

Categorized Assignment Scheduling: a Tabu Search Approach

The assignment problem (AP) and bottleneck assignment problem (BAP) are well studied in operational research literature. In this paper we consider two related problems which simultaneously generalize both AP and BAP. Unlike AP and BAP, these generalizations are strongly NP-complete. We propose two heuristics to solve these generalized problems: one based on a greedy principle and the other based on tabu search. Computational results are presented which show that these heuristics, when used together, produce good quality solutions. Our adaptation of tabu search also gives some new insight into the application of tabu search on permutation problems.     

Heuristics for the capacitated plant location model

The paper generalizes heuristics for the uncapacitated plant location model to the capacitated case. The heuristics are ADD, DROP, SHIFT, ALA (Alternate Location Allocation) and VSM (Vertex Substitution Method). The generalizations take place within an unifying framework based on elementary ADD and DROP operations.Heuristics from the literature are discussed and compared to the procedures developed in this paper.     

考虑共享不确定因素的应急设施最大覆盖选址模型

为提升应急设施的服务质量和抵御中断风险的能力,研究应急设施最大覆盖选址-分配决策问题。扩展无容量限制的固定费用的可靠性选址决策模型,建立考虑共享不确定因素的应急设施最大覆盖选址优化模型,通过在目标和约束中引入budget不确定集刻画共享不确定因素,基于Bertsimas和Sim鲁棒优化方法建立混合整数规划模型,并将非线性问题转化为易于求解的鲁棒等价模型,利用带混沌搜索策略的改进灰狼优化算法求解模型,并对不确定鲁棒水平和中断概率进行敏感性分析。最后通过案例及数据仿真结果的对比分析,验证了模型的合理性和有效性,并给出最优的选址分配布局。     

带投资约束且p不确定的推广p-中位问题

p-中位问题是设施选址中的一个经典模型,在交通、物流等领域有着广泛应用．在经典p-中位问题的基础上提出一种p不确定的推广p-中位问题,并且加上总投资约束,使得此推广模型更加实用．针对此推广模型,提出三种启发式算法：简单启发式算法、变邻域搜索算法和改进的遗传算法．数值实验结果表明变邻域搜索算法和改进的遗传算法在求解此推广模型时是有效的．     

Reducing work-in-process movement for multiple products in one-dimensional layout problems

This research describes a method to assign M machines, which are served by a material handling transporter, to M equidistant locations along a track, so that the distance traveled by a given set of jobs is minimized. Traditionally, this problem (commonly known as a machine location problem) has been modeled as a quadratic assignment problem (QAP), which is NP-hard, thus motivating the need for efficient procedures to solve instances with several machines. In this paper we develop a branching heuristic to obtain sub-optimum solutions to the problem; a lower bound on the optimum solution has also been presented. Results obtained from the heuristics are compared with results obtained from other heuristics with similar objectives. It is observed that the results are promising, and justify the usage of developed methods.     

大洪水算法在平面选址问题中的应用

大洪水算法是通过模拟洪水上涨过程来进行全局寻优的启发式算法.针对连续优化问题,基于三种不同的邻域搜索策略对其进行改进,并针对一类平面选址问题进行应用测试.仿真结果表明,大洪水算法是一类简单高效的算法,可用于连续优化问题的求解.     

Heuristics for the fixed cost median problem

We describe in this paper polynomial heuristics for three important hard problems—the discrete fixed cost median problem (the plant location problem), the continuous fixed cost median problem in a Euclidean space, and the network fixed cost median problem with convex costs. The heuristics for all the three problems guarantee error ratios no worse than the logarithm of the number of customer points. The derivation of the heuristics is based on the presentation of all types of median problems discussed as a set covering problem.     

Optimal sequencing of skip collections and deliveries

The purpose of this paper is to model and solve a complex routing problem associated with the collection and delivery of skips. This study is motivated by a real-life problem encountered by a skip rental firm in Belgium. Two simple heuristics as well as an exact enumerative algorithm are developed for the problem. Computational experiments carried out on both randomly generated and real-life data confirm the efficiency of the proposed approach.     

A scatter search algorithm for the single row facility layout problem

The single row facility layout problem (SRFLP) is the problem of arranging facilities with given lengths on a line, with the objective of minimizing the weighted sum of the distances between all pairs of facilities. The problem is NP-hard and research has focused on heuristics to solve large instances of the problem. In this paper we present a scatter search algorithm to solve large size SRFLP instances. Our computational experiments show that the scatter search algorithm is an algorithm of choice when solving large size SRFLP instances within limited time.