The Palgrave Handbook of Operations Research

Preface
Acknowledgments
Contents
Contributors
List of Figures
List of Tables
Part I Discrete (Combinatorial) Optimisation
1 Bilevel Discrete Optimisation: Computational Complexity and Applications
1.1 Introduction
1.2 Main Definitions and Properties
1.3 Computational Methods
1.3.1 Exact Methods
1.3.2 Metaheuristics
1.4 Computational and Approximation Complexity
1.4.1 Polynomial Hierarchy
1.4.2 Σ2P-Hard Bilevel Programming Problems
1.4.3 Approximation Hierarchy
1.5 Applications
1.6 Conclusion
References
2 Discrete Location Problems with Uncertainty
2.1 Introduction
2.2 The Single-Source Capacitated Facility Location Problem with Uncertainty
2.3 Covering Location Problems with Uncertainty
2.3.1 Set Covering Models with Uncertainty
2.3.2 Maximum Covering Models with Uncertainty
2.3.3 Other Covering Location Models
2.4 Hub Location Problems with Uncertainty
2.4.1 Demand, Cost, and Time Uncertainty
2.4.2 Network Reliability and Resilience
2.4.3 Hub Interdiction and Fortification
2.5 Conclusions
References
3 Integrated Vehicle Routing Problems: A Survey
3.1 Introduction
3.2 Inventory Routing Problems
3.3 Location Routing Problems
3.4 Routing in Combination with Packing: Routing with Loading Constraints
3.4.1 Introduction to the Class of Problems
3.4.2 The Capacitated Vehicle Routing Problem with Two-Dimensional Loading Constraints
3.4.2.1 Recent Trends in the Literature on the 2L-CVRP
3.4.3 The Capacitated Vehicle Routing Problem with Three-Dimensional Loading Constraints
3.4.3.1 Recent Trends in the Literature on the 3L-CVRP
3.5 Routing in Combination with Routing: Two-Echelon Routing Problems
3.5.1 Introduction to the Class of Problems
3.5.2 The Two-Echelon Capacitated Vehicle Routing Problem
3.5.3 Recent Trends in the Literature on 2E-VRPs
3.6 Conclusions
References
4 The Knapsack Problem and Its Variants: Formulations and Solution Methods
4.1 Introduction
4.2 Variants with a Single Knapsack Constraint
4.2.1 The Multiple-Choice Knapsack Problem
4.2.2 The Discounted Knapsack Problem
4.2.3 The Knapsack Problem with Setup
4.2.4 The Knapsack Problem with Neighbor Constraints
4.2.5 The Knapsack Constrained Maximum Spanning Tree Problem
4.2.6 The Set Union Knapsack Problem
4.2.7 The Precedence Constrained Knapsack Problem
4.2.8 The Disjunctively Constrained Knapsack Problem
4.2.9 The Product Knapsack Problem
4.3 Variants with Multiple Knapsack Constraints
4.3.1 The Multidimensional Knapsack Problem
4.3.2 The Multidimensional Knapsack Problem with Demand Constraints
4.3.3 The Multiple Knapsack Problem
4.3.4 The Compartmentalized Knapsack Problem
4.3.5 The Multiple Knapsack Problem with Color Constraints
4.4 Conclusion and Suggestions
References
5 Rank Aggregation: Models and Algorithms
5.1 Introduction
5.2 Ranking of Elements
5.2.1 Linear Ordering Problem
5.2.2 Rank Aggregation Problem in Cyclic Sequences
5.2.3 Target Visitation Problem
5.2.4 The Center Ranking Problem
5.3 Ranking of Sets from a Ranking of Elements
5.3.1 The Optimal Bucket Order Problem
5.3.2 The Linear Ordering Problem with Clusters
5.3.3 The Linear Ordering Problem of Sets
5.3.4 The Center Ranking Problem of Sets
5.4 Feasible Regions Similarities and Differences Through a Small Example
References
Part II Continuous (Global) Optimisation
6 Multi-Objective Optimization: Methods and Applications
6.1 Introduction to Multi-Objective Optimization
6.2 Solving a Multi-objective Problem
6.2.1 Basic Concepts
6.2.2 Pareto Set Generation
6.2.2.1 ε-Constraint Method
6.2.2.2 Multi-Objective Evolutionary Algorithms
6.2.2.3 Quality of the Pareto-Optimal Set
6.3 Goal Programming
6.4 Compromise Programming
6.5 Applications and Usage
6.5.1 Application of Techniques
6.5.2 Use of Techniques
6.6 Conclusions
References
7 Competitive Facilities Location
7.1 Introduction
7.2 Approaches to Estimating Market Share
7.2.1 Deterministic Rules
7.2.2 Probabilistic Rules
7.2.3 Estimating Attractiveness
7.3 Distance Correction
7.4 Extensions
7.4.1 Minimax Regret Criterion
7.4.2 The Threshold Objective
7.4.3 Leader-Follower Models
7.4.4 Location and Design
7.4.5 Lost Demand
7.4.6 Cannibalization
7.5 Solution Methods
7.5.1 Single Facility
7.5.2 Multiple Facilities
7.5.3 The TLA Method
7.6 Applying the Gravity Rule to Other Objectives
7.6.1 Gravity p-Median
7.6.2 Gravity Hub Location
7.6.3 Gravity Multiple Server
7.7 Summary and Suggestions for Future Research
References
8 Interval Tools in Branch-and-Bound Methods for Global Optimization
8.1 Introduction
8.1.1 Interval Analysis
8.1.2 Aim of the Chapter
8.2 Prototype Interval B&B Method
8.2.1 Bounding Rule
8.2.2 Elimination/Filtering Rules
8.2.3 Selection Rule
8.2.4 Division Rules
8.2.5 Termination Rule
8.2.6 Interval B&B Methods for MINLP Problems
8.3 Bounding Techniques
8.4 Discarding Tests
8.5 Selection of the Next Box to Be Processed
8.6 Subdivision Rule
8.7 Software
8.7.1 Libraries
8.7.2 Packages with Interval B&B Implementations
8.8 Interval B&B Methods for MINLP Problems
References
9 Continuous Facility Location Problems
9.1 Introduction
9.2 Single Facility Location Problems
9.2.1 The Weber (One-Median) Location Problem
9.2.1.1 Extensions to the Basic Weber Problem
9.2.2 The Minimax (One-Center) Location Problem
9.2.3 The Obnoxious Facility Location Problem
9.2.4 Equity Models
9.2.5 Location on a Sphere
9.2.5.1 Calculating Spherical Distances
9.2.5.2 Various Location Models on the Sphere
9.3 Multiple Facilities Location Problems
9.3.1 Conditional Models
9.3.2 The p-Median Location Problem
9.3.3 The p-Center Location Problem
9.3.4 Cover Models
9.3.4.1 Gradual Cover Models
9.3.5 The Multiple Obnoxious Facilities Location Problem
9.3.6 Equity Models
9.3.7 Not Necessarily Patronizing the Closest Facility
9.4 Solution Methods
9.4.1 Generating Replicable Test Problems
9.4.2 Solving Single Facility Problems
9.4.2.1 Solving with the Solver in Excel
9.4.2.2 Voronoi Diagram and Delaunay Triangulation
9.4.2.3 General Global Optimization Algorithms
9.4.2.4 Solving the Weber Problem
9.4.2.5 Solving the One-Center Problem
9.4.2.6 Solving the Obnoxious Facility Problem
9.4.2.7 Solving Spherical Problems
9.4.3 Multiple Facilities Solution Methods
9.4.3.1 p-Median
9.4.3.2 p-Center
9.4.3.3 Multiple Obnoxious Facilities Solution Methods
9.5 Summary and Suggestions for Future Research
References
10 Data Envelopment Analysis: Recent Developments and Challenges
10.1 Introduction
10.2 Background
10.2.1 The CCR Model in the Envelopment and Multiplier Forms
10.2.2 The BCC Model in Envelopment and Multiplier Forms
10.2.3 The Additive Model
10.3 A Short Literature Survey and Trend of Publications on DEA
10.3.1 Statistics Based on Publication Years
10.3.2 Statistics Based on Journals
10.3.3 Statistics Based on Authors
10.3.4 Statistics Based on Keywords
10.3.5 Statistics Based on Page Numbers (Size)
10.4 Recent Theoretical Developments in DEA
10.4.1 Network DEA
10.4.2 Stochastic DEA
10.4.3 Fuzzy DEA
10.4.4 Bootstrapping
10.4.5 Directional Measure and Negative Data
10.4.6 Undesirable Factors
10.4.7 Directional Returns to Scale in DEA
10.5 Recent Applications and Future Developments
10.6 Conclusions
References
Part III Heuristic Search Optimisation
11 An Overview of Heuristics and Metaheuristics
11.1 Introduction
11.1.1 Optimisation Problems
11.1.1.1 Local vs Global Optimality
11.1.1.2 Modelling Approach
11.1.2 The Need for Heuristics
11.1.3 Some Characteristics of Heuristics
11.1.4 Performance of Heuristics
11.1.4.1 Computational Effort
11.1.5 Heuristic Classification and Categorisation
11.2 Improvement-Only Heuristics
11.2.1 Hill-Climbing Methods
11.2.2 Classical Multi-Start
11.2.3 Greedy Randomised Adaptive Search Procedure (GRASP)
11.2.4 Variable Neighbourhood Search (VNS)
11.2.5 Iterated Local Search (ILS)
11.2.6 A Multi-Level Composite Heuristic
11.2.7 Problem Perturbation Heuristics
11.2.8 Some Other Improving Only Methods
11.3 Not Necessarily Improving Heuristics
11.3.1 Simulated Annealing
11.3.2 Threshold-Accepting Heuristics
11.3.3 Tabu Search
11.4 Population-Based Heuristics
11.4.1 Genetic Algorithms
11.4.2 Ant Colony Optimisation
11.4.3 The Bee Algorithm
11.4.4 Particle Swarm Optimisation (PSO)
11.4.5 A Brief Summary of Other Population-Based Approaches
11.5 Some Applications
11.5.1 Radio-Therapy
11.5.2 Sport Management
11.5.3 Educational Timetabling
11.5.4 Nurse Rostering
11.5.5 Distribution Management (Routing)
11.5.6 Location Problems
11.5.7 Chemical Engineering
11.5.8 Civil Engineering Applications
11.6 Conclusion and Research Issues
11.6.1 Conclusion
11.6.2 Potential Research Issues
References
12 Formulation Space Search Metaheuristic
12.1 Introduction
12.2 Literature Review
12.3 Methodology
12.3.1 Stochastic FSS
12.3.2 Deterministic FSS
12.3.3 Variable Neighborhood FSS and Variants
12.4 Some Applications
12.4.1 Circle Packing Problem
12.4.1.1 Reformulation Descent
12.4.1.2 Formulation Space Search
12.4.2 Graph Coloring Problem
12.4.3 Continuous Location Problems
12.4.3.1 Preliminaries
12.4.3.2 Reformulation Local Search for Continuous Location
12.5 Conclusions
References
13 Sine Cosine Algorithm: Introduction and Advances
13.1 Introduction
13.2 Sine Cosine Algorithm (SCA)
13.3 Parameters Involved in the SCA
13.4 Advances in the Sine Cosine Algorithm
13.4.1 Extension of SCA
13.4.1.1 Multi-Objective
13.4.1.2 Binary
13.4.1.3 Discrete
13.4.1.4 Constrained
13.4.1.5 Miscellaneous
13.5 Conclusion
References
14 Less Is More Approach in Heuristic Optimization
14.1 Introduction
14.2 Literature Review of LIMA Implementations
14.3 LIMA Algorithm
14.3.1 What Is More and What Is Less in Algorithm Design
14.3.2 Steps of the LIMA Algorithm
14.4 Applications of LIMA
14.4.1 Minimum Differential Dispersion Problem
14.4.2 Planar p-Median Problem
14.4.3 Multiple Obnoxious Facility Location Problem
14.4.4 Gray Patterns
14.4.5 Discussion
14.5 Conclusions
References
15 The New Era of Hybridisation and Learning in Heuristic Search Design
15.1 Hybridisation Search
15.1.1 Hybridisation of Heuristics with Heuristics
15.1.1.1 Hyper-Heuristics
15.1.1.2 Memetic Algorithm and Its Variants
15.1.1.3 A Brief Summary of Other Metaheuristic Hybridisations
15.1.2 Integrating Heuristics within Exact Methods
15.1.3 Integration of ILP within Heuristics/Metaheuristics
15.1.3.1 Heuristic Concentration (HC)
15.1.3.2 Problem Decomposition
15.1.3.3 Data Mining
15.2 Big Data and Machine Learning
15.2.1 Decision Trees and Random Forest (RM)
15.2.2 Support Vector Machines (SVM)
15.2.3 Neural Networks (NN)
15.2.4 MLs Evaluation Measures
15.3 Deep Learning Heuristics
15.4 Implementation Issues in Heuristic Search Design
15.4.1 Data Structure
15.4.2 Duplication Identification
15.4.3 Cost Function Approximation
15.4.4 Reduction Tests/Neighbourhood Reduction
15.4.5 Parameters and Hyper Parameters Optimisation
15.4.6 Impact of Parallelisation
15.5 Conclusion and Research Issues
References
Part IV Forecasting, Simulation and Prediction
16 Forecasting with Judgment
16.1 Introduction
16.2 Why Is the Use of Judgment so Widespread in Forecasting?
16.2.1 The Benefits of Judgment in Forecasting
16.2.2 The Drawbacks of Using Judgment in Forecasting
16.2.2.1 Motivational Biases
16.2.2.2 Cognitive Factors
16.3 Strategies for Improving the Role of Judgment in Forecasting
16.3.1 Providing Feedback
16.3.2 Providing Advice
16.3.3 Restrictiveness
16.3.4 Decomposition
16.3.5 Correcting Forecasts
16.3.6 Other Improvement Strategies
16.3.7 Improving Forecasts from Groups
16.3.8 Integrating Judgment with Algorithm-based Forecasts
16.4 Conclusions
References
17 Input Uncertainty in Stochastic Simulation
17.1 Introduction
17.2 Characterizing Input Uncertainty
17.3 Confidence Interval Construction and Variance Estimation
17.3.1 Parametric Methods
17.3.1.1 Central Limit Theorem and Delta Method
17.3.1.2 Bayesian Methods
17.3.1.3 Metamodel-Based Methods
17.3.1.4 Green Simulation
17.3.2 Nonparametric Methods
17.3.2.1 Bootstrap: Elementary Schemes
17.3.2.2 Bootstrap: Computational Enhancements
17.3.2.3 Batching, Sectioning, and Sectioned Jackknife
17.3.2.4 Mixture-Based and Nonparametric Bayesian
17.3.2.5 Robust Simulation
17.3.3 Empirical Likelihood
17.4 Other Aspects
17.4.1 Bias Estimation
17.4.2 Online Data
17.4.3 Data Collection vs Simulation Expense
17.4.4 Model Calibration and Inverse Problems
17.5 Simulation Optimization under Input Uncertainty
17.5.1 Selection of the Best under Input Uncertainty
17.5.1.1 Ranking and Selection
17.5.1.2 Subset Selection and Multiple Comparisons with the Best
17.5.2 Global Optimization under Input Uncertainty
17.5.3 Online Optimization with Streaming Input Data
17.6 Future Research Directions
References
18 Fuzzy multi-attribute decision-making: Theory, methods and Applications
18.1 Introduction
18.2 Literature Review of Fuzzy MADM
18.3 Fuzzy MADM Based on the Information Integration
18.3.1 Information Integration and Fuzzy MADM
18.3.2 Fuzzy Aggregation Operators
18.3.3 Supplementary Instruction
18.4 Fuzzy Measures and MADM
18.4.1 Fuzzy Measures
18.4.2 Application of Fuzzy Measures in MADM
18.5 Fuzzy Preference Relations and MADM
18.5.1 Fuzzy Preference Relations
18.5.2 Fuzzy Analytic Hierarchy Process
18.6 Some Other Classical Synthetic Fuzzy MADM Methods
18.6.1 Fuzzy PROMETHEE
18.6.2 Fuzzy ELECTRE
18.6.3 Hesitant Fuzzy TODIM
18.7 Prospects for Future Research Directions
References
19 Importance Measures in Reliability Engineering: An Introductory Overview
19.1 Introduction
19.2 Basic Concepts of Reliability
19.2.1 Reliability Function
19.2.2 System Reliability Analysis
19.3 Importance Measures
19.3.1 Technology-Based Measures
19.3.1.1 Structure Importance
19.3.1.2 Reliability Importance
19.3.1.3 Lifetime Importance
19.3.2 Utility-Based Importance Measures
19.3.3 Importance Measures Based on the Survival Signature
19.3.4 Importance Measures and Some Important Concepts
19.3.4.1 Importance Measures and Risk
19.3.4.2 Importance Measures and Resilience
19.4 Information Needed for Importance Measures
19.5 Applications of Importance Measures
19.6 Concluding Remarks
References
20 Queues with Variable Service Speeds: Exact Results and Scaling Limits
20.1 Introduction
20.2 Queues with Vacation/setup time
20.2.1 Vacation Models
20.2.2 Models with Workload /Queue-Length-Dependent Service
20.2.3 Models with Setup Time
20.2.3.1 Multiserver Model with Setup Time
20.2.3.2 Retrial Model with Setup Time 
20.2.4 Open Problems
20.3 Infinite-Server Queues with Changeable Service
20.3.1 Stability Condition
20.3.2 Exact Analysis
20.3.2.1 Two Types of Service Speeds
20.3.2.2 More than Two Types of Service Speeds
20.3.3 Limit Analysis
20.3.3.1 Limit analysis for a queue length distribution
20.3.3.2 Limit analysis for a queue length process
References
21 Forecasting and its Beneficiaries
21.1 Background
21.2 Forecasting for Social Good
21.3 Barriers to Sharing the Benefits of Forecasting
21.3.1 Access to Resources
21.3.2 Access to Expertise
21.3.3 Communication Issues
21.4 More Effective Communications
21.4.1 Forecast Producers
21.4.2 Commercial Software Developers
21.4.3 Forecasting Academics
21.5 Democratising forecasting
21.5.1 Data Science Initiatives
21.5.2 Democratising Forecasting Initiative
21.5.3 Benefits and Impact of Democratising Forecasting
21.5.4 Challenges in Delivering Democratising Forecasting Workshops
21.5.5 Limitations of the Democratising Forecasting Initiative
21.5.6 Future Agenda for Democratising Forecasting
21.6 Conclusions
References
Part V Problem Structuring and Behavioural OR
22 Behavioural OR: Recent developments and future perspectives
22.1 Introduction
22.2 Recent Developments
22.2.1 Conceptual Framework of BOR
22.2.2 Comparison between BOR and BOM
22.2.3 Empirical Basis of BOR
22.2.4 Behavioural Science and BOR
22.3 Future Developments
22.3.1 BOR and AI
22.3.2 Theoretical and Methodological Resources for BOR
22.3.3 Education Resources for BOR
22.4 Conclusions
References
23 Problem Structuring Methods: Taking Stock and Looking Ahead
23.1 Introduction
23.2 The Characteristics of PSMs
23.2.1 PSM Tools
23.2.2 PSM Process
23.3 The Use of PSMs in Practice
23.3.1 Sample of PSM applications
23.3.2 Evidence of Use and Applications
23.3.2.1 Surveys of PSM use in practice
23.3.2.2 Academic Reviews of PSM Applications
23.4 PSM Products, Mechanisms, Supporting Evidence
23.4.1 Claimed Products and Facilitative Mechanisms
23.4.2 Supporting Empirical Evidence
23.5 The Future of PSMs
23.5.1 Becoming a Competent PSM Practitioner
23.5.2 Becoming a Competent PSM Researcher
23.6 Conclusion
References
24 Are PSMs Relevant in a Digital Age? Towards an Ethical Dimension
24.1 Introduction
24.2 Where Are We Now?
24.2.1 What Is the Nature of the Problem Today?
24.2.2 PSMs Today
24.2.3 So What’s the Issue?
24.3 The Ethical Boundary
24.3.1 Case Vignette: Comparison of Two PSMs’ Remote Applications
24.3.1.1 Analysis of the Case Vignette: Shaping
24.3.1.2 Analysis of the Case Vignette: Design
24.3.1.3 Analysis of the Case Vignette: Comparison
24.4 Conclusions
References
Part VI Recent OR Applications
25 Recent Advances in Big Data Analytics
25.1 Introduction
25.2 Ultrahigh-Dimensional Data Analysis
25.2.1 Feature Screening
25.2.2 Interaction Screening for Regression Models
25.2.3 Interaction Screening for Classification
25.3 Massive Data Analysis
25.3.1 Divide-and-Conquer Methods
25.3.2 Subsampling Methods
25.3.2.1 Nonuniform Subsampling Via Leveraging
25.3.2.2 Information-Based Optimal Subdata Selection
25.3.2.3 Optimal Subsampling
25.4 Summary and Discussion
References
26 OR/MS Models for the Humanitarian-Business Partnership
26.1 Introduction to Humanitarian Logistics
26.2 Humanitarian Supply Chains and Their Challenges
26.3 The Incentives of Partnership During the Disaster Phases
26.4 Literature Review
26.4.1 Relief Procurement
26.5 Relief Warehousing, Transportation, and Distribution
26.6 Gap Analysis of Extant Literature
26.7 A Mathematical Model for Humanitarian-Business Partnership
26.8 Conclusion and Suggestions
References
27 Drones and Delivery Robots: Models and Applications to Last Mile Delivery
27.1 Introduction
27.2 Literature Review
27.2.1 Drones: Last Mile Delivery Applications
27.2.2 Delivery Robots: Last Mile Delivery Applications
27.3 Problem Description
27.3.1 The Estimation of Emissions
27.3.2 Mathematical Formulation
27.3.3 Solution Methodology
27.3.4 Initial Solution Generation
27.3.5 The Adaptive Mechanism for Deciding the Use of Operators
27.3.6 The Proposed Neighborhood Operators
27.3.6.1 Removal Operators
27.3.6.2 Insertion Operators
27.4 Numerical Analyses
27.4.1 Instances and Parameters
27.4.1.1 Benchmark Instances
27.4.1.2 Emissions-Related Parameters
27.4.1.3 Parameters Used in the Algorithm
27.4.2 Computational Results
27.4.3 Sensitivity Analysis
27.4.3.1 Drone Capacity
27.4.3.2 The Speed of Delivery Robot
27.5 Conclusions
References
28 Evaluating the Quality of Radiation Therapy Treatment Plans Using Data Envelopment Analyis
28.1 Introduction
28.2 The DEA Model
28.2.1 Orientation and Returns to Scale
28.3 Feature Selection
28.3.1 Expert Opinions
28.3.2 Principal Component Analysis
28.3.3 Environmental Factors
28.4 Dealing with Uncertainty
28.4.1 Simulation
28.4.2 Uncertain DEA
28.5 Application in Practice
28.5.1 Informing the Treatment Planning Process
28.5.2 Integration in the Treatment Planning Process
References
Index