


Research Efficiency in modern industrial operations requires that resources be deployed in an optimal manner. This has resulted in extensive work in operations research on resource allocation with a focus on optimal or nearoptimal planning. Facility location applications are concerned with the placement of one or more facilities/routes in a way that optimizes a specified objective, such as minimizing transportation cost, providing equitable service to customers, capturing the largest market share, etc. These problems give rise to challenging combinatorial problems. The research on locating logistics spans many fields such as operations research/management science, geography, computer science, mathematics, etc. Our project activities have grown in two seemingly different directions as our research activities in the past years have been greatly influenced by the problems of our industrial sponsors. We have also made great progress in various fundamental problems in discrete optimization which include vehicle routing problems, network facility center locations, network flows etc. In the past two years, we have worked with two industrial partners: Mobile Knowledge and BC Ferries. Mobile Knowledge offers advanced GPS, wireless, and mobile data communications technology to customers in a wide variety of markets for enhanced fleet management applications. We are continuing to invest considerable time and resources to generate efficient routes for scheduling services in city networks, keeping an eye on the road conditions round the clock for realistic travel times. For BC Ferries, we studied the effectiveness of their current schedules to the gulf islands, given the passenger demands.
The Pickup and Delivery Problem with Time Windows (PDPTW) deals with finding a set of routes for serving a set of transportation requests. Each transportation request is defined by a pickup location, a delivery location and a load. Each location has a time window within which it has to be served. A certain number of vehicles is activated at the beginning of a day, but if a new request cannot be feasibly served by these active vehicles, a new vehicle is added. The dynamic PDPTW deals with the problem in a dynamic (realtime) environment where not all of the requests are known in advance. The methodology used for solving the dynamic PDPTW is an online approach  the problem is being solved repeatedly as new requests become known. Future requests are not predicted nor stochastically modeled, i.e., the algorithm optimizes only over known requests. Very large scale neighborhood (VLSN) search algorithms are known to produce good solutions for various practical optimization problems [1]. The neighborhood of a solution consists of set of solutions that may be derived by applying certain changes to the solution. Many simple local search procedures and many metaheuristics are neighborhood search procedures. We have used the concept of ‘improvement graph’ to explore the neighborhood for local search [1]. The improvement graph consists of a set of nodes linked together by edges. Each scheduled jobpair corresponds to a node in the improvement graph. This is called a 1node. In general a knode is a node in the improvement graph corresponding to k jobpairs. All 1nodes are present in the improvement graph but only select subsets of all knodes make it to the improvement graph. Because improvement nodes correspond to scheduled jobpairs, it makes sense to talk about a node's route. A node route in an improvement graph is just the route in which its associated jobpair(s) is scheduled. There is an edge between two nodes provided they are associated with different routes. The edges are directed and are used to store two types of weights, a path weight and a cycle weight. The cycle weight is defined to be the change in the objective function when the jobpair associated with the destination node is removed from its route and the jobpair from the the source node is added to the destination route (at the best possible location, using a greedy algorithm). Note that the source jobpair is inserted into the destination route after the destination jobpair is removed. The path weight is defined in exactly the same way, except that the destination jobpair is not removed from its route. With these definitions, it is easy to see that a routedisjoint negative cycle in the improvement graph corresponds to a better schedule. The search for a negative cycle starts and ends at the same node; while this search is performed it is possible to make use of the path weight to find improvements that do not start and end at the same node. Therefore the search for improvements is reduced to finding routedisjoint negative paths and/or cycles in the improvement graph. Unfortunately, because of the route disjointness requirement, this problem is NPhard. The algorithm we use to locate negative cycles is a considerable improvement of the method described in [1]. Our group members are active in this broad research area. Combining VLSN search and variable neighborhood search produced superior results in some classes of optimization problems considered by our group members [44]. How to extend this approach to our routing and scheduling problems that have an online component is not immediately obvious. However, we believe further investigation on variations of this approach could lead to viable solution approaches. Investigating this will be another priority. It may be noted that ejection chain algorithms developed in the previous phase of this project could be viewed as a VLSN search algorithm. The shortest path problem is a fundamental problem with numerous applications. Here we study a variant of the problem, where the goal is to find a pointtopoint shortest path distance in a directed graph. We have considered the road network of the Greater Vancouver area as our directed graph. In the courier dispatching and the patient transfer problems in Greater Vancouver, we repeatedly require travel distance/time computations between the job locations. This is also true for our Limousine dispatching system for the city of Ottawa. Surely, one can store all the interpoint distances in the road network. However, this imposes a severe storage bottleneck on the prototype system being developed for the courier routing and the patient transfer problems. We have therefore decided to compute the distances on the fly. Thus we allow preprocessing, with only one restriction, that the additional space used to store precomputed data is limited. Our goal is a fast algorithm for approximating pointtopoint shortest path/travel times for any road network which does not require any cityspecific massaging of data. Most of the reported research is on producing the optimal path for the pointtopoint shortest path queries. An excellent review on this variant of the shortest path problem can be found in [26]. We have used the wellseparated concept introduced by Callahan and Kosaraju [15]. This paper develops a data structure, called the wellseparated pair decomposition, that organizes the pairs of points into pairs of clusters, or wellseparated pairs, in a way that preserves approximate distance. This leads to substantial improvements over algorithms that enumerate all distinct pairs of points. We have generalized the results in [15] to road networks. Efficient wellseparated pair decomposition data structures have been designed and implemented. We have further studied the shortest path algorithms and used A^{*} search in combination with the bounding technique based on wellseparted sets. Our algorithms compute almost optimal shortest paths (with less than 1 percent error) and work on any road network. Our experimental results show that the algorithm explores significantly less number of nodes than the algorithm of Goldberg [26] does while computing the shortest paths. Our latest involvement with Mobile Knowledge is also very exciting.An essential part of finding the travel time between two points in a city is the underlying road network. The problem is that digital maps containing the information required to produce dependable travel time estimates can be very expensive for small to moderatesize companies. Nowadays, most companies involved in the transportation business add GPS chips to their vehicles. This means that every time a communication occurs with a driver, the current time and GPS position are included in the message. Even in a smallsize company, if messages occur at frequent intervals the amount of GPS data is enourmous. The goal of our current project with Mobile Knowledge is to make use of this GPS data to recreate the underlying road network and to use this to produce accurate travel time estimates in a dynamic environment. We define a track to be two consecutive GPS data points emitted by the same vehicle. Thus our input is a set of tracks. However, the GPS data are easily corruptible by the local environments and satellite alignments. Using statistical analysis of the noisy data and tools from computational geometry, we are able to construct a good approximation of the road network in an unsupervised mode. Once the road map is constructed using the GPS tracks, we apply linear programmingbased techniques to estimate an appropriate ‘average’ speed for every road segment. This is done using the available GPS track data. In fact it is possible to compute average speed for every road segment at different times during the day. Given this information, we are able to estimate the average travel time in the city network for any given weekday and time.
We have identified the following topics which have direct relevance to the proposed vehicle routing system.
While integer programming and metaheuristics such as VLSN search were extremely useful in our applied research, our project also focused considerable time on fundamental research. We obtained significant advancement in network flows ([58][36]), in TSP([3],[4]) and in establishing tight performance bounds on various classes of vertex cover problems [29],[30]. The approximation results in vehicle routing problems, network facility location problems and wireless coverage problems are separately discussed below. The vehicle routing problem is a generalization of the traveling salesman problem, but is a special case of the pickup and delivery problems. In this problem, we are given p vehicles and a complete graph G, and the objective is to find a separate tour for each vehicle with respect to minimizing or maximizing some objective function, such as the total cost of the tours. This problem has direct relevance to the industryrelated research we are pursuing. The vehicle routing problem has numerous variations, and has been extensively investigated by many researchers. Various techniques, such as linear programming, local search, and even clustering, have been applied or invented to solve these problems. However, as a well recognized method of dealing with NPhard problems, good approximation algorithms have not been well explored for this problem. An extensive coverage of VRP can be found in [53] Techniques usedWe have made significant progress in the design of approximation algorithms for various forms of vehicle routing problems. For two models of CVRPPD, namely the DialaRide problem and the kdelivery TSP on paths and trees, we propose a strategy called the come back rule. Our algorithms are all based on this strategy. Under the come back rule[34], the vehicle would not be allowed to cross a particular edge e if some condition is met. Such a condition varies for different problems. The existing method for these problems, follows the strategy (first introduced in [17]) that, the vehicle would continue to pick up (deliver) items if possible. The come back rule differs from this method in that, under the come back rule the vehicle may not deliver its load immediately, but come back and pick up more items for a better schedule. As a consequence, on its way back, the vehicle may traverse several edges without servicing any jobs, even when it is carrying a large load. This is somewhat contrary to our intuition. For two problems in the category of MVRP, namely MDCVRP and MVSP in trees, we propose a new way of using dynamic programming to design constantfactor approximation algorithms. Under this approach, dynamic programming is used to decompose a problem instance P indirectly to a set of disjoint subproblems. As it is not possible to try all the configurations of the subproblems by directly obtaining solutions for P, we instead find another problem P' and locate a set S of disjoint subproblems by using dynamic programming to solve P' in the underlying graph. We then work on approximation algorithms for the subproblems in S. It is guaranteed that a good approximation for P can be obtained by approximating these subproblems well. To achieve this, we choose P' in a way such that P' satisfies some property inherent in the optimal solution of P. P' is much simpler and can be solved well by using dynamic programming in the underlying tree. More importantly, as P' is a relaxation of P, after solving P' we not only find a lower bound on OPT(P) , but also obtain a set of subproblems with good properties which can be used to approximate P. This method is used to give a 2approximation and a 3approximation for MDCVRP and MVSP in trees, respectively. No constantratio approximation algorithms are previously known for these two problems. The results are summarized in the table below.
Network facility location problems investigate where to physically locate a set of facilities (i.e., resources, servers) in the underlying network to satisfy some set of demands (i.e., customers, clients). The demand set consists of all points of the network that require services, and the supply set consists of all candidate locations of facilities. The goal is to place these facilities in the supply set such that the quality of service provided is optimized. In general, the quality of service is measured by some objective function, subject to a set of constraints. There are many different objective functions of possible interests, among which the minimization of maximum distance from a demand point to its closest facility is one of the most studied. The corresponding problem is referred to in the literature as the center problem. The network center location problem has been extensively studied in the literature. In [37], pcenter problems in general networks have been shown to be NPhard (even when the network is a planar network of maximum vertex degree four). However, center problems are no longer NPhard when either p is constant [37],[51], or the underlying network is restricted to be a specialized network, such as a tree [35],[37], a cactus [8], or a partial ktree (fixed k) [27]. We have achieved significant results for center location problems in general networks as well as specialized networks, such as tree networks, cactus networks, and partial ktree networks (fixed k). Our achievements are summarized in Table 2.
In the above table, we use a 3position scheme of Handler and Mirchandani [31], that is, (G)/(G)/p (supply set/demand set/number of facilities), to label different problems. Mainly, four cases of the center problem, where the demand set (G) and the supply set (G) are either subsets of the vertex set V(G) or subsets of the point set A(G), are considered. When the demand set is a subset of the vertex set, its weighted version of the problem is also considered where each demand vertex is associated with a nonnegative weight. Moreover, we also have some achievements on variations of the network center location problem in an edgeweighted tree network, including conditional extensive facility location problems (CELP), continuous pedgepartition problems (CEPP), and conditional covering problems (CCP). Our results are summarized in the table below.
Monitoring and surveillance are two of the main applications of wireless sensor networks. Network coverage measures how well an area is monitored by a sensor network. As an important research issue in wireless sensor networks today, the coverage problem has been studied extensively, and many solutions have been proposed. Some solutions focus on pure coverage problems to characterize the coverage of wireless ad hoc sensor networks, i.e., the kcoverage problem [56] bnd the arrier coverage problem [38]. Other solutions integrate network connectivity into coverage problems, since network connectivity, which indicates whether any two nodes in a sensor network can communicate with each other, is necessary for successful data transmission. We have investigated variations of coverage models in wireless sensor networks and some results are briefly described as follows. Given a barrier (i.e., a path, a cycle, a simple polygon) and mobile sensors (or robots) that are lying in the interior of this barrieri, where the sensors can move autonomously in the plane, we investigate how to move the sensors within this region so as to optimize either the minimum sum or the minimum of the maximum of the distances covered by the respective sensors. In [10], we introduced the above problem and showed that,
Most recently, we studied the kbarrier coverage problem on a belt region [38] and proposed an efficient algorithm for it with an approximation ratio of no more than 2. A belt region with a sensor network deployed over it is said to be kbarrier covered if and only if all paths crossing through the belt are kcovered by the sensor network. In [11], we investigate the problem of converting (connected) networks of omnidirectional sensors to strongly connected networks of sensors with multiple directional antennae. Consider a set S of n points in the plane modeling sensors of an ad hoc network. Each sensor uses a fixed number, say 1 ≤ k ≤ 5, of directional antennae modeled as a circular sector with a given spread (or angle) and range (or radius). In the paper, we give algorithms for orienting the antennae at each sensor so that the resulting directed graph induced by the directed antennae on the nodes is strongly connected, and also study tradeoffs between angle spread and range for maintaining connectivity. The next table summarizes the results obtained and also mentions previous results from the literature. We assume that the maximum length of edges in a Minimum Spanning Tree of S is 1. (Notation: Let φ_{k} be a given nonnegative value in [0,2π) such that the sum of angles of k antennae at each sensor location is bounded by φ_{k}, k=1,2,3,4.)
In [11], we gave several tradeoffs between antenna spread and range when each sensor has k directional antennae, k = 2, 3, 4, so as to guarantee the resulting network is strongly connected. Several problems remain open. Lower bounds are lacking from our study and it remains open to prove NP completeness results for the case of multiple antennae per sensor. Another interesting question concerns ensuring that for a given integer c the resulting network is strongly cconnected, i.e., it remains strongly connected after the deletion of any c1 nodes. Vehicle Routing Problems Most of the problems in VRP area, discussed above, are still open for the graph networks. We list below some other interesting practical vehicle routing problems for which no approximation algorithms are known.
Network Facility Location Problems
Although we have proposed many efficient algorithms for the network center problems when either the number of facilities to be opened (i.e., p) is constant or the underlying network is restricted to be a specialized network, such as a tree, a cactus, or a partial ktree with fixed k, many algorithmic issues are still unresolved. We list a few examples as follows. First, the running time of our algorithms for a tree network or the real line is exponential in p. One challenging task will be to resolve a long standing open problem: Is there a lineartime algorithm for a tree network or the real line for arbitrary p. Second, a sustained effort on location problems in a treelike network, such as a cactus or a partial ktree with fixed k, is needed. Especially for a partial ktree network of bounded treewidth, we introduce a twolevel tree decomposition data structure to assist servicecost queries for any set of facilities, which is very helpful for a small number of facilities and a small number of facility candidate locations. We would like to know how to enhance the data structure to support more complicated queries, e.g., a set of continuous regions instead of a set of facility points. Third, not many results have been achieved for the case when the demands are located everywhere in a treelike network or a general network, and for the case where the demands are represented by some connected structures instead of isolated points. In addition, recently, more and more attention has been paid to facility location problems combined with network modification subject to certain budget constraints. That is, for a given budget, the goal is to change some parameters of the underlying network in order to improve the quality of a facility location (e. g., see [59]). Recent results have shown that when the underlying network is a line or tree, one can find a strategy in polynomial time to enhance the performance of the network by modifying (reducing) vertex weights and/or edge lengths subject to that the sum of reducing costs or the maximum reducing cost is not exceed the given budget (e. g., see [18]). However, the study of the modifications of other possible parameters, i.e., openfacility costs, vertex demand, and capacity, is a new and emerging field of study, and much remains to be explored. [1] R.K. Ahuja, O. Ergun, J.B. Orlin, and A.P. Punnen, Very Large Scale Neighborhood Search: Theory, Algorithms and Applications, in Approximation Algorithms and Metaheuristics T. Gonzalez(ed), CRC Press, 2006.[2] R. Barlovic, T. Huisinga, A. Schadschneider, and M. Schreckenberg, Adaptive Traffic Light Control in the ChSch Model, Workshop on Granular Flow, 2003. [3]D. Benvenuti and A.P. Punnen, On weighted graphs with hamiltonian cycles of same cost, Submitted for publication, 2008. [4] Benvenuti and A.P. Punnen, Characterization of disjoint spanning 2paths with three or less distinct values, Submitted for publication, 2008. [5] R. Benkoczi, B. Bhattacharya, and Q. Shi, New upper bounds on continuous tree edgepartition problem, in Proc. AAIM'08 (2008) 3849. [6] B. BenMoshe, B. Bhattacharya, Q. Shi and A. Tamir, Efficient algorithms for center problems in cactus networks, Theoretical Computer Science 378:3 (2007) 237252. [7] B. BenMoshe B. Bhattacharya, and Q. Shi, An optimal algorithm for the continuous/discrete weighted 2center problem in trees, in Proc. LATIN'06 (2006) 166177. [8] B. BenMoshe, B. Bhattacharya and Q. Shi, Efficient algorithms for the weighted 2center problem in a cactus graph, in Proc. ISAAC'05 (2005) 693703. [9] Bhattacharya, B.K., Carmi, P., Hu, Y., Shi, Q., Vehicle Scheduling Problem on Networks with Release and Handling Times, 19th ISAAC, Australia, 2008. [10] B. Bhattacharya, M. Burmester, Y. Hu, E. Kranakis, Q. Shi, and A. Wiese, Optimal movement of mobile sensors for barrier coverage of a planar region, invited to a special issue of the Theoretical Computer Science (2008). [11] B. Bhattacharya, Y. Hu, E. Kranakis, D. Krizanc, and Q. Shi, Sensor network connectivity with multiple directional antennae of a given angular sum, submitted to IEEE IPDPS'09 (2008). [12] Bhattacharya, B.K., Hu, Y., and Kononov A., Approximation Algorithms for the Black and White Traveling Salesman Problem, COCOON: 559567, 2007 (Invited to a special issue). [13] B. Bhattacharya, Q. Shi, and A. Tamir, Optimal algorithms for the path/treeshaped facility location problems in trees, accepted to Algorithmica in Dec. 3, 2007. [14] B. Bhattacharya and Q. Shi, Application of computational geometry to network pcenter location problems, in Proc. CCCG'08 (2008). [15] P.B Callahan and S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to knearestneighbors and nbody potential fields, Journal of ACM, Vol 42, No. 1, pp .6790, 1991. [16] I.Caragiannis, C.Kaklamanis, E.Kranakis, D.Krizanc, and A.Wiese, Communication in wireless networks with directional antennae, in Proc. of SPAA'08 (2008). [17] M. Charikar, B. Raghavachari, The Finite Capacity DialARide Problem. FOCS, Page:458467, 1998. [18] E. Gassner, Up and downgrading the 1center in a network, European Journal of Operational Research (2008). [19] Y. Chen, A New Method for Urban Traffic State Estimation based on Vehicle Tracking Algorithm, IEEE Intelligent Transportation Systems Conf., Seattle, Sept. 2007, pages 10971101. [20] S. Dornbush, StreetSmart Traffic: Discovering and Disseminating Automobile Congestion Using VANETs, IEEE VTC Spring 2007, pages 1115. [21] C. Drane and J.L Ygnace, Cellular Telecommunication and Transportation Convergence: A Case Study, IEEE Intelligent Transportation Systems Conference, 2001. [22] See http://www.etsi.org/WebSite/technologies/IntelligentTransportSystems.aspx . [23] C. Furtlehner, J. M. Lasgouttes and A. de La Fortelle, A Belief Propagation Approach to Traffic Prediction using Probe Vehicle, IEEE Intelligent Transportation Systems Conference, Seattle, Sept. 2007, pages 10221027. [24] C. Gershenson, Selforganizing Traffic Lights, Complex Systems, Vol. 16(1), 2953. [25] GERTRUDE: RealTime Management for TownPlanning, Transport and the Environment. See web site: http://www.gertrude.fr/, accessed in August 2008. [26] A. V. Goldberg and C. Harrelson,Computing the shortest path: A* search meets graph theory, SODA, 2005, 156165. [27] D. Granot, D. SkorinKapov, On some optimization problems on ktrees and partial ktrees, Disc. App. Math. 48 (1994) 129145. [28] Irina Gribkovskaia, Gilbert Laporte, Aliaksandr Shyshou The single vehicle routing problem with deliveries and selective pickups. Computers and Operations Research, Vol 35, Issue 9, 29082924, 2008. [29]Q. Han, A.P. Punnen, Y. Ye, An edgereduction algorithm for the vertex cover problem, Revised for Operations Research Letters, 2008. [30]Q. Han and A.P. Punnen, On the approximability of vertex cover and related problems, Submitted for publication, 2008. [31] G.Y. Handler and P.B. Mirchandani, Location on networks theory and algorithms, MIT Press, Cambridge (1979). [32] J.A. Horne, J.C. Smith, Dynamic programming algorithms for the conditional covering problem on path and extended star graphs, Networks, 46:4 (2005) 177185. [33] J.A. Horne, J.C. Smith, A dynamic programming algorithm for the conditional covering problem on tree graphs, Networks, 46:4 (2005) 186197. [34]Y. Hu, Approximation algorithms for vehicle routing problems, Ph.D. Thesis Proposal, Simon Fraser University, 2008. [35] M. Jeger and O. Kariv, Algorithms for finding pcenters on a weighted tree (for relatively small p), Networks, 15 (1985) 381389. [36]S.N. Kabadi and A.P. Punnen, A strongly polynomial simplex method for the linear fractional assignment problem, Operations Research Letters, 36 (2008) 402407. [37] O. Kariv and S.L. Hakimi, An algorithmic approach to network location problems, Part I. The pcenters, SIAM J. Appl. Math., 37 (1979) 513538. [38] S. Kumar, T.H. Lai, and A. Arora, Barrier coverage with wireless sensors, Wireless Networks, 13:6 (2007) 817834. [39] H. Kuriyama, et al., Congestion Alleviation Scheduling Technique for Car Drivers Based on Prediction of Future Congestion on Roads and Spots, IEEE Intelligent Transportation Systems Conference, Seattle, Sept. 2007, pages 910915. [40] J.J. Lin, C.Y. Chan, and B.F. Wang, Improved algorithms for the continuous tree edgepartition problems, Submitted to Disc. App. Math., (2007). [41]H. X. Liu, J.S. Oh, and W. Recker, Adaptive Signal Control System with Online Performance Measure, Transportation Res. Record 1811, 2002, pages 131138. [44] S. MitrovicMinic and A.P. Punnen, Local Search Intensified: Very LargeScale Variable Neighborhood Search for the MultiResource Generalized Assignment Problem. Accepted, Discrete Optimization, 2008. [45]S. MitrovicMinic and A.P. Punnen, A mixed integer programming model and algorithm for scheduling a reconfigurable fleet of heterogeneous ferries. Manuscript in preparation, 2008. [46] D. de Oliveira, A. L. C. Bazzan, and V. Lesser, Using Cooperative Mediation to Coordinate Traffic Lights: A Case Study, The Fourth Int. Conf. on Autonomous Agents and Multiagent Systems, 2005, pp. 463470. [47] R.G. Parker and R.L. Rardin, Guaranteed performance heuristics for the bottleneck traveling salesman problem, Oper. Res. Lett, 2:6 (1984) 269272. [48] W. PatttaraAtikom, et al., Estimating Road Traffic Congestion using Cell Dwell Time with Simple Threshold and Fuzzy Logic Techniques, IEEE Intelligent Transportation Systems Conference, Seattle, Sept. 2007, pages 956961. [49] H. Rakha, M. V. Aerde, K. Ahn, and A. A. Trani, Requirements for Evaluating Traffic Signal Control Impacts on Energy and Emissions Based on Instantaneous Speed and Acceleration Measurements, Paper no. 001134, Transportation Research Board 79th Annual Meet, Jan. 2000. [50] Q. Shi, Efficient algorithms for network center/covering location optimization problems, Ph.D. Thesis, Simon Fraser University (2008). [51] A. Tamir, Improved complexity bounds for center location problems on networks by using dynamic data structures, SIAM J. Discret. Math., 1(3):377396, 1988. [52] A. Tamir, J. Puerto, J.A. Mesa, A.M. RodriguezChia, Conditional location of path and tree shaped facilities on trees, Journal of Algorithms, 56 (2005) 5075. [53] P. Toth and D. Vigo (eds), The vehicle routing problem, SIAM Monographs on Discrete Mathematics and Applications, 2002. [54]United States Vehicular Infrastructure Integration http://www.its.dot.gov/vii/ [55] L. Wang, C. Wang, X. Shen and Y. Fan, Probe Vehicle Sampling for RealTime Traffic Data Collection, IEEE Intelligent Transportation Systems Conf., 2005,pages 886888. [56] Y. Wang, X.Y. Li, and Q. Zhang, Efficient algorithms for pselfprotection problem in static wireless sensor networks, IEEE Transactions on Parallel and Distributed Systems, 19:10 (2008) 14261438. [57] M. Wiering, J. Vreeken, J. Van Veenen, and A. Koopman, Simulation and Optimization of Traffic in a City, IEEE Intelligent Vehicles Symposium, 2004. [58]R. Zhang and A.P. Punnen, Bottleneck Flows in Networks, Submitted for publication, 2008. [59] J.Z. Zhang, X.G. Yang, and M.C. Cai, A network improvement problem under different norms, Computational Optimization and Applications, 2004. [60] X. Zhang, et al., A New Realtime Traffic Information System Based on Wireless Mesh Networks, IEEE Intelligent Transportation Systems Conf., Seattle, Sept. 2007, pages 618623. 