Institute of Transportation, MOTC

This study investigates the capacitated vehicle routing problem with overlapping service regions, which is an extension of the conventional vehicle routing problem (VRP). We are interested in solving the optimal decisions including the fleet deployment using the vehicles in the original region, the trans-regional vehicles and the vehicles from outsourcing and the corresponding vehicle routes for logistics companies to satisfy customers’ demand with pre-determined and overlapping service regions. We present a new districting concept of “general overlapping service regions” (GOSR) in this study, that is a more generic version of the “chain-type overlapping service regions” than that presented in a previous study. GOSR allows more than two service regions overlapping with each other, increases the flexibility in vehicle routing and fleet deployment, and serves as a novel model of the distribution operations for logistics companies.
We formulate a mathematical model following the scenario of the capacitated VRP with overlapping service regions. It is well known that the conventional VRP is NP-hard. Therefore, the concerned problem in this study is more complicated and hence, more difficult, and we propose a genetic algorithm (GA) as our solution approach. The Data structure of chromosome encoding in our GA is not only comprehensive, but also easy to deal with the situation of GOSR. In addition, we also develop a local search mechanism to enhance the search ability of our GA. We randomly generate our instances in our numerical experiments by referring to the benchmark problems for the conventional VRP and taking into account of the characteristics of GOSR. Our experimental results show that our proposed GA with the proposed local search mechanism is able to obtain solutions with excellently quality effectively, and making use of GOSR may save distribution cost up to 10% for logistics companies.