×

Optimizing consolidation processes in hubs: the hub-arrival-departure problem. (English) Zbl 1490.90133

Summary: To realize economies of scale in transportation, hubs are important entities in today’s distribution networks. Hubs, such as cross docks for trucks, central ports for container vessels, transshipment yards for freight trains, and air hubs for airplanes, allow to consolidate less-than-vehicle-load shipments and to improve the utilization of transport capacities. In this context, we consider a generic optimization problem to streamline hub processes. We assign vehicles consolidating their shipments at a central hub each an arrival time slot where a vehicle is unloaded and a later departure time slot where it is loaded with the goods it takes back to its designated territory. Since the processing of goods inside a hub terminal takes some time, we want to synchronize the exchange of goods among vehicles such that three different consolidation-oriented objectives are optimized. For instance, we aim to minimize the number of goods missing their dedicated departures after a fixed consolidation time for goods inside the hub. We prove important structural properties, provide a comprehensive analysis of computational complexity, and derive suited solution procedures. Our problem occurs in the real world at the air hub of postal service provider DHL in Leipzig, where freight airplanes from all over the world exchange goods and need to be assigned landing and departure slots on the runway. Our problem, however, is generic, and we sketch some extensions in order to adapt it to further hubs.

MSC:

90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management
Full Text: DOI

References:

[1] Bennell, J. A.; Mesgarpour, M.; Potts, C. N., Airport runway scheduling, Annals of Operations Research, 204, 1, 249-270 (2013) · Zbl 1269.90039
[2] Bierwirth, C.; Meisel, F., A survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research, 202, 3, 615-627 (2010) · Zbl 1176.90373
[3] Bierwirth, C.; Meisel, F., A follow-up survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research, 244, 3, 675-689 (2015) · Zbl 1346.90326
[4] Boysen, N., Truck scheduling at zero-inventory cross docking terminals, Computers Operations Research, 37, 1, 32-41 (2010) · Zbl 1171.90391
[5] Boysen, N.; Emde, S.; Stephan, K.; Weiß, M., Synchronization in hub terminals with the circular arrangement problem, Naval Research Logistics, 62, 6, 454-469 (2015) · Zbl 1411.90043
[6] Boysen, N.; Fliedner, M., Cross dock scheduling: Classification, literature review and research agenda, Omega, 38, 6, 413-422 (2010)
[7] Boysen, N.; Fliedner, M., Scheduling aircraft landings to balance workload of ground staff, Computers & Industrial Engineering, 60, 2, 206-217 (2011)
[8] Boysen, N.; Fliedner, M.; Jaehn, F.; Pesch, E., A survey on container processing in railway yards, Transportation Science, 47, 3, 312-329 (2013)
[9] Boysen, N.; Fliedner, M.; Scholl, A., Scheduling inbound and outbound trucks at cross docking terminals, OR Spectrum, 32, 1, 135-161 (2010) · Zbl 1181.90111
[10] Boysen, N.; Jaehn, F.; Pesch, E., Scheduling freight trains in rail-rail transshipment yards, Transportation Science, 45, 2, 199-211 (2011)
[11] Briskorn, D.; Choi, B.-C.; Lee, K.; Leung, J.; Pinedo, M., Complexity of single machine scheduling subject to nonnegative inventory constraints, European Journal of Operational Research, 207, 2, 605-619 (2010) · Zbl 1205.90115
[12] (to appear) · Zbl 1466.90006
[13] Briskorn, D.; Jaehn, F.; Pesch, E., Exact algorithms for inventory constrained scheduling on a single machine, Journal of Scheduling, 16, 1, 105-115 (2013) · Zbl 1297.90065
[14] Briskorn, D.; Leung, J., Minimizing maximum lateness of jobs in inventory constrained scheduling, Journal of the Operational Research Society, 64, 12, 1851-1864 (2013)
[15] Caprara, A.; Galli, L.; Toth, P., Solution of the train platforming problem, Transportation Science, 45, 2, 246-257 (2011)
[16] Chiarello, A.; Gaudioso, M.; Sammarra, M., Truck synchronization at single door cross-docking terminals, OR Spectrum, 40, 2, 395-447 (2018) · Zbl 1397.90171
[17] Dorndorf, U.; Drexl, A.; Nikulin, Y.; Pesch, E., Flight gate scheduling: State-of-the-art and recent developments, Omega, 35, 3, 326-334 (2007)
[18] Dorndorf, U.; Jaehn, F.; Pesch, E., Modelling robust flight-gate scheduling as a clique partitioning problem, Transportation Science, 42, 3, 292-301 (2008)
[19] Emde, S.; Boysen, N., Berth allocation in container terminals that service feeder ships and deep-sea vessels, Journal of the Operational Research Society, 67, 4, 551-563 (2016)
[20] Fedtke, S.; Boysen, N., Layout planning of sortation conveyors in parcel distribution centers, Transportation Science, 51, 1, 3-18 (2017)
[21] Gerbner, D.; Keszegh, B.; Palmer, C.; Palvölgyi, D., Topological orderings of weighted directed acyclic graphs, Information Processing Letters, 116, 9, 564-568 (2016) · Zbl 1358.05132
[22] Guo, P.; Weidinger, F.; Boysen, N., Parallel machine scheduling with job synchronization to enable efficient material flows in hub terminals, Omega, 89, 110-121 (2019)
[23] Kuhn, H. W., The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2, 1-2, 83-97 (1955) · Zbl 0143.41905
[24] Leung, J. Y.-T.; Vornberger, O.; Witthoff, J. D., On some variants of the bandwidth minimization problem, SIAM Journal on Computing, 13, 3, 650-667 (1984) · Zbl 0545.68058
[25] O’Kelly, M. E., Routing traffic at hub facilities, Networks and Spatial Economics, 10, 2, 173-191 (2010) · Zbl 1187.90075
[26] Papadimitriou, C. H., The NP-completeness of the bandwidth minimization problem, Computing, 16, 177-192 (1976)
[27] Steenken, D.; Voß, S.; Stahlbock, R., Container terminal operation and operations research-a classification and literature review, OR Spectrum, 26, 1, 3-49 (2004) · Zbl 1160.90322
[28] Tsui, L. Y.; Chang, C.-H., A microcomputer based decision support tool for assigning dock doors in freight yards, Computers & Industrial Engineering, 19, 309-312 (1990)
[29] Van Belle, J.; Valckenaers, P.; Cattrysse, D., Cross-docking: State of the art, Omega, 40, 6, 827-846 (2012)
[30] Wikum, E. D.; Llewellyn, D. C.; Nemhauser, G. L., One-machine generalized precedence constrained scheduling problems, Operations Research Letters, 16, 87-99 (1994) · Zbl 0823.90066
[31] Yu, W.; Egbelu, P. J., Scheduling of inbound and outbound trucks in cross docking systems with temporary storage, European Journal of Operational Research, 184, 1, 377-396 (2008) · Zbl 1278.90177
[32] Yu, W.; Hoogeveen, H.; Lenstra, J. K., Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard, Journal of Scheduling, 7, 333-348 (2004) · Zbl 1154.90506
[33] Zhen, L.; Chew, E. P.; Lee, L. H., An integrated model for berth template and yard template planning in transshipment hubs, Transportation Science, 45, 4, 483-504 (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.