Solving material distribution routing problem in mixed manufacturing systems with a hybrid multi-objective evolutionary algorithm

Abstract

The material distribution routing problem in the manufacturing system is a complex combinatorial optimization problem and its main task is to deliver materials to the working stations with low cost and high efficiency. A multi-objective model was presented for the material distribution routing problem in mixed manufacturing systems, and it was solved by a hybrid multi-objective evolutionary algorithm (HMOEA). The characteristics of the HMOEA are as follows: 1) A route pool is employed to preserve the best routes for the population initiation; 2) A specialized best-worst route crossover (BWRC) mode is designed to perform the crossover operators for selecting the best route from Chromosomes 1 to exchange with the worst one in Chromosomes 2, so that the better genes are inherited to the offspring; 3) A route swap mode is used to perform the mutation for improving the convergence speed and preserving the better gene; 4) Local heuristics search methods are applied in this algorithm. Computational study of a practical case shows that the proposed algorithm can decrease the total travel distance by 51.66%, enhance the average vehicle load rate by 37.85%, cut down 15 routes and reduce a deliver vehicle. The convergence speed of HMOEA is faster than that of famous NSGA-II.

Keywords

material distribution routing problem / multi-objective optimization / evolutionary algorithm / local search

References

[1] ChakravortyS. S.. Improving distribution operations: Implementation of material handling systems [J]. Int J Production Economics, 2009, 122: 89-106

[2] LiX.-y., TianP., LeungS. C. H.. Vehicle routing problems with time windows and stochastic travel and services times: Models and algorithm [J]. Int J Production Economics, 2010, 125: 137-145

[3] BodinL., BruceG.. Classification in vehicle routing and scheduling [J]. Network, 1981, 11: 97-108

[4] BakerB. M., AyechewM. A.. A genetic algorithm for the vehicle routing problem [J]. Computers & Operations Research, 2003, 30: 787-800

[5] TanK. C., ChewY. H., LeeL. H.. A hybrid multi-objective evolutionary algorithm for solving vehicle routing problem with time windows [J]. Computational Optimization and Applications, 2006, 34: 115-151

[6] BentR., van HentenryckP.. A two stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows [J]. Computers and Operations Research, 2006, 33: 875-893

[7] MarinakisY., MarinakiM.. A hybrid genetic-Particle swarm optimization algorithm for the vehicle routing problem [J]. Expert Systems with Application, 2010, 37: 1446-1455

[8] WangC.-h., LuJ.-zhang.. An effective evolutionary algorithm for the practical capacitated vehicle routing problems [J]. Journal of Intelligence Manufacturing, 2010, 21: 363-375

[9] GhoseiriK., GhannadpourS. F.. Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm [J]. Applied Soft Computing, 2010, 10: 1096-1107

[10] ChenJ., PanJ. C. H., LinC. M.. A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem [J]. Expert System with Application, 2008, 34: 570-577

[11] TanK. C., CheongC. K., GohC. K.. Solving multi-objective vehicle routing problem with stochastic demand via evolutionary computation [J]. European Journal of Operation Research, 2007, 177: 813-839

[12] OmbukiB., RossB., HansharF.. Multi-objective genetic algorithm for vehicle routing problem with time windows [J]. Applied Intelligence, 2006, 24: 17-30

[13] MARINAKIS Y, MARINAKI M, DOUNIAS G. Honey bees mating optimization algorithm for the vehicle routing problem [C]// KRASNOGOR N, NICOSIA G, PAVONE M, PELTA D. Nature inspired cooperative strategies for optimization-NICSO 2007. Studies in Computational Intelligence, 2008, 129: 139–148.

[14] HombergerJ., GehringH.. Two evolutionary meta-heuristics for the vehicle routing problem with time windows [J]. INFOR, 1999, 37: 297-318

[15] OMBUKI B, NAKAMURA M, MAEDA O. A hybrid search based on genetic algorithms and tabu search for vehicle routing [C]// BANFF A B, LEUNG H. Proceedings of the 6th IASTED International Conference on Artificial Intelligence and Soft Computing (ASC2002). Marbella, Spain: 2002: 176–181.

[16] THANGIAH S R. A hybrid genetic algorithm simulated annealing and Tabu search heuristic for vehicle routing problems with time windows [M]// CHAMBERS L. Practical Handbook of Genetic Algorithms Complex Structures. vol.3. CRC Press: 1999, 347–381.

[17] SolomonM. M.. Algorithms for the vehicle routing and scheduling problems with time window constraints [J]. Operations Research, 1987, 35: 254-265

[18] MarinakisY., MigdalasA., PardalosP. M.. A hybrid genetic-GRASP Algorithm using Langrangean relaxation for the traveling salesman problem [J]. Journal of Combinatorial Optimization, 2005, 10: 311-326

[19] TAN K C, LEE T H, CHEW Y H., LEE L H. A multi-objective evolutionary algorithm for solving vehicle routing problem with time windows [C]// Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Washington, DC, USA, 2003: 361–366.

[20] CoelloC. C. A.. Evolutionary multi-objective optimization: A historical view of the field [J]. IEEE Computational Intelligence Magazine, 2006, 1: 28-36

[21] ISHIBASHI H, AGUIRRE H, TANAKA K, SUGIMURA T. Multi-objective optimization with improved genetic algorithm [C]// Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC). Nashville, 2000: 3852–3857.

[22] MarinakisY., MigdalasA., PardalosP. M.. Expanding neighborhood GRASP for the traveling salesman problem [J]. Computational Optimization and Applications, 2005, 32: 231-257

[23] MarinakisY., MigdalasA., PardalosP. M.. Multiple phase neighborhood search GRASP based on Lagrangean relaxation and random back tracking Lin Kernighan for the traveling salesman problem [J]. Journal of Combinatorial Optimization, 2007, 18: 201-216

[24] MarinakisY., MigdalasA., PardalosP. M.. A new bi-level formulation for the vehicle routing problem and a solution method using a genetic algorithm [J]. Journal of Global Optimization, 2007, 38: 555-580

[25] DebK., PratapA., AgarwalS., MeyarivanT.. A fast and elitist multiobjective Genetic algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197