Combining exact and heuristic methods for solving a Vessel Routing Problem with inventory constraint and time windows

We look at the real-world problem of the transportation of a single commodity by sea between producing and consuming factories within the same company using a fleet of vessels. The objective is to minimize transportation costs while ensuring satisfactory inventory levels at all the factories. Classical OR techniques use considerable time to find solutions even for moderately sized test cases. We present a new approach, using an iterative improvement heuristic combined with an LP solver to solve this problem. The solution method presented consists of two parts. The iterative improvement heuristic is used to solve the combinatorial problem of finding the vessel routes and an LP model is used to find time for calls and quantity to load or discharge. The method is implemented in C++, using callable CPLEX for solving the LP problems. Testing on real-world cases have yielded good solutions within acceptable time limits.