Schedule seminars spring 2016

Venue: H10-31
Time: 12:00

Bas den Heijer (Ortec) 

5 February 2016

Engineering Highway Node Routing


Highway Node Routing (HNR) is a clever algorithm that exploits typical structures in road networks to make extremely quick shortest path queries possible. Like most of us in OR we need a lot of shortest paths at ORTEC, so we've implemented this algorithm and use it with great enthusiasm! While you lunch I'll explain how the algorithm works and mix the explanation of the theory with some crafty programming tricks by the authors to save running time and memory in practice.

Frans de Ruiter (Tilburg University)

12 February 2016

Duality in Two-stage Adaptive Linear Optimization: Faster Computation and Stronger Bounds.


During this talk we show how to derive and exploit duality in general two-stage adaptive linear optimization models. The equivalent dualized formulation we derive is again a two-stage adaptive linear optimization model. Therefore, all existing solution approaches for two-stage adaptive models can be used to solve or approximate the dual formulation. The new dualized model differs from the primal formulation in its dimension and uses a different description of the uncertainty set. The optimal primal affine policy can be directly obtained from the optimal affine policy in the dual formulation. We provide empirical evidence that the dualized model, in the context of two-stage lot-sizing on a network and two-stage facility location problems, solves an order of magnitude faster than the primal formulation with affine policies. We also provide an explanation and associated empirical evidence that offer insight on which characteristics of the dualized formulation make computations faster. Furthermore, the affine policy of the dual formulations can be used to provide stronger lower bounds on the optimality of affine policies. At the end of the talk we will discuss some potential future research directions based on this dualized formulation for adaptive optimization problems.

This research is based on joint work with Dimitris Bertsimas (MIT).

Daniele Vigo (DEI - Alma Mater Università di Bologna)

18 February 2016

Optimization of real-world collection, treatment and disposal of waste


Waste management is a crucial activity which absorbs huge resources and involves complex organizational problems. We review the main characteristics of the collection and disposal of waste, both of municipal and industrial origin, with special attention to the optimization problems and their practical solution. We consider both strategic problems, consisting in the design of treatment and disposal network of plants, the operational allocation of waste flows to plants and the design of collection areas and routes.

Thijs van der Klauw

26 February 2016

Scheduling Problems in Residential Demandside Management for Future Smart Energy Solutions


Our energy system is rapidly evolving. Part of this evolution is caused by a drive towards small-scale renewable energy generation (e.g., rooftop photovoltaic) and electrification of our energy supply (e.g., e-mobility). These changes greatly increase the stress on our energy supply infrastructure, which was designed and build several decades ago. To reduce stress on critical network assets by, e.g., better matching local supply and demand of energy, we consider residential demandside management. In this talk we first consider the challenges in (residential) electricity distribution grids. We then consider devices that can offer flexibility in their time and amount of energy consumption, e.g., electric vehicles, heat pumps, and so-called smart appliances. We present a methodology to coordinate the scheduling of the flexibility offered by the various devices in a residential neighbourhood. Finally, we show that this methodology is capable of greatly reducing the stress on our energy supply network.

Jelke van Hoorn (VU Amsterdam and Ortec)

11 March 2016

Finding all optimal solutions for the job shop scheduling problem


In [1] we described a dynamic programming algorithm to solve the job shop scheduling problem. We improved this algorithm by adding bounds. We will shortly present these results. We create an algorithm based on this dynamic programming algorithm to find all optimal solutions. For almost all small benchmark instances we were able to find all optimal instances. We will see that the number of optimal instances over differs quite a lot over the different instances.

[1] Gromicho, J., van Hoorn, J., Saldanha da Gama, F., Timmer, G.; Solving the job-shop scheduling problem optimally by dynamic programming; Computers and Operations Research (2012); doi:10.1016/j.cor.2012.02.024.1

Rutger Kerkkamp (Econometric Institute, EUR)

29 April 2016

Two-echelon supply chain coordination under information asymmetry


Consider a two-echelon supply chain with a supplier and a retailer under the classical economic order quantity (EOQ) setting. We assume that both the supplier and the retailer want to minimise their own costs, without taking the other party into consideration. In particular, they do not strive for perfect (centralised) supply chain coordination. Coordination is also hindered by the asymmetric power relation between the supplier and the retailer. The retailer has the market power to force the supplier to satisfy the retailer's ordering policy. However, by offering a contract the supplier can persuade the retailer to change his policy. This leads to an optimisation problem for the supplier to determine a contract that is accepted by the retailer and that minimises his own costs. If the retailer shares his cost parameters with the supplier, the resulting optimisation problem is straightforward to solve. We consider the case where the retailer keeps his holding costs private. Hence, there is information asymmetry. In this case, the supplier has to design an optimal menu of contracts from which the retailer can choose. We show how to solve this problem efficiently and provide structural properties of the optimal solution.

Arturo E. Pérez Rivera (University of Twente)

20 May 2016

Anticipatory freight consolidation in intermodal networks using approximate dynamic programming


We study the planning problem of transporting freights that have different characteristics, in an intermodal network, over a multi-period horizon. Although freights and their characteristics become known gradually over time, there is probabilistic knowledge about them. The goal is to use this knowledge and balance current and future costs, in order to minimize the total costs over the planning horizon. To model and optimize this tradeoff, we propose a Markov Decision Process (MDP) model and an Approximate Dynamic Programming (ADP) approach. We show the benefits and difficulties of our look-ahead approach, under different problem settings and compared to other planning approaches.

Evelot Duizer (Erasmus University Rotterdam)

3 June 2016

The most efficient critical vaccination coverage and its equivalence with maximizing the herd effect  


In infectious disease epidemiology the severity of an infectious disease is often expressed in terms of the reproduction ratio R, related to the initial growth rate of infected individuals, and the final size (the eventual number of people that have become infected). Although the two measures are related, there is no obvious connection between minimization of the two. In this paper we establish a connection between these measures. We show that for the threshold R = 1 the introduction of the disease in a population does not result in an outbreak. `Critical vaccination coverages' are vaccination allocations that result in this threshold. To find the most efficient critical vaccination coverage, we define the following optimization problem: minimize the required amount of vaccines to obtain R=1. We prove that this optimization problem is equivalent to maximizing the proportion of susceptibles that escape infection during an epidemic, i.e., maximizing the herd effect. This herd effect is directly related to the final size of an outbreak. We propose an efficient general algorithm to solve these optimization problems based on Perron-Frobenius theory. We study two special cases that provide further insight into these optimization problems. Finally, we apply our solutions in a case study for pre-pandemic vaccination in the initial phase of an influenza pandemic. The results show that for the optimal allocation the critical vaccination coverage is achieved for a much smaller amount of vaccines as compared to allocations proposed previously.

Harilaos Psaraftis (Technical University of Denmark)

30 June 2016

Speed optimization for green maritime transportation


Among the spectrum of logistics – based measures for green maritime transportation, in this talk we discuss speed optimization. This involves the selection of an appropriate speed by the vessel, so as to optimize a certain objective.  As ship speed is not fixed, depressed shipping markets and/or high fuel prices induce slow steaming which is being practised in many sectors of the shipping industry. In recent years the environmental dimension of slow steaming has also become important, as ship emissions are directly proportional to fuel burned. Win-win solutions are sought, but they will not necessarily be possible. We present some basics, discuss the main trade-offs and also examine combined speed and route optimization problems.  We finally present some examples so as to highlight the main issues that are at play.  


Remy Spliet
Room: 11-05 
Phone: 010-4081342