مدل ها و رویکرد تولید ستون برای کمترین مسائل هزینه مسدود هزینه منابع با رله  Models and Column Generation Approach for the Resource-constrained Minimum Cost Path Problem with  Relays

1. Introduction In this paper, we study the resource-constrained minimum cost path problem with relays (RMCPR), which can be used to model many network design problems. For example in freight transport systems, it becomes impractical for both truck drivers and the whole transportation process to cover very long-haul distance in one trip (Willoughby and Uyeno 2001). In the truckload industry, the long-distance travel leads to a serious and chronic problem of high turnover rate, e.g., typically more than 100% (Uster and Kewcharoenwong ¨ 2011). This requires setting relay points along the paths for exchange of drivers, trucks and trailers. These relay points can be used for various purposes, e.g., driver rest and gasoline station. In addition, the RMCPR can also be used to model the network design problems in telecommunication systems, where the relay points may be used to boost signal quality over long distance (Cabral et al. 2007). More importantly, long-distance travel will inevitably lead to consumption of varieties of resources, typically including fuels of vehicle, time, distance, capacity, money, workload, and reliability requirements (Zhu and Wilhelm 2007). All these introduce issues of multi-resource constraints in the network design problems. We now formally define the RMCPR over a directed network G = (N, A,K) with node set N = {1, 2, . . ., n}, arc set A (|A| = m), and resource set K = {1, 2, . . ., r}. Each arc (i, j) has an installation cost of ci,j and an r -dimensional resource consumption vector wi,j = (w 1 i,j , w2 i,j , . . ., wr i,j ), where w k i,j represents the consumption of resource k along arc (i, j). A fixed cost gi occurs when a relay is located at node i. The RMCPR consists of selecting network arcs, finding a path from the source s to the destination t, and locating relays on some nodes of the path, such that the total cost of setting arcs and relays is minimized, and in the meantime for each resource k, the total resource consumption along the subpath between the source and the first relay, any two consecutive relays, and the last relay and the destination do not exceed a predefined maximum resource consumption Wk . The RMCPR essentially can be viewed as a single-commodity multi-resource-constrained network design problem with relays. To illustrate, we give an example of the RMCPR with three resources (e.g., K = {1, 2, 3}) in Figure 1. In this example, we need to determine a path from source s to destination t. The predefined maximum resource consumption Wk is 5 for each resource. A feasible path is given by the full line with relays located at nodes b, k, h and e. As one may observe, the source consumption along each subpath all does not exceed 5. For example, three resource consumptions between b and k are 5, 3 and 3, respectively. Whereas for subpath between h and e, these values are 5, 4 and 2, respectively.