"This site requires JavaScript to work correctly"

Sortierung:
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

  • 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

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

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

Software zur Tourenplanung ‐ Marktstudie 2015 / 2016

Fraunhofer Verlag Stuttgart

  • (2015)
  • Angewandte Naturwissenschaften und Wirtschaftsingenieurwesen
  • MOBIL
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

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

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

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

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

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