Network Models and Optimization: Multiobjective Genetic Algorithm Approach

Front Cover
Springer Science & Business Media, Jul 10, 2008 - Technology & Engineering - 692 pages

Network models are critical tools in business, management, science and industry. Network Models and Optimization: Multiobjective Genetic Algorithm Approach presents an insightful, comprehensive, and up-to-date treatment of multiple objective genetic algorithms to network optimization problems in many disciplines, such as engineering, computer science, operations research, transportation, telecommunication, and manufacturing.

Network Models and Optimization: Multiobjective Genetic Algorithm Approach extensively covers algorithms and applications, including shortest path problems, minimum cost flow problems, maximum flow problems, minimum spanning tree problems, travelling salesman and postman problems, location-allocation problems, project scheduling problems, multistage-based scheduling problems, logistics network problems, communication network problem, and network models in assembly line balancing problems, and airline fleet assignment problems.

Network Models and Optimization: Multiobjective Genetic Algorithm Approach can be used both as a student textbook and as a professional reference for practitioners in many disciplines who use network optimization methods to model and solve problems.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

523 Genetic Representations for JSP
316
524 GenTsujimuraKubotas Approach
325
525 ChengGenTsujimuras Approach
326
526 GoncalvesMagalhacsResendes Approach
330
527 Experiment on Benchmark Problems
335
53 Flexible Jobshop Scheduling Model
337
531 Mathematical Formulation of fJSP
338
532 Genetic Representations for fJSP
340

13 Hybrid Genetic Algorithms
15
131 Genetic Local Search
16
132 Parameter Adaptation
18
14 Multiobjective Genetic Algorithms
25
141 Basic Concepts of Multiobjective Optimizations
26
142 Features and Implementation of Multiobjective GA
29
143 Fitness Assignment Mechanism
30
144 Performance Measures
41
References
44
Basic Network Models
49
Node Selection and Sequencing
50
Arc Selection
51
Arc Selection and Flow Assignment
52
214 Representing Networks
53
215 Algorithms and Complexity
54
216 NPComplete
55
217 List of NPcomplete Problems in Network Design
56
22 Shortest Path Model
57
221 Mathematical Formulation of the SPP Models
58
222 Prioritybased GA for SPP Models
60
223 Computational Experiments and Discussions
72
23 Minimum Spanning Tree Models
79
231 Mathematical Formulation of the MST Models
83
232 PrimPredbased GA for MST Models
85
233 Computational Experiments and Discussions
96
241 Mathematical Formulation
99
242 Prioritybased GA for MXF Model
100
243 Experiments
105
25 Minimum Cost Flow Model
107
251 Mathematical Formulation
108
252 Prioritybased GA for MCF Model
110
253 Experiments
113
26 Bicriteria MXFMCF Model
115
261 Mathematical Formulations
118
262 Prioritybased GAfor bMXFMCF Model
119
263 iawGA for bMXFMCF Model
123
264 Experiments and Discussion
125
27 Summary
128
References
130
Logistics Network Models
135
32 Basic Logistics Models
139
322 Prufer Numberbased GAfor the Logistics Models
146
323 Numerical Experiments
152
33 Location Allocation Models
154
331 Mathematical Formulation of the Logistics Models
156
332 Locationbased GAfor the Location Allocation Models
159
333 Numerical Experiments
170
34 Multistage Logistics Models
175
341 Mathematical Formulation of the Multistage Logistics
176
342 Prioritybased GAfor the Multistage Logistics
185
343 Numerical Experiments
190
35 Flexible Logistics Model
193
351 Mathematical Formulation of the Flexible Logistics Model
196
352 Direct Pathbased GAfor the Flexible Logistics Model
202
353 Numerical Experiments
206
36 Integrated Logistics Model with Multitime Period and Inventory
208
361 Mathematical Formulation of the Integrated Logistics Model
210
362 Extended Prioritybased GA for the Integrated Logistics Model
213
363 Local Search Technique
218
364 Numerical Experiments
221
37 Summary
222
References
225
Communication Network Models
229
42 Centralized Network Models
234
421 Capacitated Multipoint Network Models
235
422 Capacitated QoS Network Model
242
43 Backbone Network Model
246
431 Pierre and Legaults Approach
248
432 Numerical Experiments
252
433 Konak and Smiths Approach
253
434 Numerical Experiments
257
441 Reliable Backbone Network Model
259
442 Reliable Backbone Network Model with Multiple Goals
269
443 Bicriteria Reliable Network Model of LAN
274
444 Bilevel Network Design Model
283
45 Summary
290
References
291
Advanced Planning and Scheduling Models
297
52 Jobshop Scheduling Model
303
521 Mathematical Formulation of JSP
304
522 Conventional Heuristics for JSP
305
533 Multistage Operationbased GA for fJSP
344
534 Experiment on Benchmark Problems
353
54 Integrated Operation Sequence and Resource Selection Model
355
541 Mathematical Formulation ofiOSRS
358
542 Multistage Operationbased GA for iOSRS
363
543 Experiment and Discussions
372
55 Integrated Scheduling Model with Multiplant
376
551 Integrated Data Structure
379
552 Mathematical Models
381
553 Multistage Operationbased GA
383
554 Numerical Experiment
389
56 Manufacturing and Logistics Model with Pickup and Delivery
395
562 Multiobjective Hybrid Genetic Algorithm
399
563 Numerical Experiment
407
57 Summary
412
Project Scheduling Models
419
62 Resourceconstrained Project Scheduling Model
421
621 Mathematical Formulation of rcPSP Models
422
622 Hybrid GA for rcPSP Models
426
623 Computational Experiments and Discussions
434
63 Resourceconstrained Multiple Project Scheduling Model
438
631 Mathematical Formulation ofrcmPSP Models
440
632 Hybrid GA for rcmPSP Models
444
633 Computational Experiments and Discussions
451
64 Resourceconstrained Project Scheduling Model with Multiple Modes
457
642 Adaptive Hybrid GA for rcPSPmM Models
461
643 Numerical Experiment
470
65 Summary
472
References
473
Assembly Line Balancing Models
477
72 Simple Assembly Line Balancing Model
480
722 Prioritybased GAfor sALB Models
484
723 Computational Experiments and Discussions
492
73 Ushaped Assembly Line Balancing Model
493
731 Mathematical Formulation ofuALB Models
495
732 Prioritybased GAfor uALB Models
499
733 Computational Experiments and Discussions
505
741 Mathematical Formulation of rALB Models
509
742 Hybrid GA for rALB Models
512
743 Computational Experiments and Discussions
523
75 Mixedmodel Assembly Line Balancing Model
526
751 Mathematical Formulation of mALB Models
529
752 Hybrid GAfor mALB Models
532
753 Rekiek and Delchambres Approach
542
754 Ozmehmet Tasan and Tunalis Approach
543
76 Summary
546
Tasks Scheduling Models
551
811 Hard Realtime Task Scheduling
553
812 Soft Realtime Task Scheduling
557
82 Continuous Task Scheduling
562
821 Continuous Task Scheduling Model on Uniprocessor System
563
822 Continuous Task Scheduling Model on Multiprocessor System
575
83 Realtime Task Scheduling in Homogeneous Multiprocessor
583
831 Soft Realtime Task Scheduling Problem srTSP and Mathematical Model
584
832 Multiobjective GA for srTSP
586
833 Numerical Experiments
592
84 Realtime Task Scheduling in Heterogeneous Multiprocessor System
595
842 SAbased Hybrid GA Approach
597
843 Numerical Experiments
601
85 Summary
602
References
604
Advanced Network Models
607
911 Fleet Assignment Model with Connection Network
613
912 Fleet Assignment Model with Timespace Network
624
92 Container Terminal Network Model
636
921 Berth Allocation Planning Model
639
922 Multistage Decisionbased GA
643
923 Numerical Experiment
646
93 AGV Dispatching Model
651
931 Network Modeling and Mathematical Formulation
652
932 Random Keybased GA
658
933 Numerical Experiment
664
94 Car Navigation Routing Model
666
941 Data Analyzing
667
942 Mathematical Formulation
670
943 Improved Fixed Lengthbased GA
672
944 Numerical Experiment
677
95 Summary
681
References
682
Index
687
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 14 - The method may work reasonably well when the feasible search space is convex and it constitutes a reasonable part of the whole search space.
Page 20 - This rule states that the ratio of successful mutations to all mutations should be 1/5, hence if the ratio is greater than 1/5 then increase the step size, and if the ratio is less than 1/5 then decrease the step size.
Page 15 - GA have proved to be a versatile and effective approach for solving optimization problems. Nevertheless, there are many situations in which the simple GA does not perform particularly well, and various methods of hybridization have been proposed. One of most common forms of hybrid genetic algorithm (hGA) is to incorporate local optimization as an add-on extra to the canonical GA loop of recombination and selection.
Page 1 - ... rejecting others so as to keep the population size constant. Fitter chromosomes have higher probabilities of being selected. After several generations, the algorithms converge to the best chromosome, which hopefully represents the optimum or suboptimal solution to the problem.
Page 11 - The genetic operators and their significance can now be explained. Crossover. Crossover is the main genetic operator. It operates on two individuals at a time and generates an offspring by combining schemata from both parents. A simple way to achieve crossover would be to choose a random cut point and generate the offspring by combining the segment of one parent to the left of the cut point with the segment of the other parent to the right of the cut point. This method works well with the bit string...
Page 12 - If it is too low, many genes that would have been useful are never tried out; but if it is too high, there will be much random perturbation, the offspring will start losing their resemblance to the parents, and the algorithm will lose the ability to learn from the history of the search.

About the author (2008)

Professor Mitsuo Gen is currently a professor of the Graduate School of Information, Production and Systems at Waseda University. He previously worked as a lecturer and professor at Ashikaga Institute of Technology. His research interests include genetic and evolutionary computation; fuzzy logic and neural networks; supply chain network design; optimization for information networks; and advanced planning and scheduling (APS).

Runwei Cheng is a Doctor of Engineering and currently works for JANA Solutions, Inc.

Lin Lin is currently a PhD candidate and research assistant at Waseda University, where he gained his MSc from the Graduate School of Information, Production and Systems. His research interests include hybrid genetic algorthims; neural networks; engineering optimization; multiobjective optimization; applications of evolutionary techniques; production and logistics; communication networks; image processing and pattern recognition; and parallel and distributed systems.

Bibliographic information