Iterative Local-Search Heuristic for Weighted Vehicle Routing Problem
Xinyu Wang, Shuai Shao, Jiafu Tang
Abstract
Solutions to the weighted vehicle routing problem (WVRP) find numerous applications, such as home-to-work bus service, toll-by-weight cargo transportation, perishable-food delivery, and hazardous waste collection. This paper presents mathematical WVRP models corresponding to both collection and delivery cases. This study demonstrates WVRPs to be NP-hard, and proposes an efficient heuristic method (RI-ILS) to solve WVRPs. RI-ILS is based on principles of regret-insertion and iterative local-search. Several computational experiments were performed in this study to demonstrate the utility of the RI-ILS approach. As observed, when solving traditional vehicle routing problems (VRPs), RI-ILS yields good results under all testing conditions. In particular, it provides new best-known solutions under 12 testing conditions. When solving WVRPs, the RI-ILS method outperforms two recently published state-of-the-art algorithms in terms of solution quality, computational time, and stability. Case studies have also been performed in this research based on real-world data obtained from two Chinese companies that provide home-to-work bus service to their employees.