VT Paschos
John Wiley & Sons
0e druk, 2010
9781848211490
Applications of Combinatorial Optimization V 3
Specificaties
Gebonden, 408 blz.
|
Engels
John Wiley & Sons |
0e druk, 2010
ISBN13: 9781848211490
Rubricering
Onderdeel van serie
ISTE
Levertijd ongeveer 8 werkdagen
Samenvatting
Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management.
The three volumes of the Combinatorial Optimization series aims to cover a wide range of topics in this area. These topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization.
Applications of Combinatorial Optimization is presenting a certain number among the most common and well–known applications of Combinatorial Optimization.
Specificaties
ISBN13:9781848211490
Taal:Engels
Bindwijze:gebonden
Aantal pagina's:408
Uitgever:John Wiley & Sons
Druk:0
Serie:ISTE
Inhoudsopgave
<p>Preface xiii</p>
<p>Chapter 1. Airline Crew Pairing Optimization 1<br /> Laurent ALFANDARI and Anass NAGIH</p>
<p>1.1. Introduction 1</p>
<p>1.2. Definition of the problem 2</p>
<p>1.3. Solution approaches 7</p>
<p>1.4. Solving the subproblem for column generation 11</p>
<p>1.5. Conclusion 21</p>
<p>1.6. Bibliography 22</p>
<p>Chapter 2. The Task Allocation Problem 23<br /> Moaiz BEN DHAOU and Didier FAYARD</p>
<p>2.1. Presentation 24</p>
<p>2.2. Definitions and modeling 24</p>
<p>2.3. Review of the main works 29</p>
<p>2.4. A little–studied model 38</p>
<p>2.5. Conclusion 43</p>
<p>2.6. Bibliography 43</p>
<p>Chapter 3. A Comparison of Some Valid Inequality Generation Methods for General 0 1 Problems 49<br /> Pierre BONAMI and Michel MINOUX</p>
<p>3.1. Introduction 49</p>
<p>3.2. Presentation of the various techniques tested 53</p>
<p>3.3. Computational results 67</p>
<p>3.4. Bibliography 70</p>
<p>Chapter 4. Production Planning 73<br /> Nadia BRAUNER, Gerd FINKE and Maurice QUEYRANNE</p>
<p>4.1. Introduction 73</p>
<p>4.2. Hierarchical planning 74</p>
<p>4.3. Strategic planning and productive system design 75</p>
<p>4.4. Tactical planning and inventory management 77</p>
<p>4.5. Operations planning and scheduling 90</p>
<p>4.6. Conclusion and perspectives 104</p>
<p>4.7. Bibliography 105</p>
<p>Chapter 5. Operations Research and Goods Transportation 111<br /> Teodor Gabriel CRAINIC and Frédéric SEMET</p>
<p>5.1. Introduction 111</p>
<p>5.2. Goods transport systems 113</p>
<p>5.3. Systems design 115</p>
<p>5.4. Long–distance transport 122</p>
<p>5.5. Vehicle routing problems 137</p>
<p>5.6. Exact models and methods for the VRP 139</p>
<p>5.7. Heuristic methods for the VRP 147</p>
<p>5.8. Conclusion 160</p>
<p>5.9. Appendix: metaheuristics 161</p>
<p>5.10. Bibliography 164</p>
<p>Chapter 6. Optimization Models for Transportation Systems Planning 177<br /> Teodor Gabriel CRAINIC and Michael FLORIAN</p>
<p>6.1. Introduction 177</p>
<p>6.2. Spatial interaction models 178</p>
<p>6.3. Traffic assignment models and methods 181</p>
<p>6.4. Transit route choice models 193</p>
<p>6.5. Strategic planning of multimodal systems 197</p>
<p>6.6. Conclusion 204</p>
<p>6.7. Bibliography 204</p>
<p>Chapter 7. A Model for the Design of a Minimum–cost Telecommunications Network 209<br /> Marc DEMANGE, Cécile MURAT, Vangelis Th. PASCHOS and Sophie TOULOUSE</p>
<p>7.1. Introduction 209</p>
<p>7.2. Minimum cost network construction 210</p>
<p>7.3. Mathematical model, general context 213</p>
<p>7.4. Proposed algorithm 216</p>
<p>7.5. Critical points 220</p>
<p>7.6. Conclusion 223</p>
<p>7.7. Bibliography 223</p>
<p>Chapter 8. Parallel Combinatorial Optimization 225<br /> Van–Dat CUNG, Bertrand LE CUN and Catherine ROUCAIROL</p>
<p>8.1. Impact of parallelism in combinatorial optimization 225</p>
<p>8.2. Parallel metaheuristics 226</p>
<p>8.3. Parallelizing tree exploration in exact methods 235</p>
<p>8.4. Conclusion 247</p>
<p>8.5. Bibliography 248</p>
<p>Chapter 9. Network Design Problems: Fundamental Methods 253<br /> Alain Quilliot</p>
<p>9.1. Introduction 253</p>
<p>9.2. The main mathematical and algorithmic tools for network design 258</p>
<p>9.3. Models and problems 275</p>
<p>9.4. The STEINER–EXTENDED problem 280</p>
<p>9.5. Conclusion 281</p>
<p>9.6 Bibliography 281</p>
<p>Chapter 10. Network Design Problems: Models and Applications 291<br /> Alain Quilliot</p>
<p>10.1. Introduction 291</p>
<p>10.2. Models and location problems 293</p>
<p>10.3. Routing models for telecommunications 298</p>
<p>10.4. The design or dimensioning problem in telecommunications 301</p>
<p>10.5. Coupled flows and multiflows for transport and production 306</p>
<p>10.6. A mixed network pricing model 314</p>
<p>10.7. Conclusion 319</p>
<p>10.8. Bibliography 319</p>
<p>Chapter 11. Multicriteria Task Allocation to Heterogenous Processors with Capacity and Mutual Exclusion Constraints 327<br /> Bernard ROY and Roman SLOWINSKI</p>
<p>11.1. Introduction and formulation of the problem 328</p>
<p>11.2. Modeling the set of feasible assignments 331</p>
<p>11.3. The concept of a blocking configuration and analysis of the unblocking means 334</p>
<p>11.4. The multicriteria assignment problem 346</p>
<p>11.5. Exploring a set of feasible non–dominated assignments in the plane g2 × g3 348</p>
<p>11.6. Numerical example 357</p>
<p>11.7. Conclusion 363</p>
<p>11.8. Bibliography 364</p>
<p>List of Authors 365</p>
<p>Index 369</p>
<p>Summary of Other Volumes in the Series 373</p>
<p>Chapter 1. Airline Crew Pairing Optimization 1<br /> Laurent ALFANDARI and Anass NAGIH</p>
<p>1.1. Introduction 1</p>
<p>1.2. Definition of the problem 2</p>
<p>1.3. Solution approaches 7</p>
<p>1.4. Solving the subproblem for column generation 11</p>
<p>1.5. Conclusion 21</p>
<p>1.6. Bibliography 22</p>
<p>Chapter 2. The Task Allocation Problem 23<br /> Moaiz BEN DHAOU and Didier FAYARD</p>
<p>2.1. Presentation 24</p>
<p>2.2. Definitions and modeling 24</p>
<p>2.3. Review of the main works 29</p>
<p>2.4. A little–studied model 38</p>
<p>2.5. Conclusion 43</p>
<p>2.6. Bibliography 43</p>
<p>Chapter 3. A Comparison of Some Valid Inequality Generation Methods for General 0 1 Problems 49<br /> Pierre BONAMI and Michel MINOUX</p>
<p>3.1. Introduction 49</p>
<p>3.2. Presentation of the various techniques tested 53</p>
<p>3.3. Computational results 67</p>
<p>3.4. Bibliography 70</p>
<p>Chapter 4. Production Planning 73<br /> Nadia BRAUNER, Gerd FINKE and Maurice QUEYRANNE</p>
<p>4.1. Introduction 73</p>
<p>4.2. Hierarchical planning 74</p>
<p>4.3. Strategic planning and productive system design 75</p>
<p>4.4. Tactical planning and inventory management 77</p>
<p>4.5. Operations planning and scheduling 90</p>
<p>4.6. Conclusion and perspectives 104</p>
<p>4.7. Bibliography 105</p>
<p>Chapter 5. Operations Research and Goods Transportation 111<br /> Teodor Gabriel CRAINIC and Frédéric SEMET</p>
<p>5.1. Introduction 111</p>
<p>5.2. Goods transport systems 113</p>
<p>5.3. Systems design 115</p>
<p>5.4. Long–distance transport 122</p>
<p>5.5. Vehicle routing problems 137</p>
<p>5.6. Exact models and methods for the VRP 139</p>
<p>5.7. Heuristic methods for the VRP 147</p>
<p>5.8. Conclusion 160</p>
<p>5.9. Appendix: metaheuristics 161</p>
<p>5.10. Bibliography 164</p>
<p>Chapter 6. Optimization Models for Transportation Systems Planning 177<br /> Teodor Gabriel CRAINIC and Michael FLORIAN</p>
<p>6.1. Introduction 177</p>
<p>6.2. Spatial interaction models 178</p>
<p>6.3. Traffic assignment models and methods 181</p>
<p>6.4. Transit route choice models 193</p>
<p>6.5. Strategic planning of multimodal systems 197</p>
<p>6.6. Conclusion 204</p>
<p>6.7. Bibliography 204</p>
<p>Chapter 7. A Model for the Design of a Minimum–cost Telecommunications Network 209<br /> Marc DEMANGE, Cécile MURAT, Vangelis Th. PASCHOS and Sophie TOULOUSE</p>
<p>7.1. Introduction 209</p>
<p>7.2. Minimum cost network construction 210</p>
<p>7.3. Mathematical model, general context 213</p>
<p>7.4. Proposed algorithm 216</p>
<p>7.5. Critical points 220</p>
<p>7.6. Conclusion 223</p>
<p>7.7. Bibliography 223</p>
<p>Chapter 8. Parallel Combinatorial Optimization 225<br /> Van–Dat CUNG, Bertrand LE CUN and Catherine ROUCAIROL</p>
<p>8.1. Impact of parallelism in combinatorial optimization 225</p>
<p>8.2. Parallel metaheuristics 226</p>
<p>8.3. Parallelizing tree exploration in exact methods 235</p>
<p>8.4. Conclusion 247</p>
<p>8.5. Bibliography 248</p>
<p>Chapter 9. Network Design Problems: Fundamental Methods 253<br /> Alain Quilliot</p>
<p>9.1. Introduction 253</p>
<p>9.2. The main mathematical and algorithmic tools for network design 258</p>
<p>9.3. Models and problems 275</p>
<p>9.4. The STEINER–EXTENDED problem 280</p>
<p>9.5. Conclusion 281</p>
<p>9.6 Bibliography 281</p>
<p>Chapter 10. Network Design Problems: Models and Applications 291<br /> Alain Quilliot</p>
<p>10.1. Introduction 291</p>
<p>10.2. Models and location problems 293</p>
<p>10.3. Routing models for telecommunications 298</p>
<p>10.4. The design or dimensioning problem in telecommunications 301</p>
<p>10.5. Coupled flows and multiflows for transport and production 306</p>
<p>10.6. A mixed network pricing model 314</p>
<p>10.7. Conclusion 319</p>
<p>10.8. Bibliography 319</p>
<p>Chapter 11. Multicriteria Task Allocation to Heterogenous Processors with Capacity and Mutual Exclusion Constraints 327<br /> Bernard ROY and Roman SLOWINSKI</p>
<p>11.1. Introduction and formulation of the problem 328</p>
<p>11.2. Modeling the set of feasible assignments 331</p>
<p>11.3. The concept of a blocking configuration and analysis of the unblocking means 334</p>
<p>11.4. The multicriteria assignment problem 346</p>
<p>11.5. Exploring a set of feasible non–dominated assignments in the plane g2 × g3 348</p>
<p>11.6. Numerical example 357</p>
<p>11.7. Conclusion 363</p>
<p>11.8. Bibliography 364</p>
<p>List of Authors 365</p>
<p>Index 369</p>
<p>Summary of Other Volumes in the Series 373</p>