A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands

The multi-compartment vehicle routing problem (MC-VRP) consists of designing transportation routes to satisfy the demands of a set of customers for several products that, because of incompatibility constraints, must be loaded in independent vehicle compartments. Despite its wide practical applicability the MC-VRP has not received much attention in the literature, and the few existing methods assume perfect knowledge of the customer demands, regardless of their stochastic nature. This paper extends the MC-VRP by introducing uncertainty on what it is known as the MC-VRP with stochastic demands (MC-VRPSD). The MC-VRPSD is modeled as a stochastic program with recourse and solved by means of a memetic algorithm. The proposed memetic algorithm couples genetic operators and local search procedures proven to be effective on deterministic routing problems with a novel individual evaluation and reparation strategy that accounts for the stochastic nature of the problem. The algorithm was tested on instances of up to 484 customers, and its results were compared to those obtained by a savings-based heuristic and a memetic algorithm (MA/SCS) for the MC-VRP that uses a spare capacity strategy to handle demand fluctuations. In addition to effectively solve the MC-VRPSD, the proposed MA/SCS also improved 14 best known solutions in a 40-problem testbed for the MC-VRP.     

The distributed permutation flowshop scheduling problem

This paper studies a new generalization of the regular permutation flowshop scheduling problem (PFSP) referred to as the distributed permutation flowshop scheduling problem or DPFSP. Under this generalization, we assume that there are a total of F identical factories or shops, each one with m machines disposed in series. A set of n available jobs have to be distributed among the F factories and then a processing sequence has to be derived for the jobs assigned to each factory. The optimization criterion is the minimization of the maximum completion time or makespan among the factories. This production setting is necessary in today's decentralized and globalized economy where several production centers might be available for a firm. We characterize the DPFSP and propose six different alternative mixed integer linear programming (MILP) models that are carefully and statistically analyzed for performance. We also propose two simple factory assignment rules together with 14 heuristics based on dispatching rules, effective constructive heuristics and variable neighborhood descent methods. A comprehensive computational and statistical analysis is conducted in order to analyze the performance of the proposed methods.     

DEMORS: A hybrid multi-objective optimization algorithm using differential evolution and rough set theory for constrained problems

The aim of this paper is to show how the hybridization of a multi-objective evolutionary algorithm (MOEA) and a local search method based on the use of rough set theory is a viable alternative to obtain a robust algorithm able to solve difficult constrained multi-objective optimization problems at a moderate computational cost. This paper extends a previously published MOEA [Hernández-Díaz AG, Santana-Quintero LV, Coello Coello C, Caballero R, Molina J. A new proposal for multi-objective optimization using differential evolution and rough set theory. In: 2006 genetic and evolutionary computation conference (GECCO’2006). Seattle, Washington, USA: ACM Press; July 2006], which was limited to unconstrained multi-objective optimization problems. Here, the main idea is to use this sort of hybrid approach to approximate the Pareto front of a constrained multi-objective optimization problem while performing a relatively low number of fitness function evaluations. Since in real-world problems the cost of evaluating the objective functions is the most significant, our underlying assumption is that, by aiming to minimize the number of such evaluations, our MOEA can be considered efficient. As in its previous version, our hybrid approach operates in two stages: in the first one, a multi-objective version of differential evolution is used to generate an initial approximation of the Pareto front. Then, in the second stage, rough set theory is used to improve the spread and quality of this initial approximation. To assess the performance of our proposed approach, we adopt, on the one hand, a set of standard bi-objective constrained test problems and, on the other hand, a large real-world problem with eight objective functions and 160 decision variables. The first set of problems are solved performing 10,000 fitness function evaluations, which is a competitive value compared to the number of evaluations previously reported in the specialized literature for such problems. The real-world problem is solved performing 250,000 fitness function evaluations, mainly because of its high dimensionality. Our results are compared with respect to those generated by NSGA-II, which is a MOEA representative of the state-of-the-art in the area.     

A new heuristic to solve the one-warehouse N-retailer problem

We deal with a multi-echelon inventory system in which one warehouse supplies an item to multiple retailers. Customer demand arrives at each retailer at a constant rate. The retailers replenish their inventories from the warehouse that in turn orders from an outside supplier. It is assumed that shortages are not allowed and lead times are negligible. The goal is to determine replenishment policies that minimize the overall cost in the system. We develop a heuristic to compute efficient policies, which also can easily be used in a spreadsheet application. The main idea consists of finding a balance between the replenishment and the inventory holding costs at each installation. This new heuristic we compare with two other approaches proposed in the literature; the computational studies show that in most of the instances generated the new method provides lower costs.     

Optimization of biochemical systems through mathematical programming: Methods and applications

In this work we present a general (mono and multiobjective) optimization framework for the technological improvement of biochemical systems. The starting point of the method is a mathematical model in ordinary differential equations (ODEs) of the investigated system, based on qualitative biological knowledge and quantitative experimental data. In the method we take advantage of the special structural features of a family of ODEs called power-law models to reduce the computational complexity of the optimization program. In this way, the genetic manipulation of a biochemical system to meet a certain biotechnological goal can be expressed as an optimization program with some desired properties such as linearity or convexity.The general method of optimization is presented and discussed in its linear and geometric programming versions. We furthermore illustrate the use of the method by several real case studies. We conclude that the technological improvement of microorganisms can be afforded using the combination of mathematical modelling and optimization. The systematic nature of this approach facilitates the redesign of biochemical systems and makes this a predictive exercise rather than a trial-and-error procedure.     

Min-degree constrained minimum spanning tree problem: New formulation via Miller–Tucker–Zemlin constraints

Given an undirected network with positive edge costs and a positive integer $d>2$, the minimum-degree constrained minimum spanning tree problem is the problem of finding a spanning tree with minimum total cost such that each non-leaf node in the tree has a degree of at least $d$. This problem is new to the literature while the related problem with upper bound constraints on degrees is well studied. Mixed-integer programs proposed for either type of problem is composed, in general, of a tree-defining part and a degree-enforcing part. In our formulation of the minimum-degree constrained minimum spanning tree problem, the tree-defining part is based on the Miller–Tucker–Zemlin constraints while the only earlier paper available in the literature on this problem uses single and multi-commodity flow-based formulations that are well studied for the case of upper degree constraints. We propose a new set of constraints for the degree-enforcing part that lead to significantly better solution times than earlier approaches when used in conjunction with Miller–Tucker–Zemlin constraints.     

Simple procedures of choice in multicriteria problems without precise information about the alternatives’ values

The additive model of multiattribute value theory is widely used in multicriteria choice problems. But often it is not easy to obtain precise values for the scaling weights or the alternatives’ value in each function. Several decision rules which require weaker information, such as ordinal information, have been proposed to select an alternative under these circumstances. We propose new decision rules and test them using Monte-Carlo simulation, considering that there is ordinal information both on the scaling weights and on the alternatives’ values. Results show the new rules constitute a good approximation. We provide guidelines about how to use these rules in a context of selecting a subset of the most promising alternatives, considering the contradictory objectives of keeping a low number of alternatives yet not excluding the best one.     

An experiment for improving students performance in secondary and tertiary education by means of m-learning auto-assessment

Mobile learning is considered an evolution of e-learning that embraces the ubiquitous nature of current computational systems in order to improve teaching and learning. Within this context it is possible to develop mobile applications oriented to learning, but it is also important to assess to what extent such applications actually work. In this paper we present a new tool designed to reinforce students’ knowledge by means of self-assessment. Improvement in student achievement was evaluated and an attitudinal survey was also carried out to measure student attitudes towards this new tool. Three different experimental groups were selected for this research, with students aged from 14 to 21 years old, including high-school and university students. Results show that this kind of tool improves student achievement, especially amongst younger learners, with a relatively low impact on current teaching activities and methodology.     

A parallel direct solver for the self-adaptive hp Finite Element Method

In this paper we present a new parallel multi-frontal direct solver, dedicated for the hp Finite Element Method (hp-FEM). The self-adaptive hp-FEM generates in a fully automatic mode, a sequence of hp-meshes delivering exponential convergence of the error with respect to the number of degrees of freedom (d.o.f.) as well as the CPU time, by performing a sequence of hp refinements starting from an arbitrary initial mesh. The solver constructs an initial elimination tree for an arbitrary initial mesh, and expands the elimination tree each time the mesh is refined. This allows us to keep track of the order of elimination for the solver. The solver also minimizes the memory usage, by de-allocating partial LU factorizations computed during the elimination stage of the solver, and recomputes them for the backward substitution stage, by utilizing only about 10% of the computational time necessary for the original computations. The solver has been tested on 3D Direct Current (DC) borehole resistivity measurement simulations problems. We measure the execution time and memory usage of the solver over a large regular mesh with 1.5 million degrees of freedom as well as on the highly non-regular mesh, generated by the self-adaptive hp$hp$-FEM, with finite elements of various sizes and polynomial orders of approximation varying from p=1$p=1$ to p=9$p=9$. From the presented experiments it follows that the parallel solver scales well up to the maximum number of utilized processors. The limit for the solver scalability is the maximum sequential part of the algorithm: the computations of the partial LU factorizations over the longest path, coming from the root of the elimination tree down to the deepest leaf.