An improved memetic algorithm for integrated production scheduling and vehicle routing decisions

摘要

Motivated by traditional Chinese medicine decoction and delivery problems in our collaborative Chinese medicine decoction company, this study addresses integrated production scheduling and vehicle routing decisions. To deal with this problem, we first propose a mixed integer linear programming model considering hybrid flow shop production and multi-trip multi-vehicle delivery, which is challenging to solve for medium -and large-size instances. We then propose an improved memetic algorithm (MA) that combines a genetic algorithm (GA) with education operators, including local search procedures. To improve the performance of the MA, we consider the contribution of diversity in the fitness function to enhance the exploratory ability, propose a parent selection operator by considering the softmax function to balance exploitation and exploration, and design three customized crossover operators and five education operators with local search procedures. Numerical experiments show that the integrated scheduling method shortens the total makespan by 11.19% compared with separated production scheduling and vehicle routing methods. We compare the proposed MA with Gurobi for small-size instances, and with the GA for special cases (single-stage production) for medium -or large-size instances. The results of numerical experiments for 360 instances show that the MA can find solutions with a gap of no more than 2% from the optimal solution within 3 s for small-size instances, and can improve the solutions of the GA and the adaptive large neighborhood search (ALNS) algorithm by more than 30% and 10%.