Modeling and Simulation of Logistics Flows 1

Jean-Michel Réveillac is a consultant-adviser and lecturer for large companies. He currently teaches at the University of Burgundy, and CNAM in France and at IGA in Morocco.

• Foreword xiiiAbout This Book xviiIntroduction xxiiiChapter 1. Operational Research 11.1. A history 11.2. Fields of application, principles and concepts 21.2.1. Identification 21.2.2. Modeling 31.2.3. Solution 51.2.4. Validation 61.2.5. Implementation 61.2.6. Improvement 61.3. Basic models 71.4. The future of OR 7Chapter 2. Elements of Graph Theory 92.1. Graphs and representations 92.2. Undirected graph 102.2.1. Multigraph 102.2.2. Planar and non-planar graph 112.2.3. Connected and unconnected graph 112.2.4. Complete graph 112.2.5. Bipartite graph 122.2.6. Partial graph, subgraph, clique and stable 122.2.7. Degree of a vertex and a graph 132.2.8. Chain and cycle in a graph 132.2.9. Level of connectivity (or beta index) 152.2.10. Eulerian graph 152.2.11. Hamiltonian graph 162.2.12. Planar graph 172.2.13. Isthmus 182.2.14. Tree and forest 192.2.15. Arborescence 202.2.16. Ordered arborescence 212.3. Directed graph or digraph 222.3.1. Path and circuit in a digraph 222.3.2. Absence of circuit in a digraph 232.3.3. Adjacency matrix 242.3.4. Valued graph matrix 242.4. Graphs for logistics 25Chapter 3. Optimal Paths 273.1. Basic concepts 273.2. Dijkstra's algorithm 283.2.1. An example of calculating minimal paths 283.2.2. Interpreting the results of the calculations 303.3. Floyd--Warshall's algorithm 303.3.1. Creating the starting matrices (initialization of the algorithm) 303.3.2. Filling the matrices for the following repetitions 313.3.3. An example of calculating minimal paths 323.3.4. Interpreting the results 343.4. Bellman--Ford's algorithm 353.4.1. Initialization 363.4.2. The next repetitions with relaxation 363.4.3. An example of calculation 373.4.4. Interpreting the results 393.5. Bellman--Ford's algorithm with a negative circuit 403.5.1. Example 403.6. Exercises 433.6.1. Exercise 1: Optimizing journey time 433.6.2. Exercise 2: A directed graph with negative cost side 443.6.3. Exercise 3: Routing data packets 453.6.4. Solutions to exercise 1 453.6.5. Solutions to exercise 2 463.6.6. Solutions to exercise 3 48Chapter 4. Dynamic Programming 514.1. The principles of dynamic programming 514.2. Formulating the problem 524.2.1. Example 1: The pyramid of numbers 524.2.2. Example 2: The Fibonacci sequence 544.2.3. Example 3: The knapsack 564.3. Stochastic process 604.4. Markov chains 604.4.1. Property of Markov chains 614.4.2. Classes and states of a chain 624.4.3. Matrix and graph 634.4.4. Applying Markov chains 644.5. Exercises 664.5.1. Exercise 1: Levenshtein distance 664.5.2. Exercise 2 674.5.3. Exercise 3: Ehrenfest model 674.5.4. Solutions to exercise 1 684.5.5. Solutions to exercise 2 694.5.6. Solutions to exercise 3 70Chapter 5. Scheduling with PERT and MPM 735.1. Fundamental concepts 735.2. Critical path method 745.3. Precedence diagram 745.4. Planning a project with PERT-CPM 775.4.1. A brief history 775.4.2. Methodology 785.5. Example of determining a critical path with PERT 865.5.1. Using the example to create a precedence table 875.5.2. Creating the graph 875.5.3. Numbering of vertices 895.5.4. Determining earliest dates of each of the tasks 895.5.5. Determining the latest dates for each of the tasks 905.5.6. Determining the critical paths 925.6. Slacks 935.6.1. Total slack 945.6.2. Free slack 945.6.3. Certain slack (or independent slack) 945.6.4. Properties 945.7. Example of calculating slacks 955.8. Determining the critical path with the help of a double-entry table 965.8.1. Creating a table using our example 965.8.2 Filling out the table 965.8.3. ES dates 975.8.4. LF dates 995.8.5. Critical path 1005.9. Methodology of planning with MPM 1015.9.1. A brief history 1015.9.2. Formalizing the graph 1025.9.3. Rules of construction 1035.9.4. Earliest and latest dates 1045.9.5. Determining the critical path 1055.10. Example of determining a critical path with MPM 1065.10.1. Creating the graph 1065.10.2. Determining the earliest dates for each task 1075.10.3. Determining the latest dates of each task 1085.10.4. Determining the critical path(s) 1095.10.5. Slacks 1095.11. Probabilistic PERT/CPM/MPM 1115.11.1. Probability of tasks 1125.11.2. Implementation in an example 1135.11.3. Calculating average durations and variance 1145.11.4. Calculating the average duration of the project 1145.11.5. Calculating the probability of finishing the project in a chosen duration 1145.11.6. Calculating the duration of the project for a given probability 1155.12. Gantt diagram 1165.12.1. Creating the diagram 1165.12.2. Example 1175.13. PERT-MPM cost 1195.13.1. Method 1205.13.2. Example 1215.14. Exercises 1255.14.1. Exercise 1 1255.14.2. Exercise 2 1265.14.3. Exercise 3 1265.14.4. Exercise 4 1275.14.5. Solutions to exercise 1 1295.14.6. Solutions to exercise 2 1305.14.7. Solutions to exercise 3 1325.14.8. Solutions to exercise 4 133Chapter 6. Maximum Flow in a Network 1376.1. Maximum flow 1376.2. Ford--Fulkerson algorithm 1386.2.1. Presentation of the algorithm 1396.2.2. Application of an example 1416.3. Minimum cut theorem 1476.3.1. Example of cuts 1486.4. Dinic algorithm 1496.4.1. Presenting the algorithm 1496.4.2. Application in an example 1506.5. Exercises 1546.5.1. Exercise 1: Drinking water supply 1546.5.2. Exercise 2: Maximum flow according to Dinic 1556.5.3. Solutions to exercise 1 1556.5.4. Solutions to exercise 2 158Chapter 7. Trees, Tours and Transport 1637.1. The basic concepts 1637.2. Kruskal's algorithm 1657.2.1. Application to an example 1657.3. Prim's algorithm 1687.3.1. Application to an example 1707.4. Sollin's algorithm 1757.4.1. Application to an example 1767.5. Little's algorithm for solving the TSP 1827.5.1. Application to an example 1847.6. Exercises 1957.6.1. Exercise 1: Computer network 1957.6.2. Exercise 2: Deliveries 1967.6.3. Solutions to exercise 1 1977.6.4. Solutions to exercise 2 200Chapter 8. Linear Programming 2058.1. Basic concepts 2058.1.1. Formulation of a linear program 2068.2. The graphic resolution method 2068.2.1. Identification 2078.2.2. Formalization 2078.2.3. Resolution 2128.3. Simplex method 2158.3.1. Steps 2158.3.2. An example to be addressed 2158.3.3. Formalization 2168.3.4. Change into standard form 2178.3.5. Creation of the table 2188.3.6. Determination of the pivot 2188.3.7. Iterations 2198.3.8. Interpretation 2228.4. Duality 2238.4.1. Dual formulation 2248.4.2. Passage from primal to dual formalization 2248.4.3. Determination of the pivot 2268.4.4. Iterations 2278.4.5. Interpretation 2288.5. Exercises . 2288.5.1. Exercise 1: Video and festival 2288.5.2. Exercise 2: Simplex 2288.5.3. Exercise 3: Primal and dual 2298.5.4. Solutions to exercise 1 2298.5.5. Solutions to exercise 2 2328.5.6. Solutions to exercise 3 234Chapter 9. Modeling Road Traffic 2379.1. A short introduction to road traffic 2379.2. Scale of models and networks 2399.3. Models and types 2399.4. Learning more information about the models 2409.4.1. Microscopic models 2409.4.2. Macroscopic models 2459.4.3. The families of macroscopic models 2509.4.4. The discretization of models 2529.4.5. Mesoscopic models 2539.4.6. Hybrid models 2549.5. Urban modeling 2559.6. Intelligent transportation systems 2569.7. Conclusion 256Chapter 10. Software Programs 25910.1. Software programs for OR and logistics 25910.2. Spreadsheets 26010.2.1. Existing software programs 26210.3. Project managers 26610.3.1. The procedure for creating a project 26810.3.2. The different software programs available on the market 26810.4. Flow simulators 27110.4.1. Generalist software programs 27310.4.2. Pedestrian simulators 28110.4.3. Traffic simulators 28810.4.4. The creation of a simulation process 300Appendices 303Appendix 1: Standard Normal Distribution Table 305Appendix 2: GeoGebra 309Conclusion 319Glossary 323Bibliography 329Index 337