Modeling and Simulation of Logistics Flows 1 E-Book

Jean-Michel Reveillac

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 356

Veröffentlichungsjahr: 2017

Beschreibung

Volume 1 presents successively an introduction followed by 10 chapters and a conclusion: * A logistic approach * an overview of operations research * The basics of graph theory * calculating optimal routes * Dynamic programming * planning and scheduling with PERT and MPM * the waves of calculations in a network * spanning trees and touring * linear programming * modeling of road traffic

Leseprobe

Table of Contents

Cover

Title

Copyright

Foreword

About This Book

Introduction

I.1. What is logistics?

I.2. History

I.3. New tools and new technologies

1 Operational Research

1.1. A history

1.2. Fields of application, principles and concepts

1.3. Basic models

1.4. The future of OR

2 Elements of Graph Theory

2.1. Graphs and representations

2.2. Undirected graph

2.3. Directed graph or digraph

2.4. Graphs for logistics

3 Optimal Paths

3.1. Basic concepts

3.2. Dijkstra’s algorithm

3.3. Floyd–Warshall’s algorithm

3.4. Bellman–Ford’s algorithm

3.5. Bellman–Ford’s algorithm with a negative circuit

3.6. Exercises

4 Dynamic Programming

4.1. The principles of dynamic programming

4.2. Formulating the problem

4.3. Stochastic process

4.4. Markov chains

4.5. Exercises

5 Scheduling with PERT and MPM

5.1. Fundamental concepts

5.2. Critical path method

5.3. Precedence diagram

5.4. Planning a project with PERT-CPM

5.5. Example of determining a critical path with PERT

5.6. Slacks

5.7. Example of calculating slacks

5.8. Determining the critical path with the help of a double-entry table

5.9. Methodology of planning with MPM

5.10. Example of determining a critical path with MPM

5.11. Probabilistic PERT/CPM/MPM

5.12. Gantt diagram

5.13. PERT-MPM cost

5.14. Exercises

6 Maximum Flow in a Network

6.1. Maximum flow

6.2. Ford–Fulkerson algorithm

6.3. Minimum cut theorem

6.4. Dinic3 algorithm

6.5. Exercises

7 Trees, Tours and Transport

7.1. The basic concepts

7.2. Kruskal’s algorithm

7.3. Prim’s algorithm

7.4. Sollin’s algorithm

7.5. Little’s algorithm for solving the TSP

7.6. Exercises

8 Linear Programming

8.1. Basic concepts

8.2. The graphic resolution method

8.3. Simplex method

8.4. Duality

8.5. Exercises

9 Modeling Road Traffic

9.1. A short introduction to road traffic

9.2. Scale of models and networks

9.3. Models and types

9.4. Learning more information about the models

9.5. Urban modeling

9.6. Intelligent transportation systems

9.7. Conclusion

10 Software Programs

10.1. Software programs for OR and logistics

10.2. Spreadsheets

10.3. Project managers

10.4. Flow simulators

Appendices

Appendix 1: Standard Normal Distribution Table

A1.1. Use

Appendix 2: GeoGebra

A2.1. Presentation of the software

A2.2. Using GeoGebra

Conclusion

Glossary

Bibliography

Index

End User License Agreement

List of Tables

3 Optimal Paths

Table 3.1.

Repetitions of the algorithm

Table 3.2.

Initialization

Table 3.3.

Repetition no. 1

Table 3.4.

Repetition no. 2

Table 3.5.

Repetition no. 3

Table 3.6.

Repetition no. 4

Table 3.7.

Repetition no. 5

Table 3.8.

Initialization of the vertices

Table 3.9.

Initialization of the vertices in the example

Table 3.10.

Table of relaxation for repetition no. 1

Table 3.11.

Table of the vertices for repetition no. 1

Table 3.12.

Table of relaxation for repetition no. 2

Table 3.13.

Table of the vertices for repetition no. 2

Table 3.14.

Table of relaxation for repetition no. 3

Table 3.15.

Table of the vertices for repetition no. 3

Table 3.16.

Table of vertices at initialization

Table 3.17.

Table of relaxation for repetition no. 1

Table 3.18.

Table of the vertices for repetition no. 1

Table 3.19.

Table of relaxation for repetition no. 2

Table 3.20.

Table of the vertices for repetition no. 2

Table 3.21.

Table of relaxation for repetition no. 3

Table 3.22.

Table of vertices for repetition no. 3

Table 3.23.

Table of relaxation for repetition no. 4

Table 3.24.

Table of vertices for repetition no. 4

Table 3.25.

The repetitions of the algorithm

Table 3.26.

Initialization

Table 3.27.

Repetition no. 1

Table 3.28.

Repetition no. 2

Table 3.29.

Repetition no. 3

Table 3.30.

Repetition no. 4

Table 3.31.

Initialization

Table 3.32.

Table of relaxation for repetition no. 1

Table 3.33.

Table of the vertices for repetition no. 1

Table 3.34.

Table of relaxation for repetition no. 2

Table 3.35.

Table of the vertices for repetition no. 2

4 Dynamic Programming

Table 4.1.

Objects, values and weight

Table 4.2.

The table obtained from phase 1 of the algorithm

Table 4.3.

Phase 2b

Table 4.4.

Phase 2b, objects and the knapsack

Table 4.5.

Monthly figures for the hire company

5 Scheduling with PERT and MPM

Table 5.1.

Predecessors

Table 5.2.

Predecessors–successors

Table 5.3.

Tasks and predecessors for a sound system

Table 5.4.

Earliest starts and latest finishes

Table 5.5.

Calculating slacks

Table 5.6.

Double-entry matrix, empty, for our example

Table 5.7.

Double-entry matrix, filled with the duration of tasks

Table 5.8.

Double-entry matrix. The earliest dates are present

Table 5.9.

Double-entry matrix. The earliest and latest dates are present

Table 5.10.

The double-entry matrix and determining the critical path

Table 5.11.

Example of section 5.5.1 with new durations

Table 5.12.

Average durations and variances

Table 5.13.

All of the data necessary for a Gantt diagram

Table 5.14.

Durations, costs and accelerated costs

Table 5.15.

Marginal costs

Table 5.16.

Summary of costs

Table 5.17.

Table of predecessors

Table 5.18.

Durations and predecessors

Table 5.19.

The precedences for exercise 4

Table 5.20.

Costs and durations for exercise 4

Table 5.21.

Total slacks and free slacks

Table 5.22.

Precedence table

Table 5.23.

Double-entry matrix with the earliest and latest dates

Table 5.24.

Total slacks and free slacks

Table 5.25.

Calculating average durations and variances for critical tasks

Table 5.26.

Calculation of normal cost

Table 5.27.

Calculation of accelerated and marginal costs

Table 5.28.

Calculation of optimized cost

7 Trees, Tours and Transport

Table 7.1.

The symmetric matrix

Table 7.2.

Search for the minimums in each row

Table 7.3.

Reduction of the matrix according to the minimums in each row and search for the minimums in each column

Table 7.4.

Reduction of the matrix according to the minimums in each column

Table 7.5.

Calculation of regret

Table 7.6.

The new matrix

Table 7.7.

Removal of loop BN (subtours)

Table 7.8.

Search for the minimums in each row

Table 7.9.

Reduction of the matrix according to the minimums in each row and search for the minimums in each column

Table 7.10.

Calculation of regret

Table 7.11.

New matrix with removal of subtour BP and reduction

Table 7.12.

Calculation of regret

Table 7.13.

New matrix with removal of the subtours LM and reduction

Table 7.14.

Calculation of regret

Table 7.15.

New matrix and reduction

Table 7.16.

Calculation of regret

Table 7.17.

Distances between the shops given in meters

Table 7.18.

Reduction no. 1

Table 7.19.

Calculation of regrets no. 1

Table 7.20.

Reduction no. 2

Table 7.21.

Calculation of regrets no. 2

Table 7.22.

Reduction no. 3

Table 7.23.

Calculation of regrets no. 3

Table 7.24.

Reduction no. 4 of the matrix for calculating branches B3B1 excluded and B3B1 included

Table 7.25.

Calculation of regrets no. 4

Table 7.26.

Reduction no. 5

Table 7.27.

Calculation of regrets no. 5

Table 7.28.

The final matrix: we can add B5B4 and B6B2 without increasing cost

8 Linear Programming

Table 8.1.

All of the data in the example

Table 8.2.

All of the data of the example being addressed

Table 8.3.

The simplex table

Table 8.4.

Determination of the pivot

Table 8.5.

Entering and leaving base

Table 8.6.

Calculation of row e1

Table 8.7.

Calculation of row e2

Table 8.8.

Calculation of row e3

Table 8.9.

Calculation of row z

Table 8.10.

The new table at iteration no. 1

Table 8.11.

Determination of the new pivot

Table 8.12.

The new table at iteration no. 2

Table 8.13.

From the primal to the dual

Table 8.14.

Cost coefficients of the primal

Table 8.15.

Dual simplex table

Table 8.16.

Determination of the pivot

Table 8.17.

The simplex at iteration no. 1

Table 8.18.

The simplex at iteration no. 2

Table 8.19.

The solution using the simplex

Table 8.20.

The succession of iterations for calculating the simplex of the PL primal

Table 8.21.

The succession of iterations for calculating the simplex of the PL dual

9 Modeling Road Traffic

Table 9.1.

Transportation models and goals to be met (source: [COS 13])

Appendix 1: Standard Normal Distribution Table

Table A1.1.

Standard normal distribution

Guide

Cover

Table of Contents

Begin Reading

Pages

C1

iii

iv

v

xiii

xiv

xv

xvii

xviii

xix

xx

xxi

xxiii

xxiv

xxv

xxvi

xxvii

xxviii

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

303

305

306

307

309

310

311

312

313

314

315

316

317

319

320

321

323

324

325

326

327

329

330

331

332

333

334

335

336

337

338

339

340

341

342

G1

G2

G3

G4

G5

G6

G7

G8

Series Editor

Jean-Paul Bourrières

Modeling and Simulation of Logistics Flows 1

Theory and Fundamentals

Jean-Michel Réveillac

First published 2017 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

www.iste.co.uk

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.wiley.com

© ISTE Ltd 2017

The rights of Jean-Michel Réveillac to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2016957972

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-78630-106-2

Foreword

In a society in which the fundamental role of transport only fully appears when it does not work or works badly, logistics does not tend to be seen negatively. This is not due to the fact that the average citizen possesses knowledge of the processes behind it, the requirements and the missions of such a phenomenon, but because very often logistics seem almost foreign, merely associated with transportation and the mobility of goods. A social representation of logistics would not only require one to envisage the geographical division of work but also consider the infinite consequences that come from a mass consumption system, an absolute social phenomenon described by E. Durkheim1.

The term logistics covers three crucial dimensions regarding the flow of goods, which every business that produces such commodities will encounter: supply, flow within the business – one thus speaks of production management – and distribution. Every movement of people or goods, whether the destination be near or far, will demand space, time and energy. Logistics, perceived as a general discipline in the realm of flow management, is somewhat strange in that its effectiveness is inversely proportional to its visibility. The better the performance, the less visible it becomes and many economic powers, both local and global, will only realize their main concerns when, for many reasons, they are unable to find answers to the complex problems that they set out to solve.

“Thoughts arise from action in order to return to action”2, H. Wallon once affirmed. If there is one world in which this quotation proves productive, it is in that of logistics. Logistics is to transportation and mobility what thoughts are to action. As demonstrated in the few historical pages of the work that you are currently reading, though for centuries soldiers have created flows that enable their armed forces to move systematically, it was not until the second half of the last century, during which the concept of mobility was made commonplace in Western societies along with the emergence of global labor division and a globalized society of mass consumption, that the rationalized organization of flow became a crucial discipline for the productivity of firms. Assimilated in chart of accounts as an expenditure account, despite everything logistics is still very often associated with loss for businesses that produce goods. It is about time that it is seen as an asset.

Logistics has established itself using empirical knowledge that is modeled so as to offer us tools that rationalize modes of mobility, and each concept or logistical model is immediately confronted with reality in terms of effectiveness: modify the packaging of your product and the characteristics of transportation are immediately modified. Change the providers and you change the chain of supply and the storage techniques. Create a new product and it is your chain of production that must then be remodeled.

We could, for example, be faced with the task of delivering four parcels in two different locations. Easy! But we could also be faced with the task of organizing the rounds of 140 drivers (some employed by our business, others temporarily contracted and even more subcontracted), each with a vehicle that contains over 10 tons of goods spread throughout more than 250 parcels to be delivered to 50 different locations. Some of these delivery locations can belong to the same client and be several dozens or hundreds of kilometers away. Here, we are faced with a jigsaw puzzle that consists of over a million possibilities. Rational types would opt to travel in a straight line, losing time, space and money. It is better to maintain to a Pascalien vision of modelized management of uncertainties. Yet the creation of a systemic and complex vision of flow reality and its crucial concrete effectiveness demands one to abandon one’s common sense.

Until the oil crisis of the 1970s, needs for the future always exceeded those of the past. Consequently, there was little concern about vehicle fill rate, the pollution caused or the global cost of stocks as long as the “trip” was profitable.

At the start of the 21st Century, conditions changed. In the international framework of sustainable mobility, for reasons regarding productivity, traceability, quality, etc., it is no longer possible to ignore the optimization of flux or to misunderstand logistics. The knowledge acquired by logistics coordinators must be shared, spread and popularized, such that mobility is perceived as one of the fundamental concepts in sustainable development and an inevitable dimension of profitability of productive actions. A product can only be regarded as complete insofar as it is available to anyone who needs it: logistics, which enables this access, is an integral and inescapable part of industry.

Every exchange of goods requires information to be transferred between those concerned. Today, manufacturers must find the best balance between geo-space, concerning land, and cyberspace, concerning the virtual land of exchanging data.

Logistics are everywhere, all the time. Of course, all is not logistic, but logistics can be perceived in everything. Yet today, knowledge of logistics is only shared between specialists. The aim of this book is to make sense of the issue to explain modelizations coming from knowledge accumulated by logistics coordinators in order to find realistic applications. This book, dotted with numerous graphs and images, is not only a collection of techniques that help produce decisions. The intentión is to spread this knowledge onto a public that is much greater in number than the experts. My friend J.-M. Reveillac has purposefully limited vast mathematical demonstrations in order to make the modelizations of flux management understandable while adding value to operational research.

Undertaking logistics involves finding the best balance between all the coercive systems, which circulate around mobility in order to transform it into something that is accessible. And this must no longer be made up, as in business it is humans themselves who will ultimately decide the actions of other humans.

Pascal MAUNYHead of IUT at Chalon sur SaôneUniversity of Bourgogne

1

Emile Durkheim (1858–1917), French, Philosophy specialist, considered the founder of modern sociology.

2

Henri Wallon (1879–1962), French, philosopher, psychologist and politician, author of “De l’acte à la pensée”, 1942.

About This Book

There are already several works about logistics, operational research, decision support, the theory of graphs, dynamic programming, etc., but few of them gather all of these domains together by proposing an overall vision that focuses less on pure and hard mathematical aspects, without totally ignoring them, while offering numerous practical exercises.

This book is one of three volumes. This first volume tackles theoretical aspects with corrected exercises for each chapter, finishing with a presentation of the principal software systems dedicated to operational research (OR) and logistical simulation. The second and third volumes are dedicated to practice and specialized applications of software programs.

Most of the studies proposed here are able to be completed using a simple calculator, a sheet of paper and a pen or even with the help of a spreadsheet on Microsoft Excel, Apache OpenCalc, Apple Numbers, etc.

The presented techniques and their uses are multiple, yet I am sure that a student, a software programmer, a developer, a technician, an engineer, an IT specialist, a decision-maker and you, the reader, will find practical applications that were unexpected in your professional or even personal life.

Intended public

This work is designed for all those who encounter logistical problems linked to flux management, decision support, optimization of journeys or rounds, research for an aim when confronted with multiple constraints, creation of dashboards, relevant simulations, etc.

The works presented require a minimum level of mathematical knowledge, and a post A level student in science or economics will not encounter major difficulties. I tried to maintain simplicity and go straight toward the objective in the theoretical approach without going into great demonstrations, which to me do not seem necessary.

In terms of the practical exercises, on a laptop, tackled in Volumes 2 and 3, a good knowledge of the exploitation system (track, records and lists, files, names, extensions, sheet, movement, etc.) will prove essential.

Since a few works use a spreadsheet, it is thus necessary to master the basic functionalities of this type of software program. It will also be convenient to know the primary use of pivot table data manipulation tools.

If we know about visual basic application (VBA) language or its equivalent, we can easily understand, improve, enrich and create new solutions to certain problems.

Lastly, if we understand the basic systems for managing data and relational algebra, then we will be at ease in every domain explored.

Organization and contents of the book

This work is composed of three volumes:

– Volume 1: Theory and fundamentals;

– Volume 2: Dashboards, traffic planning and management;

– Volume 3: Discrete and continuous flows in 2D/3D.

Volume 1 presents an introduction followed by 10 chapters and a conclusion:

– approach for logistics;

– an overall view of operational research;

– basics of the theory of graphs;

– calculation of optimal routes;

– dynamic programming;