Combinatorial formulation guided local search for inland waterway routing and scheduling

Abstract

We investigate the optimization of inland transport routes of barge container ships with the objective to maximize the profit of a shipping company. This problem consists of determining the upstream and downstream calling sequence and the number of loaded and empty containers transported between any two ports. We present Combinatorial as well as Mixed Integer Linear Programming (MILP) formulation for this problem. We propose to combine these two approaches with an aim to generate efficient heuristic to solve considered problem. The proposed mixed-formulation Local Search (MIX-LS) represents good basis for implementation of LS-based meta-heuristic methods and we presented Multi-start Local Search (MLS) within this framework. To compare the proposed approach with the state-of-the-art Mixed Integer Programming (MIP) based heuristics we run all methods within a predefined time limit. It appears that pure local search is comparable with the MIPbased heuristic methods, while MLS outperforms all methods regarding both criteria: solution quality and running time.