An effective iterated greedy algorithm for solving a multi-compartment AGV scheduling problem in a matrix manufacturing workshop

• Published in: Applied soft computing 2021-02, Vol.99, p.106945, Article 106945
• Main Authors: Zou, Wen-Qiang, Pan, Quan-Ke, Tasgetiren, M. Fatih
• Format: Article
• Language: English
• Subjects: Automated guided vehicle; Heuristics; Iterated greedy algorithm; Multi-compartment; Scheduling
• ISSN: 1568-4946; 1872-9681
• DOI: 10.1016/j.asoc.2020.106945

In this paper, we address a multi-compartment automatic guided vehicle scheduling (MC-AGVS) problem from a matrix manufacturing workshop that has attracted more and more attention of manufacturing firms in recent years. The problem aims to determine a solution to minimize the total cost including the travel cost, the service cost, and the cost of vehicles involved. For this purpose, a mixed-integer linear programming model is first constructed. Then, a novel iterated greedy (IG) algorithm including accelerations for evaluating objective functions of neighboring solutions; an improved nearest-neighbor-based constructive heuristic; an improved sweep-based constructive heuristic; an improved destruction procedure; and a simulated annealing type of acceptance criterion is proposed. At last, a series of comparative experiments are implemented based on some real-world instances from an electronic equipment manufacturing enterprise. The computational results demonstrate that the proposed IG algorithm has generated substantially better solutions than the existing algorithms in solving the problem under consideration. •A multi-compartment automatic guided vehicle scheduling problem is studied.•An effective iterated greedy algorithm is proposed.•Accelerations for evaluating solutions are presented.•The proposed algorithm is the best performing against all the existing methods.