Proposed Research Plan

Vehicle Routing Problems
Most of the problems in VRP area, discussed above, are still open for the graph networks. We list below some other interesting practical vehicle routing problems for which no approximation algorithms are known.

• VRP with satellite facilities (VRPSF). In VRPSF, there are several satellite facilities scattered in a given graph. When servicing the customers, the vehicle can go to these satellite facilities to replenish instead of coming back to the depot. For example, consider the case when multiple vehicles are available to service the customers. Then each customer should be serviced by exactly one vehicle, while each satellite facility can be visited by multiple vehicles.
• VRP with Cross Docking (VRPCD). In this problem we are given $p$ vehicles to transport various types of product from suppliers to customers through a cross-dock. The cross-dock serves as a temporary inventory, where product in a vehicle can be dumped and reassembled. In VRPCD one vehicle may collect some amount of product from the suppliers and dump them at the cross-dock and continue to pick up more goods, and another vehicle may upload some amount of product at the cross-dock and deliver them to the corresponding customers. The objective of VRPCD is to compute a schedule minimizing the maximum completion time of the vehicles (makespan).
• VRP with Pickup and Delivery(VRPPD) with excessive supplies. In the traditional settings of VRP with pick ups and deliveries, every pick up and delivery demand should be serviced. However, there are circumstances for which not all demands need to be satisfied. For example, in an instance of the $k$ -delivery TSP, we may have excessive supplies, so the number of pick up vertices may be larger than the number of delivery vertices. Therefore only a subset of the pickup vertices should be chosen in the tour to service all the delivery vertices. The solution techniques for the $k$ -MST problem might be helpful for this variation.

  In [28] Laporte et al. studied a similar model called the single vehicle routing problem with deliveries and selective pick ups (SVRPDSP). In this problem it is no longer required that all the pick up demands should be satisfied. Instead a pickup profit is associated with each vertex, and a tour of SVRPDSP should visit each customer, satisfy all the delivery demands and only part of the pick up demands. The cost of such a tour is defined to be the total edge cost of the tour minus the profit collected from the vertices. The objective of SVRPDSP is to find such a tour with the minimum cost. No approximation algorithms are known for this problem.
  

Network Facility Location Problems
Although we have proposed many efficient algorithms for the network center problems when either the number of facilities to be opened (i.e., $p$ ) is constant or the underlying network is restricted to be a specialized network, such as a tree, a cactus, or a partial $k$ -tree with fixed $k$ , many algorithmic issues are still unresolved. We list a few examples as follows. First, the running time of our algorithms for a tree network or the real line is exponential in $p$ . One challenging task will be to resolve a long standing open problem: Is there a linear-time algorithm for a tree network or the real line for arbitrary $p$ . Second, a sustained effort on location problems in a tree-like network, such as a cactus or a partial $k$ -tree with fixed $k$ , is needed. Especially for a partial $k$ -tree network of bounded tree-width, we introduce a two-level tree decomposition data structure to assist service-cost queries for any set of facilities, which is very helpful for a small number of facilities and a small number of facility candidate locations. We would like to know how to enhance the data structure to support more complicated queries, e.g., a set of continuous regions instead of a set of facility points. Third, not many results have been achieved for the case when the demands are located everywhere in a tree-like network or a general network, and for the case where the demands are represented by some connected structures instead of isolated points.

In addition, recently, more and more attention has been paid to facility location problems combined with network modification subject to certain budget constraints. That is, for a given budget, the goal is to change some parameters of the underlying network in order to improve the quality of a facility location (e. g., see [58]). Recent results have shown that when the underlying network is a line or tree, one can find a strategy in polynomial time to enhance the performance of the network by modifying (reducing) vertex weights and/or edge lengths subject to that the sum of reducing costs or the maximum reducing cost is not exceed the given budget (e. g., see [18]). However, the study of the modifications of other possible parameters, i.e., open-facility costs, vertex demand, and capacity, is a new and emerging field of study, and much remains to be explored.