The problem addressed in this paper-the linehaul- feeder vehicle routing problem with virtual depots (LFVRP-VD)-can be regarded as an extension of the vehicle routing problem. During delivery operation, one large vehicle departs from the physical depot (PD) and services all virtual depots (VDs). A set of small vehicles delivers to customers and, if necessary, reloads either from the PD or from the large vehicle at a VD before continuing work. The objective of the operation is to minimize the total travel and waiting costs for all vehicles. Two heuristics that embed the cost-sharing method and the threshold method are proposed for initial solution construction. Seventeen test problems are extensively examined. The results show that the cost-sharing method outperforms the threshold method in terms of several selected performance measures. In addition, the more candidates available a VD can choose, the better the obtained objective value. Note to Practitioners-Linehaul-feeder vehicle routing problem with virtual depots is practical to the logistics and transportation companies, especially in the urban area where local streets are too narrow or large vehicles are not allowed to enter. Note that the higher the customer demands, the better the benefit of the LFVRP-VD.
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING