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.
Several families of objective functions for the PRV problem (minimizing the variation in the rate at which different products are produced on an assembly line) are formalized, relationships between them are established and it is demonstrated that, in very general conditions, they can be optimized by solving an assignment problem or a polynomially bounded sequence of assignment problems.
This note establishes a connection between two problems that appear in different contexts: the Product Rate Variation (PRV) problem (sequencing units in a mixed-model assembly line in order to maximize the regularity of the sequence with regard to the output of units) and the apportionment problem. This allows us to apply to the PRV problem the properties of the apportionment problem and known procedures for solving it, and suggests alternative approaches to the former problem.
Sequencing units on an assembly line in order to obtain a regular requirement of resources is a problem that can be modelled in a variety of ways. One of the most popular is known as the Monden problem, and the heuristic proposed to obtain a ‘satisfactory’ solution is called ‘goal-chasing’ ethod. In the paper the myopic behaviour of this heuristic is shown, and some improvements are proposed. An exact procedure, based on BDP, is also proposed. By relaxing the assumptions, the BDP procedure becomes a new, powerful heuristic. A sample of computational results is included.
The different varieties of a particular article for widespread consumption are characterized by the material used and its length. Each material is acquired in jumbos of a particular length. By cutting them, we must obtain for each production period at least as many items for each variety as are required to cover consumption for the following period; anything above this value will be used in later periods. In order to minimize the cost associated with this process (that of offcuts plus the inventory holding cost), procedures combining ILP with heuristics based on dynamic programming have been designed; these heuristics have been applied to the daily resolution of the industrial problem.