ICAOR 2016 ABSTRACTS

ICAOR 2016 ABSTRACTS

8^TH INTERNATIONAL CONFERENCE ON APPLIED OPERATIONAL RESEARCH

28-30 JUNE 2016, ROTTERDAM, THE NETHERLANDS

PUBLIC TRANSPORT: PLANNING AND REAL-TIME CONTROL

Leo Kroon

Rotterdam School of Management, Erasmus University, Rotterdam, Netherlands

Burgemeester Oudlaan 50, 3062 PA Rotterdam, Netherlands

Abstract. This presentation gives an overview of Operations Research models for improving public transport systems, and of their impact in practice. Relevant elements to be taken into account are the passengers, the infrastructure, the line system and the timetable, the vehicles and the crews. Traditionally, Operations Research models for public transport systems focused mainly on supporting operational planning processes, but currently also real-time control is recognized as a fruitful area for the application of Operations Research models. Especially disruption management is an important topic within real-time control. The application of Operations Research models is supported nowadays by the availability of large amounts of data about the movements of passengers and vehicles, but it is still quite a challenge to use these data effectively.

OPTIMAL CONNECTIONS ON A NETWORK WITH MULTIPLE INTERCHANGEABLE ORIGINS AND MULTIPLE DESTINATIONS

Michael Todinov

Department of Mechanical Engineering and Mathematical Sciences

Oxford Brookes University, Headington Rd, Oxford OX3 0BP, United Kingdom

Abstract. On the basis of counter-examples, it is demonstrated that the time-honoured successive shortest path strategy fails to achieve a minimal total length of the transportation routes on a network with multiple interchangeable origins and multiple destinations. In certain cases the successive shortest path strategy fails to achieve a minimal total length of the transportation routes even for multiple interchangeable origins and a single destination. This is due to the appearance of cyclic paths with dominating flow in one of the directions of traversal called dominated parasitic flow loops. Removing all dominated parasitic flow loops does guarantee a minimal total length of the transportation routes and is the key to developing efficient transportation and communication networks. The probability of existence of dominated parasitic flow loops in networks is surprisingly high and a state where such flow loops are present is the ‘natural state’ of real networks. Accordingly, a new algorithm for eliminating all dominated flow loops in networks has been proposed, based on transforming the initial network into a single source/single sink network connected with the rest of the network through edges with unit capacities, followed by maximising the flow in the transformed network at a minimum cost. In addition, a technique referred to as ‘repeated inversion of the flow of dominated parasitic flow loops’ is proposed and successfully applied to reduce the total length of transportation routes.

A COMPROMISE METHOD FOR SOLVING FUZZY MULTI OBJECTIVE FIXED CHARGE TRANSPORTATION PROBLEM

Ratnesh R. Saxena ¹ and Mudita Upmanyu ²

¹ Department of Mathematics, DDU College, University of Delhi, Karampura, Delhi 110015, India

² Department of Mathematics, Faculty of Mathematical Sciences, University of Delhi, Delhi 110021, India

Abstract. The fixed charge transportation problem is a special case of the traditional fixed charge problem wherein other than the direct costs, a fixed charge is associated when a transportation activity takes place between a source and destination pair-which does not depend on the level of activity. This paper studies a particular form of this problem where there are multiple and conflicting objectives, and when the information provided by the decision maker regarding these fixed charges and the direct cost coefficients in the objective functions is imprecise.

SIMULATION OF RAIL REPLACEMENT BUS SERVICE IN OSLO

Dag Kjenstad, Oddvar Kloster, Kjell Fredrik Pettersen, Morten Smedsrud, Christian Schulz, Patrick Schittekat and Tomas Eric Nordlander

SINTEF ICT, Department of Applied Mathematics, Oslo, Norway

Abstract. This paper describes an applied simulation study on the flow of rail replacement buses in Oslo. We performed the studies using SIMADES, a newly developed multi-agent discrete event simulator. In the project, we enriched the simulator with agents representing entities commonly found in the urban mobility domain. Our study identified the main bottlenecks that limit the flow of buses through the road network under the traditional way of scheduling and dispatching buses. The study furthermore identified the best actions to implement that enable a significant increase of capacity for rail replacement buses. The conclusions are expected to lead to concrete changes in how the rail replacement bus service will be executed in Oslo during planned and unplanned maintenance of the rail network.

REPLACEMENT SERVICES FOR PLANNED MAINTENANCES OF THE INFRASTRUCTURE OF A PUBLIC TRANSPORT SYSTEM

Alexander Kiefer ¹, Michael Schilde ² and Karl F. Doerner ¹

¹ Christian Doppler Laboratory for Efficient Intermodal Transport Operations,

² Department of Business Administration,

University of Vienna, Oskar-Morgenstern-Platz 1, Vienna, Austria

Abstract. This paper deals with planning the replacement services in case of a scheduled maintenance of parts of the infrastructure of a public transport system. The considered maintenances last over a long period, e.g., days or weeks, and involve the blockade of some segments of the affected line. As a consequence, replacement services have to be planned thoroughly. These services typically include the establishment of additional lines and augmented frequencies of some existing lines. For this purpose, a mixed integer programming model is developed. The model is then used to solve a case of the city of Vienna using CPLEX.

REGULARITY PATTERNS FOR ROLLING STOCK ROTATION OPTIMIZATION

Ralf Borndörfer, Boris Grimm, Markus Reuthe, Stanley Schade and Thomas Schlechte

Zuse Institute Berlin, Takustr. 7, D-14195 Berlin, Germany

Abstract. The operation of railways gives rise to many fundamental optimization problems. One of these problems is to cover a given set of timetabled trips by a set of rolling stock rotations. This is well known as the Rolling Stock Rotation Problem (RSRP). Most approaches in the literature focus primarily on modeling and minimizing the operational costs. However, an essential aspect for the industrial application is mostly neglected. As the RSRP follows timetabling and line planning, where periodicity is a highly desired property, it is also desired to carry over periodic structures to rolling stock rotations and following operations. We call this complex requirement regularity. Regularity turns out to be of essential interest, especially in the industrial scenarios that we tackle in cooperation with DB Fernverkehr AG. Moreover, regularity in the context of the RSRP has not been investigated thoroughly in the literature so far. We introduce three regularity patterns to tackle this requirement, namely regular trips, regular turns, and regular handouts. We present a two-stage approach in order to optimize all three regularity patterns. At first, we integrate regularity patterns into an integer programming approach for the minimization of the operational cost of rolling stock rotations. Afterwards regular handouts are computed. These handouts present the rotations of the first stage in the most regular way. Our computational results (i.e., rolling stock rotations evaluated by planners of DB Fernverkehr AG) show that the three regularity patterns and our concept are a valuable and, moreover, an essential contribution to rolling stock rotation optimization.

BENCHMARKING EFFICIENCY OF DELHI TRANSPORT CORPORATION: A DATA ENVELOPMENT ANALYSIS APPROACH

Punita Saxena

Department of Mathematics, Shaheed Rajguru College of Applied Sciences for Women

Vasundhara Enclave, Near Chilla Sports Complex, New Delhi, Delhi 110096, India

Abstract. Transport sector is a very crucial sector for any developing economy. The economic life of a country is dependent largely on this sector. Growing economy leads to more job opportunities and movement of people from rural to urban areas. The urban cities have to optimize their resources to meet the rising needs in terms of available infrastructure and resources. This paper discusses the efficiency of Delhi Transport Corporation (DTC) using the technique of DEA. A data set of 37 State Transport Undertakings of India have been considered for the study. It was observed that DTC is one of the worst performers that need special attention to improve its efficiency amongst its peers. It showed a technical inefficiency of 51.32% and was operating on decreasing returns to scale. It was also observed that DTC needs to decrease its total cost by 19% apart from increasing its increase its output in order to attain the level of efficiency. Regression analysis was performed to identify the explanatory variables for reduction in its total cost.

THE IMPORTANCE OF CONSIDERING PUSHBACK TIME AND ARRIVALS WHEN ROUTING DEPARTURES ON THE GROUND AT AIRPORTS

Christofas Stergianos ¹, Jason Atkin ¹, Patrick Schittekat ², Tomas Eric Nordlander ², Chris Gerada ¹ and Herve Morvan ¹

¹ Institute for Aerospace Technology, The University of Nottingham, Nottingham NG7 2RD United Kingdom

² SINTEF ICT, Department of Applied Mathematics, Oslo, Norway

Abstract. With the constant increase in air traffic, airports are facing capacity problems. Many airports are increasingly interested in utilising optimisation methods for specific airport processes. However, many such processes do happen in parallel, and maximising the potential benefits will require a complex optimisation model. A model which considers multiple processes simultaneously and the detailed complexities of the processes, rather than using more abstract models. This paper investigates how the arriving aircraft can affect the routing process and whether the pushback process can result into different types of delays. Furthermore, aircraft are routed backwards, starting from the destination in order to be at the runway on time and to respect the departure sequence. After testing our model with and without the arriving aircraft we found that arriving aircraft can indeed produce a lot of delays. Such delays would otherwise pass unnoticed as they result to departing aircraft choose different paths or pushback earlier so they be at the runway on time. Having an accurate model for the pushback process is important in order to understand in depth how the pushback process affects the other processes that happen in parallel. Furthermore, it led to more accurate and realistic model, which may assist the decision making process for ground movement operations and thereby help airports increase their capacity and become more environmentally friendly.

A BRANCH-AND-PRICE ALGORITHM FOR DYNAMIC SECTOR CONFIGURATION

Tambet Treimuth ¹, Daniel Delahaye ¹ and Sandra Ulrich Ngueveu ^2,3

¹ French Civil Aviation University (ENAC) F-31400 Toulouse, France

² University of Toulouse, INP, LAAS, F-31400 Toulouse, France

³ CNRS, LAAS, 7 avenue du Colonel Roche, F-31400 Toulouse, France

Abstract. Air traffic generates workload for the air traffic controllers in charge of the airspace. For a large airspace, a single air traffic controller is not able to manage all this workload and the airspace is divided into sectors, each of them being assigned to a controller. When the traffic demand is decreasing during the night, the sectors are gathered together into groups to reduce the number of controllers in operation. Nowadays, this regrouping is performed empirically by airspace experts. In this paper, we show how the branch-and-price method can be used to compute a balanced grouping of air traffic control sectors to optimally reduce the number of controller teams during daily low flow periods.

ROBUST ITINERARY GENERATION FOR DISRUPTION MANAGEMENT IN AIRLIFT OPERATIONS

Udatta S. Palekar and Alok Tiwari

University of Illinois at Urbana-Champaign, Urbana, USA

Abstract. We describe an approach for generating robust itineraries for disruption management in airlift operations. The concept of a robust optimal policy and a robust worst-case itinerary are developed. A polynomial algorithm that calculates both the robust policy and worst-case itinerary for a discretized version of the problem is presented along with preliminary computational results for a small problem.

MULTI OBJECTIVE GATE ASSIGNMENT MODELS FOR INCREASING SHOPPING REVENUES AT AIRPORTS

Gülesin Sena DAŞ

Kırıkkale University, Ankara Yolu 7. Km, 71450 Yahşihan/Kırıkkale, Turkey

Abstract. In this study, multi objective models that aim to increase the shopping revenues at airports are investigated. The aim of the proposed multi objective model is to assign passengers to specific gates near shopping facilities in order to increase shopping revenues at airports. Using the data obtained from previous studies, proposed multi objective models are tested. Results revealed that it is possible to assign more passengers to gates located near to the shopping facilities without increasing passenger walking distances.

HOMECARE PLANNING, A CHALLENGING TASK IN A GROWING MARKET

Tomas Eric Nordlander ¹, Leonardo Lamorgese ¹, Thi Viet Ly Nguyen ² and Roberto Montemanni ²

¹ SINTEF ICT, Department of Applied Mathematics, Oslo, Norway

² Dalle Molle Institute for Artificial Intelligence (IDSIA –USI/SUPSI), Galleria 2, 6928 Manno, Switzerland

Abstract. The homecare services market is large and rapidly growing due to ageing populations and increasingly skewed age demographics. Human resources are the dominant factor simultaneously determining quality of care and driving costs. The planning of homecare services involves allocating personnel among shifts, assigning staff members to patients, routing staff members’ client visits and scheduling treatments. Homecare planning is primarily done manually even though optimisation techniques have aided in solving similar problems in other domains. Efficient homecare planning requires optimisation techniques, but current, related optimisation research suffers from several shortcomings (above all, a lack of integration in handling the different planning sub-problems) and needs certain changes. This paper highlights these shortcomings and suggests approaches to realise the benefits of optimisation techniques in homecare planning.

DYNAMIC APPOINTMENT SCHEDULING WITH PATIENT TIME PREFERENCES AND DIFFERENT SERVICE TIME LENGTHS

Anne Zander and Uta Mohring

Karlsruhe Institute of Technology, Kaiserstr.12, 76131 Karlsruhe, Germany

Abstract. Advance admission scheduling in the field of health care is an important and complex problem. Often, exact models of realistic size cannot be solved due to the curse of dimensionality and heuristics have to be used. In this paper we consider the appointment schedule of a physician’s day. We assume patient types defined by different time preferences and service time lengths. Patient requests for the day are handled directly during a booking horizon. We present a mixed integer linear programming model to determine a set of appointments to offer a patient requesting an appointment. The objective is to schedule the requesting patient while also taking future demand into account. We want to maximize the overall utilization assuring a certain fairness level. We further perform a simulation in order to test the mixed integer linear program and to compare it to simpler online heuristics. We develop different scenarios and show that using the mixed integer linear program to schedule patients is beneficial.

PLANNING THE CAPACITY OF HOSPITAL LIFTS FOR A NEW AMBULATORY BLOCK

Jonathan Wing Cheong Ng ¹ and Carrie Ka Yuk Lin ²

¹ Department of Industrial and Manufacturing Systems Engineering, The University of Hong Kong, Hong Kong, China

² Department of Management Sciences, City University of Hong Kong, Hong Kong, China

Abstract. In a regional acute general public hospital, a new multi-storey ambulatory care block is under construction to accommodate specialty out-patient clinics to meet future growth in patient demand. Hospital lifts play a key role in vertical transportation and are an expensive long-term investment. The building design includes several lift groups each serving different floors and targeting user groups in the new ambulatory block. The main objective of this study is to decide on the capacity in terms of number of lifts needed in each group. Statistical forecasting provides demand estimates for comparison with projected figures from staff. A simulation model is developed to study the performance of different capacities under three demand scenarios to find the right level of service in terms of lift waiting time performance. Sensitivity analysis of the capacities has provided comprehensive information for multiple stakeholders, including the Hospital Authority Head Office, hospital management and the building contractor, to finalize the capacity decision which would have a long-term impact on service quality and cost.

CHALLENGES AND EXPERIENCE IN SOLVING INDUSTRIAL OPTIMISATION PROBLEMS

Tomas Eric Nordlander

SINTEF ICT, Department of Applied Mathematics, Oslo, Norway

Abstract. The approach to solving industrial optimisation problems differs greatly to approaches to academic optimisation problems in the research community. SINTEF Optimisation has worked in both of these areas for more than 20 years, working on basic research projects funded by grants and on developing optimisation engines for software vendors or for end-users. I will talk about our experience in customer contacts, business models, intellectual property, contract negotiation, expectation management, and different kinds of support. There are compromises to be made and various points to consider, depending on whether you work with applied, applicable, or stylized and theoretical problems. I will also share thoughts considerations we often made on the simplification and limitations of models, the choice of solution methods, verification and validation, dealing with uncertainty, etc.. Working in applied industrial optimisation has some very positive sides, but also some aspects of it are, in some way, counterproductive to general objectives of optimisation research. In this talk, I want to share our experience at SINTEF Optimisation on this topic.

PACKING REGULARITY OF PERMUTATION CODES

János Barta ¹, Roberto Montemanni ¹ and Derek H. Smith ²

¹ Dalle Molle Institute for Artificial Intelligence (IDSIA – USI/SUPSI), Galleria 2, 6928 Manno, Switzerland

² Division of Mathematics and Statistics, University of South Wales, Pontypridd, CF37 1DL, Wales, UK

Abstract. Permutation codes have been extensively investigated, both because of their intrinsic mathematical interest and because of relevant applications based on error-correcting codes. The Maximum Permutation Code Problem (MPCP) is a challenging packing problem on permutations. The objective is to maximize the size of permutation codes with a given minimum Hamming distance between the codewords. In a similar way to the well-known sphere packing problem, an optimal permutation packing usually has a highly regular structure. In this paper a new idea of regularity degree of permutation codes is developed and the relationship between packing density and regularity degree of permutation codes is investigated. Computational experiments on random permutation packings run on different MPCPs confirm that, analogously to the sphere packing problem, the regularity degree of permutation codes tends to increase as the code size approaches to the optimum.

FINANCING A PRIVATELY OWNED HOME: A TIME ORIENTED RISK ANALYSIS OF COMBINED SAVING AND FINANCING

Ursula Walther ¹ and Thomas Burkhardt ²

¹ Berlin School of Economics and Law, Badensche Straße 52, 10825 Berlin, Germany

² Universität Koblenz-Landau, Universitätsstr. 1, 56070 Koblenz, Germany

Abstract. Financing a privately owned home is often the major financial goal a private household pursues. Typically, the process consists of a savings period followed by the debt amortization. We propose a six variable model to analyze the nature of the process’ interest rate risk, which depends materially on the amount of equity used and the loan terms, in particular fixed interest periods. Historical simulations reveal risk profiles and sensitivities of different strategies. Our study distinguishes from related work by focusing on the time span needed to reach the goal. This realistically reflects the situation of households with income restrictions. Thus, we contribute to a broader and more reasonable understanding of financial risk.

SIMULATION ANALYSIS OF OPERATIONAL CONTROL DECISIONS IN SEMICONDUCTOR WAFER FABRICATION

Pyung-Hoi Koo, Min-Jung Park and Shie-Gheun Koh

Department of Systems Management & Engineering, Pukyong National University, 45 Yongsoro, Namgu, Busan, South Korea

Abstract. This paper examines operational control decisions in a semiconductor wafer fabrication line, including lot release control, dispatching and batch loading. In most previous works, these control problems have been considered separately. In this paper, we consider these problems at the same time, and present new control rules for bottleneck stations, non-bottleneck stations and batch processing stations, respectively. Simulation experiments are carried out to examine the performance of the control rules. Some insights on the performance of the control policies are discussed.

SINGLE MACHINE SCHEDULING WITH TWO AGENTS FOR TOTAL COMPLETION TIME OBJECTIVES

Yuvraj Gajpal and Hongwei Li

Asper School of Business, University of Manitoba, Winnipeg, Manitoba R3T 5V4 Canada

Abstract. This paper proposes heuristics for the single machine scheduling problem, in which two agents are considered. A set of jobs is involved in each agent and processed by only one processing resource. The objective is to minimize the total completion time of jobs in the first agent subject to an upper bound on the total completion time of the jobs for second agent. We propose two heuristics motivated by the shortest processing time (SPT) first rule to solve this problem. For evaluating the performance of proposed heuristics, numerical experiment is performed on randomly generated problem instances. We use the optimal algorithm from existing literature to evaluate the performance of proposed heuristics for small problems up to 20 jobs. We also used bigger problem instances up to 150 jobs to evaluate the performance of heuristics.

STUDENT RANKING BY MEANS OF NON-LINEAR MATHEMATICAL OPTIMIZATION OF PARTICIPATION MARKS

A. van der Merwe, J.V. du Toit and H.A. Kruger

North-West University, Potchefstroom Campus, Potchefstroom, South Africa

Abstract. Ranking students according to their growing participation marks could encourage them to develop self-motivational attitudes toward their academic progress. This paper describes the ranking of students by means of a non-linear mathematical optimization model. The model uses optimization techniques to find the best weights for calculating students’ participation marks, effectively eliminating manual evaluation of all possible equations. The optimal weights are used to calculate the average participation marks and the students are ranked accordingly.

NATURAL RESOURCE EXTRACTION WITH PRODUCTION TARGET: THE REAL OPTION VALUE OF VARIABLE EXTRACTION RATE

Wen Chen, Nicolas Langrené and Tanya Tarnopolskaya

The Commonwealth Scientific and Industrial Research Organisation, Australia

Abstract. We consider the problem faced by mining companies to adjust their extraction rate over time in order to meet the production targets from a real option perspective. The idea of using real option approach to optimize mining operations in response to metal price uncertainty is not new: as early as 1985, Brennan & Schwarz proposed a simple, stylized model to quantify the value of temporarily closing, or even abandoning, mines as a response to a drop in metal price. Though mathematically elegant, this approach was never embraced by mine managers. We decide to make two major modifications to Brennan & Schwarz framework to make it more appealing to industry. Firstly, we assume that the mining companies set a fixed production target for a given time frame as part of their strategic planning. Secondly, instead of a binary all-or-nothing choice for the production rate, we assume that it can vary on a finer grid of production regimes, allowing for smaller adjustments over time. The extraction rate is constrained by the planned target, but remains flexible around a certain base rate. Due to the uncertainty in commodity prices in the financial market, this flexibility to adjust the production rate has its value. We formulate this resource extraction problem as a multi-regime constrained stochastic control problem. We solve this problem numerically using an extension of the simulation-based Least-Squares Monte Carlo algorithm.