| dc.description.abstract | Denne masteroppgaven tar for seg ruting av skip, brukt til å betjene et industrielt nettverk av noder som dekker lokasjoner for lakseoppdrett langs norskekysten. Oppdrettslokasjonene betjenes med fôr som produseres ved en sentral fabrikk og fraktes med selveide skip. Målet med oppgaven er å formulere en routingmodell som minimerer operasjonskostnader, mens fôrleveransene er tilstrekkelig for å møte fôrforbruket ved oppdrettslokasjonene til enhver tid. Fiskefôr er en av kostnadsdriverne i oppdrettssektoren og mangel på fôrleveranser kan føre til mindre vekst blant laks, som igjen fører til tapt omsetning. Sikre og forutsigbare leveranser er derfor essensielt for å holde enhetskostnadene nede. Litteraturstudiet viste at det allerede er gjort mye arbeid med anvendelser av Vehicle Routing Problems og Inventory Routing Problems i maritime næringer. Dekomponering og cross-entropy algoritmer er noen av løsningsmetodene som er brukt for Inventory Routing Problemer i litteraturen.
En inventory routing model ble formulert for å inkludere både rutingen og administrasjon av fôrnivåer samtidig. Både en arc-load og en arc-flow modell ble implementer i Gurobi gjennom Matlab, og modellforbedringer ble vurdert. Modellforbedringene inkluderer sub-tour elimination constraints og clique inequalities. I tillegg er Dantzig-Wolfe dekomponering modellert. Invetory Routing problemet er modellert med flere noder for hver oppdrettslokasjon, og problemet blir derfor fort meget komplekst når et økende antall oppdrettslokasjoner inkluderes i problemet. Modellforbedringer er derfor essensielle for å holde tiden det tar å løse problemet nede, og for å generere gode løsninger og nedre grenser. Alle modellforbedringer er testet på eksempelsett, hvor oppdrettslokasjoner er gruppert sammen i grupper med forskjellige antall oppdrettslokasjoner i hver gruppe.
Arc-flow modellen genererte de beste løsningene uavhengig av hvilke modellforbedringer som ble testet. Eliminasjonen av constraints basert på Big M metoden var trolig avgjørende for at arc-flow modellen utkonkurrerte arc-load modellen. Sub-tour elimination constraints og clique inequalities gav betydelig forbedringer i løsningene for arc-load modellen, men hadde mindre effekt når de ble brukt med arc-flow modellen. Med å begrense hvilke skip som kunne besøke hvilke havner ble tidene det tok å løse problemene redusert betydelig. Dette kom på bekostning av økte kostnader, ettersom mindre kostbare rutealternativer ble neglisjert. Mye av de økte kostnadene kunne reverseres ved å tillate større skip å besøke oppdrettslokausjoner med høyt konsum. Testing av modellene ved endret fôrkonsum ble også utført, og viste som forventet at kostnadene økte ved økt konsum. Interessante emner for videre undersøkelse inkuderer straffekostnader ved forsikret levering og modellering av stokastiske prosesser. | |
| dc.description.abstract | This master's thesis addresses routing of ships, used in order to serve an industrial network of nodes covering aquaculture locations along the Norwegian coastline. Aquaculture locations are served with feed from a central factory with self-operated vessels or with externally produced feed by external vessel. The aim of the master's thesis is making a routing model that minimizes operating costs, while ensuring feed deliveries that meet the feed requirements at the fish farms at any given time. Fish feed is one of the main cost drivers in the salmon farming industry. Failure to provide sufficient amount of feed at the right time can impact the growth of the salmon and therefore also reduce revenues. Reliable deliveries are therefore crucial in order to keep unit costs low in the salmon farming industry. The literature study found that substantial work have been done on Vehicle Routing Problem with maritime applications. This includes route generation methods applied in the aquaculture industry for feed deliveries. There are also literature on Inventory Routing Problem with maritime applications. Evolutionary algorithms, cross-entropy methods and decomposition methods are examples of solution methods used to solve IRPs in existing literature.
An Inventory Routing Model is formulated in order to include both inventory management and routing in the planning process. Both arc-load and arc-flow models of the problem are implemented, and further formulation improvements are considered. This includes sub-tour elimination constraints and clique inequalities. In addition a Dantzig-Wolfe decomposition is formulated. Inventory Routing Problems are modelled with multiple nodes at each harbour in order to incorporate the possibility of multiple deliveries at a harbour. Thus, the computational complexity grows rapidly. Model formulations and formulation improvements are therefore essential in order to keep computation times down, and to provide better solutions and bounds. All model formulations are applied on test cases where fish farms are clustered into a varying number of nodes. Model formulations are also applied in order to test consumption scenarios, compatibility scenarios and robustness.
The arc-flow model consistently generated superior solutions and bounds for all test cases, helped by the removal of Big M methods. Both the split and aggregated sub-tour elimination constraints, as well as the clique inequalities, gave significant improvements in solutions and bounds for the arc-load formulation, but had limited effect when coupled with the arc-flow formulation. By limiting compatibility between ships and fish farms, integrality gaps were significantly reduced. However, the solutions found were inferior as arcs of lower cost were neglected. A major part of the cost increases associated with limited compatibility could be avoided by small changes, as allowing large vessels to serve high demand clusters. Consumption scenarios were also tested. As expected, increased consumption lead to increased costs, as external deliveries were needed in order to serve all fish farms. Interesting topic for further research that are not included in this thesis, includes additions of penalty costs for late deliveries and modelling of stochastic behaviour. | |
