"This site requires JavaScript to work correctly"
minimize Header

Prof. Dr. Michael Drexl

Faculty of Computer Science

Professors

Professor

ITC2 2.28

0991/3615-587

Sortierung:
Zeitschriftenartikel

  • Michael Drexl

On efficient testing of capacity constraints in pickup-and-delivery problems with trailers

In: 4OR - A Quarterly Journal of Operations Research vol. 19 pg. 289-307.

  • (2021)

DOI: 10.1007/s10288-020-00452-z

Efficient feasibility tests are important in many heuristics for routing problems. This paper considers several variants of pickup-and-delivery problems with trailers. Its contribution consists in the description of constant-time procedures for testing observance of capacity constraints when inserting tasks into routes. It is demonstrated that the presence of vehicles with detachable trailers makes capacity feasibility tests considerably more involved.
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl

On the one-to-one pickup-and-delivery problem with time windows and trailers

In: Central European Journal of Operations Research vol. 29 pg. 1115-1162.

  • (2021)

DOI: 10.1007/s10100-020-00690-w

This paper studies an extension of the well-known one-to-one pickup-and-delivery problem with time windows. In the latter problem, requests to transport goods from pickup to delivery locations must be fulfilled by a set of vehicles with limited capacity subject to time window constraints. Goods are not interchangeable: what is picked up at one particular location must be delivered to one particular other location. The discussed extension consists in the consideration of a heterogeneous vehicle fleet comprising lorries with detachable trailers. Trailers are advantageous as they increase the overall vehicle capacity. However, some locations may be accessible only by lorries. Therefore, special locations are available where trailers can be parked while lorries visit accessibility-constrained locations. This induces a nontrivial tradeoff between an enlarged vehicle capacity and the necessity of scheduling detours for parking and reattaching trailers. The contribution of the paper is threefold: (i) it studies a practically relevant generalization of the one-to-one pickup-and-delivery problem with time windows. (ii) It develops an exact amortized constant-time procedure for testing the feasibility of an insertion of a transport task into a given route with regard to time windows and lorry and trailer capacities. (iii) It provides a comprehensive set of new benchmark instances on which the runtime of the constant-time test is compared with a naïve one that requires linear time by embedding both tests in an adaptive large neighbourhood search algorithm. Computational experiments show that the constant-time test outperforms its linear-time counterpart by one order of magnitude on average.
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • C. Tilk
  • Michael Drexl
  • S. Irnich

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

In: European Journal of Operational Research vol. 276 pg. 549-565.

  • https://www.sciencedirect.com/science/article/abs/pii/S0377221719300761 (2019)

DOI: 10.1016/j.ejor.2019.01.041

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.
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
  • MOBIL
Zeitschriftenartikel

  • N. Bianchessi
  • Michael Drexl
  • S. Irnich

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

In: Transportation Science vol. 53 pg. 1067-1084.

  • (2019)

DOI: 10.1287/trsc.2018.0862

In classical routing problems, each customer is visited exactly once. By contrast, when allowing split deliveries, customers may be served through multiple visits. This potentially results in substantial savings in travel costs. Even if split deliveries are beneficial to the transport company, several visits may be undesirable on the customer side: At each visit the customer has to interrupt his primary activities and handle the goods receipt. The contribution of the present paper consists in a thorough analysis of the possibilities and limitations of split delivery distribution strategies. To this end, we investigate two different types of measures for limiting customer inconvenience (a maximum number of visits and the temporal synchronization of deliveries) and evaluate the impact of these measures on carrier efficiency by means of different objective functions (comprising variable routing costs, costs related to route durations, and fixed fleet costs). We consider the vehicle routing problem with time windows in which split deliveries are allowed (SDVRPTW) and define the corresponding generalization that takes into account customer inconvenience constraints (SDVRPTW-IC). We design an extended branch-and-cut algorithm to solve the SDVRPTW-IC and report on experimental results showing the impact of customer inconvenience constraints. We finally draw useful insights for logistics managers on the basis of the experimental analysis carried out.
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
  • MOBIL
Zeitschriftenartikel

  • T. Gschwind
  • Michael Drexl

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

In: Transportation Science vol. 53 pg. 480-491.

  • (2019)

DOI: 10.1287/trsc.2018.0837

In the dial-a-ride problem, user-specified transport requests from origin to destination points have to be served by a fleet of homogeneous vehicles. The problem variant we consider aims at finding a set of minimum-cost routes satisfying constraints on vehicle capacity, time windows, maximum route duration, and maximum user ride times. We propose an adaptive large neighborhood search (ALNS) for its solution. The key novelty of the approach is an exact amortized constant-time algorithm for evaluating the feasibility of request insertions in the repair steps of the ALNS. In addition, we use two optional improvement techniques: a local-search-based intraroute improvement of routes of promising solutions using the Balas–Simonetti neighborhood and the solution of a set covering model over a subset of all routes generated during the search. With these techniques, the proposed algorithm outperforms the state-of-the-art methods in terms of solution quality. New best solutions are found for several benchmark instances.
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
  • MOBIL
Zeitschriftenartikel

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

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

In: Transportation Science vol. 52 pg. 1174-1190.

Gutenberg School of Management and Economics, Johannes-Gutenberg-Universität Mainz Gutenberg School of Management and Economics, Johannes-Gutenberg-Universität Mainz

  • 2016 (2018)

DOI: 10.1287/trsc.2017.0765

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.
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
  • MOBIL
Zeitschriftenartikel

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

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

In: Transportation Science vol. 52 pg. 300-319.

  • (2017)

DOI: 10.1287/trsc.2016.0730

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.
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
  • MOBIL
Zeitschriftenartikel

  • M. Schneider
  • Michael Drexl

A Survey of the Standard Location-Routing Problem

In: Annals of Operations Research vol. 259 pg. 389-414.

  • (2017)

DOI: 10.1007/s10479-017-2509-0

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
  • MOBIL
Zeitschriftenartikel

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

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

In: European Journal of Operational Research vol. 255 pg. 935-947.

  • (2016)

DOI: 10.1016/j.ejor.2016.05.058

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
  • MOBIL
Zeitschriftenartikel

  • Michael Drexl
  • M. Schneider

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

In: European Journal of Operational Research vol. 241 pg. 283-308.

  • (2015)

DOI: 10.1016/j.ejor.2014.08.030

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
  • NACHHALTIG
  • MOBIL
Buch (Monographie)

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

Software zur Tourenplanung ‐ Marktstudie 2015 / 2016

Fraunhofer Verlag Stuttgart

  • (2015)
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
  • MOBIL
Buch (Monographie)

  • Michael Drexl

A Generic Heuristic for Vehicle Routing Problems with Multiple Synchronization Constraints

In: Discussion Paper Series No. 1412

Gutenberg School of Management and Economics, Johannes-Gutenberg-Universität Mainz Gutenberg School of Management and Economics, Johannes-Gutenberg-Universität Mainz

  • 2014 (2014)
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl

On the Generalized Directed Rural Postman Problem

In: Journal of the Operational Research Society vol. 65 pg. 1143-1154.

  • (2014)

DOI: 10.1057/jors.2013.60

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl

Branch-and-Cut Algorithms for the Vehicle Routing Problem with Trailers and Transshipments

In: Networks vol. 63 pg. 119-133.

  • (2014)

DOI: 10.1002/net.21526

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl
  • S. Irnich

Solving Elementary Shortest-Path Problems as Mixed-Integer Programs

In: OR Spectrum vol. 36 pg. 281-296.

  • (2014)

DOI: 10.1007/s00291-012-0302-7

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl

Applications of the Vehicle Routing Problem with Trailers and Transshipments

In: European Journal of Operational Research vol. 227 pg. 275-283.

  • (2013)

DOI: 10.1016/j.ejor.2012.12.015

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl

A Note on the Separation of Subtour Elimination Constraints in Elementary Shortest Path Problems

In: European Journal of Operational Research vol. 229 pg. 595-598.

  • (2013)

DOI: 10.1016/j.ejor.2013.03.009

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl
  • J. Rieck
  • T. Sigl
  • B. Press

Simultaneous Vehicle and Crew Routing and Scheduling for Partial- and Full-Load Long-Distance Road Transport

In: BuR ‐ Business Research vol. 6 pg. 242-264.

  • (2013)

DOI: 10.1007/BF03342751

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Beitrag (Sammelband oder Tagungsband)

  • Michael Drexl
  • H. Werr

Keine Stangenware

pg. 90-93.

Munich

  • (2012)
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl

Synchronization in Vehicle Routing‐-A Survey of VRPs with Multiple Synchronization Constraints

In: Transportation Science vol. 46 pg. 297-316.

  • (2012)

DOI: 10.1287/trsc.1110.0400

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl

Rich Vehicle Routing in Theory and Practice

In: Logistics Research vol. 5 pg. 47-63.

  • (2012)

DOI: 10.1007/s12159-012-0080-2

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl

Branch-and-Price and Heuristic Column Generation for the Generalized Truck-and-Trailer Routing Problem

In: Journal of Quantitative Methods for Economics and Business Administration vol. 12 pg. 5-38.

  • (2011)
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl

Marktstudie Tourenplanungssoftware

In: OR News (Das Magazin der Gesellschaft für Operations Research e.V.) vol. 41 pg. 6-9.

  • (2011)
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • Michael Drexl
  • E. Prescott-Gagnon

Labelling Algorithms for the Elementary Shortest Path Problem with Resource Constraints Considering EU Drivers’ Rules

In: Logistics Research vol. 2 pg. 79-96.

  • (2010)

DOI: 10.1007/s12159-010-0022-9

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Buch (Monographie)

  • Michael Drexl

Software zur Tourenplanung ‐ Marktstudie 2010

Fraunhofer Verlag Stuttgart

  • (2010)
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
Zeitschriftenartikel

  • E. Prescott-Gagnon
  • G. Desaulniers
  • Michael Drexl
  • L.-M. Rousseau

European Driver Rules in Vehicle Routing with Time Windows

In: Transportation Science vol. 44 pg. 455-473.

  • (2010)

DOI: 10.1287/trsc.1100.0328

  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen