Abstract
We consider a combined time constrained ship routing and inventory managementproblem. A fleet of ships transports a single product between production and consumptionharbours. The transporter has the responsibility for keeping the stock level within its limitsat all actual harbours, and there should be no need to stop the production at any harboursdue to missing transportation possibilities. The number of arrivals to each harbour and thequantities loaded and discharged at each arrival are determined by the continuous productionrates at the harbours, the stock limits and the actual ships visiting the harbours. We use apath flow formulation for this planning problem, and generate paths for each ship includinginformation about the geographical route, the load quantity and start time at each harbourarrival. In addition, we generate paths for each harbour including information about thenumber of arrivals to the harbour, the load quantity and start time at each harbour arrival.We emphasise the formulation of the path generation problems which are subproblems inthe total planning problem. The generated paths appear as columns in a path flow problemwhich corresponds to a master problem. We use a column generation approach to solve thecontinuous problem. The solution is made integer optimal by branch-and-bound. Computationalresults indicate that a path flow formulation and an optimisation based solutionapproach work for real instances of the planning problem.
Similar content being viewed by others
References
G.G. Brown, G.W. Graves and D. Ronen, Scheduling ocean transportation of crude oil, Management Science 33(1987)335 – 346.
M. Christiansen, Inventory and time constrained ship routing – a mathematical programming approach, Ph.D. Thesis, Department of Economics and Technology Management, Norwegian University of Science and Technology, Trondheim, Norway, 1996.
M. Christiansen, Decomposition of a combined inventory and time constrained ship routing problem, Transportation Science, to appear.
M. Christiansen and B. Nygreen, A method for solving ship routing problems with inventory constraints, Annals of Operations Research 81(1998)357 – 378.
N. Christofides, A. Mingozzi and P. Toth, State-space relaxation procedures for the computation of bounds to routing problems, Networks 11(1981)145– 164.
M. Desrochers, J. Desrosiers and M. Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Operations Research 40(1992)342 – 354.
M. Desrochers and F. Soumis, A generalized permanent labelling algorithm for the shortest path problem with time windows, INFOR 26(1988)191 – 211.
M. Desrochers and F. Soumis, A reoptimization algorithm for the shortest path problem with time windows, European Journal of Operational Research 35(1988)242 – 254.
J. Desrosiers, Y. Dumas, M.M. Solomon and F. Soumis, Time constrained routing and scheduling, in: Handbooks in Operations Research and Management Science 8, Network Routing, North-Holland, Amsterdam, 1995, pp. 35 – 139.
M. Dror and M. Ball, Inventory/routing: Reduction from an annual to a short-period problem, Naval Research Logistics 34(1987)891 – 905.
Y. Dumas, J. Desrosiers and F. Soumis, The pickup and delivery problem with time windows, European Journal of Operational Research 54(1991)7 –22.
EDS, SCICONIC User Guide, Version 2.3, Milton Keynes, England, 1993.
A. Federgruen and D. Simchi-Levi, Analysis of vehicle routing and inventory-routing problems, in: Handbooks in Operations Research and Management Science 8, Network Routing, North-Holland, Amsterdam, 1995, pp. 297 – 373.
M.L. Fisher and M.B. Rosenwein, An interactive optimization system for bulk-cargo ship scheduling, Naval Research Logistics 36(1989)27– 42.
I. Ioachim, S. Gélinas, F. Soumis and J. Desrosiers, A dynamic programming algorithm for the shortest path problem with time windows and linear node costs, GERAD and École Polytechnique, Montréal, Canada, H3T1V6, 1996.
A.W.J. Kolen, A.H.G. Rinnooy Kan and H.W.J.M. Trienekens, Vehicle routing with time windows, Operations Research 35(1987)266 – 273.
Rights and permissions
About this article
Cite this article
Christiansen, M., Nygreen, B. Modelling path flows for a combined ship routingand inventory management problem. Annals of Operations Research 82, 391–413 (1998). https://doi.org/10.1023/A:1018979107222
Issue Date:
DOI: https://doi.org/10.1023/A:1018979107222