Solving the Bus Network Design Problem
http://leidykla.vgtu.lt/conferences/ENVIRO_2014/Articles/3/114_Ciaffi.pdf
We are constantly surrounded by networks of the social sort, such as email, texting Facebook, or Twitter. However, people are not the only things networks can connect. An article titled “A New Methodology for the Public Transport Network Design” describes a way in which a visual model of networks can be used to solve the problem of optimizing public transport.
BNDP, or the Bus Network Design Problem, is an issue that effects any area that uses buses as its main form of public transportation. The problem is that of optimization, and how to achieve the most efficient bus patterns so that both the cost of operating buses and using buses is minimized. In order to calculate the optimal route configuration in terms of bus routes and frequencies, experts make great use of networks. According to the article, ” The best and most efficient solution methods are based on…test cases and real-life networks of small size.” The network used in this case can be illustrated by a simple graph in which the nodes represent transit centers and edges represent connections or roads between these centers. A route is thus a sequence of adjacent nodes. The graphical model is kept in balance because the required frequency of service never exceeds the maximum: bus schedules and time constraints do not allow the length of any sequence to be over a certain number. The minimum frequency of service is never reached because when the distance between nodes becomes too short, it is more efficient for the bus user to walk than to use the bus system.
Once the network of possible routes is established, experts can calculate the optimal bus routes using a complex system of formulas and algorithms. First, a heuristic algorithm generates 3 sets of possible routes: the first set consists of routes connecting the nodes most frequented by bus users. The second set aims at creating a network which factors in both connecting the nodes of highest demand, and using the edges that carry the highest volume of passengers. The third set is simply the existing network of bus routes. All three of these sets are combined according to specific criteria of efficiency and rationality. Finally, the set of feasible routes generated from the combination of the previous three sets is plugged into a genetic algorithm which calculates the optimal route choices.
Experts attempting to solve the Bus Network Design Problem implement networks in their everyday research. Networks help them to visualize the bus routes and attempt to optimize the efficiency of the transport system. Inputs to the optimization algorithms inherently include characteristics of road networks in order to compute the most efficient bus routes, as well as the most cost-effective method of transportation by bus. The article offers a last statistic in support of their use of networks and algorithms as a good way of optimizing bus transportation: “Specific numerical experiments about performance sensitivity to changes in lines frequency, carried out on the network of two districts if the city of Rome, highlighted that fleet size is much more sensible to supply changes in terms of runs respect to performance for users.”