Bas den Heijer (Ortec)
5 February 2016
Engineering Highway Node Routing
Abstract:
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.
Abstract:
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
Abstract:
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
Abstract:
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
Abstract:
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.
References
[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
Abstract:
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
Abstract:
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
Abstract:
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
Abstract:
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.
Florian Arnold (University of Antwerp)
16 September 2016
Generating problem-specific knowledge (for the Vehicle Routing Problem)
Abstract:
The Vehicle Routing Problem (VRP) is probably the most-studied problem in Operations Research. However, in the race for faster algorithms and better solutions, few research has been performed to shed light on the problem itself. Even though problem specific knowledge is an important ingredient in the design of heuristics, such knowledge is rare for the VRP. As an example, it is proven that in the Traveling Salesman Problem does no optimal solution contain intersecting edges. Even though such a statement is not true for the VRP, it should be possible to deduct general guidelines such as: "In general, solutions can be improved by removing intersections". In this presentations, we take a first step in this direction and use data mining techniques to identify properties that distinguish optimal from non-optimal solutions. Those properties describe the geometrical nature and relations of routes. We combine them with instance characteristics to derive findings that are independent of the specific problem instance. With the help of a classification learner we are able to predict with a relatively high percentage from the defined properties whether a certain solution for any instance is optimal or not. Moreover, we extract rules that explain why a solution is not optimal. Finally, we demonstrate how these rules can be used in the design of heuristics. We implement a local search technique that uses a rule-database to determine the most-promising moves in each step.
Corinne Luteyn (Centre for Industrial Management/Traffic & Infrastructure, KU Leuven)
23 September 2016
Improving an Incomplete Road Network by small Arc Changes
Abstract:
In most Routing Problems, it is assumed that the considered road network is complete and fixed. However, in practice, this is usually not the case. Most existing road networks are, for example, incomplete, since there is no direct connection between each pair of locations. In this research, the possibility to improve an incomplete road network by some small arc changes is investigated. Three possible changes are studied in this research: (re-)opening pedestrian zones for vehicles, widening existing roads and converting existing roads into one-way roads with a higher speed. Different procedures are proposed to find the best improvement such that the total travel time of the vehicles on the network is minimized. This improvement can be the best single change or the best set of changes given a budget constraint. The first procedure combines a construction part and an analysis part with a testing stage. During the construction part, routes for the vehicles are constructed in the existing network using a fast Variable Neighborhood Search. In the second part of the heuristic, the constructed routes are analyzed heuristically in order to determine a good improvement for the network. Since the selected improvements in a set can interfere with each other, the determined improvement is tested during the testing stage. The second approach is an Adaptive Large Neighborhood Search of which the main structure is based on a Simulated Annealing algorithm. New solutions are generated by a large neighborhood, which consists of a set of destroy and a set of repair methods. To test the proposed procedure, 32 benchmark instances are constructed from a real road network. These benchmark instances have one up to four vehicles available to serve 20 up to 150 customers. Based on the experiments on these test networks can be concluded that improving an incomplete road network by a single change leads in average to a reduction in travel time of about 1.5%. Furthermore, if the network is improved by a set of changes given a budget allowing a combination of around three improvements, the average reduction is about 5%.
Harwin de Vries (Erasmus School of Economics)
7 October 2016
Optimizing Population Screening for Infectious: The Case of HAT Disease Control in D.R. Congo
Abstract:
Population screening by mobile units is crucial to control several infectious diseases. We consider the following planning problem: given a set of populations at risk, the expected evolution of the epidemic in these populations, and a fixed number of mobile units, which villages should be screened when? We present descriptive models for the development of the burden of disease over time which take screening explicitly into account, use these to develop planning policies, and numerically analyze them in the context of the control of sleeping sickness (HAT) in D.R. Congo.
Charlie Ye (Erasmus School of Economics)
21 October 2016
Participation behavior and social welfare in repeated task allocations
Abstract:
Task allocation problems have focused on achieving one-shot optimality. In practice, many task allocation problems are of repeated nature, where the allocation outcome of previous rounds may influence the participation of agents in subsequent rounds, and consequently, the quality of the allocations in the long term. We investigate how allocation influences agents' decision to participate using prospect theory, and simulate how agents' participation affects the system's long term social welfare. We compare two task allocation algorithms in this study, one only considering optimality in terms of costs and the other considering optimality in terms of primarily fairness and secondarily costs. The simulation results demonstrate that fairness incentivizes agents to keep participating and consequently leads to a higher social welfare.
Maaike Hoogeboom (VU Amsterdam)
4 November 2016
The Vehicle Routing Problem with arrival time diversification
Abstract:
Cash in Transit (CIT) companies deliver valuable goods to banks, ATMs and stores. Legal regulations and security considerations force these companies to take various measures to protect their valuable cargo against attacks. Driving varying routes to serve their customers is one key strategy to lower the risk of an attack. In this research, we want to generate sufficiently unpredictable routes by varying the arrival time at a customer, while minimizing transportation costs. We present a novel solution approach, by removing previous arrival time slots at customers from the solution space. This results in a routing problem with multiple time windows in which the customers are still available for service. The problem is solved using a rolling horizon framework by taking into account previous arrival times at the customers. Since waiting time at a customer is not allowed due to safety reasons, an efficient method is proposed to check if a route is feasible. An iterated tabu search is used to solve the routing problem and the proposed solution approach is tested on benchmark instances from the literature. We were able to find new best solutions for all but one instance and we study the trade-off between arrival time diversification and transportation cost.
Rolf van Lieshout (Erasmus School of Economics)
2 December 2017
The Vehicle Rescheduling Problem with Retiming
Abstract:
When a vehicle breaks down in a transportation system, the remaining vehicles can be rescheduled to minimize the impact of the breakdown. In this paper, we discuss the vehicle rescheduling problem with retiming (VRSPRT). To incorporate delays, we expand the recovery network with retiming possibilities. As the network gets too large, we propose an iterative neighborhood exploration heuristic to solve the VRSPRT. Experiments show that by delaying one or two trips with on average 4 minutes, we can decrease the average number of cancelled trips with 30 percent.