A two-echelon routing problem in forest-industry logistics with a nonlinear cost function: A modified ant colony algorithm on a transport graph with transit vertices

Abstract

This paper studies the problem of planning forest-product transportation from a single shipping point through a network of intermediate transfer hubs to final consumers over a real road network. A key feature of the formulation is that the unit cost per kilometer depends nonlinearly on vehicle load: partially loaded trucks cost the industry more per unit of goods delivered. The aim of the study is to propose a mathematical model of this two-level logistics problem and an algorithm to solve it that is suitable for transportation networks of realistic size. A modified version of the ant colony optimization algorithm – a bio-inspired optimization method – has been developed; it jointly optimizes the routes of both delivery levels. The proposed algorithm is compared with three reference approaches: an exact method based on mixed integer linear programming, its lower bound, and a simple nearest-neighbor greedy heuristic. Experiments were carried out on a training scenario with fifty consumers and on the real road network of the Primorsky Krai region of Russia, containing 203 nodes. The proposed algorithm outperformed the greedy heuristic in 49 out of 50 runs with an average improvement of about 7.7%, and outperformed the exact method in 76 out of 80 cases. On the real road network the improvement over the greedy heuristic was about 7%, and the algorithm results were stable: the spread between runs did not exceed 1%. The practical value of the work is the applicability of the model and algorithm to transportation planning in the forest-industry sector and in other sectors with extensive delivery networks.