GRASP and path relinking for the max–min diversity problem

The max–min diversity problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among the selected elements is maximized. The problem is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in the social and biological sciences. We propose a heuristic method—based on the GRASP and path relinking methodologies—for finding approximate solutions to this optimization problem. We explore different ways to hybridize GRASP and path relinking, including the recently proposed variant known as GRASP with evolutionary path relinking. Empirical results indicate that the proposed hybrid implementations compare favorably to previous metaheuristics, such as tabu search and simulated annealing.     

Tabu search with path relinking for an integrated production–distribution problem

This paper deals with the problem of integrating production and distribution planning over periods of a finite horizon. We consider a capacity-constrained plant that produces a number of items distributed by a fleet of homogenous vehicles to customers with known demand for each item in each period. The production planning defines the amount of each item produced in every period, while the distribution planning defines when customers should be visited, the amount of each item that should be delivered to customers, and the vehicle routes. The objective is to minimize production and inventory costs at the plant, inventory costs at the customers and distribution costs. We propose two tabu search variants for this problem, one that involves construction and a short-term memory, and one that incorporates a longer term memory used to integrate a path relinking procedure to the first variant. The proposed tabu search variants are tested on generated instances with up to ten items and on instances from the literature involving a single item.     

Tabu search and lower bounds for a combined production–transportation problem

In this paper we consider a combined production–transportation problem, where n jobs have to be processed on a single machine at a production site before they are delivered to a customer. At the production stage, for each job a release date is given; at the transportation stage, job delivery should be completed not later than a given due date. The transportation is done by m identical vehicles with limited capacity. It takes a constant time to deliver a batch of jobs to the customer. The objective is to find a feasible schedule minimizing the maximum lateness.     

Formulations and relaxations for a multi-echelon capacitated location–distribution problem

We consider a multi-echelon location–distribution problem arising from an actual application in fast delivery service. We present and compare two formulations for this problem: an arc-based model and a path-based model. We show that the linear programming (LP) relaxation of the path-based model provides a better bound than the LP relaxation of the arc-based model. We also compare the so-called binary relaxations of the models, which are obtained by relaxing the integrality constraints for the general integer variables, but not for the 0–1 variables. We show that the binary relaxations of the two models always provide the same bound, but that the path-based binary relaxation appears preferable from a computational point of view, since it can be reformulated as an equivalent simple plant location problem (SPLP), for which several efficient algorithms exist. We also show that the LP relaxation of this SPLP reformulation provides a better bound than the LP relaxation of the path-based model.     

The integrated production–inventory–distribution–routing problem

The integration of production and distribution decisions presents a challenging problem for manufacturers trying to optimize their supply chain. At the planning level, the immediate goal is to coordinate production, inventory, and delivery to meet customer demand so that the corresponding costs are minimized. Achieving this goal provides the foundations for streamlining the logistics network and for integrating other operational and financial components of the system. In this paper, a model is presented that includes a single production facility, a set of customers with time varying demand, a finite planning horizon, and a fleet of vehicles for making the deliveries. Demand can be satisfied from either inventory held at the customer sites or from daily product distribution. In the most restrictive case, a vehicle routing problem must be solved for each time period. The decision to visit a customer on a particular day could be to restock inventory, meet that day’s demand or both. In a less restrictive case, the routing component of the model is replaced with an allocation component only. A procedure centering on reactive tabu search is developed for solving the full problem. After a solution is found, path relinking is applied to improve the results. A novel feature of the methodology is the use of an allocation model in the form of a mixed integer program to find good feasible solutions that serve as starting points for the tabu search. Lower bounds on the optimum are obtained by solving a modified version of the allocation model. Computational testing on a set of 90 benchmark instances with up to 200 customers and 20 time periods demonstrates the effectiveness of the approach. In all cases, improvements ranging from 10–20% were realized when compared to those obtained from an existing greedy randomized adaptive search procedure (GRASP). This often came at a three- to five-fold increase in runtime, however.     

A GRASP×ELS approach for the capacitated location-routing problem

This paper addresses the capacitated location-routing problem (CLRP), raised by distribution networks involving depot location, fleet assignment and routing decisions. The CLRP is defined by a set of potential depot locations, with opening costs and limited capacities, a homogeneous fleet of vehicles, and a set of customers with known demands. The objective is to open a subset of depots, to assign customers to these depots and to design vehicle routes, in order to minimize both the cost of open depots and the total cost of the routes. The proposed solution method is a greedy randomized adaptive search procedure (GRASP), calling an evolutionary local search (ELS) and searching within two solution spaces: giant tours without trip delimiters and true CLRP solutions. Giant tours are evaluated via a splitting procedure that minimizes the total cost subject to vehicle capacity, fleet size and depot capacities. This framework is benchmarked on classical instances. Numerical experiments show that the approach outperforms all previously published methods and provides numerous new best solutions.     

A feasibility evaluation approach for time-evolving multi-item production–distribution networks

Time-dependent multi-item problems arise frequently in management applications, communication systems, and production–distribution systems. Our problem belongs to the last category, where we wish to address the feasibility of such systems when all network parameters change over time and product. The objective is to determine whether it is possible to have a dynamic production–shipment circuit within a finite planning horizon. And, if there is no such a flow, the goal is to determine where and when the infeasibility occurs and the approximate magnitude of the infeasibility. This information may help the decision maker in their efforts to resolve the infeasibility of the system. The problem in the discrete-time settings is investigated and a hybrid of scaling approach and penalty function method together with network optimality condition is utilized to develop a network-based algorithm. This algorithm is analysed from theoretical and practical perspectives by means of instances corresponding to some electricity transmission-distribution networks and many random instances. Computational results illustrate the performance of the algorithm.     

An effective GRASP and tabu search for the 0–1 quadratic knapsack problem

As a generalization of the classical 0-1 knapsack problem, the 0-1 Quadratic Knapsack Problem (QKP) that maximizes a quadratic objective function subject to a linear capacity constraint is NP-hard in strong sense. In this paper, we propose a memory based Greedy Randomized Adaptive Search Procedures (GRASP) and a tabu search algorithm to find near optimal solution for the QKP. Computational experiments on benchmarks and on randomly generated instances demonstrate the effectiveness and the efficiency of the proposed algorithms, which outperforms the current state-of-the-art heuristic Mini-Swarm in computational time and in the probability to achieve optimal solutions. Numerical results on large-sized instances with up to 2000 binary variables have also been reported.     

A review and critique on integrated production–distribution planning models and techniques

Optimisation modelling of integrated production–distribution (P–D) plans has raised significant interest among both researchers and practitioners over the past two decades. This paper provides the readers with a comprehensive review and critique on the current P–D planning and optimisation literature. We classify the published P–D planning models into seven categories based on their degree of complexity and hence capability in addressing real-life scenarios. Summary tables highlight the main characteristics of the selected models at each category. Next, the paper reclassifies and evaluates the proposed models based on the solution techniques used. Lastly, the unaddressed areas in the current literature are highlighted, important managerial implications are proposed and directions for future research in the area are suggested.     

A GRASP × ILS for the vehicle routing problem with time windows,synchronization and precedence constraints

Efficient use of resources while ensuring quality services points the attention of Home Health Care structures (HHC). HHC structures propose keeping at home patients who do not necessarily need full hospitalization, and enabling people who suffered serious illnesses to follow the care from their own home. Habitually, asked services have to be performed at specific times, and may require the intervention of several qualified caregivers related by precedence constraints. These structures have the concern to reduce product consumption costs, limit losses and provide high quality services. Their main budgetary item is defined by the personal salary, which is incompressible. So, costs should be reduced on other posts. In this context, personal travel cost has a major importance in the spending of the institutions, which seems necessary to optimize. Moreover, patient satisfaction is also a significant criterion in improving the service quality of such structures. Therefore, developing an effective caregivers planning require the use of optimization methods and decision tools. In this article, this issue is modeled as a particular variant of vehicle routing problem with time windows and timing constraints, where some patients ask for more than one visit simultaneously or in a given priority order, called as the VRPTW-SP. Timing constraints handled in this paper make the problem realistic that are more difficult to solve than VRPTW. The VRPTW-SP is a challenging and novel optimization problem, whose objective is the minimization of the caregivers travel cost added to the non preferences toward caregivers. To solve this problem, a Mixed Integer Linear Program, a greedy heuristic, two local search strategies and three metaheuristics are proposed, one being a hybridization of the two others. Experiments are conducted on new instances derived from the literature. As the metaheuristics share the same components the positive contribution of the hybridization is proved on the VRPTW-SP by statistical tests.     

A GRASP×ELS for the vehicle routing problem with basic three-dimensional loading constraints

This paper addresses an extension of the capacitated vehicle routing problem where the client demand consists of three-dimensional weighted items (3L-CVRP). The objective is to design a set of trips for a homogeneous fleet of vehicles based at a depot node which minimizes the total transportation cost. Items in each vehicle trip must satisfy the three-dimensional orthogonal packing constraints. This problem is strongly connected to real-life transportation systems where the packing of items to be delivered by each vehicle can have a significant impact on the routes. We propose a new way to solve the packing sub-problem. It consists of a two-step procedure in which the z-constraints are first relaxed to get a (x,y) positioning of the items. Then, a compatible z-coordinate is computed to get a packing solution. Items can be rotated but additional constraints such as item fragility, support and LIFO are not considered. This method is included in a GRASP×ELS hybrid algorithm dedicated to the computation of VRP routes. The route optimization alternates between two search spaces: the space of VRP routes and the space of giant trips. The projection from one to the other is done by dedicated procedures (namely the Split and the concatenation algorithms). Moreover, a Local Search is defined on each search space. Furthermore, hash tables are used to store the result of the packing checks and thus save a substantial amount of CPU time. The effectiveness of our approach is illustrated by computational experiments on 3L-CVRP instances from the literature. A new set of realistic instances based on the 96 French districts are also proposed. They range from 19 nodes for the small instances to 255 nodes for the large instances and they can be stated as realistic since they are based on true travel distances in kilometers between French cities. The impact of the hash tables is illustrated as well.     

A simulation based heuristic discrete particle swarm algorithm for generating integrated production–distribution plan

Deciding the strategy for production and distribution in a stochastic demand scenario is important for the manufacturing industries. An integrated production–distribution plan considering regular, overtime and outsourced production costs along with inventory holding, backorder, hiring/laying-off and trip-wise distribution costs is developed for a renowned bearing manufacturing industry producing three types of products at three locations. Demand is assumed to vary uniformly and a novel simulation based heuristic discrete particle swarm optimization (DPSO) algorithm is used for obtaining the best production–distribution plan that serves as a trade-off between holding inventory and backordering products. The algorithm also uses an innovative regeneration type constraint handling method which does not require a penalty operator. In addition to the bearing manufacturing industry data set, two other test data sets are also solved. The simulation based optimization approach gives good approximate solutions for the stochastic demand problems.     

A priori and a posteriori error analysis of an augmented mixed-FEM for the Navier–Stokes–Brinkman problem

We introduce and analyze an augmented mixed finite element method for the Navier–Stokes–Brinkman problem with nonsolenoidal velocity. We employ a technique previously applied to the stationary Navier–Stokes equation, which consists of the introduction of a modified pseudostress tensor relating the gradient of the velocity and the pressure with the convective term, and propose an augmented pseudostress–velocity formulation for the model problem. The resulting augmented scheme is then written equivalently as a fixed point equation, so that the well-known Banach fixed point theorem, combined with the Lax–Milgram lemma, are applied to prove the unique solvability of the continuous and discrete systems. We point out that no discrete inf–sup conditions are required for the solvability analysis, and hence, in particular for the Galerkin scheme, arbitrary finite element subspaces of the respective continuous spaces can be utilized. For instance, given an integer $k\ge 0$, the Raviart–Thomas spaces of order $k$ and continuous piecewise polynomials of degree $\le k+1$ constitute feasible choices of discrete spaces for the pseudostress and the velocity, respectively, yielding optimal convergence. We also emphasize that, since the Dirichlet boundary condition becomes a natural condition, the analysis for both the continuous an discrete problems can be derived without introducing any lifting of the velocity boundary datum. In addition, we derive a reliable and efficient residual-based a posteriori error estimator for the augmented mixed method. The proof of reliability makes use of a global inf–sup condition, a Helmholtz decomposition, and local approximation properties of the Clément interpolant and Raviart–Thomas operator. On the other hand, inverse inequalities, the localization technique based on element-bubble and edge-bubble functions, approximation properties of the $L^2$-orthogonal projector, and known results from previous works, are the main tools for proving the efficiency of the estimator. Finally, some numerical results illustrating the performance of the augmented mixed method, confirming the theoretical rate of convergence and properties of the estimator, and showing the behavior of the associated adaptive algorithms, are reported.     

A preference ordered classification for a multi-objective max–min redundancy allocation problem

In this study, we consider a bi-objective redundancy allocation problem on a series–parallel system with component level redundancy strategy. Our aim is to maximize the minimum subsystem reliability, while minimizing the overall system cost. The Pareto solutions of this problem are found by the augmented ε-constraint approach for small and moderate sized instances. After finding the Pareto solutions, we apply a well known sorting procedure, UTADIS, to categorize the solutions into preference ordered classes, such as A, B, and C. In this procedure, consecutive classes are separated by thresholds determined according to the utility function constructed from reference sets of classes. In redundancy allocation problems, reference sets may contain a small number of solutions (even a single solution). We propose the τ-neighborhood approach to increase the number of references. We perform experiments on some reliability optimization test problems and general test problems.     

A mixed hemivariational–variational problem and applications

We consider an abstract system with Lagrange multipliers which consists of a hemivariational inequality and a variational inequality. The hemivariational inequality is governed by a hemicontinuous, generalized monotone, possibly nonlinear operator as well as by a bilinear form. This bilinear form also governs the variational inequality. We are looking for a pair solution in a subset of a product of two real reflexive Banach spaces. In order to illustrate the applicability of the abstract results, two examples in terms of PDEs are delivered. Each example is related to the weak solvability of a boundary value problem arising in contact mechanics.     

Heuristic and exact algorithms for a min–max selective vehicle routing problem

In this work, we investigate a vehicle routing problem where not all clients need to be visited and the goal is to minimize the longest vehicle route. We propose two exact solution approaches for solving the problem: a Branch-and-cut (BC) algorithm and a Local Branching (LB) method that uses BC as its inner solver. Our computational experience indicates that, in practice, the problem is difficult to solve, mainly when the number of vehicles grows. In addition to the exact methods, we present a heuristic that relies on GRASP and on the resolution of a restricted integer program based on a set covering reformulation for the problem. The heuristic was capable of significantly improving the best solutions provided by BC and LB, in one tenth of the times taken by them to achieve their best upper bounds.     

A simple and effective evolutionary algorithm for the capacitated location–routing problem

This paper proposes a hybrid genetic algorithm (GA) to solve the capacitated location–routing problem. The proposed algorithm follows the standard GA framework using local search procedures in the mutation phase. Computational evaluation was carried out on three sets of benchmark instances from the literature. Results show that, although relatively simple, the proposed algorithm is effective, providing competitive results for benchmark instances within reasonable computing time.     

A posteriori error estimates for combined finite volume–finite element discretizations of reactive transport equations on nonmatching grids

We derive in this paper guaranteed and fully computable a posteriori error estimates for vertex-centered finite-volume-type discretizations of transient linear convection–diffusion–reaction equations. Our estimates enable actual control of the error measured either in the energy norm or in the energy norm augmented by a dual norm of the skew-symmetric part of the differential operator. Lower bounds, global-in-space but local-in-time, are also derived. These lower bounds are fully robust with respect to convection or reaction dominance and the final simulation time in the augmented norm setting. On the basis of the derived estimates, we propose an adaptive algorithm which enables to automatically achieve a user-given relative precision. This algorithm also leads to efficient calculations as it balances the time and space error contributions. As an example, we apply our estimates to the combined finite volume–finite element scheme, including such features as use of mass lumping for the time evolution or reaction terms, of upwind weighting for the convection term, and discretization on nonmatching meshes possibly containing nonconvex and non-star-shaped elements. A collection of numerical experiments illustrates the efficiency of our estimates and the use of the space–time adaptive algorithm.     

Simultaneous determination of the optimal production–inventory and product inspection policies for a deteriorating production system

In this paper, we attempt to find a method for the optimization of production–inventory and product inspection policies for deteriorating production systems. Taking advantage of the nature of a deteriorating production system, a strategy would be not to inspect the first s items of the batch. Therefore, an inspection policy which disregards the first s (DTF-s) items of the batch is proposed. Under the DTF-s policy, we do not inspect the first s produced items but inspect only those items from the (s+1)th till the end of the production run. The objective of this study was the joint determination of the production lot size and the inspection policy s, resulting in a minimization of the expected average cost per unit time. Based on this model, the underlying conditions necessary for the existence of an optimal policy are given. Two commonly used inspection strategies, no inspection and full inspection are discussed. Under both inspection strategies, an optimal production–inventory lot is bounded by the traditional economic quantity. The case of full inspection is shown to be an extension of previously reported results. The option of investing in the process of quality improvement is also discussed. Finally, numerical examples are given to illustrate the method and its advantages in the conclusion.Scope and purposeThis paper considers the relationship between production, inventory and inspection in a deteriorating production system which may transit from the “in-control” state to the “out-of-control” state after a period of operation. Once the transition to the “out-of-control” state has occurred, it is assumed that some percentage of the items produced are defective or of substandard quality. However, in many cases, defects in a defective item can only be identified by an inspection process which carries an inspection cost. Those inspected items which are found to be defective are reworked at some cost before being shipped. On the other hand, defective items which are not inspected will be passed to the customer, incurring a much larger warranty cost. In order to operate such a system economically, tradeoffs among production setup, inventory, inspection and defective cost must be analyzed. Deterioration of the production system is an inherent process in all manufacturing industries. An understanding of the relationship among production, inventory and inspection for such systems will help managers to maintain efficient and economic control of operations.