Research

• Science
• Industry-sponsored research
  • Dynamic pickup and delivery problem with time windows
  • Computing City Distances
  • Future Research Plan
• Fundamental Research
  • Approximation algorithms of VRP
  • Network Facility Location Problems
  • Coverage Problem in Wireless Sensor Networks
  • Proposed Research Plan
• References

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 near-optimal 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.

• Mobile Knowledge asked us to consider the problem of limousine dispatching scheduling in urban cities. The SRE (Shared Ride Engine) is a customized implemetation of the Vehicle Routing Problem with Time Windows. It serves as an automated dispatcher and as such it deals with two types of objects: jobs and vehicles. The jobs are the customers that must be moved from place to place in the city. The vehicles are the resources available to the company to service these jobs. There are two inherently different scheduling problems in vehicle routing problems (VRP). The first problem is to decide how to assign jobs to vehicles, the second is to find an optimal ordering for the jobs of each vehicle. The SRE acts as a black box that automatically finds good solutions to both these problems.

  The jobs scheduled by the SRE represent customers requiring transportation. Therefore, each job comes in a pair; there is always a pick up followed by a drop off. Moreover for each job-pair there is a concept called “Maximum Relative Passenger Delay”. The RPD is related to the quality of service and is defined to be total elapsed time between the pick up and drop off divided by the time it would take to go directly from the pick up to the drop off location if no other passengers were picked up up or dropped off on the way. No job RPD can exceed the max RPD. In addition, every job has a set of contraints, such as the number of passengers, wheelchair passengers as well as any specific client requirements. A vehicle must be able to satisfy the constraints of every job composing its route.

  We are very excited to report that SRE has been successfully field-tested by the company and is now operational in commercial settings in cities such as Chicago and Ottawa.

• BC Ferries operates in southern gulf islands linking Swartz Bay, Otter Bay (Pender Island), Village Bay (Mayne Island), Long Harbour (Salt Spring Island), Sturdies Bay (Galiano Island), Lyall Harbour (Saturna Island), and Tsawwassen using the vessels Bowen Queen (BQ), Mayne Queen (MQ), Queen of Nanaimo (QN) and Queen of Cumberland (QC). These operations comprised of three routes.

  In this project, we investigated the possibility of improving existing schedules of ferries operated by BC Ferries connecting gulf islands. We developed an integer programming model, and a new heuristic procedure based on the very large scale neighbourhood which is searched successfully using general purpose integer programming solvers. The method proved to be very efficient in solving large-scale real-life problems. Our research results confirmed ideas discussed by BC ferries scheduling group internally based on their experience. A research paper is under preparation based on the mathematical model and solution methods used in this project [45]. [ 47 ]

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 (real-time) environment where not all of the requests are known in advance. The methodology used for solving the dynamic PDPTW is an on-line 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 job-pair corresponds to a node in the improvement graph. This is called a 1-node. In general a k-node is a node in the improvement graph corresponding to k job-pairs. All 1-nodes are present in the improvement graph but only select subsets of all k-nodes make it to the improvement graph. Because improvement nodes correspond to scheduled job-pairs, 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 job-pair(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 job-pair associated with the destination node is removed from its route and the job-pair from the the source node is added to the destination route (at the best possible location, using a greedy algorithm). Note that the source job-pair is inserted into the destination route after the destination job-pair is removed. The path weight is defined in exactly the same way, except that the destination job-pair is not removed from its route.

With these definitions, it is easy to see that a route-disjoint 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 route-disjoint negative paths and/or cycles in the improvement graph. Unfortunately, because of the route disjointness requirement, this problem is NP-hard. 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 on-line 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 point-to-point 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 inter-point 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 point-to-point shortest path/travel times for any road network which does not require any city-specific massaging of data. Most of the reported research is on producing the optimal path for the point-to-point shortest path queries. An excellent review on this variant of the shortest path problem can be found in [26].

We have used the well-separated concept introduced by Callahan and Kosaraju [15]. This paper develops a data structure, called the well-separated pair decomposition, that organizes the pairs of points into pairs of clusters, or well-separated 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 well-separated 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 well-separted 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.

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 moderate-size 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 small-size 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 re-create 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 programming-based 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.

• Industry-driven research

  We are focussed on developing a comprehensive vehicle routing system that adapts to the particularities of urban scheduling. Our powerful model for vehicle scheduling in cities operates according to the following conditions:

  • New job requests are handled in real time. Each job is associated with particular time slots.
  • The scheduler maintains a schedule in real time.
  • The vehicle locations are monitored constantly; changes in the schedule, if needed, are updated.
  • The road systems in the city are being monitored by accessing live data such as the GPS feeds of the transfer vehicles. The average speed of the road networks is appropriately altered to reflect the current situation.
  • The point-to-point travel time/distance is computed on the fly.

  There are two important components that need to be tackled in developing our comprehensive vehicle scheduling system:

  1. When given a non-dynamic “snapshot” of the current roadway situation, computing a near optimal schedule is extremely hard. Moreover, such a schedule has to be computed quickly; otherwise new events such as new jobs, changes in road conditions, etc. make the schedule unrealistic. We have used the local search technique coupled with an approach based on column generation to find a near optimal schedule. While this general philosophy is applicable in various routing and scheduling problems, the quality and efficiency of the approach depends on the ability to generate appropriate columns which in turn reduces to another optimization problem. Because of the additional restrictions in our applications and the context in which the column generation is used, a practically viable column generation method for our problems needs much more sophistication than straightforward adaptations of the method.

  2. Travel times within a city change depending on various conditions, for example the time of day, current weather conditions, time of the year, and current traffic conditions.

     The calculation of these travel times is different from the calculation of travel times for intercity transportation. We are interested in monitoring the road conditions for any events that might affect the traffic in some parts of the city. Our approach of collecting road information from GPS tracking data will form the basis of our future work.

     We are working on a set of algorithms that will predict, with a high degree of accuracy, the travel time of a vehicle in any city road network at any given time. This requires a tremendous amount of data and data processing. The result will be a real-time tool, which will estimate travel time based on actual observed speeds by time of day on the roads ahead. Currently, the system allows the user to change the road network characteristics manually. Once the changes are made, the system then computes travel times on the fly. In the comprehensive routing systems, this process will be handled by the system.

• Next Generation Transportation System

  Developments in wireless communications, anywhere accessibility of the Internet, hand-held devices, sensor networks, and geographic information systems (GIS) have been paving way for novel applications in the field of road transportation. Road networks and vehicles, equipped with communication infrastructures and computing capabilities and connected to the Internet, are commonly referred to as intelligent transportation systems (ITS) [22]. For example, radio and TV channels provide periodic updates on road and traffic conditions on major highways, tolls are collected by using overhead sensors and cameras, and GPS (global positioning system) assisted routing with onboard computers is slowly gaining popularity. The COMPASS system of the Ministry of Transportation of Ontario, the RESCU system of city of Toronto, the Electronic Toll Road (ETR) 407 in Ontario, and numerous GPS-based navigation systems in the market amply demonstrate the potential of ITS systems and applications. In the COMPASS system, data from the sensors, which are deployed underneath the pavement, are transmitted to a central site via a wired network, and verified by human observers on a closed-circuit TV network. Travel information from the central site is delivered to drivers via overhead displays and radio/TV channels. Mexico City, Lisbon, Bordeaux, and Beijing use a real-time centralized system called GERTRUDE to control intersections and give priority to public transports [25]. Governments, auto makers, standardization bodies, and researchers have been making a concerted effort to develop novel ITS systems. Among applications, advanced traveler information systems (ATIS), novel traffic light control systems, automatic toll collection systems, navigation systems, and driver warning systems are on the rise. Less congestion, less travel time and distance, and availability of safety information are important to drivers.

1. Traffic Control Algorithms

   The key ideas in traffic control are as follows: (i) in normal conditions, enable cars to move at their free-flow speeds; (ii) when incidents occur, minimize their impacts. Researchers have studied and evaluated traffic control algorithms using the following metrics: waiting time [57], delay [41], travel time [41], percentage of stopped cars [24], density of cars [46], global flow [2], and fairness [41]. Those reports do not address environmental impacts. A key concept in vehicle routing and traffic control is automatic detection of incidents and congestion. Though an ITS system can be manually updated with incidents, researchers have shown the feasibility of automated detection by means of VANETs [20].

2. Estimation of Traffic Congestion

   The estimation of traffic congestion is central to developing routing algorithms for a variety of metrics, such as shortest time, shortest distance, and minimum fuel and emission costs. Pattara-tikom, et al. [48] propose a congestion prediction technique based on the cell dueling time (CDT) of the mobile phones of users. Their study suggests that CDT duration can be used to estimate the degree of congestion with an accuracy level up to 85%. Chen, et al. [19] propose a congestion modeling technique based on GPS based vehicle tracking. Average velocities of road links are calculated and distributed to related links. By integrating all the velocity contributions on each road link, traffic states are determined along rolling time periods. Furtlehner, et al. [ 23 ] show how the idea of belief propagation, a concept developed for intelligent systems -- can be applied to traffic prediction using probe vehicles equipped with GPS devices [ 21 ]. Zhang, et al. [60] present a design of a wireless mesh network for efficient and scalable communication with probe vehicles. Kuriyama, et al. [39] propose a method for finding non-congested routes by sharing route information among users and a schedule to alleviate congestion at specific places. A mathematical model of the probe vehicle sample size is given in [21], and it has been validated in [55].

We have identified the following topics which have direct relevance to the proposed vehicle routing system.

• Objective 1: Congestion modeling and prediction

  Occurrence of congestion is a dynamic phenomenon. In the COMPASS system, drivers are merely warned of occurrences of congestions via overhead CMS (Changeable Message System) display boards. It is important to have two capabilities: first, model congestion by considering the past and present pattern of traffic; second, develop a technique to predict congestion in the short-term, up to one hour. A lead time in congestion prediction will allow us to take actions to diffuse the intensity of congestion. For example, techniques such as early warning for all drivers and traffic flow balancing hold much potential in diffusing the intensity of congestion.

  Methodology

  For modeling and predicting congestion, we will have a system to collect data about individual vehicles, such as location, speed, and destination. Such data can be easily collected by replacing the current “induction-loop” technique with an IP (Internet Protocol) message-based technique utilizing wireless communication. We will develop algorithms for forecasting congestion, similar to short-term weather forecasting and financial forecasting. Soft and evolutionary computing techniques, such as fuzzy logic, genetic algorithms, and neural networks, will be applied to develop efficient heuristics. We have completed literature review to know the state-of-art in congestion detection. We will focus on low-cost, accurate modeling of congestion based on historical traffic and current traffic. The capabilities of vehicular ad hoc networks (VANETS) will be utilized in gathering data in a cost-effective manner for this purpose.

• Objective 2: Soft Infrastructure for ITS Applications [54]

  We will develop communication architecture, protocols, and algorithms for urban vehicle flow control to optimize the following performance metrics: travel time, travel distance, congestion, fuel consumption, GHG emissions and quality of travel experience (QOTE). Effective vehicle routing is key to the success of an ITS system, because drivers and the transportation ministries are interested in sustaining the free-flow of vehicles. The above stated performance metrics naturally follow from the free-flow requirement. Traffic congestion occurs during peak hours due to a large number of vehicles being on the road, and at any time if there are road-related incidents. Incidents tend to reduce the available capacity of certain road segments, thereby causing resource bottlenecks. It is important to identify and process real-time parameters of road networks to generate a balanced flow, and disseminate the information to control points and drivers.

  Methodology

  A road network is often modeled as a dynamic network (i.e., graph), where a node models a road intersection and a directed edge represents a road segment. The “cost” of an edge will be modeled by a vector of time varying metrics, namely, length, travel time, fuel cost of travel, and emission cost. Travel time will be modeled as a function of a new parameter called “degree of congestion”, whereas fuel and emission costs will be modeled as functions of instantaneous speeds and accelerations [49]. The degree of congestion will be modeled as functions of instantaneous speeds and accelerations - this will be new in our work. The progress made in computing city distances in this project will form the basis to develop shortest-time routes in a dynamic network.

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 industry-related 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 NP-hard problems, good approximation algorithms have not been well explored for this problem. An extensive coverage of VRP can be found in [53]

We have made significant progress in the design of approximation algorithms for various forms of vehicle routing problems. For two models of CVRPPD, namely the Dial-a-Ride problem and the k-delivery 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 constant-factor 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 2-approximation and a 3-approximation for MDCVRP and MVSP in trees, respectively. No constant-ratio approximation algorithms are previously known for these two problems. The results are summarized in the table below.

Problem	Previous approximation ratio	Our results
k-delivery TSP on paths [34]	O(n2/min(k,n)) time, exact	optimal
k-delivery TSP in trees [34]	2	5/3
dial-a-ride on paths [34]	3	2.5
dial-a-ride on height balanced trees [34]	8√k	6√k
BWTSP [12]	—	4-3/(2Q)
BWTSP [12] , exact	—	4-15/(8Q)
constrained kCCP [34]	—	2
kCCPSC [34]	no constant factor	2
SVSP on paths [9]	5/3	1.5
SVSP in trees [9]	2	11/6
SVSP in cycles [9]	—	9/5
MDCVRP on paths [34]	—	O(n3) time, exact
MDCVRP in trees [34]	—	2
MDCVRP in general graphs [34]	—	min(k, O(log(n)))
MVSP in trees [34]	no constant factor	3
TSP Travelling Salesman Problem BWTSP Black and White TSP kCCPSC k-Cycle Covering Problem with Short Cycles SVSP Single Vehicle Scheduling Problem MDCVRP MultiDepot Capacitated Vehicle Routing Problem MVSP MultiVehicle Sceduling Problem

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], p-center problems in general networks have been shown to be NP-hard (even when the network is a planar network of maximum vertex degree four). However, center problems are no longer NP-hard 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 k-tree (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 k-tree networks (fixed k). Our achievements are summarized in Table 2.

Results for the network p-center problems
Underlying network	Problem	Previous result	Our result
A tree T	Weighted V(T)/V(T)/p (fixed p)	O(n⋅log(n))[35]	O(n) [7],[50]
	Weighted A(T)/V(T)/p (fixed p)	O(n⋅log(n))[35]	O(n)[7],[50]
A cactus G	Unweighted V(G)/A(G)/1	—	O(n) [6]
	Unweighted A(G)/A(G)/1	—	O(n) [6]
	Weighted V(G)/V(G)/1	—	O(n⋅log(n)) [8]
	Weighted A(G)/V(G)/1	—	O(n⋅log(n)) [8]
	Weighted A(G)/V(G)/2	—	O(n⋅log3(n)) [8]
	Obnoxious A(G)/V(G)/1	—	O(n⋅log3(n)) [8]
	Unweighted V(G)/A(G)/p	—	O(n2) [6]
	Unweighted A(G)/A(G)/p	—	O(n2⋅log2(n)) [6]
	Weighted V(G)/V(G)/p	—	O(n⋅log2(n)) [6]
	Weighted A(G)/V(G)/p	—	O(n2)[6]
A partial k-tree G (fixed k)	Weighted V(G)/V(G)/1	—	O(n⋅logk(n)) [14]
	Weighted V(G)/V(G)/p (fixed p)	O(nk+2)[27]	O(np⋅log2k(n))[14]
	Weighted A(G)/V(G)/p	—	O(p2n2k+3⋅log(n)) [14]
A general network G	Weighted A(G)/V(G)/p	O(mpnpα(n)⋅log(n)) 1[51]	O(mpnp/2⋅2log*(n)⋅log(n))[14]
1: α(n) is the inverse Ackermann function.

In the above table, we use a 3-position 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 non-negative weight.

Moreover, we also have some achievements on variations of the network center location problem in an edge-weighted tree network, including conditional extensive facility location problems (CELP), continuous p-edge-partition problems (CEPP), and conditional covering problems (CCP). Our results are summarized in the table below.

Some variations of network center location problems in a tree network
Problem	Previous result	Our result
CELP	O(n⋅log(n))[52]	O(n)[13]
Max-Min CEPP	O(n2) [40]	O(n⋅log2(n))[5]
Min-Max CEPP	O(n2) [40]	O(n⋅hT⋅log(n)) 1 [5]
CCP in a path	O(n2) [32]	O(n⋅log(n))[50]
CCP in an extended-star	O(n2)[32]	O(n1.5⋅log(n))[50]
CCP in a tree	O(n4) [33]	O(n3⋅log(n)) [50]
1: hT is the height of the underlying tree network

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 k-coverage 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,

• the min-max problem on the unit-disk-barrier can be solved in O(n^3.5⋅log(n)) time where n is the number of mobile sensors,
• the min-max problem on a simple polygon can be solved in O(mn^3.5⋅log(n)) time where m is the size of the simple polygon,
• for a given constant ε, there is an O(1/ε⋅n⁴)-time algorithm for the min-sum problem on the unit-disk-barrier with an approximation ratio of no more than 1+ε, and
• for a given constant ε, there is an O(1/ε⋅mn⁵)-time algorithm for the min-sum problem on a simple polygon with an approximation ratio of no more than 1+ε.

Most recently, we studied the k-barrier 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 k-barrier covered if and only if all paths crossing through the belt are k-covered 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 non-negative 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 c-connected, i.e., it remains strongly connected after the deletion of any c-1 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.

• VRP with satellite facilities (VRPSF). In VRPSF, there are several satellite facilities scattered in a given graph. When servicing the customers, the vehicle can go to these satellite facilities to replenish instead of coming back to the depot. For example, consider the case when multiple vehicles are available to service the customers. Then each customer should be serviced by exactly one vehicle, while each satellite facility can be visited by multiple vehicles.
• VRP with Cross Docking (VRPCD). In this problem we are given p vehicles to transport various types of product from suppliers to customers through a cross-dock. The cross-dock serves as a temporary inventory, where product in a vehicle can be dumped and reassembled. In VRPCD one vehicle may collect some amount of product from the suppliers and dump them at the cross-dock and continue to pick up more goods, and another vehicle may upload some amount of product at the cross-dock and deliver them to the corresponding customers. The objective of VRPCD is to compute a schedule minimizing the maximum completion time of the vehicles (makespan).

• VRP with Pickup and Delivery(VRPPD) with excessive supplies. In the traditional settings of VRP with pick ups and deliveries, every pick up and delivery demand should be serviced. However, there are circumstances for which not all demands need to be satisfied. For example, in an instance of the k-delivery TSP, we may have excessive supplies, so the number of pick up vertices may be larger than the number of delivery vertices. Therefore only a subset of the pickup vertices should be chosen in the tour to service all the delivery vertices. The solution techniques for the k-MST problem might be helpful for this variation.

  In [28] Laporte et al. studied a similar model called the single vehicle routing problem with deliveries and selective pick ups (SVRPDSP). In this problem it is no longer required that all the pick up demands should be satisfied. Instead a pickup profit is associated with each vertex, and a tour of SVRPDSP should visit each customer, satisfy all the delivery demands and only part of the pick up demands. The cost of such a tour is defined to be the total edge cost of the tour minus the profit collected from the vertices. The objective of SVRPDSP is to find such a tour with the minimum cost. No approximation algorithms are known for this problem.

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 k-tree 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 linear-time algorithm for a tree network or the real line for arbitrary p. Second, a sustained effort on location problems in a tree-like network, such as a cactus or a partial k-tree with fixed k, is needed. Especially for a partial k-tree network of bounded tree-width, we introduce a two-level tree decomposition data structure to assist service-cost 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 tree-like 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., open-facility costs, vertex demand, and capacity, is a new and emerging field of study, and much remains to be explored.