Operations Research Proceedings 2014 (eBook)

Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), RWTH Aachen University, Germany, September 2-5, 2014

Marco Lübbecke, Arie M.C.A. Koster, Peter Letmathe, Reinhard Madlener, Britta Peis, Grit Walther (Herausgeber)

eBook Download: PDF

2016 | 1st ed. 2016
XIV, 659 Seiten
Springer International Publishing (Verlag)
978-3-319-28697-6 (ISBN)

Infos

This book contains a selection of refereed papers presented at the 'International Conference on Operations Research (OR 2014)', which took place at RWTH Aachen University, Germany, September 2-5, 2014. More than 800 scientists and students from 47 countries attended OR 2014 and presented more than 500 papers in parallel topical streams, as well as special award sessions. The theme of the conference and its proceedings is 'Business Analytics and Optimization'.

Inhalt

Preface 6
Contents 7
Experimental Validation of an Enhanced System Synthesis Approach 15
1 Introduction 15
2 Problem Description 16
3 Mixed Integer Linear Program 16
4 Experimental Validation 17
4.1 The Test Rig 18
4.2 Comparison of Optimization Results and Measurements 19
5 Conclusion 21
References 21
Stochastic Dynamic Programming Solution of a Risk-Adjusted Disaster Preparedness and Relief Distribution Problem 22
1 Introduction 22
2 Risk-Adjusted Multistage Stochastic Programming Model 23
3 Stochastic Dual Dynamic Programming Applications 25
3.1 Numerical Results 26
4 Conclusions 27
References 27
Solution Approaches for the Double-Row Equidistant Facility Layout Problem 29
1 Introduction 29
2 The Structure of Optimal Layouts 30
3 Formulations 31
4 Computational Experiments 33
References 35
Simulation of the System-Wide Impact of Power-to-Gas Energy Storages by Multi-stage Optimization 36
1 Introduction 36
2 Mathematical Model 37
2.1 Objective Function 37
2.2 Constraints 38
3 Developed Method 39
4 Exemplary Results 40
5 Conclusions 41
References 41
An Approximation Result for Matchings in Partitioned Hypergraphs 42
1 Introduction 42
2 Definitions 43
3 Polyhedral Investigations 44
4 Integrality Gap 45
References 47
On Class Imbalance Correction for Classification Algorithms in Credit Scoring 48
1 Introduction 48
2 Methodology 49
3 Experiments 50
4 Results and Summary 53
References 53
The Exact Solution of Multi-period Portfolio Choice Problem with Exponential Utility 55
1 Introduction 55
2 Multi-period Portfolio Problem for an Exponential Utility 56
2.1 Multi-period Portfolio Weights 58
3 Summary 60
References 60
On the Discriminative Power of Tournament Solutions 62
1 Introduction 62
2 Methodology 63
2.1 Preference Profiles and Tournament Solutions 63
2.2 Empirical Data 64
2.3 Stochastic Models 64
3 Experimental Results and Discussion 65
References 67
An Actor-Oriented Approach to Evaluate Climate Policies with Regard to Resource Intensive Industries 68
1 Introduction 68
2 Previous Works and Estimation of Plant Configurations 69
3 Actor-Oriented Simulation Model 70
4 Results of an Example Application 72
5 Conclusions 73
References 73
Upper Bounds for Heuristic Approaches to the Strip Packing Problem 74
1 Introduction 74
2 Two-Dimensional Approaches 75
3 Three-Dimensional Approaches 76
4 Conclusions and Outlook 79
References 79
An Approximative Lexicographic Min-Max Approach to the Discrete Facility Location Problem 80
1 Introduction 80
2 Problem Formulation 81
3 The Algorithm A-LEX 82
4 Numerical Experiments 83
5 Conclusions 84
References 85
Effects of Profit Taxes in Matrix Games 86
1 Introduction 86
2 The Model 87
3 Results for Relative and Constant Profit Taxes 88
4 Conclusion and Open Questions 91
References 91
Extension and Application of a General Pickup and Delivery Model for Evaluating the Impact of Bundling Goods in an Urban Environment 92
1 Introduction 92
2 Methodology 93
3 Case Study 96
4 Results 97
References 98
Optimizing Time Slot Allocation in Single Operator Home Delivery Problems 99
1 Introduction 99
2 Modeling 100
3 Defining and Computing Assignment Policies 102
4 Computational Results 103
References 105
Robust Scheduling with Logic-Based Benders Decomposition 106
1 Introduction 106
2 Modeling the Problem 107
3 Logic-Based Benders Decomposition 108
4 Computational Results 110
5 Conclusion 111
References 111
Optimal Adaptation Process of Emergency Medical Services Systems in a Changing Environment 113
1 Problem Description and Criteria of an Optimal Adaptation Process 113
2 Model and Solution Approach 114
3 Case Study and Results 117
4 Conclusion and Outlook 118
References 118
Strategic Network Planning of Recycling of Photovoltaic Modules 120
1 Decision Situation and Model Requirements 120
2 Strategic Network Planning Approach for PV Recycling 122
3 Strategic Network Model Enhanced with Resource Criticalities 123
4 Case Study and Computational Results 124
5 Conclusion and Outlook 125
References 125
Designing a Feedback Control System via Mixed-Integer Programming 126
1 Introduction 126
2 State of the Art 127
3 Tank Level Control 128
4 Conclusion 131
References 131
Fair Cyclic Roster Planning---A Case Study for a Large European Airport 133
1 Introduction 133
2 Customers Fairness Rules 134
3 Transforming a Roster into a Fair Roster 135
4 Numerical Results 137
5 Conclusions 138
References 138
Why Does a Railway Infrastructure Company Need an Optimized Train Path Assignment for Industrialized Timetabling? 140
1 Introduction 140
2 Requirements and Constraints of the Slot Assignment Model 142
3 Practical Use of the Optimization Model 143
4 Conclusion and Outlook 145
References 145
A Polyhedral Study of the Quadratic Traveling Salesman Problem 146
1 Introduction 146
2 Problem Description 147
3 Polyhedral Study of PAQTSPn 148
References 151
New Inequalities for 1D Relaxations of the 2D Rectangular Strip Packing Problem 153
1 Introduction 153
2 LP-Based Constructive Algorithm 154
2.1 1D-CSP and 1D-MCSP Adapted to 2D-SPP 154
2.2 Algorithm 155
3 Constraints for Bottom Patterns 156
4 Higher Level Continuing 157
5 Numerical Experiments and Conclusions 158
References 159
Representing Production Scheduling with Constraint Answer Set Programming 160
1 Introduction 160
2 Lot Scheduling Problem 161
3 Constraint Answer Set Programming 162
4 Modeling Production Scheduling 163
5 Results 165
References 166
Day-Ahead Versus Intraday Valuation of Flexibility for Photovoltaic and Wind Power Systems 167
1 Introduction and Background 167
2 Value Formulation 168
3 Value Comparison 170
4 Conclusion 172
References 172
A Real Options Model for the Disinvestment in Conventional Power Plants 173
1 Introduction 174
2 Model Specification 174
3 Case Study and Results 176
4 Conclusion 178
References 178
Political Districting for Elections to the German Bundestag: An Optimization-Based Multi-stage Heuristic Respecting Administrative Boundaries 180
1 Electoral Districts in Elections to the German Bundestag 180
2 The Political Districting Problem 181
3 Optimization-Based Multi-stage Heuristic 183
4 In Search of an Optimal Number of German Electoral Districts 185
References 185
Duality for Multiobjective Semidefinite Optimization Problems 187
1 Introduction and Preliminaries 187
2 Duality for Multiobjective Semidefinite Optimization Problems 188
References 192
Algorithms for Controlling Palletizers 194
1 Introduction 194
2 Preliminaries 196
3 Algorithms for the FIFO Stack-Up Problem 197
References 199
Capital Budgeting Problems: A Parameterized Point of View 201
1 Introduction 201
2 Single-Period Capital Budgeting Problem 202
3 Multi-period Capital Budgeting Problem 204
References 206
How to Increase Robustness of Capable-to-Promise 208
1 Problem 208
2 Numerical Testbed 209
3 Numerical Results 210
4 Conclusions 213
References 214
An Iterated Local Search for a Re-entrant Flow Shop Scheduling Problem 215
1 Introduction 215
2 Problem Description 216
3 Proposed Iterated Local Search 217
3.1 Initial Solution 217
3.2 Shaking 218
3.3 Local Search 218
4 Computational Experiments 218
5 Conclusions 220
References 220
Selecting Delivery Patterns for Grocery Chains 221
1 Problem Description 221
2 Model Formulation 223
3 Solution Approach 224
4 Numerical Example 225
5 Summary 226
References 226
Towards a Customer-Oriented Queuing in Service Incident Management 227
1 Introduction 227
2 Problem Formulation and Solution Approach 228
3 Computational Results 231
4 Conclusions and Recommendations for Further Research 232
References 232
A Lagrangian Relaxation Algorithm for Modularity Maximization Problem 234
1 Introduction 234
2 Modularity Maximization Problem 235
3 Lagrangian Relaxation and Lagrangian Dual Problem 236
4 Proposed Algorithm 237
5 Computational Experiments 238
References 240
Row and Column Generation Algorithm for Maximization of Minimum Margin for Ranking Problems 241
1 Introduction 241
2 Hard Margin Problem for Separable Case 242
3 Kernel Technique for Hard Margin Problem 243
4 Soft Margin Problems for Non-separable Case 244
5 Illustrative Example and Conclusion 246
References 247
Dual Sourcing Inventory Model with Uncertain Supply and Advance Capacity Information 248
1 Introduction 248
2 Model Formulation 249
3 Characterization of the Optimal Policy 251
4 The Value of Advance Capacity Information 251
5 Conclusions 252
References 253
Integrated Line Planning and Passenger Routing: Connectivity and Transfers 254
1 Introduction 254
2 Steiner Connectivity Problem 255
3 A Transfer Model for Line Planning 257
4 Computational Results and Potsdam Line Plan 2010 259
References 260
Robust Discrete Optimization Problems with the WOWA Criterion 261
1 Problem Formulation and Motivation 261
2 Complexity of the Problem 263
3 Approximation Algorithm 264
4 Conclusions 266
References 266
Robust Single Machine Scheduling Problem with Weighted Number of Late Jobs Criterion 268
1 Preliminaries 268
2 Single Machine Scheduling Problem with the Number of Late Jobs Criterion Under Uncertainty 269
3 Single Machine Scheduling Problem with the Weighted Number of Late Jobs Criterion Under Uncertainty 271
References 273
Price of Anarchy in the Link Destruction (Adversary) Model 274
1 Equilibrium Concepts for Graphs 274
2 Link Destruction Model 276
3 PoA for Nash Equilibrium 277
4 PoA for Pairwise Stability and Pairwise Nash Equilibrium 278
References 279
Decision Support System for Week Program Planning 281
1 Introduction 281
2 Research Issue---Procedure of Filling 282
3 The Logistic Assistance System 283
4 Dispatching Algorithm 284
5 Results 285
6 Conclusion and Outlook 286
References 287
On Multi-product Lot-Sizing and Scheduling with Multi-machine Technologies 288
1 Introduction 288
2 Problem Formulation 289
3 Problem Complexity in Case of Zero Setup Times 290
4 Mixed Integer Programming Model 290
5 Polynomially Solvable Cases 292
6 Conclusion 293
References 293
Condition-Based Maintenance Policies for Modular Monotic Multi-state Systems 294
1 Introduction 294
2 A Deterministic Model 295
2.1 Definitions 295
2.2 Development of the Model 296
3 Solution Approach for a Serial System with Two Components 297
4 Stochastic Model and Approximate Dynamic Programming 298
5 Conclusions 299
References 299
An Optimization Model and a Decision Support System to Optimize Car Sharing Stations with Electric Vehicles 300
1 Introduction 301
2 Optimization Model and Decision Support System 301
3 Benchmarks in Hannover and Zürich 303
4 Generalization, Limitations and Conclusion 306
References 307
Optimising Energy Procurement for Small and Medium-Sized Enterprises 308
1 Introduction 308
2 Energy Procurement of SMEs 309
3 Two-Stage Optimisation Model 310
4 Case Study 311
5 Conclusion 313
References 313
Approximation Schemes for Robust Makespan Scheduling Problems 314
1 Introduction 314
2 Min Max Parallel Machine Scheduling Problem 315
3 Min Max Flow Shop Scheduling Problem 317
4 Approximation Scheme for Online Problems 319
References 319
The Price of Fairness for a Small Number of Indivisible Items 321
1 Introduction 321
2 Basic Notation and Definitions 322
3 The Smallest Case: One Item per Agent 323
3.1 Special Structure of the Optimal Solutions for m=n 324
3.2 An Improved ILP Formulation and an Almost Tight Bound for penvy(n,n) 324
4 Bounds for penvy(n,m) for a Small Number of Items 325
5 Conclusion 326
References 326
Robustness Concepts for Knapsack and Network Design Problems Under Data Uncertainty 327
1 Introduction 327
2 Part I: Concepts 328
3 Part II: Robust Knapsack Problems 329
4 Part III: Robust Network Design Problems 331
5 Conclusions 332
References 332
An Insight to Aviation: Rostering Ground Personnel in Practice 334
1 Introduction 334
2 Related Work 335
3 Monthly Rostering of Ground Personnel 336
4 Practical Experience 338
5 Conclusions 340
References 340
Consensus Information and Consensus Rating 341
1 Introduction 341
2 Information Set and Consensus Information 342
2.1 No Contradictory Information 343
2.2 Contradictory Information 344
3 Rating and Default Probability 345
4 Conclusion 346
References 346
Integration of Prospect Theory into the Outranking Approach PROMETHEE 347
1 Introduction 347
2 The Integration of Prospect into PROMETHEE 348
3 Feedback from an Application of PT-PROMETHEE Within a Case Study 351
4 Conclusion 351
References 352
Multistage Optimization with the Help of Quantified Linear Programming 353
1 Introduction 353
2 Quantified Linear (Integer) Programming 354
3 Computational Results 357
4 Conclusion 358
References 358
Analysis of Ambulance Location Models Using Discrete Event Simulation 360
1 Introduction 360
2 Ambulance Location Models 361
3 Discrete Event Simulation of EMS Systems 363
4 Case Study and Results 364
5 Conclusion and Outlook 365
References 365
Tight Upper Bounds on the Cardinality Constrained Mean-Variance Portfolio Optimization Problem Using Truncated Eigendecomposition 367
1 Introduction 367
2 Theory and Solution Principle 368
3 Numerical Results and Conclusion 371
References 373
Scheduling Identical Parallel Machines with a Fixed Number of Delivery Dates 375
1 Introduction 375
2 Problem Statement and Characteristics 376
3 Mathematical Programming Formulation 377
4 Numerical Results 378
5 Conclusion 379
References 380
Kinetic Models for Assembly Lines in Automotive Industries 381
1 Introduction 381
2 Mathematical Modeling 382
2.1 Microscopic Model 382
2.2 Macroscopic Equations 384
3 Experimental Results 385
4 Conclusion 386
References 387
Optimization of Vehicle Routes with Delivery and Pickup for a Rental Business: A Case Study 388
1 Introduction 388
2 Vehicle Routing for a Rental Business 389
3 Integer Programming Formulation and Solution Strategy 390
4 Computational Experiments 391
5 Conclusions and Future Work 393
References 394
An Ant Colony System Adaptation to Deal with Accessibility Issues After a Disaster 395
1 Introduction 395
2 Problem Modeling 396
3 Ant Colony System Adaptation 397
4 An Illustrative Example 399
5 Conclusions 400
References 400
Modelling and Solving a Train Path Assignment Model 402
1 Introduction and Motivation 402
2 Basic Models 403
3 A Branch Cut and Price Approach 404
4 Computational Results 406
References 407
A New Approach to Freight Consolidation for a Real-World Pickup-and-Delivery Problem 408
1 Introduction 408
2 The Recursive Savings Algorithm 409
3 Benchmarks and Results 412
4 Conclusion 413
References 414
High Multiplicity Scheduling with Switching Costs for Few Products 415
1 Introduction 415
2 The Model and Basic Properties 416
3 Single Product Case 417
4 Continuous Case with Two Products 418
References 421
Sampling-Based Objective Function Evaluation Techniques for the Orienteering Problem with Stochastic Travel and Service Times 422
1 Introduction 422
2 Problem Definition 423
3 Objective Function Evaluators 424
4 Experiments 425
5 Conclusions 427
References 427
Optimized Pattern Design for Photovoltaic Power Stations 428
1 Optimization of Photovoltaic Power Plants 428
1.1 Analyzed Problem 429
2 Mathematical Formulation 430
3 Computational Results 431
4 Summary 433
References 433
What Are New Insights Using Optimized Train Path Assignment for the Development of Railway Infrastructure? 434
1 Introduction 435
2 Determining the Potential for Railway Infrastructure Development 435
2.1 Routing of Freight Traffic and Capacity Utilization 436
2.2 Quality and Transport Time 436
2.3 Bottlenecks and Spare Capacity 437
2.4 From Bottlenecks to Measures for the Development of Railway Infrastructure 439
3 Conclusion and Outlook 440
References 440
The Cycle Embedding Problem 441
1 The Cycle Embedding Problem (CEP) 441
2 Application to Rolling Stock Rotation Planning 444
References 447
Dispatch of a Wind Farm with a Battery Storage 448
1 Introduction 448
2 Problem Formulation and Solution Approach 449
3 Computational Results 451
3.1 Data 451
3.2 Results for Wind-Battery System 451
3.3 Results for Reference Scenarios 452
3.4 Comparison 453
4 Conclusions and Recommendations for Further Research 453
References 453
Exact Algorithms for the Vehicle Routing Problem with Soft Time Windows 455
1 Introduction 455
2 A Mathematical Model for Minimal Time Windows Violation 457
3 Branch-and-Cut-and-Price Algorithm for the VRPSTW 458
4 Alternative Formulation and Bisection Search 458
References 460
Impact of Heat Storage Capacity on CHP Unit Commitment Under Power Price Uncertainties 461
1 Introduction 461
2 CHP Unit Commitment Under Power-Price Uncertainties 462
3 Simulation Study with Varying Heat Storage Capacities and Uncertain Power Prices 464
4 Conclusion and Outlook 466
References 466
Optimizing Information Security Investments with Limited Budget 467
1 Introduction 467
2 Security Optimization in the Context of Risk Management 468
3 Problem Description 469
4 Computational Results 470
5 Conclusion 472
References 473
Cut-First Branch-and-Price Second for the Capacitated Arc-Routing Problem 474
1 Capacitated Arc-Routing Problem 474
2 Cut-First Branch-and-Price Second 475
2.1 Cutting 475
2.2 Master Problem 475
2.3 Branching 476
2.4 Pricing Problem and Relaxations 477
3 Computational Results 478
4 Conclusion 478
References 479
Solving a Rich Position-Based Model for Dairy Products 480
1 Introduction 480
2 Problem Description 481
3 Solution Approach 483
4 First Solutions 484
5 Summary and Outlook 484
References 486
A European Investment and Dispatch Model for Determining Cost Minimal Power Systems with High Shares of Renewable Energy 487
1 Introduction 487
2 Mathematical Programming 488
2.1 Multiple Markets Investment Model---MMIM 489
2.2 Multiple Markets Dispatch Model---MMDM 489
2.3 Single Market Dispatch Model---SMDM 491
3 Case Study 492
4 Examplary Results 492
References 493
Pre-selection Strategies for Dynamic Collaborative Transportation Planning Problems 494
1 Introduction 494
2 Selection of Collaborative Requests 495
3 Pre-selection Strategies 496
4 Computational Experiments 497
5 Conclusion 499
References 500
Optimal Operation of a CHP Plant for the Energy Balancing Market 501
1 Introduction 501
2 Participation of a CHP Plant in the Energy Balancing Market 502
3 Optimization Model for the Operation of a CHP Plant 503
4 Illustrative Results 505
5 Conclusion 506
References 507
Gas Network Extension Planning for Multiple Demand Scenarios 508
1 Introduction 508
2 Planning for Multiple Demand Scenarios 509
3 Scenario Decomposition 510
3.1 Reusing Solutions 511
4 Computational Results 512
5 Outlook 513
References 513
Impacts of Electricity Consumers' Unit Commitment on Low Voltage Networks 514
1 Introduction 514
2 Scheduling of Consumers' Generation, Demand, and Storage 515
3 A Local Electricity System Modeled as Multi-agent System 517
4 Input Parameters and Results 518
5 Conclusion 519
References 520
Congestion Games with Multi-Dimensional Demands 521
1 Introduction 521
2 Characterizations of k-Consistency 524
References 526
Unit Commitment by Column Generation 527
1 Introduction 527
2 Unit Commitment Problem 528
3 Application of Column Generation 529
4 Numerical Experiments 530
5 Concluding Remarks 532
References 532
Parallel Algorithm Portfolio with Market Trading-Based Time Allocation 534
1 Introduction 534
2 Problem Formulation 535
3 Proposed Algorithm Portfolio 536
4 Experimental Results 537
5 Conclusions 540
References 541
Global Solution of Bilevel Programming Problems 542
1 Introduction 542
2 Reformulations 543
3 Relations of Global Solutions 544
References 547
Robustness to Time Discretization Errors in Water Network Optimization 548
1 Introduction 548
2 Problem Description 549
3 Time Discretization 550
4 Robustness to Discretization Error 552
5 Conclusion 554
References 554
Forecasting Intermittent Demand with Generalized State-Space Model 556
1 Introduction 556
2 Model 557
2.1 Mixture Distribution and Components 557
2.2 State-Space Expression 558
2.3 Parameter Estimation 559
3 Comparison Analysis 559
3.1 Analyzing Data, and Models for Comparison 559
3.2 Results 562
4 Conclusions 562
References 562
Optimal Renewal and Electrification Strategy for Commercial Car Fleets in Germany 564
1 Introduction 564
2 Methodology 565
3 The Data 566
4 Results 567
4.1 Normalized Sensitivity and Scenario Analysis 567
5 Conclusions 569
References 570
A Time-Indexed Generalized Vehicle Routing Model for Military Aircraft Mission Planning 571
1 Introduction 571
2 Problem Setting 572
3 Mathematical Model 573
4 Dantzig--Wolfe Decomposition 575
5 Results and Conclusion 576
References 577
Adapting Exact and Heuristic Procedures in Solving an NP-Hard Sequencing Problem 578
1 Introduction 578
2 Modeling the Problem 579
3 Algorithm 581
4 Solution 582
References 584
Strategic Deterrence of Terrorist Attacks 585
1 Introduction 585
2 The Basic Model 586
3 Traditional Risk Analysis as Adaptive Play 587
4 Discussion 589
References 590
Optimal Airline Networks, Flight Volumes, and the Number of Crafts for New Low-Cost Carrier in Japan 591
1 Introduction 591
2 Proposed Model 592
3 Method of Parameter Assignments 594
4 Example Calculations 595
5 Conclusion 596
References 596
Variable Speed in Vertical Flight Planning 598
1 Introduction and Motivation 598
2 Mathematical Model 599
3 Experiments and Results 602
References 604
A Fast Greedy Algorithm for the Relocation Problem 605
1 Introduction 605
2 System Description 606
3 Greedy Algorithm 606
4 Relocation Policies 607
4.1 Policy 1 607
4.2 Policy 2 608
4.3 Policy 3 608
5 Results and Experimentation 609
6 Conclusion and Future Works 610
References 610
Multicriteria Group Choice via Majority Preference Relation Based on Cone Individual Preference Relations 611
1 Introduction 611
2 Model of Multicriteria Individual Choice Problem 612
3 Majority Preference Relation and Its Properties 613
4 Using ``Quanta'' of Information in Case of 3 DMs 614
5 Conclusion 616
References 616
Author Index 618

Produkt-Details

• Erscheint lt. Verlag: 20.2.2016
• Reihe/Serie: Operations Research Proceedings
• Reihe/Serie: Operations Research Proceedings
• Zusatzinfo: XIV, 659 p. 105 illus. in color.
• Verlagsort: Cham
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• Themenwelt: Wirtschaft ► Allgemeines / Lexika
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Logistik / Produktion
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Planung / Organisation
• Schlagworte: Business Analytics • Computational Economics • Engineering Economics • German Operations Research society • GOR • Optimization • OR Applications in Energy • OR Applications in Industry • OR Applications in Mobility
• ISBN-10: 3-319-28697-8 / 3319286978
• ISBN-13: 978-3-319-28697-6 / 9783319286976