Abdelkader Sbihi

Richard William Eglese

The relationship between vehicle routing and scheduling and green logistics -a literature survey

Keywords: vehicle routing, scheduling, emission, congestion, environment, green logistics

The basic Vehicle Routing and Scheduling Problem (VRSP) is described followed by an outline of solution approaches. Different variations of the basic VRSP are examined that involve the consideration of additional constraints or other changes in the structure of the appropriate model. An introduction is provided to Green Logistics issues that are relevant to vehicle routing and scheduling including discussion of the environmental objectives that should be considered. Particular consideration is given to VRSP models that relate to environmental issues including the timedependent VRSP, the transportation of hazardous materials and dynamic VRSP models. Finally some conclusions are drawn about further research needs in this area and the relation to road pricing.

Introduction

The Vehicle Routing and Scheduling Problem (VRSP) concerns the determination of routes and schedules for a fleet of vehicles to satisfy the demands of a set of customers. The basic Capacitated Vehicle Routing Problem (CVRP) can be described in the following way. We are given a set of homogeneous vehicles each of capacity Q, located at a central depot and a set of customers with known locations and demands to be satisfied by deliveries from the central depot. Each vehicle route must start and end at the central depot and the total customer demand satisfied by deliveries on each route must not exceed the vehicle capacity, Q. The objective is to determine a set of routes for the vehicles that will minimize the total cost. The total cost is usually proportional to the total distance traveled if the number of vehicles is fixed and may also include an additional term proportional to the number of vehicles used if the number of routes may vary.

The vehicle routing problem scheme

The CVRP and many of its variants have been well studied in the literature since its introduction by Danzig and Ramser in 1959 [START_REF] Dantzig | The truck dispatching problem[END_REF]. Its exact solution is difficult to determine for large-scale problems as it is a member of the class of NP-Hard problems, where no algorithms have yet been devised where the time to find a guaranteed optimal solution that is proportional to the size of the problem (in this case, the number of customers). Specialised algorithms are able to consistently find optimal solutions for cases with up to about 50 customers; larger problems have been solved to optimality in some cases, but often at the expense of considerable computing time.

In practice, other variations and additional constraints that must be taken into consideration usually make the vehicle routing problem even more difficult to solve to optimality. So many solution procedures are based on heuristic algorithms that are designed to provide good feasible solutions within an acceptable computing time, but without a guarantee of optimality.

There are several books and survey articles that have been written that summarise different approaches and provide references to the large number of journal articles that have been written on this topic, for example [START_REF] Golden | Vehicle Routing: Methods and Studies[END_REF] [START_REF] Golden | Vehicle Routing: Methods and Studies[END_REF] and [START_REF] Toth | The Vehicle Routing Problem[END_REF] [START_REF] Toth | The Vehicle Routing Problem[END_REF]. There are many other research works about the classical CVRP; we may cite some exact methods for this problem, for example [START_REF] Laporte | Exact algorithms for the vehicle routing problem[END_REF] [START_REF] Laporte | Exact algorithms for the vehicle routing problem[END_REF] or [START_REF] Agarwal | A set-partitioning-based exact algorithm for the vehicle routing problem[END_REF] [START_REF] Agarwal | A set-partitioning-based exact algorithm for the vehicle routing problem[END_REF] have proposed optimal approaches to solve the CVRP. Others have proposed approximate methods and heuristics due to the complexity of the problem and to try to solve it in a reasonable computing time: we cite, for example, [START_REF] Laporte | Classical heuristics for the capacitated VRP[END_REF] [START_REF] Laporte | Classical heuristics for the capacitated VRP[END_REF] and [START_REF] Cordeau | Tabu search heuristics for the vehicle routing problem[END_REF] [START_REF] Cordeau | Tabu search heuristics for the vehicle routing problem[END_REF], and [START_REF] Cordeau | New heurisics for the vehicle routing problem[END_REF] [START_REF] Cordeau | New heurisics for the vehicle routing problem[END_REF] or [START_REF] Gendreau | Metaheuristics for the capacitated VRP[END_REF] [START_REF] Gendreau | Metaheuristics for the capacitated VRP[END_REF]. Most of these approaches are based on local search techniques.

Most papers assume that the costs and times of traveling between the depot and the customers and between customers are known and fixed. They are either given or calculated using a shortest path algorithm on the graph or network representing the locations. In practice, the times and shortest paths may vary, particularly by time of day and this feature will be discussed more fully in Section 3.

The following section outlines other variations on the basic CVRP which are important in practical distribution problems.

Distance or time constraints for each route

In some formulations, a constraint on the maximum distance that can be traveled by any vehicle before it completes its route is imposed. In other cases, the constraint concerns the maximum time taken for each route which may relate to a legal constraint on the working time of the driver. There may be a distinction between a constraint on the driving time that only includes time when the vehicle is traveling and a constraint on the total time that also includes time to load the vehicle and to service each customer on the route. The reader may refer to some articles (see [START_REF] Desrochers | Vehicle Routing with TimeWindows: Optimization and Approximation[END_REF] [START_REF] Desrochers | Vehicle Routing with TimeWindows: Optimization and Approximation[END_REF]). We also cite the work developed in [START_REF] Cordeau | New heurisics for the vehicle routing problem[END_REF] [START_REF] Laporte | Optimal routing under capacity and distance restrictions[END_REF].

Time Window constraints

These constraints restrict the times at which a customer is available to receive a delivery. We call this typical problem the Vehicle Routing Problem with Time Window (VRPTW). These time window constraints are usually expressed in terms of a time interval or intervals within which service must begin for each customer. If a vehicle arrives at a customer before the start of a time window, then it must normally wait until the start of the time window before service can commence. Other formulations may treat the time windows as soft constraints where early or late service may be allowed but at the expense of a penalty in the objective function. Some exact and approximate methods have been tailored especially to solve the VRPTW. One example is an optimization algorithm developed for the VRPTW and attributed to [START_REF] Kolen | Vehicle routing with time windows[END_REF] [START_REF] Kolen | Vehicle routing with time windows[END_REF]. Other more recent papers include, for example, [START_REF] Kallehauge | Lagrangean duality applied to the vehicle routing with time windows[END_REF] [START_REF] Kallehauge | Lagrangean duality applied to the vehicle routing with time windows[END_REF] who have developed an exact algorithm. Approximate and heuristic methods have also been built, for example, [START_REF] Potvin | A parallel route building algorithm for the vehicle routing and scheduling problem with time windows[END_REF] [START_REF] Potvin | A parallel route building algorithm for the vehicle routing and scheduling problem with time windows[END_REF], Braysy (2002) [START_REF] Braysy | Fast local searches for the vehicle routing problem with time windows[END_REF] or [START_REF] Lau | Vehicle routing problem with time windows and a limited number of vehicles[END_REF] [START_REF] Lau | Vehicle routing problem with time windows and a limited number of vehicles[END_REF].

CVRP with Backhauls

In this variation, there are two subsets of customers: the first subset requires deliveries from the depot and the second subset requires goods to be picked up to be delivered to the depot. Normally all deliveries on each route must be completed before any pick-ups. The total deliveries and the total pick-ups on each route must separately be less than the capacity of each vehicle, Q. The reader may refer to Goetschalckx and Jacobs-Blecha (1993) [START_REF] Goetschalckx | The Vehicle Routing Problem with Backhauls: An Optimization Based Approach[END_REF] and [START_REF] Casco | Vehicle routing with backhauls: Models, algorithms, and case studies[END_REF] [START_REF] Casco | Vehicle routing with backhauls: Models, algorithms, and case studies[END_REF].

CVRP with Pick-up and Delivery

This situation concerns a set of customer orders where a single commodity is to be picked up from one location and delivered to a second location. The vehicle routes, starting and finishing at a central depot, must be constructed so that the route visits the pick-up location for an order before the corresponding delivery location and the load on each vehicle never exceeds the capacity, Q. We recall here some research addressed to this type of VRSP, for example, [START_REF] Desaulniers | VRP with pickup and delivery[END_REF] [START_REF] Desaulniers | VRP with pickup and delivery[END_REF] and [START_REF] Derigs | A matching-based approach for solving a delivery/pick-up VRP with time constraints[END_REF] [START_REF] Derigs | A matching-based approach for solving a delivery/pick-up VRP with time constraints[END_REF]. More can be found in [START_REF] Toth | The Vehicle Routing Problem[END_REF] [START_REF] Toth | The Vehicle Routing Problem[END_REF].

CVRP with non-homogeneous vehicle fleet

In practice, many vehicle routing problems are addressed by a non-homogeneous vehicle fleet where vehicles of different capacities may be used. The vehicles may also have differences in other operating characteristics such as the average speed of travel or the service time at a customer (e.g. due to different goods handling equipment).

Open VRSP

The term "Open" is applied to problems where each vehicle is not required to return to the central depot after visiting the final customer, i.e. the vehicle routes are open paths instead of closed circuits. This formulation may be appropriate for a situation where vehicles are hired from a third party and the cost of the hire is based on the distance traveled while the vehicles are loaded. For more details, one may refer to [START_REF] Brandaõ | A tabu search algorithm for the open vehicle routing problem[END_REF] [START_REF] Brandaõ | A tabu search algorithm for the open vehicle routing problem[END_REF] and [START_REF] Fu | A new tabu search heuristic for the open vehicle routing problem[END_REF] [START_REF] Fu | A new tabu search heuristic for the open vehicle routing problem[END_REF]. An exact method for the Open VRSP is to be found in [START_REF] Letchford | A branch-and-cut algorithm for the capacitated open vehicle routing problem[END_REF] [START_REF] Letchford | A branch-and-cut algorithm for the capacitated open vehicle routing problem[END_REF].

One variant of the Open VRSP includes the constraint that each route terminates at one of the driver nodes which are specified beforehand. Driver nodes practically correspond to parking lots or homes of drivers. The presence of such fixed driver nodes suits especially those situations in which deliveries to customers are outsourced to a shipping company, or drivers use the same vehicles to commute between home and depot.

Period VRSP

This problem can be defined as the problem of finding routes for all days of a given T-day period to minimize total costs. These types of problems are also called allocation/routing problems. The allocation part consists of the assignment of customers to days of the period, while the routing part governs for the daily planning. Some articles dealing with this variant of the VRSP are available in the literature, for example, [START_REF] Cordeau | A tabu search heuristic for periodic and multi-depot vehicle routing problems[END_REF] [START_REF] Cordeau | A tabu search heuristic for periodic and multi-depot vehicle routing problems[END_REF] and [START_REF] Mourgaya | Periodic Vehicle Routing Problem: classification and heuristic[END_REF] [START_REF] Mourgaya | Periodic Vehicle Routing Problem: classification and heuristic[END_REF].

Other variations

Many other variations of the basic CVRP have been studied that may include some of the features already described. These include multi-depot models where a set of depots replaces the single central depot. If the capacity of the available fleet of vehicles cannot service the required demand, then the objective may be focused on satisfying as many customers as possible using the available fleet. There may also be considerations due to different types of commodities that imply additional constraints. For example, in delivering groceries with vehicles where only the front section of the trailer is refrigerated, frozen goods must be loaded first into the trailer and other non-frozen goods loaded behind. This may lead to a constraint of delivering all non-frozen goods, before frozen goods can be unloaded. Distribution managers may also need to construct routes where a single vehicle is away from the central depot over more than one day and provision must be made for a suitable location for the vehicle to be parked over night while the driver rests before continuing the route the following day. We cite here some of the articles dealing with other variants of the VRSP, for example, [START_REF] Anily | One warehouse multiple retailer systems with vehicle routing costs[END_REF] [START_REF] Anily | One warehouse multiple retailer systems with vehicle routing costs[END_REF] and Baldacciet al., (2006) [START_REF] Baldacci | The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem[END_REF]. For the case of shipping, we cite Barnes-Schuster and Bassok (1997) [START_REF] Barnes-Schuster | Direct Shipping and the Dynamic Single Single-depot/Multi-retailer Inventory System[END_REF].

Arc Routing Problems

These vehicle routing problems are significantly different to all the VRSPs described so far. These have all been Node Routing Problems because the customer demands are all located at points or at the nodes of an underlying graph or network. In Arc Routing Problems, the demands are associated with the links between the nodes, called edges (in the undirected case) or arcs (in the directed case). These represent roads or carriageways in the underlying road network. Such problems arise naturally in several applications such as garbage collection, mail delivery, snow clearing, meter reading, school bus routing, police patrols, and winter gritting. In these cases, a service must be carried out which involves the vehicle traveling the length of road section performing the required service. This is often done at a different speed from when a vehicle is simply traveling along one of the roads without servicing it, which is often referred to as "deadheading". These problems may also have similar variations to those described for Node Routing Problems such as the existence of time window constraints for the service.

A comprehensive survey of Arc Routing Problems is provided in the book edited by [START_REF] Dror | Arc Routing: Theory, Solutions and Applications[END_REF] [START_REF] Dror | Arc Routing: Theory, Solutions and Applications[END_REF].

Stochastic VRSP

The customer demand in many cases is known before the routes need to be planned because orders have been received at the central depot. However in some situations, the size of demand from a customer may be unknown until the vehicle arrives at the customer. This is an example of a stochastic vehicle routing problem where routes must be planned based on the probability distribution of the demand at any customer. In such problems, there needs to be a strategy defined that explains what happens when a vehicle runs out of the commodity it is carrying before it has completed all its deliveries, for example returning to the depot by the shortest route in order to reload (for more details see [START_REF] Stewart | Stochastic vehicle routing: A comprehensive approach[END_REF] [START_REF] Stewart | Stochastic vehicle routing: A comprehensive approach[END_REF], [START_REF] Dror | Vehicle routing with stochastic demands and restricted failures[END_REF] [START_REF] Dror | Vehicle routing with stochastic demands and restricted failures[END_REF] and [START_REF] Yang | Stochastic vehicle routing with restocking[END_REF] [START_REF] Yang | Stochastic vehicle routing with restocking[END_REF]).

The stochastic nature of these problems may take many forms. As well as the level of demand, the timing and location of demand may vary. The availability of resources may vary as well due to service times, dock times and operations in other zones, regions or areas of operation. More details can be found in [START_REF] Secomandi | A rollout policy for the vehicle routing problem with stochastic demands[END_REF] [START_REF] Secomandi | A rollout policy for the vehicle routing problem with stochastic demands[END_REF] and [START_REF] Laporte | The vehicle routing problem with stochastic travel times[END_REF] [START_REF] Laporte | The vehicle routing problem with stochastic travel times[END_REF].

Dynamic or Real-time VRSP

Models discussed so far have been suitable for planning the operations of a vehicle fleet in advance. However models are also being developed to assist in the real-time management and control of a distribution operation. To be effective, these rely on up-to-date information. One type of dynamic model may consider new customer orders that arise after the routes had been initially planned, see [START_REF] Bagchi | Dynamic vehicle sheduling: An expert system approach[END_REF] [START_REF] Bagchi | Dynamic vehicle sheduling: An expert system approach[END_REF]. With a common commodity, the original vehicle routes may be modified to include the new demand. Another issue is the incorporation of real-time information on the location of the vehicles and current information on road conditions (such as unexpected congestion due to an accident). One can refer to Papastavrou [START_REF] Papastavrou | A Stochatic and Dynamic Routing Policy using Branching Processes with State Dependent Immigration[END_REF]. There may be the opportunity to re-route vehicles in the light of this information to reduce costs and to meet customer service time windows. The dynamic behavior has given a name to a typical variant of the VRSP, we name the Dynamic Vehicle Routing Problem: [START_REF] Minkoff | A markov decision model and decomposition heuristic for dynamic vehicle dispatching[END_REF] [START_REF] Minkoff | A markov decision model and decomposition heuristic for dynamic vehicle dispatching[END_REF].

The dynamic vehicle routing problem calls for online algorithms that work in real-time since the immediate requests should be served, if possible. As conventional static vehicle routing problems are NP -hard, it is not always possible to find optimal solutions to problems of realistic sizes in a reasonable amount of computation time. This implies that the dynamic vehicle routing problem also belongs to the class of NP-hard problems, since a static VRP should be solved each time a new immediate request is received. Generally, the more restricted and complex the routing problem is, the more complicated the insertion of new dynamic customers will be (see [START_REF] Hvattum | Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic[END_REF] [START_REF] Hvattum | Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic[END_REF]). For instance, the insertion of new customers in a time window constrained routing problem will usually be much more difficult than in a nontime constrained problem. Note that in an online routing system customers may even be denied service, if it is not possible to find a feasible spot to insert them. Often this policy of rejecting customers includes an offer to serve the customers the following day of operation. However, in some systems -as for instance the pick-up of long-distance courier mail -the service provider (distributor) will have to forward the customer to a competitor when they are not able to serve them. Others article dealing with the DVRP include Gendreau and Potvin (1998) [START_REF] Gendreau | Dynamic Vehicle Routing and Dispatching[END_REF] and [START_REF] Montemanni | Ant Colony System for a Dynamic Vehicle Routing Problem[END_REF] [START_REF] Montemanni | Ant Colony System for a Dynamic Vehicle Routing Problem[END_REF]. A case study on pharmaceutical distribution is relted in de Magalhães and de Sousa [START_REF] De Magalhães | Dynamic VRP in pharmaceutical distribution-a case study[END_REF]. More details on the DVRP can be found in [START_REF] Zeimpekis | Urban dynamic real-time distribution services: Insights from SMEs[END_REF] [START_REF] Zeimpekis | Urban dynamic real-time distribution services: Insights from SMEs[END_REF].

Green Logistics Agenda

The consideration of environmental costs is essentially changing the transportation policy in developed countries, especially those within the European Union. The new environmental sensitivity in today's societies and governments has been described in several studies, such as INFRAS/ IWW and UNITE (INFRAS/IWW [START_REF]INFRAS/IWW: External Costs of Transport. Update study[END_REF], Betancor and Nombela [START_REF] Betancor | The pilot account for Spain, Competitive and sustainable growth programme[END_REF], Samson et al., [START_REF] Sansom | Surface Transport Costs and Charges: Great Britain[END_REF]). The European Conference of Ministers of Transport [START_REF]Ministers of Transport: Resolution No. 98[END_REF] urged European Governments to develop new instruments to incorporate externalities and environmental costs in transport management accounting. Therefore, environmental concerns have highlighted the importance of sustainable transport design.

Road transport is predicted in the EC to grow by a further 33% in the next 20 years (1 ). These trends indicate that, despite technological advances, the environmental impacts of transport will grow unless action is taken at all levels -by government, business and individuals. There is a continuing need to reduce the environmental impacts of some forms of transport -particularly road and air travel -and promote more environmentally friendly transport options such as cycling, public transport and walking.

Road transport services account for 1.6% of the European GDP and give jobs to 4.5 million people in the EU. The whole economy and society depends heavily on efficient road transport, 44% of the goods are moved by trucks and 85% of the persons by cars, buses or coaches.

The aim of the Community's land transport policy is to promote sustainable mobility that is efficient, safe and with reduced negative effects on the environment.

The objectives for road transport are therefore to promote efficient road freight and passengers transport services, to create fair conditions for competition, to promote and harmonise safer and more environmental friendly technical standards, to ensure a minimum fiscal and social harmonisation and to make sure that the rules in road transport are effectively applied without bad ecological impact.

Carbon dioxide emissions from transport have risen throughout the 1990s and now account for around one quarter of the UK's total carbon dioxide emissions. These emissions contribute to climate change that has grave domestic and global consequences. The Government has recently shown international leadership by committing the UK to work towards a 60% reduction in its car-bon dioxide emissions by 2050. For a first model one can refer to [START_REF] Davis | Development and application of an international vehicle emissions model[END_REF] [START_REF] Davis | Development and application of an international vehicle emissions model[END_REF].

Transport contributes to poor air quality. Although discharges of many of the most damaging air pollutants have declined over the last decade, there are still "hot spots" in some city centres and along motorway corridors where concentrations of nitrogen dioxide and particulates from road vehicles exceed safe levels. The Department of Health estimates that there are between 12,000 and 24,000 early deaths each year resulting from poor air quality in our cities. More can be found in London Development Agency Report, March 2004 (2 ).

Some statistics

Some backgrounds statistics recorded by the Department of Transport from the UK Government are mentioned below:

• Over the past 25 years the number of journeys made by car have increased while those by foot, rail, bus and cycle have decreased. The majority of personal travel (93%) and freight movement (65%) is now made by road (10 year transport plan, DTLR 2000).

• Road traffic in the UK, at 7,800 vehicle kilometres for each member of the population, is 26% higher than the OECD Europe average (Environmental Performance Reviews, Organisation for Economic Co-operation and Development).

• Road transport accounts for around 22% of UK CO 2 emissions. For more details, see (3 ).

• Emissions from road transport are the main causes of chronic hot spots for particulates and nitrogen dioxide in major urban areas. Road transport emits 44% of the UK's nitrogen oxides and up to 75% or more of nitrogen oxides in conurbations. Similarly vehicles account for 20% of particles nationally but about twice this in conurbations (The Urban Environment in England and Wales -a detailed assessment, Environment Agency 2002).

• The proportion of human -induced climate change accounted for by transport is three times greater than that of the equivalent amount of ground level emission of carbon dioxide. This is due to the range of greenhouse gases emitted by engines. For more details are available in the Publications of the Parliament, 19 July 2006 (4 ).

The Vienna Declaration in 2006, included some important statistics and views on the fuel used in transport particularly the impact of oil. It said "Transport accounts for about 70% of annual oil consumption in the EU. Ninety-six per cent of the fuel burned in internal-combustion engines comes from mineral oil. No other area of economic activity is so dependent on oil. In view of the foreseeable shortage of oil resources and the further price rises this will entail, all-out efforts must be made to develop oil substitutes for use in transport and, at the same time, to make transport operations far more energy-efficient. From an environmental perspective, there is no alternative to a strategy of weaning the economy off oil, and such a strategy cannot succeed unless it focuses on transport too. In all of this, however, protecting the climate must remain the overarching aim. The adverse impact of some oil substitutes, such as liquidised coal or mined shale, is so drastic that they cannot be contemplated as sustainable alternatives". For more details see ( 5)

Issues linking the VRSP and Green Logistics

There is not much literature that links VRSP models with the Green Logistics issues that have been discussed in the previous section. Most articles are concerned with objectives of minimizing economic costs. Commercial software is also designed to provide feasible solutions that will minimize economic costs. Many software vendors claim that the use of their VRSP package will result in economic benefits for their customers from reductions in the number of vehicles required and distance traveled compared with traditional manual methods. A recent survey of VRSP software packages has been published in OR/MS Today [57]. The reduction in total distance will in itself provide environmental benefits due to the reduction in fuel consumed and the consequent pollutants. However this is generally not measured or emphasized. [START_REF] Palmer | The environmental implications of grocery home delivery[END_REF] [START_REF] Palmer | The environmental implications of grocery home delivery[END_REF] has studied the connection between vehicle routing and emission in the context of grocery home delivery vehicles.

There are some examples in the literature where there are some links between VRSP and the reduction of environmental pollution. These links may not be direct and such issues are discussed in the following subsections.

Time-dependent VRSP

The Time Dependent Vehicle Routing and Scheduling Problem, TDVRSP, consists in optimally routing a fleet of vehicles of fixed capacity when the traveling times between nodes depend on the time of the day that the trip on that arc was initiated. The optimization consists in finding the solution that minimizes the number of tours (the number of vehicles used) and the total traveling time. The traveling time is calculated by knowing the departing time and an accurate estimate of the average speed of the vehicle while traveling on the arc. This version of the VRSP is motivated by the fact that in so many circumstances, traffic conditions cannot be ignored, because at peak times, traffic congestion on popular routes will cause delays. By minimizing the total traveling time, the solutions produced will tend to direct vehicles to roads where they can travel at a faster speed instead of being caught in congestion. It may even be that some solutions imply a greater total travel distance, but there is likely to be environmental benefit because less pollution is created when vehicles are traveling at the best speeds for the environment and for shorter times.

Examples of this approach can be found in the following references [START_REF] Donati | Time Dependent Vehicle Routing Problem with an Ant Colony System[END_REF] [START_REF] Donati | Time Dependent Vehicle Routing Problem with an Ant Colony System[END_REF], [START_REF] Malandraki | Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms[END_REF] [START_REF] Malandraki | Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms[END_REF].

In fact when dealing with time constraints, like the delivery time windows for the customers, the optimal solutions known for the classic case become infeasible and the degree of infeasibility increases with the variability of traffic conditions. So an additional benefit of this approach is that it enables time window constraints to be satisfied more reliably. For the time dependent model, the travel times may also depend on other factors such as the day of the week, or the season of the year. These ideas have been treated in [START_REF] Haghani | A dynamic vehicle routing problem with timedependent travel times[END_REF] [START_REF] Haghani | A dynamic vehicle routing problem with timedependent travel times[END_REF] and [START_REF] Chen | The real-time time-dependent vehicle routing problem[END_REF] [START_REF] Chen | The real-time time-dependent vehicle routing problem[END_REF]. More recently, [START_REF] Eglese | A road timetable to aid vehicle routing and scheduling[END_REF] [START_REF] Eglese | A road timetable to aid vehicle routing and scheduling[END_REF] discussed the issues involved in order to construct a database of road times for a road network. More details are developed in [START_REF] Maden | Models and heuristics algorithms for complex routing and scheduling problems[END_REF] [START_REF] Maden | Models and heuristics algorithms for complex routing and scheduling problems[END_REF].

The data requirements for the TDVRSP are significantly higher than for conventional models. Instead of simply requiring a distance between nodes on the graph representing the road network, a set of travel times are also required for every time interval defined. The shortest time path between any two nodes may be different depending on the time of travel. This is developed in [START_REF] Fu | Estimation of time-dependent, stochastic route travel times using artificial neural networks[END_REF] [START_REF] Fu | Estimation of time-dependent, stochastic route travel times using artificial neural networks[END_REF].

The TDVRSP approach is therefore likely to achieve environmental benefits, but in an indirect way and none of the articles referenced directly measure the environmental benefit of this approach. Part of the work in Work Package 6 of the Green Logistics project is designed to examine this issue.

Hazardous Materials Transportation

The transportation of hazardous materials (hazmat) is a significant environmental issue in the transportation industry. There are billions of tons of hazmat transported throughout the world every year, most of which are important raw materials used by various industries. During the transportation process, one of the most important issues is safety (see [START_REF] Erkut | Modeling of transport risk for hazardous materials[END_REF] [START_REF] Erkut | Modeling of transport risk for hazardous materials[END_REF]). Accidents, though rarely happening, could have large impacts on humans and the natural environment, especially in large urban areas. As an important strategic and tactical problem, the transportation of hazmat has been studied extensively in the research literature. In the early 1990s, the problem was highlighted by researchers and modelled to achieve different objectives, including the minimization of risk, the minimization of risk to special population categories, the minimization of travelling time, and the minimization of property damage (for more details, the reader can refer to [START_REF] Zhang | A Tabu Search Algorithm for the Safe Transportation of Hazardous Materials[END_REF] [START_REF] Zhang | A Tabu Search Algorithm for the Safe Transportation of Hazardous Materials[END_REF]. According to [START_REF] List | Modeling and analysis for hazardous materials transportation: Risk analysis, routing/scheduling and facility location[END_REF] [START_REF] List | Modeling and analysis for hazardous materials transportation: Risk analysis, routing/scheduling and facility location[END_REF], research in this field includes risk analysis, routing/scheduling and facility location. [START_REF] Karkazis | Optimal location of routes for vehicles transporting hazardous materials[END_REF] [START_REF] Karkazis | Optimal location of routes for vehicles transporting hazardous materials[END_REF] introduce an improved routing model in the context of a realistic environment.

In his introduction to hazmat transportation, Erkut ( 6 ) says "What else is relevant in this decision? For example, clearly, the shipment of hazardous waste will carry some risks to the public along the route, as well as to the environment. Accidents do happen, and the contents of the truck can be released in a serious accident. An accident can be quite costly to your company in several ways; for example the decision makers may be liable for (some of ) the cleanup costs and damages, and they insurance premiums are likely to increase. Hence, they would like to consider minimizing risk, alongside cost. How should they quantify risk on a stretch of highway? Do they focus on the likelihood of an accident by the truck, or on the consequences of that accident, or both? Should they use historical accident rates on that highway (or highway class)? What about known danger spots, such as railroad crossings and left turns? To evaluate the population to be impacted, should they use the number of people that live within a certain distance of the highway? If so what should be this distance? How to include buildings with a high concentration of population (such as schools and hospitals) in their analysis? How to consider environmental risk? It seems that the problem of selecting the "best" route for hazardous waste shipment between two destinations is more complicated than the selection of the route for any long weekend trip."

There are two major sources of complexity in this problem: quantifying different objectives, and trading off the objectives. The first one is more of a technical problem; a problem of identifying the necessary data, collecting and processing it, and identifying certain good routes via the use of quantitative modeling techniques. The second one is more of a judgement problem.

Erkut and Ingolfsson (2004) [START_REF] Erkut | Transport risk models for hazardous materials[END_REF] suggest that avoiding a catastrophe (an accident with a very large consequence) is a relevant issue in routing hazardous materials and propose three models, two of which are computationally hard and therefore only offer theoretical insights. [START_REF] Leonelli | Hazardous materials transportation: a risk-analysis-based routing methodology[END_REF] [START_REF] Leonelli | Hazardous materials transportation: a risk-analysis-based routing methodology[END_REF] employ a risk-analysis-based routing methodology to solve the hazmat transportation problem and formulate it as a minimum cost flow problem. A survey by [START_REF] Luedtke | Hazmat transportation and security: survey and directions for future research[END_REF] [START_REF] Luedtke | Hazmat transportation and security: survey and directions for future research[END_REF] summarizes some research results on hazmat transportation. Some models have been built as a bi-objective vehicle routing and scheduling problem.

There is also a unique paper by [START_REF] Kara | Designing a road nework for hazardous materials transportation[END_REF] [START_REF] Kara | Designing a road nework for hazardous materials transportation[END_REF] focusing on the nature of the relationship between the regulator and carriers. A government has the authority to close certain roads to hazmat transportation, while it is the carrier's strategy to choose roads to route their vehicles.

The safe transportation problem of hazmat is a variant of VRPTW, which considers the vehicle scheduling problem between a depot (a distribution centre of hazmat) and several customers. Each road segment has an upper bound for transportation quantity. The transportation is regarded as "safe" if the load does not exceed the upper bound when a vehicle is passing through a specific road segment. The objective is to minimize the number of vehicles used and the total travelling distance, provided that the transportation used is safe on all road segments. A model of safe transportation of hazardous materials based on VRPTW is such that each road segment (edge), (i, j), is associated with a value, v ij , which is the upper bound of the load for vehicles passing along this road segment and determined by the nearby environment. Therefore, the complete scheduled transportation route is safe if the loads of all the vehicles do not exceed the upper bound of each road segment when passing along it.

Other approaches may aim to assign each vehicle to a different route in order to spread the risk. In this case the model assigns one and only one route for each vehicle between the depot and each customer or each pair of customers.

An alternative approach is not to consider the measure of risk as an additional constraint, but to assign a risk measure to the use of any road link and then find a set of routes that minimize the total risk as an objective.

Research has primarily addressed route-finding techniques that minimize either the total travel time, the expected number of accidents (fatal or otherwise), the accident probability, the residential population within a given distance from the route, the risk of spill, or some combination of these factors. This research has been surveyed by List et al., [START_REF] List | Modeling and analysis for hazardous materials transportation: Risk analysis, routing/scheduling and facility location[END_REF]. It is immediately apparent that such single objective models cannot take into account conflicting criteria such as truck operating costs and expected damage. In fact, other researchers have considered Hazmat transportation as a bi-objective problem where one objective relates to risk and the other to the cost of the route (see [START_REF] Zografos | Multi-objective programming approach for routing hazardous materials[END_REF] [START_REF] Zografos | Multi-objective programming approach for routing hazardous materials[END_REF]).

Dynamic VRSP

There is potential for environmental benefits to arise from the use of dynamic or real-time models to manage a distribution activity. This is because vehicles may be redirected to avoid unexpected congestion due, for example, to an accident. However the implementation of these models requires real-time information on the locations of the vehicles, current traffic conditions and good communications between management and drivers (see [START_REF] Bianchi | Notes on Dynamic Vehicle Routing -The State of the Art[END_REF] [START_REF] Bianchi | Notes on Dynamic Vehicle Routing -The State of the Art[END_REF]). [START_REF] Psaraftis | A dynamic programming solution to the single vehicle many-to many immediate request dial-a-ride problem[END_REF][START_REF] Psaraftis | Dynamic vehicle routing problem[END_REF] [START_REF] Psaraftis | A dynamic programming solution to the single vehicle many-to many immediate request dial-a-ride problem[END_REF][63] lists 12 issues where the dynamic vehicle routing problem differs from the conventional static routing problem. Below we give a brief summary of these issues as they are indeed very central to our discussion of static versus dynamic routing.

1. Time dimension is essential. In a static routing problem the time dimension may or may not be important. In the dynamic counterpart time is always essential. The dispatcher must as a minimum know the position of all vehicles at any given point in time and particularly when the request for service or other information is received by the dispatcher.

2. The problem may be open-ended. The process is often temporally bounded in a static problem. The routes start and end at the depot. In a dynamic setting the process may very well be unbounded. Instead of routes one considers paths for the vehicles to follow.

3. Future information may be imprecise or unknown. In a static problem all information is assumed to be known and of the same quality. In a real-life dynamic routing problem the future is almost never known with certainty. At best probabilistic information about the future may be known.

4. Near-term events are more important. Due to the uniformity of the information quality and lack of input updates all events carry the same weight in a static routing problem, whereas in a dynamic setting it would be unwise immediately to commit vehicle resources to long-term requirements. The focus of the dispatcher should therefore be on near-term events when dealing with a dynamic routing problem.

5. Information update mechanisms are essential. Almost all inputs to a dynamic routing problem are subject to changes during the day of operation. It is therefore essential that information update mechanisms are integrated into the solution method. Naturally, information update mechanisms are not relevant within a static context.

6. Re-sequencing and reassigning decisions may be warranted. In dynamic routing new input may imply that decisions taken by the dispatcher become suboptimal. This forces the dispatcher to reroute or even reassign vehicles in order to respond to the new situation.

7. Faster computation times are necessary. In static settings the dispatcher may afford the luxury of waiting for a few hours in order to get a high quality solution, in some cases even an optimal one. In dynamic settings this is not possible, because the dispatcher wishes to know the solution to the current problem as soon as possible (preferably within minutes or seconds). The running-time constraint implies that rerouting and reassignments are often done by using local improvement heuristics like insertion and k-interchange.

8. Indefinite deferment mechanisms are essential. Indefinite deferment means the eventuality that the service of a particular demand be postponed indefinitely because of that demands unfavourable geographical characteristics relative to the other demands. This problem could for instance be alleviated by using time window constraints or by using a nonlinear objective function penalizing excessive wait. 9. Objective function may be different. Traditional static objectives such as minimization of the total distance traveled or the overall duration of the schedule might be meaningless in a dynamic setting because the process may be open-ended. If no information about the future inputs is available, it might be reasonable to optimize only over known inputs. Some systems also use nonlinear objective functions in order to avoid undesirable phenomena such as the above mentioned indefinite deferment.

10. Time constraints may be different. Time constraints such as latest pickup times tend to be softer in a dynamic routing problem than in a static one. This is due to the fact that denying service to an immediate demand, if the time constraint is not met, is usually less attractive than violating the time constraint.

11. Flexibility to vary vehicle fleet size is lower. In static settings, the time gap between the execution of the algorithm and the execution of the routes usually allows adjustments of the vehicle fleet. However, within a dynamic setting the dispatcher may not have instant access to backup vehicles. Implications of this may mean that some customers receive lower quality of service.

12. Queueing considerations may become important. If the rate of customer demand exceeds a certain threshold, the system will become congested and the algorithms are bound to produce meaningless results. Although vehicle routing and queueing theory are two very well-studied disciplines, the effort to combine these has been scant.

Conclusions

"Classical" vehicle routing and scheduling models aim to minimize cost (usually related to the number of vehicles and distance). This will also provide some environmental benefit compared with solutions that use unnecessary distance (because there will be some fuel saving). In their INRETS report, Pronello and André (2000) [START_REF] Pronello | Pollutant emissions estimation in road transport models[END_REF] suggest that existing models to measure the pollution caused by a set of vehicle routes may be unreliable. This is because reliable pollution models require input measures which are not normally part of the output of VRSP models. For example, the time spent travelling by a vehicle when the engine is cold may have a significant effect on the pollution produced. Without these linking models it is difficult to quantify the environmental benefits of different VRSP solutions.

Even if it is difficult to measure the precise environmental benefit, there should be some value in versions of VRSP models that consider alternative objectives to pure economic considerations. For example, the time-dependent vehicle routing models represent an approach which should indirectly produce less pollution because vehicles will tend to be directed away from congestion.

A policy which is being considered is the introduction of "Road Pricing". The use of roads would be charged in the UK and higher charges would be levied for vehicles using roads then tend to become congested at particular times of day. If this policy is adopted, then the development of VRSP models to minimise costs including the road price may also tend to produce environmental benefits and prevent congestion. However, the environmental benefits will depend heavily on the size of any additional charges and the schemes that are applied.

Road Pricing means that motorists pay directly for driving on a particular roadway or in a particular area. Value Pricing is a marketing term which emphasizes that road pricing can directly benefit motorists through reduced congestion or improved roadways. Economists have long advocated Road Pricing as an efficient and equitable way to pay roadway costs and encourage more efficient transportation. Road Pricing has two general objectives: revenue generation and congestion management.

However in this literature review of VRSP and Green Logistics, we have not encountered any models where the objective to be optimized is an environmental objective, in terms of a measure of pollution. This is a research challenge for the future.

Information may be consulted on www.europa.eu (accessed 13/01/2007)

The Public Health Impact of Cities and Urban Planning, Karen Jochelson, The King's Fund, March 2004, www.lda.gov.uk/server/show/ConMediaFile.725 (accessed 15/12/2006)

http://www.dft.gov.uk/stellent/groups/dft transstats/ documents/pdf/dft transstats pdf 026311.pdf (accessed15/12/2006)

http://www.publications.parliament.uk/pa/cm200506/cmselect/cmenvaud/ 981/981we20.htm (accessed6/12/2006)

http://www.greens-efa.org/cms/topics/dokbin/109/ 109638.vienna declaration@en.pdf (accessed 13/01/2007)

http://www.ualberta.ca/ERSC/pages/erhan.htm (accessed 12/01/2007)


José Niño-Mora

Sofía S Villar
email: svillar@est-econ.uc3m.es

Sensor Scheduling for Hunting Elusive Hiding Targets via Whittle's Restless Bandit Index Policy

We consider a sensor scheduling model where a set of identical sensors are used to hunt a larger set of heterogeneous targets, each of which is located at a corresponding site. Target states change randomly over discrete time slots between "exposed" and 'hidden," according to Markovian transition probabilities that depend on whether sites are searched or not, so as to make the targets elusive. Sensors are imperfect, failing to detect an exposed target when searching its site with a positive misdetection probability. We formulate as a partially observable Markov decision process the problem of scheduling the sensors to search the sites so as to maximize the expected total discounted value of rewards earned (when targets are hunted) minus search costs incurred. Given the intractability of finding an optimal policy, we introduce a tractable heuristic search policy of priorityindex type based on the Whittle index for restless bandits. Preliminary computational results are reported showing that such a policy is nearly optimal and can substantially outperform the myopic policy and other simple heuristics.

I. INTRODUCTION

In recent years, the investigation of effective dynamic policies for operating wireless sensor networks has become an active research area. An issue that has received much attention is the design of scheduling policies to allocate over time a set of sensors to track a larger set of moving targets, to optimize a system-wide performance objective. See, e.g., [1].

The sensors provide error-prone measurements of the sensed targets, such as their location, or their presence or absence at a given location. The current knowledge on each target is represented by its information state, which evolves via Bayesian updates depending on whether or not the target is sensed at each time slot. This allows us to formulate the optimal sensor scheduling problem as a partially observable Markov decision process (POMDP) with special structure, which often fits into the framework of the continuous-state multi-armed bandit problem, either in its classic version or, more often, in its restless variant. See [START_REF] Washburn | Application of multi-armed bandits to sensor management[END_REF].

Although the multi-armed restless bandit problem (MARBP) is, generally, computationally intractable, formulating a sensor scheduling problem in such a framework allows us to use the general heuristic index policy proposed by Whittle in [START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF] for the former problem. If M sensors are available to track N > M targets, such a policy attaches an index λ * n (x n ) to each target n = 1, . . . , N as a function of its current information state x n , and then senses at each time up to M targets with higher index values, among those targets, if any, whose current index value exceeds or equals the search cost c n i.e., such that λ * n (x n ) c n . Such an approach has been used to address sensor scheduling problems in, e.g., [START_REF] La Scala | Optimal target tracking with restless bandits[END_REF]- [START_REF] Liu | Indexability of restless bandit problems and optimality of Whittle index for dynamic multichannel access[END_REF]. Besides a policy, it further provides an upper bound on the optimal problem value, which can be used to assess the optimality loss of heuristic policies. A growing body of numerical work suggests that the performance of the Whittle index policy is often nearly optimal.

The targets are typically assumed to follow dynamics that are unaffected by sensing decisions. Yet, in certain applications, targets are smart, in that they react to sensing actions by changing their dynamics to make them elusive. However, few papers consider sensor scheduling with smart targets. [START_REF] Kreucher | Adaptive multimodality sensor scheduling for detection and tracking of smart targets[END_REF] uses reinforcement learning to obtain a non-myopic policy for detection and tracking of smart targets, while [START_REF] Liu | Blending sensor scheduling strategy with particle filter to track a smart target[END_REF] uses particle filter methods, and [START_REF] Savage | Sensor management for tracking smart targets[END_REF] uses game theory. [START_REF] Rucker | Using agent-based modeling to search for elusive hiding targets[END_REF] uses agentbased modeling to address a model similar to ours.

This paper extends such a line of research by investigating a sensor scheduling model where a set of identical sensors are used to hunt a larger set of heterogeneous targets, each of which is located at a corresponding site. Target states change randomly over discrete time slots between "exposed" and 'hidden," according to Markovian transition probabilities that depend on whether sites are searched or not, so as to make the targets elusive. Sensors are imperfect, failing to detect an exposed target when searching its site with a positive misdetection probability.

As a specific motivating application, consider the problem investigated in [START_REF] Rucker | Using agent-based modeling to search for elusive hiding targets[END_REF], where the targets are mobile platforms (transporter-erector-launchers) for launching Scud missiles, and the sites are areas where it is known that such platforms are located. Sensors can be mounted on unmanned aerial vehicles (UAV). The optimal sensor scheduling problem is to devise a scheduling policy for minimizing the average time until all missile launchers are detected and destroyed.

The remainder of the paper is organized as follows. Section II describes and formulates the model. Section III reviews the restless bandit indexation approach as it applies to the design of index policies for the present model. Section IV outlines how to deploy such a methodology to compute the index. Section V reports on several simulation experiments where the proposed index policy is compared with alternative heuristic policies. Finally, section VI ends the paper with concluding remarks. Detailed analysis and proofs will be included in a full version of this paper, which is currently under preparation.

II. MODEL DESCRIPTION AND FORMULATION

We consider a model where M sensors are available to hunt N > M elusive targets, where each target n is located at a corresponding site n = 1, . . . , N . The target at site n changes its visibility state s n,t at discrete time slots t = 0, 1, . . . over an infinite horizon between the hidden state (s n,t = 0), in which it is invisible to sensors but cannot perform its tasks, and the exposed state (s n,t = 1), in which it can perform its tasks but can be detected by a sensor searching the site.

The visibility state s n,t of target n evolves according to Markovian transition probabilities depending on whether or not its site is searched. We assume that only one sensor can search a site at each time slot, and model sensing decisions by binary actions a n,t , where a n,t = 1 if site n is searched at time t, and a n,t = 0 otherwise. When a n,t = a the target moves from the hidden to the exposed state (resp. from the exposed to the hidden state, in case the target is not detected) with probability p (a) n (resp. q (a) n ). Such probabilities are such that, after a site is searched and the target on it is not detected, it is more likely that the target moves into or remains in the hidden state than if the site had not been searched, i.e., q

(1)

n > q (0) n and p (1) n < p (0)
n . We assume that the visibility state processes have positive autocorrelation, i.e., ρ

(a) n 1 -p (a) n -q (a) n > 0.
The target at site n is hunted when it is searched if it is exposed, which yields a reward r n . Information on the visibility state of target n is gained by sensing it, which provides a sensing outcome o n,t ∈ {0, 1}: o n,t = 1 if the target is detected and hunted, and o n,t = 0 otherwise. Sensing is imperfect, in that the target at site n will not be detected when the site is searched and the target is exposed with a positive misdetection probability α n = P{o n,t = 0 | s n,t = 1}. Hence, the visibility state s n,t is not observable, but it is tracked by the information state X n,t ∈ X [0, 1], giving the posterior probability that the target will be exposed in slot t, conditioned on the history {X n,s , a n,s : 0 ≤ s < t} ∪ {X n,t }.

Since we assume that a site n whose target that has been hunted (x n = 0) is removed from further search, we partition a target state space X into the set X (0, 1] of controllable states, where both actions a n ∈ {0, 1} are available, and the uncontrollable state 0, where only action a n = 0 is available.

The dynamics of the information state for target n under each sensing action are obtained via Bayesian updates. If the site is searched in slot t (a n,t = 1), with its information state being X n,t , and the target is detected (o n,t = 1), which happens with probability (1α n )X n,t , then the target is hunted, and the site is removed. We model such a situation by letting the target information state drop to X n,t+1 = 0.

On the other hand, if the target is not detected (o n,t = 0), which happens with probability 1 -(1α n )X n,t , it is readily calculated that the information state changes to

X n,t+1 = p (1) n + ρ (1) n α n X n,t 1 -(1 -α n )X n,t .
Thus, if site n is searched, its next information state is obtained in a randomized fashion depending on the sensing outcome. Finally, if site n is not searched (a n,t = 0) in slot t, with its information state being X n,t , then, as long as the target has not yet been hunted (i.e., if X n,t > 0), its next information state is determined by X n,t+1 = p

(0) n (1 -X n,t ) + 1 -q (0) n X n,t = p (0) n + ρ (0)
n X n,t . Yet, if the target has already been hunted (X n,t = 0), its information state remains at 0, i.e., X n,t+1 = 0.

Actions are prescribed by a scheduling policy π from the class Π(M ) of admissible policies. The class Π(M ) consists of the nonanticipative policies (i.e., based on the history of states and actions) that search at most M sites per slot:

N n=1 a n,t M, t = 0, 1, . . . (1)
As for the economic consequences of the actions, taking action a n on site n when it occupies the information state x n yields the expected one-slot net reward

R n (x n , a n ) r n (1- α n ) x n -c n a n , where c n 0 is the cost of searching site n.
Consider the problem of finding a discounted-reward optimal policy,

max π∈Π(M) E π x0 ∞ t=0 N n=1 β t R n X n,t , a n,t , (2)
where 0 < β 1 is the discount factor, x 0 = (x n,0 ) N n=1 , and

E π x0 [•]
denotes expectation under policy π conditioned on the initial joint state being equal to x 0 . Note that the case β = 1 (total expected reward criterion) is well defined here.

Problem ( 2) is a POMDP of MARBP type. Since such problems are hard to solve, our main goal is to develop tractable policies that are close to optimal.

Given their intuitive appeal and tractability, we will focus on heuristics of priority-index type. Such policies attach an index λ n (x n ) to each site n as a function of its state x n . At time t, the index policy selects at most M sites to sense, using λ n (x n,t ) as a priority index for sensing site n (where a larger index value means a higher priority), among those sites, if any, at which the current index value exceeds or equals the search cost (λ n x n,t c n ), breaking ties arbitrarily.

III. MARBP FORMULATION AND THE WHITTLE INDEX

We will deploy the approach developed and applied in other real-state MARBP models in [START_REF] Niño-Mora | An index policy for dynamic fading-channel allocation to heterogeneous mobile users with partial observations[END_REF]- [START_REF] Niño-Mora | Multitarget tracking via restless bandit marginal productivity indices and Kalman filter in discrete time[END_REF], as reviewed next.

A. Relaxed Problem, Lagrangian Relaxation and Performance Bound

Along the lines introduced in [START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF] for the equalityconstrained case, we first construct a relaxation of (2), replacing the sample-path activity constraint (1) with the weaker constraint that the expected total discounted (ETD) number of sensed sites does not exceed M/(1β), i.e.,

E π x0 ∞ t=0 N n=1 β t a n,t M 1 -β . (3)
Denoting by Π the class of nonanticipative scheduling policies that are allowed to search any number of sites at any time, the relaxed primal problem is

max (3),π∈ Π E π x0 ∞ t=0 N n=1 β t R n X n,t , a n . (4)
Note that the optimal value V R (x 0 ) of ( 4) gives an upper bound on the optimal value V * (x 0 ) of (2).

To address the constrained MDP (4) we use a Lagrangian analysis, dualizing the constraint (3) using a multiplier λ 0. The resulting problem

max π∈ Π E π x0 ∞ t=0 N n=1 β t R n X n,t , a n,t -λa n,t + M λ 1 -β (5
) is a Lagrangian relaxation of (4), whose optimal value V L (x 0 ; λ) gives an upper bound on V R (x 0 ). The Lagrangian dual problem is to find a value λ * (x 0 ) of λ giving the best such upper bound, which we denote by V D (x 0 ):

V D (x 0 ) = min λ 0 V L (x 0 ; λ) (6)
Note that ( 6) is a scalar convex optimization problem, since λ → V L (x 0 ; λ) is convex. Under suitable regularity conditions, strong duality holds, i.e., V D (x 0 ) = V R (x 0 ).

B. Indexability and the Whittle Index Policy

Since target state transitions are independent, problem (5) decomposes into the N single-sensor single-site subproblems [START_REF]A restless bandit marginal productivity index for opportunistic spectrum access with sensing errors[END_REF] where Π n denotes the class of admissible policies for operating a single sensor on site n. Note that the Lagrange multiplier λ plays the role of an additional search cost.

max πn∈Πn E πn xn,0 ∞ t=0 β t {R n X n,t , a n,t -λa n,t } ,
Denoting by V L n (x n,0 ; λ) the optimal value of subproblem [START_REF]A restless bandit marginal productivity index for opportunistic spectrum access with sensing errors[END_REF], the optimal value V L (x 0 ; λ) of ( 5) is decomposed as

V L (x 0 ; λ) = M λ (1 -β) + N n=1 V L n (x n,0 ; λ). (8)
We will say that the single-site subproblem ( 7) is indexable if there exists an index λ * n (x n ) attached to the controllable information states x n ∈ X (0, 1], which is such that, for any value of λ ∈ R, it is optimal to search the site when it occupies state x n , regardless of the initial state, iff λ * n (x n ) λ.We will refer to λ * n (x n ) as the Whittle index, or the marginal productivity (MP) index for site n.

If each subproblem [START_REF]A restless bandit marginal productivity index for opportunistic spectrum access with sensing errors[END_REF] is indexable, then we can use the Whittle indices λ * n (x n ) to obtain a corresponding priorityindex policy, as described above.

C. Sufficient Indexability Conditions and Index Evaluation

The indexability property for restless bandits, introduced in [START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF], cannot be taken for granted, needing to be established for the model at hand. The introduction in [START_REF] Niño-Mora | Restless bandits, partial conservation laws and indexability[END_REF], [START_REF]Dynamic allocation indices for restless projects and queueing admission control: A polyhedral approach[END_REF] of sufficient indexability conditions for discrete-state restless bandits, along with an index algorithm, based on satisfaction of partial conservation laws (PCLs), provided a methodology for such a purpose. See the review [START_REF]Dynamic priority allocation via restless bandit marginal productivity indices[END_REF]. Such conditions were extended to real-state restless bandits in [START_REF] Niño-Mora | An index policy for dynamic fading-channel allocation to heterogeneous mobile users with partial observations[END_REF], as reviewed next.

We focus here on a generic site and target, dropping the subscript n from the notation. We will evaluate sensing policies π ∈ Π along two dimensions: the work measure g(x, π), giving the ETD number of times the site is searched under policy π starting from X 0 = x; and the reward measure f (x, π), giving the ETD reward earned:

g(x, π) E π x ∞ t=0 β t a t , f (x, π) E π x ∞ t=0 β t R(X t , a t ) .
The single-site subproblem ( 7) is thus formulated as

max π∈Π f (x, π) -λg(x, π). (9)
By standard results, there exists an optimal policy for the discounted real-state MDP (9) that is stationary deterministic. Such policies are conveniently represented by their active (state) sets, i.e., the set of information states where the active action (search the site) is prescribed. For an active set B ⊆ X, we will thus refer to the B-active policy.

We will further focus on the family of threshold policies. Given a threshold z ∈ R , the z-threshold policy prescribes to search the site in information state x iff x > z, so its active set is B(z) {x ∈ X : x > z}. Note that B(z) = (z, 1] for 0 z < 1, B(z) = X = (0, 1] for z < 0, and B(z) = ∅ for z 1. We denote by g(x, z) and f (x, z) the work and reward measures under the z-threshold policy.

In the sequel, we will write b(x) 1 -(1α)x, and

φ (0) (x) p (0) + ρ (0) x, φ (1) (x) p (1) + ρ (1) αx b(x) . (10)
Given threshold z, the performance measures g(x, z) and f (x, z) are characterized as the unique solutions to the following functional equations:

g(x, z) =      1 + βb(x)g φ (1) (x), z , x ∈ (z, 1] βg φ (0) (x), z , x ∈ (0, z] 0 x = 0, (11)
f (x, z) =      R(x, 1) + βb(x)f φ (1) (x), z , x ∈ (z, 1] βf φ (0) (x), z , x ∈ (0, z] 0 x = 0. (12
) Given threshold z and action a, denote by a, z the policy that takes action a in the initial time slot and then follows the z-threshold policy thereafter. Define the marginal work measure w(x, z) and the marginal reward measure r(x, z) for x ∈ X by w(x, z) g(x, 1, z )g(x, 0, z )

(13) = 1 + βb(x)g(φ (1) (x), z) -β g(φ (0) (x), z), r(x, z) f (x, 1, z ) -f (x, 0, z ) = R(x, 1) + βb(x)f (φ (1) (x), z) -β f (φ (0) (x), z). (14)
If w(x, z) = 0, define the marginal productivity measure

λ(x, z) r(x, z) w(x, z) . ( 15
)
We say that subproblem ( 9) is PCL-indexable (with respect to threshold policies) if:

(i) positive marginal work: w(x, z) > 0, x ∈ X, z ∈ R; (ii)
nondecreasing index: the index defined by

λ * (x) λ(x, x), x ∈ X. ( 16
)
is monotone nondecreasing in x Theorem 1. If subproblem (9) is PCL-indexable, then it is indexable and the λ * (x) in ( 16) is its Whittle index.

IV. INDEX COMPUTATION

To apply the PCL-indexability conditions, we must first calculate the evaluation measures g(x, z) and f (x, z).

In some cases (see [START_REF] Niño-Mora | An index policy for dynamic fading-channel allocation to heterogeneous mobile users with partial observations[END_REF]), such measures can be evaluated in closed form, which allows for direct verification of the PCL-indexability conditions, and yields a closed-form index formula. Such is not the case, however, with the present model. This section outlines how to solve the evaluation equations to perform a PCL-indexability analysis, and further shows how to use such solutions to compute in practice the index λ * (x).

A. Total and Marginal Evaluation Measures

As a preliminary step for solving [START_REF] Liu | Blending sensor scheduling strategy with particle filter to track a smart target[END_REF] and ( 12), we define φ (a) t (x) for a ∈ {0, 1} as the t-th iterate of the recursion φ

a) t (x) φ (a) (φ (a) t-1 (x)). Note that, for any x ∈ X, lim t→∞ φ (a) t (x) = φ (a)
∞ , where

φ (0) ∞ = p (0) 1 -ρ (0) , φ (1) ∞ = γ -γ 2 -4(1 -α)p (1) 2(1 -α) , with γ 1 -ρ (1) + (1 -α)(p (1) + ρ (1)
). The above assumptions on the transition probabilities for the target visibility state ensure that φ

(1)

∞ < φ (0)
∞ . Hence, to solve the evaluation equations we must distinguish three cases, as discussed below. In the sequel we assume, without loss of generality, that the search cost is c = 0.

Case I: z ∈ 0, φ (1)
∞ : In this case, once the target state X t reaches the active set B(z) = (z, 1], it remains in B(z) as long as the target is not hunted. Thus, given the initial state x z, let t * 0 (x, z) min{t 1 : X t > z} be the first hitting time to B(z), which can be computed as t * 0 (x, z) min{t 1 : φ (0) t (x) > z}, and let y φ (0) t * 0 (x,z) (x). Also, denote by θ(x, z, t) the survival probability that the target has not been hunted before time slot t under the z-threshold policy, starting from state x. Note that, for x > z,

θ(x, z, t) = t-1 s=0 1 -(1 -α) φ (1)
s (x) , t 1, and θ(x, z, 0) = 1. We have the work measure evaluation

g(x, z) =      ∞ t=0 β t θ(x, z, t), x ∈ (z, 1] β t * 0 (x,z) g(y, z), x ∈ (0, z]. (17)
Similarly, we obtain the reward measure evaluation

f (x, z) =      ∞ t=0 β t θ(x, z, t)R φ (1) t (x, z), 1 , x ∈ (z, 1] β t * 0 (x,z) f (y, z), x ∈ (0, z]. (18)
The above infinite series are convergent, yet they do not admit closed form formulae. Hence, they must be truncated in practice to approximate w(x, z) and r(x, z) via ( 13)-( 14), and for approximating the index λ * (x) in ( 16) for 0 < x φ

(1)

∞ . Case II: z ∈ φ (1) ∞ , φ (0)
∞ : In this case, the state X t jumps above and below the threshold z until the target is found. Following the argument introduced in [START_REF]A restless bandit marginal productivity index for opportunistic spectrum access with sensing errors[END_REF], define the map φ(x, z) 1 {x>z} φ (1) (x) + 1 {x z} φ (0) (x), and let φ 0 (x, z) = x, φ t (x, z) = φ(φ t-1 (x, z), z) for t 1. Then, writing a t (x, z) 1 {φt(x,z)>z} , (φa) t (x, z) φ t (x, z)a t (x, z). In this case, the survival probability θ(x, z, t) has the evaluation

θ(x, z, t) = t-1 s=0 1 -(1 -α) (φa) s (x, z) , t 1, with θ(x, z, 0) = 1. We have that g(x, z) = ∞ t=0 β t θ(x, z, t)a t (x, z), ( 19
) f (x, z) = ∞ t=0 β t θ(x, z, t)(φa) t (x, z). ( 20
)
Since the series ( 19) and (20) cannot be calculated in closed form, we must evaluate them numerically by truncating them.

From this, we can approximately compute the index λ * (x) via ( 16) for φ

(1)

∞ < x < φ (0) ∞ . Case III: z ∈ φ (0)
∞ , 1 : In this case, X t remains in the passive set B c (z) = (0, z] after first hitting it. For x > z, let τ * (x, z) min{t 1 : X t z} be the first hitting time to B c (z) starting from x. Note that τ * (x, z) is a random variable with maximum value t * 1 (x, z) min{t 1 : φ

(1) t (x) z}. Then, we have that, for x > z,

g(x, z) = t * 1 (x,z)-1 t=0 β t θ(x, z, t), (21) f (x, z) = t * 1 (x,z)-1 t=0 β t θ(x, z, t)R(φ (1) t (x), 1), (22)
where θ(x, z, t) is the survival probability as in Case I. From the above and ( 13)-( 14), we can compute the w(x, z) and r(x, z) for x > z by computing finite sums. Further, for x z it is readily seen that w(x, z) = 1 and r(x, z) = R(x, 1). Therefore, the index in ( 16) reduces to

λ * (x) = R(x, 1), φ (0) ∞ x 1 (23)

B. Verification of PCL-indexability and Index Evaluation

Based on the results in Section IV-A and on further work not shown here, we present the following conjecture.

Conjecture 1. The single-site search problem ( 9) is PCLindexable for β ∈ [0, β * ), with

β * = (1-α) 1 - 1 -(1 -α)(p (1) + ρ (1) ) (1 -α)φ (1) ∞ (1 -(1 -α)φ (1) ∞ )
.

Therefore, under Conjecture 1, the index λ * (x) calculated above is the Whittle index.

V. COMPUTATIONAL EXPERIMENTS

A. Index Evaluation

The index was computed using a Matlab script based on the results in Sec. IV for a target instance with q (0) = 0.1, p (0) = 0.5, q (1) = 0.5, p (1) = 0.3, r = 1, and α = 0.05. The fixed points are thus φ

(1) ∞ = 0.3043 and φ (0) ∞ = 0.8333. The discount factor β varied over the range β ∈ {0, 0.1, 0.2, . . . , 0.9, 0.99} and β * = 0.7472. For each β, the index λ * (x) was evaluated on a grid of x values of width 10 -2 , and the infinite sums of Cases I and II were approximately evaluated by truncating them to T = 10 4 . Fig. 1 plots the results. Note that the index λ * (x) is continuous in x and piecewise differentiable, converging as β ր 1 to a limiting index. Note also that, for small enough x, the index λ * (x) is negative, reflecting the intuition that it is counterproductive to search a site when it is very unlikely that the target is visible, as doing so will only drive the target into hiding, delaying the hunt. For each x, the time expended to compute λ * (x) was negligible.

B. PCL-indexability

This section presents computational evidence for the validity of Conjecture 1 for the target instance analyzed in Sec. V-A. As required by the PCL-indexability condition (ii), Fig. 1 shows that in each case the index λ * (x) is strictly increasing in x. Regarding condition (i), Fig. 2 shows the marginal work measure w(x, z) for fixed threshold values z in {0.05, 0.5, 0.85}, letting x vary in X, analyzing Β 0 Β 0 .9 9

Β 1 Φ 0 Φ 1 1 x Λ x
Fig. 1: The index λ * (x) for different discount factors β.

a z value for each of the three cases described in Sec. IV-A. The discount factor β varies over the range β ∈ {0, 0.1, 0.2, . . . , 0.9, 0.99, 0.999}. For each β and z, the index w(x, z) was evaluated on a grid of x values of width 10 -2 , and the infinite sums of cases I and II were approximately evaluated by truncating them to T = 10 4 . Fig. 2 illustrates how w(x, z) differs for each threshold case considered. Further, notice that, in the examples for Case I (z = 0.05) and Case II (z = 0.5), the marginal work measure positivity condition only holds for β 0.8.

C. Benchmarking the Whittle Index Policy

We have performed some small-scale preliminary simulation studies, where the performance of the proposed Whittle index policy is compared against simpler policies: the myopic policy, based on index λ M (x) = R(x, 1), which corresponds with the case β = 0, the belief state policy, based on index λ B (x) = x, and the random selection policy which picks a site at random, with each site having the same probability of being selected.

Experiment #1: Cautious and Reckless Targets

In this experiment we assess the relative performance of the Whittle index policy against the other heuristics distinguishing target instances between reckless and cautious. We call reckless those targets that "after not being searched, are highly likely to expose themselves", i.e., with p (0) ≈ 1, while cautious targets display the opposite behavior, i.e., have p (0) ≈ 0 (while having p (0) > p (1) ). Each base instance has a single sensor M = 1 for N = 30 sites. In one instance all targets are reckless with p (1) n = 0.97, q (0) n = 0.003, α n = 0.30 and r n = 1 for all n. Also, we take the initial state x n = 1, which corresponds to exact knowledge of N exposed targets at the start of the search. Sensing costs were taken to be zero and we consider two possible discount factors β ∈ {0.7, 0.99}, where β * is equal to 0.9491 both for the reckless and cautious instance. Both base instances were modified, letting the number of sensors increase from M = 1 Fig 3 shows the ETD net rewards under each policy as the number of sensors in the network grows. The upper bound from the relaxation for all the instances with reckless targets was of 24.510 and 29.735 for discount factors 0.7 and 0.99, respectively, whereas for cautious targets those values were 22.767 and 29.374 . The Whittle index policy outperforms other heuristic policies for any number of sensors with the performance improvement increasing as M → N . An interesting result is that the Whittle index policy optimality loss goes to 0 for a relatively small number of sensors when β → 1, while the largest sensor network size is required for the Whittle index policy to be nearly optimal for smaller β (i.e., when hunting targets is urgent). Notice that as the number of sensors grows, all other policies perform worse, since they overuse the network resources thus making targets more elusive and hence, more difficult to hunt. Table I shows the average time that the system takes to hunt all targets operated under each policy. Such results illustrate the fact that a large sensor network which is constantly searching will spend a larger slot of time to hunt targets. However, all policies succeed at finding the N targets at some slot. The Whittle index policy takes significantly less time to hunt targets than the alternative polices for both Reckless and Cautious targets, yet hunting the Cautious targets naturally takes longer for all policies. These results also show the overuse under other heuristics since their average operating time substantially increases as the number of sensors grows.

Experiment #2: Sensing Cost & Sensor Network Size

In this experiment we assess the relative performance of the Whittle index policy against the other heuristics when the sensing cost increases. We consider two base instances of N = 30 sites with M = 1 and N = 5 sensors. In both instances targets parameters are: p

(1) n = 10 -3 , q

(1) n = 0.97, p (0) n = 0.05, q (0) n = 0.003, α n = 0.30, x n = 1, β = 0.99 and r n = 1 for all n. Both base instances were modified, letting sensing costs vary as c ∈ {0, 0.3, 0.5, 0.75}. For each instance, 10 3 independent runs were performed on a horizon of T = 10 4 time slots. Fig 4 shows the ETD net rewards under each policy and the upper bound as c grows. Results show that the Whittle index policy outperforms the other policies in all instances. The resulting performance and its upper bound decrease with c with all policies yielding 0 rewards for c > 0.75. Notice that the Whittle index policy is nearly optimal for all values of the sensing cost when M = 5 while the optimality loss of the other heuristics is larger for M = 5 than for M = 1.

VI. CONCLUDING REMARKS

This paper has introduced a novel dynamic index policy for a relevant sensor network scheduling problem where the goal is to hunt a fixed number of smart targets, in which the theory of restless bandit indexation is applied to a POMDP setting. The resulting policy has been shown in simulation experiments to outperform simpler heuristics.

[1] W. Moran, S. Suvorova, and S. Howard, "Application of sensor scheduling concepts to radar," in Foundations and Applications of Sensor

(

  while in the other instance all targets are cautious with p (0) n = 0.35. In both instances, p (1) n = 10 -3 , q

Fig. 2 :

 2 Fig. 2: Marginal work measure for the three threshold cases.

Fig. 3 :

 3 Fig. 3: Experiment 1: (3a) & (3b) Reckless Targets instances and (3c) & (3d): Cautious Targets instances

5 Fig. 4 :

 54 Fig. 4: Experiment 2: Sensing Cost Effect with: M/N = 1/5 (4a) and M/N = 5/5 (4b)

TABLE I :

 I Average Time to Hunt All Targets

	M / Reckless	T M P	T M y	T B	T R
	1	6.175	9.768	7.083	31.039
	2	5.778	18.994	12.021	42.475
	3	2.405	49.074	45.718	95.318
	4	3.344	36.678	33.071	70.652
	5	3.034	90.074	76.949	102.643
	15	1.928	122.554	155.053	371.901
	30	1.924	373.586	366.239	458.258
	M / Cautious	T M P	T M y	T B	T R
	1	10.770	43.833	37.630	44.864
	2	6.384	29.845	33.414	80.638
	3	4.841	66.301	55.581	87.306
	4	3.828	74.822	76.426	138.993
	5	3.970	135.726	86.134	182.447
	15	3.277	281.945	264.044	410.706
	30	3.073	448.593	465.127	423.586

This work has been supported in part by the Spanish Ministry of Education and Science project MTM2007-63140 and by the Ministry of Science and Innovation project MTM2010-20808.