Vehicle Routing Problem with Overlap constraints

In this paper we studied an adaptive version of the vehicle routing problem for logistic of valuable goods. This problem is motivated by the need to reduce the predictability of the service. The objective is to minimize the total cost of a set of solutions but with not exceed a similarity degree in the set. The temporal similarity aspect is a very important factor of predictability but has never been take into account at the best of our knowledge. A new mathematic formulation is then proposed by introduced specifics constraints which avoid to create similar routes. The model was tested in modified Solomon's instances for the vehicle routing problem with time windows and results are discussed. Finally, two heuristics are proposed and compared both with an exact method and together.