Printer Friendly

Acoustic signal based optimal route selection problem: performance comparison of multi-attribute decision making methods.

1. Introduction

The route guidance system provides an optimum route to drivers based on a cost function and a route solution. The cost function is related to the distance towards destination, travel time (TT), or the cost of a road segment, etc. The route choice mechanism can provide the optimum route for drivers, based on the cost function. The route selection mechanism is the key technique of vehicle navigation systems providing route-planning strategy for travelers. Defining suitable mathematical models to represent the route selection mechanism in traditional methods uses numerical techniques and methods where perceived traffic attributes are treated as crisp inputs. However, much of human reasoning is based on vague, imprecise, and subjective values. Thus, the traditional methods ignore the presence of vagueness and ambiguity in drivers' perception, making them difficult to be valid mathematical models.

Four different traffic attributes such as distance, traffic density state, travel time and number of intersections were considered for this problem of study. Here in this research work, for one of the considered attribute namely traffic density state, we have modeled it as Very low, Low, Below Medium, Medium, Above Medium, High and Very High using cumulative road side acoustic signal.

Why cumulative acoustic signal? Due to Urbanization, Motorization and increased population, traffic density on road segments and highways has been increasing constantly in recent years. Developed countries possess main characteristics of lane driven traffic condition. The efficient and reliable approach for traffic density and traffic density state estimation is through use of magnetic loop detectors, cameras, and speed guns but the installation, operational and maintenance cost of these intrusive sensors significantly high. Researchers have been developing several numbers of sensors, which have a number of significant advantages and disadvantages relative to each other. Nonintrusive traffic- monitoring methods based on ultrasound, radar, laser and audio signals posses different characteristics in terms of robustness to changes in environmental conditions; manufacture, installation, and repair costs; safety regulation compliance, and so forth [1]. Chaotic and non-lane driven city traffic conditions with the extremely varied speed ranges of 0-10, 10-20, 20-40, 40-50, 50-60 km/h, and more than 60 km/h, are very common in cities of developing geographies (India and South Asia) and are the one part of focus of this paper. For traffic analysis and traffic density estimation general purpose surveillance cameras were widely used. The quality of surveillance data is generally poor, and the range of operational conditions (e.g., night time, inclement, and changeable weather) requires robust techniques. The modality of road side acoustic signal seems to be good approach for traffic density state estimation, having very low installation, operation and maintenance cost; low-power requirement; operate in day and night condition.

Why traffic density state? Nowadays, urban traffic congestion is a complicated and ubiquitous problem. Continuous changes of traffic congestion with respect to the time lead to change the travel times of transportation network. These changes show the importance of time in transportation analyses in addition to the location. So determining the optimal path in a time-dependent transportation network is a challenging task. In the optimal route selection process, many attributes such as distance, traffic density, travel time, passenger car unit, encroachment, parking on road, road width, number of intersections etc. plays a key role. However many of them can indirectly constitute to traffic density state.

We begin with state of art literature in Section 2 followed by motivation to carry out this research work through spectrogram analysis in Section 3 followed by audio modality for traffic density state estimation in Section 4, wherein acoustic feature extraction is described in sub-section 4.1 and acoustic classification using adaptive neuro fuzzy classifier in sub-section 4.2. Comparative performance of multi attributes decision making methods such as SAW, WPM, AHP, TOPSIS in Section 5, followed by result and discussion, finally the conclusions are drawn in Section 6.

2. Related Work

Route guidance is one of the most key components of intelligent transportation systems. The route guidance system assist drivers by guidance information, which reduces travelers anxiety of unknown traffic density state and finds a optimal path from source to destination pair [2] Many scholars have proposed a variety of optimal path selection method. Teodorovic and Kikuchi [3] first proposed the fuzzy logic method for route selection problem where the drivers' perceived TTs are treated as fuzzy numbers, and route choices are given by an approximate reasoning model and fuzzy inference. This model consists of rules indicating the degree of preference of each route. However, this model only considers TT attributes, which is also difficult when generalized to multiple routes. Teodorovic and Kalic [4] proposed a route choice model for air transportation using fuzzy logic. This approach, other than TT, considers more attributes, such as travel cost, flight frequency, and the number of stopovers. However, it is limited to two possible routes. Pang et al [5] proposed a path selection method based on a fuzzy neural network, the method uses fuzzy neural network to express the relationship of various factors affecting the path selection and sorts all possible paths according to driver's preference. Yager and Kelman [6] introduced an extension of the analytical hierarchy process (AHP) approach using ordered weighted averaging (OWA) operators, suggesting that the capabilities of AHP as a comprehensive tool for decision-making improved by integration of the fuzzy linguistic OWA operators. Ben Elia and Shiftan [7] established a learning-based model of route choice behavior under real-time information using prospect theory and random utility theory. Lu [8] proposed models of drivers' response behaviors under guidance condition by using the Game Theory in this field. Hyunmyung Kim and Yongtaek Lim [9] developed a new dayto- day route choice model which includes network uncertainty, and they adopted a psychological theory called "reference point" theory.

Traffic density state is considered to be one of the key attribute in optimal route selection process and the acoustic modality for traffic density estimation is rising area of research. J. Kato proposed method for traffic density estimation based on recognition of local temporal variations that appear on the power signals in accordance with vehicle passes through reference point. HMM is used for observation of local temporal variations over small periods of time, extracted by wavelet transformation. Experimental results show good accuracy for detection of passage of vehicles [10]. The detailed design of an acoustic sensing hardware prototype which has been deployed by the side of the road is presented [11]. This unit samples and processes road noise to compute various metrics like amount of vehicular honks and vehicle speed distribution and sends the metrics to a remote server every alternate minute. Traffic density state as congested and free-flow is estimated. Vivek Tyagi et al. classify traffic density state as free flowing, Medium flow and Jammed. They consider short term spectral envelops features of cumulative acoustic signal, and then class conditional probability distribution is modelled on three broad traffic density state (mentioned above). Bayes classifier is applied to classify traffic density state which results in ~95% of accuracy, which is then improved by using discriminative classifier such as RBF-SVM [12]. Compare with the existing computer vision and traffic monitoring system in [13] and [14] this technique is independent of light condition and works well for developing regions.

Contribution of this research work: In this research work, traffic density state is considered as one of the prime attribute in optimal route selection process and a statistical framework (refer Section 4) is used to estimate vehicular traffic density state using the cumulative acoustic signal.

* We investigate the usefulness of roadside acquired cumulative audio signal in traffic density state estimation and corresponding decision making in optimal route selection process. Decision making using presented nonintrusive technique will be robust and independent of environmental conditions also it has significant advantages in the context of low manufacturing, installation, operational and maintenance cost.

* Various multi-attribute decision making techniques such as SAW, WPM, AHP and TOPSIS are incorporated in this study.

3. Motivation for research

Urban areas are concerned with effective traffic signal control and traffic management. Travel Time estimation for journey using real time traffic density information is major concern of city authorities. Referring to the developing geographical areas like Asia, the traffic is characterised be non lane-driven. In such conditions finding optimal route is a difficult job and density on road segment plays vital role in route selection process. The traffic density estimation using magnetic loop detectors, speed guns and video monitoring seems to be best, but the installation, maintenance and operation cost associated with these approaches are very high. Use of road side acoustic signal seems to be an alternative for traffic density estimation. The various traffic density states induce different cumulative acoustic signals. To prove the above statement, we have examined the spectrogram of the different traffic state's cumulative acoustic signals.

Spectrogram analysis: An omnidirectional microphone was placed on the pedestrian sidewalk at about 1 to 1.5 m height. We have collected about 2 hr of cumulative roadside acoustics data from Area segment (64, Ring rd to 505/507 wardha rd) of Nagpur city, India. Samples were collected for time durations of around 30s for seven different traffic density state conditions (Very low, low, below medium, medium, above medium, high and very high) and with 16000 Hz sampling frequency. Spectrogram for above traffic density states is presented in Fig. 1 (a) to (g).

* For the very low and low density traffic condition in Fig. 1 (a, b), we only see air turbulence noise and the wideband drive-by noise of the vehicles. No vehicle honks or very few honks are observed for very low and low traffic density condition.

* For the below medium, medium and above medium density traffic condition in Fig. 1 (c, d, e), we can see some vehicle honks, some wideband drive-by noise, and some concentration of the spectral energy in the low-frequency ranges.

* For the high and very high density traffic condition in Fig. 1 (f, g), we notice domination of several honk signals, almost no wideband drive-by engine noise or air turbulence noise. We note the several harmonics of the honk signals, and they are ranging from (2, 6) kHz.

We next describe (in Section 4) the statistical framework for traffic density state estimation which constitute of feature extraction scheme namely Mel-Frequency Cepstral Coefficients (MFCC) from the roadside acquired cumulative acoustic signal, followed by the description of theAdaptive Neuro-Fuzzy Classifier used in this work for classification.

4. Acoustic Modality for Traffic Density State Estimation

This section presents a statistical framework which uses MFCC for feature extraction and ANFC for traffic density state modeling. MFCC has proven to be one of the most successful feature representations in speech-related recognition tasks. Neuro-fuzzy systems has been proved to be most popular hybrid system with the sophisticated layer-by-layer learning procedures of neural networks, to create completely data-driven automated classification.

4.1 MFCC

Mel-Frequency Cepstral Coefficients (MFCC), which are the Discrete Cosine Transform (DCT) coefficients of a Mel-filter smoothed logarithmic power spectrum. Generally 13-20 Cepstral coefficients of acoustic signal's short time spectrum sufficiently capture the smooth spectral envelope information. For our experimental purpose, we have considered first 13 Cepstral coefficients to represent roadside cumulative acoustic signal for corresponding traffic density state. These coefficients have been very successfully applied as the acoustic features in speech recognition, speaker recognition [15], and music recognition and to vast variety of problem domains. Feature extraction using MFCC is as follows,

Pre-emphasis: to emphasis the higher frequencies

y[n] = x[n]-[alpha]x[n-1], [alpha] [euro] (0.9, 1) (1)

Framing and windowing: to keep the continuity of the first and the last points in the frame, frame size of 500ms and shift by 200ms would be considered for better interpretation of traffic density state as it is physical slow changing process.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

DFT: to converts each frame of N samples from time domain into frequency domain.

X[k] = [[summation].sup.N-1.sub.n=0] x[n][e.sup.-j2[pi]nk/N] u, 0 [less than or equal to] k [less than or equal to] N (3)

Triangular Bandpass filtering:

F (Mel) = 2595 x log 10 [1 + f/700] (4)

The ith Mel-filter bank energy ([M.sub.FB](i)) is obtained as

([M.sub.FB](i)) = ([Mel.sub.i](k)) x [[absolute value of X(k)].sup.2], k [euro] (0, N/2) (5)

DCT: This is the process to convert the log Mel spectrum into time domain

[c.sub.j] = [[summation].sup.24.sub.i=1] log([M.sub.FB](i))[square root of 2/24] cos([pi]ji-0.5/24), j [euro] (0, 12) (6)

Data energy and Spectrum:

Energy = [summation] [X.sup.2] [t] (7)

4.2 Adaptive Neuro Fuzzy Classifier

A neural-fuzzy system is a combination of neural networks and fuzzy systems. The combination is such that the neural networks or neural networks algorithms are used to determine parameters of fuzzy system. This means, the main intention of neural- fuzzy approach is to create or improve a fuzzy system automatically by means of neural network methods. An adaptive network is a multi-layer feed-forward network where each node performs a particular function based on incoming signals and a set of parameters pertaining to node. Fuzzy classification systems, which are founded on the basis on fuzzy rules, have been successfully applied to various classification tasks [16]. The fuzzy systems can be constituted with neural networks, and resultant systems are called as Neuro-fuzzy systems. The Neuro-fuzzy classifiers define the class distributions and show the input-output relations, whereas the fuzzy systems describe the systems using natural language. Neural networks are employed for training the system parameters in neuro-fuzzy applications. An ANFIS consist of input, membership function, fuzzification, defuzzification, normalization and output layers [16, 17, 18].

Layer 1: Refer to Fig. 2, Every mode in this layer is an adaptive node with a node function. where x (or y) is the input to node I and Ai (or Bi-2) is a linguistic label and O11 is the membership grade of fuzzy set A(= A1, A2, B1or B2) and it specifies the degree to which the given input x (or y) satisfies the quantifier

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (8)

Layer 2: Every node in this layer is a fixed node labeled [pi], whose output is the product of all the incoming signals. Each node output represents the firing strength of a rule.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

Layer 3: Every node in this layer is a fixed node labeled N. The i-th node calculates the ratio of the i-th rule's firing strength to the sum of all rules' firing strengths. Outputs of this layer are called normalized firing strengths.

[0.sub.3,i] = [[bar.W].sub.i] = [W.sub.i]/[W.sub.1] + [W.sub.2], i = 1, 2 (10)

Layer 4: Every node I in this layer is an adaptive node with a node function. Where [[bar.W].sub.i] is a normalized firing strength from layer 3 and [[p.sub.i], [q.sub.i], [r.sub.i]] is the parameter set of this node. Parameters in this layer are referred as consequent parameters.

[0.sub.4,i] = [[bar.W].sub.i][f.sub.i] = [[bar.W].sub.i] ([p.sub.i]x + [q.sub.i]y + [r.sub.i]), (11)

Layer 5: The single node in this layer is a fixed node labelled [summation], which computes the overall output as the summation of all incoming signals. Overall output is:

[0.sub.5,1] = [[summation].sub.i][[bar.W].sub.i][f.sub.i] = [[summation].sub.i][w.sub.i][f.sub.i]/[[summation].sub.i][w.sub.i] (12)

Average traffic density state is estimated using ANFC (refer Table 1) for traffic density states (VL: Very Low, L: Low, BM: Below Medium, M: Medium, AM: Above Medium, H: High and VH: Very High) for time span of 6-7 AM, 10-11 AM, 2-3 PM, 4-6 PM, 9-10 PM over seven different route segments (Ref. Fig. 4 (a) to (g))

5. Optimal Route Selection using MADM Methods

Multiple criterion decision making (MCDM) refers to decision making in the presence of multiple, usually conflicting criteria. The MCDM problems can be broadly classified into two categories: multiple attribute decision making (MADM) and multiple objective decision making (MODM), depending on whether the problem is a alternative selection problem or a objective problem. The multiple attribute decision making is employed when problem which involves selection from among finite number of alternatives. (a) Alternatives, (b) Attributes, (c) weight or relative importance of each attribute and (d) measure of performance of alternatives with respect to the attributes are the main parts in each decision table of MADM methods [19, 20].

At instance of time T = 4-6 PM, let intersection 1 (64, Pratap Nagar sq.) be source and 19 (505/506/507 Wardha Rd.) be destination (refer Fig. 3). There may be n number of routes and the best possible alternatives are,

To select optimal route out of considered alternatives, we have identified 4 attributes such as Distance from source to destination, Average Traffic density state estimated through acoustic signature (in Section 4.), Travel time without traffic and Number of intersections. The above route selection problem is formulated as (refer Table 2),

Route (with Ref. Fig. 3): Route 1: 1-2-3-4-9-15-19; Route 2: 1-2-4-9-15-19; Route 3: 1-2-5-6-4-9-15-19; Route 4: 1-2-5-6-8-9-15-19; Route 5: 1-10-11-7-8-9-15-19; Route 6: 1-10-11-12-16-17-18-19; Route 7: 1-10-11-7-13-14-18-19

Attributes: DT: Distance from source to destination (in Km); TD: Traffic Density State estimated using acoustic signal; TT: Travel Time without traffic; NI: Number of Intersections from source to destination. In reality, measure of performance (Cj can be crisp, fuzzy and/or linguistic. The decision makers can appropriately make use of any of the eight scales suggested [21]. For example, an 11-point scale and the corresponding crisp scores of the fuzzy numbers are presented in Table 3 and the quantitative values using fuzzy conversion scale for optimal route selection problem are provided in Table 4.

MADM methods are generally discrete, with a few numbers of predetermined alternatives. MADM is an approach employed to solve problems involving selection from among a finite number of alternatives. An MADM method specifies how attribute information is to be processed in order to arrive at a choice. Of the many MADM methods reported in the literature [21, 24, 25, 26, 27], we have applied few methods to solve optimal route selection problem.

5.1 SAW

A simple and most often used multi attribute decision technique. This method is based on weighted addition. The performance score for every alternative is calculated by multiplying the normalized value given to the alternative of that attribute with the weights of relative importance. These weights are directly assigned by decision maker followed by summation of the products for all attributes. The SAW method consists of following steps [22].

Step 1. Compute the decision matrix: The decision matrix is expressed as The decision table, given in Table 5, shows alternatives, Ai (for i = 1, 2, ..., n), attributes, [B.sub.j] (for j = 1, 2, ..., m), weights of attributes, [w.sub.j] (for j = 1, 2, ..., m) and the measures of performance of alternatives, [C.sub.ij] (for i = 1, 2, ..., n; j = 1, 2, ..., m). Given multi attribute decision making method and the decision table information, the task of the decision maker is to find the best alternative and/or to rank the entire set of alternatives. To consider all possible attributes in decision problem, the elements in the decision table must be normalized to the same units.

Step 2. Compute the normalized decision matrix:

The attributes can be considered as beneficial or non-beneficial. Normalized values are calculated by [([C.sub.ij]).sub.K]/[([C.sub.ij]).sub.L], where [([C.sub.ij]).sub.K] is the measure of the attribute for the Kth alternative, and [([C.sub.ij]).sub.L] is the measure of the attribute for the Lth alternative that has the highest measure of the attribute out of all alternatives considered. This ratio is valid for beneficial attributes only. A beneficial attribute (e.g., efficiency) means its higher measures are more desirable for the given decision-making problem. By contrast, non-beneficial attribute (e.g., cost) is that for which the lower measures are desirable, and the normalized values are calculated by [([C.sub.ij]).sub.L]/[([C.sub.ij]).sub.K] [19]. Table 6 describes the normalized values for the presented optimal route selection problem.

Step 3. Evaluate each alternative, Ai by the following formula:

[P.sub.i] = [[summation].sup.m.sub.j=1] [w.sub.j][([c.sub.ij]).sub.normal] (13)

where ([C.sub.ij])normal represents the normalized value of [C.sub.ij], and [P.sub.i] is the overall or composite score of the alternative [A.sub.i]. The alternative with the highest value of [P.sub.i] is considered as the best alternative. and

[w.sub.j] = [m.sub.j]/[[summation].sup.m.sub.j] [m.sub.j] (14)

Where [m.sub.j] is user preference weight for attribute, ex. Let for mj for DT be 45, TD be 50, TT be 15 and NI be 20, weights will be as follows, [w.sub.DT] = 0.3462, [w.sub.TD] = 0.3846, [w.sub.TT] = 0.1154 and [w.sub.NI] = 0.1538. Table 7 gives the overall score of seven alternatives (route) using SAW method. The alternative which is having highest score will be selected, here route 4 will be selected as it is having highest score of 0.8668.

5.2 WPM

Method is similar to SAW. The main difference is that, instead of addition in the model, there is multiplication [23]. The overall or composite performance score of an alternative is given by,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

The normalized values are calculated as explained under the SAW method. Each normalized value of an alternative with respect to an attribute, i.e., ([C.sub.ij])normal, is raised to the power of the relative weight of the corresponding attribute. The alternative with the highest Pi value is considered the best alternative. Table 8 gives the overall score of seven alternatives (route) using WPM method.

5.3 AHP

Analytical Hierarchy process (AHP) is one of the most popular analytical techniques for solving complex decision making problems [24, 25]. A number of functional characteristics make AHP a useful methodology. These include the ability to handle decision situations involving subjective judgments, multiple decision makers, and the ability to provide measures of consistency of preferences [26]. Designed to reflect the way people actually think, AHP continues to be the most highly regarded and widely used decision making method. AHP can efficiently deal with objective as well as subjective attributes.

Step 1: Determine the objective and the evaluation attributes. Develop a hierarchical structure with a goal or objective at the top level, the attributes at the second level and the alternatives at the third level.

Step 2: Determine the relative importance of different attributes with respect to the goal or objective.

Construct a pair-wise comparison matrix using a scale of relative importance (refer Table 9). The judgments are entered using the fundamental scale of the analytic hierarchy process [24, 25].

Assuming M attributes, the pair-wise comparison of attribute i with attribute j yields a square matrix [B.sub.M*M] where [b.sub.ij] denotes the comparative importance of attribute i with respect to attribute j. In the matrix, [b.sub.ij] = 1 when i = j and [b.sub.ji] = 1/[b.sub.ij].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Find the relative normalized weight ([w.sub.j]) of each attribute by (a) calculating the geometric mean of the i-th row, and (b) normalizing the geometric means of rows in the comparison matrix. This can be represented as:

[GM.sub.j] = [[[[PI].sup.M.sub.j=1][b.sub.ij]].sup.1/M] (16)

[w.sub.j] = [GM.sub.j]/[[summation].sup.M.sub.j][GM.sub.j] (17)

The geometric mean method of AHP is commonly used to determine the relative normalized weights of the attributes, because of its simplicity, easy determination of the maximum Eigen value, and reduction in inconsistency of judgments.

a) Calculate matrices A3 and A4 such that A3 = A1 * A2 and A4 = A3/A2, where A2 = [[[w.sub.1], [w.sub.2], ..., [W.sub.j]].sup.T]. where A1 is relative importance matrix.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

b) Determine the maximum Eigen value [lambda]max that is the average of matrix A4.

[lambda]max = 4.1147

c) Calculate the consistency index CI = ([lambda]max - M)/(M - 1). The smaller the value of CI, the smaller is the deviation from the consistency. Here M = 4.

CI = 0.0382

d) Obtain the random index (RI) for the number of attributes used in decision making. Refer to Table 10 for details.

e) Calculate the consistency ratio CR = CI/RI. Usually, a CR of 0.1 or less is considered as acceptable, and it reflects an informed judgment attributable to the knowledge of the analyst regarding the problem under study.

CR = 0.0430

Step 3: The next step is to obtain the overall or composite performance scores for the alternatives by multiplying the relative normalized weight (wj) of each attribute (obtained in step 2) with its corresponding normalized weight value for each alternative (obtained in step 2 of SAW method), and summing over the attributes for each alternative. This step is similar to the SAW method. Table 11 gives the overall score of seven alternatives (route) using AHP method.

5.4 TOPSIS

Hwang and Yoon [27] developed the TOPSIS method and it is based on the idea that the best alternative should have the shortest distance from the positive ideal solution and farthest distance from the negative ideal solution. The ideal solution is a hypothetical solution for which all attribute values correspond to the maximum attribute values in the database comprising the satisfying solutions; the negative ideal solution is the hypothetical solution for which all attribute values correspond to the minimum attribute values in the database. TOPSIS thus gives a solution that is not only closest to the hypothetically best, that is also the farthest from the hypothetically worst.

The TOPSIS method consists of the following steps:

Step 1. Same as SAW method.

Step 2. The normalized value [r.sub.ij] (refer Table 12) for positive attribute is computed as [r.sub.ij] = [c.sub.ij]/[square root of [[summation].sup.m.sub.j=1][c.sup.2.sub.ij]] (18)

Step 3. The weighted normalized decision matrix (refer Table 13) is constructed by multiplying each element [r.sub.ij] with its associated weight [w.sub.j]. Here weights are same as calculated by AHP method.

[V.sub.ij] = [r.sub.ij][w.sub.j] (19)

Step 4. Obtain the ideal (best) and negative ideal (worst) solutions in this step. The ideal (best) and negative ideal (worst) solutions can be expressed as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21)

Where J = (j = 1, 2, ..., M)/j is associated with beneficial attributes, and J' = (j = 1, 2, ..., M)/j is associated with non-beneficial attributes.

[V.sup.+.sub.j] indicates the ideal (best) value of the considered attribute among the values of the attribute for different alternatives. In the case of beneficial attributes (i.e., those of which higher values are desirable for the given application), [V.sup.+.sub.j] indicates the higher value of the attribute. In the case of non-beneficial attributes (i.e., those of which lower values are desired for the given application), [V.sup.+.sub.j] indicates the lower value of the attribute.

[V.sup.-.sub.j] indicates the negative ideal (worst) value of the considered attribute among the values of the attribute for different alternatives. In the case of beneficial attributes (i.e., those of which higher values are desirable for the given application), [V.sup.-.sub.j] indicates the lower value of the attribute. In the case of non-beneficial attributes (i.e., those of which lower values are desired for the given application), [V.sup.-.sub.j] indicates the higher value of the attribute

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Step 5. The distance of each alternative from the ideal and the negative ideal solution are given by

[S.sup.+.sub.j] = [square root of ([[summation].sup.M.sub.j=1][([V.sub.ij] - [V.sup.+.sub.j]).sup.2])] i=1,2 ... N (22)

[S.sup.-.sub.i] = [square root of ([[summation].sup.M.sub.j=1][([V.sub.ij] - [V.sup.-.sub.j]).sup.2])] i=1,2 ... N (23)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Step 6. The relative closeness coefficient of each alternative [A.sub.i] (i = 1, 2, ..., m) from the ideal solution can be expressed as

[P.sub.i] = [s.sup.-.sub.i]/[s.sup.-.sub.i] + [s.sup.+.sub.i] (24)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Step 7. The best alternatives are ranked according to the Pi value in descending order. Table 14 gives the overall score of seven alternatives (route) using TOPSIS method.

Discussion: Traffic density state has been estimated using cumulative road acoustic signal. Classification accuracy achieved using Adaptive Neuro-Fuzzy classifier is of 93.33% for 13 MFCC coefficients. Multi attribute decision making algorithms such as Simple Additive Weighting (SAW), Weighted Product Method (WPM), Analytic Hierarchy Process (AHP) method and Total Order Preference by Similarity to the Ideal Solution (TOPSIS) methods have been applied for optimal route selection problem; rank of routes are as follows (refer Table 15)

Discussion: Table 16 provides the overall score of every alternative using various multi-attrbute decision making menthods such as SAW, WPM, AHP and TOPSIS over observed time span of 6-7 AM, 10-11 AM, 2-3 PM and 9-10 PM which was presented in Table 1. The obtained results are validated as the consistency ratio obtained using AHP is 0.0430 which is much less than 0.1.

6. Conclusion

This paper describes a simple technique which uses MFCC features of the road side cumulative acoustic signal to model traffic density state as Very Low, Low, Below Medium, Medium, Above Medium, High and Very High using Adaptive Neuro-Fuzzy Classifier. As this technique uses simple microphone so its installation, operational and maintenance cost is very low. This technique work well under non lane driven and chaotic traffic condition, and is independent of lighting condition. In this paper, optimal route selection problem is considered, having one of the attribute as traffic density state which is estimated using acoustic signal. Simple point method and AHP has been used to determine the weights of the attributes and SAW, WPM, AHP and TOPSIS techniques have been used for optimal route selection problem. Performance analysis of MADM techniques shows that almost same route is selected by all methods. Therefore, all techniques are effective for route selection. SAW and WPM method is widely used and the best known method. It is very simple and easy to implement. TOPSIS is one of the best methods because the best alternative is closest to positive ideal solution but farthest from negative ideal solution.

http://dx.doi.org/10.3837/tils.2016.02.012

Acknowledgments

Authors are thankful to Dr. P. R. Bajaj, Director of GHRCE, for motivation and providing infrastructure to carry out research work and also to also to the anonymous reviewers for many helpful suggestions.

References

[1] R. Valcarce, C. Mosquera and R. Gonzalez, "Estimation of road vehicle speed using two omnidirectional microphones: A maximum likelihood approach," EURASIP J. Appl. Signal Process, pp. 1059-1077, 2004. Article (CrossRef Link).

[2] Li. Weiwu, W. Hui and Q. Jixin, "New trends in route guidance algorithm research of intelligent transportation system," Journal of Zhejiang University: Engineering Science, vol.39, pp.819-825, 2005.

[3] D. Teodorovic and S. Kikuchi, "Transportation route choice model using fuzzy inference technique," in Proc. of 1st Int. Symp. Uncertainty Model. Anal.: Fuzzy Reason., Probab. Models, Risk Manage., College Park, MD, USA, pp. 140-145, 1990. Article (CrossRef Link).

[4] D. Teodorovic and M. Kalic, "A fuzzy route choice model for air transportation networks," Transp. Plann. Technol., vol. 19, no. 2, pp. 109-119, Nov. 1995. Article (CrossRef Link).

[5] G. K. H. Pang, K. Takahashi, and T. Yokota, "Adaptive route selection for dynamic route guidance system based on fuzzy-neural approaches," IEEE Trans. Veh. Technol., vol. 48, no. 6, pp. 2028-2041, Nov. 1999. Article (CrossRef Link).

[6] R. R. Yager and A. Kelman, "An extension of the analytical hierarchy process using OWA operators," J. Intell. Fuzzy Syst., vol. 7, no. 4, pp. 401-417, Dec. 1999.

[7] Eran Ben-Elia, Yoram Shiflan, "Which road do I take? A learning based model of route-choice behavior with real-time information," Transportation Research Part A, vol.44, pp. 249-264, 2010. Article (CrossRef Link).

[8] LU C L, "The models of driver's response behavior with game theory under guide information," Journal of Transportation Systems Engineering and Information Technology, vol.5, pp.58-61, 2005

[9] Hyunmyung Kim, Yongtaek Lim, "A Day-to-day Route Choice Model based on Drivers' Past Experience," KSCE Journal of Civil Engineering, vol.16, pp.1267-1279, 2012. Article (CrossRef Link).

[10] J. Kato, "An Attempt to Acquire Traffic Density by Using Road Traffic Sound," in Proc. of Active Media Technology, Proceedings of the 2005 International Conference on, pp. 353- 358, 2005. Article (CrossRef Link).

[11] R. Sen, P. Siriah and B. Raman, "Roadsoundsense: Acoustic sensing based road congestion monitoring in developing regions," Sensor, Mesh and Ad Hoc Communications and Networks (SECON), 8th Annual IEEE Communications Society Conference on, pp. 125-133, 2011. Article (CrossRef Link).

[12] V. Tyagi, S. Kalyanaraman and R. Krishnapuram, "Vehicular traffic density state estimation based on cumulative road acoustics," IEEE Trans. Intell. Transp. Syst. vol. 13, no. 3, pp. 1156-1166, 2012. Article (CrossRef Link).

[13] R. Cucchiara, M. Piccardi and P. Mello, "Image analysis and rule based reasoning for a traffic monitoring system," IEEE Transaction on Intelligent. Transp. Syst., vol. 1, no. 2, pp. 119-130, 2000. Article (CrossRef Link).

[14] S. Kamijo, Y. Matsushita and K. Ikeuchi, "Traffic monitoring and accident detection at intersections," IEEE Transaction on Intelligent Transp. Syst.,vol.1, no. 2, pp. 108-118, 2000. Article (CrossRef Link).

[15] S. Nakagawa, W. Longbiao and S. Ohtsuka, "Speaker Identification and Verification by Combining MFCC and Phase Information," IEEE Transaction on Audio, Speech, and Language Processing, vol. 20, no. 4, 2012. Article (CrossRef Link).

[16] J.S.R Jang, C.T. Sun and E. Mizutani, "Neuro-fuzzy and soft computing," Upper Saddle River: Prentice Hall, 1997

[17] B. Cetisli, "Development of an adaptive neuro-fuzzy classifier using linguistic hedges: Part 1," Expert Systems with Applications, 2010. Article (CrossRef Link).

[18] B. Cetisli and A. Barkana, "Speeding up the scaled conjugate gradient algorithm and its application in neuro-fuzzy classifier training," Soft Comput, 2010. Article (CrossRef Link).

[19] R. Rao, "Decision Making in the Manufacturing Environment Using Graph Theory and Fuzzy Multiple Attribute Decision Making," Springer series in advanced manufacturing, 2007. Article (CrossRef Link)

[20] R. Rao, "Decision Making in Manufacturing Environment Using Graph Theory and Fuzzy Multiple Attribute Decision Making Methods," Springer series in advanced manufacturing, vol. 2, 2013. Article (CrossRef Link).

[21] SJ. Chen and CL. Hwang, "Fuzzy multiple attribute decision making-methods and applications," Lecture Notes in Economics and Mathematical Systems, Springer, New York, 1992. Article (CrossRef Link).

[22] PC. Fishburn, "Additive utilities with incomplete product set: applications to priorities and assignments," Operations Research Society of America, Baltimore, 1967. Article (CrossRef Link).

[23] DW. Miller and MK. Starr, "Executive decisions with operations research," Prentice Hall, Englewood Cliffs, New Jersey, 1969

[24] T. L. Saaty, "The analytic hierarchy process, planning, priority setting, resource allocation," New York: McGraw-Hill, 1980.

[25] T. L. Saaty, "Fundamentals of decision making and priority theory with AHP," R WS Publications, Pittsburg, 2000.

[26] E. Triantaphyllou, "Multi-criteria decision making methods: a comparative study," Springer, London, 2000. Article (CrossRef Link).

[27] CL. Hwang and KP. Yoon, "Multiple attribute decision making: methods and applications," Springer, New York, 1981. Article (CrossRef Link).

Prashant Borkar is a research scholar in department of CSE at GHRCE, Nagpur, India. His area of research includes signal processing, data mining, fuzzy systems and intelligent transport systems. He is regular reviewer of IEEE Transaction of System Man and Cybernetics, International Journal of Fuzzy Systems (Springer), Transportation Letters: The International Journal of Transportation Research (Springer), Elsevier Computers & Electrical Engineering, WSEAS Journals (Transactions) and Conferences like ICISP 15, ICETET 13, 15. He is member and web chair of Data Science group under ACM Nagpur Chapter. He has published more than 23 research papers in reputed journals and conferences. He is receipient of Best Teacher award for the academic session 2014-15.

Dr. M. V. Sardoe is a Professor and Head of Department of Computer Science & Technology, JCOET, Yavatmal. He has received PhD degree from Amravati University. His research interests include Image processing, Computer Networks and Internet. He is a senior professor with teaching experience of 18 years. Dr. Sarode is life member of CSI and presented more than 33 research papers in journals and conferences.

Dr. L. G. Malik is a Professor and Head of Department of Computer Science & Engineering, GHRCE, Nagpur. Her research interests include Document Processing, Bioinformatics, Pattern Recognition, Intelligent Systems and Image Processing. She has completed Ph.D. (Computer Science & Engineering) from Visveyaraya National Institute of Technology in 2010, M.Tech. (Computer Science & Engineering) from Banasthali Vidyapith, Rajasthan, India and B.E. (Computer Engineering) from University of Rajasthan, India. She is gold medalist in B.E. and M.Tech. She has teaching experience of 16 years. Mrs. Latesh Malik is life member of ISTE, CSI, ACM and presented 22 papers in international journal and 39 papers in international conference. She is recipient of one RPS and 1 MODROBs by AICTE. She guided 26 PG projects and 8 Ph.D. students are registered under RTM Nagpur University.

Prashant Borkar (1), M. V. Sarode (2) and L. G. Malik (1)

(1) G H Raisoni College of Engineering, GHR Labs & Research Centre Nagpur, 440016--INDIA

[e-mail: prashant.borkar@raisoni.net, latesh.malik@raisoni.net]

(2) JCOET, Departement of CSE Yawatmal, INDIA

[e-mail:milind09111970@gmail.com]

* Corresponding author: Prashant Borkar

Received February 1, 2015; revised September 5, 2015; revised November 14, 2015; accepted December 28, 2015; published February 29, 2016

Table 1. Average traffic density state estimated using ANFC

Route                 Estimated Traffic Density State

          T=6-7 AM   T=10-11 AM   T=2-3 PM   T=4-6 PM   T=9-10 PM

Route 1   L          H            AM         VH         AM
Route 2   VL         H            AM         AM         AM
Route 3   VL         AM           M          H          M
Route 4   L          M            BM         VL         BM
Route 5   L          AM           M          M          H
Route 6   BM         H            AM         L          AM
Route 7   L          AM           M          BM         BM

Table 2. Optimal route selection problem

Route     DT    TD             TT   NI

Route 1   5     Very High      7    8
Route 2   4.6   Above Medium   8    7
Route 3   5     High           8    6
Route 4   5.2   Very Low       11   6
Route 5   4.6   Medium         9    7
Route 6   5.1   Low            11   6
Route 7   4.9   Below Medium   10   4

Table 3. Values of selection attribute

Qualitative measures of   Fuzzy        Assigned
selection attribute       number       crisp score

Exceptionally low         [M.sub.1]    0.0455
Extremely low             [M.sub.2]    0.1364
Very low                  [M.sub.3]    0.2273
Low                       [M.sub.4]    0.3182
Below medium              [M.sub.5]    0.4091
Medium                    [M.sub.6]    0.5000
Above medium              [M.sub.7]    0.5909
High                      [M.sub.8]    0.6818
Very high                 [M.sub.9]    0.7727
Extremely high            [M.sub.10]   0.8636
Exceptionally high        [M.sub.11]   0.9545

Table 4. Quantitative values using
fuzzy conversion scale for optimal
route selection problem

Route     DT    TD       TT   NI

Route 1   5     0.7727   7    8
Route 2   4.6   0.5909   8    7
Route 3   5     0.6818   8    6
Route 4   5.2   0.2273   11   6
Route 5   4.6   0.5000   9    7
Route 6   5.1   0.3182   11   6
Route 7   4.9   0.4091   10   4

Table 5. Decision Table in MADM methods

Alternatives   Attributes (weights)

               [B.sub.1]     [B.sub.2]
               ([w.sub.1])   ([w.sub.2])

[A.sub.1]      [C.sub.11]    [C.sub.12]
[A.sub.2]      [C.sub.21]    [C.sub.22]
[A.sub.3]      [C.sub.31]    [C.sub.32]
--             --            --
--             --            --
[A.sub.n]      [C.sub.n1]    [C.sub.n2]

Alternatives   Attributes (weights)

               [B.sub.3]     --   --   [B.sub.m]
               ([w.sub.3])             ([w.sub.m])

[A.sub.1]      [C.sub.13]    --   --   [C.sub.14]
[A.sub.2]      [C.sub.23]    --   --   [C.sub.24]
[A.sub.3]      [C.sub.33]    --   --   [C.sub.34]
--             --            --   --   --
--             --            --   --   --
[A.sub.n]      [C.sub.n3]    --   --   [C.sub.n4]

Table 6. Normalized data of optimal route selection problem

Route     DT       TD       TT       NI

Route 1   0.9200   0.2942   1.0000   0.5000
Route 2   1.0000   0.3847   0.8750   0.5714
Route 3   0.9200   0.3334   0.8750   0.6667
Route 4   0.8846   1.0000   0.6364   0.6667
Route 5   1.0000   0.4546   0.7778   0.5714
Route 6   0.9020   0.7143   0.6364   0.6667
Route 7   0.9388   0.5556   0.7000   1.0000

Table 7. Alternatives scores and rank for optimal
route selection problem using SAW

Route     Score    Rank

Route 1   0.6239   7
Route 2   0.6830   5
Route 3   0.6502   6
Route 4   0.8668   1
Route 5   0.6987   4
Route 6   0.7630   3
Route 7   0.7733   2

Table 8. Alternatives scores and rank for
optimal route selection problem using WPM

Route     Score    Rank

Route 1   0.5455   7
Route 2   0.6257   5
Route 3   0.5891   6
Route 4   0.8547   1
Route 5   0.6582   4
Route 6   0.7561   2
Route 7   0.7490   3

Table 9. Saaty's 1-9 scale of pair wise comparison

Intensity of importance   Definition

1                         Equal importance
3                         Moderate importance
5                         Strong importance
7                         Very strong importance
9                         Extreme importance
2 4 6 8                   Intermediate values

Table 10. Random Index (RI) values

Attributes   3      4      5      6      7      8     9      10

RI           0.52   0.89   1.11   1.25   1.35   1.4   1.45   1.49

Table 11. Alternatives scores and rank for optimal
route selection problem using AHP

Route     Score    Rank

Route 1   0.6029   7
Route 2   0.6729   5
Route 3   0.6329   6
Route 4   0.8900   1
Route 5   0.6966   4
Route 6   0.7740   2
Route 7   0.7667   3

Table 12. Normalized decision matrix

Alternative     DT       TD       TT       NI

Route 1       0.3842   0.5489   0.2858   0.4730
Route 2       0.3534   0.4198   0.3266   0.4139
Route 3       0.3842   0.4844   0.3266   0.3548
Route 4       0.3996   0.1615   0.4491   0.3548
Route 5       0.3534   0.3552   0.3674   0.4139
Route 6       0.3919   0.2261   0.4491   0.3548
Route 7       0.3765   0.2906   0.4082   0.2365

Table 13. Weighted normalized decision matrix

Alternative     DT       TD       TT       NI

Route 1       0.1450   0.2355   0.0186   0.0607
Route 2       0.1334   0.1801   0.0213   0.0531
Route 3       0.1450   0.2078   0.0213   0.0455
Route 4       0.1508   0.0693   0.0293   0.0455
Route 5       0.1334   0.1524   0.0240   0.0531
Route 6       0.1479   0.0970   0.0293   0.0455
Route 7       0.1421   0.1247   0.0266   0.0303

TABLE 14. Alternatives scores and
rank for optimal route selection
problem using TOPSIS

Route     Score    Rank

Route 1   0.0668    7
Route 2   0.3431    5
Route 3   0.1913    6
Route 4   0.8678    1
Route 5   0.4973    4
Route 6   0.7931    2
Route 7   0.6704    3

TABLE 15. Alternatives ranking for optimal
route selection problem using SAW, WPM,
AHP and TOPSIS

MADM      Ranking of routes

Methods   R1   R2   R3   R4   R5   R6   R7

SAW       7    5    6    1    4    3    2
WPM       7    5    6    1    4    2    3
AHP       7    5    6    1    4    2    3
TOPSIS    7    5    6    1    4    2    3

TABLE 16. Alternatives scores and rank for
optimal route selection problem over varying
time span using SAW, WPM, AHP and TOPSIS

Route     Time Span: 6-7 AM

          SAW               WPM

           Score     Rank    Score     Rank

Route 1   0.785536    5     0.767317    5
Route 2   0.919656    1     0.903494    1
Route 3   0.906617    2     0.898859    2
Route 4   0.756959    6     0.751008    6
Route 5   0.798571    4     0.783129    4
Route 6   0.701939    7     0.686439    7
Route 7   0.834324    3     0.824971    3

Route     Time Span: 10-11 AM

          SAW               WPM

           Score     Rank    Score     Rank

Route 1   0.792852    6     0.775112    6
Route 2   0.817104    5     0.801908    5
Route 3   0.847453    4     0.842929    3
Route 4   0.866828    2     0.854741    2
Route 5   0.849275    3     0.83584     4
Route 6   0.770299    7     0.76377     7
Route 7   0.885028    1     0.880499    1

Route     Time Span: 2-3 PM

          SAW               WPM

           Score     Rank    Score     Rank

Route 1   0.777076    6     0.758141    6
Route 2   0.801328    5     0.784351    5
Route 3   0.836697    4     0.832103    3
Route 4   0.866828    2     0.854741    2
Route 5   0.838519    3     0.825105    4
Route 6   0.754523    7     0.747049    7
Route 7   0.874272    1     0.86919     1

Route     Time Span: 9-10 PM

          SAW               WPM

           Score     Rank    Score     Rank

Route 1   0.777076    5     0.758141    5
Route 2   0.801328    4     0.784351    4
Route 3   0.836697    3     0.832103    3
Route 4   0.866828    2     0.854741    2
Route 5   0.754611    6     0.732333    7
Route 6   0.754523    7     0.747049    6
Route 7   0.944193    1     0.938921    1

Route     Time Span: 6-7 AM

          AHP               TOPSIS

           Score     Rank   Score    Rank

Route 1   0.814332    5     0.4599    6
Route 2   0.950956    1     0.8091    2
Route 3   0.935413    2     0.8336    1
Route 4   0.784647    6     0.4806    5
Route 5   0.829871    4     0.4928    4
Route 6   0.730172    7     0.1365    7
Route 7   0.863709    3     0.5385    3

Route     Time Span: 10-11 AM

          AHP               TOPSIS

           Score     Rank   Score    Rank

Route 1   0.821648    6     0.1740    7
Route 2   0.848404    5     0.2808    5
Route 3   0.876249    4     0.4939    3
Route 4   0.894516    2     0.6624    1
Route 5   0.880575    3     0.4809    4
Route 6   0.798532    7     0.2255    6
Route 7   0.914413    1     0.5988    2

Route     Time Span: 2-3 PM

          AHP               TOPSIS

           Score     Rank   Score    Rank

Route 1   0.805872    6     0.1584    7
Route 2   0.832628    5     0.2550    5
Route 3   0.865493    4     0.4951    3
Route 4   0.894516    2     0.6940    1
Route 5   0.869819    3     0.4841    4
Route 6   0.782756    7     0.2036    6
Route 7   0.903657    1     0.5825    2

Route     Time Span: 9-10 PM

          AHP               TOPSIS

           Score     Rank   Score    Rank

Route 1   0.805872    5     0.3195    6
Route 2   0.832628    4     0.3668    4
Route 3   0.865493    3     0.6317    3
Route 4   0.894516    2     0.7637    2
Route 5   0.785911    6     0.1899    7
Route 6   0.782756    7     0.3456    5
Route 7   0.973577    1     0.8802    1
COPYRIGHT 2016 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Borkar, Prashant; Sarode, M.V.; Malik, L.G.
Publication:KSII Transactions on Internet and Information Systems
Article Type:Report
Date:Feb 1, 2016
Words:7908
Previous Article:Efficient channel assignment scheme based on finite projective plane theory.
Next Article:An amplify-and-forward relaying scheme based on network coding for deep space communication.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters