BILEVEL LINEAR PROGRAMMING MODELS AND ALGORITHMS FOR FREIGHT TRANSPORTATION
Freight transportation is generally a very complex domain where several players, each with its own set of objectives, act and operate at various decisional levels. There are different players in the field. The shippers who decide how much of each commodity to move from every origin to every destination and the means by which the goods will be moved. The carriers who respond to this transportation demands and route freight over the actual transportation network under their contro!. Finally, the government defined as the set of international, national and local authorities involved in any way with freight transportation via regulation and the provision of transportation infrastructure. In this work, we consider the case where only one shipper determines the demand for transportation over a network. However, he cannot decide fiow levels on arcs in a fully independent way due to the presence of a second agent controlling some links of the network and optimizing her own objective function. This situation is modelled as a game between two players P and Q acting o n the same network G. Player P fixes the fiows o n the arcs of G in such a way t ha t their divergence at some given nodes (sources and sinks) is equal to prescribed values. Such divergences may represent demand and availability levels for some commodity. On the other hand, player Q decides the values of the maximum capacities of some arcs of the network. Both players are interested in the fact that the connectivity between the sources and the sinks in the network is respected, i.e., they both want that the goods can reach their destination. However, they have different objectives. Player P aims at minimizing the transportation costs, whereas player Q aims at maximizing her profit (or, in generai, her utility) that is proportional to the fiow passing through the arcs under her control. Note that, in generai, the profit of player Q is not assumed to be equal to the cost of player P for the same are. Such game between players P and Q is modelled as a minimum cost flow problem for player P, where the are costs are given and the player Q decides the are capacities. The modelling of the games under investigation are mainly based upon three different research lines. First, the players understand the freight transportation system as a system where the actors involved do not act simultaneously and they explicitly take into account the sequential nature of the interactions among them. Second, they play a (hierarchical) game over a flow network which causes severe limitations and constraints to their action sets. Finally, the games exhibit linear characteristics and can be solved using bilevel linear programming. All these issues have already been discussed in the scientific literature, even though in different separate contexts. The merging of three mentioned approaches in only one single framework is a major contribution of our modelling perspective. Furthermore, bilevel programming is rich of theoretical results and numerica! algorithms, but is scare in actual applications. From this point of view, the present work might be considered as an interesting addition to the field. Bilevel noncooperative games in which one player ( called the leader) declares his strategy first an d enforces i t o n the other players ( called the followers) w ho react (rationally) to the leader's decision are referred to as Stackelberg games. Since the payoff functions and all the constraints in our Stackelberg games may be expressed in a linear form, these games will be formalized as bilevellinear programming problems (BLPPs). In generai, bilevel programming problems are difficult to sol ve because of their inherent non-convexity and non-differentiability. To face their NP-hard nature, we identify some properties of the game solutions which allow us to define a heuristic algorithm restricting its (local) search on the set of the Nash equilibrium points. The optimal solution of any BLPP lies on a vertex of the leader's inducible region. Relying on this result, we develop an algorithm which allows to move from a starting point of the shipper's inducible region to another point in the shipper's inducible region always providing a better solution for him. When no further better points may be attained, the algorithm stops. Unfortunately, only a local optimum is identified. The rationale behind the algorithm stems from the consideration that the optimal solution for our BLPP is also a Nash equilibrium point. In particular, the algorithm moves from a Nash equilibrium point to another better Nash equilibrium point of the BLPP under study. This framework may describe, as an example, the situation where restrictions are imposed by some alpine country on the number of trucks allowed to cross it by road each year. A different context involving the presence of a second agent o n the shipper's network occurred when the International Transporters' Association (UND) of Turkey had to face when the war in the Balkans started. This situation motivates our investigation on hierarchical noncooperative network games. The road freight traffi.c from Turkey to Centrai and Western Europe and viceversa suffered major disruptions because of the war in Balkans during the nineties. UND is the shipper controlling the quasi-totality of this traffi.c thus assuming the role of player P. H e had to cope with an "adverse entity" able to modify the available capacity on some specific links his vehicles had to pass through. The region involved in the confiict may be represented as a connected subnetwork disconnecting the origin and the destinations of the road transportation network since alternative road routes are not easily affordable. Other possibilities, like the seaborne links now operating, did not exist at that time. Hence the whole freight traffi.c was performed using a single mode of transport. The models developed in this work allow the shipper to perform a worst-case analysis at the strategie level for this situation assuming that player Q wishes to maximize the costs he has to afford when going through the region under her control. In fact, it is meaningless to talk about the utility or the profit the war may seek t o maximize. However, i t becomes a sensible modelling when the utility of player Q is strictly related to the costs afforded by player P on this portion of the network. lf player Q is maximizing her utility which corresponds to player P's costs, automatically she plays to maximize player P's costs. Hence the model represents a worst-case analysis for player P. A simple graph composed of 99 nodes and 181 arcs is presented. Player P controls a sub network composed of 100 arcs. The others 81 links representing the connections within the Balkans and Eastern Europe form a connected sub network. Only the main road links ha ve been considered ( motorways or highways). The capacities are calculated taking into account the total number of transit permits available for each country. This figure is annually fixed in bilatera! Joint Committee Meetings. Player P's costs are the average generalized costs derived as a function of lengths and transfer times in the physicallinks. Player Q does not have profits or losses for the fiows passing through the P zone and it is also assumed that the profits she earns for each unit of fiow going through the arcs under her control are equal to the costs afforded by the shipper when traversing these arcs. All the relevant data required to calculate these figures are collected in the UND Annual Sector Report 1997-98 (1999). The heuristic algorithm has been tested on this network and its results have been compared with the outcome obtained by using an exact enumeration procedure. Since it turns out that the percentage error of the heuristic algorithm is equal to 0,3%, we may claim that its performances are certainly highly satisfactory, at least in this specific example. Different extensions of the models and the algorithm developed may be easily envisaged both from the theoretical and the application side. These advances would provide either faster local or global search algorithms either more complete models representing in deeper detail the actual system and the interactions among the actors involved. Hence a decision support system for the shipper's decision making process at the strategie level can be built and effectively used by freight transportation practitioners.