The paper describes a Lagrangian heuristic algorithm for a cross-docking problem, where given amounts of several products must be directly transshipped from a given set of inbound trucks to a given set of outbound trucks. The cross-docking centre is equipped with some inbound and outbound doors (or gates), where the discharging/loading activities, which are assumed to require a constant time for each truck, take place. The objective is to schedule the activities and to design the transshipment plan, while minimizing the ending time of the whole process. Moving along a research line recently traced for the single-door case, the main contribution of the paper is the Lagrangian decomposition scheme for the structured integer linear model of the problem. In particular, decomposition in three subproblems is provided. For all such problems effective solution algorithms are proposed. Two repairing heuristics are embedded into the algorithm for tackling the Lagrangian dual, thus allowing calculation of both lower and upper bounds on the optimal objective function. The performance of the algorithm is evaluated through extensive computational experiments on instances of different typologies in terms of number of gates, trucks and products.

A Lagrangian heuristics for the truck scheduling problem in multi-door, multi-product Cross-Docking with constant processing time

Manlio Gaudioso;Maria Flavia Monaco
;
In corso di stampa

Abstract

The paper describes a Lagrangian heuristic algorithm for a cross-docking problem, where given amounts of several products must be directly transshipped from a given set of inbound trucks to a given set of outbound trucks. The cross-docking centre is equipped with some inbound and outbound doors (or gates), where the discharging/loading activities, which are assumed to require a constant time for each truck, take place. The objective is to schedule the activities and to design the transshipment plan, while minimizing the ending time of the whole process. Moving along a research line recently traced for the single-door case, the main contribution of the paper is the Lagrangian decomposition scheme for the structured integer linear model of the problem. In particular, decomposition in three subproblems is provided. For all such problems effective solution algorithms are proposed. Two repairing heuristics are embedded into the algorithm for tackling the Lagrangian dual, thus allowing calculation of both lower and upper bounds on the optimal objective function. The performance of the algorithm is evaluated through extensive computational experiments on instances of different typologies in terms of number of gates, trucks and products.
Heuristics Cross-docking Lagrangian decomposition Scheduling
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/302981
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? ND
social impact