A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock

This paper studies truck scheduling in a resource-constrained crossdock. The problem decides on the sequence of incoming and outgoing trucks at the dock doors of the crossdocking terminal, subject to the availability of crossdock resources including dock doors and material handling systems. The reso...

Full description

Saved in:
Bibliographic Details
Main Authors: Shakeri, Mojtaba., Low, Malcolm Yoke Hean., Turner, Stephen John., Lee, Eng Wah.
Other Authors: School of Computer Engineering
Format: Article
Language:English
Published: 2013
Subjects:
Online Access:https://hdl.handle.net/10356/84446
http://hdl.handle.net/10220/13131
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-84446
record_format dspace
spelling sg-ntu-dr.10356-844462020-05-28T07:18:55Z A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock Shakeri, Mojtaba. Low, Malcolm Yoke Hean. Turner, Stephen John. Lee, Eng Wah. School of Computer Engineering A*STAR SIMTech DRNTU::Engineering::Computer science and engineering This paper studies truck scheduling in a resource-constrained crossdock. The problem decides on the sequence of incoming and outgoing trucks at the dock doors of the crossdocking terminal, subject to the availability of crossdock resources including dock doors and material handling systems. The resources are assumed non-preemptive making it necessary to address the feasibility of the problem before its optimality as it might be entrapped in deadlock and no feasible solution is produced. The paper thus aims at developing an algorithmic approach capable of establishing solution feasibility for truck scheduling problem instances of various types and difficulty levels which at the same time can be readily implemented in an industrial setting. The proposed approach is a two-phase heuristic algorithm where in the first phase, a heuristic search is deployed to construct a feasible sequence of trucks for the assignment to dock doors and in the second, a rule-based heuristic is used to assign each sequenced truck to a proper dock door, subject to a limited number of forklifts, such that significant savings in the truck schedule length are achieved. Extensive experiments are conducted to evaluate the efficiency of the algorithm in terms of deadlock avoidance and solution quality. The evaluation is carried out against the solutions generated by the exact mathematical model of the problem and a constructive heuristic developed for a similar truck scheduling problem. Experimental results demonstrate that the proposed algorithm is robust in avoiding deadlock and generates feasible solutions for the instances where the other two approaches cannot. Furthermore, significant improvement in the solution quality is achieved by augmenting the algorithm to a re-starting heuristic. 2013-08-15T08:09:07Z 2019-12-06T15:45:22Z 2013-08-15T08:09:07Z 2019-12-06T15:45:22Z 2012 2012 Journal Article Shakeri, M., Low, M. Y. H., Turner, S. J.,& Lee, E. W. (2012). A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock. Computers & Operations Research, 39(11), 2564-2577. 0305-0548 https://hdl.handle.net/10356/84446 http://hdl.handle.net/10220/13131 10.1016/j.cor.2012.01.002 en Computers & operations research
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic DRNTU::Engineering::Computer science and engineering
spellingShingle DRNTU::Engineering::Computer science and engineering
Shakeri, Mojtaba.
Low, Malcolm Yoke Hean.
Turner, Stephen John.
Lee, Eng Wah.
A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock
description This paper studies truck scheduling in a resource-constrained crossdock. The problem decides on the sequence of incoming and outgoing trucks at the dock doors of the crossdocking terminal, subject to the availability of crossdock resources including dock doors and material handling systems. The resources are assumed non-preemptive making it necessary to address the feasibility of the problem before its optimality as it might be entrapped in deadlock and no feasible solution is produced. The paper thus aims at developing an algorithmic approach capable of establishing solution feasibility for truck scheduling problem instances of various types and difficulty levels which at the same time can be readily implemented in an industrial setting. The proposed approach is a two-phase heuristic algorithm where in the first phase, a heuristic search is deployed to construct a feasible sequence of trucks for the assignment to dock doors and in the second, a rule-based heuristic is used to assign each sequenced truck to a proper dock door, subject to a limited number of forklifts, such that significant savings in the truck schedule length are achieved. Extensive experiments are conducted to evaluate the efficiency of the algorithm in terms of deadlock avoidance and solution quality. The evaluation is carried out against the solutions generated by the exact mathematical model of the problem and a constructive heuristic developed for a similar truck scheduling problem. Experimental results demonstrate that the proposed algorithm is robust in avoiding deadlock and generates feasible solutions for the instances where the other two approaches cannot. Furthermore, significant improvement in the solution quality is achieved by augmenting the algorithm to a re-starting heuristic.
author2 School of Computer Engineering
author_facet School of Computer Engineering
Shakeri, Mojtaba.
Low, Malcolm Yoke Hean.
Turner, Stephen John.
Lee, Eng Wah.
format Article
author Shakeri, Mojtaba.
Low, Malcolm Yoke Hean.
Turner, Stephen John.
Lee, Eng Wah.
author_sort Shakeri, Mojtaba.
title A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock
title_short A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock
title_full A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock
title_fullStr A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock
title_full_unstemmed A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock
title_sort robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock
publishDate 2013
url https://hdl.handle.net/10356/84446
http://hdl.handle.net/10220/13131
_version_ 1681059662297825280