Skip to main content
Erschienen in: OR Spectrum 2/2013

01.03.2013 | Regular Article

Truck scheduling in cross-docking terminals with fixed outbound departures

verfasst von: Nils Boysen, Dirk Briskorn, Martin Tschöke

Erschienen in: OR Spectrum | Ausgabe 2/2013

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

At a cross-docking terminal, inbound shipments are directly transshipped across the terminal to designated outbound trucks, so that delays and inventories are kept as low as possible. We consider an operational truck scheduling problem, where a dock door and a start time have to be assigned to each inbound truck. A set of outbound trucks is scheduled beforehand and, therefore, departure times are fixed. If a shipment is not unloaded, transshipped to the outbound gate and loaded onto the designated outbound truck before its departure, we consider the shipments’s value as lost profit. The objective is to minimize total lost profit. This paper at hand formalizes the resulting truck scheduling problem. We settle its computational complexity and develop heuristics (namely, decomposition procedures and simulated annealing) in order to tackle the problem. We show the efficiency of these heuristics by means of a computational study. Last but not least, a case study is presented.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
Zurück zum Zitat Aarts, E., Korst, J., van Laarhoven, J.: Simulated annealing. In: Aarts, E., Lenstra, J. (eds.) Local Search in Combinatorial, Optimization, pp. 91–120 (1997) Aarts, E., Korst, J., van Laarhoven, J.: Simulated annealing. In: Aarts, E., Lenstra, J. (eds.) Local Search in Combinatorial, Optimization, pp. 91–120 (1997)
Zurück zum Zitat Boysen N (2010) Truck scheduling at zero-inventory crossdocking terminals. Comput. Oper. Res. 37:32–41CrossRef Boysen N (2010) Truck scheduling at zero-inventory crossdocking terminals. Comput. Oper. Res. 37:32–41CrossRef
Zurück zum Zitat Boysen N, Fliedner M (2010) Cross dock scheduling: classification, literature review and research agenda. Omega 38:413–422CrossRef Boysen N, Fliedner M (2010) Cross dock scheduling: classification, literature review and research agenda. Omega 38:413–422CrossRef
Zurück zum Zitat Boysen N, Fliedner M, Scholl A (2010) Scheduling inbound and outbound trucks at cross docking terminals. OR Spect. 32:135–161CrossRef Boysen N, Fliedner M, Scholl A (2010) Scheduling inbound and outbound trucks at cross docking terminals. OR Spect. 32:135–161CrossRef
Zurück zum Zitat Briskorn D, Choi B-C, Lee K, Leung J, Pinedo M (2010) Complexity of single machine scheduling subject to nonnegative inventory constraints. Eur. J. Oper. Res. 207(2):605–619CrossRef Briskorn D, Choi B-C, Lee K, Leung J, Pinedo M (2010) Complexity of single machine scheduling subject to nonnegative inventory constraints. Eur. J. Oper. Res. 207(2):605–619CrossRef
Zurück zum Zitat Brucker P (2004) Sched. Algorithms. Springer, Berlin Brucker P (2004) Sched. Algorithms. Springer, Berlin
Zurück zum Zitat Chen F, Lee C-Y (2009) Minimizing the makespan in a two-machine cross-docking flow shop problem. Eur. J. Oper. Res. 193:59–72CrossRef Chen F, Lee C-Y (2009) Minimizing the makespan in a two-machine cross-docking flow shop problem. Eur. J. Oper. Res. 193:59–72CrossRef
Zurück zum Zitat Chen F, Song K (2009) Minimizing makespan in two-stage hybrid cross docking scheduling problem. Comput. Oper. Res. 36:2066–2073CrossRef Chen F, Song K (2009) Minimizing makespan in two-stage hybrid cross docking scheduling problem. Comput. Oper. Res. 36:2066–2073CrossRef
Zurück zum Zitat Chen Z, Powell W (1999) Solving parallel machine scheduling problems by column generation. Informs J. Comput. 11:78–94CrossRef Chen Z, Powell W (1999) Solving parallel machine scheduling problems by column generation. Informs J. Comput. 11:78–94CrossRef
Zurück zum Zitat Forger, G.: Ups starts world’s premiere cross-docking operation. In: Modern Material Handling, pp. 36–38 (1995) Forger, G.: Ups starts world’s premiere cross-docking operation. In: Modern Material Handling, pp. 36–38 (1995)
Zurück zum Zitat Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimisation and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5:236–287 Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimisation and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5:236–287
Zurück zum Zitat Gue K (1999) The effect of trailer scheduling on the layout of freight terminals. Transp. Sci. 33:419–428CrossRef Gue K (1999) The effect of trailer scheduling on the layout of freight terminals. Transp. Sci. 33:419–428CrossRef
Zurück zum Zitat Held M, Karp R (1962) A dynamic programming approach to sequencing problems. SIAM J. 10:196–210CrossRef Held M, Karp R (1962) A dynamic programming approach to sequencing problems. SIAM J. 10:196–210CrossRef
Zurück zum Zitat Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems, 1st edn. Springer, BerlinCrossRef Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems, 1st edn. Springer, BerlinCrossRef
Zurück zum Zitat Kirkpatrick S, Gelatt CD, Vecchi MPGR (1983) Optimization by simulated annealing. Sci. New Series 220(4598):671–680 Kirkpatrick S, Gelatt CD, Vecchi MPGR (1983) Optimization by simulated annealing. Sci. New Series 220(4598):671–680
Zurück zum Zitat Lawler E (1977) A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. Ann. Discrete Math. 1:331–342CrossRef Lawler E (1977) A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. Ann. Discrete Math. 1:331–342CrossRef
Zurück zum Zitat Lowerre, B T (1976) The HARPY Speech Recognition System. PhD thesis, Carnegie-Mellon University, USA Lowerre, B T (1976) The HARPY Speech Recognition System. PhD thesis, Carnegie-Mellon University, USA
Zurück zum Zitat M’Hallah R, Bulfin R (2005) Minimizing the weighted number of tardy jobs on parallel processors. Eur. J. Oper. Res. 160(2):471–484CrossRef M’Hallah R, Bulfin R (2005) Minimizing the weighted number of tardy jobs on parallel processors. Eur. J. Oper. Res. 160(2):471–484CrossRef
Zurück zum Zitat Miao Z, Lim A, Ma H (2009) Truck dock assignment with operational time constraint within crossdocks. Eur. J. Oper. Res. 192(1):105–115CrossRef Miao Z, Lim A, Ma H (2009) Truck dock assignment with operational time constraint within crossdocks. Eur. J. Oper. Res. 192(1):105–115CrossRef
Zurück zum Zitat Ow P, Morton T (1988) Filtered beam search in scheduling. Int. J. Prod. Res. 26:35–62CrossRef Ow P, Morton T (1988) Filtered beam search in scheduling. Int. J. Prod. Res. 26:35–62CrossRef
Zurück zum Zitat Sabuncuoglu I, Gocgun Y, Erel E (2008) Backtracking and exchange of information: methods to enhance a beam search algorithm for assembly line scheduling. Eur. J. Oper. Res. 186:915–930CrossRef Sabuncuoglu I, Gocgun Y, Erel E (2008) Backtracking and exchange of information: methods to enhance a beam search algorithm for assembly line scheduling. Eur. J. Oper. Res. 186:915–930CrossRef
Zurück zum Zitat Stalk G, Evans P, Shulman L (1992) Competing on capabilities: the new role of corporate strategy. Harvard Bus. Rev. 70(2):57–69 Stalk G, Evans P, Shulman L (1992) Competing on capabilities: the new role of corporate strategy. Harvard Bus. Rev. 70(2):57–69
Zurück zum Zitat Van den Akker J, Hoogeveen J, Van de Velde S (1999) Parallel machine scheduling by column generation. Oper. Res. 47:862–872CrossRef Van den Akker J, Hoogeveen J, Van de Velde S (1999) Parallel machine scheduling by column generation. Oper. Res. 47:862–872CrossRef
Zurück zum Zitat Witt C (1998) Crossdocking: concepts demand choice. Mater. Handl. Eng. 53(7):44–49 Witt C (1998) Crossdocking: concepts demand choice. Mater. Handl. Eng. 53(7):44–49
Zurück zum Zitat Yu W, Egbelu PJ (2008) Scheduling of inbound and outbound trucks in cross docking systems with temporary storage. Eur. J. Oper. Res. 184:377–396CrossRef Yu W, Egbelu PJ (2008) Scheduling of inbound and outbound trucks in cross docking systems with temporary storage. Eur. J. Oper. Res. 184:377–396CrossRef
Metadaten
Titel
Truck scheduling in cross-docking terminals with fixed outbound departures
verfasst von
Nils Boysen
Dirk Briskorn
Martin Tschöke
Publikationsdatum
01.03.2013
Verlag
Springer-Verlag
Erschienen in
OR Spectrum / Ausgabe 2/2013
Print ISSN: 0171-6468
Elektronische ISSN: 1436-6304
DOI
https://doi.org/10.1007/s00291-012-0311-6

Weitere Artikel der Ausgabe 2/2013

OR Spectrum 2/2013 Zur Ausgabe