Adaptive approach heuristics for the generalized assignment problem

The Generalized Assignment Problem consists in assigning a setof tasks to a set of agents with minimum cost. Each agent hasa limited amount of a single resource and each task must beassigned to one and only one agent, requiring a certain amountof the resource of the agent. We present new metaheuristics forthe generalized assignment problem based on hybrid approaches.One metaheuristic is a MAX-MIN Ant System (MMAS), an improvedversion of the Ant System, which was recently proposed byStutzle and Hoos to combinatorial optimization problems, and itcan be seen has an adaptive sampling algorithm that takes inconsideration the experience gathered in earlier iterations ofthe algorithm. Moreover, the latter heuristic is combined withlocal search and tabu search heuristics to improve the search.A greedy randomized adaptive search heuristic (GRASP) is alsoproposed. Several neighborhoods are studied, including one basedon ejection chains that produces good moves withoutincreasing the computational effort. We present computationalresults of the comparative performance, followed by concludingremarks and ideas on future research in generalized assignmentrelated problems.

Driver scheduling problem modelling

The Drivers Scheduling Problem (DSP) consists of selecting a set of duties for vehicle drivers, for example buses, trains, plane or boat drivers or pilots, for the transportation of passengers or goods. This is a complex problem because it involves several constraints related to labour and company rules and can also present different evaluation criteria and objectives. Being able to develop an adequate model for this problem that can represent the real problem as close as possible is an important research area.The main objective of this research work is to present new mathematical models to the DSP problem that represent all the complexity of the drivers scheduling problem, and also demonstrate that the solutions of these models can be easily implemented in real situations. This issue has been recognized by several authors and as important problem in Public Transportation. The most well-known and general formulation for the DSP is a Set Partition/Set Covering Model (SPP/SCP). However, to a large extend these models simplify some of the specific business aspects and issues of real problems. This makes it difficult to use these models as automatic planning systems because the schedules obtained must be modified manually to be implemented in real situations. Based on extensive passenger transportation experience in bus companies in Portugal, we propose new alternative models to formulate the DSP problem. These models are also based on Set Partitioning/Covering Models; however, they take into account the bus operator issues and the perspective opinions and environment of the user.We follow the steps of the Operations Research Methodology which consist of: Identify the Problem; Understand the System; Formulate a Mathematical Model; Verify the Model; Select the Best Alternative; Present the Results of theAnalysis and Implement and Evaluate. All the processes are done with close participation and involvement of the final users from different transportation companies. The planner s opinion and main criticisms are used to improve the proposed model in a continuous enrichment process. The final objective is to have a model that can be incorporated into an information system to be used as an automatic tool to produce driver schedules. Therefore, the criteria for evaluating the models is the capacity to generate real and useful schedules that can be implemented without many manual adjustments or modifications. We have considered the following as measures of the quality of the model: simplicity, solution quality and applicability. We tested the alternative models with a set of real data obtained from several different transportation companies and analyzed the optimal schedules obtained with respect to the applicability of the solution to the real situation. To do this, the schedules were analyzed by the planners to determine their quality and applicability. The main result of this work is the proposition of new mathematical models for the DSP that better represent the realities of the passenger transportation operators and lead to better schedules that can be implemented directly in real situations.

The struggle against creative accounting: Is "true and fair view" part of the problem or part of the solution?

Creative accounting is a growing issue of interest in Spain. In this article we argue that the concept true and fair view can limit or promote the use of creative accounting depending upon its interpretation. We review the range of meanings that true and fair view can take at an international level and compare the experience of the United Kingdom with the Australian one by analysing the use of true and fair view to limit creative accounting. Finally, we suggest lines of action to be considered by the Spanish accounting standards-setting institutions.

A new chance-constrained maximum capture location problem

The paper presents a new model based on the basic Maximum Capture model,MAXCAP. The New Chance Constrained Maximum Capture modelintroduces astochastic threshold constraint, which recognises the fact that a facilitycan be open only if a minimum level of demand is captured. A metaheuristicbased on MAX MIN ANT system and TABU search procedure is presented tosolve the model. This is the first time that the MAX MIN ANT system isadapted to solve a location problem. Computational experience and anapplication to 55 node network are also presented.

Integration of high-resolution geophysical data for the characterization of alluvial aquifers : new approaches and implications for hydrological predictions

Abstract Accurate characterization of the spatial distribution of hydrological properties in heterogeneous aquifers at a range of scales is a key prerequisite for reliable modeling of subsurface contaminant transport, and is essential for designing effective and cost-efficient groundwater management and remediation strategies. To this end, high-resolution geophysical methods have shown significant potential to bridge a critical gap in subsurface resolution and coverage between traditional hydrological measurement techniques such as borehole log/core analyses and tracer or pumping tests. An important and still largely unresolved issue, however, is how to best quantitatively integrate geophysical data into a characterization study in order to estimate the spatial distribution of one or more pertinent hydrological parameters, thus improving hydrological predictions. Recognizing the importance of this issue, the aim of the research presented in this thesis was to first develop a strategy for the assimilation of several types of hydrogeophysical data having varying degrees of resolution, subsurface coverage, and sensitivity to the hydrologic parameter of interest. In this regard a novel simulated annealing (SA)-based conditional simulation approach was developed and then tested in its ability to generate realizations of porosity given crosshole ground-penetrating radar (GPR) and neutron porosity log data. This was done successfully for both synthetic and field data sets. A subsequent issue that needed to be addressed involved assessing the potential benefits and implications of the resulting porosity realizations in terms of groundwater flow and contaminant transport. This was investigated synthetically assuming first that the relationship between porosity and hydraulic conductivity was well-defined. Then, the relationship was itself investigated in the context of a calibration procedure using hypothetical tracer test data. Essentially, the relationship best predicting the observed tracer test measurements was determined given the geophysically derived porosity structure. Both of these investigations showed that the SA-based approach, in general, allows much more reliable hydrological predictions than other more elementary techniques considered. Further, the developed calibration procedure was seen to be very effective, even at the scale of tomographic resolution, for predictions of transport. This also held true at locations within the aquifer where only geophysical data were available. This is significant because the acquisition of hydrological tracer test measurements is clearly more complicated and expensive than the acquisition of geophysical measurements. Although the above methodologies were tested using porosity logs and GPR data, the findings are expected to remain valid for a large number of pertinent combinations of geophysical and borehole log data of comparable resolution and sensitivity to the hydrological target parameter. Moreover, the obtained results allow us to have confidence for future developments in integration methodologies for geophysical and hydrological data to improve the 3-D estimation of hydrological properties.

Inventory-routing model, for a multi-period problem with stochastic and deterministic demand

The need for integration in the supply chain management leads us to considerthe coordination of two logistic planning functions: transportation andinventory. The coordination of these activities can be an extremely importantsource of competitive advantage in the supply chain management. The battle forcost reduction can pass through the equilibrium of transportation versusinventory managing costs. In this work, we study the specific case of aninventory-routing problem for a week planning period with different types ofdemand. A heuristic methodology, based on the Iterated Local Search, isproposed to solve the Multi-Period Inventory Routing Problem with stochasticand deterministic demand.

The donor problem

Donors often rely on local intermediaries to deliver benefits to target beneficiaries. Each selected recipient observes if the intermediary under-delivers to them, so they serve as natural monitors. However, they may withhold complaints when feeling unentitled or grateful to the intermediary for selecting them. Furthermore, the intermediary may distort selection (e.g. by picking richer recipients who feel less entitled) to reduce complaints. We design an experimental game representing the donor s problem. In one treatment, the intermediary selects recipients. In the other, selection is random - as by an uninformed donor. In our data, random selection dominates delegation of the selection task to the intermediary. Selection distortions are similar, but intermediaries embezzle more when they have selection power and (correctly) expect fewer complaints.

A simple optimised search heuristic for the job-shop scheduling problem

This paper presents a simple Optimised Search Heuristic for the Job Shop Scheduling problem that combines a GRASP heuristic with a branch-and-bound algorithm. The proposed method is compared with similar approaches and leads to better results in terms of solution quality and computing times.

Metaheuristics for the bus-driver scheduling problem

We present new metaheuristics for solving real crew scheduling problemsin a public transportation bus company. Since the crews of thesecompanies are drivers, we will designate the problem by the bus-driverscheduling problem. Crew scheduling problems are well known and severalmathematical programming based techniques have been proposed to solvethem, in particular using the set-covering formulation. However, inpractice, there exists the need for improvement in terms of computationalefficiency and capacity of solving large-scale instances. Moreover, thereal bus-driver scheduling problems that we consider can present variantaspects of the set covering, as for example a different objectivefunction, implying that alternative solutions methods have to bedeveloped. We propose metaheuristics based on the following approaches:GRASP (greedy randomized adaptive search procedure), tabu search andgenetic algorithms. These metaheuristics also present some innovationfeatures based on and genetic algorithms. These metaheuristics alsopresent some innovation features based on the structure of the crewscheduling problem, that guide the search efficiently and able them tofind good solutions. Some of these new features can also be applied inthe development of heuristics to other combinatorial optimizationproblems. A summary of computational results with real-data problems ispresented.

Adaptive dynamics and the implementation problem with complete information

This paper studies the equilibrating process of several implementationmechanisms using naive adaptive dynamics. We show that the dynamics convergeand are stable, for the canonical mechanism of implementation in Nash equilibrium.In this way we cast some doubt on the criticism of ``complexity'' commonlyused against this mechanism. For mechanisms that use more refined equilibrium concepts,the dynamics converge but are not stable. Some papers in the literatureon implementation with refined equilibrium concepts have claimed that themechanisms they propose are ``simple'' and implement ``everything'' (incontrast with the canonical mechanism). The fact that some of these ``simple''mechanisms have unstable equilibria suggests that these statements shouldbe interpreted with some caution.

Development of a system for 3D high-resolution seismic reflection profiling on lakes

A high-resolution three-dimensional (3D) seismic reflection system for small-scale targets in lacustrine settings has been developed. Its main characteristics include navigation and shot-triggering software that fires the seismic source at regular distance intervals (max. error of 0.25 m) with real-time control on navigation using differential GPS (Global Positioning System). Receiver positions are accurately calculated (error < 0.20 m) with the aid of GPS antennas attached to the end of each of three 24-channel streamers. Two telescopic booms hold the streamers at a distance of 7.5 m from each other. With a receiver spacing of 2.5 m, the bin dimension is 1.25 m in inline and 3.75 m in crossline direction. To test the system, we conducted a 3D survey of about 1 km(2) in Lake Geneva, Switzerland, over a complex fault zone. A 5-m shot spacing resulted in a nominal fold of 6. A double-chamber bubble-cancelling 15/15 in(3) air gun (40-650 Hz) operated at 80 bars and 1 m depth gave a signal penetration of 300 m below water bottom and a best vertical resolution of 1.1 m. Processing followed a conventional scheme, but had to be adapted to the high sampling rates, and our unconventional navigation data needed conversion to industry standards. The high-quality data enabled us to construct maps of seismic horizons and fault surfaces in three dimensions. The system proves to be well adapted to investigate complex structures by providing non-aliased images of reflectors with dips up to 30 degrees.

Taking "Galton's problem" Seriously : Towards a Theory of Policy Diffusion

This article builds on the recent policy diffusion literature and attempts to overcome one of its major problems, namely the lack of a coherent theoretical framework. The literature defines policy diffusion as a process where policy choices are interdependent, and identifies several diffusion mechanisms that specify the link between the policy choices of the various actors. As these mechanisms are grounded in different theories, theoretical accounts of diffusion currently have little internal coherence. In this article we put forward an expected-utility model of policy change that is able to subsume all the diffusion mechanisms. We argue that the expected utility of a policy depends on both its effectiveness and the payoffs it yields, and we show that the various diffusion mechanisms operate by altering these two parameters. Each mechanism affects one of the two parameters, and does so in distinct ways. To account for aggregate patterns of diffusion, we embed our model in a simple threshold model of diffusion. Given the high complexity of the process that results, strong analytical conclusions on aggregate patterns cannot be drawn without more extensive analysis which is beyond the scope of this article. However, preliminary considerations indicate that a wide range of diffusion processes may exist and that convergence is only one possible outcome.