Finding Viable Pollution Routes in an Urban Network under a Predefined Cost

Authors: Dimitra Alexiou, Stefanos Katsavounis, Ria Kalfakakou

Abstract:

In an urban area the determination of transportation routes should be planned so as to minimize the provoked pollution taking into account the cost of such routes. In the sequel these routes are cited as pollution routes.

The transportation network is expressed by a weighted graph G=(V,E,D,P) where every vertex represents a location to be served and E contains unordered pairs (edges) of elements in V that indicate a simple road. The distances / cost and a weight that depict the provoked air pollution by a vehicle transition at every road are assigned to each road as well. These are the items of set D and P respectively.

Furthermore the investigated pollution routes must not exceed predefined corresponding values concerning the route cost and the route pollution level during the vehicle transition.

In this paper we present an algorithm that generates such routes in order that the decision maker selects the most appropriate one. 

Keywords: bi-criteria, pollution, shortest paths.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1337129

References:

[1] Chao-Lin Liu, Tun-Wen Pai, Chun-Tien Chang, and Chang-Ming Hsieh, Path-Planning Algorithms for Public Transportation Systems, Fourth International conference on Intelligent Transportation Systems, Okland, California, USA, August 20011.
[2] Irina Dumitrescu, Natashia Boland, Algorithms for the Weight Constrained Shortest Path Problem, International Transactions in Operational Research, V8, Issue 1, pages 15–29, January 2001.
[3] Monir H. Sharker, Hassan A. Karimi, Computing least air Pollutio exposure routes, International Journal of Geographical Informati Science, V28, Issue 2, 2014.
[4] Ulungu, E. L. and Teghem, J. (1994), Multi-objectiv combinatorial optimization problems: A survey. J. Multi-Crit. Decis. Anal., 3: 83 104.