Modeling and Simulation of Logistics Flows 1: Theory and Fundamentals

By Jean-Michel Réveillac

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

• Language: English
• Publisher: Wiley
• Release date: Jan 18, 2017
• ISBN: 9781119368526

Book preview

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

List of Illustrations

Introduction

Figure I.1. Antoine de Jomini (source: Wikipedia)

2 Elements of Graph Theory

Figure 2.1. A graph

Figure 2.2. A multigraph – the vertex b has a loop and a and e are connected by two edges

Figure 2.3. A planar graph (left) and a non-planar graph (right)

Figure 2.4. A connected graph (left) and an unconnected graph with two connected components {a, e} and {b, c, d, f} (right)

Figure 2.5. A complete graph

Figure 2.6. A bipartite graph

Figure 2.7. Graph G and its subgraph G′

Figure 2.8. A 4-degree graph (on a, c and f)

Figure 2.9. A graph with eight vertices and 12 edges

Figure 2.10. A Eulerian graph

Figure 2.11. A planar graph

Figure 2.12. A clique K5 and a bipartite graph K3,3

Figure 2.13. A graph where the edge (G, H) is an isthmus

Figure 2.14. A tree (left) and a forest (right)

Figure 2.15. A graph and one of its roots, G

Figure 2.16. An arborescence

Figure 2.17. An arborescence divided into levels and the rows of its vertices

Figure 2.18. The ordered arborescence of the algebraic expression (3x + 2)/4x(x – 4)

Figure 2.19. An arborescence and its two searches

Figure 2.20. Un digraph

Figure 2.21. A digraph without circuit

Figure 2.22. A digraph without circuit with its rows and levels

Figure 2.23. An example of a graph and its adjacency matrix

Figure 2.24. A valued digraph

3 Optimal Paths

Figure 3.1. An example of a road network

Figure 3.2. The road network used for the example

Figure 3.3. The graph of our example with five towns A–F

Figure 3.4. An example of a graph with a negative circuit

Figure 3.5. A graph representing a metro network

Figure 3.6. A graph with a negative cost side

Figure 3.7. The network connecting the two servers

4 Dynamic Programming

Figure 4.1. The methods: dynamic programming (left) and divide and conquer (right)

Figure 4.2. The initial pyramid of numbers to cross

Figure 4.3. The tree of possibilities with the possible calculations (above) and their results (below). The highest totals are indicated in bold. For a color version of this figure, see www.iste.co.uk/reveillac/modeling1.zip

Figure 4.4. The pyramid obtained by retaining only the maximum totals in each line. The numbers in bold are the maximal values in each line. For a color version of this figure, see www.iste.co.uk/reveillac/modeling1.zip

Figure 4.5. Multiplicity of calculations when carrying out the algorithm

Figure 4.6. The transition graph G

Figure 4.7. The digraph corresponding to our example

Figure 4.8. The maze for exercise 2

Figure 4.9. The graph for exercise 2: question 1

Figure 4.10. The graph of the Erhenfest model

5 Scheduling with PERT and MPM

Figure 5.1. A matrix

Figure 5.2. A codified task or activity A, of duration 5, framed by vertices 1 and 2

Figure 5.3. Different assembly of possible tasks in a PERT graph. At the top A is previous to B and B comes after A

Figure 5.4. Two examples of complex dependencies of several tasks

Figure 5.5. The different logistical sequences of overlapping

Figure 5.6. A fictive task X within a graph

Figure 5.7. Rules to respect when constructing a PERT graph

Figure 5.8. Several examples of possible numbering. In the top graph, task E, with a duration of 7 min, can be marked by the pair (2, 6)

Figure 5.9. The different types of calculations from the earliest date in a PERT graph

Figure 5.10. The different types of calculations of the latest date in a PERT graph

Figure 5.11. The graph of our example corresponding to the precedence table. One may note the presence of the fictive task X with duration of 0 min

Figure 5.12. Another possibility of tracing fictive task X

Figure 5.13. The graph with its vertices (steps)

Figure 5.14. PERT graph with the earliest dates calculated and displayed above each vertex

Figure 5.15. PERT graph with the latest dates calculated and displayed below each peak

Figure 5.16. The critical path of our example

Figure 5.17. Earliest start, latest start, earliest finish and latest finish available for a task on the PERT graph

Figure 5.18. Some possible representations of a task and an associated constraint (arch) in an MPM graph

Figure 5.19. Different assembly of possible tasks in an MPM graph

Figure 5.20. The two types of calculation of an earliest date on an MPM graph

Figure 5.21. Two types of calculation of a latest date on an MPM graph

Figure 5.22. MPM graph with its tasks and their durations placed at each step

Figure 5.23. MPM graph of our example with the earliest dates calculated

Figure 5.24. MPM graph for our example with the earliest dates and latest dates calculated

Figure 5.25. Critical tasks (A, D, F, G and I) in the MPM graph of our example

Figure 5.26. Determining the earliest start of the following task on an MPM graph. We can see the specific case of task B that goes toward C and F

Figure 5.27. Determining the latest finishing date on an MPM graph. We can see the specific case of task B that goes toward C, D and E

Figure 5.28. The system of axes of the Gantt diagram for our example

Figure 5.29. Gantt diagram and its tasks

Figure 5.30. The diagram with its margins

Figure 5.31. Arrows showing successive constraints.

Figure 5.32. The project after reducing the duration of task A to 58 min

Figure 5.33. The project after reducing the duration of task G to 20 min

Figure 5.34. The project after reducing the duration of task F to 12 min

Figure 5.35. The project after reducing the duration of task D to 18 min

Figure 5.36. PERT graph

Figure 5.37. PERT diagram

Figure 5.38. The Gantt diagram with its legend, all of the tasks and slacks, as well as the anteriority constraints

Figure 5.39. MPM diagram with its critical tasks (in yellow)

Figure 5.40. PERT graph

6 Maximum Flow in a Network

Figure 6.1. The principle of marking

Figure 6.2. The graph of our example

Figure 6.3. Initialization

Figure 6.4. The graph after marking no. 1 (the dotted lines are the augmenting chain)

Figure 6.5. The graph once the edges of the augmenting chain sADt have been calculated

Figure 6.6. The graph after marking no. 2 (the dotted lines are the augmenting chain)

Figure 6.7. The graph once the edges of the augmenting chain sACt have been calculated

Figure 6.8. The graph after marking no. 3 (the dotted lines are the augmenting chain)

Figure 6.9. The graph once the edges of the augmenting chain sBDt have been calculated

Figure 6.10. The graph after marking no. 4 (the dotted lines are the augmenting chain)

Figure 6.11. The graph once the edges of the augmenting chain sBCt have been calculated

Figure 6.12. The graph after marking no. 5 (the dotted lines are the augmenting chain)

Figure 6.13. The graph once the edges of the augmenting chain sBDACt have been calculated

Figure 6.14. Four cuts defined in the previous example

Figure 6.15. A network for our algorithm

Figure 6.16. Initialization step

Figure 6.17. The graph GL with its four levels

Figure 6.18. Graphs G and Gf at the first passage in loops 1 and 2

Figure 6.19. Graphs G and Gf at the first passage in loop 1 and at the second passage in loop 2

Figure 6.20. Graphs G and Gf at the first passage in loop 1 and at the third passage in loop 2

Figure 6.21. The level graph GL at the second passage in loop 1

Figure 6.22. Graphs G and Gf at the second passage in loop 1 and at the first passage in loop 2

Figure 6.23. The level graph GL. We can see that the sink can no longer be reached

Figure 6.24. The water distribution and supply network for the municipality of Monchâteau

Figure 6.25. The network for exercise 2

Figure 6.26. The completed network

Figure 6.27. The first three steps of the solution

Figure 6.28. The last four steps of the solution

Figure 6.29. The final step of the Ford–Fulkerson algorithm for question 5.4

Figure 6.30. The level graph GL of exercise 2 once the vertices have been reordered

Figure 6.31. Graphs G and the associated residual graphs Gf

Figure 6.32. Graph GL

Figure 6.33. Graphs G and the associated residual graphs Gf

Figure 6.34. Graph GL

Figure 6.35. Graphs G and the associated residual graphs Gf

Figure 6.36. The final graph GL: passage is no longer possible between level 1 and 4

7 Trees, Tours and Transport

Figure 7.1. The graph of our example

Figure 7.2. The graph of step 6. The arcs with dotted lines have already been chosen

Figure 7.3. The graph of step 8

Figure 7.4. Step 1

Figure 7.5. Step 2

Figure 7.6. Step 3

Figure 7.7. Step 4

Figure 7.8. Step 5

Figure 7.9. Step 6

Figure 7.10. Step 7

Figure 7.11. Initialization

Figure 7.12. Step 1

Figure 7.13. Step 2

Figure 7.14. Step 3

Figure 7.15. Step 4

Figure 7.16. Step 5

Figure 7.17. Step 6

Figure 7.18. Step 7

Figure 7.19. Step 8

Figure 7.20. The map used in our example

Figure 7.21. The parent vertex (node) of our search tree

Figure 7.22. Creation of branches and nodes 2 and 3 from parent node 1

Figure 7.23. Child node 3 of the included branch with its cost

Figure 7.24. Child nodes 4 and 5 with their costs

Figure 7.25. Child nodes 6 and 7 with their costs

Figure 7.26. Child nodes 8 and 9 with their costs

Figure 7.27. Child nodes 10 and 11 with their costs

Figure 7.28. The solution to our example: the shortest tour for visiting all of the cities

Figure 7.29. The possible layout of the network with the overall costs of the work (burying and positioning of the fiber, linking, materials, labor, etc.), related, for each of the connections, in thousands of dollars

Figure 7.30. The graph obtained after reorganization

Figure 7.31. The minimum spanning tree providing a solution to exercise 1

Figure 7.32. The global search tree: solution to our exercise

Figure 7.33. Tour B2B5B4B1B3B6B2

8 Linear Programming

Figure 8.1. Plot of the first half-plane defined by the constraint 3q1 + 6q2 ≤ 24. The straight line passes through the pairs of coordinates (0, 4) and (2, 3)

Figure 8.2. Plot of the second half-plane defined by the constraint 3q1 + 3q2 ≤ 15. The straight line passes through the pairs of coordinates (1, 4) and (3, 2)

Figure 8.3. Plot of the third half-plane defined by the constraint 3q1 ≤ 12. The straight line passes through q1 = 4 whatever q2 is

Figure 8.4. Plot of the fourth half-plane defined by the constraint q1 ≥ 0. The straight line passes through q1 = 0 whatever q2 is

Figure 8.5. Plot of the fifth half-plane defined by the constraint q2 ≥ 0. The straight line passes through q2 = 0 whatever q1 is

Figure 8.6. The area of the solutions

Figure 8.7. Straight line 3q1 + 2q2 = 0. The straight line passes through the pairs of coordinates (–2, 2) and (2, –3)

Figure 8.8. The solution showing the optimum obtained for b = 28. The straight line passes through the pairs of coordinates (2, 4) and (4, 1)

Figure 8.9. Symmetry also exists between the two tables of the simplex (primal on the lower left, dual on the upper right)

Figure 8.10. The constraints and the cost function which define all of the solutions represented by the light area of the plot. For a color version of this figure, see www.iste.co.uk/reveillac/modeling1.zip

Figure 8.11. The pairs to be kept as solutions to our exercise. For a color version of this figure, see www.iste.co.uk/reveillac/modeling1.zip

Figure 8.12. The graphic solution. For a color version of this figure, see www.iste.co.uk/reveillac/modeling1.zip

9 Modeling Road Traffic

Figure 9.1. Total change in the sale of cars between 2010 and 2014: 43.3% for China, 33% for Russia, 6.4% for India and 5.6% for Brazil (source: INOVEV – 2015). For a color version of this figure, see www.iste.co.uk/reveillac/modeling1.zip

Figure 9.2. Example of a diagram modeling the trajectory of two vehicles A and B

Figure 9.3. The four possibilities for characterizing of the spatial and temporal parameters of the two vehicles A and B that are following each other

Figure 9.4. Formalization of the variables on a single axis. (xn(t): position of the vehicle n in time t; Ln – 2: length of vehicle n – 2; Δv: interdistance between vehicles n and n – 1

Figure 9.5. A lane change by vehicle n made in order to pass leader n – 1

Figure 9.6. A necessary lane change made by taking a ramp

Figure 9.7. A merger within an intersection with a stop sign

Figure 9.8. An example of a fundamental diagram

Figure 9.9. Diagram showing the concept of flow

Figure 9.10. Diagram showing the concept of concentration

Figure 9.11. Diagram showing the relationships between flow, concentration and speed

Figure 9.12. An example of the shape of