Forskning – NORS

Det norske forskningsmiljøet for operasjonsanalyse er veldig aktivt. På EURO-konferansen som nylig ble arrangert, ble Norge representert av 28 ulike forfattere og 19 bidrag. Følgende abstrakter oppsummerer noe av det det norske forskningsmiljøet for operasjonsanalyse har å tilby.

ABSTRAKTER

Fra forfattere med norsk tilknytning på EURO XXVIII, Poznan, Polen, 3. – 6. juli 2016.

Keynote – Optimization of Maritime Transportation

Marielle Christiansen

In this tutorial, we will give a short introduction to the shipping industry and an overview of some OR-focused planning problems within maritime transportation. Examples from several real ship routing and scheduling cases, elements of models and solution methods will be given. Finally, we present some trends regarding future developments and use of OR-based decision support systems for ship routing and scheduling.

MRI Block Scheduling at a Norwegian Hospital

Anders N. Gullhav, Marielle Christiansen, Bjørn Nygreen, Mats M. Aarlott, Jon Erik Medhus

The process of scheduling patients to MRI (magnetic resonance imaging) scanners at hospitals is typically done in multiple stages. On a tactical decision making level, the hospital in this study develops a block schedule that is used as a guide in the appointment scheduling on the operational level. The block schedule is a weekly recurring schedule that specifies an assignment of patient groups, which is defined according to medical characteristics, to the different heterogeneous MRI scanners at different time slots during a week. The block schedule must satisfy various technical and staffng requirements, such as change of coils and available personnel. In this work, we suggest using mathematical programming to create appropriate block schedules, and propose a mixed integer linear programming (MILP) formulation of the problem. The MILP is solved using a commercial solver on test data obtained from a major Norwegian hospital.

Crowdshipping in PDPTW – Effects of Different Compensation Schemes

Lars Dahle, Marielle Christiansen, Henrik Andersson

The concept of crowdshipping, where ordinary people handle some transportation requests for a company, is at its early stages. This gives rise to an interesting new variant of the Pickup and Delivery Problem with Time Windows (PDPTW), where companies not only use their own vehicles to service transportation requests, but also take advantage of ordinary people already on the road to handle some of their requests. As transportation can be a significant cost for last-mile and same-day pickup and delivery, studying the potential savings of using crowdshipping is an important task. The literature is scarce regarding crowdshipping in routing problems. In this article, we introduce the PDPTW with Occasional Drivers, and study the effect of different compensation schemes for how to compensate occasional drivers. We allow an occasional vehicle to handle multiple requests and model the preferences of a driver using threshold values.

Integrating Timetabling and Crew Scheduling at a Freight Railway Operator

Twan Dollevoet, Lukas Bach, Dennis Huisman

The planning process at a freight railway operator is commonly decomposed into three phases. First, a timetable is constructed for the trains; then, engines are assigned to all trains in the timetable and finally, duties are generated for the crew members. This paper focuses on the crew scheduling phase. Usually, a fixed timetable and engine schedule are used as input for the crew scheduling problem. We observed a low utilization in the engine schedules. As a consequence, many different optimal, and near-optimal, solutions exist for the first planning phases. We exploit these alternative solutions, by leaving some of the timetable decisions open for adjustment when scheduling the crew. When doing so, we make sure that the engine schedules remain feasible. In particular, we fix the order of tasks in each individual engine schedule, but allow to adjust the exact timing of these tasks when scheduling the crew. We have implemented a heuristic branch-and-price algorithm to solve this model. In the master problem, the timetable is determined and a suitable set of duties is selected. In the pricing problem, new crew duties are generated. The pricing problem is modeled as a set of resource-constrained shortest-path problems, which can be solved in parallel. We have performed an empirical study on cases from a European freight operator and show that costs can be significantly reduced in comparison to a purely sequential approach.

The Dynamics of Global Offshore Oil Production

Onur Özgün, Bent Erik Bakken

Offshore oil has represented most of global oil production growth the 1970s. Despite its relatively high cost, high oil prices has provided conditions for the growth of offshore oil. However, depletion of off- shore reserves, dropping oil prices and emerging unconventional extraction technologies, the future of offshore oil may not be as bright. We present a system dynamics model that given a scenario for global oil demand, endogenously creates production capacities of conventional onshore, unconventional onshore and offshore oil as a result of short-term and long-term dynamics. The short-term imbalance between supply and delay is compensated by adjustments in capacity utilization. In the longer term, any sustained rise in oil prices creates investments, which increases capacity after a delay. Differences in the behaviours of three types of oil are created as a result of differences in costs, investment responses and initial conditions. The model also considers the effects of learning and reserve depletion on the costs of oil production for three categories of oil. The effects of strategic policies of OPEC countries and political conflicts on capacity utilization can also be directly introduced as an external input. Validation runs closely mimics historical mix between the three oil sectors. This model is used for strategic planning in the oil sector to analyse the effects of different cost, reserve and strategy scenarios on the future of oil production.

Congestion Management in a Stochastic Dispatch Model for Electricity Markets

Endre Bjorndal, Mette Bjørndal, Kjetil Midthun, Golbon Zakeri

We discuss the design of electricity markets with stochastic dispatch. Our discussion is based on a model framework similar to that in (Pritchard et al. 2010) and (Morales et al. 2014), where an electricity market with two sequential market clearings is used. The stochastic market clearing is compared to the (standard) myopic market model in a small example, where wind power generation is uncertain. We examine how changes in market design influence the effciency of the stochastic dispatch. In particular, we relax the network flow constraints when clearing the day ahead market. We also relax the balancing constraints when clearing the day ahead market to see if this additional flexibility can be valuable to the system.

MRI Block Scheduling at a Norwegian Hospital

Anders N. Gullhav, Marielle Christiansen, Bjørn Nygreen, Mats M. Aarlott, Jon Erik Medhus

Dealing with uncertainty in a maritime inventory routing problem

Filipe Rodrigues, Agostinho Agra, Marielle Christiansen, Lars Magnus Hvattum

We consider a single product maritime inventory routing problem in which the production and consumption rates are constant over the planning horizon. The problem involves a heterogeneous fleet and multiple production and consumption ports with limited storage capacity. Maritime transportation is characterized by high levels of uncertainty. The weather conditions are the principal uncertainty source since they have a great impact on sailing times. In this paper, uncertainty in sailing times is analyzed according to three different approaches: deterministic, robust and stochastic. In the deterministic approach, where sailing times are assumed known and fixed, safety stocks are considered to account for uncertainty. In the robust approach, the sailing times are assumed to belong to the well-known budget uncertainty polytope. In the stochastic approach, the sailing times are assumed to follow a log-logistic distribution. For each approach a mathematical formulation is proposed. The two last approaches assume two stages of decisions where the routing and the order the ports are visited, as well as the quantities to load/unload, are fixed before the uncertainty is revealed, while the visit time to ports can be adjusted to the scenario. To solve these two approaches, decomposition algorithms based on separation schemes are used. A computational comparison of the three approaches, in terms of the solution structure and costs, is presented.

Investments in Shipping Capacity under Uncertainty: Maximizing the Rate of Return

Giovanni Pantuso, Ove Mørch, Kjetil Fagerholt, Jørgen Glomvik Rakke

Decisions regarding investments in shipping capacity expansion or renewal require taking into account both the operating fitness and the financial performance of the investment. However, while several operating requirements have been considered in the operations research literature, the corresponding financial aspects have not received as much attention. In addition, investors in ships need to face the uncommonly high uncertainty affecting the maritime business. We present a stochastic programming model for the renewal of shipping capacity. The new model maximizes the Average Internal Rate of Return (AIRR). Maximizing the AIRR sets stricter return requirements on money expenditures than classic profit maximization models and may describe more closely shipping investors’ preferences. We illustrate how the resulting nonlinear model can be linearized to ease computation. Based on data from a major liner shipping company, worldwide leader in the transportation of rolling equipment, we compare the AIRR maximization model with a profit maximization model. Results show that while maximizing profits results in aggressive expansions of the fleet, maximizing the return provides more balanced renewal strategies which may be preferable to most shipping investors.

Optimizing simulation parameters for stochastic empty container repositioning

Massimo Di Francesco, Alexei Gaivoronski, Paola Zuddas

We face the stochastic empty container repositioning by a discrete event simulation model, which is based on lower and upper inventory thresholds at each port. We look for the inventory thresholds optimizing the average system performance with respect to all observations of random parameters entering the system description in each period of the planning horizon. These random parameters are the net supply of empty containers at ports, ship loading and unloading times and transport capacities. The optimal values of these thresholds are determined by an optimization algorithm, which belongs to the family of stochastic gradient methods.

A Conic Optimization Model for Replicated Data Stores in Geo-distributed Cloud Applications

Julio Góez, Juan F. Pérez

We consider a software application provider that serves a set of geographically distributed users by exploiting cloud resources. The application relies heavily on data as it provides its users with a service to access content via a set of channels, a service that must comply with a certain quality of service (QoS). In fact, data replication is implemented to ensure both availability and QoS. The application provider must decide where to locate and how to replicate the data, considering costs, QoS, and traffc patterns. The goal is to find the deployment of minimum cost, subject to quality constraints, defined in terms of the application response times. For this problem we introduce a mixed integer non-linear optimization model and show that it can be reformulated as an equivalent mixed integer second order cone optimization problem. We find that in many of our test instances CPLEX reaches the time limit without determining if the problem has a solution. To circumvent this issue we develop a feasibility test that also allows the derivation of an initial feasible solution for the problem.

On Symmetry, Breaks Within Double Rounds and the South American World Cup Qualifiers to Russia 2018

Mario Guajardo, Guillermo Durán, Denis Saure

In July 2015, Ronaldo and Forlán drew balls from two pots to define the schedule of the South American World Cup Qualifiers to the 2018 football World Cup Russia. One pot contained the names of the ten national teams that participate in this qualification tournament. The other pot contained ten numbers referring to the position that each team would take in a predefined schedule template. We generated this schedule template by using integer programming. We included criteria such as symmetry and breaks within double rounds. This talk reports on several symmetric formats we considered as alternative to meet these criteria. We also compare our finally adopted solution against a previous schedule that was used in the four previous World Cup qualifiers.

Consensus based siting of wind power (ConSite Wind)

Frank Hanssen, Roel May

Norway’s campaign for expanded wind energy production cause increased pressure on Norwegian wilderness areas. Emerging construction projects demand improved planning and decision support tools. The Norwegian Institute for Nature Research (NINA) is developing a Spatial Multi-Criteria Decision Analysis tool (SMCDA) for siting of onshore wind-power named ConSite Wind (Consensus Based Siting). ConSite Wind aims to secure stakeholder participation, conflict reduction, re-examination and improved decision making. The tool is structured into the operational steps of a classical SMCDA: Problem structuring (dialogue meetings), value functions (fuzzy logic normalization), weight assessment (AHP), aggregation (WLC/OWA) and sensitivity analysis. All criteria maps are normalized into conflict maps according to the stakeholders/experts degree of acceptance ranging from 0 (low conflict) to 1 (high conflict). Siting options in low-medium conflict areas is finally outlined and evaluated according to the areas overall suitability. ConSite Wind has great inter-disciplinary synergies and addresses the societal demands for transparency and democracy in public decision making. This was emphasized by the EU Commission DGE Environment at the Geospatial World Forum in Rotterdam in 2013. ConSiteWind is currently implemented in conflict zoning and siting of wind-power plants in Lithuania.

Applied OR at SINTEF

Geir Hasle

SINTEF is a Norwegian cross-disciplinary contract research institute that aims at bridging the gap between academia and industry. OR activities are found in many organizational units. In this talk, I will present examples of OR activities in the Group of Optimization, Department of Applied Mathematics. Examples include logistics simulation and optimization in railway and bus transportation, air traffc management, vehicle routing, and healthcare.

Statistical analysis of randomization in adaptive large neighborhood search

Lars Magnus Hvattum, Ahmad Hemmati

Randomization is common in many metaheuristics, and is typically a main ingredient when considering adaptive large neighborhood search (ALNS). We consider a standard implementation of ALNS for maritime pickup and delivery problems, identify seven randomized components in that implementation, and propose and analyze simple nonrandomized alternatives to those components. The results reveal that for one out of seven components, the randomized alternative performs slightly better. The deterministic alternatives perform better for one component, while the randomized and deterministic alternatives have similar performance for the remaining five components. There seems to be a larger variance in the results obtained with only randomized components, compared to the results with only deterministic components, even though the average results are similar. Much of the randomization typically found in implementations of ALNS therefore seems redundant.

A Comparison of Acceptance Criteria for the Adaptive Large Neighbourhood Search Metaheuristic

Alberto Santini, Stefan Ropke, Lars Magnus Hvattum

The adaptive large neighbourhood search (ALNS) metaheuristic has become a popular template for implementing heuristic solution methods. The metaheuristic allows the use of problem specific knowledge when specifying operators for partially destroying and then repairing a solution to an optimisation problem. Problem independent components of the ALNS dictate how different destroy and repair operators should be used and control the search trajectory. One presumably important component that influences the search trajectory is the move acceptance criterion. In the original ALNS, this criterion was based on simulated annealing, whereas earlier work on large neighbourhood search by Shaw had accepted only improved solutions. Recently, some implementations have used the record-to-record acceptance criterion instead. Currently, however, there are no guidelines available to recommend one acceptance criterion over another. This paper intends to fill this gap by investigating a large number of different move acceptance criteria by subjecting them to extensive computational testing. Through empirical experiments we will attempt to 1) suggest which move acceptance criterion is better suited for an implementation of ALNS, 2) quantify the effect on performance from using different acceptance criteria, 3) attempt to measure in which way the move acceptance criteria influence the search behaviour.

Homecare planning, a challenging optimization task.

Tomas Eric Nordlander, Leonardo Lamorgese

The planning of homecare services is a complex process that involves: 1) allocating personnel among shifts, 2) assigning staff members to patients, 3) routing staff visits and 4) scheduling treatments while considering, for example, required competences, patient and caregiver preferences, labour laws, union regulations, organisational policies and temporal precedence of activities within a limited budget. 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 and optimised homecare can deliver significant savings for municipalities, regions and hospitals. From the patient’s perspective, higher-quality homecare services provide higher living standards. Improved service quality results in better treatments (assignment of staff members with the appropriate competences), higher continuity of care (less rotation of staff members for the same patient) and fulfilment of patient preferences. More effcient homecare services allow treating more patients at home, which patients indicate is their preferred place of care. However, homecare planning is still mostly performed manually. Researchers need to address the integrated optimisation problem to obtain effcient, global solutions. Existing research has focused on planning on the operational level, but attention also needs to be placed on the strategic and tactical levels.

Time-indexed formulations for airport runway scheduling

Pasquale Avella, Maurizio Boccia, Carlo Mannino, Igor Vasiliev

Air traffc management typically consists of the coordinated solution of three distinct problems: The Departure Management Problem (DMAN), the Arrival Management Problem (AMAN) and the Surface Management Problem (SMAN). The DMAN problem decides take-off times for each departing flight, whereas AMAN focuses on landing times of arrival flights. Finally, the SMAN Problem decides how arriving and departing airplanes move in the airdrome. Even though in principle the three problems are tightly connected and should be solved jointly, it is common practice of the airport management to handle them independently. In this work we present a time-indexed formulation for AMAN, DMAN and their integration, ADMAN (Arrival and Departure MANagement), exploiting the relation with a classical scheduling problem, namely, the single machine problem with sequence dependent setup times. Starting from a time-indexed formulation recently proposed for single machine scheduling problems with sequence dependent setup times and release dates, we present a compact reformulation based on new families of clique inequalities, leading to significantly better lower hounds. We report on preliminary computational results on real and realistic instances, validating the effectiveness of the proposed approach.

Dynamic Input-Output Modeling of North Dakota’s Economy: A System Dynamics Approach

David Wheat

Building on previous work (Wheat & Pawluczuk, Economics and Management, 4, 2014), this paper extends the integration of two approaches to economic modeling—input-output tables and system dynamics – to develop a multi-industry dynamic model of the economy of North Dakota in the United States. The original model’s structure has been modified to achieve a more robust representation of production constraints originating in inter-industry supply chains and in interstate labor markets. The model is being developed for policy planning by state government offcials in a shale-oil-based regional economy shaken by the collapse of world oil prices. Integration of the two modeling methods extends the applicability and value of input-output analysis by eliminating static assumptions of fixed technology, fixed combinations of labor and capital, fixed prices, and infinite supplies of factors of production. Moreover, integration provides a disciplined way to disaggregate system dynamics models to a level of inter-industry detail that is needed for economic impact studies of regions and small nations. In North Dakota, the model will be useful for modeling oil price scenarios and projecting workforce supply and demand, interstate labor migration, social infrastructure requirements, and other economic development issues. Later versions of the model will include structured representations of policy options to address state officials’ concerns.