Schedule seminars spring 2017
Joris Wagenaar (Erasmus School of Economics)
20 januari 2017
Maintenance Appointments in Railway Rolling Stock Scheduling
This paper addresses the Rolling Stock Rescheduling Problem (RSRP), while taking maintenance appointments into account. After a disruption, the rolling stock of the disrupted passenger trains has to be rescheduled in order to restore a feasible rolling stock circulation. Usually, a number of train units have a scheduled maintenance appointment during the day: these appointments must be taken into account while rescheduling the rolling stock. In this paper we propose three Mixed Integer Programming (MIP) models for this purpose. The Extra Unit Type model adds an additional rolling stock type for each train unit that requires maintenance. The Shadow-Account model keeps track of a shadow account for each train unit that requires maintenance. The Job-Composition model creates a path for each train unit such that the train units that require maintenance are on time for their maintenance appointments. All models are tested on instances of Netherlands Railways (NS). The results show that especially the Shadow-Account model and the Job-Composition model are e ffectively able to take maintenance appointments into account during real-time rescheduling. It depends on the characteristics of an instance whether the Shadow-Account model or the Job-Composition model performs best.
Bart van Riessen (Erasmus School of Economics)
27 January 2017
The Cargo Fare Class Mix Problem
The intermodal hinterland transportation of maritime containers is under pressure from port authorities and shippers to achieve a more integrated, efficient network operation. Current optimisation methods in literature yield limited results in practice, though, as the transportation product structure limits the flexibility to optimise network logistics. Several transportation providers in the industry aim to overcome this with the concept of Synchromodality. We study the case of European Gateway Services' hinterland network in North West Europe: they are developing a portfolio of fare classes based on differentiation in price and lead time. However, higher priced fare classes come with tighter planning restrictions and must be carefully balanced with lower priced fare classes to match available capacity and optimise network utilisation. We propose the Cargo Fare Class Mix problem, aimed at setting limits for each fare class at a tactical level, such that the expected revenue is maximised, considering the available capacity at the operational level. A solution method for a single intermodal corridor is proposed, serving one region with multiple destinations. We show that using a limit on each fare class increases revenue and reliability, thereby outperforming existing fare class mix policies, such as Littlewood. Currently, our work focuses on extending this approach to multiple corridor networks.
Juan S. Borrero (Industrial Engineering at the University of Pittsburgh)
28 February 2017
Sequential Max-Min Bilevel Programming with Incomplete Information and Learning
We present a framework for a class of sequential decision-making problems in the context of max-min bilevel programming, a class of hierarchical optimization problems with applications in network interdiction, defense, vulnerability analysis, among others. At each period, the leader allocates resources to disrupt the performance of the follower (e.g., as in the defender-attacker, attacker-defender or interdiction problems), who in turn minimizes some cost function over a set of activities that depend on the leader's decision. While the follower has complete knowledge of his/her problem, the leader has only partial information, and needs to learn about the cost parameters, available resources, and the follower's activities from the feedback generated by the follower's actions. We propose a class of greedy and robust policies and show that these policies are weakly optimal, eventually match the oracle's actions, and provide a real-time certificate of optimality. In particular, we measure policy performance in terms of its time-stability, defined as the number of periods it takes for the leader to match the actions of an oracle with complete information. We also study a lower bound on any policy performance based on the notion of a semi-oracle. Our numerical experiments demonstrate that the proposed policies consistently outperform several other reasonable benchmarks, and perform fairly close to the semi-oracle.
Heleen Stellingwerf (Univesity of Wageningen)
17 March 2017
The load dependent vehicle routing problem for temperature controlled road transportation and gain allocation to enable sustainable collaborative transportation
Temperature controlled transport is used to maintain quality of products such as fresh and frozen foods and pharmaceuticals. Road transportation is responsible for a considerable part of global emissions, and temperature controlled transportation exhausts even more emission than ambient temperature transport because extra fuel is needed to provide the energy for cooling. The transportation sector is under pressure to improve both its environmental and economic performance. To explore opportunities to reach this goal, the Load Dependent Vehicle Routing Problem (LDVRP) has been developed. However, this approach does not take into account the environmental effects of temperature regulation. Therefore, an extension of the LDVRP to account for thermal energy requirements is needed. This extended LDVRP is applied in a case study in the Dutch fresh food industry. Our results show that taking into account energy needed for temperature control can result in different optimal routes and speeds compared to the LDVRP and the VRP. Also, it shows that taking into account thermal energy requirement can improve the estimation of fuel consumption and emissions related to temperature controlled transport. In our search for ways to improve sustainability of transportation, we also look at tactical level logistics concepts like collaboration. Currently, trucks are not efficiently used: on average, trucks driving in the EU use less than half of their available capacity. This results in the need to organize fresh food logistics more efficiently such that it will become more sustainable. Literature suggests that food companies collaborate in order to improve food supply chain sustainability. However, the effects of collaboration on sustainability have only scarcely been quantified; most papers only focus on economic sustainability. We use the extended LDVRP to test collaboration scenarios and to find routes that minimize fuel, total emissions and costs. However, fair sharing of these cost savings (gains) is crucial to make the collaboration work. We look for a gain sharing method that reflects the contribution of partners to economic as well as to environmental sustainability.
DeniseTönissen (Technical University Eindhoven)
31 maart 2017
Recoverable Robust Maintenance Location Routing for Rolling Stock
We consider the problem of locating maintenance facilities in a railway setting. Different facility sizes can be chosen for each candidate location. We have a discrete set with capacities and associated fixed facility costs, for each maintenance facility, that can capture the economies of scale. Because of the strategic nature of facility location, this problem has to be feasible for the current situation, but also for any of the scenarios that can occur in the future. These discrete scenarios capture changes such as changes to the rolling stock schedule, up and down-scaling of service frequencies and the introduction of new rolling stock types. We allow recovery in the form of opening additional facilities, closing facilities and upgrading the facility size for each scenario. We provide a two-stage robust programming formulation. In the first stage, we decide where to open what size of facility. In the second stage, we solve a NP-hard maintenance location routing problem. We reformulate the problem as a mixed integer program that can be used to make an efficient column-and-constraint generation algorithm that improves the computational time and can handle larger instances due to more efficient memory usage. Furthermore, we perform an extensive case study with data from the Dutch Railways.
Thomas Visser (Erasmus School of Economics)
7 April 2017
Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems with Route Duration Constraints
We consider the Vehicle Routing Problem with Time Windows, time-dependent travel times and in which route duration is constrained or minimized. This problem arises in many real world transportation applications, for instance when modelling road traffic congestion and driver shifts with maximum allowed working time. In the rapidly growing field of e-commerce logistics, higher quality solutions are desired while the available computation time must decrease to lower customer lead-times. To obtain high quality solutions for instances of 1000+ requests, (meta-) heuristics are needed, which typically rely on some form of Neighborhood Search. In such algorithms, it is crucial to quickly check feasibility and exact objective change of local improvement moves. Although constant time checks based on pre-processing are known for both the time-dependent VRPTW, and the VRPTW with duration constraints, the combination of the two is significantly harder, leading to quadratic time complexity in the number of requests. We show how pre-processing can be used to decrease the move evaluation complexity from quadratic to linear time. Furthermore, we introduce a new data structure that reduces computation times further by maintaining linear time move evaluation complexity even when the neighborhood is searched in non-lexicographic order. We support our complexity results by presenting numerical results of various benchmark instances.
Roel van den Broek (University of Utrecht)
21 April 2017
Planning Heuristics for Integrated Train Shunting and Service Scheduling
Trains have to be maintained and cleaned regularly to ensure passenger safety and satisfaction. These service tasks must be performed outside the rush hours, when the trains are parked off the main railway network on shunting yards. At these shunting yards, planners have to match incoming and outgoing trains, schedule the service tasks, assign trains to parking tracks and route the trains over the location. The corresponding planning problem combines the Train Unit Shunting Problem (TUSP) with features of classical RCPSPs. To find feasible plans, we propose a local search approach that integrates the four planning aspects. The performance of this heuristic is investigated in a case study for the Dutch Railways (NS).
Caroline Jagtenberg (Ortec B.V.)
19 May 2017
Efficiency and fairness in ambulance planning
In emergency situations where every second counts, the timely presence of an ambulance can be a matter of life or death. Thereto, we've developed several optimization models for the logistics of Emergency Medical Services (EMS). In this talk we highlight two aspects:
- Facility location models: efficiency versus fairness. Rather than simply maximizing the number of people served, we consider the distribution over the different areas where people live. To that end, we view ambulance optimization models from a social welfare perspective. We analyze existing ambulance planning models and show that they tend to maximize either the number of people served (utilitarian social welfare) or maximize the service to the person who is worst off (egalitarian social welfare). We propose a third option: the so-called Bernoulli-Nash social welfare. We introduce a new facility location model that maximizes this Bernoulli-Nash social welfare, and show that it offers an attractive compromise between the utilitarian and egalitarian optimum.
- Improving response times in operational planning: relocating idle vehicles to increase coverage. We introduce an efficient heuristic to solve this complex problem. The practical relevance of this heuristic was demonstrated by the implementation in a decision support tool used by the EMS region Flevoland.
Marilène Cherkesley (Département de management et technologie, École des sciences de la gestion, Université du Québec à Montréal)
30 June 2017
The pickup and delivery problem with LIFO constraints
In this presentation, we propose models and algorithms for two variants of the pickup and delivery problem with handling constraints: the pickup and delivery problem with time windows and last-in-first-out (LIFO) loading constraints (PDPTWL) and the pickup and delivery problem with time windows and multiple stacks (PDPTWMS). In the pickup and delivery problem, vehicles based at a depot are used to satisfy a set of requests which consists of transporting goods (or items) from a specific pickup location to a specific delivery location. We consider an unlimited fleet of identical vehicles with multiple homogeneous compartments of limited capacity. A vehicle route is feasible if the load in each compartment of the vehicle does not exceed its capacity and each completed request is first picked up at its pickup location and then delivered at its corresponding delivery location. In the PDPTWL, the LIFO loading rule ensures that no handling is required prior to unloading an item from a vehicle: an item can only be delivered if it is the last one in the stack. In the PDPTWMS, each vehicle contains multiple stacks that are operated in a LIFO fashion. The problem consists of determining a set of least-cost feasible routes in which the number of vehicles is first minimized. To solve those variants of the pickup and delivery problem, two families of branch-price-and-cut algorithms are developed. The first family tackles the handling constraints in the shortest path pricing problem and applies a dynamic programming algorithm relying on an ad hoc dominance criterion. The second family incorporates the handling constraints partly in the shortest path pricing problem and adds additional inequalities to the master problem when infeasible paths are encountered. Known valid inequalities are adapted to the PDPTWL, and the PDPTWMS. Instances with up to 75 requests are solved within two hours of computational time.
Marcel Turkensteen (Aarhus University)
13 July 2017 (Thursday) 13:00-14:00
An assessment of carbon emission reductions from improving the degree of vehicle utilization
The emission of greenhouse gases is one of the negative side effects of road freight transportation. One way to reduce this negative impact is by using existing vehicle capacity more efficiently: An increase in the degree of vehicle utilization can cause a reduction in the number of kilometers driven for given transport hauls, which could reduce carbon emissions. In this presentation, we consider the increase in vehicle utilization that can be achieved if we add a return load to a vehicle that makes deliveries from a depot to a set of customers, for example, by picking up recyclable materials on the way. To that end, we discuss the following two topics:
- We evaluate tools to compute the carbon emissions of vehicles with different loads and discuss some of the challenges with their usage. The question is what type of carbon computation tools are suitable in operations research studies in inventory and routing models.
- We perform an assessment of the carbon emission savings that can be achieved when a logistics provider can combine outbound deliveries as well as pickup orders from supply locations on the same vehicles. The question is under which conditions this leads to the largest (smallest) benefits in terms of carbon emissions.