An effective self-adaptive iterated greedy algorithm for a multi-AGVs scheduling problem with charging and maintenance. (15th April 2023)

• Record Type: Journal Article
• Authors: Zou, Wen-qiang; Pan, Quan-ke; Meng, Lei-lei; Sang, Hong-yan; Han, Yu-yan; Li, Jun-qing
• Is Part Of: Expert systems with applications. Volume 216(2023)
• Publication Date: 2023-04-15
• Subjects: Automated guided vehicle -- Scheduling -- Iterated greedy algorithm -- Charging -- Maintenance; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2023.119512
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A multi-AGVs scheduling problem with charging and maintenance is studied. A mixed-integer linear programming model with the total cost is built. A self-adaptive iterated greedy algorithm is proposed to solve the problem. Experimental results show the effectiveness of the proposed algorithm. Abstract: The automatic guided vehicle (AGV) scheduling problem in matrix manufacturing workshop has been a research hotspot in recent years because of its wide industrial applications. However, the research on multi-AGVs scheduling problem with charging and maintenance (MAGVSCM ) is rarely reported. In the paper, the MAGVSCM is investigated to reduce the total cost composed of travel cost, penalty cost and vehicle cost. To this end, a mixed-integer linear programming model and a self-adaptive iterated greedy (SAIG) algorithm are proposed. Based on the problem characteristics, a new solution presentation and the solution accelerated evaluation method are presented and applied in the SAIG. In the SAIG, several nearest-neighbor-based improved heuristics are proposed and used to generate an initial solution. A destruction procedure with self-adaptive strategy is developed to enhance the exploration capability of the algorithm. A merging local search method is used to reduce the number of AGVs as much as possible without lowering the total cost. An acceptance criterion with restart strategy is designed to determine the current solution in the next iteration. A large number of experimental results show that the proposed algorithm significantly outperforms the existing algorithms in solving the problem under consideration.