Construction of a real world bilevel linear program of the highway network design problem

UNIVERSITY OF

ILLINOIS LIBRARY

AT URBANA-CHAMPAIGN

BOOKSTACKS

V7

CENTRAL CIRCULATION AND BOOKSTACKS

The person borrowing this material is re-
sponsible for its renewal or return before
the Latest Date stamped below. You may
be charged a minimum fee of $75.00 for
each non-returned or lost item.

Theft, mutilation, or defacement of library materials can be
causes for student disciplinary action. All materials owned by
the University of Illinois Library are the property of the State
of Illinois and are protected by Article 16B of lllinoii Criminal
law and Procedure.

TO RENEW, CALL (217) 333-8400.
University of Illinois Library at Urbana-Champaign

SEP 011999

6 2001

When renewing by phone, write new due date
below previous due date. L162

BEBR

FACULTY WORKING
PAPER NO. 1464

fHE LIBRARY OF Tu«r

iOiS

Construction of a Real World Bilevel Linear
Program of the Highway Network Design Problem

Omar Ben-Ayed
Charles E. Blair
David E. Boyce

College of Commerce and Business Administration
Bureau of Economic and Business Research
University of Illinois, Urbana-Champaign

BEBR

FACULTY WORKING PAPER NO. 1464

College of Commerce and Business Administration

University of Illinois at Urbana- Champaign

June 1988

Construction of a Real World Bilevel Linear Program
of the Highway Network Design Problem

Omar Ben-Ayed, Graduate Student
Department of Business Administration

Charles E. Blair, Professor
Department of Business Administration

David E. Boyce
Department of Civil Engineering, University of Illinois

Digitized by the Internet Archive

in 2011 with funding from

University of Illinois Urbana-Champaign

http://www.archive.org/details/constructionofre1464bena

CONSTRUCTION OF A REAL WORLD

BILEVEL LINEAR PROGRAM

OF THE HIGHWAY NETWORK DESIGN PROBLEM

OMAR BEN-AYED and CHARLES E. BLAIR

Department of Business Administration, University of Illinois
at Urbana-Champaign, 467 Commerce West, Champaign, IL 61820

DAVID E. BOYCE

Department of Civil Engineering, University of Illinois
at Urbana-Champaign, 205 N. Mathews Street, Urbana, IL 61801

(May 1988)

The formulation of the Highway Network Design Problem (NDP) as a Bilevel
Linear Program (BLP) allows more realistic solutions taking into account the
reaction of the users to the improvements made by the system. In this paper, a
conceptual framework for the optimization of the investment on the inter-
regional highway networks in developing countries is proposed . The model is
applied to the formulation of a real world case study based on empirical data
for Tunisia. Much effort was ended to make the implementation as realistic as
possible , taking into consideration travel time, operating costs, accidents
costs, improvement costs , conservation laws , effect of intra-regional flow . . . A
new formulation allowing the incorporation of any improvement cost functions ,
including non-convex and non-concave functions , is introduced .

1- INTRODUCTION

This paper is concerned with the construction of a Bilevel Linear Program
(BLP) for optimizing the investment in the interregional highway network of a
developing country. The notion of development is related, in this study, only
to rural highway transportation. A country or region is considered to be
developing if most or all of its inter-city traffic is carried on two-lane
highways or on a lower quality of roads.

The study is based on actual data for Tunisia. Tunisia (Figure 1) is a
164,000 square kilometer country located in North-Africa and bounded on the
north and east by the Mediterranean Sea, on the south-east by Libya and on the
west by Algeria (The American University 1979 pp.ix-xvii). Its population was
6,966,173, with 47 % rural and less than 15 % living in the south, as reported
by the census of March 30, 1984 (Institut National de la Statistique 1984 p. 24
and pp. 269-270). The largest cities are Tunis (the capital), Banzart (Bizerte),
Safaqis (Sfax), Susah (Sousse), Qayrawan (Kairouan), and Qabis (Gabes). The per
capita income is about US$ 1,100 and the inflation averaged nearly 10.5 % in
1983-1984 (Embassy of Tunisia 1987). The currency in Tunisia is the Tunisian
Dinar (TD); 1 TD is equivalent to 1.24 US$ as of November 4, 1987 (Bank of
America Global Trading 1987).

The highway network in Tunisia consists of 18,142 kilometers (KM) of roads
(Direction de l'Entretien et de 1 'Exploitation Routiere 1984 pp. 1-2); 53 % of
them are paved. The average width of paved roads is 5.5 meters (M); 17 % are
narrower than 4.5 M. The total number of vehicles in the country was estimated

at 385,600 on December 31, 1982 (Direction de l'Entretien et de 1 'Exploitation
Routiere 1982 p. 78).

The choice of a developing country seeks to motivate wider applications of
operations research models to solve transportation design problems in those
regions where sophisticated decision making techniques are not sufficiently
introduced. The allocation of the budget among road links in developing
countries is often based on simple rules, such as the comparison of the
increases of daily traffic on the links to be improved or the comparison of the
differences between benefits and costs for the projected improvements. The high
cost of highway improvements makes it necessary to elaborate more powerful
optimization models to utilize better the assigned budget and to take into
account the specific characteristics of the transportation networks in those
countries. Such characteristics are very important especially in rural networks
where the difference between developed and developing is so significant that
the models elaborated for one category can hardly be applied to the other. For
example, models measuring capacity in number of lanes do not make sense in a
developing country where it is uncommon to find a rural highway with more than
two lanes; even worse, a high proportion of the roads are not paved.

While a great effort has been made to make the presentation as realistic as
possible, considerable liberties were taken with the data, both to fill in gaps
and to simplify the model. Some of the data used were recent; others were old.
For some parts of the model, no data existed at all; in this case information
was obtained from other countries and adjusted, or sensible subjective es-
timates were used.

2- RURAL HIGHWAY NETWORKS IN DEVELOPING COUNTRIES

The highway network in developing countries basically consists of two-lane
paved and unpaved roads. Two- lane roads are in principle undivided, meaning
that the passing of slower vehicles requires the use of the opposing lane where
sight distance and gaps in the opposing traffic stream permit. The traffic flow
in one direction influences the flow in the other direction, which requires the
inclusion of the total flow in both directions in all cost functions.

A significant part of the analysis is built on the data from the Highway
Capacity Manual (Transportation Research Board 1985 pp. 8 • 1-8 • 32) . The Manual
uses the concept of levels of service (LOS), a qualitative measure describing
operational conditions within a traffic stream and their perception by the
travellers. Six levels of service are defined from A to F; level of service A
represents the best operating conditions (free flow) and level of service F the
worst (forced or breakdown flow). Level of service E represents operating
conditions at or near capacity.

The Highway Capacity Manual (HCM) provides (Table 81 p. 8-5) maximum values
of the ratio of flow to capacity measured under ideal conditions (ideal
capacity); ideal conditions, as defined by the HCM, are nonrestrictive geometr-
ic, traffic, or environmental conditions; specifically they include: 1) design
speed is greater than or equal to 60 miles per hour (97 KM/H) , 2) roadway width
is greater than or equal to 24 feet (7.3 M), 3) width of both usable shoulders
is greater than or equal to 12 feet (3.7 M) , 4) "no passing zones" are not used
on the highway, 5) all vehicles are passenger cars, 6) directional split of
traffic is 50/50, 7) there are no impediments to through traffic due to traffic
control or turning vehicles, and 8) terrain is level.

Whenever ideal conditions are not satisfied, adjustments are made using the
following relationship:

X± = 2800R1DWH, (1)

where Xj is the flow in both directions for prevailing roadway and traffic
conditions for level of service i in vehicles per hour, R^ is the ratio of flow
to ideal capacity for level of service i, obtained from Table 81 in the HCM, D
is an adjustment factor for directional distribution of traffic, obtained from
Table 8-4, W is an adjustment factor for narrow lanes and restricted shoulders
width, obtained from Table 8-5, H is an adjustment factor for the presence of
heavy vehicles in the traffic stream, computed as:

H = [1 + pT(eT - 1) + pR(eR - 1) + pB(eB - l)]'1

where p-p is the proportion of trucks in the traffic stream, pR is the propor-
tion of recreational vehicles, pg is the proportion of buses, e-p is the
passenger-car units (PCU) equivalent of one truck (passenger-cars refer to all
vehicles having exactly four wheels contacting the road, including light vans
and pickup trucks), eR is the PCU equivalent of one recreational vehicle, and
eg is the PCU equivalent of one bus; e-j-, eR, and, e« are obtained from Table
8-6 in the HCM. Under ideal conditions and level of service E, relationship (1)
gives an ideal capacity of 2800 PCU; for different conditions the actual
capacity can be found easily by simple application of the formula.

The data suggested by the HCM might be applied to developing countries;
however, some extensions are necessary. Table 8-5 does not consider roadways
narrower than 5.5 M, whereas 4 M roadways are very common in developing count-
ries. Moreover, the HCM ignores the condition of the road surface, even though
the surface has an important impact on many factors such as capacity and
operating costs. Surfaces can be classified into three categories: asphaltic
concrete overlay (referred to in this study as asphaltic), surface treatment
(referred to in this study as treatment), and unpaved. Every road in each
surface category can be ranked as good, fair, or poor, which gives a total of
nine states of surface.

The surface of the shoulders as well as the roadway can be included in a
capacity analysis. The surface of the shoulders is always of lower quality;
when the surface is the same, the road is considered to consist of a roadway
and no shoulders, as is usually the case for unpaved roads. According to Table
8-5 in the HCM, widening of shoulders beyond 12 feet (3.7 M) has no effect on
increasing capacity. This result is applicable to roads with wide roadways (>
5.5 M); however, when roads with narrower roadways are considered, the effect
of wider shoulders is significant and must be included in the Table. The
quality of the surface can be given by two other tables, one for the roadway
and the other for the shoulders. It is important to notice that the effect of
the surface of the shoulders depends on their width: the narrower the shoul-
ders, the less significant the effect of their surface. Relationship (1) can be
modified to become:

Xi = 2800RiDWHPS, (2)

where P is an adjustment factor for the effect of the quality of the roadway,
and S is an adjustment factor for the effect of the quality of the shoulders.
An empirical analysis is necessary to extend Table 8-5 in the HCM to narrower
widths and to provide realistic estimates for the coefficients P and S. Two
more ideal conditions need be added to those listed in the HCM: 9) the surface
of the roadway is asphaltic concrete (or a similar quality) and in good
condition, 10) the shoulders are treatment and in good condition.

3- THE DECISION VARIABLES

The two decision variables that are related to every (existing or added)
link in the network are the flow and the added capacity . The flow is usually
measured with respect to the design hour. The selection of an appropriate hour
for design purposes is a compromise between providing an adequate level of
service for every (or almost every) hour of the year and economic efficiency.
Customary practice is to base design on an hour between the 10 and the 50
highest hour of the year. For rural highways, the 30 highest hour is commonly
used (Transportation Research Board 1985 p. 2 -10). The flow during the design
hour is not a constant value; however, it is often agreed that for rural
highways the flow during the 30 h highest hour is about 12 % of the average
daily flow (Wohl and Martin 1967 pp. 164-179; Transportation Research Board 1985
pp. 2 • 7-2 • 12) . This coefficient, called the design hour ratio, is used to
convert daily flow into hourly flow, or vice-versa.

The capacity is assumed to be continuous to permit small link improvements.
One convenient unit of measure of capacity is the PCU per hour. Since the
traffic involves other vehicles such as buses and large trucks, those heavy
vehicles are converted to equivalent PCU (Table 8-6, HCM) . Capacity refers to
the maximum PCU allowed in the road in both directions, without leading to
heavily congested flow (high delays and low speeds). Likewise, the added
capacity is evaluated in PCU added to the capacity of the road, and the flow is
also measured in PCU.

For the study of the Tunisian highway network, we found it suitable, given
the data available, to partition Tunisia into 19 regions (Figure 1). The study
examines the transportation network connecting those regions. Each region is
both an origin and a destination, and is represented by a centroid node labeled
from 1 to 19. The network includes also 39 intermediate nodes labeled from 20
to 58. The 112 links included in this study, described in Table 1, are defined
by their end nodes, length, terrain (1 for level, 2 for rolling and 3 for
mountainous), roadway width, shoulder width, roadway surface quality and
shoulder quality (1 for asphaltic-good, 2 for asphaltic-fair, 3 for asphaltic-
poor, 4 for treatment-good, 5 for treatment-fair, 6 for treatment-poor, 7 for
unpaved-good, 8 for unpaved-fair and 9 for unpaved-poor) . The data about the
terrain are given by the Army Map Service (NSPE 1957), whereas most of the
other data are provided by the publications of the Direction de l'Entretien et
de 1 'Exploitation Routiere (detailed maps, Infrastructure du Reseau Routier
pp. 7-51 and map of Recensement General de la Circulation). However, little
information is available about the width and the quality of the roadway surface
and no information was available about the shoulders. The following assumptions
are made: l)if the road is national (referred to as GP) its width is 6.5 M or
larger; if it is regional (referred to as MC) its width is 4.5 M or larger but
less than 6.5 M; and if it is local (referred to as RVE) its width is less than
4.5 M; 2)the real width of the roadway is proportional to the width of the road
on the detailed maps and is also proportional to its average flow; 3)the sum of
the widths of roadway and shoulders of all roads is at least 10 M (SETEC 1982
pp. An- 13 • 2 • 1-An- 13 -2 • 10) ; 4)the pavement is asphaltic when the roadway is at
least 8 M width; otherwise, the pavement is treatment (SETEC 1982 p. 13 25);
5)the surface quality of the pavement of all links in a given region is equal
to the average quality of all pavements of that region, rounded to the nearest
integer; 6) if a link connects two regions, its quality is the average of their
qualities; 7)the quality of the surface of all unpaved roads is fair; 8)the
quality of the shoulders is unpaved-fair for paved roads; 9)there are no shoul-
ders for unpaved roads.

4- FORMULATION OF THE NETWORK DESIGN PROBLEM (NDP) AS A BLP

Bilevel Linear Programming (BLP) is similar to a standard Linear Programming
(LP), except that the constraint region is modified to include a linear
objective function; BLP can be visualized as an organizational hierarchy in
which two decision makers seek to improve their strategies from a jointly
dependent set S, S=[(x,y): Ax+By<b, x,y>0}. The upper decision maker, who has
control over x, makes his decision first, hence fixing x before the lower
decision maker selects y (Bialas and Karwan 1982 and 1984, Bard 1983, and Ben-
Ayed 1988). The optimization problem being formulated in this paper is con-
cerned with the optimal allocation of investment among the links of the
transportation network, by adding new arcs or improving existing ones.

While investment costs are controlled and allocated in an optimal way from
the system's perspective, travel costs depend on traffic flows, which are
determined by users' route choice (Ben-Ayed, Boyce and Blair 1988). Since users
are assumed to make their choices so as to maximize their individual utility
functions, their choices do not necessarily coincide, and may conflict, with
the choices that are optimal for the system. The system can influence users'
choices, however, by improving some links and making them more attractive than
others. In deciding on these improvements, the system tries to influence the
users' preferences in minimizing total system costs. The partition of the
control over the decision variables between two ordered levels requires the
formulation of the Network Design Problem (NDP) as a Bilevel Program, in which
the system is the upper-level decision maker and the user is the lower-level
decision maker.

LeBlanc and Boyce (1986) first gave an explicit formulation of the NDP as a
BLP; their formulation, however, requires the unrealistic assumption of linear
improvement cost functions. Ben-Ayed et al. (1988) gave a similar, but more
general, formulation that allows convex as well as concave improvement cost
functions. Next, we propose a new formulation that has the ability to incor-
porate any piecewise linear function, including non-convex and non-concave
functions .

Consider any piecewise linear function of Z defined as:

f(Z) = bmZ + dm, for all Z e [qm-l>qrJ » m=1» ■ ' >J-
The function f can be equivalent ly stated as:

f(Z) = (biqi + dl) + Ij = i,m-i bJ+1(qi+1 - qj) + bm(Z - q^)

for all Z e [^m-l'^m^' m=l,--»J- By adding and subtracting Z - = 1 m_1 Z(b--
b-+^), we obtain:

f(Z) = (b^+di) + iioi^-iCbj+i-bjXZ-qj) + 2j=m,j.i(bi+1-bj)0

= (bjZ + dx) +^j = i,j-i (bj + 1J - bj)ilAX[(ZJ - 'qp, &].

If we denote by W: the maximum of (Z-qi) and 0, function f can be formulated
as a BLP as follows:

MIN tbyZ + dx) + Ij.„if j-i (bJ+1 - bj)Wj

where $ - solve:

MIN Ejii j Wj

Wi * Z - q,J

Wj > 0.

Using the above concepts for improvement cost functions and building on Ben-
Ayed et al., the following formulation of the NDP as a BLP can be obtained:

MINZa la *Ca + *KblaZa + dla) + Zm=l,Ja-l <bm+l
where Ca, Ca, Wfl, Xa and Xa(j solve:

KIN la {(Ca + sCa) 4- E^ja.! Wma}

such that:

,a

- braa)Vl)

for each node n and each destination

d:

ZaeAn Xad " ZasBn Xad = und
for each link a:

Ca . " rmaXa " SmaZa - sma>
^a " ^maXa + £maZa - ^ma'

"ma ~ Za - "^ma'

W < h - n
"ma - ua 4ma'

ld xad " xa = 0

Za> Ca> ^a> Wma> Xa' Xad - °

m=l, . . ,Ma
m=l, . . ,Ma
m=l, . . , Jfl-
m=l, . . , Ja-

1
1

where Za is the number of units of capacity added to link a; Xfl is the flow on
link a; Xa(j is the flow on link a with destination d; Ca is the approximation
of the system travel cost function on link a; Ca is the approximation of the
cumulative user cost function on link a; d^a is the intercept of the first
piece of the improvement cost function; bma is the slope of the piece m
delimited by qm_i a and qma; Wma is the maximum of (Za-qma) and 0; x is a
factor to convert improvement cost to the same units as travel time; Ma, Ma,
and Ja are the numbers of segments in the approximations of system travel cost,
cumulative user travel cost, and improvement cost of link a, respectively; e is
a positive scalar sufficiently small so that the optimum to the above problem
is the same as the one with e equal to zero; AR and Bn are the sets of links
pointing out of and in node n, respectively; u ^ is the required number of
trips between node n and destination d; rma and rma are the slopes of the
linear pieces in the travel cost approximations; s a and s„a are the intercepts
of the same pieces; and g a and g __ are the effects of improvement on reducing
sma and sma, respectively.

It should be emphasized that the NDP is always concerned with the costs of
the system to the community as a whole; the objective function to be minimized
is the total system costs consisting of system travel costs as a function of
the flows and the links improvements, and improvements costs as a function of
the links improvements. The lower objective, which is a constraint, consists of
the cumulative user travel cost, or integral of the average travel cost with
respect to flow, and the sum of the W_a required by the non-convex improvement
functions .

5- THE OBJECTIVE FUNCTIONS
Travel Time Functions

To our knowledge, all travel time functions in the literature are function
of directional flow, and therefore are implicitly intended for divided highways
only; no analytical representation is available for two-lane highways. An
empirical travel time function is now proposed based on data provided by the
HCM. Table 81 in the HCM gives the minimum average speeds versus the maximum
values of the ratio of flow to capacity. For example under ideal conditions the
speed at level of service A is greater than or equal to 93 KM/H. Equivalently
the travel time spent per KM is less than or equal to .643 minute (60/93). On
the other hand, the ratio of flow to capacity is less than or equal to .15
which means that the flow is less than or equal to 420 PCU. Therefore, a flow

less than or equal to 420 PCU corresponds to a travel time less than or equal
to .6428 minute per KM. It seems reasonable to assume equality . Similarly for
the other levels of service, a flow equal to 756 PCU corresponds to a travel
time of .678 minute/KM, 1204 corresponds to .717, 1792 corresponds to .746 and
2800 corresponds to .829. A sixth point can also be obtained; free flow
corresponds to the design speed, or equivalently, travel time is .621 minute/KM
when speed is 97 KM/H. For any other value of the flow between 0 and capacity,
a linear interpolation is used; an average travel time function is obtained by
connecting the six points, as shown in Figure 2.

For every link, an average travel time function can be obtained by applying
relationship (2) to the corresponding entries of Table 8-1. For rolling and
mountainous terrain, the design speeds need be known to find the travel time
corresponding to free flow. Given any geometric, traffic, environmental, and
surface condition, the average travel time obtained using the above procedure
is monotonously increasing with respect to the flow.

Level of service F was not considered so far because of its instability.
This level is distinguished by its high density, or number of vehicles occupy-
ing a given length or roadway. The density corresponding to the capacity is
called the critical density; level of service F occurs when the density exceeds
the critical density. At this level queues are formed which are characterized
by stop-and-go movement. Since at level of service F the vehicles are delayed,
the flow is small. A small flow can correspond to either a high travel time if
the flow is unstable, or a low travel time if the flow is stable. Therefore,
each flow can correspond to two travel times, which violates the definition of
a function. This problem can be overcome by assuming that the flow can exceed
the capacity, but for those flows greater than the capacity the travel time
increases sharply.

For our case study, some of the data needed for the formulation of the
travel time functions are not available; the following assumptions are added:
l)the data of Tables 8-1, 8-4, 8-5 and 8-6 in the HCM apply to the Tunisian
case; 2)the directional split is 60/40 for all links (HCM p. 8 -13); 3)the per-
centages of no passing zones are 20 % in level terrain, 40 % in rolling terrain
and 60 % in mountainous terrain (HCM p. 8 -13); 4)the design speeds are 95 KM/H
for level terrain, 90 KM/H for rolling terrain and 75 KM/H for mountainous
terrain (personal experience); 5)additional data can be obtained from any table
by using either interpolation or extrapolation; interpolation is linear while
extrapolation is based on regression analysis; 6)the vehicle mix, for all
links, consists of 83.5 % passenger cars, 13.9 % trucks and 2.6 % buses
(Direction de l'Entretien et de 1' Exploitation Routiere 1982 p. 22); 7)the
factors P and S in Tables 4 and 5 apply to the Tunisian case; 8)when the flow
exceeds the capacity, the slope of the average travel time is an arbitrarily
high number that is the same for all links. Based on those assumptions, Tables
2 and 3 are constructed as extensions of the original tables 81 and 8-5 in the
HCP.

For each link, an average travel time function is found by applying the
procedure explained at the beginning of this section, and using the new Tables.
To illustrate, consider a typical road in Tunisia; it is a 6.5 M width paved
road where the pavement type is treatment and the condition is fair, the
shoulders are unpaved-fair and 5 M wide, and the terrain is level. The average
travel time function obtained for this link is shown in Figure 3. The system
travel time function is shown in Figure 4; the system travel time at a flow X
is equal to the product of X by the average travel time at flow X. The cumula-
tive user travel time function is shown in Figure 5; the cumulative user travel

8

time at a flow X is equal to the area below the average travel time and above
the abscissa axis, and delimited by 0 and X.

In developing countries, travel time cannot be the only component of the
travel cost function because of the low value of time of travellers. Other
factors such as operating costs and accidents costs must be included.
Operating Costs

Operating costs include ownership costs and running costs. Ownership costs,
such as purchase costs, insurance, and economic ageing costs can be neglected
because they are independent of the decision variables; so only running costs,
such as fuel, grease, oil, tires, and depreciation (technical ageing) are
considered. Steenbrink (1974 p. 209) emphasized that vehicle operating costs be
taken without taxes "because the share of taxes in the market-prices of these
costs are very high". The inclusion of taxes in the social costs is misleading
since what is relevant for the community is not what is paid by the individual
for a liter of gasoline, for example, but what the value of that liter is. In
developing countries, besides the products being highly taxed where the
consumer pays more than the economic value, there are other products that are
subsidized by the government and their prices are less than their economical
values. As far as the social objective function is concerned, the economic
values must be considered without taking into account the price paid by the
individual; but when the objective of the user equilibrium is concerned, the
price paid by the individual is the one to be considered.

Since running costs differ from one car to another, a standard car represe-
nting the average cost must be considered. The average running cost of this car
should be computed for different conditions including surface, flow, capacity,
and terrain. As was noted by Moyer and Winfrey (1949), the differences in
operating costs on stabilized surfaces, bituminous, port land cement concrete,
and brick surfaces are small and difficult to measure; but when compared to
operating costs on untreated gravel and earth, the differences are very marked.
The connection of the flow and the capacity to the running costs is visualized
by the fact that in high traffic densities, queues are formed and then breaking
and accelerating are more often required, causing extra use of fuel, extra wear
of tires and extra wear on the gearbox (Steenbrink 1974 p. 210). Assuming that
drivers operate their vehicles at the maximum speed permitted by prevailing
flow and road design, high speeds made possible by low traffic densities also
result in extra running costs (e.g. increases in fuel consumption). As long as
the flow is stable, it seems reasonable to assume that the effect of the flow
on operating costs is reflected by the effect of speed. To obtain running costs
as a function of the flow, the inverse function of average travel time is used,
since travel time is the inverse of speed. However, for flow corresponding to
level of service F, operating costs must increase sharply, as was the case for
travel time. While the effect of flow and capacity is assumed to be reflected
by the effect of speed, this assumption does not hold for surface and terrain;
operating costs are higher in mountainous and unpaved roads than in level and
paved roads, even when speed remains the same.

The formulation of the running costs in Tunisia is based on the data
provided by SETEC (1982 pp. 7 • 10-7 • 16) . Table 6 gives the average running costs
for 1980 in TD/100 KM of an average passenger car in Tunisia, when the speed is
80 KM/H, the terrain is level and the surface is paved and fair. Tables 7 and 8
provide the adjustment factors for the effects of the surface condition and the
terrain, respectively. The running costs (tax excluded) for speeds ranging from
24 KM/H to 112 KM/H are given in Table 9. The Tables need some modifications to
better fit our study. For this purpose, the following assumptions are added:
l)running costs on asphaltic are the same as on treatment; 2)the economical

value of 1 TD in a given year is the same as 1.1 TD in the next year (based on
the inflation rate); 3) taxes in 1990 are the same as in 1980; 4) running costs,
tax excluded, in 1990, at a given speed, are equal to running costs, tax
excluded, in 1980, at the same speed, multiplied by a constant; 5)when flow
exceeds capacity, running costs increase as sharply as travel time.

Let RCTE be the running costs in TD/100 KM, tax excluded, in 1990, at 80
KM/H; RCTE is obtained by multiplying the values of the first four entries of
the first row of Table 6 by (l.l)1 , then multiplying the obtained values by
the corresponding row of Table 7 depending on the surface. The fuel entry also
needs to be multiplied by the corresponding adjustment factor of the terrain
from Table 8; the sum of the calculated values of the components gives RCTE.
Let RCTI be the running costs in TD per 100 KM, tax included, in 1990 at 80
KM/H. Every component of RCTE is multiplied by the corresponding tax, obtained
from the original Table 6, and the sum gives RCTI. The running costs as a
function of the flow are computed from Table 9; after the speed is substituted
by its equivalent travel time, the inverse function of the average travel time
function is applied to convert the travel times into the corresponding flows;
columns with negative flows are discarded. Also, the costs corresponding to
unstable flows are replaced by higher values; the values in the original Table
9 were measured for test speeds and therefore are not applicable to unstable
flows. An adjustment factor, AF, is obtained by dividing RCTE by the entry of
the second row of Table 9 corresponding to the 80 KM/H column. The average
running costs, tax excluded, as a function of the flow are obtained after the
multiplication of the second row of Table 9 by the calculated adjustment factor
AF and the connection of the points. To have the same function with tax
included, we just multiply the costs, tax included, by (RCTI/RCTE).

Figure 6 shows the function of the average running costs, tax excluded, of
the road described above; this function is the basis of the system running
costs functions (Figure 7). In contrast, the cumulative user running costs
function (Figure 9) is based on the average running costs, tax included (Figure
8).
Accident Costs

The costs of accidents include the social costs caused by road accidents of
corporal damages, such as deaths and hospitalization, and material damages to
vehicles and environment. Hence, they are included in the system objective
function, but not in the user objective; the costs are not direct costs for the
individual. The number and severity of accidents depend on many factors, such
as congestion (flow), signalization, width, surface (capacity), illumination,
time (day, night), condition of the car, the driver, and speed. Some of those
factors are related to the decision variables of the model, and hence can be
controlled by the model; but some others are beyond the scope of those vari-
ables because of their independence with flow and capacity.

The number of accidents is usually defined with respect to a unit of length.
Depending on the data available, accidents are classified into different
categories and a function is evaluated to relate the costs of each category to
the causal factors included in the decision variables of the optimization
problem. A natural way to find the relationships is a regression model. Its
coefficient of determination R is not expected to be very high since only the
factors controlled by the optimization problem are included in the regression
model .

The accident data available for this study pertain to 20 regions in Tunisia
comprising for each region the average number of accidents in 1983 (without any
details on the severity), the average flow per day, the average width of paved
roads, the average quality of the surface of the roadway, and the length of the

10

included links (Direction de l'Entretien et de 1 ' Exploitation Routiere 1984
pp. 7-51, and 1982 pp. 46-47 and p. 82). Four independent variables are chosen
(Ben-Ayed 1988 Table 4-14): l)average flow per hour, 2)width of paved roads in
M, 3)surface condition of the roadway, 4)capacity in PCU using the relationship
(2). Surface condition is quantified by introducing a scale measure (10 for
good, 5 for fair and 0 for poor). One observation having an exceptionally high
number of accidents was discarded to avoid misleading results. Based on the
remaining 19 observations, the regression analysis shows that accidents depend
mainly on flow and width. However, those two variables are significantly
correlated (R=.69). Since the number of accidents depends more on flow (R=.88)
than on width (R=.56), the following relationship is retained (Figure 10):

Number of Accidents per 100 KM = .2677(Flow per hour) - 5.6466

the adjusted coefficient of determination R is 76 %.

The insignificant correlation between the number of accidents and the
remaining two variables (quality of roadway surface and capacity) may reflect
that good roads attract more vehicles, which results in more accidents due to
congestion. However, more accurate data that include unpaved roads may give
different results. Nineteen observations are too few to generate a reliable
regression model. Moreover, those observations are averages for each region;
they are not specific to any link of the network.
Improvement and Maintenance Costs

Link improvement has two different aspects; the first is its cost, and the
second is its effect on reducing travel costs. For this reason, the choice of
the improvement cost functions is critical in the model. Unfortunately, no
accurate data are available about improvement costs for Tunisia. Subjective
estimates given by Tollie (1987) and adjusted by Thompson (1987) are used.

The improvements considered in this study do not include adding new arcs,
nor widening the roadway beyond the existing width of the roadway and the
shoulders. This restriction is made to avoid consideration of the costs of land
acquisition and earthwork. Land acquisition costs vary dramatically from one
region to another, but no data are available. The solution of the optimization
problem may suggest further study of some links to investigate the possibility
of adding more lanes or even upgrading the road to a divided highway. In this
study, however, the types of improvements are limited to maintenance costs,
roadway widening, roadway surface improvement, and shoulders surface improve-
ment, which excludes some major periodic costs such as the construction of the
road-bed and bridges.

The costs related to each type of improvement depend on several factors
other than the length of the improved road. The cost of resurfacing per unit of
length, for example, depends on the width of the roadway, the type of the
surface, and the condition of the existing one. For each link, it is necessary
to have one specific improvement cost depending on the specific conditions of
that link. The data needed can be summarized in two tables, one giving the cost
of improving the existing surface (of shoulders or roadway) from the existing
state to any other feasible state, and the other giving the effect of width on
that cost. Widening of the roadway is considered to be an improvement of a
portion of the shoulder, because the widening of the roadway is always made at
the expense of the shoulders. For the same reason, the effect of the terrain is
ignored since the costs of resurfacing are not considerably affected by
terrain.

11

Table 10 gives the costs of possible surface improvements considered in this
study. The costs given in the Table apply if the surface to be improved is at
least 4 M wide. If the width is only .5 M, the cost per M2 is assumed to
double. For widths between .5 and 4 M, a linear interpolation is used. It is
usually required that widening of the roadway be accompanied by resurfacing. To
avoid double counting fixed costs, we assume that the costs of widening and
resurfacing at the same time is 90 % the sum of their costs if done separately.
We also assume that if the existing surface is good and if the new surface is
in the same category (asphaltic, treatment or unpaved), the cost of resurfacing
is 30 % of the cost of upgrading from poor to good in that category.

An ideal improvement cost function for our model is one that gives the cost
of every PCU of added capacity. However, the capacity can be increased in many
ways with different costs and effects on travel costs. Resurfacing the roadway,
for example, may increase the capacity by the same amount as improving the
shoulders, but the two alternatives do not necessarily have the same cost nor
have the same effect on reducing the travel cost. Even for the same improve-
ment, the effect varies from one flow to another. The formulation of the
investment function, therefore, involves serious difficulties because of the
large number of the decision variables, which is equal to the number of
possible improvements, their overlapping, their technical requirements, their
qualitative nature, their dependency on the flow, and their different effect on
travel costs. Following the analysis of the maintenance costs and the ad-
ditivity of the cost functions, a procedure is proposed to formulate implicitly
all details related to each type of improvement and yield the cost and the
effect of each added PCU.

The analysis of the maintenance costs is based on the data provided by SETEC
(1982 pp. 13 • 19-13 • 26) . Those annual costs depend on the type of road (Table
11). Based on the following assumptions, Tables 10 and 11 can be used after
updating the values of the costs to 1990 and deducting the taxes: l)Table 10
applies to Tunisia for the year 1987; 2)taxes on investment and maintenance
costs are 20 % of the total cost (SETEC 1982 p. 13 -13); 3)the data about earth
surface apply to all unpaved roads.
Additivity of the Cost Functions

The upper and lower objective functions for each link are obtained by adding
the components of the system cost functions and the components of the cumula-
tive user cost functions, respectively. However, such an addition is possible
only when the components are expressed in the same units and for the same
period of time. For this study, we choose the unit to be one thousand TD and
the period to be one year. We assume that this study is intended to allocate
the optimal interregional highway investment for a five year period from 1988
to 1992; the year 1990 is assumed to be an average year. The choice of the unit
and the period is not relevant to the model because their change is equivalent
to the multiplication of the objective functions by a positive constant which
does not affect the solution of the optimization problem.

In contrast, the choice of the conversion factors is significant. The value
of time is provided by SETEC (1984 p. 24). This value is estimated to be .250
TD/hour in 1986 with an increase of 2.8 % per year, which gives a value of .279
TD/hour in 1990; however, since the average number of passengers per vehicle in
Tunisia is 4.38 (SETEC 1982 p. 5-8), this value becomes 1.217 TD. For the costs
of accidents, no Tunisian data are found; therefore, the cost per accident in
1985 provided by the National Safety Council (1986 pp. 2-49) for the United
States is applied to Tunisia. To take into account the differences in the
standards of living, we multiply the costs of wage loss, medical expense and
insurance administration (29.3 billions of dollars) by the ratio of the

12

Tunisian gross national product per capita to the U.S. gross national product
per capita (1,420/12,820 according to the World Tables 1986). To convert the
value to 1990 we multiply by (1.028)5 which corresponds to the increase of
salaries in Tunisia during that period (SETEC 1984 p. 24). Then we add the
motor-vehicle property damage (19.3 billions of dollars) multiplied by the
inflation factor (1.1) , and divide the computed total cost by the total number
of accidents in the U.S. in 1985 (19,300,000). We obtain a cost of $ 1,832 or
1,573 TD per accident. The number of accidents in 1990 is assumed to be the
same as in 1983.

The travel time function has units of time per hour because flow is defined
with respect to the hour. To convert those functions to the year, we divide by
. 12, to obtain the travel time per day, as explained in Section 3, then we
multiply by 365. We assume that the flow is uniform during the 365 days of the
year (Direction de l'Entretien et de 1' Exploitation Routiere 1982 p. 74). On the
other side, improvement costs cover a period that is usually much longer than
one year. Let Ci be the actual expenditure in the first year, n the lifetime of
the investment and C the equivalent annual expenditure over the n-year period.
Assuming an instant year, Cn is given by (Morlok 1978 pp. 345-369):

Cn = [iCL+D^J/Kl+i)11-!]

where i is the interest rate. The interest rate retained for Tunisia is 10 %
(SETEC 1982 pp. 15 • 1-15 • 18) . The lifetime of each investment (Table 12) is
assumed to be 1.5 times the period given by SETEC for what they call "period-
ical maintenance costs" (p. 13-25).

Using the above information, the total system travel costs and the total
cumulative user costs for the illustrative link can be obtained (Figures 11 and
12 respectively). As shown by the figures, those functions are basically
composed of two pieces corresponding to stable and unstable flows. This result
was confirmed for all other links of the data.
Piecewise Linear Approximation of the Cost Functions

To have a finite number of possible added widths, we assume that the
widening of the roadway can be done only by adding to the existing width a
multiple of one-half meter, up to the maximum width of the road. Since the
number of all possible states of surface is limited to nine, the total number
of possible improvements of a given road is finite. For the illustrative link,
the roadway can be widened by 0, .5, 1, 1.5, ... up to 5 M (11 possibilities).
The pavement can be either improved to asphaltic-good or treatment -good or kept
as it is; however, if there is widening there must be resurfacing. The shoul-
ders can be left as they are, improved to unpaved-good, or, in case the roadway
is upgraded to asphaltic, they can be improved to treatment-good. This gives a
total number of 54 possible improvements (7 possibilities if the roadway is not
widened, 2 if it is widened by 5 meters, and 45 otherwise). Those improvements,
including the possibility of no improvement, represented by their added
capacities versus their costs, are shown in Figure 13.

For each link, all possible improvement points are enumerated and the cost
for each improvement is evaluated using Tables 11 and 12. Whenever one improve-
ment has a lower cost and a higher added capacity than another improvement, the
latter one is dominated by the first and eliminated. For the illustrative link,
34 possible improvements are dominated and eliminated. The remaining 20 points
are shown in Figure 16. For each of the possible and non-dominated improve-
ments, new travel cost functions are obtained, as shown by Figures 14 and 15.
Those figures confirm that only two pieces have to be considered with the
breakpoints at the capacity level.

13

To linearize the above functions, piecewise linear approximation is used.
For the improvement cost functions, we assume a maximum of three pieces; each
piece is obtained by using linear regression and the best approximation is
chosen to be the one that minimizes the error, defined as the sum of the
squares of the differences between the actual costs and the approximated costs.
In order to ensure that we get the best approximation, we take all possible
combinations. Every segment is the best linear fit of an ordered set of points
where the ending point could be any point that exceeds the ending point of the
set of the previous segment, and the starting point could be any point preced-
ing its own ending point.

There are two special cases; the set of the first segment must start with
the 0 improvement point and that of the third segment must end with the last
point, the most expensive improvement. It is required that the approximated
cost given by the first segment at zero improvement be nonnegative and no
greater than twice the actual cost; when this condition is not satisfied for a
given approximation, the exact value of that point is imposed. For each of the
112 links of the study, the best approximation consists of a three-piece
nonconvex function, thereby requiring BLP formulation for all 112 links and
introducing a great complexity to the problem to be solved. The other alterna-
tive, which is the convex and/or linear formulation, is much more efficient
from a computational point of view, but is often much less accurate; the best
convex formulation increases the error for 10.71 % of the links by more than 12
times as compared to the nonconvex approximation. Fortunately, there are other
links for which the difference is small enough to allow convex approximation.

In dealing with such a tradeoff between accuracy and computational efficien-
cy, we decided to use concave approximation only when this latter decreases the
error by more than 50 % as compared to convex approximation. This restriction
permitted the number of nonconvex improvement cost functions to be reduced to
36 (all 36 are three-piece nonconvex-nonconcave) ; the remaining 76 consist of 8
linear and 68 two-piece convex. For our illustrative link, the best approxima-
tion is three-piece nonconvex-nonconcave (Figure 16); this approximation was
selected after considering 16,816 combinations.

With regard to the total travel cost functions, a unique piece is involved
when the flow is stable. Since the costs are defined in our case by break-
points, their approximation is obtained by applying linear regression, with
zero intercept, to all breakpoints corresponding to stable flow for all
possible and non-dominated improvements. Figures 17 and 18 show the plots of
those points and their approximations for the illustrative link. The effect of
the added capacity on the travel cost is to shift the breakpoint separating
stable and unstable flows.

To obtain the approximation of the total travel costs for unstable flow, we
have to take into account two facts; l)the costs depend on the flow X and the
added capacity Z; 2)the points to be considered are the ones at levels E and F
for all possible and non-dominated improvements. Let eg and Ci be the slopes of
the (system or cumulative user) total travel costs at stable and unstable
flows, respectively, and d^ the intercept at unstable flow. Let X-g be the flow
at LOS E before improvement and Xg+Z the flow at LOS E after improvement. We
have:

Decrease in intercept = c-^Xjr + Z) + d-^ - cQ(XE + Z) = (c^ - cQ)Z

because c-^Xg + d^ = CgX^. The total travel cost function T is formulated as a
piecewise linear function:

14

MIN T
such that:

T> c0X
- (c1 - c0)Z + d1.

Let us call Zj one possible improvement, X^ the flow at the new capacity (Xg^)
and/or beyond the new capacity (Xp^), and T^ the corresponding travel cost. As
for stable flow, by enumerating all possible Z^ an accurate linear approxima-
tion of the travel cost at unstable flow can be obtained by using regression
analysis to obtain the parameters c^ and d^ of the following relationship:

Ti = cl<Xi " Z0 + (c0Zi + di>-

A simpler way would take one specific value of Zj, such as the one correspond-
ing to the existing situation (added capacity equal to zero) and find the line
that connects the two points (Xgg, Tpg) and (Xpg, Tj?q); c-^ is assumed to be the
same for any improvement (see Figures 14 and 15) and d^ varies linearly with Z
as shown above. In our case, assuming an unstable flow caused by a flow 10 %
larger than capacity, the following linear approximations are obtained for the
travel costs at unstable flow:

System: 3,708.94X - 5,049,167.84
User: 308. 22X - 387,532.36

Another way to deal with the total travel costs at unstable flow is to
eliminate them by imposing strict capacities:

such that:
X < Existing Capacity + Z

which means that instead of assigning an arbitrarily high cost for unstable
flow, this flow is simply not allowed in the model. Such a simplification is
not always possible; sometimes it causes infeasibility, specifically when the
number of travellers to be carried from all origins to all destinations is
higher than the sum of the capacities after improvement of all links.

6- THE CONSTRAINTS

The constraints treated in the previous section are needed just to complete
the formulation of the objective functions. In this section, different types of
constraints are considered.
The Conservation of Flow Conditions

One way to state the conservation of flow conditions is:

^"reRod Xr od = uod» ^or eacn origin-destination pair od (3)

where RQ(j is the set of all routes r going from origin-node o to destination
node d, Xr ocj is the flow of passengers (per unit time) from o to d using route
r, and, uQj is an element of the trip-matrix giving the required number of
vehicle trips (per unit time) from o to d.

An equivalent formulation of those conditions is:

for each destination d and each node n other than d:

(4)

EaeAn Xad " EaeBn Xad = und

15

where Xa(j is the flow on link a with destination d, and, un(j is the required
number of trips between node n and destination d.

A choice has to be made between relationship (3) and relationship (4) in
order to minimize the numbers of constraints and variables involved in the
formulation of the conservation of flow conditions. Since the network consists
of 19 origin-destination nodes, 39 intermediate nodes and 224 directed links,
relationship (4) requires 4,256 variables (19 times 224) and 1,083 equality
constraints (19 times 57). Relationship (3), however, requires at most 342
equality constraints (19 times 18), but many more variables. Besides its fewer
number of constraints, the latter relationship has a very important advantage,
as compared to the first one; the numbers of variables and constraints can be
considerably decreased as there are origin-destination pairs with zero entries
in the trip matrix. If an origin-destination pair has a zero entry in the trip
matrix, it means that it does not belong to the set of od pairs; therefore
there is no reason to have any variable or constraint associated with it.

In attempting to test the efficiency of such a property in the use of
relationship (3), we had to limit the number of variables. The following three
assumptions are made: 1) every traveller going from origin o to destination d
chooses his route among the 100 first shortest routes from o to d, 2) no
traveller chooses a route where there is a node visited more than once, 3) no
traveller chooses a route that is more than twice as long as the shortest
route. Based on those assumptions, for every origin-destination pair, the 100
shortest paths are computed, then all routes with nodes visited more than once
and all routes with length more than twice that of the first shortest path are
excluded. Using the data provided by Table 1 (columns 2, 3 and 4) after its
modification to include directed links, the number of variables was limited to
11,900. The computation of those routes is based on Shier' s Double-Sweep Method
(1974).

SETEC (1982 pp.5- 9-6-1) provided a 29 by 29 trip matrix for 1977 and
predicted numbers for 1986. We retained the same rates of increase to find the
predicted numbers of required trips between each origin-destination pair for
1990. Some subregions had to be grouped to obtain the 19 by 19 trip matrix;
flows between subregions belonging to the same region were discarded. The
entries of the matrix are converted into average annual trips per hour (in PCU)
to be consistent with the definition of the flow. The trip matrix obtained is
shown in Table 13. All origin nodes are also destination nodes (refer to them
as origin-destination nodes), which explains the symmetry of the trip matrix in
Table 13. Among the 342 entries of the Table, 24 have a value of zero which
means that the 342 constraints required by relationship (3) can be decreased to
318. Among the 11,900 variables, 1006, corresponding to those 24 od pairs with
zero entry, are redundant, thereby decreasing the number of variables to
10,894. Those numbers can be decreased by much more when the following two
facts are recognized.

First, in many cases all trips from origin o to destination d have to go
through a third origin-destination node x. In such a case, the trip matrix can
be modified to include zero trips from o to d. Call t, m and n the required
numbers of trips from o to d, o to x, and, x to d, respectively; if all routes
from o to d include the node x, then it is equivalent to say that m+t are
required to go from o to x, n+t are required to go from x to d, and zero trips
are required to go from o to d. Applying this fact to the trip matrix shown in
Table 13, the number of entries with zero value is increased to 102 which
decreases the number of od constraints to 240 and the number of routes to
7,655.

16

The second fact is even more important; it applies only to two- lane highways
for which all objective functions depend on the sum of the flows in both direc-
tions. Since the trip matrix is symmetrical, we kept the directional split
constant; the cost is the same if we consider 2t trips going from o to d and
zero trips from d to o, instead of t trips from o to d and t trips from d to o.
Also, because of the symmetry of the trip matrix, the conservation of flow
conditions are still satisfied if the entries of the upper right triangle of
the matrix are changed to zero, and the values of the entries of the lower left
triangle are multiplied by two. This fact, by itself, increases the number of
zero entries to 183.

When both facts are used, the number of zero entries becomes 222 (Table 14),
yielding 3,824 variables and 120 constraints. Those numbers clearly dominate
those obtained by relationship (4), namely 4,256 for the variables and 1,083
for the constraints. Therefore, for our case, relationship (3) is used for the
formulation of the conservation of flow conditions. Furthermore, many od pairs
are far away from each other, which results in a large number of routes and a
small number of required trips between the od pairs. In other words, those
pairs are introducing a huge number of variables that can be discarded without
having a considerable effect on the problem. For this purpose, we limit the
number of routes corresponding to each od pair to twice the number of required
trips between the nodes of that pair. This limitation allows the elimination of
1,729 more routes leaving a final number of flow variables equal to 2,095.
Intra-Regional Flow Effect

The links included in the study are used by inter-regional flow as well as
by intra-regional flow. Intra-regional flow includes all trips between inter-
mediate nodes or between any other places inside the regions. Those flows have
to be considered by the model because of their effect in congesting the roads
and thereby increasing the travel costs to the inter-regional flow. A con-
venient way to include intra-regional flows is to assume that they reduce the
capacity of the road used by the interregional flow. Assuming that the intra-
regional flow is 40 % of the existing capacity, when strict capacity is used
the constraint Xa < kfl, where ka is the existing capacity of a, is replaced by
Xfl < -6ka. For the case of nonstrict capacity, we substitute (Xfl+.4ka) in the
objective functions for Xa, and we subtract the constant cost of -4ka:

ca * cla

MIN (Ca -
Ca * c0a(XJ

4c0a>

4k J

<xa +

4kfl) - (c

la

"a
" c0a

>za + dla-

7- FINAL FORMULATION OF THE PROBLEM

The empirical analysis described above results in the following final
formulation:

MIN

Za

where {Xfl, C,

Za=l,N

la=l N KCa"-4c0aka) +

+ *m=l,Ma(bm+l,a~bma)Wma
c. w
-a» wma

(blaza+b0a

a=l', 112, m=l,Ma} and {Yr, r=l,2095} solve:

MIN *a=l,N *Ca + Im=1)Ma Wma}
subject to:

mammal * 6
for each origin-destination pair od:

*blaza + l

- la b

a u0a

'rcRod

Yr " uod

Yr > 0, for all reRod
for each link a:

a " Er=l,2095 6arYr = °

(5)

17

Ca > c0a(Xa + .4ka)

ca * cla<xa + -4ka) " ^cla " <Wza + dla
Ca > c0a(Xa + .4ka)

Ca * ^la^a + -4ka) " Ccla - cQa)Za + dla

wma " za * -%a ra=1>Ma

Za * <*3a

za> Xa> Ca> £&> Wma * ° m=1>Ma

where N is the number of links in the network, Cga and c-^a are the slopes of
the system travel cost at stable and unstable flows, respectively; Cq3 and c^a
are the slopes of the cumulative user travel cost at stable and unstable flows,
respectively; d^a and d^a are the intercepts of the travel cost at unstable
flow of the system and the cumulative user, respectively; Mfl is the number of
breakpoints in the improvement cost function of link a; Ma is 0 when the curve
is linear, 1 when the curve has 2 pieces and 2 when it has 3 pieces; bga is the
intercept of the first piece of the improvement cost function on link a, bma is
the slope of the piece delimited by qm_^ a and qma, m=l,Ma+l, qga being equal
to zero and qvja+1 equal to q3a, the maximum improvement allowed by the model;
ka is the existing capacity of link a, Xa is the flow on link a, Ca is the
system total travel cost on link a, Ca is the cumulative user total travel cost
on link a, Za is the PCU added to the capacity of link a, Wma is the maximum of
(Za~qma) and 0, Y_ is the flow on route r, 6 is the amount of budget available,
RQ(j is the set of all routes from origin o to destination d, u_j are the
entries of the trip matrix, 5ar is binary number equal to 1 when link a belongs
to route r, and equal to 0 otherwise.

The values of the coefficients of the above formulation are provided by
Tables 5-1, 5-2, 5-3 and Appendix C in Ben-Ayed 1988. More details about the
formulation and the data can be found in the same reference.

8- THE SOLUTION OF THE EMPIRICAL PROBLEM

An algorithm based on the structure of the empirical problem formulated
above is described by Ben-Ayed, Blair and Boyce (1988). There are two reasons
for having a BLP formulation in (5); first the user-optimized flow requirement
(user-equilibrium), and second the nonconvex improvement functions. The
algorithm deals with each of the two lower problems separately; at each
iteration we try to find a better compromise with the user, while including the
smallest possible number of nonconvex improvement functions to get the exact
solution with the minimum computation effort. The algorithm is an iterative
procedure that tries at each iteration to reduce the gap between ideal solution
and incumbent solution. The procedure terminates when the gap is brought below
a desired accuracy value, or when the number of iterations exceeds a fixed
limit. About 15.25 minutes CPU time and 1.4 million words (64 bits per word)
computing storage space were required to solve the problem; the computation was
conducted on the supercomputer CRAY X-MP/24 of the National Center for Super-
computing Applications at the University of Illinois at Urbana-Champaign. A
fairly accurate solution, with a gap between upper and lower bounds decreased
to as low as 2.56 %, was obtained despite the complexity involved in the
problem (see Ben-Ayed and Blair 1988 for a discussion on the computational
difficulties of BLP). The complete presentation of the solution is provided in
Appendix E of Ben-Ayed (1988).

The links to be improved in this solution are shown on the map in Figure 19.
Almost all improvements are on the roads connecting Tunis, the capital, to its
major neighboring cities. This result can be intuitively predicted by examining
the trip matrix; the trips originating or ending in Tunis are 56 % of all the

18

trips of the matrix. A similar recommendation was made by SETEC (1982 pp. 6-8)
stating that the roads corresponding to the exits of Tunis will be highly
congested by the year 2000 if no improvements are made. In contrast, the
entries of the trip matrix corresponding to regions in the south are very low,
which results in no improvement even for unpaved roads.

Table 15 gives for each link to be improved the interregional flow, the
existing capacity available to this flow (60 % of the total existing capacity),
the added capacity, its cost and the maximum added capacity allowed by the
formulation. The improvement required for link 14 is very small; a slight
improvement of the surface of this link gives it exactly the same capacity as
the adjacent link 79 which does not need improvement although it is closer to
the capital. All other improvements are more significant and three of them,
namely those on links 3, 20 and 26, require the maximum added capacity allowed
by the formulation. For each of the links the flow is higher than the new
capacity; more detailed study is needed to include the possibility of upgrading
them to divided four-lane highways. Link 90 is also congested; however, the
solution for the system does not add more capacity although it has the pos-
sibility to do so. The reason is that the congestion on those roads is less
expensive than the addition of more capacity.

An analysis of the results obtained (Ben-Ayed 1988) draws the attention to
several possible improvements of the empirical formulation. First, the travel
times at the different levels of service A to E are so close, according to the
HCM, that the resulting system and cumulative user costs at stable flow turned
out to be one-piece linear functions that do not depend on the added capacity.
The only instrument in the model for the system to influence the user's choice
of the routes is by adding capacity if flow is unstable; therefore, the ability
of the system to affect the user-optimized equilibrium is almost negligible.
More detailed empirical data about travel costs are needed to represent the
effects of congestion on user costs.

Second, the data about land purchase should be included in the study. Their
unavailability meant that new links could not be considered and restricted
investments to improvement of existing links without allowing the added width
to go beyond the existing shoulders. This limitation resulted in low improve-
ment costs. It can be seen from Table 15 that improvement costs are about fifty
times smaller than travel costs. The introduction of the sophisticated BLP
formulation of the investment costs did not give much saving as compared to the
simpler LP formulation because the costs are already low according to the data
of the problem.

9- CONCLUSIONS

This paper is an attempt to go beyond theoretical formulations and the small
illustrative examples to much more interesting real world problems. The study
was devoted to the construction of a Bilevel Linear Programming formulation, a
major step in the formal optimization of the inter-regional highway network of
a developing country. The Tunisian case study gave an illustration for the
application of some advanced operations research techniques, such as Bilevel
Linear Programming, in real situations.

The reliability of any formulation is conditioned by the realism of the
formulation and the tractability of the resulting problem to be solved. The
problem formulated in this paper has been shown to be tractable from the
computational point of view (Ben-Ayed 1988 and Ben-Ayed, Blair and Boyce 1988).
The complexity of the formulation does not present a barrier to solving the
problem. However, the refinement of the formulation and the success to solving
the resulting optimization problem do not necessarily guarantee the credibility

19

of the solution. The most important dilemma is the availability of the data.
Careful and detailed theoretical and empirical studies are needed to give more
representative data, including better travel cost functions and better improve-
ment cost functions for two- lane and unpaved highways.

Finally, our fixed demand, user-equilibrium route choice formulation is
somewhat artificial. A further study could include stochastic route choice and
estimation of travel demand. Moreover, transportation improvements often have a
considerable impact on regional location decisions, potentially implying income
redistribution effects of considerable importance. It is therefore hardly
surprising that motives of income redistribution have a way of appearing
implicitly or explicitly in the rationale for many public transportation
investments (Meyer and Straszheim 1971). In fact, transportation investments
can result directly in improved productivity and expanded employment over the
long run; transportation infrastructure can affect ways in which regions and
communities develop (National Transportation Policy Commission 1979). There-
fore, the study could be expanded to optimize societal objectives such as a
more balanced economic growth among the regions. One simple way to include
those concepts in the optimization model is to extend the same problem we
solved, modifying it to introduce higher trip matrix entries to the less
developed regions, so that more budget is allocated to the roads in those
regions in order to help activate their development.

REFERENCES

The American University (1979) Tunisia: A Country Study, Washington, DC.

The Army Map Service (NSPE) (1957) Gagliari-Tunis (NJ-32), Sfax (NI-32), and
Gadames (NH-32), Series 1301, Corps of Engineers, U.S. Army, Washington, DC.

Bank of America Global Trading, London (1987) World Value of the Dollar, The
Wall Street Journal, LXIX, 18, 24.

Bard J. F. (1983) An Efficient Point Algorithm for a Linear Two-Stage Optimiz-
ation Problem, Operations Research 31, 670-684.

Ben-Ayed 0. (1988) Bilevel Linear Programming: Analysis and Application to the
Network Design Problem, Ph.D. Thesis, University of Illinois, Urbana-
Champaign, IL.

Ben-Ayed 0. and C. E. Blair (1988) Computational Difficulties of Bilevel Linear
Programming, Submitted to Operations Research.

Ben-Ayed 0., Boyce D. E. and Blair C. E. (1988) A General Bilevel Linear
Programming of the Network Design Problem, Transportation Research B22.

Ben-Ayed 0., Blair C. E. and Boyce D. E. (1988) Solving a Real World Highway
Network Design Problem Using Bilevel Linear Programming, submitted to
Operations Research.

Bialas W. F. and Karwan M. H. (1982) On Two-Level Optimization, IEEE Trans-
action on Automatic Control AC-27, 1, 211-214.

Bialas W. F. and Karwan M. H. (1984) Two-Level Linear Programming, Management
Science 30, 8, 1004-1020.

Direction de l'Entretien et de 1 ' Exploitation Routiere (1982) Recensement
General de la Circulation: Annee 1982, Republique Tunisienne, Ministere de
l'Equipement et de l' Habitat, Direction Generale des Ponts et Chausees.

Direction de l'Entretien et de 1 ' Exploitation Routiere (1984) Infrastructure Du
Reseau Routier: Donnees Statistiques au 1-1-84, Republique Tunisienne,
Ministere de l'Equipement et de l' Habitat, Direction Generale des Ponts et
Chaussees .

Embassy of Tunisia in Washington (1987) Tunisia.

20

Institut National de la Statistique (1984) Recensement General de la Population

et de 1' Habitat, Volume 1, Republique Tunisienne, Ministere du Plan.
LeBlanc L. J. and Boyce D. E. (1986) A Bilevel Programming Algorithm for Exact

Solution of the Network Design Problem with User-Optimal Flows, Transport-
ation Research 20B, 259-265.
Meyer J. R. and Straszheim M. R. (1971) Techniques of Transportation Planning,

Volume 1: Pricing and Project Evaluation, The Brookings Institutions,

Washington DC.
Morlok E. K. (1978) Introduction to Transport at ion Engineering and Planning,

McGraw-Hill, New York.
Moyer R. A. and Winfrey R. (1949) Cost of Operating Rural-Mail-Carrier Motor

Vehicles on Pavement, Gravel, and Earth, The Iowa State College Bulletin,

143.
National Safety Council (1986) Accidents Facts, Chicago.
National Transportation Policy Commission (1979) Economic Development and Land

Use, National Transport at ion Policies Through The Year 2000. Final Report.
Republique Tunisienne (1987) VII EME Plan de Developpement Economique et Social

( 1987-1991) , Le Contenu Sectoriel (Tome 2), Troisieme Partie (Les Ind-
ustries Non Manufacturieres) , Imprimerie du Ministere du Plan, Tunis.
SETEC Economie et S0TINF0R (1982) Plan Directeur Routier, Rapport General Tomes

1 et 2, Republique Tunisienne, Ministere de 1 'Equipement , Direction des

Ponts et Chausees, Sous-Direction des Etudes.
SETEC International et SOTUETEC-SOTINFOR (1984) Etude de l'Entretien Routier,

Cout de Fonc t ionnemen t des Vehicules, Rapport N° 8, Republique Tunisienne,

Ministere de 1* Equipement , Direction des Ponts et Chausees.
Shier D. R. (1974) Computational Experience with an Algorithm for Finding the K

Shortest Paths in a Network, Journal of Research of the National Bureau of

Standards, Mathematical Sciences, 78B, 3, 139-165.
Steenbrink P. A. (1974) Optimization of Transport Networks , Wiley, New York.
Thompson M. R. (1987) (Professor of Transportation Facilities, Department of

Civil Engineering, University of Illinois at Urbana-Champaign) Personal

discussion.
Tollie J. (1987) (Highway Engineer, The World Bank) Personal Communication.
Transportation Research Board (1985) Highway Capacity Manual, Special Report

209, National Research Council, Washington D.C.
Wohl M. and Martin B. V. (1967) Traffic System Analysis, MacGraw-Hill, New

York.
World Bank (1983) World Tables, Volumes 1 and 2, from the Data Files of the

World Bank, The Johns Hopkins University Press, Baltimore and London.

21

I i nk from to
number node node

ength terrain roadway shoulders roadway
(km) (1,2,3) width(m) width (m) surf ace( 1-9)

1

2

65

2

20

65

3

23

37

4

24

23

5

25

31

6

26

53

7

2

20

37

8

3

20

64

9

3

21

38

10

3

28

47

11

3

29

37

12

3

31

22

13

4

5

47

14

4

29

68

15

4

33

60

16

4

48

52

17

4

49

59

18

5

30

24

19

5

31

23

20

6

23

30

21

6

27

14

22

7

25

28

23

7

26

13

24

7

32

27

25

7

35

41

26

8

10

23

27

8

1 1

54

28

8

35

44

29

8

38

31

30

8

41

12

31

8

39

26

32

9

14

104

33

9

39

25

34

9

40

41

35

10

39

21

36

10

41

25

37

1 1

12

93

38

1 1

37

80

39

1 1

38

36

40

1 1

44

24

41

1 1

47

17

42

12

29

51

43

12

32

67

44

12

33

34

45

13

16

112

46

13

34

27

47

13

49

66

48

14

40

62

49

14

42

82

50

14

43

75

51

14

50

61

52

14

58

69

53

15

46

16

54

15

51

55

55

15

55

19

56

15

56

23

57

16

17

143

58

16

19

97

59

16

51

77

60

16

56

66

61

17

18

77

62

17

42

51

63

17

52

125

64

17

53

42

65

18

53

73

66

19

52

99

67

20

21

70

68

20

24

48

69

21

22

34

70

22

30

43

71

23

27

26

72

24

25

22

73

24

28

34

74

25

28

35

75

25

32

29

76

26

27

29

77

26

36

18

8,
7,
10,
7
7,
6,
6,
6,
4,
6,
4.
6,

6.5
6.5
6.5
6.5
4.5
6.5

10.0
7.0
8.0
6.5
8.0
6.5
4.5
4.5
4.5
6.5
6.5
4.5
6.5

6.5
6.5

6.5
5.5
5.5

10.0
4.0

5.

5.
5.
5.
5.
5.
5.
5.
7.
5.
7.
5.
5.
5.
5.
5.
7.
5.
5.
5.
5.
7.
6.
7.
7.
5.
5.
5.
5.
5.
5.
7.
7.
7.
5.
5.
7.
5.
5.
5.
5.
6.
5.
5.
5.
5.
5.
5.
5.
5.
5.
6.
6.
7.
6.
6.
5.
5.
5.
5.
5.
5.
5.
7.
0
7.
5.
6.
5.
5.
5.
6.
5.
5.
5.
5.
5.

shou I ders
surf ace(4-9!

8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8

Table 1 Definition of Links

22

I i nk from to
number node node

ength terrain roadway shoulders roadway shoulders
(km) (1,2,3) width(m) width (m) surface(1-9) surf ace ( 4-9)

78

27

36

16

79

28

29

43

80

28

32

45

81

29

31

38

82

30

31

37

83

32

35

58

84

32

37

28

85

33

44

58

86

33

48

25

87

34

45

28

88

34

46

23

89

34

48

66

90

35

36

21

91

35

38

24

92

37

38

41

93

39

40

41

94

39

41

47

95

40

41

52

96

40

58

48

97

42

50

71

98

42

57

42

99

43

50

16

100

43

54

38

101

43

55

36

102

44

45

54

103

44

47

19

104

45

46

22

105

46

56

29

106

47

54

17

107

47

55

69

108

48

49

35

109

50

57

32

no

51

57

24

111

52

53

81

112

54

58

33

7.5

6.5

4.5

4.0

4.0

4.0

6.5

5.5

6.5

4.0

6.5

4.0

8.0

7.0

10.0

4.5

5.0

8.0

5.5

10.0

10.0

10.0

4.5

6.5

6.5

4.0

6.5

6.5

6.5

10.0

10.0

4.5

4.5

10.0

5.5

5.

5.

7.

7.

7.

7.

5.

6.

5.

7.

6.

5.

5.

5.
0

7.

6.

5.

6.
0
0
0

7.

5.

5.

7.

5.

5.

5.
0
0

7.

7.
0

6.

1

b

I

6
4
4
5
5
4

4
1

4
8
5
4
1
5
3
8
8
5
5
5
5
5
5
5
8
8
5
5
8
5

Table 1 (Continued) Definition of Links

23

Figure 1 Tunisian Inter-Regional Highway Network

24

Flow

420 756 1204 1792

Figure 2 Average Travel Time Function

2800

Maximum Ratios R- of Flow to Ideal Capacity (Both Directions)

Flow (LOS)

0 FLOW

LOS A

LOS B

LOS C

LOS D

LOS E

Average Speed

in KM/H
Ratio Ri

Level Terrain

95
0

92
.12

87
.24

82
.39

79
.62

71
1.00

Average Speed

in KM/H
Ratio Ri

Rolling Terrain

90
0

86
.07

81
. 19

77
.35

74
.52

60
.92

Average Speed

in KM/H
Ratio Ri

Mountainous Terrain

75
0

70
.04

68
. 13

61
.23

56

.40

44
.82

Table 2

25

Adjustment Factors W for the Combined Effect of

Roadway and Shoulder Width

Width in

Width in Meters of Both Lane;

Meters

of Both

10.0

7.5

7.0

6

0

Usable
Shoul-

LOS LOS

LOS LOS

LOS LOS

LOS

LOS

ders

A-D E

A-D E

A-D E

A-D

E

> 4.0

1.28 1.28

1.02 1.02

.97 .97

.82

.85

2.5

1.20 1.25

.94 .99

.89 .95

.75

.83

1.0

1.04 1.19

.81 .94

.76 .89

.65

.78

0

1.00 1.10

.72 .90

.67 .85

.57

.74

Width in

Width in Meters of Both Lanes

Meters
of Both

5.5

5.0

4.5

4

0

Usable
Shoul-

LOS LOS

LOS LOS

LOS LOS

LOS

LOS

ders

A-D E

A-D E

A-D E

A-D

E

> 7.0

.70 .76

.65 .71

.60 .66

.54

.60

4.0

.70 .76

.62 .70

.53 .62

.42

.53

2.5

.66 .74

.58 .68

.48 .60

.38

.52

1.0

.56 .70

.50 .63

.41 .55

.32

.47

0

.49 .66

.43 0.59

.36 .52

.28

.43

Table 3

Adjustment Factors P for the Surface of the Roadway

Quality

Good

Fair

Poor

Asphaltic

1.0

.8

.5

Treatment

.9

.7

.4

Unpaved

.5

.4

.2

Table 4

26

1 1 3

1.65

. , r— 1 -

^1.55

!

r

O

2».«

-

I_

i

<D

^_^_-- —

^1.35

^^~^^^

00

^

1_

^

D

^ —

° 1.25

"

1.15

^^^^

^^-^^ AVERAGE TRAVEL TIME

1.05

~~^^"^ ..iii,

200

400 600

Flow per Hour

800 1000

n Both Directions

ieoo

1380

Figure 3

2500

eooo -

o

1500

CD

a.

1000

ZD

o

500

200 400 600 800 1000

Flow per Hour in Both Directions

ieoo

1380

Figure 4

2320

2100

1800

27

o

o

isoo

1200

l_

Q.

co 900

i_

O

z: 6oo

300

CUMULATIVE USER
TRAVEL TIME

200

*00 600 500 1000 1200

Flow per Hour in Both DirecTions

1 4CC

4.6-

Figure 5

3.2

AVERAGE RUNNING COSTS
TAX EXCLUDED

eoo 4oo 6oo ooo 1000

Flow per Hour in Both Directions

Figure 6

leoo

28

Adjustment Factors S for the Quality of the Shoulders

Shoulders Quality

Treatment
Good

Treatment
Poor

Unpaved
Good

Unpaved
Poor

> 4 M width shoulders

1.00

.95

.97

.90

0 M width shoulders

1.00

1.00

1.00

1.00

Table 5

Average Running Costs in TD per 100 KM for 1980

Tax

Fuel

Grease-Oil

Tires

Depreciation

Total

Excluded
Included

.8623
1.7500

.0299
.0447

.1503
.2322

.4139
.4967

1.4564
2.5236

Table 6

Adjustment Factors :

for the
on the

Effect of the !
Running Costs

state of 1

bhe Surface

State of the Surface

Fuel

Grease-Oil

Tires

Depreciation

Paved and Good

.96

.94

.92

.80

Paved and Fair

1.00

1.00

1.00

1.00

Paved and Poor

1.04

1.06

1.08

1.20

Unpaved and Good

1.20

1.11

2.41

1.40

Unpaved and Fair

1.26

1.25

3.73

1.68

Unpaved and Poor

1.37

1.39

5.06

1.96

Table 7

Adjustment Factors for the Effect of the Terrain
on the Fuel Consumption

Terrain

Level

Rolling

Mountainous

Adjustment

1.000

1.022

1.041

Table 8

29

6000 r

400 600 BOO 1000

Flow per Hour in Both Directions
Figure 7

ieoo

1390

e.-t

7.9

7.4

O

o

V5
Q.

6.9

to

O 6.4

C

<5

5.9

5.4

AVERAGE RUNNING COSTS
TAX INCLUDED

e00 400 600 600 1000

^low per Hour in Both Directions
Figure 8

ieoo

1390

30

Running Costs (Tax Excluded in TD per 100 KM) as a Function
of the Speed in KM/H for 1980

Speed

24

32

40

48

56

64

Cost

1.241

1.204

1.148

1.174

1.200

1.291

Speed

72

80

86

96

104

112

Cost

1.344

1.456

1.551

1.717

1.903

2.241

Table 9

Costs (Tax Included) of Surface Improvement in TD per M

Existing Surface

Asphaltic
Good

Treatment
Good

Unpaved
Good

Asphaltic-Fair

6.0

-

-

Asphaltic-Poor

9.0

-

-

Treatment -Good

9.5

-

-

Treatment -Poor

11.0

5.5

-

Unpaved-Good

12.0

6.5

-

Unpaved-Poor

13.0

7.5

2.5

Table 10

15000

12500

10000

o
o

Q.

(/I

7500

O 5000

i5

2500

31

/

CUMULATIVE USER
RUNNING COSTS

eoo

400 600 800 1 COO 1 200

Flow per Hour in Both Directions
Figure 9

1100

1 600

210

100

200 300 400 500 600

Flow per Hour in Both Directions
Figure 10

700

800

32

Annual Fixed Maintenance Costs in TD per KM for 1981

Type of Road

Earth

Paved 4-5 M

Paved 6-7 M

Paved 9-10M

Annual Costs

120

220

260

330

Table 11

Lifetime of Investment

Type of Road

Earth

Treatment

Asphaltic

Lifetime (Years)

7.5

10.5

18

Table 12

33

35000

30000

O
O

25000

^20000
O

c

Q 15000

W 10000

c
o
(/I

^ 5000

o

0 -
0

SYSTEM TOTAL

TRAVEL COSTS

DURING THE YEAR

200 400 600 800 1000

Flow per hour in Both Directions

1200

id 9 0

Figure 11

80000

70000

o
o

'60000

Q.

"S0000
</)

o

C 40000

30000

20000

CUMULATIVE USER

TOTAL COSTS
DURING THE YEAR

250

500 750 1000 1250

Flow per Hour in Both Directions

1500

750

Figure 12

34

2000

o

Q.

.„ 12C0

O

c

aoo -

t/i

<Z

O 400

o

250

500 750 1000

Added Capacity in PCI)
Figure 13

1250

-

!

i

O

m

o

■ B " "

- 4
-

-

.

-

a
a

m

s
a

■

B c » ■ .

D

* ■

-

a

-

a

IMPROVEMENT COSTS

■

5000C

SYSTEM TRAVEL

ANNUAL COSTS FOR

DIFFERENT IMPROVEMENTS

500

iooo 1500 eooo

Flow per Hour in Both Directions

2500

E670

Figure 14

35

DUUUU

70000

' / ' i IJ/Z/M^-

O
O

/ 1 J ///s?0^

■"""•eoooo

II / ////^^

// ///^^

50000

1 //>y^

OT

o

C 40000

f^y^

Q

j£s^

«*■ 30000

o

<^^

00

^^

^ 20000

^^^

o

"1

^^ CUMULATIVE USER

o ioooo

>^ ANNUAL COSTS FOR

^

^^ DIFFERENT IMPROVEMENTS

0

s^ , . , , ,

400

800 ieoo i6oo eooo e4oo

Flow per Hour in Both Directions

eooo

3eoo

Figure 15

2000

250

500 750 1( 00

Added Capacity in PCU
Figure 16

1 250

1500

36

45000

O37500

o

03 30000
Q.

a

C22S00

SYSTEM TRAVEL COSTS
DURING THE YEAR
FOR STABLE FLOW

300 1000

Flow per Hour

1500 eooo

n Both Directions

esoo

2830

Figure 17

70000

o
o

60000

1_

50000

(V

a.

1_

•40000

a

c

Q

30000

LO

20000

■a

c
o

3 10000

CUMULATIVE USER COSTS
DURING THE YEAR
FOR STABLE FLOW

500 1000 1500 2000

Flow per Hour in Both Directions

esoo

s**

2530

Figure 18

37

10

1

916

491

146

419

1330

116

361

67

■"00

2

915

51

7

8

60

28

22

3

15

3

491

51

25

40

28

15

8

3

8

4

146

7

25

49

4

3

9

3

9

5

419

8

40

49

13

5

4

2

2

6

1330

60

28

4

13

20

50

6

29

7

116

28

15

3

5

20

18

6

16

8

361

22

8

9

4

50

18

91

1409

9

67

3

3

3

2

6

6

91

162

10

100

15

8

9

2

29

16

1409

162

11

86

1

3

9

4

15

17

183

24

22

12

62

2

22

35

2

4

12

1 1

3

15

13

24

3

4

37

2

4

1

8

4

5

14

251

23

3

6

5

33

5

67

170

31

15

9

0

2

1

1

1

1

6

5

2

16

14

1

1

1

2

1

2

2

2

1

17

48

2

4

1

2

3

1

12

5

3

18

15

1

0

0

0

0

0

2

1

1

19

16

0

1

1

1

1

1

1

1

1

tota

4471

1143

709

346

561

1602 267

2264

558

1831

1 1

12

13

14

15

16

17

18

19

tota I

1

86

62

24

251

9

14

48

15

16

4471

2

1

2

3

23

0

1

2

1

0

1143

3

3

22

4

3

2

1

4

0

709

4

9

35

37

6

1

1

1

0

346

5

4

2

2

5

1

2

2

0

561

6

15

a

4

33

1

1

3

0

1602

7

17

12

1

5

1

2

1

0

267

8

183

1 1

8

67

6

2

12

2

2264

9

24

3

4

170

5

2

5

1

558

10

22

15

5

31

2

1

3

1

1831

11

23

9

37

25

7

3

0

2

470

12

23

8

3

4

3

1

0

1

211

13

9

8

14

8

16

2

0

4

153

14

37

3

14

81

9

39

3

5

785

15

25

4

8

81

16

10

0

9

181

16

7

3

16

9

16

28

0

16

122

17

3

1

2

39

10

28

31

12

207

18

0

0

0

3

0

0

31

1

55

19

2

1

4

5

9

16

12

1

74

ota 1

470

211

153
Table

785
13 Or

181
ieina

122
1 Trii

207
-i Matr

55
ix

74

16010

10 11 12 13 14 15 16 17

tota

2

1832

1832

3

982

102

1084

4

292

14

50

356

5

838

16

80

98

1032

6

2660

120

56

8

26

2870

7

232

56

:>0

6

10

40

374

8

1056

80

38

36

12

170

80

1472

9

6

4

352

362

10

3260

324

3584

11

172

2

6

18

8

36

34

454

48

778

12

124

4

44

70

4

8

24

52

6

46

382

13

48

6

8

74

4

8

2

8

44

16

218

14

502

46

6

12

10

66

10

134

340

62

74

6

28

1296

15

18

4

2

2

2

10

4

64

8

16

162

292

16

60

2

4

4

6

6

6

4

28

8

40

18

50

236

17

126

6

8

2

4

6

2

28

12

8

6

2

4

84

20

56

374

18

108

108

19

10

112

24 2

148

8942 454 334 336 90 334 160 4280 754 78 262 40 88 274 70 168 132

16798

Table 14 Equivalent Trip Matrix

38

Bizeni

MEDITERRANEAN

Cap* Bon

Ptnultem
(ITALY!

bole
Ptiagn

fTAlYI

MEDITERRANEAN
SEA

Figure 1 Links to Be Improved

39

Links to Be

[mproved

Link

Flow

Existing

Added

Improvement

Limit on Added

Capacity

Capacity

Cost

Capacity

1

2144

1370

774

592

887

3

2537

1637

899

394

899

4

2112

1115

997

297

1083

6

2015

1055

960

615

1070

10

1980

814

1166

484

1460

12

1052

448

604

84

2046

14

306

271

35

22

1354

19

1056

447

609

89

2046

20

2275

1173

1101

463

1101

26

2537

1637

899

245

899

28

2010

1370

640

362

887

30

1517

1370

147

60

887

73

2112

862

1250

394

1496

77

1772

1055

717

156

1070

90

2058

1370

687

179

887

Table 15

rtECKMAN

BINDERS NC.

JUN95

»N.MANCHK^a

I

BgafaafflKBt