به حداقل رساندن هزینه شبکه با استفاده از تنزیل مبتنی بر سطح آستانه

A network design problem in which every pair of nodes can communicate directly is discussed. However, there is an incentive to combine flow from different sources, namely, if the total flow through a link exceeds the prescribed threshold, then the cost of this flow is discounted by a factor α. Alternative mixed integer linear formulations for this problem are presented. Computational results comparing the models on a set of benchmark problems are also presented. The results show the effectiveness of the formulations: for discounts of 5–10%, the gaps between linear and integer solutions are within few percent. Such a model offers economic incentives in building and utilizing communication networks.

Special type of networks, so-called hub-and-spoke networks, have been used by the airline and telecommunication industry. A hub-and-spoke network supports traffic flows between multiple origins and destinations (many to many network). In order to exploit economies of scale, smaller number of links are selected to serve a large number of origin–destination pairs. Nodes where amalgamation is taking place (hubs) play a role of central transshipment facilities. The subnetwork consisting only of hub nodes is completely interconnected. Utilizing hubs as transshipment facilities implies a reduction in construction costs, centralized handling and sorting, and allows carriers to take advantage of economies of scale. There are many different instances of the hub location problem (HLP), and a common thread is to decide on which locations the investor must establish hubs in order to minimize the cost of the total traffic flow. The incentive for amalgamation of flow is offered through discounted costs for interhub traffic. This problem has been addressed in many papers. A detailed overview of existing formulations for p-HLPs can be found in Campbell [2]. Integer programming formulations for p-hub median problem, uncapacitated HLP, p-hub center problem and hub covering problems are presented. Several variations of these problems include the concept of flow thresholds on hub-spoke links. In this case, a link can be established only when the flow exceeds the threshold value. Skorin-Kapov et al. [16] have developed tight LP relaxations for hub location and some related uncapacitated p-hub median problems. Their approach led to exact solvability for the Civil Aeronautical Board (CAB) benchmark data set (air-traffic between 25 major US cities). Ernst and Krishnamoorthy [5] proposed a redesign of a postal delivery network in order to minimize overall costs. Services in their network can be sorted into three types: collection, transfer and distribution. Unit costs associated with these activities are proportional to distances. The cost factor for transfer (α) is a discount factor offered for inter-hub traffic, i.e., α<1. Four and three dimensional formulations were introduced and computationally compared (size vs. tightness). A procedure of adding cuts to tighten the formulations was developed. They used a data set generated by the Australia Post (AP) that contains 200 nodes representing postal districts. Smaller subproblems were used for the analysis of the behavior of shortest path-based heuristic, enumeration, and branch and bound algorithms. In [7] a network design problem was presented based on three service policies (one-stop, two-stop, all-stop). No hub-and-spoke structure was assumed. The objective was to minimize costs of running a single airline with several types of aircraft in its fleet. For all the policies, a heuristic solution procedure based on local improvements was developed and tested. From the obtained solutions they concluded that several nodes might be strong candidates for hub locations regardless of the policy used. The location of the candidates depended more on their geographical position than on their demand level. The tests were performed on the CAB data set and on a 39-node data set generated by a simple gravity model. An analysis of hub-to-hub link utilization might reveal that some links are indeed very busy. However, it can happen that the rest of the hub-to-hub links carry only a small amount of flow. Nevertheless, the cost of this small traffic is discounted because it is going through the hub-to-hub link. The amounts of traffic on the discounted links can be disproportional, which brings the idea of discounting only heavily used links. In [12] the HLP was modified to include possibilities of differential discounts on interhub links, depending on total traffic amounts, namely, an interhub link with larger flow will allow a larger discount than some other, less heavily used interhub link. The inherently nonlinear cost function is approximated by a piecewise continuous linear function, hence allowing linear programming solution methods. The cost function is increasing at decreasing rate as flows increase. Such an approach offers a more realistic treatment of discounts available to network users. Even in the case where the cost function is piecewise linear, the search for the optimal solution might be very difficult. One such class of problems, where the cost of a link is a concave nondecreasing piecewise linear function, is known as the Minimum Concave Cost Network Flow problem (MCCNF). The MCCNF problem is known to be NP-hard, and several solution techniques for the problem have been developed over the last two decades. One of the specialized MCCNF solution techniques is presented in [10]. One can also refer to [6]. Bryan [1] provides some additional extensions to hub location problems designed to increase efficiency of interhub links. In one of her formulations interhub links with flow below a minimum threshold are not open. In yet another formulation, the hubs should be completely interconnected. However, it is required that interhub links achieve a certain level of flow. This requirement determines the number of hubs to be open. The location of hubs and allocation of non-hub nodes is simultaneously provided. In this paper, we develop a model outside the traditional hub approach by emphasizing the links, not the nodes, of the communication network. We address a modification of the original HLP, as formulated in e.g., [16], namely, we do not proclaim certain nodes to be hubs, hence, we do not force the flows to use interhub links. Nevertheless, based on discounting incentives for amalgamation of flow, we would still like to construct a network with fewer links than in the complete interconnected network. The result is that with large enough discounts we will obtain a hub-like network, since users will be motivated to use a smaller number of discounted links. The problem can be applied to telecommunication networks, parcel delivery and airline transportation networks. Regarding today's explosion of bandwidth and speed associated with telecommunication networks, an important aspect of network design is the possibility to increase utilization of a link. This, in turn, creates economic incentives by constructing networks with fewer, but better utilized links. In Section 2, we describe the problem and formulate it as a mixed integer program. Section 3 presents a more compact formulation resulting in an alternative mixed integer model. Computational results are displayed in Section 4. The LP relaxation of the 4-dimensional formulation is tighter than the corresponding 3-dimensional LP relaxation. However, due to memory consumption, the 3-dimensional model serves better for larger data sets. The paper concludes with some directions for further research.

In this paper, we presented new alternative mixed integer programming formulations addressing network usage in light of possible discounted flows. Given discounting incentives based on total amount of flow on network links, users are motivated to amalgamate their flow. Three- and four-dimensional mixed integer programming formulations of our model were stated, and some solution strategies were tested on the benchmark CAB data set consisting of instances with n=10, 15, 20 and 25 nodes. The preference was given to branch and bound based techniques. For small n (n=10,15) it was possible to obtain the optimal solutions rather quickly. The strategies that we found attractive were mvs and frv (see Table 2). The frv strategy has a useful property that it aggressively searches for integer solutions. Hence, one can stop the execution of the frv branch and bound procedure if the best current integer solution is satisfactory. For middle-sized problems (n=20), our suggestion is to use the heuristics with fxb strategies (either fxb_mvs or fxb_frv) which almost always generate optimal solutions. For large problems (n=25), the simple rounding heuristic he0 produces satisfactory results in real time. For small discounts of 5–10%, all the proposed heuristics generate feasible integer solutions to the (CAB) data set with the gaps less than 3–4%. The behavior of our model clearly depends on input parameters (α,T). For larger values of α (i.e., for small discounts), the solution can still have a large number of non-discounted links. If the value of α is reduced, the number of discounted links increases followed by the cost reduction. The number of discounted links depends also on the threshold level. For small T the number of discounted links is larger than for larger T values. We believe that our model could be used in cases where a solution to the p-HLP generates discounts to links with insignificant flow. A solution to the p-HLP could force a pair of nodes to use hubs, although a direct link could be more beneficial for the nodes. In this case, the nodes have the incentive to leave the network. Our model could be used in cases where a customer is looking to satisfy his traffic needs using a network of a service provider with the threshold-based discounting. The customer will then amalgamate his flow generating an overall cost reduction for using the network. The model discussed in this paper allows several modifications as follows. For some applications (such as traffic flow, parcel delivery) it would be appropriate to add link capacities ukm. In the original model the role of upper-bounds on the flow were played by fij. The addition of link capacities might make our problem tighter. The new constraint would be defined as View the MathML source Further, a decision maker might find it inappropriate to use the same threshold T for all edges. The threshold could be modified to reflect the specific needs on a certain link. A matrix T=Tkm can be introduced. The new inequality can be then expressed as View the MathML source We anticipate that the models introduced in this paper could well be applied to the modified problem. Another extension of our work could lead to cost allocation problems and cooperative game theory based formulations, namely, by amalgamating flows, the total network cost could be reduced. Having a number of users with different proportions of flow contributing to total flow, and different multi-hop routes from sources to destinations, the challenge would be to allocate network cost in a fair manner, or to devise rules for formulating charges for network usage. A concern should be how to devise a cost structure so that users are encouraged to cooperate in order to bring the overall network costs down. This approach leads to cooperative game theory approach, extensively studied in a number of applications. For results concerning cost allocation in hub networks, see [14]. Since our model generalizes hub models, a future avenue of research will deal with developing cost allocation game theoretic approach to hub-like models.