Free Essay

Operations Research Journal

In: Business and Management

Submitted By agnivasaha
Words 6029
Pages 25
Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

A SHORTEST PATH ALGORITHM FOR REAL ROAD NETWORK BASED ON PATH OVERLAP Yongtaek LIM Assistant Professor Division of Transportation and Logistics System Engineering Yosu National University San 96-1, Dundeok-dong, Yosu city Chunnam, 550-749, KOREA Fax:+82-061-659-3340 E-mail:limyt@yosu.ac.kr Hyunmyung KIM PhD Student Department of Civil Engineering Institute of Transportation Studies University of California, Irvine USA Fax: (949) 824-8385 E-mail: hyunmyuk@uci.edu

Abstract : Existing k-shortest path algorithms has some weaknesses such as path similarity among determined paths and network expansion for describing turn prohibitions. Path similarity represents that many of the alternative paths derived from the k-shortest path algorithm are likely to share a lots of links, so they could not represent heterogeneity. The turning restrictions popularly adopted in real road may violate Bellman’s principle of optimality in searching shortest path, so network expansion technique is widely used to avoid such difficulty. But, this method needs additional works to expand the network. This paper proposes a link-based shortest path algorithm to generate dissimilar paths for the travel information in real road network where exists turn prohibitions. The main merit of proposed model is to provide efficient alternative paths under consideration of overlaps among paths to alleviate the path similarity. Another merit is that it does not require extra nodes and links for expanding the network. Thus it is possible to save the time of network modification and of computer running. The algorithm is tested with some example networks and then will be expanded to a dynamic case. Key Words : dissimilar path, path overlap, turn prohibition, link-based algorithm, k-shortest path

1. INTRODUCTION A shortest path problem is for finding a path with minimum travel cost from one or more origins to one or more destinations through a connected network. It is an important issue because of its wide range of applications in transportations. In some applications, it is also beneficial to know the second or third shortest paths between two nodes. For instance, in order to improve the effectiveness of travel information provision, there is a need to provide some rational alternative paths for road users driving in real road network. To meet it, k shortest path algorithms have been used in general. Yen (1971) first proposed k shortest path searching method, which could generate several additional paths by deleting node on the shortest path. Since Yen, Several k-shortest algorithms have been suggested. Although k shortest path algorithm can provide several alternative paths, it has inherent limit of heavy overlapping among derived paths, which may lead to wrong travel information to the users. This is that significant proportion of links on the first path is overlapped by second and third path calculated from the method, so the drivers on those links may suffer severe congestions if they follow the travel information. This is the same problem of IIA (Independence of

1426

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

Irrelevant Alternatives) in logit-based stochastic assignment. On the other hand existing shortest path algorithms such as Dijkstra, Moore build the optimal path based on the node they reach. However, in the case of considering the network consisting of several turn prohibitions such as restricting left-turn, which are popularly adopted in real world network, it makes difficult for the traditional network optimization technique to deal with. Banned and penalized turns may be not described appropriately for in the standard node/link method of network definition with intersections represented by nodes only. The reason is that Bellman`s 'Principle of Optimality` does not hold in that case. Several approaches have been proposed for solving the problem. Among all methods currently available, the most widely used method is network expansion for describing turn penalties, adding extra nodes and extra links to original network and modify the network to be easily implemented the conventional shortest path algorithms. The principal advantage of this method is that it can describe the turn prohibitions perfectly. The method, however, has limitation of expanding network as the size of network increases, so this method could not apply to large networks as well as dynamic case due to its overwhelming additional works. This paper proposes a link-based shortest path algorithm for the travel information in real road network where exists turn prohibitions. When penalized turns are dealt with without explicitly expanding the network, node-based existing shortest path algorithm is inappropriate, because the Bellman’s optimality condition has the property that no node may be approached from the origin for less cost than the chosen preceding node which is also reached by a shortest cost path. But link-based shortest path algorithm makes possible to reflect all turns effectively because it holds Bellman’s optimal condition in searching step. The main merit of proposed model is to provide efficient alternative paths for route guidance under consideration of overlaps among paths. The algorithm builds new path based on both the degree of overlapping between each path and travel cost, and stops building when the degree of overlapping ratio exceeds its criterion. Because proposed algorithm generates the shortest path based on the link-end cost instead of node cost and constructs path between origin and destination by link connection, the network expansion does not require. Thus it is possible to save the time of network modification and of computer running. The algorithm is tested with some example networks and then will be expanded to dynamic case. This paper has been organized as follows. In the next section, two problems of existing shortest path algorithms are given. A detailed description of the proposed algorithm is defined in section 3, and the comparison with conventional algorithm and performance of the algorithm are illustrated in section 4 with some numerical examples. Finally, conclusions are drawn in section 5.

2. TWO PROBLEMS IN REAL ROAD NETWORK FOR FINDING SHORTEST PATHS 2.1 K shortest paths and similarity In single objective route-planning problems, it may be adequate to choose a single best path from an origin to a destination. In contrast, there may be some cases that several paths are required for specific purposes such as route guidance, road construction and hazardous

1427

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

material transportation. It is possible to accomplish this via a k-shortest path algorithm by selecting a sufficiently large k. A straightforward way to define a set of k-paths is to successively select the 1st, 2nd, 3rd…, k-th shortest path. In some applications, it is also beneficial to know the second or third shortest paths between two nodes. There are a number of algorithms to find the paths classified by two categories such as simple paths without repeated nodes and arcs, and as looping paths with repeated node and arcs. (Yen, 1971; Shier,1979). However, many of these alternative paths derived from the k-shortest path algorithm are likely to share a large number of links. It represents spatial similarity between generated paths and may not be representative for the heterogeneity that can be found in the set of all paths. In order to obtain a path set that is more representative for the variety of choice that are available, overlapping alternatives should be excluded. Heuristic alternatives to the k-shortest paths method are based on link elimination and link penalty rules. Both methods consist of modifying the network after identifying the shortest path. A lot of approaches have been presented regarding this problem. Barra et al. (1993) proposed a link penalty method such that the network is modified by increasing the cost of all links on the shortest path. After modifying the network a new shortest path is computed according to the increased costs and the process continues until no more paths are required or no more paths can be determined. Scott et al.(1997) proposed an approach that would find the best k-similar paths that have at most k links in common with the shortest path. Akgun et al.(2000) determined a dissimilar path set by measuring the spatial dissimilarity between any two paths in the past set. The dissimilar paths are calculated by choosing some paths from the paths set in a way that the minimum of distance between any two paths is maximized. Although we adopt the link penalty method of Barra et al.(1993), the method proposed in this paper is somewhat different from that of Barra et al. in that the alternative paths are found under the maximum degree of overlap among paths determined previously. The merit of this method is that it allows path cost and path overlaps simultaneously for searching the k-paths. 2.2 Turn prohibitions On the other hand, some kinds of turning restrictions such as turn prohibitions, P-turn or U-turn which are popularly adopted in real world network analysis, make difficult for the traditional network optimization technique to deal with. Banned and penalized turns are not described appropriately for in the standard node/link method of network definition with intersections represented by nodes only. Caldwell(1961) proposed a method for incorporating them in the basic road network by transforming it into a much larger network in which each node represents a link in the original network and each link is a permitted turning movement. This approach adopted on a network-wide basis as in the TRRL method of network definition, is however, not suitable for networks which are already large when defined by the standard node/link method. It is possible to handle banned or penalized turns without explicitly expanding the network; If the turn from link(i,j) into link(j,k), ie. turn i→j→k, is penalized, the network data table for link(j,k) is extended to include node i and the turning penalty. Data for any number of penalized turns into link(j,k), or any other link, may be stored in this way at the expense of increased run time spent searching for and taking account of the relevant penalties. When penalized turns are dealt with without explicitly expanding the network, tree-building algorithm is inappropriate, because of not allowing turning penalties. Existing vine-based algorithms, however, have limitations to find shortest path in some cases of that P-urn, U-turn,

1428

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

turn prohibitions are included. In real road network P-turn and U-turn are introduced frequently in order to prevent left-turn for the purpose of reducing the number of signal phases at intersection. In such case conventional vine algorithm has the difficulty in searching optimal path. The reason also comes from the fact that optimality condition is not valid any more. Bellman’s optimality condition has the property that no node may be approached from the origin for less cost than the chosen preceding node which is also reached by a shortest cost path. However, introduction of turn delay and bans means that it is sometimes necessary, in practice to violate this condition. The ‘P-turn’ or ‘U-turn’ shown in Figure 1 provides common examples.

(a) P-turn

(b) U-turn

Figure1. Examples for P-turn and U-turn The solution to model the situations correctly is to build trees in a form known as vines. Vines have the property that a node may occur more than once in a path. Vines are built by expanding the network so that each turning movement at a node is represented as an arc. The vine-based algorithm, however, also has the limitation of finding shortest path in the case of considering successive banned turns. Kim (1998) showed that in some cases vine-based method could not search optimal path. A case is shown in Figure 2. Two successive banned left-turns are existed on the network which has one origin-destination pair from node r to node s. The banned left-turns are represented with relatively big turning penalties. The number of links and link travel times are on the link in the Figure, the values in parenthesis are link travel times. In this case, conventional vine-based algorithms may lead to wrong result; not finding optimal path. The reason comes from that the vine algorithms, satisfying the optimality condition, restrict the feasible searching nodes.

r

1(1)

1
3(2)

2(1)

2
5(3)

4(2)

3
6(3)

4

7(4)

5

8(3)

6

9(2)

s

Figure 2. Example network by Kim (1998) To overcome the limitations above-mentioned, in this paper we adopt a link-based shortest path algorithm, which was originated by Potts and Oliver (1972). This method does not

1429

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

require the network expansion, thus enable to save the time of network modification and of computer running. The algorithm builds the shortest path based on the link-end cost instead of node cost. Thus, it makes possible to reflect all turns such as left-turn, right-turn, U-turn, P-turn and turn prohibition effectively when we search for the shortest path in real world.

3. DESCRIPTION OF THE ALGORITHM 3.1 Link-based shortest path algorithm Let a network consist of a set of nodes and a set of links connecting the nodes. The nodes are also referred to as vertices or points. The links are also called arcs, edges, and branch. A network can be represented by the notation G=(N,A) , where N is the set of nodes and A the set of links of the network G . Let LC(i,j) be the nonnegative link cost required to travel from node i to node j and LEC(o,i) be the link end cost, or minimum path cost from origin to node i through link(o,i) which refer to the directed link leading from node o to node i .TP[link(o,i),link(i,j)] is the turn penalty which implies the additional cost at node i between from link(o,i) to link(i,j) when turning prohibitions exist as shown in Figure 3. With these notations we can define the link-based shortest path optimality condition with turn penalty as follows. LEC(o,i)+TP[link(o,i),link(i,j)]+LC(i,j)≤LEC(i,j) , FORALL o,i,j ∈ N (1)

Figure 3. Basic concept of the link-based shortest path algorithm The optimality condition in equation (1) has the unique solution, because we can easily take over the optimality theorem already proved for node-based case by simply replacing link costs by the sum of link costs and turn penalty, TP. The optimality theorem for node-based searching method is explained fully in Potts & Oliver(1972). In the paper, instead of preceding nodes in conventional shortest path algorithms, preceding links are used to memorize the track of shortest path. The preceding link from node i to node j , PL(i,j) , of Figure 3 is defined as PL(i,j)=link(o,i) ie. PL(i,j) is the link immediately before link(i,j) on the shortest path. (2)

Based on the equation (1) and (2), the steps of link-based shortest path algorithm are as lists. Let R be the set of all labeled links, Rºset of unlabelled links and O the set of all connected nodes with origin. [Step 1] Label the link(h,i) , connecting origin node h with node i , ∈ O

1430

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

enter link(h,i) into set R , i.e. R= { link(h,i) } set LEC(h,i)=LC(h,i) and LEC(h,j)=INF ∀ j ≠ i PL(h,i)= Φ [Step 2] Find an unlabelled link If LEC(i,j)+TP[link(i,j),link(j,k)]+LC(j,k)≤LEC(j,k) Then, LEC(j,k)=LEC(i,j)+TP[link(i,j),link(j,k)]+LC(j,k) PL(j,k)=link(i,j) [Step 3] Label the link(i,j) Add the link(i,j) to the set R , and delete it from the set Rº [Step 4] If Rº= Φstop, otherwise go to [Step 2]. The main advantage of the algorithm described above is that it is easy to code and possible to consider the turn restrictions on the way of shortest path searching. The algorithm is very similar to the conventional tree building algorithms. The only difference is that it is link-based searching, not node-based. Thus with a little modification, the conventional algorithms can be used. Now consider computational experience of the algorithm. A time taken by an algorithm, which is also called the running time of the algorithm, depends on the topology of the network. A time requirement for an algorithm is a function of the problem size and specifies the largest amount of time needed by the algorithm to solve any problem instance of a given size. In other words, the time requirement measures the rate of growth in solution time as the problem size increases. To compare the efficiency of the shortest path algorithms, we use the notation,O(n) , with the network parameter n . O(n) means the maximum time requirement to solve the problem and the complexity of the algorithm (see Ahuja,et.al.,(1993) in more detailed). With the notation O(n) , we can compare the efficiency of the algorithms. The conventional tree-based algorithm has the time requirement of O(n²) with parameter n, number of nodes. The vine-based algorithm, however, has O(n³) . On the other hand, if the example network composed of n node and l links has bi-directional rectangular topology, there exists a relationship between n and l; l=4[ n- √ n ] . Because the link-based algorithm presented in the paper is based on links, not nodes, it has O(l²= [ 4(n- √ n) ]²) of time requirement, which is greater than tree-based algorithm but less than the vine-based one. This implies that the algorithm dose not requires too much running time to find the path, compared with the existing algorithms. In special when it applies to a network with turn prohibitions or to an integrated network with several transportation modes on it, less computing time is required because it does not need to expand the network. 3.2 Formulation of a shortest path algorithm with path overlap The shortest path algorithm proposed in this paper generates several dissimilar paths by adopting both the link-based shortest path technique of section 3.1 and the link penalty method for finding dissimilar ones. The algorithm builds new path based on the degree of overlapping between each path and travel cost, and stops building when the degree of overlapping ratio exceeds its criterion. First let some new variables be denoted. rs ln length of n-th path for origin-destination pair rs

1431

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

rs pn

n-th path for origin-destination pair rs rs rs path set for origin-destination pair rs ; P rs ={ pn , ln }

P rs olkrs/ n rs k

overlapping length of n-th path to the length of k -th path for origin-destination pair k = n − 1, n − 2,...,1

rs , ∀P ∈ P rs ,

Op

rs k /n

degree of overlap between the length of n-th path and the length of k -th path for

origin-destination pair rs ; Opkrs/ n =

olkrs/ n , ∀Pkrs ∈ P rs , k = n − 1, n − 2,...,1 rs ln

Op
Oz

α

maximum degree of overlap 1 link penalty; Oz = [ ]α Op positive parameter

With these variables, we can describe the shortest path algorithm as, [Step0] Initialization set Op and n = 1 [Step1] With the link-based shortest path algorithm, find the first shortest path rs rs rs and add l n , pn to path set; P rs = {Pnrs , l n } [Step2] Link cost update (Link penalty) new link costs of the n-th path = link costs of the n-th path * Oz [Step3] Path search and Overlapping ratio calculate (3.1) n = n + 1 rs (3.2) with the link-based shortest path algorithm, find the n -th shortest path; { Pnrs , l n }

(3.3) degree of overlap : Op

rs k/n

ol krs/ n = rs , ∀Pkrs ∈ P rs , k = n − 1, n − 2,...,1 ln

[Step4] Convergence test rs if Opk / n > Op , then stop rs otherwise, add { Pnrs , l n } to P rs and proceed [Step2]

In Step 2 of the algorithm, the costs of links belonging to the shortest path are modified by multiplying link penalty of Oz , which is a function of degree of path overlap( Op ). Thus only one path is generated if all paths are allowed of overlapping each other ( Op = 1.0 ), while more than one path are generated if the value of Op is below 1.0.

4. NUMERICAL EXAMPLES

Some numerical examples are presented to illustrate the performance of the algorithm; the first is for verifying whether the proposed link-based algorithm in section 3.1 obtain optimal path or not, and the others for comparing and assessing the proposed algorithm.

1432

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

4.1 Successive turn-prohibited network

The first example network is the one proposed by Kim (1998) as shown in Figure 2, this network includes 9 directed links, 8 nodes and 2 banned left-turns which impose turn penalties. The number of links and link travel times are on the link in Figure 2, values in parenthesis are link travel time. Turning penalties are given in Table 1. Table 1. Turn penalties of the first example turn penalty ②→⑤→⑥ 900 ③→⑥→ⓢ 900 Table 2 describes in detail the procedure for searching shortest path from origin r to destination s. Figures in the table show that we obtain exact optimal path and its cost of 12. From the result, we find that link-based algorithm can easily search the shortest path under considering banned turns, which may not be accounted in conventional vine-based algorithms Table 2. Results of the first example
Number of link 1 2 3 4 5 6 7 8 i r 1 1 2 2 3 4 5 5 9 6 6 j 1 2 4 3 5 6 5 6 6 s s LC(i,j) 1 1 2 2 3 3 4 3 3 2 2 LEC(i,j) 1 2 (1+1) 3 (1+2) 4 (1+1+2) 5 (1+1+3) 7 (1+1+2+3) 7 (1+2+4) 908 (1+1+3+900+3) 10 (1+2+4+3) 909 (1+1+2+3+900+2) 12 (1+2+4+3+2) 1–3-7-8–9 PL(i,j) labelled link set(R ) 0 1 1 2 2 4 3 5 7 6 8 1 1,2 1,2,3 1,2,3,4 1,2,3,4,5 1,2,3,4,5,6 1,2,3,4,5,6,7 1,2,3,4,5,6,7,8 1,2,3,4,5,6,7,8 1,2,3,4,5,6,7,8,9 1,2,3,4,5,6,7,8,9 link set for path 1 1,2 1,3 1,2,4 1,2,5 1,2,4,6 1,3,7 1,2,5,8 1,3,7,8 1,2,4,6,9 1,3,7,8,9 12

link set for shortest path

shortest path cost ( r → s )

4.2 Sioux Falls network The second test is performed with the Sioux Falls network, which has 24 nodes and 76 links. This paper just considers only one origin-destination pairs from node 1 to node 20 for clear comparison between the method proposed in this paper and existing k-shortest path method. The specifications for the network are shown in [Appendix A].

Figure 4 shows explicit difference between the k-shortest path algorithm and the proposed algorithm. Both algorithms generate 5 different paths. The k-shortest path algorithm finds very similar paths as we expect, while the proposed algorithm produce relatively dissimilar paths because it considers the degree of path overlap in searching steps. So the paths derived

1433

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

from the k-shortest algorithm are concentrated, but the paths from the proposed method are scattered over the whole network. Table 3 summarizes the values of path cost and links on the path. The first two paths have the same values of path costs for all method, but the rest three path costs of the proposed algorithm are higher than those of k-shortest path one because it generates the paths in order of degree of path overlap, not in order of path costs. From the point of view in travel information for drivers, the similar paths may occur to vehicle concentration to some specific routes, which leads to oversaturation of traffics. In such environments dissimilar paths generated from the proposed method may be more efficient to spread vehicles over the network.
3 1 1 2 5 8 3 6 4 9 13 23 21 7 35 10 31 9 24 25 33 12 36 11 32 27 10 29 51 30 34 40 28 43 17 56 60 53 37 38 14 41 42 71 70 23 72 63 73 74 13 39 24 75 76 66 21 64 69 65 73 68 62 20 13 39 74 24 75 76 66 21 64 69 65 68 62 20 22 46 67 59 61 23 72 63 44 15 45 42 71 70 22 57 19 58 37 38 14 41 46 67 59 61 44 15 45 57 19 53 58 34 40 28 43 49 52 30 17 56 60 26 48 16 50 22 47 55 18 12 36 8 20 18 54 33 11 32 27 10 29 51 49 52 25 26 48 16 50 11 5 12 16 19 17 7 7 35 10 31 9 24 22 47 55 18 15 6 3 6 4 2 14 2 1 1 5 8 4 9 13 23 21 8 20 18 54 11 5 12 16 19 17 7 15 6 4 3 2 14

(a) Paths from k-shortest path method

(b) Paths from the proposed method

Figure 4. Comparison between the methods Paths 1st path 2nd path 3rd path 4th path 5th path Table 3. Generated paths and each path costs k-shortest path method The proposed method Link set Path cost Link set Path cost 2-7-37-39-75-64 1260 2-7-37-39-75-64 1260 1-4-16-22-50-56 1320 1-4-16-22-50-56 1320 1-4-16-22-49-53-59 1320 2-6-9-13-25-30-53-59 1440 2-6-9-13-25-30-53-59 1440 2-7-36-34-41-46-68 1500 2-7-37-39-75-65-68 1440 2-6-10-32-28-45-59 1680

Table 4, Table 5 and Figure 5 show some results of the proposed method when left-turn

1434

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

prohibitions at node 11, node 14 and node 23 exist, with the value of 50% of path overlap. Table 4 demonstrates that five dissimilar paths are also generated, and that last 2 paths are different from those of paths in Table 3 due to turning restrictions. We note here that the 5th path has U-turn movement at node 24 because of left-turn prohibition at node 23. Path overlapping ratios among paths calculated from the method are shown in Table 5. Each figure in the table is below 0.5 except for diagonal elements, since the maximum degree of path overlap sets 50%. Figure 5 depicts the number of paths produced from the method with varying the degree of path overlap ( Op ) from 0.1 to 1.0. There are maximum 5 paths through Op =0.4 to 0.7 and only one path when Op =1.0 that all paths are possible to be overlapped, as we expect. Figure 6 shows the number of paths with varying the value of parameter ( α ) in the link penalty ( Oz ). Table 4. Generated paths and path cost (when Op = 0.5 and α =1.8) Link set Path cost 2-7-37-39-75-64 1260 1-4-16-22-50-56 1320 2-6-9-12-25-30-53-59 1440 2-7-36-32-28-46-68 1560 2-6-10-34-42-73-76-72-68 1860 U-turn at node 24 Table 5. Matrix of degree of path overlaps (when Op = 0.5 and α =1.8) 1 2 3 4 5 1.000 0.000 0.167 0.333 0.167 0.000 1.000 0.000 0.000 0.000 0.125 0.000 1.000 0.125 0.250 0.286 0.000 0.143 1.000 0.286 0.111 0.000 0.222 0.222 1.000

Paths 1st path 2nd path 3rd path 4th path 5th path

Paths 1 2 3 4 5

Figure 5. Number of paths with varying Op Figure 6. Number of paths with varying α
7 6 5 4 3 2 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Op
8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 Op=0.5 7 8 Op=0.8 9 10 alhpa

Op=0.2

4.3 Expansion to dynamic case

The proposed algorithm here expands to a dynamic one, in which each link cost is variable as time elapses. This dynamic shortest path algorithm adopts the method of Jayakrishnan et al. (1995), who presented a link-based time-expanded network technique corresponding to static

1435

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

network. Step 1 and Setp 3 in section 3.2 are replaced with this dynamic algorithm for generating dynamic shortest paths. A numerical result applying to Sioux Fall network is given in Appendix B, where each link cost is generated at random with mean and variance.

5. CONCLUSION

In this paper, a new shortest path algorithm capable of considering path overlap and turn prohibitions was proposed and tested, which provided efficient dissimilar alternative paths. This algorithm builds paths based on the degree of overlapping ratio and does not need network expansion to find the shortest path because it searches the paths with link-end cost, not node cost. After verifications of the algorithm with some examples, we also expanded it to dynamic one and tested. From the results of some numerical examples, we may conclude that the algorithm is more efficient for finding several dissimilar shortest paths than others. The algorithm proposed in the paper may be applied to a variety of network analyses. In first, it could be adopted in the field of travel information such as providing diverse routes for drivers. Secondly, the algorithm generates dissimilar paths so that it could alleviate the problem of IIA (Independence of Irrelevant Alternatives) in logit-type stochastic assignment. Lastly, it can be also used for solving easily multi-mode traffic assignment, which should consider transfer behaviors of users.

REFERENCES a) Books and Books chapters

Ahuja,R.K., T.L. Magnanti, J.B. Orlin(1993) Network Flows: Theory, Algorithms and Applications, Prentice Hall Bellman,R.E.(1957) Dynamic programming, Princeton University Press, Princeton Potts,R.B., R.M. Oliver(1972) Flows in transportation networks, Academic press
b) Journal papers

Akgun,A.,Erkut,E.,Batta,R. (2000) On finding dissimilar paths, European Journal of Operational Research 121, 232-246 Caldwell,T.(1961) On finding minimum routes in a network with turn penalties, Commum, ACM4, 107-108 Dijkstra, E. W.(1959) “A note on two problems in connection with graphs”, Numer.Math.1, 269-271 Jayakrishnan,R.,W.K.Tsai, A.Chen (1995) A dynamic traffic assignment model with traffic-flow relationships, Transportation Research (C), Vol3, 51-72 Kim,I.(1998) Development of a modified vine building shortest path algorithm for ATIS, Journal of Korean society of transportation, Vol.16, No.2, 157-167 Shier, R.D.(1979) On algorithms from finding the k shortest paths in a network, Networks, V ol.9, 195-214 Yen J.Y.(1971) Finding the K shortest loopless paths in a network, Management Science, Vo l 17, No. 11, 712-716

1436

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

c) Papers presented to conferences

Barra, T. et al.(1993) Multidimensional Path Search and Assignment, 21st PTRC Summmer Annual Conference Scott,K., Pabon-Jimenez,G.,Bernstein,D. (1997) Finding alternatives to the best path, Presented at the 76th Annual Meeting of the Transportation Research Board, Washington,DC
[Appendix A] Specifications of Sioux Fall network Link From node To node Link cost 1 1 2 360 2 1 3 120 3 2 1 360 4 2 6 120 5 3 1 120 6 3 4 300 7 3 12 300 8 4 3 300 9 4 5 180 10 4 11 300 11 5 4 180 12 5 6 180 13 5 9 120 14 6 2 120 15 6 5 180 16 6 8 180 17 7 8 180 18 7 18 300 19 8 6 180 20 8 7 180 21 8 8 180 22 8 16 120 23 9 5 120 24 9 8 180 25 9 10 120 26 10 9 120 27 10 11 300 28 10 15 240 29 10 16 180 30 10 17 180 31 11 4 300 32 11 10 300 33 11 12 180 34 11 14 240 35 12 3 300 36 12 11 180 37 12 13 360 38 13 12 360

Link 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

From node 13 14 14 14 15 15 15 15 16 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 20 21 21 21 22 22 22 22 23 23 23 24 24 24

To node 24 11 15 23 10 14 19 22 8 10 17 18 10 16 19 7 16 20 15 17 20 18 19 21 22 20 22 24 15 20 21 23 14 22 24 13 21 23

Link cost 120 240 240 180 240 240 180 180 120 180 120 180 180 120 180 300 180 360 180 180 240 360 240 180 240 180 120 180 180 240 120 240 180 240 120 120 180 120

1437

Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 1426 - 1438, 2005

[Appendix B] Generated dynamic paths and cost (when Op = 0.5 and α =1.8) Paths Time intervals Link set 1 2 3 7 1st path 8 37 13 39 15 75 18 64 1 1 6 4 2nd path 8 16 11 22 13 50 16 56 1 1 6 4 8 15 3rd path 11 13 13 25 15 30 18 53 21 59 1 2 3 6 8 9 4th path 13 12 17 16 20 22 22 50 26 56 1 2 3 6 8 10 5th path 13 34 17 42 20 73 22 75 26 64

Path cost 1247

1258

1493

1647

1666

1438…...

Similar Documents

Premium Essay

Indian Streams Research Journals

...Indian Streams Research Journal Vol.2,Issue.IV/May; 12pp.1-4 Asst. Prof. Rajani Kota Research Papers ISSN:-2230-7850 SOFTWARE DEVELOPMENT TECHNIQUES Asst. Prof. Rajani Kota Dept. of Computer Science A.R.Burla Womens' College, Solapur. Abstract Software development is the set of activities and processes for programmers that will eventually result in a software product. This may include requirement analysis, software design, implementation, testing, documentation, maintenance and then describing computer programs that meet user requirements within the constraints of the environment. It is a structure imposed on the development of software product. Software development is the most important process in developing a Software/tool. The successful execution of the project highly depends on the techniques used to develop the model. Software development technology has an under the model-explicit or implicit-of the development process. In order to understand more about the development process and the methodologies, we abstract from these. The perspective chosen for the abstraction include models developed during the process and the kind of abstraction involved in the techniques of the process. I .INTRODUCTION Software is a one kind of system or we can say the package which is used in many organization. It is a general term for the various kinds of programs used to operate computers and related devices. It can be thought of as the variable part of a computer and......

Words: 3338 - Pages: 14

Premium Essay

Indian Streams Research Journals

...Indian Streams Research Journal Vol.2,Issue.IV/May; 12pp.1-4 Asst. Prof. Rajani Kota Research Papers ISSN:-2230-7850 SOFTWARE DEVELOPMENT TECHNIQUES Asst. Prof. Rajani Kota Dept. of Computer Science A.R.Burla Womens' College, Solapur. Abstract Software development is the set of activities and processes for programmers that will eventually result in a software product. This may include requirement analysis, software design, implementation, testing, documentation, maintenance and then describing computer programs that meet user requirements within the constraints of the environment. It is a structure imposed on the development of software product. Software development is the most important process in developing a Software/tool. The successful execution of the project highly depends on the techniques used to develop the model. Software development technology has an under the model-explicit or implicit-of the development process. In order to understand more about the development process and the methodologies, we abstract from these. The perspective chosen for the abstraction include models developed during the process and the kind of abstraction involved in the techniques of the process. I .INTRODUCTION Software is a one kind of system or we can say the package which is used in many organization. It is a general term for the various kinds of programs used to operate computers and related devices. It can be thought of as the variable part of a computer and......

Words: 3338 - Pages: 14

Free Essay

Indian Streams Research Journals

...Indian Streams Research Journal Vol.2,Issue.IV/May; 12pp.1-4 Prof. N. G. Alvi Research Papers ISSN:-2230-7850 “Dynamic Load and Stress Analysis of a Crankshaft” Dr. S. V. Deshmukh Prof.& Head, Bapurao Deshmukh College of Engineering, Sevagram, Wardha, India Ram.R.Wayzode Lecturer, Suryodaya College of Engineering & Technology, Nagpur, India Prof. N. G. Alvi Prof,Suryodaya College of Engineering & Technology, Nagpur,India ABSTRACT In this study a dynamic simulation was conducted on a crankshaft from a single cylinder four stroke engine. Finite element analysis was performed to obtain the variation of stress magnitude at critical locations. The pressure-volume diagram was used to calculate the load boundary condition in dynamic simulation model, and other simulation inputs were taken from the engine specification chart. The dynamic analysis was done analytically and was verified by simulation in ADAMS which resulted in the load spectrum applied to crank pin bearing. This load was applied to the FE model in ABAQUS, and boundary conditions were applied according to the engine mounting conditions. The analysis was done for different engine speeds and as a result critical engine speed and critical region on the crankshaft were obtained. Stress variation over the engine cycle and the effect of torsional load in the analysis were investigated. Results from FE analysis were verified by strain gages attached to several locations on the crankshaft. Results......

Words: 3588 - Pages: 15

Premium Essay

Operation Research

...11-1 Inventory Management 11-2 Inventory Management CHAPTER Operations Management 11 William J. Stevenson Inventory Management 8th edition McGraw-Hill/Irwin Operations Management, Eighth Edition, by William J. Stevenson Copyright © 2005 by The McGraw-Hill Companies, Inc. All rights reserved. 11-3 Inventory Management 11-4 Inventory Management Types of Inventories Inventory: a stock or store of goods Independent Demand A Dependent Demand Raw materials & purchased parts • Partially completed goods called work in progress • • Finished-goods inventories • B(4) C(2) D(2) E(1) D(3) F(2) (manufacturing firms) or merchandise (retail stores) Independent demand is uncertain. Dependent demand is certain. 11-5 Inventory Management Types of Inventories (Cont’d) (Cont’ 11-6 Inventory Management Functions of Inventory • • Replacement parts, tools, & supplies Goods-in-transit to warehouses or customers • • • • To meet anticipated demand To smooth production requirements To decouple operations To protect against stock-outs 11-7 Inventory Management Functions of Inventory (Cont’d) (Cont’ To take advantage of order cycles To help hedge against price increases To permit operations To take advantage of quantity discounts 11-8 Inventory Management Objective of Inventory Control • • • • • To achieve satisfactory levels of customer service while keeping......

Words: 1284 - Pages: 6

Free Essay

Operation Research & Methods

...Operational Research Models and Methods in CIM1 Abstract : Many models and methods of Operational Research can be adapted for industrial applications. In this chapter, we show on one hand the main problems of a manufacturing system and, on the other hand, how they can be ranged in a hierarchical order, derived from a CIM architecture (from the strategic decisions to the production constraints). Then, we present an Operational Research tool for solving each of these problems. 1 Introduction Flexible Manufacturing Systems (FMS) are nowadays installed in the mechanical industry, especially in car factories. However, the market constraints impose to always improve the production system and the whole production organization. The concepts developed by Taylor and applied at the beginning by Ford are progressively abandoned and replaced by the Just-In-Time concept and the Computer Integrated Manufacturing philosophy (CIM). One of the aims of the CIM philosophy is to provide an integrated information system which avoids the rigid separations between the different functionalities of a complete production system. With such integrated information systems, the loss of time on one hand between the customer order and the part delivery, on the other hand between the product design and its manufacture will be drastically reduced. To understand the complete production system, it is relatively easy to find in the scientific literature excellent general books explaining the different......

Words: 5165 - Pages: 21

Free Essay

Operation Research

...Cases in Operation Management Semester 4 PGDBA (Operations) Page 1 Question-: 1 The “Quality Auto Works” is a manufacturer of auto parts. All the auto parts being manufactured in the industry are required to be phosphated for surface protection. Presently other small units are done this phosphated work. Quality Auto Work is now thinking of installing its own phosphating plant and is interested about knowing about following. (A) Should the install new plant or continue the present practice of subcontracting? For finding out whether the firm should do the phosphating work by own or it should contract other for the some one, we have to compare both the cost which are as follows. Annual Cost of subcontracting Cost of purchase =6.25x12000x12 =9, 00,000/- Cost of Transportation Total Cost =1800x12=21600/- =9, 21,600 Annual cost for installing own phosphating plant: Installation cost of plant: 2, 80,000x0.2452= 68,656/- Labor cost Benefit to labor Power Raw material : 8000x12 = : 96000x40/100 = : 12,000x0.23x12 = : 12000x0.45x12 = 96,000/- 38,400/- 33,120/- 64,800/- Total cost of installing = 3, 00,976/- ......

Words: 826 - Pages: 4

Premium Essay

International Journal of Financial Research

...www.sciedu.ca/ijfr International Journal of Financial Research Vol. 3, No. 3; July 2012 The Strategic Transformation of Automobile Industry in China Som Techakanjanakit School of Management, Wuhan University of Technology 122 Luoshi Road, Hongshan District, Wuhan 430070, Hubei, China Tel: 86-186-7239-9237 E-mail: som7125@hotmail.com Meifang Huang (Corresponding author) School of Economics, Wuhan University of Technology 122 Luoshi Road, Hongshan District, Wuhan 430070, Hubei, China Tel: 86-186-7239-9537 Received: May 28, 2012 doi:10.5430/ijfr.v3n3p8 Abstract In the past few years, the global automobile industry is developing difficultly because of the influence from the financial crisis. In contrast, China's automobile production and sales are still having a blowout type growth, and jumped into the world's largest automobile production and sales market. At the same time, Chinese automobile companies continue to deepen and join with international brand cooperation; independent research and development of the independent brand production, and their technical also get greatly strengthened. Similarly, in the tide of industrial upgrading and international acquisitions, strategic transformation era of Chinese automobile industry has gradually started. This paper based on the world economic crisis brought both challenge and opportunity to the automobile industry in China, comprehensively analysis China's automobile industry development present situation and development......

Words: 5828 - Pages: 24

Premium Essay

Operations Research

...PRINCIPLES AND APPLICATIONS OF OPERATIONS RESEARCH * Jayant Rajgopal Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania ABSTRACT This chapter will provide an overview of Operations Research (O.R.) from the perspective of an industrial engineer. The focus of the chapter is on the basic philosophy behind O.R. and the so-called “O.R. approach” to solving design and operational problems that industrial engineers commonly encounter. In its most basic form, O.R. may be viewed as a scientific approach to solving problems; it abstracts the essential elements of the problem into a model, which is then analyzed to yield an optimal solution for implementation. The mathematical details and the specific techniques used to build and analyze these models can be quite sophisticated and are addressed elsewhere in this handbook; the emphasis of this chapter is on the approach. A brief review of the historical origins of O.R. is followed by a detailed description of its methodology. The chapter concludes with some examples of successful real-world applications of O.R. * Maynard's Industrial Engineering Handbook, 5th Edition, pp. 11.27-11.44. 1.1 INTRODUCTION Although it is a distinct discipline in its own right, Operations Research (O.R.) has also become an integral part of the Industrial Engineering (I.E.) profession. This is hardly a matter of surprise when one considers that they both share many of the same objectives, techniques and application......

Words: 11680 - Pages: 47

Free Essay

Operations Research

...COMPUTATIONAL COMPLEXITY OPERATIONS RESEARCH Pooja Punjabi Manash Hazarika INDIAN INSTITUTE OF MANAGEMENT, KOZHIKODE COMPUTATIONAL COMPLEXITY Computational Complexity is a measure of the computational time taken by a particular algorithm. In a scenario where there are multiple algorithms available for a particular problem, the effectiveness of any particular algorithm is gauged on the basis of the time constraint. This is done by breaking the algorithm into its basic steps and then taking a count of each of them. Hence greater is the number of steps, greater is the complexity. Now for example, if we take two 5 bit binary numbers and XOR them, the number of steps taken is 5 and if the same process is repeated for a 100 bit binary number, the number of steps goes up to 100. The algorithm employed in either case is the same; the complexity is given by the size of the numbers. When we say size of a number n, it is defined as the number of binary bits which are required to denote ‘n’ in base 2. For example, 5 in base 10 when expressed in binary takes the form 101, thereby giving n = 3. Similarly 20 is given by 101002 which makes n = 5. Now if we XOR any two numbers each of size n=b, the number of steps taken will be ‘b’. Hence we can say that XORing those numbers has computational complexity of order ‘b’ which is denoted by O(b). This can be applied to even simpler applications like addition wherein if we are to add two n digit numbers, the minimum number of steps taken......

Words: 3078 - Pages: 13

Premium Essay

Operations Research

... it's not just about price it's also about what the shopper gets for her money. By comparison, national brands operate on a different playing field, one that is far more costly. Their goal is to be in every store in the country. That means they spend huge sums of money on advertising, merchandising and promotion. Store brands are not cheaper they are just less expensive to market than national brands are. That's good news for consumers. Store Brands: The Smarter Choice Exactly how much do consumers save? Last year, American shoppers who reached for the store brand version of their favorite food and non-food grocery products rather than the national brand enjoyed an estimated $32 billion in annual savings. Ongoing research by PLMA consistently reveals that on a trip to a typical supermarket shoppers save about one-third on basic grocery and household items by choosing store brands over national brands. The difference is the so-called marketing tax, which consists of advertising and promotional costs incurred by national brand makers that are then passed on to consumers in the form of higher prices. Big CPG companies spend more than $21 billion annually on advertising media. They earmark about 25 cents of every dollar to build brand equity. They do this to satisfy shareholders and Wall Street analysts who place a premium on the perceived value of their brands. A store brand manufacturer does not have these costs. But it buys the......

Words: 34880 - Pages: 140

Premium Essay

International Journal of Education and Research

...International Journal of Education and Research Vol. 1 No. 10 October 2013 The effects of Cell phone use on the study habits of University of Zimbabwe First Year Faculty of Arts students. Leslei Kahari ABSTRACT The objective of this study is to examine the effects of cell phone use on the study habits of University of Zimbabwe 1st year Faculty of Arts students. The research was carried out using questionnaires distributed to 200 students who own cell phones .The questionnaires collected demographic information about the respondents, cell phone type preferences, uses of cell phones during study, predominant usage during study and information about challenges facing students in using mobile phones for study purposes. The results showed significant gender differences in several aspects of cell phone use .The results also revealed that cell phone use has negative and positive effects on the study habits of university students depending on usage patterns .The study concluded that despite the challenges faced by students ,cell phones unlike other educational innovations are firmly rooted in the society in which education and institutions are part of and ignoring the use or applications of this technology would be ill-advised. Key words: Cell phone, study habits, University of Zimbabwe INTRODUCTION This study investigates the effects of cell phone use during study on the study habits of University of Zimbabwe 1st year Faculty of Arts students. Many students starting......

Words: 5810 - Pages: 24

Free Essay

Operations Research

...Year | 2015-16 | Academic Term | T1☐ T2☐ T3☐ T4☐ T5☐T6☐ | Functional Areas | OPERATIONS MANAGEMENT | Core ☐ Elective x☐x | Title | Quantitative Methods II | Abbreviation | QM-II | Course Coordinator | Prof. RAVI SHANKAR | Teaching Members | | Course Revision Record Version | Version Date | Recommendation | 1 | 05 Sept 2015 | | Credits | 3 | Contact Hours | 30 | Learning Hours | 60 | Office Hours | 30 | Contact Details | 09811033937 | Course eMail | r.s.reaches@gmail.com | Course Descriptor Course Overview(200 words) | Quantitative Methods-II, focuses on ‘Operations Research’ tools which helps in solving problems in different functional domain of business. It also helps to optimize business operations/processes. The Quantitative Method-II tools act as aids to decision makers to take best decision for effective & efficient use of resources which ultimately lead to profit maximization or to achieve multiple goals or objective. | Course must be aligned with a strategic objective of the program Prerequisites/Co-requisites | Quantitative Methods I | Learning Objectives | To learn basic optimization techniques and their managerial applications with a focus on methodologies such as Linear Programming, Transportation models, Assignment Models, Transhipment Models, Games Theory, Queuing Models, Goal Programming, Integer Programming, Non-linear Programming, Simulation and Decision Theory. | Learning objectives must be aligned with......

Words: 1342 - Pages: 6

Premium Essay

Operations Research

...Business Research Methods (BRM) Project submission on Meru Cabs: Why is this cab service provider losing market share? Submitted by: Group 8 Submitted by: Group 8 Aditi Chaudhary | PGP/19/183 | Alka | PGP/19/186 | Alla Bharath Reddy | PGP/19/187 | Avishek Pandey | PGP/19/196 | Miranda Boro | PGP/19/207 | Md. Talha | PGP/19/208 | Declaration "We hereby declare that this submission is our own work and that, to the best of our knowledge and belief, it contains no material previously published or written by another person nor material which has been accepted for the award of any other degree or diploma of the university or other institute of higher learning, except where due acknowledgment has been made in the text.” Contents Introduction 1. Business Research problem 2. Why did we select it? 3. Introduction 4. Research Methods 5. Information regarding collection of data a. Quantitative b. Qualitative 6. Research Methodology c. Survey d. Focus Groups Discussions 7. Expected analysis and outcome Conclusion Business Research problem: “Why is Meru cabs losing its market share? “ The overall bookings are very less on Meru as compared to its competitors and it is lagging behind low-cost cab service providers such as Ola, Uber and Taxi for sure. Our present research proposal addresses this issue and tries to find out the reasons behind the same. Why did we select it? Many of our team......

Words: 1548 - Pages: 7

Premium Essay

Operation Research

...other related topic from internet such as definition of oil and gas , the cause of oil and gas and to know about the advantages and disadvantages of oil and gas 2. The time available * I did the research after class finish and completed the task given usually at night 3. The financial resources at disposal * I spend my money to print out the report and for references I just took from internet and library. There is no cost for references. 4. Knowledge and expertise in the areaMy major is management. I have learned International Economic and Oil and Gas Economic in class. I learned the economic growth and what are the cause of economy fall. | STEP 7 | Double-check | 1. I am interested with the chosen topic. I am curious how tough the oil price can impact the economy. 2. I agree with the objective I have been stated. With the specific objective, easier to me to learn the specific impact of low oil price on economy. 3. I have adequate resources to complete the task. I am using internet (website) and book. And lecturer as a supervisor to guide me to complete the task. 4. I been learn economic and microeconomic subject in the class so that easier to me to do the research. And I am refer to lecturer who teach me economic subject to help me in this research. |...

Words: 402 - Pages: 2

Premium Essay

Operations Research

...weekly meeting will be scheduled at which time students may ask questions, discuss homework exercises, etc. Attendance at this meeting is optional. Grading System • There will be 2 examinations, one at the middle of the course, and one at the end. • Homework will be assigned each week, but this will not be given to the instructor to be graded. Students are encouraged to work together on homework assignments. • There will be a short (multiple choice) quiz each week which tests whether you have understood the homework assignment. Only the best 10 quizzes for each student will be used in computing the course grade. Midcourse Examination Final Examination Weekly Quizzes (best ten) 30% 50% 20% page 3 What is “Operations Research”? • other names: management science, decision science • application of information technology for decision-making • designing systems to operate in the most effective way or deciding how to allocate scarce human resources, money, equipment, or facilities • closely related to several other fields: o applied mathematics, o computer science, o economics, o industrial engineering, and o systems engineering page 4 Typical problems faced by an O.R. practitioner: • In what sequence should parts be produced on a machine in order to minimize the change-over time? • How can a dress manufacturer lay out its patterns on rolls of cloth to minimize wasted material? • How many elevators should be installed in a new......

Words: 508 - Pages: 3

IMDb: 7.9 265,165 S5E1 The Flash - Season 5 | Written Updates | Virtual DJ