An effective multi-objective evolutionary algorithm for solving the AGV scheduling problem with pickup and delivery

摘要

This paper investigates a new automatic guided vehicle scheduling problem with pickup and delivery from the goods handling process in a matrix manufacturing workshop with multi-variety and small-batch production. The problem aims to determine a solution that maximizes customer satisfaction while minimizing distribution cost. For this purpose, a multi-objective mixed-integer linear programming model is first formulated. Then an effective multi-objective evolutionary algorithm is developed for solving the problem. In the algorithm, a constructive heuristic is presented and incorporated into the population initialization. A multi-objective local search based on an ideal-point is used to enforce the exploitation capability. A novel two-point crossover operator is designed to make full use of valuable information collected in the non-dominated solutions. A restart strategy is proposed to avoid the algorithm trapping into a local optimum. At last, a series of comparative experiments are implemented based on a number of real-world instances from an electronic equipment manufacturing enterprise. The results show that the proposed algorithm has a significantly better performance than the existing multi-objective algorithms for solving the problem under consideration.