|
Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications
by Lakhmi C. Jain; N.M. Martin
CRC Press, CRC Press LLC
ISBN: 0849398045 Pub Date: 11/01/98
|
4.3 A Nonstandard GA
A different approach is taken in [26], as the authors apply the general principles of genetic search on the routes themselves and do not address the encoding issue. Hence, a population of solutions (not chromosomes) evolve from one generation to the next through the application of operators that are similar in spirit to crossover and mutation. For example, the Sequence-Based Crossover (SBX) merges the first part of a route in a given solution to the end part of another route in another solution. This operator is illustrated in Figure 11. First, a link is randomly selected and removed from each parent solution. Then, the customers that are serviced before the break point on the route of the first parent solution are linked to the customers that are serviced after the break point on the route of the second parent solution (c.f. black nodes). This new route then replaces the old one in the first parent solution. A second offspring can be created by inverting the role of the parents. In the process, customers are likely to be duplicated or eliminated from the resulting offspring solution. Hence, repair operators are used to transform an infeasible solution into a feasible one; a duplicate is eliminated by removing the customer from one of the routes, while customers that were left apart by the SBX operator are reintroduced in the solution through a simple insertion mechanism.
In the GENEROUS system, this algorithm is coupled with powerful local reoptimization methods that improve the offspring solutions by exchanging customers between routes or by moving customers from one position to another on the same route. With such local reoptimization methods, the GENEROUS system was able to produce many best known solutions on a set of benchmark problems with time windows [34], outperforming other competing approaches based on simulated annealing and tabu search.
5. Conclusion
This chapter has reported some interesting developments in the field of vehicle routing using neural networks and genetic algorithms. Genetic algorithms, in particular, have been successful for different types of academic VRPs with complex side constraints as well as for real-world applications. This is probably related to the fact that GAs work with a population of solutions, rather than a single solution, thus achieving a wider exploration of the solution space.
Neural network models have not obtained the same success on some classical vehicle routing problems. Since the human mind is not particularly well suited for solving complex combinatorial optimization problems, the fundamental analogy upon which these models rely do not really hold. However, the vehicle dispatching problem reported in Section 3 is an interesting application for this paradigm, since the problem is ill-defined and requires a fair amount of human expertise. Such carefully identified problems should provide a niche for the application of neural networks.
Hybrid approaches combining genetic algorithms and neural networks could also provide interesting research avenues in the future. An example is found in [27], where a neural network is used to find good seed points for a set of vehicle routes; the GA then tunes the parameters of the following insertion phase.
Acknowledgments
The first author was funded by the Canadian Natural Sciences and Engineering Research Council (NSERC) and by the Quebec Fonds pour la Formation de Chercheurs et lAide à la Recherche (FCAR). The second author was partially supported by the Slippery Rock University Faculty Development Grant. This support is gratefully acknowledged.
References
- 1 Blanton, J.L. and Wainwright, R.L. (1993), Multiple Vehicle Routing with Time and Capacity Constraints using Genetic Algorithms, in Proceedings of the 5th Int. Conf. on Genetic Algorithms, Urbana-Champaign, IL, pp. 452-459.
- 2 Christofides, N., Mingozzi, A., and Toth, P. (1979), The Vehicle Routing Problem, in Combinatorial Optimization, N. Christofides, A. Mingozzi, P. Toth, and C. Sandi (Eds.), Wiley: Chichester, pp. 315-338.
- 3 Clarke, G. and Wright, J. (1964), Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operations Research 12, pp. 568-581.
- 4 Cullen, F.H. (1984), Set Partitioning Based Heuristics for Interactive Routing, Ph.D. Dissertation, Georgia Institute of Technology, Georgia.
- 5 Davis, L. (1991), Handbook of Genetic Algorithms, Van Nostrand Reinhold: New York.
- 6 DeJong, K.A. (1975), An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Ph.D. Dissertation, University of Michigan.
- 7 Durbin, R. and Willshaw, D. (1987), An Analogue Approach to the Traveling Salesman Problem using an Elastic Net Method, Nature 326, pp. 689-691.
- 8 Garey, M.R. and Johnson, D.S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman: San Francisco.
- 9 Gendreau, M., Hertz, A., and Laporte, G. (1994), A Tabu Search Heuristic for the Vehicle Routing Problem, Management Science 40, pp. 1276-1290.
- 10 Ghaziri, H. (1991), Solving Routing Problems by a Self-Organizing Map, in Artificial Neural Networks, T. Kohonen, K. Makisara, O. Simula and J. Kangas (Eds.), North-Holland: Amsterdam, pp. 829-834.
- 11 Ghaziri, H. (1993), Algorithmes Connexionnistes pour lOptimisation Combinatoire, Thèse de doctorat, Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland (in French).
- 12 Ghaziri, H. (1996), Supervision in the Self-Organizing Feature Map: Application to the Vehicle Routing Problem, in Meta-Heuristics: Theory & Applications, I.H. Osman and J.P. Kelly (Eds.), Kluwer:Boston, pp. 651-660.
- 13 Gillett, B. and Miller, L. (1974), ), A Heuristic Algorithm for the Vehicle Dispatch Problem, Operations Research 22, pp. 340-379.
- 14 Goldberg, D.E. (1989), Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley: Reading, MA.
- 15 Holland, J.H. (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press: Ann Arbor.
- 16 Hopfield, J.J. (1982), Neural Networks and Physical Systems with Emergent Collective Computational Abilities, in Proceedings of the National Academy of Science 79, pp. 2554-2558.
- 17 Hopfield, J.J. and Tank, D.W. (1985), Neural Computation of Decisions in Optimization Problems, Biological Cybernetics 52, pp. 141-152.
- 18 Johnson, D.S. and McGeoh, L.A. (1997), The Traveling Salesman Problem: A Case Study, in Local Search in Combinatorial Optimization, E. Aarts and J.K. Lenstra (Eds.), Wiley: Chichester, pp. 215-310.
- 19 Kohonen, T. (1988), Self-Organization and Associative Memory, Springer: Berlin.
- 20 Lenstra, J. and Rinnooy Kan, A. (1981), Complexity of Vehicle Routing and Scheduling Problems, Networks 11, pp. 221-227.
- 21 Maren, A., Harston, C., and Pap, R. (1990), Handbook of Neural Computing Applications, Academic Press: San Diego.
- 22 Matsuyama, Y. (1991), Self-Organization via Competition, Cooperation and Categorization Applied to Extended Vehicle Routing Problems, in Proc. of the Int. Joint Conf. on Neural Networks, Seattle, WA, pp. I-385-390.
- 23 Michalewicz, Z. (1996), Genetic Algorithms + Data Structures = Evolution Programs, Third Edition, Springer: Berlin.
- 24 Potvin, J.Y. (1993), The Traveling Salesman Problem: A Neural Network Perspective, ORSA Journal on Computing 5, pp. 328-348.
- 25 Potvin, J.Y. (1996), Genetic Algorithms for the Traveling Salesman Problem, Annals of Operations Research 63, pp. 339-370.
- 26 Potvin, J.Y. and Bengio, S. (1996), The Vehicle Routing Problem with Time Windows - Part II: Genetic Search, INFORMS Journal on Computing 8, pp. 165-172.
- 27 Potvin, J.Y., Dubé, D., and Robillard, C. (1996), A Hybrid Approach to Vehicle Routing using Neural Networks and Genetic Algorithms, Applied Intelligence 6, pp. 241-252.
- 28 Potvin, J.Y., Duhamel, C., and Guertin, F. (1996), A Genetic Algorithm for Vehicle Routing with Backhauling, Applied Intelligence 6, pp. 345-355.
- 29 Psaraftis, H.N. (1995), Dynamic Vehicle Routing, Annals of Operations Research 61, pp. 143-164.
- 30 Rosenkrantz, D., Sterns, R., and Lewis, P. (1977), An Analysis of Several Heuristics for the Traveling Salesman Problem, SIAM Journal of Computing 6, pp. 563-581.
- 31 Rumelhart, D.E., Hinton, G.E., and Williams, R.J. (1986), Learning Internal Representations by Error Propagation, in Parallel Distributed Processing - Explorations in the Microstructure of Cognition, Volume 1, D.E. Rumelhart and J.L. McClelland (Eds.), The MIT Press: Cambridge, pp. 318-364.
- 32 Schumann, M. and Retzko, R. (1995), Self-Organizing Maps for Vehicle Routing Problems - Minimizing an Explicit Cost Function, in Proceedings of the Int. Conf. on Artificial Neural Networks, F. Fogelman-Soulie (Ed.), EC2&Cie, Paris, France, pp. II-401-406.
- 33 Shen, Y., Potvin, J.Y., Rousseau, J.M., and Roy, S. (1995), A Computer Assistant for Vehicle Dispatching with Learning Capabilities, Annals of Operations Research 61, pp. 189-211.
- 34 Solomon, M.M. (1987), Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints, Operations Research 35, pp. 254-265.
- 35 Taillard, E. (1993), Parallel Iterative Search Methods for Vehicle Routing Problems, Networks 23, pp. 661-673.
- 36 Thangiah, S.R., Nygard, K., and Juell, P. (1991), GIDEON: A Genetic Algorithm System for Vehicle Routing with Time Windows, in Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications, Miami, FL, pp. 322-328.
- 37 Thangiah, S.R. and Nygard, K. (1992), School Bus Routing using Genetic Algorithms, in Proceedings of the SPIE Conference on Applications of Artificial Intelligence X: Knowledge Based Systems, Orlando, FL, pp. 387-397.
- 38 Thangiah, S.R. and Nygard, K. (1992), MICAH: A Genetic Algorithm System for Multi-Commodity Transshipment Problems, in Proceedings of the 8th IEEE Conference on Artificial Intelligence Applications, Monterey, CA, pp. 240-246.
- 39 Thangiah, S.R. (1993), Vehicle Routing with Time Windows using Genetic Algorithms, Technical Report SRU-CpSc-TR-93-23, Computer Science Department, Slippery Rock University, PA.
- 40 Thangiah, S.R., Osman, I.H., Vinayagamoorthy, R., and Sun, T. (1993), Algorithms for Vehicle Routing with Time Deadlines, American Journal of Mathematical and Management Sciences 13, pp. 323-355.
- 41 Thangiah, S.R., Vinayagamoorthy, R., and Gubbi, A. (1993), Vehicle Routing with Time Deadlines using Genetic and Local Algorithms, in Proceedings of the 5th Int. Conf. on Genetic Algorithms, Urbana-Champaign, IL, pp. 506-513.
- 42 Thangiah, S.R. (1995), An Adaptive Clustering Method using a Geometric Shape for Vehicle Routing Problems with Time Windows, in Proceedings of the 6th Int. Conf. on Genetic Algorithms, Pittsburgh, PA, pp. 536-543.
- 43 Thangiah, S.R. (1996), Vehicle Routing with Time Windows using Genetic Algorithsm, in Practical Handbook of Genetic Algorithms: New Frontiers, Volume II, Lance Chambers (Ed.), CRC Press, FL.
- 44 Thangiah, S.R., Salhi, S., and Rahman, F. (1997), Genetic Clustering: An Adaptive Heuristic for the Multi-Depot Vehicle Routing Problem, Technical Report SRU-CpSc-TR-97-33, Computer Science Department, Slippery Rock University, PA.