New Publications at DPO group
Journal articles in 2020
Six papers from the DPO group were accepted for publication in 2020.
Information on the papers and abstracts can be found below. Papers 1 and 2 focus on optimization problems in the field of warehousing: paper 1 develops high-performance mathematical models to route order pickers in parallel-aisle warehouses, and paper 2 focuses on routing pickers that are supported by automated guided vehicles. Both articles are forthcoming in INFORMS Journal on Computing (included in the UT Dallas list). Papers 3–5 address relevant extensions of classical routing problems: paper 3 a robust variant of the traveling salesman problem and papers 4 and 5 extensions of the vehicle routing problem with time windows in which mobile replenishment options are available, or electric vehicles with a limited numbers of recharges per route are employed. Papers 3 and 4 have been accepted by Transportation Science, paper 5 by Networks. Finally, paper 6 addresses the planning of the growth of crops on shelves in vertical farming cabinets under controlled growth conditions. It is forthcoming in European Journal of Operational Research.
Paper 1: D. Goeke and M. Schneider. Modeling single picker routing problems in classical and modern warehouses. INFORMS Journal on Computing. Doi: 10.1287/ijoc.2020.1040
Abstract: The standard single picker routing problem (SPRP) seeks the cost-minimal tour to collect a set of given articles in a rectangular single-block warehouse with parallel picking aisles and a dedicated storage policy, i.e., each SKU is only available from one storage location in the warehouse. We present a compact formulation that forgoes classical subtour elimination constraints by directly exploiting two of the properties of an optimal picking tour used in the dynamic programming algorithm of Ratliff and Rosenthal (1983). We extend the formulation to three important settings prevalent in modern e-commerce warehouses: scattered storage, decoupling of picker and cart, and multiple end depots. In numerical studies, our formulation outperforms existing standard SPRP formulations from the literature and proves able to solve large instances within short runtimes. Realistically sized instances of the three problem extensions can also be solved with low computational effort. For scattered storage, we note a rough tendency that runtimes increase with longer pick lists or a higher degree of duplication. In addition, we find that decoupling of picker and cart can lead to substantial cost savings depending on the speed and capacity of the picker when traveling alone, whereas additional end depots have rather limited benefits in a single-block warehouse.
Paper 2: M. Löffler, N. Boysen, and M. Schneider. Picker routing in AGV-assisted order picking systems. Forthcoming in INFORMS Journal on Computing.
Abstract: To reduce unproductive picker walking in traditional picker-to-parts warehousing systems, automated guided vehicles (AGVs) are used to support human order pickers. In an AGV-assisted order picking system, each human order picker is accompanied by an AGV during the order picking process. AGVs receive the picked items and, once a picking order is complete, autonomously bring the collected items to the shipping area. Meanwhile, a new AGV is requested to meet the picker at the first storage position of the next picking order. Thus, the picker does not have to return to a central depot but continuously picks order after order. This paper addresses both the routing of an AGV-assisted picker through a single-block parallel-aisle warehouse and the sequencing of incoming orders. We present an exact polynomial time routing algorithm for the case of a given order sequence, which is an extension of the algorithm of Ratliff and Rosenthal (1983), and a heuristic for the case in which order sequencing is part of the problem. In addition, we investigate the use of highly effective TSP solvers that can be applied after a transformation of both problem types into a standard TSP. The numerical studies address the performance of these methods and study the impact of AGV usage on picker travel: by using AGVs to avoid returns to the depot and by sequencing in (near-)optimal fashion, picker walking can be reduced by about 20\% compared to a traditional setting. Sharing AGVs among the picker workforce enables a pooling effect, so that in larger warehouses only about 1.5 AGVs per picker are required to avoid picker waiting.
Paper 3: E. Bartolini, D. Goeke, M. Schneider, and M. Ye. The robust traveling salesman problem with time windows under knapsack-constrained travel time uncertainty. Transportation Science. Doi: 10.1287/trsc.2020.1011
Abstract: We study the traveling salesman problem with time windows (TSPTW) under travel time uncertainty—modeled by means of an uncertainty set including all travel time vectors of interest. We consider a knapsack-constrained uncertainty set stipulating a nominal and a peak travel time for each arc and an upper bound delta on the sum of all deviations from the nominal times. Viewing the difference between the peak time and its nominal value as the maximum delay possibly incurred when traversing the corresponding arc, the problem we consider is thus to find a tour that remains feasible for up to delta units of delay. This differs from previous studies on robust routing under travel time uncertainty, which have relied on cardinality-constrained sets and only allow for an upper bound on the number of arcs with peak travel time. We propose an exact algorithm based on column generation and dynamic programming that involves effective dominance rules and an extension of the ng-tour relaxation proposed in the literature for the classical TSPTW. The algorithm is able to solve the robust TSPTW under both knapsack- and cardinality-constrained travel time uncertainty. Extensive computational experiments show that the algorithm is successful on instances with up to 80 customers. In addition, we study the impact of the two uncertainty sets on the trade-off between service quality and cost exhibited by the resulting solutions.
Paper 4: J. Hof and M. Schneider. Intra-route resource replenishment with mobile depots. Forthcoming in Transportation Science.
Abstract: In numerous practical vehicle-routing applications, larger vehicles are employed as mobile depots to support a fleet of smaller vehicles that perform certain tasks. The mobile depots offer the possibility to keep the task vehicles operational by supplying them en route with certain resources. For example, in two-echelon distribution systems, small task vehicles are used to navigate narrow streets and to deliver/collect goods or to collect waste, and larger vehicles serve as mobile depots to replenish the goods to be delivered or to receive collected goods or waste at the outskirts of the urban area. Accessibility constraints may also be imposed by regulations on emissions, which make some areas only accessible for environmentally-friendly vehicles such as, e.g., battery electric vehicles. Especially if the respective refueling infrastructure is sparse, mobile refueling stations seem to be an interesting alternative. In this paper, we introduce the vehicle-routing problem with time windows and mobile depots (VRPTWMD) to capture the routing decisions of the described applications in a generalized fashion. The VRPTWMD is characterized by a fleet of task vehicles (TVs) and a fleet of support vehicles (SVs). The SVs may serve as mobile depots to restore either the load or the fuel capacity of the TVs that are used to fulfill the customer requests. We present a mixed-integer program for the VRPTWMD, with which small instances can be solved using a commercial solver. Moreover, we develop a high-quality hybrid heuristic composed of an adaptive large neighborhood search and a path relinking approach to provide solutions on larger problem instances. We use a newly generated set of large VRPTWMD instances to analyze the effect of different problem characteristics on the structure of the identified solutions. In addition, our approach shows a very convincing performance on benchmark instances for the related two-echelon multiple-trip VRP with satellite synchronization, which can be viewed as a special case of the VRPTWMD. Our heuristic is able to significantly improve a large part of the previous best-known solutions while spending notably less computation time than the comparison algorithm from the literature.
Paper 5: M. Löffler, G. Desaulniers, S. Irnich, and M. Schneider. Routing electric vehicles with a single recharge per route. Networks 76(2), 2020. Doi: 10.1002/net.21964
Abstract: Driven by environmental considerations, regulations on vehicle emissions, and the offer of major subsidies, electric commercial vehicles (ECVs) are receiving ever stronger attention in logistics companies. Route planning for ECV fleets requires consideration of the special characteristics of ECVs, like limited driving range and the potential need to recharge en route at dedicated recharging stations. From a practical viewpoint, the number of recharge operations of each vehicle can very often be restricted to one recharge per route because (i) typical route distances in the most important application areas of ECVs, like small package shipping and food or beverage distribution, do not require more than one recharge given the current driving range of ECVs, and (ii) operations managers are very reluctant to plan vehicle routes with two or more recharges because recharging operations are perceived as unproductive idle times. We develop a simple hybrid of large neighborhood search and granular tabu search to solve the resulting electric vehicle‐routing problem with time windows and single recharge (EVRPTWS), considering the possibility of both full and partial recharge. The heuristic works on routes represented as customer sequences, and recharge operations are implicitly considered by determining the recharging position in the route, the recharging station to visit, and the amount to be recharged in optimal fashion. We discuss how our algorithm can be extended to handle nonlinear recharging times, different recharging times per station, and time‐dependent waiting times at stations. In numerical studies on EVRPTWS instances from the literature, the method provides optimal or near‐optimal solutions for instances with up to 100 customers within reasonable runtimes. Additional studies investigate the cost savings potential of partial recharges in comparison to full recharges in the presence of time‐window constraints, and examine the factors that influence this cost saving potential.
Paper 6: A. Santini, E. Bartolini, M. Schneider, and V. G. de Lemos. The Crop Growth Planning Problem in Vertical Farming. European Journal of Operational Research. Doi: 10.1016/j.ejor.2021.01.034
Abstract: In this paper, we study the problem of planning the growth of crops on shelves in vertical farming cabinets under controlled growth conditions. By adjusting temperature, humidity, light, and other environmental conditions in different parts of the cabinets, a planner must ensure that crop growth is able to satisfy some deterministic demand. We prove this problem to be NP-hard and propose an integer programming formulation able to capture real-life operational characteristics, including changes of growth conditions on a daily, shelf-by-shelf basis, over a planning horizon of months. We compare four objective functions from which a planner can choose, depending on the specific operations of the company. A computational study on realistic instances, which we make available as a public dataset, shows that the choice of objective function heavily influences both the difficulty of solving the model with a standard solver and the solution characteristics.