Data Instances

Braune, R. (2022). Packing-based branch-and-bound for discrete malleable task scheduling. Journal of Scheduling, 25(6), 675-704. https://doi.org/10.1007/s10951-022-00750-w

This paper addresses the problem of scheduling chain-like structures of tasks on a single multiprocessor resource. In fact, sub-tasks of unit-time length and predefined size are aggregated to composite tasks that have to be scheduled without preemption, but subject to flexibility concerning resource allocation. This setting most closely resembles the problem of malleable task scheduling, with sub-tasks being the smallest atomic unit of allocation. The specific type of malleability is realized using precedence constraints with minimum and maximum time lags. A bin packing model is established for this scheduling problem and a corresponding, dedicated branch-and-bound algorithm is devised, alongside problem-specific bound tightening, symmetry breaking and dominance concepts. The efficacy of the solution approach is demonstrated based on extensive computational experiments, including randomized instances, adapted benchmark instances from the literature, and a small real-world data set. In comparison to mixed-integer and constraint programming formulations, the new method is able to achieve a considerably higher percentage of optimal solutions at computation times that are up to orders of magnitude smaller.

Braune, R., Benda, F., Dörner, K. F., & Hartl, R. (2022). A Genetic Programming Learning Approach to Generate Dispatching Rules for Flexible Shop Scheduling Problems. International Journal of Production Economics, 243, Article 108342. https://doi.org/10.1016/j.ijpe.2021.108342

Besides benchmark sets from academic literature on flexible job shop scheduling, these also included instances from the real-world scenario. In addition to that, we used randomly generated problem instances with the same properties for training purposes.

This paper deals with a Genetic Programming (GP) approach for solving flexible shop scheduling problems. The adopted approach aims to generate priority rules in the form of an expression tree for dispatching jobs. Therefore, in a list-scheduling algorithm, the available jobs can be ranked using the tree-based priority rules generated using GP. These priority rules were tested on benchmark problem settings, such as those of Brandimarte and Lawrence, in a static and dynamic environment. The GP approaches were then applied to a special case based on the problem setting of an industrial partner. The goal of these approaches was to minimize the maximum completion time of all jobs, which is known as the makespan. To reach this goal, we considered job assignment and machine sequencing decisions simultaneously in a single-tree representation and compared this single tree with a multi-tree approach, where the terminal sets (job- and machine-related) were strictly separated. This resulted in two parallel GP populations; they were used to first decide which job to choose and then which machine it should be assigned to. Furthermore, for both tree approaches, we implemented an iterative variant that stores recorded information of past schedules to achieve further improvements. Computational experiments revealed a consistent advantage compared to the existing advanced priority rules from the literature with considerably increased performance under the presence of unrelated parallel machines and larger instances in general.

Ion Beam Facility: Considering Optional Activities and Time Window Constraints. Journal of Scheduling, 22(2), 137–154 . https://doi.org/10.1007/s10951-018-0574-0

Ion beam radiotherapy is a modern form of cancer treatment that is offered in specialized facilities. Treatment consists of multiple, almost daily irradiation appointments, followed by optional imaging and control assignments. The corresponding problem of scheduling these recurring radiotherapy treatment appointments can be classified as a complex job shop scheduling problem with custom constraints, such as recurring activities, optional activities, and special time window constraints. The objective is to minimize the operation time of the bottleneck resource, the particle beam, while simultaneously minimizing any penalties arising from violations of time window constraints. The authors model the problem mathematically and introduce various customized constraints. Three metaheuristic solution approaches—namely a genetic algorithm with tailor-made feasibility-preserving crossover operators, an iterated local search, and a combination of the two approaches—all perform well on both small and large problem instances. However, the simple combination of the two stand-alone algorithms leads to best results when applied to real-world inspired problem instances.

In the pickup and delivery problem (PDP) with alternative locations and overlapping time windows, parcels need to be transported from a seller (sender) who may have multiple roaming pickup locations throughout the day with non-overlapping time windows (since the product cannot be in two places at once) to a buyer (recipient) who has an alternative person available for delivery and an optional  24-hour locker box if one is located near their home. As such, multiple persons in different locations can be available simultaneously to accept a delivery (hence the overlapping time windows). Each person (sender or recipient) falls into one of 17 different customer profiles to gain a diverse daily schedule with 1 to 5 different locations per day. 

Our self-generated instances are based on Viennese delivery data from 2017 from an Austrian logistics provider. 700 locations were classified into 'home', 'work', and 'other' roaming locations (a place where people typically and regularly spend a block of their time, i.e., a fitness center, library, educational institution, etc.). Each location can have multiple classifications at once. Additional locations represent 24-hour locker box stations belonging to the Austrian Post in Vienna (with a separate classification 'postal locker box'). For these 799 locations (including the depot), we provide a symmetrized shortest-path real-world travel time matrix (in minutes). 

570 instances were created of 19 different scenario types and three different sizes (30, 50 and 100 requests). 

Dragomir, Alina G., Tom Van Woensel, and Karl F. Doerner. "The pickup and delivery problem with alternative locations and overlapping time windows." Computers & Operations Research 143 (2022): 105758.

We address a planning problem faced by logistics service providers who transport freight over long distances. Given a set of transportation requests, where the origin and the destination of each request are located far apart from each other, a logistics service provider must find feasible vehicle routes to fulfil those requests at minimum cost. When transporting freight over long distances, multimodal transportation provides a viable alternative to traditional unimodal road transportation. We introduce this new problem, which we call the multimodal long haul routing problem (MMLHRP), and present a mathematical formulation for it. Furthermore, we propose a matheuristic, using iterated local search within a column generation framework, for solving the MMLHRP. Results show that large cost savings can be achieved through multimodal transportation compared to unimodal road transportation.

https://ucris.univie.ac.at/portal/de/publications/a-matheuristic-for-a-multimodal-long-haul-routing-problem(eb8bd7c4-5160-4d8a-a33e-bde37917bb88).html

Dragomir, A.-G., Van Woensel, T., & Dörner, K. F. (2022). The pickup and delivery problem with alternative locations and overlapping time windows. Computers & Operations Research, 143, Article 105758. https://doi.org/10.1016/j.cor.2022.105758

Many security companies offer patrolling services, where guards have to inspect facilities or streets on a regular basis. Patrolling routes should be cost efficient, while the inspection patterns should not be predictable for of-fenders. Also cash-in-transit services result in routing problems, where cost minimization and route inconsistency have to be traded-off. We introduce this setting as multi-objective periodic node, edge, arc routing problem with the objectives being minimizing the costs and minimizing the route consistency. It is mathematically formulated and transformed into an asymmetric capacitated vehicle routing problem, once with a simple-graph and once with a multi-graph. In order to solve the problem, we propose to embed an adaptive large neighborhood search procedure into multi-objective solution frameworks. We implement three frameworks, namely multi-directional local search (MDLS), ε-constraint heuristic (ECH), and ε-box splitting heuristic (EBSH). The methods were tested on artificial as well as on real-world in-stances. In an extensive computational study, we show that EBSH and ECH seem to be the superior methods. Furthermore, the results indicate that considering more than one shortest paths between nodes, can significantly increases solution quality.

A vehicle routing problem with synchronization constraints arises in urban freight transportation, in which context customers require deliveries from one or more logistics service providers. These deliveries should be efficient to reduce idle times at the delivery locations. Idle time is defined as nonservice time between the first and the last delivery received by the customer. We propose a strategy which relies on self-imposed time windows, and we compare our approach with an exact determination of a feasible schedule and fixed time windows. The results show that idle times can be reduced by 54.12%-79.77%, with an average cost rise of 9.87%. In addition, self-imposed time windows provide solutions with 15.74%-21.43% lower costs than feasibility checks for short runtimes and 13.71%-21.15% lower than fixed time windows.

Schilde, M., Dörner, K., Hartl, R., & Kiechle, G. (2009). Metaheuristics for the Bi-Objective Orienteering Problem. Swarm Intelligence, 3(3), 179-201.

In this paper, heuristic solution techniques for the multi-objective orienteering problem are developed. The motivation stems from the problem of planning individual tourist routes in a city. Each point of interest in a city provides different benefits for different categories (e.g., culture, shopping). Each tourist has different preferences for the different categories when selecting and visiting the points of interests (e.g., museums, churches). Hence, a multi-objective decision situation arises. To determine all the Pareto optimal solutions, two metaheuristic search techniques are developed and applied. We use the Pareto ant colony optimization algorithm and extend the design of the variable neighborhood search method to the multi-objective case. Both methods are hybridized with path relinking procedures. The performances of the two algorithms are tested on several benchmark instances as well as on real world instances from different Austrian regions and the cities of Vienna and Padua. The computational results show that both implemented methods are well performing algorithms to solve the multi-objective orienteering problem.

Gansterer, M., & Hartl, R. (2018). Centralized bundle generation in auction-based collaborative transportation. OR Spectrum: quantitative approaches in management, 40(3), 613-635. doi.org/10.1007/s00291-018-0516-4

In horizontal collaborations, carriers form coalitions in order to perform parts of their logistics operations jointly. By exchanging transportation requests among each other, they can operate more efficiently and in a more sustainable way. This exchange of requests can be organized through combinatorial auctions, where collaborators submit requests for exchange to a common pool. The requests in the pool are grouped into bundles, and these are offered to participating carriers. From a practical point of view, offering all possible bundles is not manageable, since the number of bundles grows exponentially with the number of traded requests. We show how the complete set of bundles can be efficiently reduced to a subset of attractive ones. For this we define the Bundle Generation Problem (BuGP). The aim is to provide a reduced set of offered bundles that maximizes the total coalition profit, while a feasible assignment of bundles to carriers is guaranteed. The objective function, however, could only be evaluated whether carriers reveal sensitive information, which would be unrealistic. Thus, we develop a proxy for the objective function for assessing the attractiveness of bundles under incomplete information. This is used in a genetic algorithms-based framework that aims at producing attractive and feasible bundles, such that all requirements of the BuGP are met. We achieve very good solution quality, while reducing the computational time for the auction procedure significantly. This is an important step towards running combinatorial auctions of real-world size, which were previously intractable due to their computational complexity. The strengths but also the limitations of the proposed approach are discussed.

Tricoire, F., Scagnetti, J., & Beham, A. (2018). New insights on the block relocation problem. Computers & Operations Research, 89, 127-139. https://doi.org/10.1016/j.cor.2017.08.010

This article presents new methods for the block relocation problem (BRP). Although much of the existing work focuses on the restricted BRP, we tackle the unrestricted BRP, which yields more opportunities for optimisation. Our contributions include fast heuristics able to tackle very large instances within seconds, fast metaheuristics that provide very competitive performance on benchmark data sets, as well as a new lower bound that generalises existing ones. We embed it in a branch-and-bound algorithm, then assess the influence of various factors on the efficiency of branch-and-bound algorithms for the BRP.

Schneeberger, K., Schilde, M., Doerner, K.F. (2016). Solving a Rich Position-Based Model for Dairy Products. In: Lübbecke, M., Koster, A., Letmathe, P., Madlener, R., Peis, B., Walther, G. (eds) Operations Research Proceedings 2014. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-28697-6_71

The following is a description for the test instances presented in the article “Solving a Rich Position-Based Model for Dairy Products”. In total, 32 test instances are provided. The test instances are based on real-world data and guarantee a realistic setting. The data is provided as XML, to ensure an easy usage of the data. By considering the lot-sizing problem and the detailed sequencing and scheduling problem simultaneously in a very realistic model formulation we aim to improve the overall performance of the entire production process for a dairy producing company. For this purpose we extended the Position-Based Model introduced by Lütke et al. (Int. J. Prod. Res. 43, 5071–5100, 2005 [5]). Based on a set of real-world production data, we used our model to determine exact solutions to very small problem settings. As even for small instances the time required for obtaining exact solutions is too long in general, we developed a fix&optimize inspired construction heuristic to obtain a feasible solution for several products. The results of our approach show that the solutions obtained are competitive compared to the optimal solution with less time consumption.