An efficient tabu search procedure for the p-Median Problem

In this paper we present a new solution heuristic for the p-Median Problem. The algorithm is based on tabu search principles, and uses short term and long term memory, as well as strategic oscillation and random tabu list sizes. Our proposed procedure is compared with two other move heuristics: a well-known interchange heuristic and a recent hybrid heuristic. In computational tests on networks ranging in size up to 500 nodes the new heuristic is found to be superior with respect to the quality of solutions produced.     

Locating flow-capturing units on a network with multi-counting and diminishing returns to scale

In the paper we consider the problem of locating flow-capturing units (facilities) on a transportation network, where the level of consuming service by customers depends on the number of facilities that they encounter on their pre-planned tour (the effect of multi-counting). Two location problems are considered: Problem 1 — minimizing the number of facilities required to ensure the maximal level of consumption, and Problem 2 — maximizing the total consumption given a restriction on the number of facilities. Both problems are NP-hard on general networks. Integer programming formulations of the problems are given. For Problem 2, a heuristic with worst-case analysis is presented. It is shown that Problem 2 is NP-hard even on a tree (and even without multi-counting). For Problem 1 on a tree a polynomial algorithm is presented. If it is required additionally that at most one facility can be located at each node and locations are restricted to nodes, then both problems are NP-hard on trees.     

Algorithms for large scale Shift Minimisation Personnel Task Scheduling Problems

In this paper we introduce the Personnel Task Scheduling Problem (PTSP) and provide solution algorithms for a variant of this problem known as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). The PTSP is a problem in which a set of tasks with fixed start and finish times have to be allocated to a heterogenous workforce. Personnel work in shifts with fixed start and end times and have skills that enable them to perform some, but not all tasks. In other words, some personnel are qualified to only perform a subset of all tasks. The objective is to minimise the overall cost of personnel required to perform the given set of tasks. In this paper we introduce a special case in which the only cost incurred is due to the number of personnel (shifts) that are used. This variant of the PTSP is referred to as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). While our motivation is a real-life Personnel Task Scheduling Problem, the formulation may also be applied to machine shop scheduling. We review the existing literature, provide mathematical formulations, and develop a heuristic approach for the SMPTSP.     

The Single Period Coverage Facility Location Problem: Lagrangean heuristic and column generation approaches

In this paper we introduce the Single Period Coverage Facility Location Problem. It is a multi-period discrete location problem in which each customer is serviced in exactly one period of the planning horizon. The locational decisions are made independently for each period, so that the facilities that are open need not be the same in different time periods. It is also assumed that at each period there is a minimum number of customers that can be assigned to the facilities that are open. The decisions to be made include not only the facilities to open at each time period and the time period in which each customer will be served, but also the allocation of customers to open facilities in their service period.     

A branch-and-cut algorithm for a generalization of the Uncapacitated Facility Location Problem

Summary We introduce a generalization of the well-know Uncapacitated Facility Location Problem, in which clients can be served not only by single facilities but also by sets of facilitities. The problem, calledGaneralized Uncapacitated Facility Lacition Problem (GUFLP), was inspired by the Index Selection Problem in physical database design. We for mulate GUFLP as a Set Packing Problem, showing that our model contains all the clique inequalities (in polynomial number). Moreover, we describe and exact separation procedure for odd-hole inequalities, based on the particular structure of the problem. These results are used within a branch-and-cut algorithm for the exact solution of GUFLP. Computational results on two different classes of test problems are given.     

Covering models and optimization techniques for emergency response facility location and planning: a review

With emergencies being, unfortunately, part of our lives, it is crucial to efficiently plan and allocate emergency response facilities that deliver effective and timely relief to people most in need. Emergency Medical Services (EMS) allocation problems deal with locating EMS facilities among potential sites to provide efficient and effective services over a wide area with spatially distributed demands. It is often problematic due to the intrinsic complexity of these problems. This paper reviews covering models and optimization techniques for emergency response facility location and planning in the literature from the past few decades, while emphasizing recent developments. We introduce several typical covering models and their extensions ordered from simple to complex, including Location Set Covering Problem (LSCP), Maximal Covering Location Problem (MCLP), Double Standard Model (DSM), Maximum Expected Covering Location Problem (MEXCLP), and Maximum Availability Location Problem (MALP) models. In addition, recent developments on hypercube queuing models, dynamic allocation models, gradual covering models, and cooperative covering models are also presented in this paper. The corresponding optimization techniques to solve these models, including heuristic algorithms, simulation, and exact methods, are summarized.     

Combining very large scale and ILP based neighborhoods for a two-level location problem

In this paper we tackle a generalization of the Single Source Capacitated Facility Location Problem in which two sets of facilities, called intermediate level and upper level facilities, have to be located; the dimensioning of the intermediate set, the assignment of clients to intermediate level facilities, and of intermediate level facilities to upper level facilities, must be optimized, as well. Such problem arises, for instance, in telecommunication network design: in fact, in hierarchical networks the traffic arising at client nodes often have to be routed through different kinds of facility nodes, which provide different services. We propose a heuristic approach, based on very large scale neighborhood search to tackle the problem, in which both ad hoc algorithms and general purpose solvers are applied to explore the search space. We report on experimental results using datasets from the capacitated location literature. Such results show that the approach is promising and that Integer Linear Programming based neighborhoods are significantly effective.     

On the unboundedness of facility layout problems

Facility layout problems involve the location of facilities in a planar arrangement such that facilities that are strongly connected to one another are close to each other and facilities that are not connected may be far from one another. Pairs of facilities that have a negative connection should be far from one another. Most solution procedures assume that the optimal arrangement is bounded and thus do not incorporate constraints on the location of facilities. However, especially when some of the coefficients are negative, it is possible that the optimal configuration is unbounded. In this paper we investigate whether the solution to the facility layout problem is bounded or not. The main Theorem is a necessary and sufficient condition for boundedness. Sufficient conditions that prove boundedness or unboundedness are also given.     

Branch-and-Cut-and-Price for Capacitated Connected Facility Location

We consider a generalization of the Connected Facility Location Problem (ConFL), suitable to model real world network extension scenarios such as fiber-to-the-curb. In addition to choosing a set of facilities and connecting them by a Steiner tree as in ConFL, we aim to maximize the resulting profit by potentially supplying only a subset of all customers. Furthermore, capacity constraints on potential facilities need to be considered. We present two mixed integer programming based approaches which are solved using branch-and-cut and branch-and-cut-and-price, respectively. By studying the corresponding polyhedra we analyze both approaches theoretically and show their advantages over previously presented models. Furthermore, using a computational study we are able to additionally show significant advantages of our models over previously presented ones from a practical point of view.     

Tabu Search Heuristics for the Arc Routing Problem with Intermediate Facilities under Capacity and Length Restrictions

This paper deals with the Arc Routing Problem with Intermediate Facilities under Capacity and Length Restrictions(CLARPIF), a variant of the classical Capacitated Arc Routing Problem(CARP), in which vehicles may unload or replenish at intermediate facilities and the length of any route may not exceed a specified upper bound. Three heuristics are developed for the CLARPIF: the first is a constructive procedure based on a partitioning approach while the second and the third are tailored Tabu Search procedures. Computational results on a set of benchmark instances with up to 50 vertices and 92 required edges are presented and analyzed.     

A GRASP + ILP-based metaheuristic for the capacitated location-routing problem

In this paper we present a three-phase heuristic for the Capacitated Location-Routing Problem. In the first stage, we apply a GRASP followed by local search procedures to construct a bundle of solutions. In the second stage, an integer-linear program (ILP) is solved taking as input the different routes belonging to the solutions of the bundle, with the objective of constructing a new solution as a combination of these routes. In the third and final stage, the same ILP is iteratively solved by column generation to improve the solutions found during the first two stages. The last two stages are based on a new model, the location-reallocation model, which generalizes the capacitated facility location problem and the reallocation model by simultaneously locating facilities and reallocating customers to routes assigned to these facilities. Extensive computational experiments show that our method is competitive with the other heuristics found in the literature, yielding the tightest average gaps on several sets of instances and being able to improve the best known feasible solutions for some of them.     

货物列车的编组调度问题

研究的是货物列车的编组和调度问题.通过对问题的深入研究,设计了一种车辆编组调度方案的算法.按照这种算法,在数据处理的基础上利用VC编写每个问题的处理程序,实现了对列车的快速安全高效的调度.对每个问题进行处理,都得到符合要求的结果.问题一首先对整个车辆编组调度的问题进行分析,在尽量保证新组装列车满载的基础上,使每班的中时尽可能少.为此,本文解决了两个关键问题:一是选车问题,二是拆解重组的问题.采用梯形方案对列车车辆进行编队重组,对选车问题主要采用按照时间先后顺序的选车方案,然后通过启发式算法配合遗传算法的选车方案对按时间先后顺序的方案进行检验.从编写的VC程序的运行结果来看,两种方案都可得到满意的结果,遗传算法得到的结果更为合理.另外,为了达到中时最短,采用双推双滑的方式利用驼峰线,提高了调度效率,并在驼峰线和编组道之间加入了碰撞检验模块,保证了列车调度时的安全性.问题二的求解是在问题一的基础上对待拆列车按优先级进行分类.对优先级高的列车先进行拆解.救灾车辆最高,其次是军列和发往S1的车辆,最后是一般车辆.问题三的处理主要是在问题二的基础上,通过提前获得列车的相关信息来决定编组场的列车离开编组场的时刻,从而缩短车辆的中时.问题四在原有模型基础上对编组方案进行了修改,利用编写的VC程序重新计算了每班的中时和列车的调度方案.问题五主要分析了整个系统瓶颈所在,分析了提高资源利用率的可行性.最后,通过对站名的调整,达到了对地质灾害等对铁路系统的破坏突发情况的有效处理,并且进一步分析了如何提高车站的效率的调度方案和建议.     

Variable neighbourhood search heuristics for the probabilistic multi-source Weber problem

The Multi-source Weber Problem (MWP) is concerned with locating m facilities in the Euclidean plane, and allocating these facilities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation for the probabilistic MWP called the PMWP. For its solution, we propose two heuristics based on variable neighbourhood search (VNS). Computational results obtained on a number of test instances show that the VNS heuristics improve the performance of a probabilistic alternate location-allocation heuristic referred to as PALA. In its original form, the applicability of the new heuristics depends on the existence of a closed-form expression for the expected distances between facilities and customers. Unfortunately, such an expression exists only for a few distance function and probability distribution combinations. We therefore use two approximation methods for the expected distances, which make the VNS heuristics applicable for any distance function and bivariate distribution of customer locations.     

The directed profitable location Rural Postman Problem

In this paper we introduce an extension of the well known Rural Postman Problem, which combines arc routing with profits and facility location. Profitable arcs must be selected, facilities located at both end-points of the selected arcs, and a tour identified so as to maximize the difference between the profit collected along the arcs and the cost of traversing the arcs and installing the facilities. We analyze properties of the problem, present a mathematical programming formulation and a branch-and-cut algorithm. In an extensive computational experience the algorithm could solve instances with up to 140 vertices and 190 arcs and up to 50 vertices and 203 arcs.     

A multi-objective genetic algorithm for a bi-objective facility location problem with partial coverage

In this study, we present a bi-objective facility location model that considers both partial coverage and service to uncovered demands. Due to limited number of facilities to be opened, some of the demand nodes may not be within full or partial coverage distance of a facility. However, a demand node that is not within the coverage distance of a facility should get service from the nearest facility within the shortest possible time. In this model, it is assumed that demand nodes within the predefined distance of opened facilities are fully covered, and after that distance the coverage level decreases linearly. The objectives are defined as the maximization of full and partial coverage, and the minimization of the maximum distance between uncovered demand nodes and their nearest facilities. We develop a new multi-objective genetic algorithm (MOGA) called modified SPEA-II (mSPEA-II). In this method, the fitness function of SPEA-II is modified and the crowding distance of NSGA-II is used. The performance of mSPEA-II is tested on randomly generated problems of different sizes. The results are compared with the solutions of the most well-known MOGAs, NSGA-II and SPEA-II. Computational experiments show that mSPEA-II outperforms both NSGA-II and SPEA-II.     

An ILS heuristic for the traveling tournament problem with predefined venues

The Traveling Tournament Problem with Predefined Venues (TTPPV) is a single round robin variant of the Traveling Tournament Problem, in which the venue of each game to be played is known beforehand. We propose an Iterated Local Search (ILS) heuristic for solving real-size instances of the TTPPV, based on two types of moves. Initial solutions are derived from an edge coloring algorithm applied to complete graphs. We showed that canonical edge colorings should not be used as initial solutions in some situations. Instead, the use of Vizing’s edge coloring method lead to considerably better results. We also establish that the solution space defined by some commonly used neighborhoods in the sport scheduling literature is not connected in the case of single round robin tournaments, which explains the hardness of finding high quality solutions to some problem instances. Computational results show that the new ILS heuristic performs much better than heuristics based on integer programming and that it improves the best known solutions for benchmark instances.     

Multi-depot Multiple TSP: a polyhedral study and computational results

We study the Multi-Depot Multiple Traveling Salesman Problem (MDMTSP), which is a variant of the very well-known Traveling Salesman Problem (TSP). In the MDMTSP an unlimited number of salesmen have to visit a set of customers using routes that can be based on a subset of available depots. The MDMTSP is an NP-hard problem because it includes the TSP as a particular case when the distances satisfy the triangular inequality. The problem has some real applications and is closely related to other important multi-depot routing problems, like the Multi-Depot Vehicle Routing Problem and the Location Routing Problem. We present an integer linear formulation for the MDMTSP and strengthen it with the introduction of several families of valid inequalities. Certain facet-inducing inequalities for the TSP polyhedron can be used to derive facet-inducing inequalities for the MDMTSP. Furthermore, several inequalities that are specific to the MDMTSP are also studied and proved to be facet-inducing. The partial knowledge of the polyhedron has been used to implement a Branch-and-Cut algorithm in which the new inequalities have been shown to be very effective. Computational results show that instances involving up to 255 customers and 25 possible depots can be solved optimally using the proposed methodology.     

Optimal Control of a Ship for Course Change and Sidestep Maneuvers

We consider a ship subject to kinematic, dynamic, and moment equations and steered via rudder under the assumptions that the rudder angle and rudder angle time rate are subject to upper and lower bounds. We formulate and solve four Mayer problems of optimal control, the optimization criterion being the minimum time.Problems P1 and P2 deal with course change maneuvers. In Problem P1, a ship initially in quasi-steady state must reach the final point with a given yaw angle and zero yaw angle time rate. Problem P2 differs from Problem P1 in that the additional requirement of quasi-steady state is imposed at the final point.Problems P3 and P4 deal with sidestep maneuvers. In Problem P3, a ship initially in quasi-steady state must reach the final point with a given lateral distance, zero yaw angle, and zero yaw angle time rate. Problem P4 differs from Problem P3 in that the additional requirement of quasi-steady state is imposed at the final point.The above Mayer problems are solved via the sequential gradient-restoration algorithm in conjunction with a new singularity avoiding transformation which accounts automatically for the bounds on rudder angle and rudder angle time rate.The optimal control histories involve multiple subarcs along which either the rudder angle is kept at one of the extreme positions or the rudder angle time rate is held at one of the extreme values. In problems where quasi-steady state is imposed at the final point, there is a higher number of subarcs than in problems where quasi-steady state is not imposed; the higher number of subarcs is due to the additional requirement that the lateral velocity and rudder angle vanish at the final point.     

The Multi-Story Space Assignment Problem

The Multi-Story Space Assignment Problem (MSAP) is an innovative formulation of the multi-story facility assignment problem that allows one to model the location of departments of unequal size within multi-story facilities as a Generalized Quadratic 3-dimensional Assignment Problem (GQ3AP). Not only can the MSAP generate the design of the location of the departments in the facility, the MSAP also includes the evacuation planning for the facility. The formulation, background mathematical development, and computational experience with a branch and bound algorithm for the MSAP are also presented.