Joris Wagenaar (Erasmus School of Economics)
20 January 2017
Maintenance Appointments in Railway Rolling Stock Scheduling
Abstract:
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
Abstract:
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
Abstract:
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
Abstract:
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 March 2017
Recoverable Robust Maintenance Location Routing for Rolling Stock
Abstract:
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
Abstract:
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
Abstract:
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
Abstract:
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
Abstract:
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
An assessment of carbon emission reductions from improving the degree of vehicle utilization
Abstract:
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.
Joydeep Paul (RSM)
8 September 2017
Vehicle routing with shared customer consolidation in multi-channel retail
Abstract:
A multi-channel fulfillment model that is currently very popular is the buy-online-pick-up-in-store (BOPS) in which customers can buy goods online and pick them up in store. It is a common practice for multi-channel retailers using BOPS to have separate warehouses for online and offline channels to ensure efficient order fulfillment operations, and then transfer the goods from the individual warehouses to the stores. As a result, same stores are visited by vehicles from different channels. In this paper, we introduce a novel consolidation strategy in which the carrier of one distribution channel has the possibility to piggyback on the routes of the carrier of another distribution channel for the delivery of goods to a set of shared customers. Since there is not enough room to outsource all the customers, we have to decide which customers to visit directly and which customers to outsource. However, there are additional costs to transfer the demand of outsourced customers from the warehouse of one to the other's. This gives rise to a trade-off between the savings achieved by outsourcing and the transfer costs. We apply our consolidation strategy to a real grocery retail case to test that substantial savings can be achieved in terms of the travel distance and the number of customer-visits.
Florian Arnold (Faculty of Applied Economics, University of Antwerp)
22 September 2017
Fast and useful - Efficient routing and its application in practice
Abstract:
Routing problems are among the most-studied and practical-relevant problems in combinatorial optimization. To tackle their complexity, a plethora of heuristics has been developed in the last decades to compute better and better solutions in a feasible time. However, this race for better solutions has caused heuristics to become extremely intricate and difficult to study or to apply in practice. Furthermore, almost all research has been targeted to solve problems of several hundred customers, even though some applications like waste collection and parcel distributions can involve thousands or even tens of thousands of customers.
In this talk, I will demonstrate that complexity is not the only way to obtain successful heuristics. We developed a well-implemented local search which - guided by problem knowledge, obtained through data mining - is among the most efficient heuristics for the Vehicle Routing Problem. Moreover, its linear scaling can be used to solve very large scale routing problems with 10,000 and more customers in a feasible time. Such a fast routing algorithm can be used to tackle real-world problems, for instance, to simulate whether parcel deliveries via cargo bikes are a decent alternative to classical home deliveries via vans. Finally, efficient solution techniques for routing problems can be used to address more advanced problems, especially when it comes to integrating different decisions along the supply-chain in one optimisation framework. As an example, I will outline the idea of optimising the inventory strategy as well as the distribution jointly.
Dirk Siegag
26 September 2017
Choice-Based Network Revenue Management under Online Reviews
Abstract:
A choice-based network revenue management model is proposed that integrates the effect of reviews. Application areas include airlines, hotels, and rental cars. The dependency between reviews and revenue is two-fold: the content of a review depends on the product the customer purchases, and reviews impact the demand. A complicating factor in this model is that the effects of reviews are delayed, i.e., by sacrificing revenue now in order to get better reviews, long-term revenue can be increased. Novel solution methods are proposed that exploit the presence of reviews in order to optimise revenue.
Dmitry Krushinsky (Wageningen University)
27 September 2017
Old problems, new ideas
Abstract:
In this talk, he will give a brief overview of his past and current logistics-related research. The talk is focused on the idea that a careful model choice is crucial for successful optimisation. In particular, the use of non-standard approaches can provide new insights into the properties of a problem and substantially improve the performance of the related algorithms. Among others, this point will be illustrated on three rather different problems:
- simulation of pedestrian crowd movement;
- cell formation in industrial engineering;
- vehicle routing.
Niels Agatz (RSM)
6 October 2017
Dynamic Programming Approaches for the Traveling Salesman Problem with Drone
Abstract:
The fast and cost-efficient home delivery of goods ordered online is logistically challenging. Many companies are looking for new ways to cross the last-mile to their customers. One technology-enabled opportunity that recently has received much attention is the use of a drone to support deliveries. A new delivery model in this area entails the use of a delivery truck that collaborates with a drone to make deliveries. Effectively combining a drone and a truck gives rise to a new planning problem that we call the Traveling Salesman Problem with Drone (TSP-D). In this talk, I will present solution approaches to the TSP-D based on dynamic programming and discuss various new numerical results.
Christos Orlis (Vrije Universiteit Amsterdam
20 October 2017
Distributing cash with KPI considerations: the capacitated routing problem with profits and service level requirements
Abstract:
Inspired by a problem arising in cash logistics, we propose the Capacitated Routing Problem with Profits and Service Level Requirements (CRPPSLR). The CRPPSLR extends the class of Routing Problems with Profits by considering customers requesting deliveries to their (possibly multiple) service points. Moreover, each customer imposes a service level requirement specifying a minimum-acceptable bound on the fraction of its service points being delivered. A customer-specific financial penalty is incurred by the logistics service provider when this requirement is not met. The CRPPSLR consists of finding vehicle routes maximizing the difference between the collected revenues and the incurred transportation and penalty costs in such a way that vehicle capacity and route duration constraints are met. A fleet of homogeneous vehicles is available for serving the customers. We design a branch-and-cut algorithm and evaluate the usefulness of valid inequalities that have been effectively used for the capacitated vehicle routing problem and, more recently, for other routing problems with profits. Real-life case studies coming from the cash supply chain in the Netherlands highlight the relevance of the problem under consideration. Computational results illustrate the performance of the proposed solution approach under different input parameter settings for the synthetic instances. For the real-life problem instances we distinguish between coin and banknote distribution since vehicle capacities only matter when considering the former case.
Lisa Maillart (Department of Industrial Engineering at the University of Pittsburgh)
17 November 2017
Optimizing Donor Milk Bank Operations
Abstract:
Donated human milk – collected, processed and dispensed via milk banks – is the standard of care for premature inpatient infants and unhealthy outpatient infants whose mothers cannot provide adequate supply. We take a multi-criteria mixed-integer program approach to optimize (1) the daily decisions involved in the pooling of milk from different donors to meet macronutrient requirements across different product types, and (2) the batching of pooled milk for efficient pasteurization. Our numerical results demonstrate significant improvements compared to historical decisions at our partner milk bank.