The Fish Feed Production Routing Problem

This paper introduces the fish feed production routing problem (FFPRP) faced by Norwegian salmon feed producers. The FFPRP is comprised of a production scheduling problem and a rich vehicle routing problem (VRP) and thus denotes a variant of the integrated production scheduling and vehicle routing problem. We present a discrete time mixed integer programming (MIP) model of the FFPRP. Specifically, the model incorporates a multi-product, mull-trip, and mull-depot setting, where orders are produced at production lines at factories, and delivered within their respective time windows to customers by a heterogeneous fleet of vessels. The main objective is to minimize total costs, including production costs, routing costs, and costs of not delivering orders. We propose a heuristic, combining decomposition and the adaptive large neighborhood search (ALNS) heuristic, to solve the FFPRP. The decomposition-based ALNS heuristic is tested on a number of test instances which are generated based on vessel, factory, and order data from two of Norway's largest fish feed producers. For small problem instances, for which the commercial MIP solver often is able to prove optimality, the average optimality gaps of the proposed heuristic are relatively small, while for the larger problem instances, the heuristic significantly outperforms the commercial MIP solver both in terms of solution quality and run time.

Automated summary

This paper introduces the fish feed production routing problem (FFPRP) faced by Norwegian salmon feed producers and proposes a discrete time mixed integer programming (MIP) model and a heuristic algorithm combining decomposition and adaptive large neighborhood search (ALNS) to solve the problem. Experimental results show that the proposed heuristic algorithm outperforms the commercial MIP solver in terms of solution quality and run time for larger problem instances.