Free PDF Ebooks Files @AcrobatPlanet.Com

Vehicle routing and scheduling has been studied extensively in the context of truck transport and, to a lesser extent, in the context of rail transport. However, relatively little work has been done on ship routing and scheduling even though approximately 90% of the volume and 70% of the value of all goods transported worldwide is carried by sea. In the first chapter, we survey the literature on maritime transport of liquid bulk products with an eye on challenges that lend themselves to solution by operations research methodology. The survey is by no means exhaustive and is intended as an introduction to the subject for researchers new to the field. Only brief synopses of the articles are used to capture the flavor of the type of problems that arise and the models and solution strategies that have been proposed to deal with them. While the paper focuses on routing and scheduling problems, other important problems are also identified.

In the second chapter, we formulate a model for finding a minimum cost routing in a network for a heterogeneous fleet of ships engaged in pickup and delivery of several liquid bulk cargos. The problem is frequently encountered by maritime chemical transport companies, including oil companies serving an archipelago of islands. The products are assumed to require dedicated compartments in the ship. The problem is to decide how much of each product should be carried by each ship from supply ports to demand ports, subject to the inventory level of each product in each port being maintained between certain levels that are set by the production rates, the consumption rates, and the storage capacities of the various products in each port. This important and challenging inventory constrained multi-ship pickup-delivery problem is formulated as a mixed-integer nonlinear program. We show that the model can be reformulated as an equivalent mixed-integer linear program with special structure. Over 100 test problems are randomly generated and solved using CPLEX 7.5. The results of our numerical experiments illuminate where problem structure can be exploited in order to solve larger instances of the model.

The third chapter of this thesis deals with solution algorithms that take advantage of model properties. We show that the mixed-integer linear program can be decomposed into several subproblems by dualizing coupling constraints. We solved this minimization problem by the Lagrangian Relaxation method to get a better lower bound and to measure the quality of solutions obtained from two suggested randomized greedy heuristic methods.

We conducted numerical studies to establish the goodness of our combined Lagrangian Relaxation/Heuristic approach. Test results show an average duality gap of 26.8% and an average optimality gap of 12.5% on small sized problems. More importantly, our solution times are, on average, three orders of magnitude faster than getting a first feasible solution by CPLEX when using the default options of the solver.

CONTENTS
PREFACE
ACKNOWLEDGEMENTS
LIST OF TABLES
LIST OF FIGURES
SUMMARY
CHAPTER I
MARITIME TRANSPORT OF BULK MATERIALS: AN OPERATIONS RESEARCH PERSPECTIVE

1.1 Introduction
1.2 The Maritime Transportation Industry
1.3 Maritime Logistics Problems
1.3.1 Ship Routing
1.3.2 Ship Routing and Scheduling
1.3.3 Inventory Routing
1.3.4 Other Combined and Complex Models

CHAPTER II APPLICATIONS AND MODEL

2.1 Introduction
2.2 Maritime Routing and Scheduling Literature
2.3 Multi-Commodity Bulk Shipping
2.4 Model Formulation
2.4.1 Routing Constraints
2.4.2 Constraints for Loading and Discharging
2.4.3 Constraints for Time Aspects
2.4.4 Constraints for the Inventories
2.4.5 Objective Function

2.5 Linear Reformulation

2.5.1 Linearizing Ship Load Constraints
2.5.2 Linearizing Route and Schedule Compatibility Constraints
2.5.3 Linearizing Stock Level Constraints
2.5.4 Linearizing Stock Level Bounds Constraints

2.6 mixed-integer Linear Programming Formulation

2.6.1 Example
2.6.2 Computing Time

2.7 Concluding Remarks

CHAPTER III SOLUTION STRATEGY

3.1 Introduction
3.1.1 Problem Assumptions
3.1.2 Mathematical Model
3.1.3 Size of the Problem

3.2 Structure of the Problem

3.2.1 Decomposition of the Problem
3.2.2 Structure of Ship Sub-Polyhedra
3.2.3 Structure of Harbor-Sub-Polyhedra

3.3 Solution by Lagrangian Relaxation Method

3.3.1 Lagrangian Relaxation Problem
3.3.2 Dual Ascent Method

3.4 Solution Strategy by Heuristic Method

3.4.1 Harbor-First Heuristic
3.4.2 Ship-First Heuristic

3.5 Computational Results
3.6 Summary and Concluding Remarks

APPENDIX A — NOTE ON CONVEX UNDERESTIMATES OF SUMS OF PRODUCTS OF LINEAR FUNCTIONS
APPENDIX B — GLOSSARY OF NOTATION
APPENDIX C — STRUCTURE OF THE PROBLEM
REFERENCES

Download
PDF Ebook Inventory Constrained Maritime Routing and Scheduling for Multi-Commodity Liquid Bulk