In this talk, we address a truck scheduling problem in a cross-docking terminal, where products arriving by inbound trucks, are arranged with respect to retailers' requirements and directly loaded into the outbound trucks, without being stored inside the terminal. We assume that two docking gates are available, one for the unloading and the other for loading operations, and that the amount of products to be transferred from the inbound to the outbound trucks are known. The objective is to minimize the overall completion time of the operations (makespan). For this basic problem, we propose a new Mixed Integer Linear Programming formulation and a Lagrangian relaxation approach. We show that the Lagrangian relaxed problem decomposes in three structured combinatorial sub-problems, concerning, respectively, the scheduling of trucks at the inbound and outbound gates, and the transhipment flow among the trucks. We propose effective solution algorithms for all the subproblems. These algorithms are enclosed within a multiplier adjustment scheme, equipped with a repairing heuristic aimed at computing feasible solutions for the original problem, starting from the solutions of the relaxed problem. Therefore, the resulting procedure is able to compute both lower bounds of increasing value and many feasible solutions, among which to choose the best one. Finally, we discuss some preliminary numerical results.
Modelling and solving a truck scheduling and transhipment problem in a cross-docking terminal
2019
Abstract
In this talk, we address a truck scheduling problem in a cross-docking terminal, where products arriving by inbound trucks, are arranged with respect to retailers' requirements and directly loaded into the outbound trucks, without being stored inside the terminal. We assume that two docking gates are available, one for the unloading and the other for loading operations, and that the amount of products to be transferred from the inbound to the outbound trucks are known. The objective is to minimize the overall completion time of the operations (makespan). For this basic problem, we propose a new Mixed Integer Linear Programming formulation and a Lagrangian relaxation approach. We show that the Lagrangian relaxed problem decomposes in three structured combinatorial sub-problems, concerning, respectively, the scheduling of trucks at the inbound and outbound gates, and the transhipment flow among the trucks. We propose effective solution algorithms for all the subproblems. These algorithms are enclosed within a multiplier adjustment scheme, equipped with a repairing heuristic aimed at computing feasible solutions for the original problem, starting from the solutions of the relaxed problem. Therefore, the resulting procedure is able to compute both lower bounds of increasing value and many feasible solutions, among which to choose the best one. Finally, we discuss some preliminary numerical results.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
