A specialized approach based on integration of customers and deliberate restoration mechanisms for very large scale vehicle routing problem

This paper propose a new specialized approach for very large scale vehicle routing problems (VRPs). Our approach has two distinguishing mechanisms; simplification and gradual dissolution mechanisms. The first mechanism tries to reduce the number of customers apparently by gathering some neighborhood customers to one virtual customer. On the other hand, the second mechanism is used for reducing the difference between original and simplified problems by gradually reinstating the simplified problem to original one. In concrete terms, the second mechanism tries to dissolve cluster of customers gradually. The aim of our approach is to perform an effective search by the interaction of two these mechanisms.Through some typical test problems, it was demonstrated that our approach could derive better results more effectively than conventional approach for very large scale VRPs.