A multi-stage local search for a real-world vehicle routing problem

This paper considers a variant of the vehicle routing problem that involves the vehicle mixed fleet, two depots, two commodity types, multi-trip allowance and especially the decision of the vehicle queuing schedule at depots (due to depots´ limited number of available parking slots). There´re two objectives with the descending order of importance: minimizing the number of vehicles needed to serve all the customers within a time limit, and then, minimizing the total traveling times. A multi-stage local search is used to solve the problem. The algorithm is tested on 18 real-world data instances taken from the distribution system in a dairy corporation in Vietnam. Results are much better than the handmade routing plans created by experts of the corporation and highly comparative to a dynamic programming approach published before.