Workshop scheduling and public transportation on May 31
On Tuesday, May 31, we organize a workshop at Utrecht University on the occasion of the PhD-defense of Roel van den Broek the next morning.
We consider the Train Unit Shunting Problem (TUSP) extended with service task scheduling and train driver assignment. The problem consists of matching train units arriving on a railway hub to departing trains, scheduling service tasks such as cleaning and maintenance on the available resources, and shunting the trains to nearby shunting yards in order to park them on the available tracks.
In this talk, we will discuss a solution method combining local search and list scheduling policies that covers all aspects of the shunting and scheduling problem.
Disruptions are inevitable in railway operations. For instance, in the Netherlands, there are on average about 11 disruptions per day resulting in cancelled trains. A combination of disruptions can result in a so-called out-of-control situation, where there is hardly any train traffic and passenger information is either incorrect or missing at all. Unfortunately, these situations happened a few times in the Netherlands during the last decade.
In this talk, we will discuss new, decentralized approaches to either prevent or deal with such out-of-control situations.
We consider the parallel stack loading problem (PSLP) with the objective to minimize the number of reshuffles in the retrieval stage. Since in the PSLP the incoming items have to be stored according to a fixed arrival sequence, some reshuffles cannot be avoided later on. We study two surrogate objective functions (number of unordered stackings, number of badly placed items) to estimate the number of reshuffles and compare them theoretically as well as in a computational study. For this purpose, MIP formulations and a simulated annealing algorithm are proposed.
Scheduling refers to making timing decisions for a set of activities to be executed, and usually also entails the allocation of scarce resources to those activities. A very diverse set of industrial processes may be modelled, such as jobs visiting machines in a workshop, airplanes using a runway at an airport, or construction activities performed by workers at a building site. In practice, a number of the key parameters of these decision-making processes may be uncertain, for instance the activities’ durations, or the exact number of workers available each day. In this talk, we will discuss different types of uncertainty that may arise in such settings, we will look into alternative ways to model these different types, and we will also give a survey of the solution methods that have been applied over the years to optimize the different models. We will see that there is a close connection between the choices made for modelling the uncertainty, and the optimization procedures that are applied for finding good solutions. Our analysis is mainly based on the state of the art in project scheduling.
Most, if not all, public transport systems in the world are planned on the basis of timetables. These timetables are published so that passengers know at what time they can expect a vehicle. In reality a vehicle never exactly arrives according to a timetable, because of various disturbing factors like traffic conditions. Nonetheless, the planned departure times at a stop should be near to the real departure times in order to reduce waiting time and discomfort for the passenger.
In this talk we will discuss a new method for determination of planned runtimes, along with an enhanced way to measure the quality. We compare this with the most commonly used methods.
We consider the Electric Vehicle Scheduling Problem (e-VSP): a set of trips corresponding to a given time-table have to be driven by a set of electric buses with limited capacity. This problem, like many other planning problems, boils down to assigning to each bus a subset of the trips with the obvious side-constraint that the selected subset can be feasibly driven by this single bus; such a feasible subset is called a (vehicle) task then. If we know all possible tasks, then we can select the best set of tasks by solving an ILP. This idea has inspired many researchers to the heuristic of finding a decent subset of all tasks using the technique of Column Generation and then solve the ILP. For the e-VSP this approach leads to reasonable solutions, but there is still room for improvement. Instead of using Column Generation, we present a new solution approach by applying Simulated Annealing to find the subset of tasks that we use as input for the ILP. For the e-VSP this leads to far better solutions. Moreover, our approach is generally applicable and has as a clear advantage that we do not have to solve the pricing problem anymore, which increases the application possibilities.
There will be drinks afterwards.
Participation is free, but we ask you to register by sending an email to Han Hoogeveen (email@example.com) before May 24.
The workshop will take place at Utrecht University at the Buys Ballot Gebouw, Room 2.14. To enter the Buys Ballow gebouw take the entrance of the Koningsberger gebouw, take the stairs to the first floor, and then go to the right. For a map of the area click here.