Truck scheduling optimization in the logistics of crossdocking

• Main Author: Shakeri, Mojtaba
• Other Authors: Eng Wah Lee
• Format: Theses and Dissertations
• Language: English
• Published: 2013
• Subjects: DRNTU::Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/54632
• Institution: Nanyang Technological University

Crossdocking is a warehousing strategy that moves products through flow consolidation centers or crossdocks without putting them into storage. The practice not only brings substantial reduction in the distribution cost but also shortens the product delivery time. This thesis addresses an important crossdocking planning operation which is the scheduling of trucks at the crossdocking facilities of the fast moving consumer goods (FMCG) industry and military logistics. The truck scheduling problem in this scenario decides on the sequence of a number of trucks that are to exchange some of their products at the dock doors of a crossdocking terminal. The decision is subject to the availability of the crossdock critical resources including dock doors and forklifts, whose allocation is considered non-preemptive. The non-preemptive assignment of trailers to dock doors makes it necessary to address the truck scheduling solution feasibility before its optimality as the problem might be entrapped in deadlock and no feasible solution is produced. In the first place, an exact (optimal) mixed integer programming (MIP) model is developed to mathematically represent the crossdocking model and its associated truck scheduling problem. The objective function applied is to minimize the total crossdocking operation time (also referred to as makespan) starting when the first trailer is assigned to a door and ending when the last trailer releases its assigned door. Since there is no real data available to evaluate the formulated problem, synthetic data is generated based on the characteristics of a wide range of real-world crossdocking practices. The data set includes problem instances of different levels of difficulty representing small crossdocks hosting a few dozen trailers to huge ones hosting over 2000 trailers. As the mathematical approach is impractical for solving real size problem instances, sub-optimal (heuristic) algorithms are developed alternatively. The first step addresses the feasibility of the truck scheduling problem by proposing a two-phase heuristic algorithm where in the first phase, a dependency ranking search (DRS) heuristic is deployed to construct a feasible sequence of trucks for the assignment to dock doors and in the second phase, a door fitness (DF) heuristic is implemented to assign each sequenced truck to a proper dock door, subject to a limited number of forklifts, such that significant savings in the total crossdocking operation time are achieved. The efficiency of the proposed algorithm in establishing solution feasibility is evaluated against the exact mathematical model of the problem and a constructive dependency ranking (DR) heuristic developed for a similar truck scheduling problem. Experimental results show that the DRS algorithm is robust in avoiding deadlock and generates feasible solutions for the instances where the other two approaches cannot. It is also observed that re-starting DRS from a few initial points to generate a number of trailer sequence lists can noticeably improve the solution quality. The last step addresses the optimality of the truck scheduling problem by developing two meta-heuristics to improve the initial heuristics solutions: tabu search (TS) and variable neighborhood search (VNS). The search space of the problem is formed by changing the sequence of trailers for the door assignment. As a neighborhood search method, each meta-heuristic is supplemented by a fractional evaluation of the neighborhood so that the runtime is more efficiently dedicated to solution optimization. The experimental results demonstrate that the fractional evaluation significantly reduces the solution assessment time. The experimentation continues by tuning the control parameters of the two meta-heuristics so that the trade-off between solution quality and runtime can be properly balanced. The TS and VNS algorithms are then invoked to improve the DRS+DF solutions. The analysis shows a consistent reduction in the makespan in reasonable running times for different characteristics of the experimental data. Further robustness and increase in the solution quality are achieved when the two meta-heuristics are initialized with a better initial solution obtained by the re-starting version of the DRS algorithm.