Network models and optimization : multiobjective genetic algorithm approach

Network models are critical tools in business, management, science and industry. "Network Models and Optimization" 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. The book extensively covers algorithms and applications, including shortest path problems, minimum cost flow problems, maximum flow problems, minimum spanning tree problems, traveling 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. The book can be used both as a student textbook and as a professional reference for practitioners who use network optimization methods to model and solve problems.

Author Notes

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.

1 Multiobjective Genetic Algorithms	p. 1
1.1 Introduction	p. 1
1.1.1 General Structure of a Genetic Algorithm	p. 2
1.1.2 Exploitation and Exploration	p. 3
1.1.3 Population-based Search	p. 4
1.1.4 Major Advantages	p. 4
1.2 Implementation of Genetic Algorithms	p. 5
1.2.1 GA Vocabulary	p. 5
1.2.2 Encoding Issue	p. 6
1.2.3 Fitness Evaluation	p. 10
1.2.4 Genetic Operators	p. 10
1.2.5 Handling Constraints	p. 13
1.3 Hybrid Genetic Algorithms	p. 15
1.3.1 Genetic Local Search	p. 16
1.3.2 Parameter Adaptation	p. 18
1.4 Multiobjective Genetic Algorithms	p. 25
1.4.1 Basic Concepts of Multiobjective Optimizations	p. 26
1.4.2 Features and Implementation of Multiobjective GA	p. 29
1.4.3 Fitness Assignment Mechanism	p. 30
1.4.4 Performance Measures	p. 41
References	p. 44
2 Basic Network Models	p. 49
2.1 Introduction	p. 49
2.1.1 Shortest Path Model: Node Selection and Sequencing	p. 50
2.1.2 Spanning Tree Model: Arc Selection	p. 51
2.1.3 Maximum Flow Model: Arc Selection and Flow Assignment	p. 52
2.1.4 Representing Networks	p. 53
2.1.5 Algorithms and Complexity	p. 54
2.1.6 NP-Complete	p. 55
2.1.7 List of NP-complete Problems in Network Design	p. 56
2.2 Shortest Path Model	p. 57
2.2.1 Mathematical Formulation of the SPP Models	p. 58
2.2.2 Priority-based GA for SPP Models	p. 60
2.2.3 Computational Experiments and Discussions	p. 72
2.3 Minimum Spanning Tree Models	p. 79
2.3.1 Mathematical Formulation of the MST Models	p. 83
2.3.2 PrimPred-based GA for MST Models	p. 85
2.3.3 Computational Experiments and Discussions	p. 96
2.4 Maximum Flow Model	p. 96
2.4.1 Mathematical Formulation	p. 99
2.4.2 Priority-based GA for MXF Model	p. 100
2.4.3 Experiments	p. 105
2.5 Minimum Cost Flow Model	p. 107
2.5.1 Mathematical Formulation	p. 108
2.5.2 Priority-based GA for MCF Model	p. 110
2.5.3 Experiments	p. 113
2.6 Bicriteria MXF/MCF Model	p. 115
2.6.1 Mathematical Formulations	p. 118
2.6.2 Priority-based GA for bMXF/MCF Model	p. 119
2.6.3 i-awGA for bMXF/MCF Model	p. 123
2.6.4 Experiments and Discussion	p. 125
2.7 Summary	p. 128
References	p. 130
3 Logistics Network Models	p. 135
3.1 Introduction	p. 135
3.2 Basic Logistics Models	p. 139
3.2.1 Mathematical Formulation of the Logistics Models	p. 139
3.2.2 Prüfer Number-based GA for the Logistics Models	p. 146
3.2.3 Numerical Experiments	p. 152
3.3 Location Allocation Models	p. 154
3.3.1 Mathematical Formulation of the Logistics Models	p. 156
3.3.2 Location-based GA for the Location Allocation Models	p. 159
3.3.3 Numerical Experiments	p. 170
3.4 Multi-stage Logistics Models	p. 175
3.4.1 Mathematical Formulation of the Multi-stage Logistics	p. 176
3.4.2 Priority-based GA for the Multi-stage Logistics	p. 185
3.4.3 Numerical Experiments	p. 190
3.5 Flexible Logistics Model	p. 193
3.5.1 Mathematical Formulation of the Flexible Logistics Model	p. 196
3.5.2 Direct Path-based GA for the Flexible Logistics Model	p. 202
3.5.3 Numerical Experiments	p. 206
3.6 Integrated Logistics Model with Multi-time Period and Inventory	p. 208
3.6.1 Mathematical Formulation of the Integrated Logistics Model	p. 210
3.6.2 Extended Priority-based GA for the Integrated Logistics Model	p. 213
3.6.3 Local Search Technique	p. 218
3.6.4 Numerical Experiments	p. 221
3.7 Summary	p. 222
References	p. 225
4 Communication Network Models	p. 229
4.1 Introduction	p. 229
4.2 Centralized Network Models	p. 234
4.2.1 Capacitated Multipoint Network Models	p. 235
4.2.2 Capacitated QoS Network Model	p. 242
4.3 Backbone Network Model	p. 246
4.3.1 Pierre and Legault's Approach	p. 248
4.3.2 Numerical Experiments	p. 252
4.3.3 Konak and Smith's Approach	p. 253
4.3.4 Numerical Experiments	p. 257
4.4 Reliable Network Models	p. 257
4.4.1 Reliable Backbone Network Model	p. 259
4.4.2 Reliable Backbone Network Model with Multiple Goals	p. 269
4.4.3 Bicriteria Reliable Network Model of LAN	p. 274
4.4.4 Bi-level Network Design Model	p. 283
4.5 Summary	p. 290
References	p. 291
5 Advanced Planning and Scheduling Models	p. 297
5.1 Introduction	p. 297
5.2 Job-shop Scheduling Model	p. 303
5.2.1 Mathematical Formulation of JSP	p. 304
5.2.2 Conventional Heuristics for JSP	p. 305
5.2.3 Genetic Representations for JSP	p. 316
5.2.4 Gen-Tsujimura-Kubota's Approach	p. 325
5.2.5 Cheng-Gen-Tsujimura's Approach	p. 326
5.2.6 Gonçalves-Magalhacs-Resende's Approach	p. 330
5.2.7 Experiment on Benchmark Problems	p. 335
5.3 Flexible Job-shop Scheduling Model	p. 337
5.3.1 Mathematical Formulation of fJSP	p. 338
5.3.2 Genetic Representations for fJSP	p. 340
5.3.3 Multistage Operation-based GA for fJSP	p. 344
5.3.4 Experiment on Benchmark Problems	p. 353
5.4 Integrated Operation Sequence and Resource Selection Model	p. 355
5.4.1 Mathematical Formulation of iOS/RS	p. 358
5.4.2 Multistage Operation-based GA for iOS/RS	p. 363
5.4.3 Experiment and Discussions	p. 372
5.5 Integrated Scheduling Model with Multi-plant	p. 376
5.5.1 Integrated Data Structure	p. 379
5.5.2 Mathematical Models	p. 381
5.5.3 Multistage Operation-based GA	p. 383
5.5.4 Numerical Experiment	p. 389
5.6 Manufacturing and Logistics Model with Pickup and Delivery	p. 395
5.6.1 Mathematical Formulation	p. 395
5.6.2 Multiobjective Hybrid Genetic Algorithm	p. 399
5.6.3 Numerical Experiment	p. 407
5.7 Summary	p. 412
References	p. 412
6 Project Scheduling Models	p. 419
6.1 Introduction	p. 419
6.2 Resource-constrained Project Scheduling Model	p. 421
6.2.1 Mathematical Formulation of rc-PSP Models	p. 422
6.2.2 Hybrid GA for rc-PSP Models	p. 426
6.2.3 Computational Experiments and Discussions	p. 434
6.3 Resource-constrained Multiple Project Scheduling Model	p. 438
6.3.1 Mathematical Formulation of rc-mPSP Models	p. 440
6.3.2 Hybrid GA for rc-mPSP Models	p. 444
6.3.3 Computational Experiments and Discussions	p. 451
6.4 Resource-constrained Project Scheduling Model with Multiple Modes	p. 457
6.4.1 Mathematical Formulation of rc-PSP/mM Models	p. 457
6.4.2 Adaptive Hybrid GA for rc-PSP/mM Models	p. 461
6.4.3 Numerical Experiment	p. 470
6.5 Summary	p. 472
References	p. 472
7 Assembly Line Balancing Models	p. 477
7.1 Introduction	p. 477
7.2 Simple Assembly Line Balancing Model	p. 480
7.2.1 Mathematical Formulation of sALB Models	p. 480
7.2.2 Priority-based GA for sALB Models	p. 484
7.2.3 Computational Experiments and Discussions	p. 492
7.3 U-shaped Assembly Line Balancing Model	p. 493
7.3.1 Mathematical Formulation of uALB Models	p. 495
7.3.2 Priority-based GA for uALB Models	p. 499
7.3.3 Computational Experiments and Discussions	p. 505
7.4 Robotic Assembly Line Balancing Model	p. 505
7.4.1 Mathematical Formulation of rALB Models	p. 509
7.4.2 Hybrid GA for rALB Models	p. 512
7.4.3 Computational Experiments and Discussions	p. 523
7.5 Mixed-model Assembly Line Balancing Model	p. 526
7.5.1 Mathematical Formulation of mALB Models	p. 529
7.5.2 Hybrid GA for mALB Models	p. 532
7.5.3 Rekiek and Delchambre's Approach	p. 542
7.5.4 Ozmehmet Tasan and Tunali's Approach	p. 543
7.6 Summary	p. 546
References	p. 546
8 Tasks Scheduling Models	p. 551
8.1 Introduction	p. 551
8.1.1 Hard Real-time Task Scheduling	p. 553
8.1.2 Soft Real-time Task Scheduling	p. 557
8.2 Continuous Task Scheduling	p. 562
8.2.1 Continuous Task Scheduling Model on Uniprocessor System	p. 563
8.2.2 Continuous Task Scheduling Model on Multiprocessor System	p. 575
8.3 Real-time Task Scheduling in Homogeneous Multiprocessor	p. 583
8.3.1 Soft Real-time Task Scheduling Problem (sr-TSP) and Mathematical Model	p. 584
8.3.2 Multiobjective GA for srTSP	p. 586
8.3.3 Numerical Experiments	p. 592
8.4 Real-time Task Scheduling in Heterogeneous Multiprocessor System	p. 595
8.4.1 Soft Real-time Task Scheduling Problem (sr-TSP) and Mathematical Model	p. 595
8.4.2 SA-based Hybrid GA Approach	p. 597
8.4.3 Numerical Experiments	p. 601
8.5 Summary	p. 602
References	p. 604
9 Advanced Network Models	p. 607
9.1 Airline Fleet Assignment Models	p. 607
9.1.1 Fleet Assignment Model with Connection Network	p. 613
9.1.2 Fleet Assignment Model with Time-space Network	p. 624
9.2 Container Terminal Network Model	p. 636
9.2.1 Berth Allocation Planning Model	p. 639
9.2.2 Multi-stage Decision-based GA	p. 643
9.2.3 Numerical Experiment	p. 646
9.3 AGV Dispatching Model	p. 651
9.3.1 Network Modeling and Mathematical Formulation	p. 652
9.3.2 Random Key-based GA	p. 658
9.3.3 Numerical Experiment	p. 664
9.4 Car Navigation Routing Model	p. 666
9.4.1 Data Analyzing	p. 667
9.4.2 Mathematical Formulation	p. 670
9.4.3 Improved Fixed Length-based GA	p. 672
9.4.4 Numerical Experiment	p. 677
9.5 Summary	p. 681
References	p. 682
Index	p. 687

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents