An efficient incremental evaluation function for optimizing truck scheduling in a resource-constrained crossdock using metaheuristics
| Autor: | Malcolm Yoke Hean Low, Stephen John Turner, Mojtaba Shakeri, Eng Wah Lee |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
021103 operations research business.industry Computer science 0211 other engineering and technologies General Engineering 02 engineering and technology Truck scheduling Evaluation function Tabu search Computer Science Applications Scheduling (computing) Artificial Intelligence 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Local search (optimization) business Metaheuristic Variable neighborhood search |
| Zdroj: | Expert Systems with Applications. 45:172-184 |
| ISSN: | 0957-4174 |
| DOI: | 10.1016/j.eswa.2015.09.041 |
| Popis: | We address truck scheduling optimization in a multi-door resource-constrained crossdock.We develop two incremental TS and VNS metaheuristics for the problem.The incremental mechanism evaluates only the transformation applied to the solution.Our results show that the incremental mechanism is efficient in reducing the runtime.The reduction is more significant for TS when applied to huge size problem instances. This paper addresses truck scheduling optimization in a resource-constrained crossdock. The truck scheduling problem decides on the succession of incoming and outgoing trucks at the dock doors of a crossdocking terminal such that the total crossdocking operation time is minimized. The paper tackles the optimization from the computational perspective by developing an incremental evaluation of the objective function in the body of single-solution based metaheuristics. It consists in evaluating only the transformation applied to the current solution rather than the complete evaluation of the neighbor solution. The proposed incremental neighborhood evaluation is integrated into two metaheuristics including tabu search (TS) and variable neighborhood search (VNS). In terms of solution quality vs. runtime, experimental results show that the incremental mechanism helps the two algorithms with dedicating their runtime to solution optimization rather than spending it on fitness evaluation when compared with a deterministic local search (LS) algorithm that exploits a simple complete evaluation of the objective function. This is in particular evident for the TS algorithm which obtains comparable results to LS while achieving on average 67.6% reduction in runtime for huge instances of scheduling 2048 trucks in a 256-door crossdock. Our findings on the efficiency of the proposed incremental evaluation are reinforced when the two metaheuristics are re-assessed with a complete evaluation of the objective function. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect