In today’s world, the links between suppliers and customers are neither simple nor direct due to the expanded infrastructure of real supply chains, such as bulk port supply chains. In the latter, delivering the right product in good quality, to the right customer, in the right place, and at the right time by choosing the best belt-conveyor transportation routes among a complex real-world routes network is more and more challenging, making thereby the bulk port routing problem a strongly demanded optimization issue to solve. To solve the routing problem, we proposed, in a former work, a mixed integer linear program whose findings were interesting, but some means should be proposed to address difficult instances. Some closely related problems also failed to solve large instances with exact methods. In this paper, we propose a suitable solution encoding and develop a heuristic solution to handle large scale data sets. The heuristic can help the port planner to test different scenarios and provide better routing plan. The proposed method can be further refined and improved by employing a local search metaheuristic.