2010 HAROSA Workshop - Barcelona, Nov. 22-23
Titles & Abstracts
Session 1 - Optimization & Simulation
Chair: Dr. Javier Faulin (Public University of Navarre, Spain)
Title: An ILS to solve a Multiobjective Integrated Distribution Problem
Abstract: The problems arising in the logistics of commercial distribution are complex and involve several players and decision levels. One important decision is the design of the routes to distribute the products, in an efficient and inexpensive way. This article studies a multi-objective multi-period routing model with two objectives. The first one is the minimization of the total distance of the routes and second one is related with strategies that tight relationships with customers, by having the same driver delivered to the same customers along several periods. We propose a metaheuristic based on the Iterated Local Search to solve this problem. Results of the computational experiment are reported.
Title: Modular based Simulation Approach for Analysing and Operating Railway Systems.
Abstract: Simulating railways systems can be of great adavantage to assess policies to deal with incidents effectively and efficiently. For this purpose a library with Witness modules has been created for representing a wide range of systems. Building and exploiting models takes much less time by using this modules than if starting from scratch. Two case studies have been developed. One for the C5 line of the commute system in Madrid, to address a particular type of incident. The second one has been created to obtain schedules for a new line connecting Barajas T4 terminal with Chamartin station, avoiding collisions when lines cross each other.
Title: Sin of Emissions in Freight Transportation: How Operational Research can help.
Abstract: Among various environmental hazards of freight transportation, greenhouse gas emissions is one of major concern. In this talk, I will discuss ways in which emissions can be accounted for in freight transportation planning using mathematical modelling and optimisation. I will describe applications to road and rail-based freight transportation, and present results that shed-light on the tradeoffs between various parameters such as load, speed and total cost, and offer insight on economies of ‘environmental-friendly’ transportation. This talk is based on a number of joint research projects carried out with Gilbert Laporte (HEC Montreal), Teodor G Crainic (University of Quebec in Montreal) and Emrah Demir (PhD student at the University of Southampton).
Title: LOGISPLAN: a solution to the problem of optimizing delivery routes based on genetic algorithms.
Abstract: The optimization of delivery routes is listed as one of the great challenges of the transport companies. Logisplan is software that automates the process of planning the routes and optimize fleet resources. This system is implemented on an optimization engine based on genetic algorithms. In this report we show first, LOGISPLAN system characteristics and on the other hand we show real cases of system implementation in fields as diverse as oil distribution, commercial representation, movement of tourists or urban waste collection. Logisplan is develop entirely by the company Evolution Algorithms sited in Barcelona, Spain.
Session 2 - Scheduling, Modeling & Simulation
Chair: Dr. Felix Mora (ENAC, France)
Title: Scheduling in Parallel Machines with Eligibility and Release and Delivery Times
Abstract: The scheduling problem of parallel machines is very usual in companies. A single operation must be performed on a set of jobs and only needs to be carried out in one of the machines. Processing times of the operation are generally known. In our study, there are some jobs that cannot be done on any machine, which is known as eligibility. Machines, and also jobs, are distributed among levels. A machine at one level can produce jobs in their own level and at a lower level. The processing time of a job is the same for any machine. Furthermore, each job is available at a release time (also called head time) and after the end of the operation a delivery time (also tail time) is necessary. The objective is to find a feasible schedule of minimum completion time. In literature both features have been studied as separated problems, but here they must be considered together.
Title: SATyrus: Logic as a modeling language
Abstract: The modeling of optimization problems in the operations management area is typically performed via the use of mathematical programming tools. Although logic is the reasoning style used by problem modelers, most problem modeling languages are, primarily, algebraic-oriented ones. SATyrus consists of a platform for modeling problems as sets of propositional logic statements, so that they can be solved as pseudo-Boolean constraints satisfaction. This is achieved by expressing viable solutions to a problem in SATish, the SATyrus language, as compacted propositional clauses ranked by violation importance. Together with the goal function, the conjunction of the ranked propositional sentences is then mapped to global optimization with Boolean variables, and solved as an energy minimization problem.
Title: Towards a 3D Representation of a Slap Avalanche
Abstract: The purpose of this presentation is to define the first approximation that allows to model the internal behavior of a slap avalanche phenomena. We use a 2D model to represent the basic behavior of the slap avalanche using GIS data to define the different elements that take part in the calculations. From this first model, that characterize the movement of the snow, we go further in order to define the internal behavior of the snow. To use GIS data in the simulation engine a m:n-ACk cellular automata is used. m:n-ACk is a generalization of the classical cellular automaton allowing the use of different layers in a single cellular automata. We first describe briefly the m:n-ACk cellular automaton structure, describing the GIS data used to define the avalanche model. Some results of the 2D model are presented. Also the firsts steps done to define the internal behavior of the model are shown.
Title: Building Maintenance: A Time-to-Event Approach
Abstract: In this presentation we want, on one hand, to introduce survival analysis techniques for being used in building maintenance and, on the other hand, to apply this methodology for analyzing a large building stock in order to obtain information for maintenance strategies and/or prevention policies. In particular, in this contribution we are interested in describing the time to the event when the event of interest is some damage (or some level of degradation or magnitude) on the building façade. Decisions about intervention in existing buildings are generally based on information gathered from inspections, as a systematic tool for the identification of some injury in buildings. In this sense, in order to carry out an efficient preventive task and maintenance, knowledge of the evolution of injuries and their distribution are essential. However, this information, unfortunately, does not exist and there are few studies that describe the lifecycle of constructive elements in play; so we must use durability estimators based on inspections. After taking into account the censored information coming from inspections, estimates for the non-parametric durability and hazard functions are derived. A simulation study that aims to analyze the accuracy of the proposed estimators will be also presented. The possibilities of the proposed methodology will be illustrated with its application to the building façades in Hospitalet de Llobregat, the second most important city in population in Catalonia (Spain), where more than 14,000 buildings have been analyzed. The analysis of the results allows technicians to detect different zones and levels of intervention to be applied in the city.
Session 3 - Air Traffic Management
Chair: Dr. Antoni Perez (Universitat Oberta de Catalunya, Spain)
Title: European R&D in Air Traffic Management: current directions and new opportunities
Abstract: The European Air Traffic Management (ATM) is a complex system that involves different of stakeholders (i.e. air traffic controllers, airlines, airport operators, ground handlers, etc.) in the safe and efficient operation of flights. The steady growth of traffic imposes a restructuration of the current ATM systems and procedures —which are still based on technologies that date as far back as the 1950s — in order to satisfy the increasing demand whilst always guaranteeing safety. This motivates the Single European Sky ATM Research (SESAR) programme, which has been launched by the European Commission with the objective of developing the next generation ATM system for 2020. Queue management and optimisation processes based on real-time data feeds will allow maximising airport throughput, while the capacity and predictability of the overall system will increase thanks to the collaborative management of user-defined 4D trajectories. Most of these enhancements, which are currently developed and validated by the main stream work of SESAR, are based on the results of the scientific research undertaken in the last decades. A specific Work Package (WP-E) is dedicated to innovative and long term research, with the objective of addressing applications that could become operational beyond 2020, as well as innovative solutions that may have application in the nearer term. This presentation will highlight the relevant activities carried out by ALG in this area, as well as the existing opportunities for financing new collaborative projects, involving academia, industry and research centres.
Title: Advanced Fleet Assignment Problem: Discrete Time Windows, Variable Duration, Preferred Departure Times and Precedence Constraints
Abstract: The Flight Assignment Poblem (FAP) basically consists in assigning planes to a set of scheduled fights without violating any constraints (demand, time-windows, planes' speeds, etc.) This problem has been addressed previoulsy in dif erent manners, and mainly through MIP models. Due to its generality, the problem addressed in this paper can be used not only for planes but also for other means of transport. The approach highly realistic since it considers heterogeneous fleets, multiple discrete windows, time-precedence relationships among trips and variable duration for trips. A MIP model and an Ant Colony Optimization metahuristic have been developed to solve this problem.
Title: Dynamic Allocation of Airport Security Ressources: A Global Optimization Approach
Abstract: In the post 9-11 era, airport security has become worldwide not only a critical issue but also a very costly one for airports as well as for passengers and airlines. Airports have been induced to invest massively in new installations, equipment and workforce to implement the strengthened new security regulations. The cost for the public has been a bitter mix of increased airport taxes, new inconveniences and lengthened time delays. This has influenced negatively air transportation demand levels to airlines. In this communication, the problem of optimizing the allocation of equipments and work teams to control flows of passengers in an airport terminal is considered. The main objective is to minimize the possibility of dangerous situations inside the passenger terminal including dubious passenger being admitted on board an aircraft, but another objective is to insure a minimum quality of service to passengers. Here passenger terminals are represented by passengers and luggage processing machines located on a network whose flows adopt the different available paths between terminal accesses and boarding gates. A characteristic of airport passengers flows is their variability according to the airport flight departure-arrival schedules. This communication introduces a general mesoscopic modelling approach for passenger flows in an airport terminal which should be compatible with the formulation of relevant short term optimization problems for the allocation of available security equipment and staff. The adopted network approach displays the dynamic interdependencies between the different flows and queuing systems while the degree of detail adopted allows the definition and quantification of detailed performance indexes. A global optimization process for scheduling work teams, based on interactive decisions by local units, is proposed and simulation results relative to a medium size case are displayed and discussed.
Special Session - The MIT-Spain university program
Chair: Dr. Angel A. Juan (Universitat Oberta de Catalunya, Spain)
TITLE: The MIT-Spain Program – a powerful internationalization channel
Abstract: The MIT International Science and Technology Initiatives—better known as MISTI—connects MIT students and faculty with research and innovation around the world. MIT's largest international program, MISTI is a pioneer in applied international studies —a distinctively MIT concept. Working closely with a network of premier corporations, universities and research institutes, MISTI matches over 400 MIT students with internships and research abroad each year.
The MIT-Spain Program helps MIT talent find its way to select challenging opportunities in technology, engineering, science, business and innovation in Spain. Host companies and institutions that have hosted MIT talent since 2007, praise MIT students for their motivation, and depth of skills and note how they help lower barriers to their internationalization. Since 2007 (the year of its foundation) MIT‐Spain reached to 250+ MIT students from all courses and academic departments. The program helped 130+ MIT students identify opportunities in science, technology, and business in Spain and contribute to internationalizate companies and institutions. Through the MIT-Spain/La Cambra Seed Fund, 35 collaborations between Spanish companies and research labs and MIT have been unearthed. MIT-Spain remains committed to catalyze growth in the network of host institutions and increase the offering to MIT talent in Spain.
Session 4 - Routing & Location
Chair: Dr. Manel Mateo (Technical University of Catalonia, Spain)
Title: Combining Metaheuristics, Constraint Programming and lagrangean Relaxation to Tackle Routing Problems
Abstract: Among metaheuristics, Variable Neighbourhood Search (VNS) is one of the methods with far less application in routing problems. However, interesting results have been obtained even with the simplest VNS algorithm applied to the CVRP. Constraint Programming (CP) and Lagrangean Relaxation (LR) are two powerful paradigms that may be used separately or embedded into a VNS structure aiming to improve its efficiency. The approach to be presented uses CP and LR to tackle the CVRP, and may be combined with probabilistic constructive heuristics (Randomised Clarke and Wright Savings algorithm - RCWS) in order to improve algorithm’s efficiency and solution’s quality. In any case, the application of this scheme is not restricted to the CVRP, but open to add new side constraints in order to deal with time windows or pick-up and delivery orders. As an example, a CP model for the VRPTW is to be presented. It combines a VRP Library, where constraints are defined, and a search method based on the VNS and random selection.
Title: Optimizing Routes with Safety and Environmental Criteria in Transportation Management in Spain: A Case Study
Abstract: The object of logistic management is to optimise the whole value chain of the distribution of goods and merchandise. One of the main aspects of such an analysis is the optimisation of vehicle routes to deliver final products to customers. There are many algorithms to optimise the related vehicle routing problem. The objective function of that problem usually involves distance, cost, number of vehicles, or profits, among others. In this paper we also take into account safety and environmental costs. Thus, we develop some variants to traditional heuristic algorithms, such as those of Clarke and Wright or Mole and Jameson, in which we include the traditional costs along with safety and environmental cost estimates for real scenarios in Spain. We call this methodology ASEC (Algorithms with Safety and Environmental Criteria). These considerations raise the value of the global objective function, but permit a more realistic cost estimate that includes not only the internal costs involved in the problem but also the related externalities. Finally, we discuss several promising solutions to real case using our new ASEC methodology.
Title: Applying Machine-learning Heuristics to the Vehicle Routing Problem
Abstract: Our research Group, BCN_PCL (BCN Perceptual Computing Lab) involves researchers from several Universities in the neighborhood of Barcelona (UB, UOC, CVC). Our primary research goals are related to Computer Vision and Statistical Pattern Recognition problems. In this talk we will present the main topics we are working on: object recognition, face classification, social signal analysis, advanced medical image analysis and perceptual learning. We will see that many of our applications usually end up in ill-posed optimization problems. Heuristics and approximate optimization algorithms are often applied to find satisfactory solutions. We will end the talk with the introduction of the evolutive computational models, and an application to the VRP. Rather than focusing on finding an approximate solution to the VRP, we will highlight the future research lines and collaboration opportunities that may arise from this field.
Title: European Reference Indicators for Public Facilities and Services: approach to an integrated production in reference values for the basic social services infrastructure
Main author: Dr. Maria-Lluïsa Marsal-Llacuna (Universidad de Girona, Spain)
Abstract: Public services should 'live' in public facilities allocations. According to this, one must fit into the other; in the same way as citizens should find an answer in the residential park offer or production activities seek their location in the industrial areas. This high level of engagement needed is not produced. Services and facilities coexist in an historical isolation. In addition to this, while services are provided by administration, facilities are at proposal of the town plans. In this context, how can they keep a good relationship? How planning guarantees enough land to allocate public services? Of the great range and variety of public services, some of them are recognized in the countries constitutional texts as essential or universal citizen's rights. All State Main Texts of different European Nations protect the right of their citizens to enjoy -at least- a good public education, quality in provision of health services and enough offer in assistance to persons. These services, which could be labeled as 'public basics', are widespread respected and unquestioned, thus an acceptable level must be provided by administrations. This minimum threshold in basic public services should be understood as a common European level, in order to give a reference point to governments for the provision of public services. Basic public services are strictly connected to people because of their essential and universal nature. Services, whose necessity remains unmodified although race, culture, education, nationality, etc. of users’ changes. Their universal nature allows the possibility to express them in values per capita, so indicators are possible and needed. Same thing with facilities; there is a minimum amount of basic public facilities that must be preserved and protected, according to the constitutional texts of European Countries. The service sector includes the public services offer -necessarily located in public sites- and the private one (which corresponds strictly to the tertiary sector), exclusively allocated in private plots and buildings. As a primary explanation of the public-private dual offer we can say that, in general, ‘where the public offer doesn't arrive, the private one does’, understanding the lack of the public sector as a business opportunity for the private one. Also true is that, apart from covering this public services ‘gaps’ (normally concerned with ‘new services’ related to ‘new social needs’), there are -in some services- a duplicity of offers explained by some improvements introduced by the private sector. If the ‘coverage of ‘gaps’ is related to quantity, the dual offer is related mainly to quality and innovation. Here, the private offer an alternative to the obsolete, poor, or badly maintained services, public provided, which do not satisfy some or all citizens. This strong relation between public-private services hides important dangers. In public services provision, administration (normally local governments), develops a social function, guaranteeing -at least- the essential or basic services, the basis of the welfare state. Starting from the most basic ones -related to nets- such as electricity, water, gas, etc. to others –more ‘nodal’-, such as schools, sport fields, hospitals and so on. The aim of the ongoing research is to obtain indicators for basic public services and basic public facilities, all expressed in values per capita and obtained using computational science under the principles of Service Science Management Engineering. A methodology for the equivalence of service and facility indicators will be also obtained. The final step would be the production of ‘basic recommended values’ as European Reference Indicators for Public Facilities and Services.
Session 5 - Calls-for-Projects
Chair: Dr. Alex Grassas (Universitat Rovira i Virgili, Spain)
Title: 7th Framework Programme European Research Projects: 10 tips for proposal preparation
Abstract: In recent years there has been an increase of the funding opportunities for R+D projects in the European framework. This has prompted many organisations to participate and respond to calls of the European Commission Framework Programme, which in turn has increased the competitive level of the calls. Preparing a proposal for a European project is always complex because of the many different aspects to consider and combine. These include not only the scientific matters, but also the alignment with the European Commission scientific policies and priorities, the construction of a solid consortium, the inclusion of a good managerial and financial administration strategy, as well as communication and technology exploitation, amongst others. And once a project is granted, the actual implementation of the project remains a major challenge. This is mainly due to the size and ambition of the endeavour, the research components involved and the international and distributed environment in which projects take place (the consortium). This session will provide some tips on how to build a competitive European research project proposal.
Session 6 - Computational & Management Issues
Chair: Dr. Josep Jorba (Universitat Oberta de Catalunya, Spain)
Title: Availability Issues in Community Computing
Abstract: Many companies and organizations are moving their software to the cloud, which has advantages like the appearance of infinite computing resources, the lack of an up-front investment by cloud users and the ability to pay for use of resources measured in fine grain. However, this creates a relation of absolute dependance on a handful of large companies for a huge amount of users and enterprises. To avoid this we propose the model of community computing, where users contribute their resources to be used collectively. A community computing can be used as a platform to deploy services, as an alternative to large datacenters. This services make it possible to use surplus resources in a general way, while offering some of the most important characteristics of cloud computing. It is a suitable model both for small and medium enterprises and for user communities not interested in making an economic investment for deploying their services and with dependency concerns. In such systems, no guarantees about contributed resources are offered what arises interesting availability issues, e.g. which computers should be used to deploy a service to guarantee its availability during a period of time. We are going to present our current work in community computing and our preliminary work in availability issues in this kind of systems.
Title: SSMED: A new frontier for quali-quantitative research
Abstract: Service Science, Management, Engineering and Design (SSMED) has arisen in the last few years as a new interdisciplinary area where practical research is in bad need. Services are not new as a domain for research, undertaken from several points of view and origins: economics, marketing, operations, psychology, information systems, etc. However, what is now being requested is an effort to address service problems and opportunities with less specialized approaches and more holistic -and thus multidisciplinary- mindsets. The talk will present a comprehensive framework for locating and discussing open research issues within SSMED, as well as their relationships, and for thinking about the various research methods that may fit those gaps.
Title: Teaching the difficulty of Integer Factorization through Distributed Computing
Abstract: Public key cryptography is a building block of many, if not all, security solutions. For that reason, any basic course in cryptography or in computer security must include the teaching of such algorithms. Beyond the mathematical description of the algorithms, it is interesting to perform practical experiments that help students understand the robustness of proposed solutions. In this work we present a project to show the difficulty of integer factorization, which is the basis for the RSA algorithm, the most used public key algorithm nowadays. Integer factorization has subexponential complexity. In order the students can realize that the computing power they need to break short keys is huge and increasing few bits it grows exponentially, we prepared some activities in which they first try to factor big numbers using their computers and, later on, adding their computing power in a collaborative implementation using the BOINC (Berkeley Open Infrastructure for Network Computing) platform. BOINC is a software for volunteer computing that uses a client-server architecture. It provides the infrastructure to distribute and manage the tasks of an application between different clients. It can deal with any parallelized application, but works best with applications that have large sets of independent intensive jobs that require modest memory and storage resources.
Title: Data Mining and Quality in Service Industry: Review and some applications
Abstract: In Service Industry the main goal of Data Mining is to improve the Quality of the interface and the interaction between the organization system and the respective costumers and needs. Now-a-days with the technological advances, a new challenge on exploring data and extrapolating patterns has emerged. Data mining, as an exploratory data analysis tool used in large and complex data sets, allow discovering new snippets of knowledge and patterns in these vast amounts of data, and this is very often crucial on information leading to a higher position, in very competitive markets. In our work we will review some applications of Data Mining in Service Industry and explore some Quality related topics.
Session 7 - VRP Software
Chair: Dr. Daniel Riera (Universitat Oberta de Catalunya, Spain)
Title: Defining "Real-world" Vehicle Routing Problems: An Object-based Approach
Abstract: Much interest is currently being expressed in "Real-world" VRPs. But what are they and how can they be defined? The conventional method of problem formulations for the VRP are rarely extended to deal with many real-world constraints and rapidly become complex and unwieldy as the number and complexity of constraints increases. In Software Engineering practice, complex systems and constraints are commonplace, and the prevailing modelling and programming paradigm is Object-Oriented Programming. This talk will present an OOP model for the VRP and show it's application to some classic VRP variants as well as some real-world problem domains.