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.

The crew-scheduling module in the GIST system

The public transportation is gaining importance every year basically duethe population growth, environmental policies and, route and streetcongestion. Too able an efficient management of all the resources relatedto public transportation, several techniques from different areas are beingapplied and several projects in Transportation Planning Systems, indifferent countries, are being developed. In this work, we present theGIST Planning Transportation Systems, a Portuguese project involving twouniversities and six public transportation companies. We describe indetail one of the most relevant modules of this project, the crew-scheduling module. The crew-scheduling module is based on the application of meta-heuristics, in particular GRASP, tabu search and geneticalgorithm to solve the bus-driver-scheduling problem. The metaheuristicshave been successfully incorporated in the GIST Planning TransportationSystems and are actually used by several companies.

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.

Compliment de les directrius DRIVER dels repositoris cooperatius RACO, RECERCAT i TDX

Aquest informe ha estat elaborat per encàrrec del Consorci de Biblioteques Universitàries de Catalunya (CBUC). El seu objectiu és comprovar si des del punt de vista tècnic, els repositoris cooperatius que el CBUC coordina juntament amb el Centre de Supercomputació de Catalunya (CESCA), es poden integrar dins la infrastructura DRIVER.

Control de instrumentos mediante el bus GPIB programado con MATLAB

El proyecto que se expone a continuación está dedicado al control de instrumentos mediante el bus de instrumentación GPIB programado con el software Matlab. Está dividido en dos partes. La primera, será llevada a cabo en el laboratorio de docencia y el objetivo será controlar el osciloscopio y el generador de funciones. Como ejemplo del control realizado se desarrollará una aplicación que permitirá obtener el diagrama de Bode de módulo de cualquier sistema electrónico. La segunda parte será llevada a cabo en el laboratorio de investigación y el objetivo será controlar el analizador de semiconductores. En este caso, la aplicación desarrollada permitirá la realización de medidas para la caracterización de transistores. Las aplicaciones de ambas partes estarán realizadas mediante una interfaz gráfica de usuario diseñada con la herramienta GUIDE de Matlab.

Tractament de dades i geolocalització: proper bus Barcelona

Desenvolupament d'una aplicació per a mòbils Android que permeti conèixer les parades de bus més properes i el temps que falta perquè arribi cada línia de bus, mitjançant la geolocalització de l'usuari, un mapa de parades o un codi QR. Obtenció i tractament de les dades de parades i línies, així com obtenció en temps real de les properes arribades mitjançant "web scraping" (simulació de navegació d'un usuari per extreure dades dels webs) de les pàgines dels operadors.

Driver costs in small firms: Empirical analysis for farms

The agricultural sector has always been characterized by a predominance of small firms. International competition and the consequent need for restraining costs are permanent challenges for farms. This paper performs an empirical investigation of cost behavior in agriculture using panel data analysis. Our results show that transactions caused by complexity influence farm costs with opposite effects for specific and indirect costs. While transactions allow economies of scale in specific costs, they significantly increase indirect costs. However, the main driver for farm costs is volume. In addition, important differences exist for small and big farms, since transactional variables significantly influence the former but not the latter. While sophisticated management tools, such ABC, could provide only limited complementary useful information but no essential allocation bases for farms, they seem inappropriate for small farms

Driver costs in small firms: Empirical analysis for farms

The agricultural sector has always been characterized by a predominance of small firms. International competition and the consequent need for restraining costs are permanent challenges for farms. This paper performs an empirical investigation of cost behavior in agriculture using panel data analysis. Our results show that transactions caused by complexity influence farm costs with opposite effects for specific and indirect costs. While transactions allow economies of scale in specific costs, they significantly increase indirect costs. However, the main driver for farm costs is volume. In addition, important differences exist for small and big farms, since transactional variables significantly influence the former but not the latter. While sophisticated management tools, such ABC, could provide only limited complementary useful information but no essential allocation bases for farms, they seem inappropriate for small farms

Demand and revenue implications of an integrated public transport policy: the case of Madrid

One of the most popular options for promoting public transport use is the provision of an integrated and high quality public transport system. This was the strategy adopted by the regional government in Madrid in 1986 and since then public transport patronage has increased by more than 50%. This paper has two objectives. The first is to identify the factors underlying the significant increase in the demand for public transport in Madrid. To do this we estimate an aggregate demand function for bus and underground trips, which allows us to obtain the demand elasticities with respect to the main attributes of public transport services and also to calculate the long-term impact of changes in those explanatory variables on patronage. The second objective is to evaluate the impact on revenue derived from the introduction of the travel card scheme, and to discuss the consequences on revenue of changes in the relative fare levels of different types of ticket without substantially affecting patronage. This latter issue is addressed by estimating a matrix of own and cross-price elasticities for different ticket types.

Disseny de drivers per a targes de transmissió de senyals

L'objectiu del projecte és poder configurar dues targetes que s'instal∙laran al Sincrotró ALBA. Per a això s'ha desenvolupat un driver per a Linux i una interfície gràfica (GUI). Com a introducció a les targetes, la memòria descriu el Sincrotró, i més específicament el sistema de sincronització (timing) on aquestes s'utilitzaran. També descriu el disseny dels drivers per a Linux2.6 i de la GUI, escrita utilitzant el llenguatge Python amb el framework Qt. Finalment, a la memòria s'exposen els problemes i solucions trobats durant la fase de validació del correcte funcionament de les plaques i dels diferents components del projecte.

Construcció d’un microrobot

Treball de recerca realitzat per un alumne d’ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit científic del Jovent l’any 2006. La construcció d'un microrobot autònom capaç de realitzar una funció per ell mateix, ha permès exposar una introducció en el món de l'electrònica i la mecànica pràctiques. Es tracta d’un microrobot rastrejador: capaç de seguir una línia pintada al terra, per mitjà d'unes entrades (sensors detectors de llum), una lògica (C.I. operacionals) i uns motors motrius comandats per mitjà d'un C.I. driver. S’adjunten imatges dels resultats.

Learning from Shocks and the Decision to Open

Two claims pervade the literature on the political economy of market reforms: that economic crises cause reforms; and that crises matter because they bring into question the validity of the economic model held to be responsible for them. Economic crises are said to spur a process of learning that is conducive to the abandonment of failing models and to the adoption of successful models. But although these claims have become the conventional wisdom, they have been hardly tested empirically due to the lack of agreement on what constitutes a crisis and to difficulties in measuring learning from them. I propose a model of rational learning from experience and apply it to the decision to open the economy. Using data from 1964 through 1990, I show that learning from the 1982 debt crisis was relevant to the first wave of adoption of an export promotion strategy, but learning was conditional on the high variability of economic outcomes in countries that opened up to trade. Learning was also symbolic in that the sheer number of other countries that liberalized was a more important driver of others’ decisions to follow suit.

Modelo de comunicación basado en el estándar AMBA AHB

Amb aquest projecte es presenta un model de comunicacions basat en ARM AMBA AHB, escrit en SystemC i dissenyat per a utilitzar-se en qualsevol sistema que necessiti una solució per a les seves comunicacions. Amb aquest objectiu s'escriu de manera que es llancin els seus processos com a processos "threads" i així puguin ser programats des del codi utilitari per mitjà de variables compartides. Per assegurar el correcte funcionament, inicialment es prova en un bus AMBA AHB complet per, un cop comprovat el compliment de l'estàndard, provar-ho en un codi que realitzi el càlcul de la transposició de matrius.

Sistema de comunicació sense fils utilitzant Zigbee per PDA

En aquest projecte es presenta el disseny i desenvolupament d'un conjunt d'interfícies per a un sistema de comunicació basat en l'estàndard Zigbee. El sistema està composat per una tarja que integra el mòdul Zigbee, un microcontrolador i una FPGA, que es vol controlar des d'un sistema Pocket PC a través del port SD. La implementació consta d’un driver SDIO per Windows CE 4.2, el controlador SDIO a la FPGA i l'enllaç de comunicació entre la FPGA i el microcontrolador.

Análisis y diseño de un procesador RISC simple para adquisición y proceso de datos

Aquest projecte té com a objectiu l'anàlisi de prestacions de processadors RISC de baix cost i el disseny d'un processador RISC simple per a aplicacions de propòsit general relacionades amb l'adquisició i el procés simple de dades. Com a resultat es presenta el processador SR3C de 32 bits i arquitectura RISC. Aquest processador s'ha descrit i simulat mitjançant el llenguatge de descripció de hardware VHDL i s'ha sintetitzat en una FPGA. El processador està preparat per poder utilitzar-se en SoCs reals gràcies al compliment de l'estàndard de busos Wishbone. A més també es pot utilitzar com plataforma educativa gràcies a l'essamblador i simulador desenvolupats.