Refine
Document Type
- Doctoral thesis (5)
Institute
Language
- Multiple languages (3)
- English (2)
Keywords
- Operations Research (5) (remove)
Die vorliegende kumulative Dissertation befasst sich mit vier Problemstellungen der Transportplanung im Falle der Übernahme des Paket- und Medikamententransports durch Lieferwagen und Drohnen.
Der erste Beitrag thematisiert die Fahrzeugflottenplanung und Zuweisung von Drohnen zu Mikrodepots, wenn Lieferwagen und Drohnen den Transport von Paketen in der letzten Meile übernehmen. Im Vordergrund stehen die taktischen Entscheidungen, welche Kombination von Auslieferungsformen mit Lieferwagen und Drohnen optimal wäre sowie die Ausgestaltung der Fahrzeugflotte. Die Problemstellung wird als gemischt-ganzzahliges lineares Programm (MILP) modelliert. Zudem wird eine adaptive große Nachbarschaftssuche (ALNS) eingeführt, die neue problemspezifische Operatoren beinhaltet.
Der zweite Beitrag fokussiert sich auf die operative Tourenplanung eines Lieferwagens, welcher mit mehreren Drohnen ausgerüstet ist. Hierfür wird ein effizientes MILP entwickelt, welches ein kommerzieller Solver schneller lösen kann als vergleichbare MILPs für eine Ein-Drohnen Problematik aus der Literatur.
Der dritte Beitrag optimiert die simultane Bestands- und Tourenplanung für die Belieferung von Krankenhäusern unter der Berücksichtigung ihrer Lagerhaltungspolitiken. Es wird analysiert, welchen Einfluss Drohnen als Vehikel für Notfalltransporte zur Vermeidung von Fehlmengen haben. Die Problemstellung wird als zweistufiges stochastisches Programm präsentiert und eine problemspezifische ALNS wird entwickelt, welche einen innovativen Algorithmus zur Bestimmung von Bestellpunkten innerhalb der Lagerhaltungspolitiken beinhaltet.
Der vierte Beitrag thematisiert die Ausgestaltung der Drohnenflotte für die Belieferung von Apotheken und Krankenwagen im Einsatz durch einen Großhändler. Hierfür wird die Drohnenflotte in einer ereignisdiskreten Simulationsstudie hinsichtlich der Kosten bzw. der CO2-Emissionen optimiert.
This cumulative dissertation addresses issues related to different, innovative variants of the classical vehicle routing problem (VRP). In the first paper, we investigate a tactical VRP for regular deliveries to grocery retail stores over several planning periods. In contrast to previous approaches, multi-compartment vehicles are used, which allow joint deliveries of different product groups. Thus, synergy effects can be achieved if this is included in the planning of the specific delivery patterns. As a heuristic solution method for this planning problem, an Adaptive Large Neighborhood Search (ALNS) is designed. In the second paper, the VRP is extended to include time windows and customer-specific availability probabilities to improve the operational delivery of last-mile parcels. The data-driven approach that incorporates information on when recipients are more likely to be at home into delivery route planning can significantly reduce the number of failed delivery attempts. In order to efficiently solve the model developed for this purpose, the novel hybrid ALNS (HALNS), which combines elements of an ALNS and genetic algorithms. The HALNS is further developed in the third paper and applied to a whole class of VRPs that, in addition to the classical assignment and sequencing problem, also make decisions regarding the locations of the depots used. Finally, the fourth paper focuses on the multi-period VRP. The existing literature on its tactical and operational variants is surveyed and characterized, clearly distinguishing the two forms for the first time.
Diese kumulative Dissertation beschäftigt sich konzeptionell als auch methodisch mit Fragestellungen, die im Rahmen der Zustellung auf der letzten Meile auftreten. Auf konzeptioneller Ebene werden innovative Ansätze für die letzte Meile vorgestellt und bewertet (Beitrag 1 und 4). Auf methodischer Ebene wird zum einen ein etabliertes Verfahren auf eine neue Problemstellung hin angepasst (Beitrag 4), zum anderen eine neuartige Metaheuristik vorgestellt und auf neue bzw. mehrere bekannte Probleme angewandt (Beitrag 1, 2 und 3).
Der erste Beitrag entwickelt einen innovativen, datengetriebenen Ansatz zur Reduzierung fehlgeschlagener Zustellversuche, indem das Vehicle Routing Problem (VRP) um Verfügbarkeitsprofile erweitert wird. Außerdem wird eine neuartige Metaheuristik, die sog. Hybrid Adaptive Large Neighborhood Search (HALNS) vorgestellt und deren Performance analysiert. Die HALNS wird im zweiten Beitrag weiter entwickelt, sodass mehrere Varianten von VRPs mit Standortentscheidungen hinsichtlich der Depots gelöst werden können. Zu diesen Varianten zählen das 2-Echelon VRP, das Location Routing Problem sowie das Multi-Depot VRP. Der dritte Beitrag zeigt die Praxistauglichkeit der HALNS im Rahmen der Amazon Routing Research Challenge. Ziel der Challenge war es, gute Routen zu erzeugen, die außerdem der reellen Fahrweise der Fahrer möglichst nahe kommen. Der vierte Beitrag entwickelt einen innovativen Ansatz, basierend auf der Sharing Economy für die Zustellung auf der letzten Meile. Hierbei besteht die Möglichkeit sog. Gelegenheitskuriere, z.B. Pendler, für die Zustellung einzusetzen. Zur besseren Integration dieser Gelegenheitskuriere können zusätzliche Standorte, genauer Umschlagpunkte (Transshipment Points, TPs), genutzt werden.
Order picking and delivery are integral parts of many supply chains, especially those of retail and online trade. They are mostly non-value-adding, downstream processes, but they are responsible for the majority of logistics costs. Accordingly, the academic literature deals with both order picking and vehicle routing in a diverse and detailed manner. However, a holistic view of both processes is mostly not sufficiently taken into account. The interdependent effects on the operational planning level are only considered to a limited extent since the processes are usually considered isolated or sequential planning is assumed. This thesis examines different order picking and vehicle routing problems. Furthermore, it shows the advantages of integrative planning and develops exact and heuristic solution methods for the investigated problems.
The first paper develops a structural understanding of the subproblems of picking and delivery. In addition, the article illustrates the development of the research branch of integrative order picking and vehicle routing.
Further contributions examine practice-oriented problems in the field of micro-store deliveries (contribution 2), same-day deliveries (contribution 3), and the supply of supermarkets (contribution 4). In each case, different real-world constraints are included and different objectives are addressed. Furthermore, problem-specific integrative solution methods are developed and compared to classical approaches.
In many countries today, a rising life expectancy and the associated demographic shift, coupled with the advancements of modern medicine, has fueled an ever-increasing cost pressure on healthcare systems. A driving factor for these rising costs can be seen in inpatient stays in hospitals that in many cases are connected to cost-intensive treatments. A central concern of any hospital management in such an environment is therefore to understand how to make the best possible use of available resources. A decisive factor in this regard is the management of bed capacities.
The present cumulative dissertation comprises four contributions, which address
open research questions in the field of strategic, tactical and operative bed planning:
1 Walther, M., 2020. Strategical, tactical, and operational aspects of bed
planning problems in hospital environments. Submission planned to
Social Science Research Network (SSRN)
2 Hübner, A., Kuhn, H., Walther, M., 2018. Combining clinical departments
and wards in maximum-care hospitals. OR Spectrum 40, 679-709
3 Schäfer, F., Walther, M., Hübner, A., Kuhn, H., 2019. Operational
patient-bed assignment problem in large hospital settings including overflow
and uncertainty management. Flexible Services and Manufacturing
Journal 31, 1012–1041
4 Schäfer, F., Walther, M., Hübner, A., Grimm, D., 2020. Machine learning
and pilot method: tackling uncertainty in the operational patient-bed
assignment problem. Submitted to OR Spectrum on 13 February 2020
The first contribution sets out to provide an overview over the different hierarchical planning levels on which bed planning problems may be addressed. It should be noted in this context that several different aspects may be combined under the collective term “bed planning”. These may be delimited in terms of their scope and their planning horizon. A frequently used taxonomy in this context is the hierarchical subdivision of typical problems in health care into strategical, tactical and operational levels as provided by Hulshof et al. (2012). In the context of bed planning, a typical strategical problem is how to combine departments and wards to obtain benefits from pooled ward capacity. On a tactical level, an exemplary problem setting related to bed planning can be seen in devising master surgery schedules that optimize downstream bed occupancy levels as patients returning from surgery will require a bed for post-surgical recovery and monitoring. Finally,
on an operational level, patient-bed allocations need to be optimized while taking the objectives and constraints of patients and medical staff alike into account.
To start, the second contribution deals with the strategical problem of combining departments into groups and assigning pooled ward capacity to these groups with the goal of balancing bed occupancy levels within a hospital. Specifically, one of the underlying goals is to minimize the amount of beds required to meet a predetermined service level. However, merging ward capacities with the aim of simultaneously accommodating patients from different medical departments increases the complexity of organizing and ensuring proper care for these patients. This leads to so-called pooling costs. To tackle this problem, a modeling and solution approach is developed which is based on a generalized partitioning problem and is solved by integer
linear programming (ILP). This enables hospital management to determine the cost-optimal combination of all departments and wards in a hospital, while ensuring that predetermined thresholds with regard to maximum
walking distances for doctors and patients are adhered to.
Once pooled ward capacities are established, the solution space for allocating incoming patients to beds is greatly increased and the underlying allocation problem quickly becomes too complex to be handled without computational support. In this regard the third contribution ties in with the second contribution in that it deals with optimizing the operational patient-bed allocation problem. In order to enable optimal allocation of patients to beds, it is important to identify and take into account the individual needs and
limitations of the three main stakeholders involved, namely patients, doctors, and nursing staff. All of these stakeholders exhibit different and sometimes contradicting objectives and constraints, such that a trade-off has to be made that maximizes the overall utility for the hospital. In addition, the complexity of the problem is increased by the high volatility and uncertainty regarding patient arrivals, types of illnesses, and the resulting remaining lengths of stay of newly arriving patients. In order to address this situation,
a mathematical model and solution approach for the patient-bed allocation problem is developed that is designed to generate solutions for large, real-life operative planning situations. In addition to being able to deal with overflow situations, this solution approach further takes different patient types into account, for example by anticipating emergency patient arrivals.
Finally, the fourth contribution builds on the third contribution in that the modeling and solution approach to allocate patients to beds is extended by several aspects. As mentioned above, hospitals have to deal with uncertainty regarding the actual demand for beds. Here, the fourth contribution improves the anticipation of emergency patients by using machine learning. Specifically, weather data, seasons, important local and regional events, and current and historical occupancy rates are combined to better anticipate emergency inpatient arrivals. In addition, a hyper-heuristic approach is developed based on the pilot method defined by Voß et al. (2005). By combining the improved anticipation of emergency patients with this hyperheuristic approach significant improvements can be achieved compared to the solution approach presented in the third contribution.