2018 Transportation Science Triple by Michael Schneider
In 2018, three articles coauthored by Michael Schneider have been accepted for publication in the prestigious journal INFORMS Transportation Science. Another three papers have been accepted in the A-ranked journals Discrete Applied Mathematics (2 x) and European Journal of Operational Research. An additional paper will be forthcoming in NETWORKS.
Simon Emde and Michael Schneider. Just-In-Time Vehicle Routing for In-House Part Feeding to Assembly Lines, Transportation Science 52(3):657-672, 2018.
Abstract: This paper deals with the problem of routing in-house transport vehicles that feed parts to workstations in assembly plants or workshops just in time. The capacitated vehicles, typically so-called tow trains, perform their assigned route cyclically without break and provide each station with the exact quantity of parts required until the next arrival of the vehicle. Hence, the demand of each station depends on the duration of the route serving the station: The longer the route duration, the less frequently the station is visited and the higher its demand. The goal is to minimize first the number of vehicles and second the total route duration, while respecting given minimum service frequencies at the stations. We provide a mathematical formulation of this novel problem and address it by means of a large neighborhood search. The algorithm is able to solve realistic instances in acceptable time and vastly outperforms a default solver. We discuss two variants of the problem, one in which split deliveries to stations are allowed and another assuming that all stations lie on a straight line. Finally, we investigate the extent to which assuming constant demand rates may lead to problems during the day-to-day operations of the part-feeding system, where demands are not necessarily constant.
D. Goeke, R. Roberti, and M. Schneider. Exact and heuristic solution of the consistent vehicle-routing problem. Forthcoming in Transportation Science.
Abstract: Providing consistent service by satisfying customer demands with the same driver (driver consistency) at approximately the same time (arrival time consistency) allows companies in last-mile distribution to stand out among competitors. The consistent vehicle-routing problem (ConVRP) is a multi-day problem addressing such consistency requirements along with traditional constraints on vehicle capacity and route duration. The literature offers several heuristics but no exact method for this problem. The state-of-the-art exact technique to solve VRPs—column generation (CG) applied to route-based formulations where columns are generated via dynamic programming (DP)—cannot be successfully extended to the ConVRP because the linear relaxation of route-based formulations is weak. We propose the first exact method for the ConVRP, which can solve medium-sized instances with five days and 30 customers. The method solves, via CG, a formulation where each variable represents the set of routes assigned to a vehicle over the planning horizon. As upper bounding procedure, we develop a large neighborhood search (LNS) featuring a repair procedure specifically designed to improve the arrival time consistency of solutions. Used as stand-alone heuristic, the LNS is able to significantly improve the solution quality on benchmark instances from the literature compared to state-of-the-art heuristics.
M. Schiffer, M. Schneider, G. Walther, and G. Laporte. Vehicle routing and location-routing with intermediate stops: A review. Forthcoming in Transportation Science.
Abstract: This paper reviews the literature on vehicle routing problems and location routing problems with intermediate stops. We classify publications into different categories from both an application-based perspective and a methodological perspective. In addition, we analyze the papers with respect to the algorithms and benchmark instances they present. Furthermore, we provide an overview of trends in literature and identify promising areas for further research.
E. Bartolini and M. Schneider. A two-commodity flow formulation for the capacitated truck-and-trailer routing problem. Discrete Applied Mathematics.
Abstract: In the capacitated truck-and-trailer routing problem (CTTRP), a limited fleet of capacitated trucks and trailers is available at a depot to serve a set of customers, of which some are only accessible by the truck alone. In this paper, we propose a two-commodity flow formulation for the CTTRP, which uses two sets of flow variables that model the flow of goods carried by trucks pulling a trailer and by trucks alone, respectively. We describe some valid inequalities for strengthening the formulation and develop a branch-and-cut algorithm for solving it. In our computational experiments, we consider both the CTTRP and its special case in which a single capacitated truck pulling an uncapacitated trailer is available. We report results on instances derived from known benchmark sets featuring up to 40 customers. The results show that our branch-and-cut solves 30-customer instances with either a single vehicle or loose capacity constraints with very high success rate. Of the more tightly capacitated 30-customer instances, about half can be solved. We also report results on benchmark instances of the single TTRP with satellite depots with up to 50 customers. In addition, we find that the lower bounds provided by the two-commodity flow formulation are superior to those of a corresponding one-commodity flow formulation. Finally, we study the effect of forbidding transfers between trucks and trailers.
D. Goeke, T. Gschwind, and M. Schneider. Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier. Discrete Applied Mathematics.
Abstract: The vehicle-routing problem with private fleet and common carrier (VRPPC) extends the capacitated VRP by considering the option of outsourcing customers to subcontractors at a customer-dependent cost instead of serving them with the private fleet. The VRPPC has important applications in small package shipping and manufacturing, but despite its relevance, no exact solution approach has been introduced so far. We propose a branch- price-and-cut algorithm that is able to solve small to medium-sized instances and provides tight lower bounds for larger instances from the literature. In addition, we develop a large neighborhood search that shows a decent solution quality and competitive run-times compared to the state-of-the-art on instances with homogeneous as well as heterogeneous vehicle fleet. In addition, several new best known solutions are found.
F. Weidinger, N. Boysen, and M. Schneider. Picker routing in the mixed-shelves warehouses of e-commerce retailers. European Journal of Operational Research.
Abstract: E-commerce retailers face the challenge to assemble large numbers of time-critical picking orders, of which each typically consists of just a few order lines and low order quantities. To efficiently solve this task, many warehouses in this segment are organized according to the mixed-shelves paradigm. Incoming unit loads are isolated into single units, which are randomly spread all over the shelves of the warehouse. In such a setting, the probability that a picker always finds a demanded stock keeping unit (SKU) close-by is high, irrespective of his/her current position in the warehouse. In spite of this organiza- tional adaption, picker routing, i.e., the sequencing of shelf visits when retrieving a set of picking orders, is still an important optimization problem. In a mixed-shelves warehouse, picker routing is much more complex than in traditional environments: Multiple orders are concurrently assembled by each picker, many alternative depots are available, and items of the same SKU are available in multiple shelves. This paper defines the resulting picker-routing problem in mixed-shelves warehouses and provides efficient solution methods. Furthermore, we use the developed methods to explore important managerial aspects. Specifically, we benchmark mixed-shelves storage against traditional storage policies for scenarios with different ratios between small-sized and large-sized orders. In this way, we investigate whether mixed-shelves storage is also a suited policy if an omni- channel sales strategy is pursued, and large-sized orders of brick-and-mortar stores as well as small-sized online orders are to be jointly processed by the same warehouse.
J. Hof and M. Schneider. An adaptive large neighborhood search with path relinking for a class of vehicle-routing problems with simultaneous pickup and delivery. Forthcoming in NETWORKS.
Abstract: We study a class of vehicle-routing problems with simultaneous pickup and delivery (VRPSPD). In VRPSPDs, each customer may require a certain quantity of goods delivered from the depot and a quantity of goods to be picked up and returned to the depot. Besides the standard VRPSPD, we address (i) the VRPSPD with time limit (VRPSPDTL), which imposes a time limit on the routes of the transportation vehicles, (ii) the VRPSPD with time windows (VRPSPDTW), which takes customer time windows into account, (iii) the VRP with divisible deliveries and pickups (VRPDDP), which allows for fulfilling the delivery and pickup requests of each customer in two separate visits, (iv) the previously unstudied VRP with restricted mixing of divisible deliveries and pickups (VRPRMDDP), which accounts for the difficulty of rearranging the vehicle load by additionally requiring that a certain percentage of the vehicle capacity must remain unoccupied when both types of demand are simultaneously loaded, and (v) the previously unstudied VRPDDP with time windows (VRPDDPTW). We develop a hybrid heuristic solution method which combines an adaptive large neighborhood search algorithm with a path relinking approach, called ALNS-PR, and we demonstrate the competitiveness of our algorithm on benchmark instances proposed in the literature. Especially on VRPSPDTL, VRPSPDTW, and VRPDDP instances, our ALNS-PR proves to be superior to the majority of comparison algorithms and is able to obtain numerous new best solutions.