InformaApp - Publikationen

Publikationen

2019 2018 2017 2016 2015 2014 2013 2012 2011 2010

2019 2018 2017 2016 2015 2014 2013

Suche nach „[Drexl] [Michael]“ hat 26 Publikationen gefunden

Suchergebnis als PDF

Mobil Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Zeitschriftenartikel

Michael Drexl, C. Tilk, S. Irnich

Nested Branch-and-Price-and-Cut for Vehicle Routing Problems with Multiple Resource Interdependencies

European Journal of Operational Research, vol. 276, no. 2, pp. 549-565

2019

DOI: 10.1016/j.ejor.2019.01.041

Abstract anzeigen

This paper considers vehicle routing problems (VRPs) with multiple resource interdependencies and addresses the development and computational evaluation of an exact branch-and-price-and-cut algorithm for their solution. An interdependency between two resources means that the two resource consumptions influence one another in such a way that a tradeoff exists between them. This impacts the feasibility and/or the cost of a solution. The subproblem in branch-and-price-and-cut procedures for VRPs is very often a variant of the shortest-path problem with resource constraints (SPPRC). For the exact solution of many SPPRC variants, dynamic-programming based labeling algorithms are predominant. The tradeoffs in problems with multiple resource interdependencies, however, render the application of labeling algorithms unpromising. This is because complex data structures for managing the tradeoff curves are necessary and only weak dominance criteria are possible, so that the labeling algorithm becomes almost a pure enumeration. Therefore, we propose to solve also the SPPRC subproblem with branch-and-price-and-cut. This results in a two-level, nested branch-and-price-and-cut algorithm. We analyze different variants of the algorithm to enable the exchange of columns and also rows between the different levels. To demonstrate the computational viability of our approach, we perform computational experiments on a prototypical VRP with time windows, minimal and maximal delivery quantities for each customer, a customer-dependent profit paid for each demand unit delivered, and temporal synchronization constraints between some pairs of customers. In this problem, tradeoffs exist between cost and load and between cost and time.

Mobil Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Buch (Monographie)

Michael Drexl

On Testing Capacity Constraints in Pickup-and-Delivery Problems with Trailers in Amortized Constant Time

Discussion Paper Series No. 1823, Gutenberg School of Management and Economics, Johannes-Gutenberg-Universität Mainz, no. 1706

2018

Digital Mobil Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Buch (Monographie)

Michael Drexl

On the One-to-One Pickup-and-Delivery Problem with Time Windows and Trailers

Discussion Paper Series No. 1816

2018

Mobil Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Zeitschriftenartikel

A.-K. Rothenbächer, Michael Drexl, S. Irnich

Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows

Transportation Science, vol. 52, no. 5, pp. 1174-1190

2018

DOI: 10.1287/trsc.2017.0765

Abstract anzeigen

In this paper, we present a new branch-and-price-and-cut algorithm to solve the truck-and-trailer routing problem with time windows (TTRPTW) and two real-world extensions. In all TTRPTW variants, the fleet consists of one or more trucks that may attach a trailer. Some customers are not accessible with a truck-and-trailer combination, but can however be serviced by one if the trailer is previously detached and parked at a suitable location. In the first extension, the planning horizon comprises two days and customers may be visited either on both days or only once, in which case twice the daily supply must be collected. The second extension incorporates load transfer times depending on the quantity moved from a truck to its trailer. The exact branch-and-price-and-cut algorithm for the standard variant and the two new extensions is based on a set-partitioning formulation in which columns are routes describing the movement of a truck and its associated trailer. Linear relaxations of this formulation are solved by column generation where new routes are generated with a dynamic programming labeling algorithm. The effectiveness of this pricing procedure can be attributed to the adaptation of techniques such as bidirectional labeling, the ng-neighborhood, and heuristic pricing using dynamically reduced networks and relaxed dominance. The cutting component of the branch-and-price-and-cut adds violated subset-row inequalities to strengthen the linear relaxation. Computational studies show that our algorithm outperforms existing approaches on TTRP and TTRPTW benchmark instances used in the literature.

Mobil Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Zeitschriftenartikel

Michael Drexl, C. Tilk, N. Bianchessi, S. Irnich, F. Meisel

Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem

Transportation Science, vol. 52, no. 2, pp. 300-319

2017

DOI: 10.1287/trsc.2016.0730

Abstract anzeigen

This paper presents a branch-and-price-and-cut algorithm for the exact solution of the active-passive vehicle-routing problem (APVRP). The APVRP covers a range of logistics applications where pickup-and-delivery requests necessitate a joint operation of active vehicles (e.g., trucks) and passive vehicles (e.g., loading devices such as containers or swap bodies). The objective is to minimize a weighted sum of the total distance traveled, the total completion time of the routes, and the number of unserved requests. To this end, the problem supports a flexible coupling and decoupling of active and passive vehicles at customer locations. Accordingly, the operations of the vehicles have to be synchronized carefully in the planning. The contribution of the paper is twofold: First, we present an exact branch-and-price-and-cut algorithm for this class of routing problems with synchronization constraints. To our knowledge, this algorithm is the first such approach that considers explicitly the temporal interdependencies between active and passive vehicles. The algorithm is based on a nontrivial network representation that models the logical relationships between the different transport tasks necessary to fulfill a request as well as the synchronization of the movements of active and passive vehicles. Second, we contribute to the development of branch-and-price methods in general, in that we solve, for the first time, an ng-path relaxation of a pricing problem with linear vertex costs by means of a bidirectional labeling algorithm. Computational experiments show that the proposed algorithm delivers improved bounds and solutions for a number of APVRP benchmark instances. It is able to solve instances with up to 76 tasks, four active, and eight passive vehicles to optimality within two hours of CPU time.

Mobil Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Zeitschriftenartikel

Michael Drexl, M. Schneider

A Survey of the Standard Location-Routing Problem

Annals of Operations Research, vol. 259, no. 1-2, pp. 389-414

2017

DOI: 10.1007/s10479-017-2509-0

Mobil Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Buch (Monographie)

Michael Drexl, N. Bianchessi, S. Irnich

The Split Delivery Vehicle Routing Problem with Time Windows and Customer Inconvenience Constraints

Discussion Paper Series No. 1706, Gutenberg School of Management and Economics, Johannes-Gutenberg-Universität Mainz, no. 1706

2017

Mobil Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Zeitschriftenartikel

A.-K. Rothenbächer, Michael Drexl, S. Irnich

Branch-and-Price-and-Cut for a Service Network Design and Hub Location Problem

European Journal of Operational Research, vol. 255, no. 3, pp. 935-947

2016

DOI: 10.1016/j.ejor.2016.05.058

Mobil Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Buch (Monographie)

Michael Drexl, T. Gschwind

Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem

Discussion Paper Series No. 1624, no. 1624

2016

Mobil Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Buch (Monographie)

Michael Drexl, J. Avenhaus-Betz, T. Ramsauer

Software zur Tourenplanung ‐ Marktstudie 2015 / 2016

2015

Mobil Nachhaltig Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Zeitschriftenartikel

Michael Drexl, M. Schneider

A Survey of Variants and Extensions of the Location-Routing Problem

European Journal of Operational Research, vol. 241, no. 2, pp. 283-308

2015

DOI: 10.1016/j.ejor.2014.08.030

Abstract anzeigen

This is a review of the literature on variants and extensions of the standard location-routing problem published since the last survey, by Nagy and Salhi, appeared in 2006. We propose a classification of problem variants, provide concise paper excerpts that convey the central ideas of each work, discuss recent developments in the field, and list promising topics for further research.

Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Zeitschriftenartikel

Michael Drexl, S. Irnich

Solving Elementary Shortest-Path Problems as Mixed-Integer Programs

OR Spectrum, vol. 36, no. 2, pp. 281-296

2014

DOI: 10.1007/s00291-012-0302-7

Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen

Buch (Monographie)

Michael Drexl

A Generic Heuristic for Vehicle Routing Problems with Multiple Synchronization Constraints

Discussion Paper Series No. 1412, no. 1412