Intraroute Resource Replenishment with Mobile Depots

In numerous practical vehicle-routing applications, larger vehicles are employed as mobile depots to support a fleet of smaller vehicles that perform certain tasks. The mobile depots offer the possibility of keeping the task vehicles operational by supplying them en route with certain resources. For example, in two-echelon distribution systems, small task vehicles are used to navigate narrow streets and to deliver/collect goods or to collect waste, and larger vehicles serve as mobile depots to replenish the goods to be delivered or to receive collected goods or waste at the outskirts of the urban area. Accessibility constraints may also be imposed by regulations on emissions, which make some areas only accessible for environmentally friendly vehicles such as, for example, battery-powered electric vehicles. Especially if the respective refueling infrastructure is sparse, mobile refueling stations seem to be an interesting alternative. In this paper, we introduce the vehicle-routing problem with time windows and mobile depots (VRPTWMD) to capture the routing decisions of the described applications in a generalized fashion. The VRPTWMD is characterized by fleets of task vehicles (TVs) and support vehicles (SVs). The SVs may serve as mobile depots to restore either the load or the fuel capacity of the TVs that are used to fulfill the customer requests. We present a mixed-integer program for the VRPTWMD with which small instances can be solved using a commercial solver. Moreover, we develop a high-quality hybrid heuristic composed of an adaptive large neighborhood search and a path relinking approach to provide solutions on larger problem instances. We use a newly generated set of large VRPTWMD instances to analyze the effect of different problem characteristics on the structure of the identified solutions. In addition, our approach shows very convincing performance on benchmark instances for the related two-echelon multiple-trip VRP with satellite synchronization, which can be viewed as a special case of the VRPTWMD. Our heuristic is able to significantly improve a large part of the previous best-known solutions while spending notably less computation time than the comparison algorithm from the literature.