Use of Clusters in a Route Generation Heuristic for Distribution of Fish Feed

Fish farming is an industry in growth which is also expanding its area of operation. Among the biggest cost-contributors are costs associated with the distribution of fish feed. The demand is heavily varied and the system is hard to model because of uncertainties and the complex problem structure. With the help of simplifications and problem reduction techniques, we have created a tool that can be used for minimizing operational costs in a desired system, and also for evaluating fleet-compositions in different demand scenarios. An optimization model was created for the purpose of distributing a single cargo to a large number of customers from a given production location, using a pre-defined fleet. The objective function is based on fuel price, sailing distance, and specific fuel consumption for each ship. The model is based on a two-phased heuristic, that first creates all possible routing alternatives based on information in an input file, and then chooses the best combination of routes for a final solution which satisfy all requirements of the system. To be able to solve the model, a planning horizon must first be established. We categorize our routing problem as an operational decision problem, hence a planning period of around one week is suitable. For this short time period, variables such as demand can be treated as constant, hence the use of a time-continuous model can be used. To lower the calculation time to a practical level for the tool to be used as an operational planning tool, the number of customer nodes is reduced with clustering techniques and compatibility constraints. Three different methods are developed and compared for various dimensions and constraints; a regional clustering method, natural selection of clusters based on location, and a theoretical approach called k-means which are clustering the nodes based on distance between locations. A computational study was performed to determine the best trade-off between cluster size and calculation time. One system configuration was chosen for each clustering method, and the techniques were compared in three different demand scenarios; low, medium, and high. The regional method included 11 zones, the natural method had 23 clusters with full compatibility between customers and ships, while the k-means approach included 30 clusters, but with restrictions of which customer each ship can visit. The regional method ended up being too coarse for consideration, meaning that the clusters became too large to have any effect of being optimized. In most cases, the natural method turned up to be less costly than the k-means approach, showing us that a fleet with full freedom to be optimized may be more beneficial than a fleet with constrained routing-options as are used today. Finally the best clustering approach and system dimensions were used for evaluating Marine Harvest's current fleet composition in the same demand scenarios as before. Four alternative fleet configurations were compared to the original fleet, and one stood out as less costly in two out of the scenarios. This new composition is in accordance with the company's current plan of replacing one of the vessels in the fleet with a larger and faster ship. We see this as a validation that our model can be used for realistic and valuable evaluations, in addition to the main purpose of minimizing the operational costs