Dear All,
Speaking with practicians we have met a problem of optimal road
network reduction in the case of emergency (e.g. when a huge snowing
comes). We were not able to find any description of such a problem in
available bibliography, but it is unbelievable that it is not yet solved. The
probable reason is that our sources are limited and using Google we do
not choose good keywords. We have found thousands network
reduction problems, but no one concerning road networks.
Mathematical formulation of the problem could be e.g. the following:
Suppose the given road network is represented by a non oriented
graph G = (V, E, d) where d(e) is the length of the edge e. Let d(G) be
the total length of all edges in E, d(S) be the length of the minimum
spanning tree S on G.
Suppose that Q is the given O-D matrix with card(V) rows and
columns.
Suppose that an emergency state occurs (e.g. a huge snow-fall) and it
is not possible to maintain the whole network passable. It is possible
only for maximum length d0, d(S)<d0<d(G).
The problem is to find a partial graph G’ = (V, E’) such that d(G’)<= d0
and G’ minimizes the total trip length of the vehicles expressed by the
matrix Q.
Could you kindly advise us some references?
With best regards
Jan
==================================================
Jan Cerny, professor,University of Economics Prague,
Faculty of Management, 37701 Jindrichuv Hradec, Czech Rep.
Phone ++420-384417203, fax -384417277, Email [log in to unmask]
|