Decision Support Systems for Logistic Networks and
Supply Chain Optimization

When and where

When: Monday, December 18, 2006. 10:00-17:00.
Where: CWI, Amsterdam, room M280.
Directions on how to get to CWI.

10:00-10:30	Coffee, Tea
10:30-11:30	Ton de Kok (TU/e)   Supply Chain Planning: Paradigms and Models. Abstract. In this presentation we discuss supply chain planning problems as they occur in reality. Due to the complexity of these real-life problems, mathematical models underlying decision support systems are based on simplifying assumptions. Though this is obvious, the way to simplify is not obvious at all. We discuss two generic alternatives: rolling scheduling and stochastic dynamic programming. We propose a methodology to test the performance of alternative approaches. Based on this methodology we show that both approaches have their strenghts and weaknesses.
11:30-12:00	Peter Bosman, (CWI) Computationally Intelligent Online Dynamic Vehicle Routing by Explicit Load Prediction in an Evolutionary Algorithm. Abstract. In this talk we describe a computationally intelligent approach to solving the dynamic vehicle routing problem where a fleet of vehicles needs to be routed to pick up loads at customers and drop them off at a depot. Loads are introduced online during the actual planning of the routes. The approach described in this paper uses an evolutionary algorithm (EA) as the basis of dynamic optimization. For enhanced performance, not only are currently known loads taken into consideration, also possible future loads are considered. To this end, a probabilistic model is built that describes the behavior of the load announcements. This allows the routing to make informed anticipated moves to customers where loads are expected to arrive shortly. Our approach outperforms not only an EA that only considers currently available loads, it also outperforms a recently proposed enhancedEA that performs anticipated moves but doesn't employ explicit learning. Our final conclusion is that under the assumption that the load distribution over time shows sufficient regularity, this regularity can be learned and exploited explicitly to arrive at a substantial improvement in the final routing efficiency.
12:00-13:00	Lunch
13:00-13:30	Jacob Jan Paulus (UT)   Scheduling with Adjacent Resources. Abstract. In practice, many scheduling problems have additional adjacency requirements on the resources. Whenever parts of such a resource are assigned to a job, these parts have to be adjacent. Examples can be found in berth allocation of ships, scheduling and design of parallel computer processors and check-in desks at airports. In this talk we start by give an intuition of the difficulties imposed by such an adjacency requirement. We indicate both the consequences for practice and theory. For project scheduling with adjacent resources a decomposition method is presented. And more theoratical results on a machine scheduling model, give a formal insight in the complexity. These theoratical results imply that simple heuristic methods for practice will not be succesfull. We conclude with the research challenges that lie ahead.
13:35-14:05	Nico Dellaert (TU/e)   Integral capacity and inventory decision making in a simple production system. Abstract. This paper deals with the integral acquisition of capacity and material in a situation with uncertain demand, with non zero lead-times for the supply of both materials and capacity. Although there is a lot of literature on the time-phased acquisition of capacity and materials, most of this literature focuses on one of the two decisions. By using a dynamic programming formulation, we will describe the optimal balance between using safety stocks and contingent labor force for various lead time situations. We will compare the cost ingredients of the optimal strategy with the standard inventory approach that neglects capacity restrictions in the decision. Next to that, we derive characteristics of the optimal strategy that can provide a thorough basis for operational decision making. Based on work with: S.D.P. Flapper, T.Tan
14:10-14:40	Jarek Byrka (CWI)   An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. Abstract.
14:40-15:05	Coffee, Tea
15:05-15:35	John van den Broek (TU/e)   Timetabling problems at the TU Eindhoven Abstract. The students of the Industrial Design department at the TU Eindhoven are allowed to design part of their curriculum by selecting courses from a huge course pool. They do this by handing in ordered preference lists with their favorite courses for the forthcoming time period. Based on this information (and on many other constraints), the department then assigns courses to students. Until recently, the assignment was computed by human schedulers who used a quite straightforward greedy approach. In 2005, however, the number of students increased substantially, and as a consequence the greedy approach did not yield acceptable results anymore. We present the solution of this real-world timetabling problem: We give a complete mathematical formulation of it, and we explain all the constraints resulting from the situation in Eindhoven. We solve the problem using lexicographical optimization with four subproblems. For all four subproblems, an elegant integer linear programming model is given which easily can be put into CPLEX. Finally, in this talk we describe a computationally intelligent approach to solving the dynamic vehicle routing problem where a fleet of vehicles needs to be routed to pick up loads at customers and drop them off at a depot. Loads are introduced online during the actual planning of the routes. The approach described in this paper uses an evolutionary algorithm (EA) as the basis of dynamic optimization. For enhanced performance, not only are currently known loads taken into consideration, also possible future loads are considered. To this end, a probabilistic model is built that describes the behavior of the load announcements. This allows the routing to make informed anticipated moves to customers where loads are expected to arrive shortly. Our approach outperforms not only an EA that only considers currently available loads, it also outperforms a recently proposed enhanced EA that performs anticipated moves but doesn't employ explicit learning. Our final conclusion is that under the assumption that the load distribution over time shows sufficient regularity, this regularity can be learned and exploited explicitly to arrive at a substantial improvement in the final routing efficiency. We report on our computational experiments and results around the Eindhoven real-world data. Based on work with: Cor Hurkens and Gerhard Woeginger
15:40-16:10	Guido Diepen (UU)   Solving the gate and bus planning at Schiphol Abstract. Between the time an aircraft lands at Schiphol and the moment it departs again a number of tasks have to be taken care of. The most obvious tasks are that the arriving passengers must deboard the plane, while the departing passengers must board the plane. Other tasks include that the aircraft must be cleaned, the waste must be taken out the aircraft, while fresh water and food must be put in the aircraft for the upcoming flight. All of these tasks take place while the aircraft is parked at a so-called stand. Now the gate assignment problem consists of determining where to place which aircraft at Schiphol, while respecting certain constraints (e.g. security rules and feasibility rules). Now when looking at the stands, these can be divided into two categories: Remote stands and gates equipped with a passenger air bridge. Whenever an aircraft is assigned to a remote stand, passengers must be transported to and from the terminal building with buses. The bus planning problem consists of determining for each bus which aircraft it transports passengers to or from. One important thing is that we need to ensure that each bus driver does not work longer than legally allowed. Each day, we solve both of these problems for the upcoming day and for both problems we want a similar type of solution, namely a robust solution. Robust means that on the actual day it self, minor deviations to the planned arrival and departure times do not introduce the need for resolving the complete problems again, but no alterations or only minor alterations to the original solution will be needed. Traditionally these two problems are solved sequentially, meaning that we first solve the gate planning problem and use the resulting output as input for the bus planning problem. We now want to solve these two problems in an integrated fashion, enabling us to have some feed-back from the bus planning to the gate planning (e.g. the need for a lunch break for a bus driver could mean that changing the gate assignment would lead to a better global solution).
16:15-17:00	Rene Sitters (TU/e)   Traveling salesman problem with neighborhoods. Abstract. We give a survey of approximation algorithms for the problem of connecting a collection of subsets of the Euclidean plane by a tour of minimum length.

Organizers: Karen Aardal (CWI, TU/e), Johann Hurink (UT), and Ton de Kok (TU/e)

Participation is for free, and there is no registration.

All further questions to: Karen Aardal