Constraint based heuristic search applied to a vehicle routing problem

Modelling problems with explicit constraints gives the possibility of richer models and a much larger freedom of solution methods than conventional OR modelling. We have developed such a model for a real-world transportation problem, namely the transportation of goods between producing and consuming factories within the same company. The objective is to minimise transportation costs while ensuring satisfactory inventory levels at all sites. Classical OR techniques have failed to find good solutions to this problem even for moderately sized test cases. We use an iterative improvement heuristic coupled with an LP subproblem solver to solve this problem. Our solution method consists of two parts. An iterative improvement heuristics is used to solve the combinatorial problem of finding the vehicle routes and an LP model is used to find time for visits and quantity to load or unload. The improvement method is implemented in C++, while callable CPLEX is used to solve the dependent LP. Results will be reported for real world instances.