18 September 2015
Sustainability in vehicle routing and scheduling problems
The first part of the talk presents the Time-Dependent Pollution-Routing Problem (TDPRP), a vehicle routing problem where CO2e emissions and traffic congestion are accounted for. The presence of traffic congestion during the first period of the day limits the vehicles speed and increases the amount of vehicle emissions per kilometer. The objective is to determine the assignment and the scheduling of customers to vehicles, the travel speed on each arc of the route and the departure time from each node, so as to minimize a total cost function encompassing labour cost and emissions cost. We describe an integer linear programming formulation of the TDPRP and we provide an analytical characterization of the optimal solution for a single-arc version of the problem. The theoretical results show that in some cases it is optimal to wait idly at certain locations in order to avoid congestion and to reduce the cost of emissions. The second part of the talk presents the Departure Time and Speed Optimization Problem (DSOP), a vehicle scheduling problem where CO2e emissions are accounted for. The objective is to determine the departure times and the travel speed of a vehicle traveling on a fixed route, so as to minimize a total cost function composed of labour cost and emissions cost. We formulate the problem as a dynamic programming problem, and we study the structure and the properties of the value function. Based on the theoretical results, we derive an efficient solution method, which simplifies into a shortest path problem.
Kevin Thierny (University of Paderborn)
22 September 2015, 11:00-12:00
Optimizing Liner Shipping Fleet Repositioning Plans
We solve a central problem in the liner shipping industry called the Liner Shipping Fleet Repositioning Problem (LSFRP). The LSFRP poses a large financial burden on liner shipping firms. During repositioning, vessels are moved between routes in a liner shipping network. Liner carriers wish to reposition vessels as cheaply as possible without disrupting the cargo flows of the network. We present the latest computational methods for solving the LSFRP and providing decision support to repositioning coordinator. Furthermore, we show results on a real world scenario in which our approach is able to increase the profit earned by our industrial collaborator from $18.1 million to $31.8 million.
Veaceslav Ghilas (Eindhoven University of Technology)
2 October 2015
An Exact Approach for the Pickup and Delivery Problem with Time Windows and Scheduled Lines
The Pickup and Delivery Problem with Time Windows and Scheduled Lines (PDPTW-SL) concerns routing and scheduling a set of vehicles to serve a set of freight requests such that a part of the journey can be carried out on scheduled public transportation lines. In this study, we propose an exact solution approach for the PDPTW-SL based on a branch and price algorithm. A path-based set partitioning formulation is used as master problem, and a variant of elementary shortest path problem with resource constraints is studied as pricing problem. The results of extensive computational experiments show that the proposed exact algorithm is able to solve small and medium-sized PDPTW-SL instances with up to 40 freight requests.
Thomas Breugem (Econometric Institute)
16 October 2015
FPTASes for the Multi-Objective Shortest Path Problem
We discuss two FPTASes for the Multi-Objective Shortest Path problem. The first one is known in the literature, the second is a newly proposed FPTAS, aimed at exploiting small Pareto curves. Together with an exact labeling algorithm, the FPTASes are analyzed, empirically, based on worst case complexity, average case complexity and smoothed complexity. We also analyze the size of the Pareto curve under different conditions.
Remy Spliet (Econometric Institute, ESE)
30 October 2015
The time window assignment vehicle routing problem with time dependent travel times
This talk is about assigning time windows to customers before their demand is learned and designing optimal vehicle routes adhering to these time windows after demand is learned. Demand is modeled using several demand scenarios. Travel times are modeled time dependently to account for congestion which occurs in every day practice. The goal is to assign the time windows such that the expected transportation costs are minimized. A branch-price-and-cut algorithm is developed to solve this problem.
Marjolein Veenstra (Universiteit van Groningen)
6 November 2015
Pickup and Delivery Problems with Handling Operations
In pickup and delivery problems, a fleet of vehicles based at a depot is used to complete a set of requests. A request consists of transporting goods from a specific pickup location, where the item is loaded, to a specific delivery location, where the item is unloaded. We consider rear-loaded vehicles that are operated in a last-in-first-out (LIFO) fashion. If a load must be unloaded that was not loaded last, additional handling operations are needed to unload and reload other loads that block access. These additional handling operations take time and effort, and therefore we take them into account when generating vehicle routes. We introduce two different problems. The first problem is the pickup and delivery traveling salesman problem with handling costs (PDTSPH). In this problem, we consider a single vehicle and associate penalty costs with the additional handling operations. The aim of the PDTSPH is to find a feasible route such that the total costs, consisting of travel costs and penalty costs, are minimized. We propose a large neighborhood search heuristic to solve the problem. We provide new best known solutions on benchmark instances for special cases of the problem. The second problem, which is called the pickup and delivery problem with time windows and handling operations (PDPTWH), considers a fleet of homogeneous vehicles of limited capacity, incorporates time windows and includes additional time for each handling operation. For the PDPTWH, we define two different policies for the additional handling operations. A branch-price-and-cut algorithm is developed for both policies. Computational results are reported on known instances for the pickup and delivery problem with time windows.
Pieter van den Berg (Delft University of technology)
20 November 2015
Incorporating coverage for emergency calls in scheduling patient transportations
Many ambulance providers operate both advanced life support (ALS) and basic life support (BLS) ambulances. Typically, emergency calls can only be executed by ALS vehicles, whereas non-urgent patient transportations can either be served by an ALS or a BLS ambulance. BLS vehicle capacity does normally not suffice for all transportation requests. The remaining transportations are performed by ALS ambulances, which reduces coverage for emergency calls. We present a model to determine routes for BLS vehicles, so as to maximize the remaining coverage by ALS ambulances.
Harm Bart (ESE)
4 December 2015
An integer programming problem connected with the classical logarithmic residue theorem
The celebrated logarithmic residue theorem from complex function theory gives a connection between the number of zeros of an analytic function f in a domain D and the contour integral of the logarithmic derivative f'/f over the boundary of D. How is the situation when one considers analytic functions having their values in target algebras more general than the complex plane? The issue has surprisingly many ramifications. This will be illustrated by looking at the situation where the target algebra is that of the n x n upper triangular matrices.
The talk is based on earlier work with Albert Wagelmans.
Ioannis Fragkos (Erasmus University Rotterdam)
11 December 2015
Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems
Despite the significant attention they have drawn, big bucket lot-sizing problems remain difficult to solve computationally. Previous research indicates that the embedded multi-period, multi-item, capacitated submodels are also challenging to analyze (from a theoretical) and solve (from a computational) perspective. We introduce a minimal submodel that captures the complexity of capacitated multi-period, multi-item lot-sizing structures, namely a two-period, multi-item, capacitated polyhedron with single and two-period (l,S) inequalities and relaxed demand constraints. We propose a methodology that can approximate the convex hulls of all multi-item, multi-period relaxations by generating valid inequalities, guaranteed to be violated from the original problem's LP relaxation. To generate such inequalities, we separate two-period projections of fractional LP solutions from the convex hulls of the two-period closure we study. The convex hull representation of the two-period closure is generated dynamically using column generation. Contrary to regular column generation, our method is an outer approximation, and therefore can be used efficiently in a regular branch-and-bound procedure. We present computational results that illustrate how these two-period models could be effective in solving complicated problems.