Tadumadze, Giorgi (2021)
Integrating Workforce Scheduling Aspects into Daily Operations at Trailer Terminals with a Special Focus on Loading and Unloading of Trucks.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00017583
Dissertation, Erstveröffentlichung, Verlagsversion
Kurzbeschreibung (Abstract)
The cumulative dissertation at hand consists of four research papers, three of which have already been published in scientific journals. The fourth is under review to be published in another international journal. All four articles deal with the combinatorial optimization problems that arise through integrating personnel scheduling factors into operative planning at cargo handling facilities. More precisely, the considered planning problems are related to trucks' unloading and loading processes at massive transshipment terminals, crucial nodes for many modern transportation networks. Examples for such large trailer terminals can be distribution centers or cross-docks (e.g., in the food or automotive industry), hub terminals in the postal sector, etc. At such cargo facilities, hundreds of trucks are coordinated daily. In particular, goods are unloaded from incoming trucks, possibly stored for a while, consolidated, and loaded into outgoing trucks. Typically, a terminal building of such cargo facility consists of several gates (or dock doors), where trucks are docked while goods are unloaded or loaded into the trailer. One crucial planning problem at such facilities is to schedule trucks' loading and unloading processes at the terminal gates. The planning problem that determines on at which door and in which time interval each truck has to be (un-)loaded is called truck scheduling problem.
Although trailers' (un-)loading activities at the gates usually require worker's involvement, the integration of personnel planning aspects into truck scheduling problems has only received little attention in the scientific literature. The focus of this thesis is to integrate workforce planning into truck scheduling problems. The planning problems proposed in the presented articles differ in spatial aspects where the respective operations take place. They include activities at the gates in both the receiving and the shipping areas of the facility as well as activities within the terminal yard, i.e., outside the terminal building. Furthermore, as discussed below, these four papers apply different methodologies to solve the corresponding optimization problems.
The first paper focuses on inbound operations, i.e., in the receiving area of the cargo facility. We introduce a novel integrated workforce and truck scheduling problem, where incoming trucks with strict arrival and departure times are unloaded at the dock doors by a varying number of terminal employees. The duration of the trailer's unloading depends not only on the specific truckload but also on the number of workers jointly unloading it. It is worth mentioning that most existing models widely ignore the latter phenomenon by assuming constant handling times for each truck. That represents the case where a fixed number of employees are preassigned to each dock door in advance. In practice, however, terminal managers have additional flexibility in assigning a diverse number of employees to each truck, depending on the degree of its actual urgency. Since a higher number of employees speeds up the handling time, it is reasonable to solve the personnel assignment and truck scheduling problem holistically. We examine the integrated planning approach for two representative truck scheduling settings: a conventional distribution center and a cross-docking terminal. The resulting two optimization problems differ from each other in their objectives. The former's objective is to minimize the total flow-time (i.e., the total time a truck spends at the terminal, including the waiting time before the actual unloading process). In the cross-docking environment, the goods are directly moved towards the corresponding outbound trucks without any (extended) intermediate storage in the terminal. Hence, the latter problem aims to schedule the incoming trucks at the inbound gates in such a way that the unloaded goods can be transferred to the corresponding outbound trucks on time. More precisely, the truck scheduling problem in the cross-docking setting minimizes the number of delayed shipments that cannot reach the dedicated outbound trucks before the scheduled departure time.
After formalizing the planning problems as mathematical optimization problems, we develop a mixed-integer linear optimization programming model for each setting. Moreover, we provide an alternative problem reformulation as the interval scheduling problem. Based on this, we design various heuristic solution procedures, which are different in terms of the interval generation process in the model preparation phase. We test the algorithmic performance of the proposed solution approaches using newly generated problem instances. Thereby, one of the proposed strategies proves to be very successful, obtaining (near-to-)optimal solutions in a reasonable computational time for the problem instances of realistic size. Furthermore, we compare the novel integrated truck and workforce scheduling approach with existing successive methods that solve the personnel assignment and the truck scheduling problem sequentially. The results show that compared to the existing approaches, the novel integrated planning approach can significantly improve the terminal's performance for both representative settings.
The second article focuses on operations in the shipping area and deals with the loading and scheduling of outbound trucks. More precisely, the planning problem deals with the following decisions: assigning shipments with varying sizes to outgoing trucks considering the trailers' limited loading capacity, and scheduling the trucks' loading processes at the gates considering the given time windows and limited terminal workforce—required to load the shipments into trucks. Such a planning problem arises at cargo facilities where the goods are consolidated on the outbound side. An important example of such facilities is dispatch warehouses of part suppliers (e.g., in the automotive industry), from which multiple trucks depart towards the same destination each day. Such dispatch warehouses are primarily implemented to deliver readily usable parts to the assembly plant in a just-in-time or sometimes even just-in-sequence manner. Therefore, the objective of the proposed optimization problem is to ship the ordered parts as late as possible, but not later than their deadlines at the assembly line.
We formalize the resulting planning problem as a mathematical optimization problem and design two different mixed-integer linear programming models. Furthermore, we reformulate the optimization problem as the well-known generalized set covering problem, which we use as the basis for the column generation method, and design an exact branch-and-price algorithm. In series of numerical tests, we observe the computational performance of the proposed three solution approaches (i.e., two MILP models using the standard solver, and the exact branch-and-price algorithm) on newly generated large problem instances. Our results show that the branch-and-price algorithm outperforms both MILP models, obtaining optimal solutions for most of the considered problem instances in a short computational time. Moreover, we explore some managerial insights, such as the influence of the time window management and workforce amount on delivery punctuality. Our findings can be useful for terminal managers when designing a suitable time window management system or seeking the proper workforce amount at the tactical planning level.
The third article covers the activities within the trailer yard, i.e., outside the terminal building. Many large trailer terminals use specialized yard tractors (often called spotters or switchers) to transport semitrailers within the yard. This way, a new planning problem arises, associated with coordinating the intra-yard trailer movement among multiple spotters. In the third paper, we introduce a novel spotter scheduling problem that has to be solved in the planning hierarchy after defining the particular gate and the docking time for each trailer (i.e., after solving the truck scheduling problem). Our robust spotter scheduling problem assigns a set of given trailer movements to spotters such that the predefined truck schedules can be realized on time—even if unexpected delays occur in the trailer yard. We insert a buffer time between any pair of consecutive transportation requests and aim to keep it as large as possible to protect the system from propagating small delays. We propose two problem variants of the robust spotter scheduling problem, which differ in their objectives. The first problem version maximizes the weighted sum of buffer times (max-sum), and the second one the minimum weighted buffer time (max-min).
For each problem variant, we develop an exact algorithm that finds the optimal solution in polynomial time for the related optimization problem. Our approaches show an outstanding algorithmic performance in computational tests, optimally solving instances with thousands of transport requests and hundreds of spotters in short computational time. Besides, we evaluate the robustness of the proposed approaches in a simulation study. Specifically, we simulate some uncertain events at the terminal, such as delays in truck arrivals and handling processes at the loading gates, and examine whether the solutions found by the proposed approaches are indeed robust. The results show that applying a suitable robustness measure (i.e., max-min) can significantly reduce the propagation of unforeseen delays. Finally, we also observe the interrelation between the two objectives and explore the impact of the spotter fleet size on the yard performance. The latter study's findings can be a useful insight for mid-term planning when seeking an appropriate number of spotters to achieve the desired service level.
In contrast to the three previous papers, each dealing with the specific application problems, the fourth paper primarily focuses on algorithmics. Its main contribution is a novel exact algorithm, based on the combinatorial (or logic-based) Benders decomposition scheme, that can be applied to optimally solve a broader class of scheduling problems. In particular, the fundamental optimization problem is to schedule a set of jobs with release dates and deadlines on a set of unrelated parallel machines minimizing some min-max objective. Such types of machine scheduling problems have a wide range of applications for various scheduling problems in production and logistics, including truck scheduling problems. In the truck scheduling context, a job (with the release date and the deadline) corresponds to a truck (with the arrival and the departure time), and a machine to a gate that can process at most one job at a time. Apart from the exact Benders decomposition algorithm, we propose a heuristic algorithm that relies on a reformulation of the optimization problem as the well-known generalized set partitioning problem. We design the algorithms for three different minimax objective functions: minimizing the completion time of the last job (i.e., makespan), the maximum weighted flow time, and the maximum weighted lateness. Besides, we reveal how to modify the proposed algorithms for several problem-relevant extensions. We test the computational performance of the provided solution techniques in an extensive computational study on both newly generated random problem instances and existing instance sets available in the literature. The novel exact Benders decomposition approach performs quite well, solving most problem instances to proven optimality within short computational time. The proposed heuristic also does a good job, successfully providing near-optimal solutions in a reasonable time for particularly tricky problem instances with tight time windows.
| Typ des Eintrags: | Dissertation | ||||
|---|---|---|---|---|---|
| Erschienen: | 2021 | ||||
| Autor(en): | Tadumadze, Giorgi | ||||
| Art des Eintrags: | Erstveröffentlichung | ||||
| Titel: | Integrating Workforce Scheduling Aspects into Daily Operations at Trailer Terminals with a Special Focus on Loading and Unloading of Trucks | ||||
| Sprache: | Englisch | ||||
| Referenten: | Emde, Prof. Dr. Simon ; Glock, Prof. Dr. Christoph | ||||
| Publikationsjahr: | 2021 | ||||
| Ort: | Darmstadt | ||||
| Kollation: | xx, 187 Seiten | ||||
| Datum der mündlichen Prüfung: | 15 Dezember 2020 | ||||
| DOI: | 10.26083/tuprints-00017583 | ||||
| URL / URN: | https://tuprints.ulb.tu-darmstadt.de/17583 | ||||
| Kurzbeschreibung (Abstract): | The cumulative dissertation at hand consists of four research papers, three of which have already been published in scientific journals. The fourth is under review to be published in another international journal. All four articles deal with the combinatorial optimization problems that arise through integrating personnel scheduling factors into operative planning at cargo handling facilities. More precisely, the considered planning problems are related to trucks' unloading and loading processes at massive transshipment terminals, crucial nodes for many modern transportation networks. Examples for such large trailer terminals can be distribution centers or cross-docks (e.g., in the food or automotive industry), hub terminals in the postal sector, etc. At such cargo facilities, hundreds of trucks are coordinated daily. In particular, goods are unloaded from incoming trucks, possibly stored for a while, consolidated, and loaded into outgoing trucks. Typically, a terminal building of such cargo facility consists of several gates (or dock doors), where trucks are docked while goods are unloaded or loaded into the trailer. One crucial planning problem at such facilities is to schedule trucks' loading and unloading processes at the terminal gates. The planning problem that determines on at which door and in which time interval each truck has to be (un-)loaded is called truck scheduling problem. Although trailers' (un-)loading activities at the gates usually require worker's involvement, the integration of personnel planning aspects into truck scheduling problems has only received little attention in the scientific literature. The focus of this thesis is to integrate workforce planning into truck scheduling problems. The planning problems proposed in the presented articles differ in spatial aspects where the respective operations take place. They include activities at the gates in both the receiving and the shipping areas of the facility as well as activities within the terminal yard, i.e., outside the terminal building. Furthermore, as discussed below, these four papers apply different methodologies to solve the corresponding optimization problems. The first paper focuses on inbound operations, i.e., in the receiving area of the cargo facility. We introduce a novel integrated workforce and truck scheduling problem, where incoming trucks with strict arrival and departure times are unloaded at the dock doors by a varying number of terminal employees. The duration of the trailer's unloading depends not only on the specific truckload but also on the number of workers jointly unloading it. It is worth mentioning that most existing models widely ignore the latter phenomenon by assuming constant handling times for each truck. That represents the case where a fixed number of employees are preassigned to each dock door in advance. In practice, however, terminal managers have additional flexibility in assigning a diverse number of employees to each truck, depending on the degree of its actual urgency. Since a higher number of employees speeds up the handling time, it is reasonable to solve the personnel assignment and truck scheduling problem holistically. We examine the integrated planning approach for two representative truck scheduling settings: a conventional distribution center and a cross-docking terminal. The resulting two optimization problems differ from each other in their objectives. The former's objective is to minimize the total flow-time (i.e., the total time a truck spends at the terminal, including the waiting time before the actual unloading process). In the cross-docking environment, the goods are directly moved towards the corresponding outbound trucks without any (extended) intermediate storage in the terminal. Hence, the latter problem aims to schedule the incoming trucks at the inbound gates in such a way that the unloaded goods can be transferred to the corresponding outbound trucks on time. More precisely, the truck scheduling problem in the cross-docking setting minimizes the number of delayed shipments that cannot reach the dedicated outbound trucks before the scheduled departure time. After formalizing the planning problems as mathematical optimization problems, we develop a mixed-integer linear optimization programming model for each setting. Moreover, we provide an alternative problem reformulation as the interval scheduling problem. Based on this, we design various heuristic solution procedures, which are different in terms of the interval generation process in the model preparation phase. We test the algorithmic performance of the proposed solution approaches using newly generated problem instances. Thereby, one of the proposed strategies proves to be very successful, obtaining (near-to-)optimal solutions in a reasonable computational time for the problem instances of realistic size. Furthermore, we compare the novel integrated truck and workforce scheduling approach with existing successive methods that solve the personnel assignment and the truck scheduling problem sequentially. The results show that compared to the existing approaches, the novel integrated planning approach can significantly improve the terminal's performance for both representative settings. The second article focuses on operations in the shipping area and deals with the loading and scheduling of outbound trucks. More precisely, the planning problem deals with the following decisions: assigning shipments with varying sizes to outgoing trucks considering the trailers' limited loading capacity, and scheduling the trucks' loading processes at the gates considering the given time windows and limited terminal workforce—required to load the shipments into trucks. Such a planning problem arises at cargo facilities where the goods are consolidated on the outbound side. An important example of such facilities is dispatch warehouses of part suppliers (e.g., in the automotive industry), from which multiple trucks depart towards the same destination each day. Such dispatch warehouses are primarily implemented to deliver readily usable parts to the assembly plant in a just-in-time or sometimes even just-in-sequence manner. Therefore, the objective of the proposed optimization problem is to ship the ordered parts as late as possible, but not later than their deadlines at the assembly line. We formalize the resulting planning problem as a mathematical optimization problem and design two different mixed-integer linear programming models. Furthermore, we reformulate the optimization problem as the well-known generalized set covering problem, which we use as the basis for the column generation method, and design an exact branch-and-price algorithm. In series of numerical tests, we observe the computational performance of the proposed three solution approaches (i.e., two MILP models using the standard solver, and the exact branch-and-price algorithm) on newly generated large problem instances. Our results show that the branch-and-price algorithm outperforms both MILP models, obtaining optimal solutions for most of the considered problem instances in a short computational time. Moreover, we explore some managerial insights, such as the influence of the time window management and workforce amount on delivery punctuality. Our findings can be useful for terminal managers when designing a suitable time window management system or seeking the proper workforce amount at the tactical planning level. The third article covers the activities within the trailer yard, i.e., outside the terminal building. Many large trailer terminals use specialized yard tractors (often called spotters or switchers) to transport semitrailers within the yard. This way, a new planning problem arises, associated with coordinating the intra-yard trailer movement among multiple spotters. In the third paper, we introduce a novel spotter scheduling problem that has to be solved in the planning hierarchy after defining the particular gate and the docking time for each trailer (i.e., after solving the truck scheduling problem). Our robust spotter scheduling problem assigns a set of given trailer movements to spotters such that the predefined truck schedules can be realized on time—even if unexpected delays occur in the trailer yard. We insert a buffer time between any pair of consecutive transportation requests and aim to keep it as large as possible to protect the system from propagating small delays. We propose two problem variants of the robust spotter scheduling problem, which differ in their objectives. The first problem version maximizes the weighted sum of buffer times (max-sum), and the second one the minimum weighted buffer time (max-min). For each problem variant, we develop an exact algorithm that finds the optimal solution in polynomial time for the related optimization problem. Our approaches show an outstanding algorithmic performance in computational tests, optimally solving instances with thousands of transport requests and hundreds of spotters in short computational time. Besides, we evaluate the robustness of the proposed approaches in a simulation study. Specifically, we simulate some uncertain events at the terminal, such as delays in truck arrivals and handling processes at the loading gates, and examine whether the solutions found by the proposed approaches are indeed robust. The results show that applying a suitable robustness measure (i.e., max-min) can significantly reduce the propagation of unforeseen delays. Finally, we also observe the interrelation between the two objectives and explore the impact of the spotter fleet size on the yard performance. The latter study's findings can be a useful insight for mid-term planning when seeking an appropriate number of spotters to achieve the desired service level. In contrast to the three previous papers, each dealing with the specific application problems, the fourth paper primarily focuses on algorithmics. Its main contribution is a novel exact algorithm, based on the combinatorial (or logic-based) Benders decomposition scheme, that can be applied to optimally solve a broader class of scheduling problems. In particular, the fundamental optimization problem is to schedule a set of jobs with release dates and deadlines on a set of unrelated parallel machines minimizing some min-max objective. Such types of machine scheduling problems have a wide range of applications for various scheduling problems in production and logistics, including truck scheduling problems. In the truck scheduling context, a job (with the release date and the deadline) corresponds to a truck (with the arrival and the departure time), and a machine to a gate that can process at most one job at a time. Apart from the exact Benders decomposition algorithm, we propose a heuristic algorithm that relies on a reformulation of the optimization problem as the well-known generalized set partitioning problem. We design the algorithms for three different minimax objective functions: minimizing the completion time of the last job (i.e., makespan), the maximum weighted flow time, and the maximum weighted lateness. Besides, we reveal how to modify the proposed algorithms for several problem-relevant extensions. We test the computational performance of the provided solution techniques in an extensive computational study on both newly generated random problem instances and existing instance sets available in the literature. The novel exact Benders decomposition approach performs quite well, solving most problem instances to proven optimality within short computational time. The proposed heuristic also does a good job, successfully providing near-optimal solutions in a reasonable time for particularly tricky problem instances with tight time windows. |
||||
| Alternatives oder übersetztes Abstract: |
|
||||
| Status: | Verlagsversion | ||||
| URN: | urn:nbn:de:tuda-tuprints-175832 | ||||
| Sachgruppe der Dewey Dezimalklassifikatin (DDC): | 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik 300 Sozialwissenschaften > 330 Wirtschaft 500 Naturwissenschaften und Mathematik > 510 Mathematik |
||||
| Fachbereich(e)/-gebiet(e): | 01 Fachbereich Rechts- und Wirtschaftswissenschaften > Betriebswirtschaftliche Fachgebiete > Fachgebiet Management Science / Operations Research 01 Fachbereich Rechts- und Wirtschaftswissenschaften 01 Fachbereich Rechts- und Wirtschaftswissenschaften > Betriebswirtschaftliche Fachgebiete |
||||
| Hinterlegungsdatum: | 24 Mär 2021 07:17 | ||||
| Letzte Änderung: | 29 Mär 2021 09:14 | ||||
| PPN: | |||||
| Referenten: | Emde, Prof. Dr. Simon ; Glock, Prof. Dr. Christoph | ||||
| Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: | 15 Dezember 2020 | ||||
| Export: | |||||
| Suche nach Titel in: | TUfind oder in Google | ||||
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum