This paper introduces the Flexible Periodic Vehicle Routing Problem (FPVRP) where a carrier has to establish a distribution plan to serve his customers over a planning horizon. Each customer has a total demand that must be served within the horizon and a limit on the maximum quantity that can be delivered at each visit. A fleet of homogeneous capacitated vehicles is available to perform the services and the objective is to minimize the total routing cost. The FPVRP can be seen as a generalization of the Periodic Vehicle Routing Problem (PVRP) which instead has fixed service frequencies and schedules and where the quantity delivered at each visit is fixed. Moreover, the FPVRP shares some common characteristics with the Inventory Routing Problem (IRP) where inventory levels are considered at each time period and, typically, an inventory cost is involved in the objective function. We present a worst-case analysis which shows the advantages of the FPVRP with respect to both PVRP and IRP. Moreover, we propose a mathematical formulation for the problem, together with some valid inequalities. Computational results show that adding flexibility improves meaningfully the routing costs in comparison with both PVRP and IRP.
This work presents an optimization-based approach to simultaneously solve the Network Design and the Frequency Setting phases on the context of railway rapid transit networks. The Network Design phase allows expanding existing networks as well as building new ones from scratch, considering infrastructure costs. In the Frequency Setting phase, local and/or express services are established considering transportation resources capacities and operation costs. Integrated approaches to these phases improve the transit planning process. Nevertheless, this integration is challenging both at modeling and computational effort to obtain solutions. In this work, a Lexicographic Goal Programming problem modeling this integration is introduced, together with a solving strategy. A solution to the problem is obtained by first applying a Corridor Generation Algorithm and then a Line Splitting Algorithm to deal with multiple line construction. Two case studies are used for validation, including the Seville and Santiago de Chile rapid transit networks. Detailed solution reports are shown and discussed. Conclusions and future research directions are given.
The consideration of worker heterogeneity in assembly lines has received a fair amount of attention in the literature in the past decade. Most of this exploration uses as motivation the example of assembly lines in sheltered work centers for the disabled. Only recently has the community started looking at the situation faced in assembly lines in the general industrial park, when in the presence of worker heterogeneity. This step raises a number of questions around the best way to incorporate heterogeneous workers in the line, maximizing their integration while maintaining productivity levels. In this paper we propose the use of Miltenburg’s regularity criterion and cycle time as metrics for integration of workers and productivity, respectively. We then define, model and develop heuristics for a line balancing problem with these two goals. Results obtained through an extensive set of computational experiments indicate that a good planning can obtain trade-off solutions that perform well in both objectives.
Triado-Aymerich, J.; Ferrer-Martí, L.; García-Villoria, A.; Pastor, Rafael Computers & operations research Vol. 71, p. 90-99 DOI: 10.1016/j.cor.2016.01.010 Data de publicació: 2016-07-01 Article en revista
Wind-photovoltaic systems are a suitable option to provide electricity to isolated communities autonomously. To design these systems, there are recent mathematical models that solve the location and type of each of the electrification components and the design of the possible distribution microgrids. When the amount of demand points to electrify increases, solving the mathematical model requires a computational time that becomes infeasible in practice. To speed up the solving process, three heuristic methods based on mixed integer linear programming (MILP) are presented in this paper: Relax and Fix heuristics, heuristics based on a Corridor Method and Increasing Radius heuristics. In all algorithms first a relaxed MILP is solved to obtain a base solution and then it is used as a starting point to find a feasible solution by searching in a reduced search space. For each type of heuristic several options to relax and to reduce the solution space are developed and tested. Extensive computational experiments based on real projects are carried out and results show that the best heuristic vary according to the size of instances. (C) 2016 Elsevier Ltd. All rights reserved.
Wind-photovoltaic systems are a suitable option to provide electricity to isolated communities autonomously. To design these systems, there are recent mathematical models that solve the location and type of each of the electrification components and the design of the possible distribution microgrids. When the amount of demand points to electrify increases, solving the mathematical model requires a computational time that becomes infeasible in practice. To speed up the solving process, three heuristic methods based on mixed integer linear programming (MILP) are presented in this paper: Relax and Fix heuristics, heuristics based on a Corridor Method and Increasing Radius heuristics. In all algorithms first a relaxed MILP is solved to obtain a base solution and then it is used as a starting point to find a feasible solution by searching in a reduced search space. For each type of heuristic several options to relax and to reduce the solution space are developed and tested. Extensive computational experiments based on real projects are carried out and results show that the best heuristic vary according to the size of instances.
This paper introduces a new arc routing problem for the optimization of a collaboration scheme among carriers. This yields to the study of a profitable uncapacitated arc routing problem with multiple depots, where carriers collaborate to improve the profit gained. In the first model the goal is the maximization of the total profit of the coalition of carriers, independently of the individual profit of each carrier. Then, a lower bound on the individual profit of each carrier is included. This lower bound may represent the profit of the carrier in the case no collaboration is implemented. The models are formulated as integer linear programs and solved through a branch-and-cut algorithm. Theoretical results, concerning the computational complexity, the impact of collaboration on profit and a game theoretical perspective, are provided. The models are tested on a set of 971 instances generated from 118 benchmark instances for the Privatized Rural Postman Problem, with up to 102 vertices. All the 971 instances are solved to optimality within few seconds.
Single machine scheduling is a classical optimization problem that depicts multiple real life systems in which a single resource (the machine) represents the whole system or the bottleneck operation of the system. In this paper we consider the problem under a weighted completion time performance metric in which the processing time of the tasks to perform (the jobs) are uncertain, but can only take values from closed intervals. The objective is then to find a solution that minimizes the maximum absolute regret for any possible realization of the processing times. We present an exact branch-and-bound method to solve the problem, and conduct a computational experiment to ascertain the possibilities and limitations of the proposed method. The results show that the algorithm is able to optimally solve instances of moderate size (25-40 jobs depending on the characteristics of the instance)
In some assembly lines, the workpieces are larger than the workstations. This implies that at a given instant the workstations have access to only a portion of the workpieces. In this context, the accessibility windows assembly line balancing problem (AWALBP) arises. In the AWALBP, the cycle is split into forward steps and stationary stages. The workpieces advance during the forward steps and the tasks are processed during the stationary stages. In each stationary stage, the workstations have access to different parts of the workpieces. This work solves the first level of AWALBP (AWALBP-L1), which consists in assigning the tasks among the workstations and stationary stages. Specifically, it is considered the AWALBP-L1 case in which the tasks can be processed in several workstations and their processing times depend on the workstation in which the tasks are processed. To solve the problem, we propose several heuristics and simulated annealing procedures. An extensive computational experiment is carried out to evaluate their performance
This paper presents the p-next center problem, which aims to locate p out of n centers so as to minimize the maximum cost of allocating customers to backup centers. In this problem it is assumed that centers can fail and customers only realize that their closest (reference) center has failed upon arrival. When this happens, they move to their backup center, i.e., to the center that is closest to the reference center. Hence, minimizing the maximum travel distance from a customer to its backup center can be seen as an alternative approach to handle humanitarian logistics, that hedges customers against severe scenario deteriorations when a center fails.
For this extension of the p-center problem we have developed several different integer programming formulations with their corresponding strengthenings based on valid inequalities and variable fixing. The suitability of these formulations for solving the p-next center problem using standard software is analyzed in a series of computational experiments. These experiments were carried out using instances taken from the previous discrete location literature.
Controlled tabular adjustment (CIA) is a relatively new protection technique for tabular data protection. CTA formulates a mixed integer linear programming problem, which is challenging for tables of moderate size. Even finding a feasible initial solution may be a challenging task for large instances. On the other hand, end users of tabular data protection techniques give priority to fast executions and are thus satisfied in practice with suboptimal solutions. This work has two goals. First, the fix-and-relax (FR) strategy is applied to obtain good feasible initial solutions to large CTA instances. FR is based on partitioning the set of binary variables into clusters to selectively explore a smaller branch-and-cut tree. Secondly, the FR solution is used as a warm start for a block coordinate descent (BCD) heuristic (approach named FR+BCD); BCD was confirmed to be a good option for large CTA instances in an earlier paper by the second and third co-authors (Comput Oper Res 2011;38:1826-35 ). We report extensive computational results on a set of real-world and synthetic CTA instances. FR is shown to be competitive compared to CPLEX branch-and-cut in terms of quickly finding either a feasible solution or a good upper bound. FR+BCD improved the quality of FR solutions for approximately 25% and 50% of the synthetic and real-world instances, respectively. FR or FR+BCD provided similar or better solutions in less CPU time than CPLEX for 73% of the difficult real-world instances. (C) 2015 Elsevier Ltd. All rights reserved.
This paper focuses on the capacitated minimum spanning tree (CMST) problem. Given a central processor and a set of remote terminals with specified demands for traffic that must flow between the central processor and terminals, the goal is to design a minimum cost network to carry this demand.
Potential links exist between any pair of terminals and between the central processor and the terminals.
Each potential link can be included in the design at a given cost. The CMST problem is to design a
minimum-cost network connecting the terminals with the central processor so that the flow on any arc
of the network is at most Q. A biased random-key genetic algorithm(BRKGA) is a metaheuristic for
combinatorial optimization which evolves a population of random vectors that encode solutions to the
combinatorial optimization problem.This paper explores several solution encodings as well as different
strategies for some steps of the algorithm and finally proposes a BRKGA heuristic for the CMST problem.
Computational experiments are presented showing the effectiveness of the approach:Seven new best-
known solutions are presented for the set of benchmark instances used in the experiments.
This paper focuses on the capacitated minimum spanning tree(CMST)problem.Given a central
processor and a set of remote terminals with specified demands for traffic that must flow between the central processor and terminals,the goal is to design a minimum cost network to carry this demand.
Potential links exist between any pair of terminals and between the central processor and the terminals.
Each potential link can be included in the design at a given cost.The CMST problem is to design a
minimum-cost network connecting the terminals with the central processor so that the flow on any arc of the network is at most Q. A biased random-keygenetic algorithm(BRKGA)is a metaheuristic for combinatorial optimization which evolves a population of random vectors that encode solutions to the combinatorial optimization problem.This paper explores several solution encodings as well as different
strategies for some steps of the algorithm and finally proposes a BRKGA heuristic for the CMST problem.
Computational experiments are presented showing the effectivenes sof the approach:Seven newbest-
known solutions are presented for the set of benchmark instances used in the experiments.
This paper introduces the Dynamic Multiperiod Vehicle Routing Problem with Probabilistic Information, an extension of the Dynamic Multiperiod Vehicle Routing Problem in which, at each time period, the set of customers requiring a service in later time periods is unknown, but its probability distribution is available. Requests for service must be satisfied within a given time window that comprises several time periods of the planning horizon. We propose an adaptive service policy that aims at estimating the best time period to serve each request within its associated time window in order to reduce distribution costs. The effectiveness of this policy is compared with that of two alternative basic policies through a series of computational experiments. (C) 2014 Elsevier Ltd. All rights reserved.
We propose an approach combining a matheuristic and a MILP model to solve the variant Level 2 of the Accessibility Windows Assembly Line Balancing Problem (AWALBP-L2). This is a novel problem that arises in those real-world assembly lines where, in contrast to the most common ones, the length of the workpieces is larger than the widths of the workstations. This means that, at any time, a workstation cannot access an entire workpiece, but only a restricted portion of a workpiece or two consecutive workpieces. As a result, a workstation can only perform, at any time, the subset of tasks that fall inside its accessible area. The problem is to solve the task assignment and the movement scheme subproblems, while minimizing the cycle time. The proposed solving approach consists of (i) a matheuristic to generate good feasible solutions and compute bounds and (ii) a MILP model that makes use of the obtained bounds. A computational study is carried out to compare the performance of the proposed approach with the existing literature. (C) 2014 Elsevier Ltd. All rights reserved.
In this paper, we studied the assembly line worker assignment and balancing problem, which is an extension of the classical assembly line balancing problem in which an optimal partition of the assembly work among the stations is sought along with the assignment of the operators to the stations. The relationship between this problem and several other well-studied problems is explored, and new lower bounds are derived. Additionally, an exact enumeration algorithm, which makes use of the lower bounds, is developed to solve the problem. The algorithm is tested by using a standard benchmark set of instances. The results show that the algorithm improves upon the best-performing methods from the literature in terms of solution quality, and verifies more optimal solutions than the other available exact methods. (C) 2013 Elsevier Ltd. All rights reserved.
Pedrola, O.; Ruiz, M.; Velasco, L.; Careglio, D.; González de Dios , O.; Comellas, J. Computers & operations research Vol. 40, num. 12, p. 3174-3187 DOI: 10.1016/j.cor.2011.10.026 Data de publicació: 2013-12 Article en revista
In this paper we deal with the survivable internet protocol (IP)/multi-protocol label switching (MPLS)-over-wavelength switched optical network (WSON) multi-layer network optimization problem (SIMNO). This problem entails planning an IP/MPLS network layer over a photonic mesh infrastructure whilst, at the same time, ensuring the highest availability of services and minimizing the capital expenditures (CAPEX) investments. Such a problem is currently identified as an open issue among network operators, and hence, its solution is of great interest. To tackle SIMNO, we first provide an integer linear programming (ILP) formulation which provides an insight into the complexity of its managing. Then, a greedy randomized adaptive search procedure (GRASP) with path-relinking (PR) together with a biased random-key genetic algorithm (BRKGA) are specifically developed to help solve the problem. The performance of both heuristics is exhaustively tested and compared making use of various network and traffic instances. Numerical experiments show the benefits of using GRASP instead of BRKGA when dealing with highly complex network scenarios. Moreover, we verified that the use of GRASP with PR remarkably improves the basic GRASP algorithm, particularly in real-sized, complex scenarios such as those proposed in this paper.
Albareda-Sambola, M.; Alonso Ayuso, A.; Escudero, L.F.; Fernandez, E.; Pizarro-Romero, C. Computers & operations research Vol. 40, num. 12, p. 2878-2892 DOI: 10.1016/j.cor.2013.07.004 Data de publicació: 2013-12 Article en revista
A multi-period discrete facility location problem is introduced for a risk neutral strategy with uncertainty in the costs and some of the requirements along the planning horizon. A compact 0–1 formulation for the Deterministic Equivalent Model of the problem under two alternative strategies for the location decisions is presented. Furthermore, a new algorithmic matheuristic, Fix-and-Relax-Coordination, is introduced. This solution scheme is based on a specialization of the Branch-and-Fix Coordination methodology, which exploits the Nonanticipativity Constraints and uses the Twin Node Family concept. The results of an extensive computational experience allow to compare the alternative modeling strategies and assess the effectiveness of the proposed approach versus the plain use of a state-of-the-art MIP solver.
The minmax response time problem (mRTP) is a scheduling problem that has recently appeared in the literature and can be considered as a fair sequencing problem. This kind of problems appears in a wide range of real-world applications in mixed-model assembly lines, computer systems, periodic maintenance and others. The mRTP arises whenever products, clients or jobs need to be sequenced in such a way that the maximum time between the points at which they receive the necessary resources is minimised. The mRTP has been solved in the literature with a greedy heuristic. The objective of this paper is to improve the solution of this problem by means of exact and heuristic methods. We propose one mixed integer linear programming model, nine local search procedures and five metaheuristic algorithms. Extensive computational experiments are carried out to test them.
The present paper studies the single machine, no-idle-time scheduling problem with a weighted quadratic earliness and tardiness objective. We investigate the relationship between this problem and the assignment problem, and we derive two lower bounds and several heuristic procedures based on this relationship. Furthermore, the applicability of the time-indexed integer programming formulation is investigated. The results of a computational experiment on a set of randomly generated instances show (1) the high-quality results of the proposed heuristics, (2) the low optimality gap of one of the proposed lower bounds and (3) the applicability of the integer programming formulation to small and medium size cases of the problem.
The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches.
The reconstruction of founder genetic sequences of a population is a relevant issue in evolutionary biology research. The problem consists in finding a biologically plausible set of genetic sequences (founders), which can be recombined to obtain the genetic sequences of the individuals of a given population. The reconstruction of these sequences can be modelled as a combinatorial optimisation problem in which one has to find a set of genetic sequences such that the individuals of the population under study can be obtained by recombining founder sequences minimising the number of recombinations. This problem is called the founder sequence reconstruction problem. Solving this problem can contribute to research in understanding the origins of specific genotypic traits. In this paper, we present large neighbourhood search algorithms to tackle this problem. The proposed algorithms combine a stochastic local search with a branch-and-bound algorithm devoted to neighbourhood exploration. The developed algorithms are thoroughly evaluated on three different benchmark sets and they establish the new state of the art for realistic problem instances.
The reorganization of the electricity industry in Spain completed a new step with the start-up of the Derivatives Market.
One main characteristic of MIBEL’s Derivatives Market is the existence of physical futures contracts; they imply
the obligation to physically settle the energy. The market regulation establishes the mechanism for including those
physical futures in the day-ahead bidding of the Generation Companies. The goal of this work is to optimize coordination
between physical futures contracts and the day-ahead bidding which follow this regulation. We propose a
stochastic quadratic mixed-integer programming model which maximizes the expected profits, taking into account futures
contracts settlement. The model gives the simultaneous optimization for the Day-Ahead Market bidding strategy
and power planning production (unit commitment) for the thermal units of a price-taker Generation Company. The
uncertainty of the Day-Ahead Market price is included in the stochastic model through a set of scenarios. Implementation
details and some first computational experiences for small real cases are presented.
In this paper, an extensive review of recently published papers on hybrid flow shop (HFS) scheduling problems is presented. The papers are classified first according to the HFS characteristics and production limitations considered in the respective papers. This represents a new approach to the classification of papers in the HFS environment. Second, the papers have been classified according to the solution approach proposed. These two classification categories give a comprehensive overview on the state of the art of the problem and can guide the reader with respect to future research work.
In this paper a three steps heuristic for the permutation flow shop problem is proposed. The objective is to minimize the maximum time for completing the jobs, or the makespan. The first two steps are inspired by the NEH heuristic, to which a new tie breaking strategy has been incorporated in the insertion phase. Furthermore, the reversibility property of the problem dealt with is taken as a tool for improving the obtained solution. The third step consists of an iterated local search procedure with an embedded local search which is a variant of the non exhaustive descent algorithm. The statistical analysis of the results shows the effectiveness of the proposed procedures.
In this paper we introduce the multi-period incremental service facility location problem where the goal is to set a number of new facilities over a finite time horizon so as to cover dynamically the demand of a given set of customers. We prove that the coefficient matrix of the allocation subproblem that results when fixing the set of facilities to open is totally unimodular. This allows to solve efficiently the Lagrangean problem that relaxes constraints requiring customers to be assigned to open facilities. We propose a solution approach that provides both lower and upper bounds bt combining subgradient optimization to solve a Lagrangean dual with an ad hoc heuristic that uses information from the Lagrangean subproblem to generate feasible solutions. Numerical results obtained in the computational experiments show that the obtained solutions are very good. In general, we get very small percent gaps between upper and lower bounds with little computation effort.
This paper describes the methodology that we have applied for the solution of an urban
waste collection problem in the municipality of Sant Boi de Llobregat, within the metropolitan
area of Barcelona (Spain). The basic nature of the considered problem is that of a
capacitated arc routing problem, although it has several specific characteristics, mainly derived
from trafic regulations. We present the model that we have built for the problem,
which results after an appropriate transformation of the problem into a node routing one.
We also present the ant colonies heuristics that we have used to obtain the solutions to the
problem. These combine constructive methods, based on nearest neighbor and on nearest
insertion, with a local search that explores various neighborhoods. The application of the
proposed methods gives results that improve considerably the ones that were previously used
in the municipality.
Randomization is a well-known numerical method for the transient analysis of continuous-time Markov chains. The main advantages of the method are numerical stability, well-controlled computation error and ability to specify the computation error in advance. Typical implementations of the method control the truncation error in absolute value, which is not completely satisfactory in some cases. Based on a theoretical result regarding the dependence on the parameter of the Poisson distribution of the relative error introduced when a weighted sum of Poisson probabilities is truncated by the right, in this paper we develop efficient and numerically stable implementations of the randomization method for the computation of two measures on rewarded continuous-time Markovchains with control of the relative error. The numerical stability of those implementations is analyzed using a small example. We also discuss the computational efficiency of the implementations with respect to simpler alternatives.
This paper considers a combined location-routing problem. We define an auxiliary network and give a compact formulation of the problem in terms of finding a set of paths in the auxiliary network that fulfill additional constraints. The LP solution to the considered model provides an initial lower bound and is also used in a rounding procedure that provides the initial solution for a Tabu search heuristic. Additionally, we propose a different lower bound based on the structure of the problem. The results of computational testing on a set of randomly generated instances are promising.
Fault-tolerant systems are often modeled using (homogeneous) continuous time Markovchains (CTMCs).
Computation of the distribution of the interval availability, i.e. of the distribution of the fraction of time in
a time interval in which the system is operational, of a fault-tolerant system modeled by a CTMC is an important problem which has received attention recently. However, currently available methods to perform that computation are very expensive for large models and large time intervals. In this paper, we develop a new method to compute the distribution of the interval availability which, for large enough models and large enough time intervals, is significantly faster than previous methods. In the method, a truncated transformed model,
which has with some arbitrarily small error the same interval availability distribution as the original model, is obtained from the original model and the truncated transformed model is solved using a previous state-of-the-art method. The method requires the selection of a “regenerative” state and its performance depends on that selection. For a class of models, including typical failure/repair models of coherent fault-tolerant systems with exponential failure and repair time distributions and repair in every state with failed components, a natural
selection for the regenerative state exists and theoretical results are available assessing the performance of the method for that natural selection in terms of “visible” model characteristics. Those results can be used to anticipate when the method can be expected to be competitive for models in that class. Numerical results are presented showing that the new method can indeed be significantly faster than a previous state-of-the-art method and is able to deal with some large models and large time intervals in reasonable CPU times.