Sahar Bsaybes

Alain Quilliot

Annegret K Wagler

Fleet management for autonomous vehicles: Online PDP under special constraints

The VIPAFLEET project consists in developing models and algorithms for managing a fleet of Individual Public Autonomous Vehicles (VIPA). Hereby, we consider a fleet of cars distributed at specified stations in an industrial area to supply internal transportation, where the cars can be used in different modes of circulation (tram mode, elevator mode, taxi mode). One goal is to develop and implement suitable algorithms for each mode in order to satisfy all the requests under an economic point of view by minimizing the total tour length. The innovative idea and challenge of the project is to develop and install a dynamic fleet management system that allows the operator to switch between the different modes within the different periods of the day according to the dynamic transportation demands of the users. We model the underlying online transportation system and propose a corresponding fleet management framework, to handle modes, demands and commands. We consider two modes of circulation, tram and elevator mode, propose for each mode appropriate online algorithms and evaluate their performance, both in terms of competitive analysis and practical behavior.

Introduction

The project VIPAFLEET aims at contributing to sustainable mobility through the development of innovative urban mobility solutions by means of fleets of Individual Public Autonomous Vehicles (VIPA) allowing passenger transport in closed sites like industrial areas, medical complexes, campuses, business centers, big parkings, airports and train stations. A VIPA is an "autonomous vehicle" that does not require a driver nor an infrastructure to operate, it is developed by Easymile and Ligier [9,10] thanks to innovative computer vision guidance technologies developed by researchers at Institut Pascal [START_REF] Royer | Outdoor autonomous navigation using monocular vision[END_REF][START_REF] Royer | Retour d'expérience après plus de 1000 km en navette sans conducteur guidée par vision[END_REF]. This innovative project involves different partners in order to ensure the reliability of the transportation system [11]. A long-term experimentation [START_REF] Royer | Retour d'expérience après plus de 1000 km en navette sans conducteur guidée par vision[END_REF] has been performed on the industrial site "Ladoux" of Michelin at Clermont-Ferrand as part of the FUI VIPAFLEET project. A fleet of VIPAs shall be used in an industrial site to transport employees and visitors e.g. between parkings, buildings and from or to the restaurant at lunch breaks. The fleet is distributed at specified stations to supply internal transportation, and a VIPA can operate in three different transportation modes:

-Tram mode: VIPAs continuously run on predefined lines or cycles in a predefined direction and stop at a station if requested to let users enter or leave. -Elevator mode: VIPAs run on predefined lines and react to customer requests by moving to a station to let users enter or leave, thereby changing their driving direction if needed. -Taxi mode: users book their transport requests (from any start to any destination station within the network with a start and an arrival time) in real time.

This leads to a Pickup-and-Delivery Problem (PDP) where a fleet of servers shall transport goods or persons from a certain origin to a certain destination. If persons have to be transported, 1 we usually speak about a Dial-a-Ride Problem (DARP). Many variants are studied including the Dial-a-Ride Problem with time windows [START_REF] Deleplanque | Transfers in the on-demand transportation: the DARPT Diala-Ride Problem with transfers allowed[END_REF][START_REF] Fabri | Online dial-a-ride problem with time windows: an exact algorithm using status vectors[END_REF]. In our case, we are confronted with an online situation, where transportation requests are released over time [START_REF] Ascheuer | Online dial-a-ride problems: Minimizing the completion time[END_REF][START_REF] Berbeglia | Dynamic pickup and delivery problems[END_REF][START_REF] Cordeau | The dial-a-ride problem: models and algorithms[END_REF].

In a practical context, different objective functions can be considered. We focus on the economic aspect where the objective is to minimize costs by minimizing the total tour length.

In a VIPAFLEET system, users can either call a VIPA directly from a station with the help of a call-box or can book their request in real time by mobile or web applications. Since the customer requests are released over time, the classical PDP does not reflect the real situation of this project. Therefore we are interested in its online version. Our aim is to develop and install a Dynamic Fleet Management System that allows the operator to switch between different network designs, transportation modes and appropriate online algorithms within the different periods of the day in order to react to changing demands evolving during the day, with the objective to satisfy all demands in a best possible way. For that we model the underlying online transportation system and propose an according fleet management framework, to handle modes, demands and commands (see Section 2). In Section 3 we develop suitable online algorithms for tram and elevator mode and analyse them in terms of competitive analysis w.r.t minimizing the total tour length. In Section 4, we provide computational results showing that the practical behavior of the algorithms is much better than their worst case behavior captured by their competitive factors. This enables us to cluster the demands into subproblems in such a way that, for each subproblem, a suitable subnetwork and a suitable algorithm can be proposed leading to a globally good solution (transportation schedule).

Problem description and model

We embed the VIPAFLEET management problem in the framework of a metric task system. We encode the closed site where the VIPAFLEET system is running as a metric space M = (V, d) induced by a connected network G = (V, E), where the nodes correspond to stations, arcs to their physical links in the closed site, and the distance d between two nodes v i , v j ∈ V is the length of a shortest path from v i to v j . In V , we have a distinguished origin v o ∈ V , the depot of the system where all k VIPAs are parked when the system is not running, i.e., outside a certain time horizon [0, T ].

A Dynamic Fleet Management System shall allow the operator to switch between different transportation modes within the different periods of the day in order to react to changing customer demands evolving during the day. For that, for a certain period [t, t ] ⊆ [0, T ], we define a metric subspace M = (V , d ) induced by a subnetwork G = (V , E ) of G, where a subset of nodes and arcs of the network is active (i.e. where the VIPAs have the right to perform a move on this arc or pass by this node during [t, t ]). An operator has to decide when and how to move the VIPAs in the subnetworks, and to assign customer requests to VIPAs.

Any customer request r j is defined as a 4-tuple r j = (t j , x j , y j , z j ) where t j ∈ [0, T ] is the release date, -x j ∈ V is the origin node, -y j ∈ V is the destination node, -z j specifies the number of passengers.

The operator monitors the evolution of the requests and the movement of VIPAs over time and creates tasks to move the VIPAs to go to some station and pick up, transport and deliver users. More precisely, a task can be defined as τ j = (t j , x j , y j , z j , G ). This task is sent at time t j to a VIPA operating in the subnetwork G containing stations x j and y j , indicating that z j passengers have to be picked up at x j and delivered at y j . In order to fulfill the tasks, we let a fleet of VIPAs (one or many, each having a capacity for Cap passengers) circulate in the network inducing the metric space.

More precisely we determine a feasible transportation schedule S for (M, T ) consisting of a collection of tours {Γ 1 , . . . , Γ k } where:

each of the k VIPAs has exactly one tour, each request r j is served not earlier than the time t j it is released, each tour starts and ends in the depot.

If each user is transported from its start station to its final destination by only one VIPA, then S is called non-preemptive, otherwise preemptive. In particular, if start and destination station of a user do not lie on the same subnetwork G , the user has to change VIPAs on one or more intermediate stations. As this typically leads to inconveniences, the design of subnetworks has to be done in such a manner that preemption can be mostly avoided.

In addition, depending on the policy of the operator of such a system, different technical side constraints have to be obeyed. If two or many VIPAs circulate on the same (sub)network, the fleet management has to handle e.g. the meeting of two vehicles on a station or an arc, blocking the route of a VIPA by another one waiting at a station (if two VIPAs are not allowed to enter the same node or arc at the same time), and has to take into account the events of breakdown or discharge of a vehicle, technical problems with the server, the data base or the communication network between the stations, VIPAs and the central server.

Our goal is to construct transportation schedules S for the VIPAs respecting all the above constraints w.r.t minimizing the total tour length. This will be addressed by dividing the time horizon [0, T ] in different periods according to the volume and kind of the requests, and by providing specific solutions within each period. The global goal is to provide a feasible transportation schedule over the whole time horizon that satisfies all requests and minimizes the total tour length (Dynamic Fleet Management Problem). For each period, we partition the network G = (V, E) into a set of subnetworks G = (V , E ). The aim of this partition is to solve some technical side constraints for autonomous vehicles, and to solve the online PDP using different algorithms at the same time on different subnetworks. To gain precision in solutions by applying a suitable algorithm to a certain subnetwork, the choice of the design of the network in the industrial site where the VIPAs will operate is dynamic and will change over time according to the technical features and properties.

In a metric space we partition the network into subnetworks G that are either unidirected cycles, called circuits G c , or bidirected paths, called lines G . This partition is motivated by two of the operation modes for VIPAs, tram mode and elevator mode, that we will consider in the sequel of the paper.

Scenarios: combinations of modes and subnetworks

Based on all the above technical features and properties that have an impact on the feasibility of the transportation schedule, we can cluster the requests into subproblems, apply to each subproblem a certain algorithm, and check the results in terms of feasibility and performance.

The choice of the design of the network in the industrial site where the VIPAs will operate is dynamic and will change over time according to the technical features and properties. We consider four typical scenarios that occurred while operating a fleet in an industrial site 1 based on some preliminary studies of the transport requests within the site.

Morning/evening: The transport requests are between parkings and buildings. For this time period we propose the following:

• Design a collection of subnetworks (lines and circuits) s.t.

-all buildings and parkings are covered, -each subnetwork contains one parking p and all the buildings where p is the nearest parking (to ensure that for each request, origin (the parking) and destination (a building) lie in the same subnetwork). • Depending on the number of employees in the served buildings, assign one VIPA (in elevator mode) to every line and one or several VIPAs (in tram mode) to each circuit.

Lunch time:

The transport requests are between buildings and the restaurant of the industrial complex. For this time period, we propose the following:

• Design a collection of lines s.t.

-all buildings are covered, -each line contains the station of the restaurant (to ensure that for each request, to or from the restaurant, origin and destination lie in the same line). • Depending on the number of employees in the served buildings, assign one VIPA (in elevator mode) or one or several VIPAs (in tram mode) to the lines.

Emergency case: In the case of a breakdown of the central servers, the database or the communication system, transports between all possible origin/destination pairs have to be ensured without any decision by the operator. For that we propose to use one Hamilton cycle through all the stations as subnetwork and to let half of the fleet of VIPAs operate in each direction on the cycle (all in tram mode).

Other periods: There are mainly unspecified requests without common origins or common destinations. The operator can use all VIPAs in his fleet in taxi mode on the complete network or design lines and circuits s.t. all stations are covered and the chosen subnetworks intersect (to ensure transports between all possible origin/destination pairs). E.g., this can be done by using one Hamilton cycle through all stations where half of the fleet operates (in tram mode) in each direction, a spanning collection of lines and circuits meeting in a central station where one VIPA (in elevator mode) operates on each line, one or several VIPAs (in tram mode) on each circuit.

Remark 1. One of these combinations of subnetworks has been used in a long duration experimentation [START_REF] Royer | Retour d'expérience après plus de 1000 km en navette sans conducteur guidée par vision[END_REF] on the industrial site "Ladoux" of Michelin at Clermont-Ferrand. VIPAs were operating using the tram mode on a unidirected circuit where some of the buildings and parkings of the industrial site were covered.

Online algorithms and competitive analysis

Recall that the customer requests are released over time s.t. the studied PDP has to be considered in its online version. A detailed introduction to online optimization can be found e.g. in the book by Borodin and El-Yaniv [START_REF] Borodin | Online computation and competitive analysis[END_REF]. It is standard to evaluate the quality of online algorithms with the help of competitive analysis. This can be viewed as a game between an online algorithm ALG and a malicious adversary who tries to generate a worst-case request sequence σ which maximizes the ratio between the online cost ALG(σ) and the optimal offline cost OP T (σ) knowing the entire request sequence σ in advance. ALG is called c-competitive if ALG produces for any request sequence σ a feasible solution with

ALG(σ) ≤ c • OP T (σ)
for some given c ≥ 1. The competitive ratio of ALG is the infimum over all c such that ALG is c-competitive. Here, we are interested in designing and analyzing online algorithms for two possible operating modes of a VIPA, tram mode and elevator mode.

Tram mode

The tram mode is the most restricted operation mode where VIPAs run on predefined circuits in a predefined direction and stop at stations to let users enter or leave. We consider circuits C with one distinguished node, the origin of the circuit2 .

Optimal offline solution via colorings of interval graphs: An interval graph G(I) is obtained as intersection of a set I of intervals within a line segment, where the nodes of G(I) represent the intervals in I, the edges of G(I) represent their conflicts in terms of overlaps (i.e. two nodes are adjacent if the corresponding intervals have a non-empty intersection).

The clique number w(G(I)) corresponds to the largest number of pairwise intersecting intervals in I, a coloring corresponds to an assignment of colors to intervals such that no two intersecting intervals receive the same color. In all graphs, the clique number is a lower bound on the minimum number X (G(I)) of required colors. For interval graphs it was shown in [START_REF] Olariu | An optimal greedy heuristic to color interval graphs[END_REF] that the following Greedy coloring algorithm always produces an w(G(I))-coloring of G(I):

sort all intervals in I according to their left end points.

color the nodes of G(I) in this order: starting with the first node, assign to each node the smallest color that none of its already colored neighbors has.

We next interpret the offline solution for VIPAs operating in tram mode on a circuit in this context. We have given a circuit C = {v o , v 1 , . . . , v n } and a sequence σ of m requests r j = (t j , x j , y j , z j ) with origin/destination pairs (x j , y j ) ∈ C × C. W.l.o.g. we may assume that the origin v 0 of the circuit does not lie in the interior of (x j , y j ) for any r j ∈ σ. We transform C into a path P = {v 0 , v 1 , . . . , v n , v 0 } having the origin v 0 of C as start and end node (as the line segment), and we split each request r j into z j many uniform requests (resp. single passengers), interpreted as subpaths (x j , y j ) ⊆ P (to obtain the (multi) set I of intervals). By construction, we have for the resulting interval graph G σ = G(I):

the clique number w(G(I)) corresponds to the maximum number of requests r j in σ (counted with their multiplicities z j ) traversing a same edge of P , a coloring of G σ corresponds to an assignment of places in the VIPA(s) to passengers.

Clearly one VIPA can serve all (uniform) requests from up-to Cap color classes in a single subtour traversing C. We can, thus, turn any coloring of G σ into a feasible transportation schedule by waiting until time t m in the origin v 0 ( to ensure that all requests are released before they are served) selecting up to Cap many color classes and assigning the corresponding uniform requests (i.e. single passengers) to one VIPA, to be served within the same subtour traversing C, until all requests are served.

This leads to the following algorithm to compute optimal offline solutions for the tram mode: OPT-TRAM Input: σ = {r 1 , r 2 , . . . , r m }, C = {v o , v 1 , . . . , v n }, Cap and k Output: transportation schedule 1. for each r j = (t j , x j , y j , z j ) ∈ σ: create z j many intervals (x j , y j ) to obtain I, 2. sort all intervals in I according to their left end points, 3. create the interval graph G(I) and apply the Greedy algorithm to color it, 4. wait until t m (the release date of the last request), 5. as long as there are unserved requests: select Cap many (or all remaining) color classes, assign the corresponding passengers to a VIPA and perform one subtour traversing C to serve them.

Example 1. Consider a circuit C = (a, b, c, d, e) with origin a and one unit-speed server with capacity Cap = 2 (i.e. a VIPA that travels 1 unit of length in 1 unit of time), and a sequence σ of 6 requests:

r 1 = (1, c, e, 2) r 4 = (4, b, c, 2) r 2 = (2, a, d, 1) r 5 = (5, a, b, 1) r 3 = (3, d, e, 1) r 6 = (6, b, e, 1)
1. for each r j ∈ σ we create z j many intervals (x j , y j ) to obtain I: 2. We sort all intervals in I according to their left end points: I 5 , I 2 , I 41 , I 42 , I 6 , I 11 , I 12 , I 3 .

3. We create the interval graph G(I):

I5 I2 I41 I42 I6 I11 I12 I3
4. We apply the Greedy algorithm to color it: Cap many such subtours are needed to serve all requests. The transportation schedule obtained is feasible because, by waiting until t m to start any subtour, we ensure that all requests have been released before. As the Greedy coloring algorithm provides an optimal w(G(I))coloring of G(I), we can guarantee to obtain a feasible transportation schedule performing the minimal number of subtours by always choosing Cap colors (except for the last subtour where we choose all remaining ones) so that the minimal total tour length equals

OP T (σ) = w(G(I)) Cap • |C|.
The resulting solution is a load-preemptive transportation schedule because it cannot be ensured that all z j passengers coming from the same request r j are served by the same VIPA (even if z j ≤ Cap holds).

Remark 2.

• The minimal total tour length does not depend on the number of VIPAs used to serve all requests. • Algorithm OPT-TRAM is clearly polynomial because all the steps of the algorithm can be computed in polynomial time.

• By not selecting Cap color classes randomly to create subtours, it is possible to:

-reduce load-preemption, -minimize the number of stops performed to let passengers leave/enter a VIPA, -handle the case of more than one VIPA, but the so modified algorithm is not necessarily polynomial anymore.

Online algorithms: For the online situation, we propose the following simple algorithm for VIPAs operating in tram mode on a circuit C:

SIR ("Stop If Requested")
each VIPA waits in the origin of C; as soon as a request is released, a VIPA starts a full subtour in a given direction, thereby it stops at a station when a user requests to enter/leave.

In fact, in tram mode, the possible decisions of the VIPA are either to continue its tour or to wait at its current position for newly released requests. This can be used by the adversary to "cheat" an online algorithm, in order to maximize the ratio between the online and the optimal costs. Here, the strategy of the adversary is to force SIR to serve only one uniform request per subtour, whereas the adversary only needs a single subtour traversing C to serve all requests.

Example 2. Consider a circuit C = (v 0 , v 1 , . . . , v n ) with origin v 0 , a unit distance between v i and v i+1 for each i, and one unit-speed server with capacity Cap. The adversary releases a sequence σ of Cap • n uniform requests that force SIR to perform one full round (subtour) of length |C| = n + 1 for each uniform request, whereas the adversary is able to serve all requests in a single subtour (fully loaded on each edge): The adversary waits at the origin v 1 until t = (Cap-1)|C| and serves all requests r 1 , . . . , r Cap from v 0 to v 1 . Then he waits until t = (2Cap-1)|C| at v 1 and serves all requests r Cap+1 , . . . , r 2Cap from v 1 to v 2 . This is repeated for all Cap requests from v i to v i+1 , yielding OP T (σ) = |C|. The tours performed by SIR and OPT are illustrated in Fig 1 . Therefore, we obtain

-Cap requests r j = ((j -1)|C|, v 0 , v 1 , 1) for 1 ≤ j ≤ Cap -Cap requests r j = ((j -1)|C|, v 1 , v 2 , 1) for Cap + 1 ≤ j ≤ 2Cap . . . -Cap requests r j = ((j -1)|C|, v n-1 , v n , 1) for (n -1)Cap + 1 ≤ j ≤ nCap -Cap requests r j = ((j -1)|C|, v n , v 0 , 1) for nCap + 1 ≤ j ≤ (n + 1)Cap SIR starts its VIPA at time t = 0 to serve r 1 = (0, v 0 , v 1 ,
SIR(σ) OP T (σ) = Cap • |C| • |C| |C| = Cap • |C|
as a lower bound for the competitive ratio of SIR. In the special case of the lunch scenario, we may consider VIPAs operating in tram mode on circuits, where each circuit has the restaurant as its distinguished origin. A sequence σ containing the first Cap and the last Cap requests from the sequence presented in Example 2 shows that 2Cap is a lower bound on the competitive ratio of SIR, see Figure 2 for an illustration.

t, d O C 2C 3C 4C 5C 6C 7C 8C 9C 10C 11C 12C C
As for the morning resp. evening scenario, we consider VIPAs operating in tram mode on a circuit C where the parking is the distinguished origin of C. A sequence σ containing the first Cap resp. last Cap requests from the sequence presented in Example 2 shows that Cap is a lower bound on the competitive ratio of SIR, see Figure 3 and Figure 4, respectively. SIR can indeed be forced to show this behavior by releasing the requests accordingly (i.e. by using uniform requests with z j = 1 each and with sufficiently large delay between t j and t j+1 ), in general: using the sequence σ from Example 2, during lunch: using the sequence σ restricted to the first Cap and the last Cap requests (t j , v 0 , v 1 , 1) and (t j , v n , v 0 , 1) from the sequence σ presented in Example 2 as in Figure 2, during morning/evening: using the sequence σ restricted to the first Cap requests (t j , v 0 , v 1 , 1) (resp. the last Cap requests (t j , v n , v 0 , 1)) from the sequence σ presented in Example 2, as Figure 3 (resp. Figure 4) shows.

Furthermore, to maximize the ratio between this total tour length obtained by SIR and the optimal offline solution, we need to ensure that all requests in σ can be served with as few subtours of length |C| as possible. This is clearly the case if all requests have length 1 and there are Cap many requests traversing the same edge of C s.t. a single subtour suffices to serve all of them (see again Example 2). This leads to

-|G σ | = |σ| = Cap • |C| and w(G(I)) = Cap s.t. SIR(σ) OP T (σ) = Cap • |C| • |C| 1 • |C| = Cap • |C|
is the maximum possible ratio between SIR(σ) and OP T (σ) taken over all possible sequences in general.

-|G σ | = |σ | = 2Cap and w(G(I)) = Cap s.t. SIR(σ ) OP T (σ ) = 2 • Cap • |C| 1 • |C| = 2 • Cap
is the maximum possible ratio between SIR(σ) and OP T (σ) taken over all possible sequences during the lunch.

-|G σ | = |σ | = Cap and w(G(I)) = Cap s.t. SIR(σ ) OP T (σ ) = Cap • |C| 1 • |C| = Cap
is the maximum possible ratio between SIR(σ) and OP T (σ) taken over all possible sequences during the morning or evening.

Moreover, SIR can be adapted to follow the strategy of the adversary. For that, we propose two other algorithms for VIPAs operating in tram mode in the morning resp. evening: SIF M ("Start if fully loaded") for the morning scenario each VIPA waits in the parking until Cap passengers have entered, it starts a full round (as soon as it is fully loaded) and stops at stations where passengers request to leave.

SIF E ("Start if fully loaded") for the evening scenario each VIPA waits in the parking until enough requests are released to reach Cap, it starts a full round and stops at stations where passengers request to enter and returns (fully loaded) to the parking.

We can ensure optimality for these two strategies: In order to maximize the ratio, OPT needs to serve as many requests as possible using the least total tour length possible. OPT always combines Cap requests from Q 1 with Cap requests from Q 2 and serves them together by performing a subtour of length |C|. In addition, to avoid not fully loaded moves for OPT, the adversary choses |Q 1 | = |Q 2 | and as a multiple of Cap which leads to OP T

Theorem 3. SIF M (resp. SIF E ) is 1-competitive w.
(σ) = |Gσ| 2Cap • |C|, therefore SIF L (σ) OP T (σ) = |Gσ| Cap • |C| |Gσ| 2Cap • |C| = 2
is the maximum possible ratio between SIF L (σ) and OP T (σ) taken over all possible sequences on a circuit of length |C| during the lunch.

Elevator mode

The elevator mode is a less restricted operation mode where one VIPA runs on a predefined line and can change its direction at any station of this line to move towards a requested station. One end of this line is distinguished as origin O (say, the "left" end).

Optimal offline solution: In order to obtain the optimal offline solution OP T (σ) w.r.t. minimizing the total tour length, we compute a min cost flow in a suitable network. Given a line L = (v 0 , . . . , v n ) with origin v 0 as a subnetwork, capacity Cap of a VIPA, and a request sequence σ with requests r j = (t j , x j , y j , z j ).

In the sequel, we distinguish in which direction an edge v i v i+1 of L is traversed and speak of the up arc (v i , v i+1 ) and the down arc (v i+1 , v i ). In order to construct the network, we proceed as follows:

• Neglect the release dates t j and only consider the loads of the requests z j , their origins x j and their destinations y j . • Partition the requests into two subsets:

-U of "up-requests" r j ∈ σ with x j < y j , -D of "down-requests" r j ∈ σ with x j > y j . • Determine the loads of all up arcs (v i , v i+1 )) or down arcs (v i+1 , v i ) of the line L as a weighted sum of the load of all request-paths (x j , y j ) containing this arc:

-

load(v i , v i+1 ) = (vi,vi+1)∈(xj ,yj ),xj <yj z j ∀i ∈ {0, n -1}, ∀r j ∈ U -load(v i+1 , v i ) = (vi+1,vi)∈(xj ,yj ),xj >yj z j ∀i ∈ {0
, n -1}, ∀r j ∈ D • Determine the "multiplicities" m of all up/down arcs: in order to serve all the requests in σ, each arc (v i , v i+1 ) must be visited m (i,i+1) = load(vi,vi+1) Cap times and each arc (v i+1 , v i ) must be visited m (i+1,i) = load(vi+1,vi))

Cap times. In case the multiplicity m (i,i+1) resp. m (i+1,i) is equal to zero, then the corresponding up resp. down arc is removed. Now we build a network G E = (V E , A E ), where

• the node set V E = V up(o) ∪ V up(d) ∪ V down(o) ∪ V down(d) contains
-the origin nodes of all up arcs where the multiplicity is different from zero in V up(o) , -the destination nodes of all up arcs where the multiplicity is different from zero in V up(d) , -the origin nodes of all down arcs where the multiplicity is different from zero in V down(o) , -the destination nodes of all down arcs where the multiplicity is different from zero in V down(d) , -the origin v 0 of the line L as source s and as sink t.

• The arc set A

E = A s ∪ A U ∪ A D ∪ A L ∪ A t is composed of:
-source arcs from the source s to all v o) , and from all v

up(o) i ∈ V up(o) and all v down(o) i ∈ V down(o) in A s , -up arcs (v up(o) i , v up(d) i+1 ) whenever m (i,i+1) = 0 in A U , -down arcs (v down(o) i+1 , v down(d) i ) whenever m (i+1,i) = 0 in A D , -link arcs in A L going from all v up(d) i ∈ V up(d) to all v down(o) i ∈ V down(
down(d) i ∈ V down(d) to all v up(o) i ∈ V up(o) , -sink arcs from all v up(d) i ∈ V up(d) and from all v down(d) i ∈ V down(d) to the sink t in A t .
Accordingly, the objective function considers costs d(a) = d(u, v) for the flow f on all arcs a = (u, v) in A E , where d(u, v) is the length of a shortest path from u to v in the line L. To correctly initialize the system, we use the source node s as source for the flow and the sink node t as its destination. For all internal nodes, we use normal flow conservation constraints. We require a flow on all up/down arcs f (a) = m(a) for all a ∈ {A U ∪ A D }, see constraint (1e). We finally add the constraint (1d) to eliminate all possible isolated cycles that the flow may contain (since the network contains directed cycles).

This leads to a Min-Cost Flow Problem, whose output is a subset of arcs needed to form a transportation schedule for a metric task system, whose tasks are induced by the requests. The corresponding integer linear program is as follows:

min a∈A E d(a)f (a) (1a) s.t. a∈δ -(s) f (a) = 1 (1b) a∈δ -(v) f (a) = a∈δ + (v) f (a) ∀v = {s, t} (1c)
a∈δ(W ) f (a) ≥ 2 ∀W ⊂ V E \ {s, t}, 2 ≤ |W | ≤ |V E | -3 (1d) f (a) = m(a) ∀a ∈ {A U ∪ A D } (1e) f (a) ∈ Z + (1f)
where δ -(v, t) denotes the set of outgoing arcs of v, δ + (v) denotes the set of incoming arcs of v and δ(W ) denotes the set of incoming or outgoing arcs (u, v) of W s.t. u ∈ W and v / ∈ W or u / ∈ W and v ∈ W . The time required to compute the integer linear program grows in proportion to 2 |V | due to the constraint (1d) that eliminates all possible isolated cycles, and, hence, it may grow exponentially. However, this integer linear program can be computed in reasonable time provided that the number V of nodes in the original network (the line) is small. Remark 3. The family of constraints (1d) can be generated and then each inequality is separated to verify if it is violated or not. However, due to their exponential number, the process of separation in order to verify if a solution satisfies all constraints is exponential. Since the number of subtour elimination constraints is exponential, we may firstly compute the integer linear program without the constraints (1d). Then we check if there is an isolated cycle in the solution obtained, if yes, we add only the constraint (1d) using the nodes of this isolated cycle. This procedure is repeated until a solution without isolated cycles is found.

Finally, the flow in the time-expanded network is interpreted as a transportation schedule. The tracks of the VIPA over time can be recovered from the flow f (a) on the arcs by standard flow decomposition, see [START_REF] Ravindra K Ahuja | Network flows: theory, algorithms, and applications[END_REF]. Hereby, a flow f (a) on an arc a = (u, v) corresponds to a move of a VIPA on this arc. Based on the flow values, one can construct a unique path from source s to sink t traversing all arcs a with positive flow exactly f (a) times. This shows that the optimal solution of system (1) corresponds to a transportation schedule with minimal total tour length for the offline problem behind the elevator mode.

Example 3. Consider a line L = (v 0 , . . . , v n ) with origin v 0 , a unit distance between v i and v i+1 for each i, with a set σ of 9 requests shown in Figure 5, and a VIPA with capacity Cap = 2. The resulting network G E = (V E , A E ) of the line presented in this example is illustrated in Figure 6. The optimal offline solution, the transportation schedule of the VIPA with a minimal total tour length, is obtained by computing the presented integer linear program for a min-cost flow problem in the constructed network

G E = (V E , A E ). v 0 v 1 v 2 v 3 v 4 r 1 = (t 1 , v 0 , v 4 , 1) r 2 = (t 2 , v 4 , v 3 , 1) r 3 = (t 3 , v 3 , v 4 , 2) r 4 = (t 4 , v 4 , v 3 , 1) r 5 = (t 5 , v 3 , v 4 , 1) r 6 = (t 6 , v 4 , v 3 , 2) r 7 = (t 7 , v 4 , v 2 , 1) r 8 = (t 8 , v 0 , v 1 , 2) r 9 = (t 9 , v 1 , v 0 , v 1 ) load(uparcs) 3 1 1 4 load(downarcs) 1 0 1 5 m(uparcs) = load Cap 2 1 1 2 m(downarcs) = load Cap 1 0 1 3
Fig. 5. This figure illustrates the line L = (v0, . . . , vn) with origin v0, and a set σ of 9 requests and a VIPA with capacity Cap = 2. The requests are partitioned into two subsets "up-requests" (arcs in black) and "down-requests" (arcs in red). Each arc represents a load of 1, for example r3 is represented by 2 arcs going from v3 to v4. The loads of all up arcs (all arcs (vi, vi+1)) or down arcs (all arcs (vi+1, vi)) of the line L are shown in the first and second row of the table. Then the third and the forth rows contain the "multiplicities" m of all up/down arcs.

Online algorithm: An algorithm MRIN ("Move Right If Necessary") has been proposed for the Online-Traveling Salesman Problem (where no transports have to be performed, but only points to be visited) on a line and analyzed w.r.t. minimizing the makespan [START_REF] Blom | The online TSP against fair adversaries[END_REF], giving a competitive ratio of 3/2. We generalize MRIN to the Pickup and Delivery Problem and analyze it w.r.t. minimizing the total tour length. In elevator mode, the server (VIPA) has the choice to continue its tour in the current direction, to wait at its current position or to change its driving direction. Accordingly, we propose the algorithm MAIN. The adversary can again "cheat" the strategy of MAIN as the following example shows.

Example 4. Consider a line L = (v 0 , . . . , v n ) with origin v 0 , a unit distance between v i and v i+1 for each i, and one unit-speed server with capacity Cap. The adversary releases a sequence σ of uniform requests that force MAIN to leave the origin of the line and perform a subtour of a certain distance for each request, whereas the adversary is able to serve all requests in a single subtour of length 2|L|:

The third block σ 3 of n • Cap requests:

r j = (t j-1 + 2d(v 0 , v n ), v n , v n-1 , 1) for (n + 2 + 1)Cap + 1 ≤ j ≤ (n + 2 + 2)Cap r j = (t j-1 + 2d(v 0 , v n ), v n-1 , v n-2 , 1) for j = (n + 2 + 2)Cap + 1 r j = (t j-1 + 2d(v 0 , v n ), v n , v n-1 , 1) for (n + 2 + 2)Cap + 2 ≤ j ≤ (n + 2 + 3)Cap r j = (t j-1 + 2d(v 0 , v 2 ), v 1 , v 0 , 1) for j = (2n + 2 -1)Cap + 1 r j = (t j-1 + 2d(v 0 , v 1 ), v 1 , v 0 , 1) for (2n + 2 -1)Cap + 2 ≤ j ≤ (2n + 2 )Cap
MAIN starts its VIPA at time t = 0 to serve r 1 = (0, v 0 , v 1 , 1) and finishes the first subtour of length 2d(v 0 , v 1 ) = 2 without serving any further request. When the VIPA operated by MAIN is back to the origin v 0 , the second request r 2 = (2, v 0 , v 1 , 1) is released and MAIN starts at t = 2 a second subtour of length 2 to serve r 2 , without serving any further request in this subtour. This is repeated for each request until serving the first block of n • Cap requests yielding

M AIN (σ 1 ) = 2 • Cap 1≤i≤n i = Cap • |L| • (|L| + 1)
Then at t = t nCap+1 MAIN starts to serve r nCap+1 from v n to v n-1 and performs a subtour of length 2d(v 0 , v n ) = 2|L|. When the VIPA operated by MAIN is back to the origin v 0 , the request r nCap+2 is released and MAIN performs a new subtour of length 2|L| to serve it. This is repeated for each request until serving the second block of • 2Cap requests yielding

M AIN (σ 2 ) = 2 • 2Cap|L|.
Finally in order to serve the third block MAIN has the same behavior as to serve the first block of requests yielding

M AIN (σ 3 ) = 2 • Cap 1≤i≤n i = Cap • |L| • (|L| + 1). Therefore M AIN (σ) = Cap • |L| • (|L| + 1) + 2 • 2Cap|L| = (|L| + 1 + 2 ) • 2|L| • Cap.
The adversary waits at the origin v 0 until t = t Cap and serves all requests r 1 , . . . , r Cap from v 0 to v 1 . Then he waits until t = t 2Cap at v 1 and serves all requests r Cap+1 , . . . , r 2Cap from v 1 to v 2 . This is repeated for all Cap requests from v i to v i+1 until the adversary arrives to v n . OPT served the first block of n • Cap requests with a total tour length equal to |L|. Then the adversary begins to oscillate his VIPA between v n and v n-1 and serves each time Cap requests, this is repeated 2 times leading to a total tour length for σ 2 equal to 2 . Finally the adversary follows the other direction and waits each time until Cap requests are released to serve them, for all Cap requests from v i to v i-1 until reaching v 0 , yielding OP T (σ) = 2|L| + 2 . Therefore, we obtain

M AIN (σ) OP T (σ) = 2 • Cap • |L| • (|L| + 1) + ( • 2 • Cap • 2|L|) 2(|L| + ) = 2 • Cap • |L| • (|L| + 1 + 2 ) 2(|L| + ) = Cap • |L| + (1 + ) |L| + Cap • |L| -→ →+∞ 2Cap • |L|
as a lower bound for the competitive ratio of MAIN. We can determine an upper bound for the competitive ratio of MAIN close to the ratio obtained by the previous example: Proof. The worst transportation schedule results if all requests are uniform and the VIPA operated by MAIN performs a separate subtour serving a single request r j = (t j , x j , y j , 1) each time the VIPA leaves the origin v 0 of the line, yielding rj ∈σ 2 max(d(v 0 , x j ), d(v 0 , y j )) as total tour length. To maximize the ratio between the total tour length obtained by MAIN and the optimal offline solution, we need to ensure that we do not have a move with a load less than the capacity Cap of the VIPA in the transportation schedule of OP T ; all requests in σ can be served with as few and as short subtours as possible in OPT.

v 0 v 1 v 2 v 3 v 4 v
The worst ratio of subtours can be obtained when -OPT oscillates fully loaded between two neighbored nodes of L, -MAIN is forced to traverse the whole line twice per passenger, i.e. oscillates between v 0 and v n .

For that, v n needs to be either origin or destination of each request, and the delay between the release dates needs to be sufficiently large. This can be achieved with subsequence σ 2 from Example 4, with blocks each consisting of -Cap consecutive uniform requests from v n to v n-1 , alternated by -Cap consecutive uniform requests from v n-1 to v n , always with a delay 2|L| between the release dates of any two requests r j and r j+1 . We obtain

OP T (σ 2 ) = 2 and M AIN (σ 2 ) = • 2 • Cap • 2 • |L| which leads to the studied subtour ratio of M AIN (σ 2 ) OP T (σ 2 ) = • 2 • Cap • 2 • |L| 2 = 2 • Cap • |L|.
However, this ratio so far neglects the initial and final server position v 0 for the VIPA operated by OPT. The requirement of starting and ending the tour in v 0 leads to a total tour length for OPT of

OP T (σ) = |L| • 2 • |L|.
In order to maximize the ratio of the complete tours, the adversary releases more requests to ensure that the VIPA operated by -OPT can arrive at v n (resp. return from v n to v 0 ) fully loaded on each arc, -MAIN is forced to oscillate between v 0 and the destination y j (resp. the origin x j ) of each uniform request r j .

This can be achieved with the subsequences σ 1 and σ 3 from Example 4 with -Cap consecutive uniform requests from v i to v i+1 for each 0 ≤ i < n and -Cap consecutive uniform requests from v i to v i-1 for each n ≥ i ≥ 1, always with delay 2 • d(v 0 , y j ) resp. 2 • d(x j , v 0 ) between the release dates of any two requests r j and r j+1 within these subsequences. We obtain (as in Example 4) that

M AIN (σ 1 ) = M AIN (σ 3 ) = 2 • Cap 1≤i≤n i = Cap • |L| • (|L| + 1).
This finally leads to

M AIN (σ) OP T (σ) = 2 • Cap • |L| • (|L| + 1) + ( • 2 • Cap • 2|L|) 2(|L| + ) = 2 • Cap • |L| • (|L| + 1 + 2 ) 2(|L| + ) = Cap • |L| + (1 + ) |L| + Cap • |L| -→ →+∞ 2Cap • |L|
as the maximum possible ratio between M AIN (σ) and OP T (σ) taken over all possible sequences on a line L.

Concerning the lunch scenario, we may consider VIPAs operating in elevator mode on lines, where each line has the restaurant as its distinguished origin. A sequence σ containing the first Cap requests of the first block σ 1 and the last Cap requests from the third block σ 3 from the sequence presented in Example 4 shows that 2 • Cap is a lower bound on the competitive ratio of MAIN. As for the morning resp. evening scenario, we may consider VIPAs operating in elevator mode on lines, where each line has a parking as its distinguished origin. A sequence σ containing the first Cap requests of the first block σ 1 resp. the last Cap requests from the third block σ 3 from the sequence presented in Example 4 shows that Cap is a lower bound on the competitive ratio of MAIN. We can show that these examples are the worst cases for MAIN during lunch, morning and evening: Theorem 6. For one VIPA with capacity Cap operating in elevator mode on a line, MAIN is w.r.t. the objective of minimizing the total tour length -2 • Cap-competitive during the lunch scenario, -Cap-competitive during the morning resp. the evening scenario.

Proof. The worst transportation schedule results if the VIPA operated by MAIN performs a separate subtour serving a single uniform request r j = (t j , v 0 , v 1 , 1) or r j = (t j , v 1 , v 0 , 1) each time the VIPA leaves the origin v 0 of the line, yielding rj ∈σ 2d(v 0 , v 1 ) as total tour length. MAIN can indeed be forced to show this behavior by releasing the requests accordingly (i.e. by using requests with z j = 1 each and with sufficiently large delay between t j and t j+1 ). In order to maximize the ratio between the total tour length obtained by MAIN and the optimal offline solution, we need to ensure that • we do not have a move from or to the origin with a load less than the capacity Cap of the VIPA in the transportation schedule of OP T . For that, the adversary releases -during the lunch Cap many requests traversing the same arc. Whereas MAIN traverses d(v 0 , v 1 ) twice to serve a request r j = (t j , v 0 , v 1 , 1) or r j = (t j , v 1 , v 0 , 1), OPT travels d(v 0 , v 1 ) once to serve the request and can share it with Cap -1 others.

-during the morning/evening Cap many requests traversing the same arc. Whereas MAIN traverses d(v 0 , v 1 ) twice to serve a request r j = (t j , v 0 , v 1 , z j ) resp. r j = (t j , v 1 , v 0 , z i ), OPT travels the same distance to serve the request but can share it with Cap -1 others. • all requests in σ can be served with as few and as short subtours as possible in OPT. For that, the adversary releases -during the lunch a sequence σ of 2Cap requests: Cap many requests v 0 → v 1 followed by Cap many requests v 1 → v 0 . Therefore we obtain

M AIN (σ) = rj ∈σ 2d(v 0 , v 1 ) = 2 • Cap • 2d(v 0 , v 1 ) and OP T (σ) = 2d(v 0 , v 1 ) s.t. M AIN (σ) OP T (σ) = 2 • Cap • 2d(v 0 , v 1 ) 2d(v 0 , v 1 ) = 2Cap
is the maximum possible ratio between M AIN (σ) and OP T (σ) taken over all possible sequences on a line during the lunch.

-during the morning/evening a sequence σ of Cap requests: Cap many requests v 0 → v 1 resp. Cap many requests v 1 → v 0 . Therefore we obtain

M AIN (σ) = rj ∈σ 2d(v 0 , v 1 ) = Cap • 2d(v 0 , v 1 ) and OP T (σ) = 2d(v 0 , v 1 ) s.t. M AIN (σ) OP T (σ) = Cap • 2d(v 0 , v 1 ) 2d(v 0 , v 1 ) = Cap
is the maximum possible ratio between M AIN (σ) and OP T (σ) taken over all possible sequences on a line during the morning resp. evening.

Computational results

This section deals with computational experiments for the proposed online algorithms. In fact, due to the very special request structures of the previously presented worst case instances, we can expect a better behavior of the proposed online algorithms in average. The computational results presented in Table 1 and 2 support this expectation, they compare the total tour length T T L computed by the online algorithms with the optimal offline solution. The computations use instances based on the network from the industrial site of Michelin and randomly generated request sequences resembling typical instances that occurred during the experimentation [START_REF] Royer | Retour d'expérience après plus de 1000 km en navette sans conducteur guidée par vision[END_REF].The computations are performed with the help of a simulation tool developed by Yan Zhao [START_REF] Zhao | Simulator for vipafleet management[END_REF]. The instances use subnetworks as a circuit or a line depending on the mode and the algorithm with 1 to 5 VIPAs, 5-200 requests, 1-12 as the maximum load z j of a request. For every parameter set we created 6 test instances. In these tables, the instances are grouped by the number of requests and the capacity of the VIPA. The average results of the instances are shown. The operating system for all tests is Linux (CentOS with kernel version 2.6.32). The algorithms SIR, SIF L , MAIN and OPT-TRAM have been implemented in Java. For solving the integer linear program to get the optimal solution for the elevator mode, we use Gurobi 8.21.

Table 1. This table shows the computational results for several test instances of the algorithms SIR and SIFL in comparison to the value of the optimal solution. In this table, the instances are grouped by the number of requests (1st column) and the capacity (2nd column). Furthermore the values of the total tour length T T L found by SIR with morning, evening and lunch instances are shown in comparison with the optimal solution OP T and the ratio between them. Then the values of the total tour length T T L found by SIFL with lunch instances are shown in comparison with the optimal solution OP T and the ratio between them. Finally, the results for instances respecting the general scenario are shown: the total tour length T T L found by SIR, the optimal solution OP T and the ratio between them. The competitive ratio c is shown for each of the scenarios, it is always greater than T T L OP T unless c = T T L OP T = 1. In these test instances the length of the circuit used is equal to |C| = 25

Concluding Remarks

Vehicle routing problems integrating constraints on autonomy are new in the field of operational research but are important for the future mobility. Autonomous vehicles, which are intended to be used as a fleet in order to provide a transport service, need to be effective also considering to their management. We summarize the results of competitive analysis presented in this paper in Table 3. Competitive analysis has been one of the main tools for deriving worst-case bounds on Table 2. This table shows the computational results for several test instances of the algorithm M AIN in comparison to the value of the optimal solution. In this table, the instances are grouped by number of requests (1st column) and the capacity (2nd column). First the values of the total tour length T T L found by M AIN for the instances respecting the morning scenario are shown, the optimal solution OP T and the ratio between them. Then the results for instances respecting the evening scenario are shown: the total tour length T T L found by M AIN and, the optimal solution OP T and the ratio between them. Finally, the values of the total tour length T T L found by MAIN with general instances are shown in comparison with the optimal solution OP T and the ratio between them. The competitive ratio c is shown for each of the scenarios, it is always greater than T T L OP T unless c = T T L OP T = 1. In these test instances the length of the line used is equal to |L| = 32 Table 3. This table shows the competitive ratios obtained in this paper. For each case we show the competitive ratio for the algorithm on which type of graphs, using which mode.

I

  11 = (c, e) I 12 = (c, e) I 2 = (a, d) I 3 = (d, e) I 41 = (b, c) I 42 = (b, c) I 5 = (a, b) I 6 = (b, e)

5 . 6 ) 1 .

 561 As long as there are unserved requests, we select 2 random color classes, assign the corresponding passengers to a VIPA and perform one subtour traversing C to serve them, for instance:first VIPA, first round: color 1 and 2 (r 5 , r 2 , r 41 , r 11 , r 3 ) second VIPA, or second round of first VIPA: color 3 and 4 (r 42 , r 12 , rTheorem Algorithm OPT-TRAM provides a load-preemptive optimal offline solution w.r.t. minimizing the total tour length for VIPAs operating in tram mode on a circuit.Proof. By construction, splitting the requests r j from σ according to their multiplicities z j gives a (multi)set I of intervals where each of them stands for a uniform request of a single passenger. Accordingly, the clique number w(G(I)) of the resulting interval graph G(I) corresponds to the maximum number of passengers traversing a same edge e of the circuit C, that isw(G(I)) = max{ e∈(xj ,yj ),rj ∈σ z j ; e ∈ C}On the other hand, a coloring of G(I) corresponds to an assignment of places in the VIPA(s) to passengers, and subtours for the VIPA(s) can be easily created by repeatedly choosing Cap color classes and assigning the passengers colored that way to the Cap places of one VIPA. Clearly, at least w(G(I))

Fig. 1 .

 1 Fig. 1. This figure illustrates the tour performed by SIR (in blue) and the adversary (dotted in green) in order to serve the requests (dashed arcs in red) from Example 2 for Cap = 3, n = 3 and |C| = 4.

Fig. 2 .Fig. 3 .Theorem 2 .

 232 Fig. 2. This figure illustrates the tour performed by SIR (in blue) and the adversary (dotted in green) in order to serve the first Cap and the last Cap requests (dashed arcs in red) from the sequence presented in Example 2 for Cap = 3, n = 3 and |C| = 4. These requests satisfy the criterias of the lunch scenario.

Fig. 4 .

 4 Fig. 4. This figure illustrates the tour performed by SIR (in blue) and the adversary (dotted in green) in order to serve the last Cap requests (dashed arcs in red) from the sequence presented in Example 2 for Cap = 3, n = 3 and |C| = 4. These requests satisfy the criterias of the evening scenario.

Fig. 7 .

 7 Fig. 7. This figure illustrates the set σ = σ1 ∪ σ2 ∪ σ3 of requests (arcs under the line L = (v0, . . . , v5) with origin v0) from Example 4 for Cap = 3, n = 5 and = 1.

Theorem 5 .

 5 MAIN is 2Cap • |L|-competitive w.r.t minimizing the total tour length for one VIPA operating in elevator mode on a line L with length |L|.

  Cap c = Cap c = 2Cap c = 2 c = Cap • |C| m Cap T T L OP T T T L OP T T T L OP T T T L OP T T T L OP T T T L OP T c T T L T T

  Cap c = Cap c = 2Cap c = 2Cap • |L| m Cap T T L OP T T T L OP T T T L OP T T T L OP T T T L OP T T T L OP T c T T L OP T

  r.t minimizing the total tour length for one or several VIPAs operating in tram mode on a circuit during the morning (resp. evening).

Proof. Both variants of SIF are optimal, because due to the special request structure during the morning resp. evening, all requests traverse the first (resp. last) edge of P in the morning (resp. evening) s.t. G σ becomes a clique. In other words, no two passengers can share a same place in a VIPA s.t. starting fully loaded from the origin (resp. returning fully loaded to the origin) indeed provides the optimal solution w.r.t. minimizing the total tour length.

The two previous algorithms SIF E and SIF M can be merged together to obtain a version for the lunch scenario: SIF L ("Start if fully loaded on at least one arc")

each VIPA waits in the restaurant until enough requests are released s.t. by serving these requests using one VIPA, the VIPA is fully loaded at least on one arc in the circuit. it starts a full round and stops at stations where passengers request to enter or leave and returns to the restaurant. Theorem 4. SIF L is 2-competitive w.r.t minimizing the total tour length for one or several VIPAs operating in tram mode on a circuit during the lunch. Proof. Due to the special request structure during the lunch, all requests start and end in the restaurant and, thus, traverse the first and the last edge of P s.t. G σ consists of two cliques Q 1 and Q 2 resulting from all uniform requests traversing the first and the last edge, respectively. The worst transportation schedule of SIF L results if the requests are released in a way that SIF L never serves a request from Q 1 with one from Q 2 together, therefore by each subtour of length |C| performed by SIF L Cap requests are served either from the clique Q 1 or from Q 2 , yielding SIF L (σ) = |Gσ| Cap • |C| as total tour length.

  ,5 3393,5 0,96 3304,5 3426,5 0,96 2240 1855,5 1,21 2 1713 1435,5 1,19 64 200 5 1049 693,5 1,51 3317,5 695 4,77 1560 368,5 4,23 10 1171 292 4,01 320 200 10 859,5 361 2,38 3359,5 355 9,46 1679 185 9,08 20 1085 152,5 7,11 640

											1,00 2 57	35	1,63 64
	5	5	50,5 24,5 2,06	77	27	2,85	48	27	1,78 10 60	27	2,22 320
	5 10	54	28	1,93	97	28	3,46 64,5	27	2,39 20 63,5	27	2,35 640
	20 1	319	326 0,98 352	359 0,98 225,5 177 1,27 2 211	172 1,23 64
	20 5 134,5 72,5 1,86 315	72,5 4,34 194,5 57,5 3,38 10 186,5 43	4,34 320
	20 10 107	46,5 2,30 316	41,5 7,61 160,5 34	4,72 20 216 33,5 6,45 640
	200 1 3253

A long-term experimentation[START_REF] Royer | Retour d'expérience après plus de 1000 km en navette sans conducteur guidée par vision[END_REF] has been performed in the industrial site "Ladoux" of Michelin at Clermont-Ferrand where a fleet of VIPAs was operating for several months (October

-February

2015).

Circuits can also be lines where one end is the origin and the VIPA can change its direction only in the two ends of the line.

The first block σ 1 of n • Cap requests:

The second block σ 2 of 2 • Cap requests

Cap Cap the performance of algorithms but an online algorithm having the best competitive ratio in theory may reach the worst case more frequently in practice with a certain topology. That is the reason why we are not only interested in the "worst-case" but also in the "best-case" performance of the algorithms, thus we need to determine properties which govern the behavior of each chosen algorithm and define the cases where it can be applied and give the best results in terms of performance. So far, we can suggest the following:

-Morning/evening: partition the network into disjoint circuits as subnetworks such that each subnetwork contains one parking p, assign one or several VIPA to every circuit operating in tram mode using SIF M resp. SIF L . -Lunch time: consider a collection of circuits all meeting in a central station (the restaurant), one or several VIPAs on each circuit operating in tram mode using SIF L . in general: consider a spanning collection of lines and circuits meeting in a central station where one VIPA (in elevator mode) operates on each line using M AIN , one or several VIPAs (in tram mode) on each circuit using SIR.

The future works are to analyze the proposed scenarios and algorithms further, e.g., by

providing competitive ratios w.r.t. the objective of minimizing the makespan, studying also the quality of service aspect by minimizing the waiting time for customers, providing solution approaches for the taxi mode.


The language of inscriptional Tamil is very intriguing despite its complexity for many reasons including its properties such as extensive code-mix between Indo Aryan and Tamil, adaptation of different scripts and so on. The Tamil epigraphic routines or more specifically the Tamil epigraphic culture developed mostly under a pan-Indian cultural, historic and sociolinguistic context and model. The raise of Tamil as epigraphic language should be seen as a dynamic process. As can be seen from palaeographic, lexical, syntactic and semantic features, a separate variety of epigraphic Tamil evolved constantly alongside of the literary varieties. Much of the credit goes to many pioneering epigraphists and scholars for their continued contribution to the development of the fields of Indian and Tamil epigraphic studies for more than a century despite the lack of encouragements from the scholarly circle, whose attention was paid mostly to Tamil literature and history. However, the linguistic study of Tamil inscriptions is in a nascent stage. In this present work on the emergence of Tamil as inscriptional language, I would like to present succinctly, from a historical linguistic point of view, two aspects: 1) the process of Indo-Aryanisation and 2) a few salient syntactic features of inscriptional Tamil.

Language of Tamil Inscriptions and Historical Linguistics

Given the diversity of Tamil corpus spread over the course of two millennia, Tamil has a lot to contribute to the field of historical linguistics in general. Every language changes over the time during the process of its transmission, and the structure of language, has thus become a case of constant and continued evolution. Generation after generation, as we can notice in the case of Tamil, new words are coined or borrowed, the meaning of old words drifts, morphology develops or decays, the syntactic structure has changed over time and in short the 'Modern Tamil' language as a whole has become different completely or partially while compared to that of Saṅgam literature, for instance. Otherwise we would not need a special training to read and interpret our old Saṅgam literature. A closer look at the language of Saṅgam shows how it has become distant and different from the 'Modern Tamil', and that they are not mutually intelligible. This is equally true with the language of Tamil inscriptions. These natural and progressive changes in the language defy the adequacy of the traditional grammars for the description of the language of the literary and inscriptional texts. We are forced to re-create grammar and lexicon based on the type of corpus we are encountered with.

The Tamil epigraphic language has never existed as a monolithic and hermetically closed entity. Thus it is crucial to consider the Tamil epigraphic language, on the one hand, with more sociolinguistic implications, and on the other, with historical linguistic methods. Each kind of text -oral or written, inscriptional or literary -in fact has its own underlying grammatical structure. Whatever be the linguistic 'model' or 'methodology' selected to analyse the vast Tamil corpus, it is important to study each kind of corpustext separately and within a given chronological frame. Indeed, the linguistic study of Tamil epigraphic texts requires appropriate and specific analytical tools.

The Dravidian comparative linguistics, in the last few decades, has arrived at excellent results at the different levels of language change: phonology, morphology and etymology. However, the field of historical syntax remains to be explored in detail. In order to make the following discussion clear, and to lay emphasis on the need for the study of historical linguistics, let me start by the following quotations: According to Andronov, the comparative Dravidian linguistics is just 'anti-historical' or 'unhistoric': "Moreover, concentrating on the reconstruction, that is the pre-history of certain elements of accidence, they ignore their history, i.e., the historical evolution of the four literary languages." (Andronv 2001:12). Similar sentiments can be observed in the writings of Bh. Krishnamaurthi, expressed slightly differently.

Bh. Krishnamurthi, on his part, deplores the lack of historical data in comparative Dravidian studies: "Even for the literary languages, we do not have any study of syntax of the language of the classical texts. Therefore, it is not easy to make a systematic study of comparative syntax and make statements applying the comparative method." (Krishnamurthi, Bh. 2003:420). K.Rangan, in his evaluation of syntactic studies in Tamil has sounded the alarm about the general lack of interest in Tamil syntax. "The rise and fall of interest in the area of Tamil syntax have been witnessed for more than three decades. The field of Tamil syntax at present is not experiencing a period of excitement. Different models have been applied to the data of Tamil language. The models are short-lived and they disappear with the same speed with which they appear in the linguistic scene. The interest to bring counter-examples to prove or disprove the hypotheses dominate the research activities rather than the in-depth description of Tamil language". (K. Rangan 2000:58).

It is interesting to note that, more than half a century ago, V.I. Subramoniam had invited the Tamil linguists to take into account the Tamil epigraphic source: "The neglect of Tamil Epigraphy by Tamil linguists is sad indeed. Linguists of Tamilnad confine themselves to such fields like literature, history, philosophy and so on, but never paid any attention toward epigraphy. The language of literature is refined, embellished and archaic. The Changes that occur in the day to day speech seldom find a place in literature. The linguist who is content with the study of literary language is like a zoologist satisfied with the analysis of an old fossil of a living specimen". Further he explains: "The language of Epigraphists is not literary Tamil. Nor is very colloquial. It can be considered as the the standard spoken tongue of the day with minor dialectal peculiarities of the place where the epigraphs were incised" (Subramoniam V.I., 1954: 137).

Last but not the least, Y. Subbarayalu explains in clear terms why handling of inscriptional texts needs an intensive textual analysis? "Whatever conceptual framework is used to understand past history from inscriptions, intensive textual analysis should precede their interpretation. Several terms in old inscriptions are likely to be obsolete now (Subbarayalu, 2002-03). Some of them are not even found in the old literary or lexical works and so only the contexts of their occurrence can clarify their purpose. Sometimes a comparative study of Kannada inscriptions may help to clarify passages in Tamil inscriptions and vice versa. It takes time to get accustomed to the language of the inscriptions, which have some peculiar grammatical features. But there is no short cut; diligent reading is the only method available." (Y. Subbarayalu 2006:54). The above quotations suffice to highlight that the study of Tamil and Dravidian syntax, both diachronic and synchronic, and the Dravidian epigraphic corpus need due attention from scholars.

Epigraphic Tamil and Tamil Linguistics

Tamil epigraphic corpus is not only a neglected source in the study of Tamil historical linguistics but is also subject to serious social and linguistic prejudice. After T.P. Meenakshisundaran's 'History of Tamil Language (1963), number of devoted scholars on Tamil ephigraphy is very minimum in number. The works of scholars such as S. Agesthialingom and S.V.Shanmugam; K. Kanapathypillai; A. Velupillai, K.V.Zvelebil stand alone in this vast area of research. One of the reasons may be that the traditional Tamil scholars did not hold the inscriptional Tamil in high esteem as it is not 'the language of literature', hence stigmatised as less pure, and deliberated not worthy of scholarly attention.2 They considered this variety of epigraphic Tamil closer to the 'spoken Tamil'. This opinion has gained ground even among the linguists. While describing Tamil inscriptions, T. P. Menakshisundaran has stated "In these records we have more of the colloquial language as it was current in the varying ages to which the records belong". (1965:7). Zvelebil, in his Introduction to the historical grammar of Tamil proposed three language varieties: "Centamil or 'standardized literary language', the 'inscriptional language', the 'hybridized, Aryanised Buddhist and/or Jaina Jargon '" (1970:15-16). As for Zvelebil "…the inscriptional language, most probably nearer to the spoken language, best represented in its beginning stages by middle and later Pallava inscriptions, and later by the Chola inscriptions, akin to somewhat to the language of early and middle bhakti poetry " (1970:16). In this respect, A. Velupillai's work goes a step further by introducing a dichotomy namely 'standard vs not-standard' dear to Tamil linguists particularly in the case of diglossic nature of Tamil. 3 All the senior scholars might be certainly right in their findings but what is puzzling for the reader is that he is left with so many different complex linguistic assumptions like 'colloquial language', 'standard vs non-standard', 'hybridized jargon', 'language of bhakti poetry' etc., for which no empirical evidence is available.4

Indian Epigraphic culture and Language contact

The development of Sanskrit, few Middle Indo Aryan and the four major Dravidian languages as inscriptional language is very interesting from historical sociolinguistics point of view. For instance, contrary to the literary sources, the Prakrits were the first language of inscription as can be seen from the Ashokan edicts. In early Indian inscriptions the Prakrit, Middle Indo-Aryan (MIA) were the only languages from about 3rd century B.C. for at least two centuries. Sanskrit became the language of inscriptions only after the advent of Guptas to power at Pataliputra. In North India, Prakrit was replaced by Sanskrit in the 4th century A.D. This period is characterised by a highly diverse situation of language contact. Till the medieval period, "bilingual" inscriptions became prevalent throughout India. The invocatory, genealogical, and concluding portions will be in Sanskrit, while the "functional" portion recording the specific details of the gift, transaction and other details, would be in the other language. (Sircar 1965: 39-60;Solomon 1998: 72-109). A quick look at the inscriptions in different Indian languages shows, without doubt, that the process of Sanskritisation is a linguistic and cultural norm and Sanskritisation legitimizes the promotion of regional languages as epigraphic language.

Contact between Tamil and Indo-Aryan

Indo-Aryanisation should be recognized as an assertion of cultural heritage [START_REF] Sridhar | Linguistic Convergence: Indo-Aryanization of Draviadian Languages[END_REF]). The Sanskritisation is a scalar process. The non-literary languages spoken in the Indo-Aryan region seem to have undergone a greater amount of structural (morphological, syntactic) influence. Whereas the literary languages of the South have been influenced predominantly on the lexical level. The copper-plate charters of the Pallavas, the Cholas and the Pandyas were written in both Sanskrit and Tamil languages till 12th A.D. The rate of borrowing from Indo-Aryan depends on the type of Tamil inscriptions. For instance, in the earliest Tamiḻ-Brāhmi inscriptions (4 BCE-4 CE), the amount of IA borrowing is estimated to be more than 50% (I. [START_REF] Mahadevan | Early Tamil Epigraphy from the Earliest Times to the Sixth Century C.E. Revised & Enlarged Second Edition[END_REF][START_REF] Zvelebil | Introduction to the Historical Grammar of the Tamil Language[END_REF], whereas in the Hero-stone inscriptions it is around one percent. But the temple inscriptions and in copper plate charts the amount of IA borrowing is surprisingly high. I will present below a few examples to illustrate the process of Indo-Aryanisation5 and de-Indo-Aryanisation of Inscriptional Tamil and its sociolinguistic implications. The royal titles and epithets are in many instances Indo-Aryanised. Her are two examples of titles of Chola kings. pāṇṭiya kulāśaṉi 'Destroyer of the Pandya dynasty' pāṇṭiya+ kula+ aśani: Pandya + royal family, dynasty + thunder bolt This expression literally means 'the one who is like a thunderbolt to the Pandya dynasty' pāṇṭiya kulāntaka 'The one who destroys the Pandyas' pāṇṭiya+ kula+ antaka: Pantya + royal family, dynasty + : one who puts an end We notice code mixing at the morphological level. This kind of code mixing is very commonly noticed in the Tamil inscriptions. prāptiyinālē 'profit gained from assets (interest)' prāpti 'acquisition, gain, profit' -in-: augment -āl-: instrumental case -ē-: emphatic morpheme.

Phonological & morphological adaptation in Tamil of Indo-Aryan borrowings has been discussed in many previous works. (Shanmugam S.V. 1968). The following instance is attested in the earliest stone inscription of Pulankurichchi (450 CE). attikōyattār: officer of regiment of elephants, derived from hastikosa: 'officer of regiment of elephants'. hastikosa > attikōyam, in this case the phonological adaptation of the IA borrowing into Tamil is carried out exactly according to the Tamil phonological rules.

-tt-: oblique case morpheme -ār: plural and honorific suffix. Any linguistic form appearing in writing can be assumed to have been in use for some time, at least one or two centuries, in the (spoken) language. The last example illustrates the formation of a 'compound verb'. This compound verb is formed on an IA base 'śilā-lekha' which means 'writing on a stone', an inscription on stone, to which two Tamil verbs are added. slālekhai ceytu kuṭuttōm ''we made engraved on stone'. The same expression is also available in Tamil: kallil veṭṭi kuṭuttōm ''we made engraved on stone'.

De-Indo-Aryanisation, is an important and interesting sociolinguistic phenomenon found in Tamil inscriptions. This involves the creation of new terms in Tamil and can be considered as a reverse process of replacing Indo-Aryan loan words. These include royal titles and as well names of gods and deities. We come across the term kōnēriṉmai koṇṭāṉ, a title used in the royal orders, which is used to replace the king's name. This term signifies the 'peerless king', 'the king who has no equal'. Kō+nēr+iṉmai+koṇṭāṉ: 'king+matchless+acquired'. Presumably, the Tamil expression nēriṉmai is a loan translation of the Sanskrit term atulya' 'unequal, incomparable'.

In general, the Indo Aryan terms for the gods or deities are always borrowed directly and used in Tamil. Contrary to this conventional practice, we come across the creation of terms in Tamil by loan translation. For example, the term naṭarāja is not used in Tamil inscriptions. Instead we notice either āṭavallāṉ 'the one excellent in dance' or 'kūttāṇṭavaṇ' 'the god of the dance'. Another striking example is 'ardha nārīśvarā', this expression is not found in Tamil inscriptions, instead we notice an interesting form by loan translation 'peṇṇōr pākaṉ' made of both Tamil peṇ and Indo Aryan bhāga, pākaṉ derived from < bhāga. 'Person who has anything at his side; partner' (Tamil Lexicon). These attestations clearly indicate the fact that the linguistic processes namely Tamil purism and Tamilization etc., have not been nothing new and they have been in place from the medieval inscriptional periods onwards [START_REF] Murugaiyan | Stèles funéraires en pays tamoul : Langue et société aux 6 e -7 e siècles)[END_REF]).

`Indo-Aryanisation` and 'De Indo Aryanisation' or more explicitly 'Tamilization' are the two concurrent processes of historical developments in the evolution of Tamil as inscriptional language. The higher rate of IA borrowings in the Tamil inscriptions has given rise to a special style of epigraphic maṇipravāḷa. Again, what is sad to notice is that while the Tamil scholarly tradition recognizes only the vaiṣṇava maṇipraāḷa (Venkatachari K.K.A 1978) but a great amount of epigraphic maṇipravāḷa is left unnoticed. It is further unfortunate to note is that this maṇipravāḷa style is legitimised in vīracōḻiyam, a traditional Tamil grammar of 11 th century CE. The process of 'Indo-Aryanisation' and 'de-Indo-Aryanisation' or Tamilzation should be regarded in their social context and are part of historical developments in the evolution of Tamil as inscriptional language, like all other Indian languages. The earliest Tamil inscriptions (both stone -Pulanguricci inscription-and copper plate charts -Pallankoyil copper plates-) show clearly that the contact between Tamil and Indo-Aryan was already in a well advanced stage. The extent to which a given language has been influenced by Indo-Aryan depends mainly on the cultural and political motivations of the users of receiving language. As I had mentioned above, a good piece of rationalisation would be the case of Tamil Hero-Stone inscriptions, where up to 9 th century CE, the IA loan words amount hardly more than one percent. Tamil social dialectologists have to fight long and hard for the acceptance of language variation free from normative and prescriptive judgements.

Syntactic Features of Tamil Inscriptions

Inscriptions are the primary historical sources and they contain records of various types: donation and land grants to the temples and village assembly, land sale deeds, tax remissions, decisions made by the village assembly, desertion of village by cultivators, irrigation, revolt by cultivators and artisans, etc. [START_REF] Noboru | South Indian Temple Inscriptions: A New Approach to Their Study[END_REF][START_REF] Subbarayalu | Inscriptions as Sources for History, Le Sources et le Temps (Sources and Time)[END_REF]. These records are highly informative in nature and very precise. The authors of these inscriptions have used specific grammatical tools to make these records precise and un-ambiguous. A detailed linguistic analysis shows clearly that the syntactic structure of these inscriptions are based on two major principles: 1) information structure and 2) pragmatics. Any natural language can offer a variety of possibilities to express the same information. All such options are not made available in our traditional grammars. Another major problem is that the linguistic changes that have occurred in Tamil during the last two millennia are not recorded systematically in our traditional grammars. So is the need for anyone to device an appropriate grammatical tool while trying to account for the syntactic structure of Tamil inscriptions or even the Sangam texts [START_REF] Murugaiyan | Hero Stone Inscriptions in Tamil (450-650 CE.): Text to Meaning: A Functional Perspective[END_REF]). In the Tamil epigraphic texts the morphological case morphemes genitive, locative, ablative are not systematically used. Dative is the only exception. The accusative case is used only to mark the grammatical object but the donated objects are never marked in accusative case. Many body-part nouns are used as postpositions. As to the verbal forms, the finite forms are very rarely used. On other hand adverbial participles and adjectival participles are most commonly used. This gives a completely different picture of the predicate structure [START_REF] Murugaiyan | Organisation prédicative dans des textes épigraphiques tamouls[END_REF]. The commonly recognised SOV word order is not relevant in the inscriptional Tamil. On the contrary, the word order is not triggered by grammatical features, but mostly controlled by pragmatic features. In the following pages I will try to show a few selected features of the syntactic structure of the inscriptional Tamil.

Earliest Tamiḻ-Brāhmi Hero stone -Pre Early Old Tamil Structure?

The oldest written records in Dravidian are the Tamil-Brahmi inscriptions, covering a period of more than seven centuries from ca. 3rd century BCE to 5th century CE. They provide strong chronological evidence for the evolution of the Tamil language. The following inscription dating 3 rd BCE was discovered at Pulimāṉ kōmbai, Teni district in 2006. This inscription is of great historical importance by its content and also by its linguistic structure. A detailed description of this Tamiḻ Brāhmi inscription is given by K. Rajan et al. (āvaṇam 2006:1-5). 1. Kal 2. pēṭu tīyaṉ antavaṉ 3. kūṭal ūr ākōḷ which means "This is the memorial stone (erected in honor) of Pēṭu Tīyaṉ Antavan during the process of cow-lifting at Kūṭalūr" A quick examination of these inscriptions would indicate the absence of case markers and copula or other verbal forms. The word order is completely inverse while compared to that of Modern Tamil. This type of inscriptions can be interpreted successfully mainly by the semantic features of the lexical items. I. Mahadevan in the same volume suggested a new reading as follows ((āvaṇam 2006:6-8): 1. kūṭal ūrā kōḷ 2. peṭu tīyaṉ antavaṉ 3. kal And commented that, "the word order is confusing" and according to him a verb is needed to complete the sentence and hence suggested that "Pēṭu" should be replaced by the verb peṭu / paṭu 'be deceased'. One can easily understand I. Mahadevan's highly justifiable point of view. But the problem with his linguistic judgement is it is based mainly, on the one hand, on rules prescribed by traditional grammars like Tolkāppiyam and on the other hand, through the intuition of the grammar of Modern Tamil. But his analysis is not doing any justice to the historical evolution of the Tamil language during the past two thousand years and more. This and many other early Tamiḻ-Brāhmi inscriptions depict a pre-Sangam analytic structure as explained clearly by Pilot-Raichoor (Pilot-Raichoor 2012). The earliest structure of Tamil (Dravidian) language was typologically analytical. There was a typological shift from analytic to the present agglutinative structure during pre-Sangam period. M. Varadrajan was probably the first who argued in favour of analytic type in old Tamil and explained how "certain verbal forms in certain moods had no accessory notions of persons, gender and number […]" (M. Varadarajan 1957: 22). Ten years later, Zvelebil based on his works on the early Tamil texts clearly posited the idea of a typological shift [START_REF] Zvelebil | Introduction to the Historical Grammar of the Tamil Language[END_REF]. « It can be supposed that the period preceding the Early Old Tamil (EOT) stage was in a state similar to "isolation" while the EOT period [the first historically attested stage of development] had a transient character with disappearing traces of isolation, typical features of agglutination and nascent features of inflection". According to this hypothesis, the pre Old Tamil represented both an old system of isolating type and also features of agglutinative type as found in Modern Dravidian languages. Finally the credit goes to Pilot-Raichoor, who had established without doubt that Proto -Dravidian was most probably an isolating language and explained the typological shift from analytic to agglutinative type in Dravidian based on Tamil-Brāhmi data. "The Tamil-Brahmi data give evidence for both the isolating6 or 'analytical'7 tendency of the previous stage and the development of the process of agglutination. Data found in these records converge with data from other sources of Old Tamil to signal the emergence of a new type of grammar, caught in its formative stage, with a great variety of constructions which will later on be reduced to more regular constructions in derivations and morphological paradigms." (Pilot-Raichoor 2012:285). The Tamil language of Pulimāṉ Kōmbai inscription represents the grammar of the pre Early Old Tamil stage. It is misleading to analyse this text according to the agglutinative type of grammar of Modern Tamil. However, the Pulimāṉ Kōmbai Tamiḻ-Brāhmi inscription reveals two historical linguistic facts: 1) the whole syntactic structure reflects the pre Early Old Tamil stage and 2) the word order is pragmatically governed and respects the principle of information structure or information packaging.8

Accusative Case and Object of donation

Another interesting feature of inscriptional Tamil is the differential use of the accusative case marker. This differential use is not taken care of by our traditional grammars. In the inscriptional Tamil, the accusative case is used only to mark the grammatical objects but not used to mark the donated object [START_REF] Murugaiyan | Object of Donation in Tamil Epigraphic Texts (10 th -11 th Centuries): Exploring the Interaction between Syntax and Information Structure[END_REF] The above example is from an inscription describing the donation of rice fields from different villages. The village has already been mentioned in the text and is established as topic of the clause. The noun ūr 'village' marked in accusative prefixed with the deictic particle is an argument of the two place predicate ūṭaṛu 'pass across'. This noun ūr marked in accusative is in fact the definite direct object and form part of the discourse narration, and can be considered as backgrounded event. This clause is subsidiary or a framework to the propositional content 'canal which irrigates the other villages' expressed in the main clause.

The noun phrase 'vāykkāl' canal, is the subject argument of two verbs 'cross through' and 'irrigate' respectively. The object 'ivvūrai', though referring to a direct object is not the complement of a verb expressing a donation. "we members of the great assembly…. gave… to the God 200 kuḻi consisting of 5 rice fields'

This inscription describes a gift of land made by the members of the village assembly. In this example we have an 'unmarked SOV' constituent order and this is not very frequent in inscriptional Tamil. This 'unmarked order' shows no pragmatic function. The sentence contains a finite verb and shows agreement with the subject argument. It is interesting to note the inversion of the numeral quantifiers, 5 and 200 respectively, at the level of the noun phrases, thus giving rise to the phenomenon of quantifier floating. This inversion of numeral quantifiers is in correlation with the principles of pragmatic word order where the new information is placed at the focal and final position of the utterance. "Sōḻamilāṭuḍaiyāṉ had given 96 sheep for (burning) a perpetual lamp he had bestowed"

This inscription records a gift of 96 sheep for burning a perpetual lamp. In 8, there are two clauses which are arranged in a sequential order. First, Sōḻamilāṭuḍaiyāṉ gave a perpetual lamp, and second, for this perpetual lamp he offered 96 sheep. The perpetual lamp is part of the two clauses. In the first event, an object of donation, it is in focus relation. In the second event, a beneficiary marked in dative case, it is in topic relation. In the second clause, the object of donation '96 sheep' constitutes the new information and is the focus of the clause. Right dislocation of the donated object goes in symmetry with the floating of quantifier. The numeral quantifier is on the right side of the noun it qualifies instead of preceding it.

In the above example, the donated object, unmarked for accusative,9 is placed on the right of the predicate in the focus position. The object of donation is typically encoded in this dislocated noun phrase, extracted from its basic OV position through a relativization process. This right detachment triggers also the phenomenon of quantifier floating, where the quantifier is placed on the right side of the noun head. These changes bring structural symmetries which are used by the information structure to enhance the reading of the inscriptions. The dislocation of 'object of donation' is clearly the result of a discourse strategy. The variation in the order of constituent could be better explained in correlation with factors like historical changes or as a combination of syntactic, semantic and pragmatic (discourse) factors. This type of structure is common in inscriptional Tamil and may be considered as a specific grammatical technique to mark the donated object.

Word order variation in inscriptional Tamil

Change or variation in word order type is one of the most important areas in the study of historical linguistics. Several studies on historical data have shown that variation in word order is a common feature and argued that this variation in many of the languages may be dependent on the information structure (IS) : Icelandic, Old and Middle English, Greek, German, Hebrew, Vedic Sanskrit, Chinese for instance. Inscriptional Tamil is not an exception to this word order changing process. The idea of a basic word order typology is primarily based on the syntactic relations between the verb and its nominal arguments (subject and object). This means that the concept of basic word order is essentially syntactic. On the contrary, in some languages word order is established exclusively on pragmatic grounds [START_REF] Thompson | Modern English from a typological point of view: Some implications of the function of word order[END_REF][START_REF] Marianne | Is basic word order universal?[END_REF].

We can roughly identify two different views on the word order in Old Tamil: (1) Zvelebil claims in general a SOV word order, but adds "if not disturbed by stylistic or emphatic shifts…" (Zvelebil, K. 1997.43), (2) Andronov suggests a free word order (1991) and in a more recent work Suzan Herring proposes SOV as the basic order [START_REF] Herring | Poeticality and word order in Old Tamil[END_REF].

Regarding the word order in the earliest records T.P.Meenakshisundaran noticed that "the subject […] followed the predicate very frequently in ancient times, so frequently, indeed, that it cannot be rejected as mere poetic inversion. This syntactic structure represents an old state of affairs, when the subject did not always precede the predicate as it frequently does in Modern Tamil" (1965:3). This statement reminds us of the typological shift mentioned above.

A sample analysis of word order in inscriptional Tamil shows that the variation in constituent order depends on the pragmatic factors and we will focus our attention only on verbal clauses, both finite and non-finite [START_REF] Murugaiyan | Identifying Basic Constituent Order in Old Tamil: Issues in historical linguistics with Special Reference to Tamil Epigraphic texts (400-650 CE)[END_REF]. The place of different constituents in these propositions, in turn, are controlled by information structure and other contextual considerations. The term information structure is used to refer to various ways in which information, including propositional information and real-world knowledge, is linguistically encoded. In my previous analysis, I used the saliency parameter as the major pragmatic factor. By salient information we mean 'important or key piece of information that the author of the inscriptions wished to convey his audience or readers. (Mithun 1992). According to my pilot survey, the constituent order in inscriptional Tamil is neither free nor strictly adhering to SOV, but is sensitive to pragmatic factors (saliency or newsworthiness).

Various word orders are exhibited, but none of them stands out as being significantly more frequent than any other order [START_REF] Murugaiyan | Identifying Basic Constituent Order in Old Tamil: Issues in historical linguistics with Special Reference to Tamil Epigraphic texts (400-650 CE)[END_REF].

Pronominalised nouns / Appellative verbs

Finally, I would like to draw our attention on the extended use of pronominalised nouns known as kuṛippu viṉai in Tamil grammatical tradition also known as appellative verbs in Dravidian linguistics. The pronominalised nouns are widely used both as arguments and predicate in inscriptional Tamil. From a historical perspective, this particular form is very significant in the sense that it exhibits a turning point in the typological shift in Tamil from an isolating to an agglutinative language as mentioned above.

This pronominalised noun (PNN) is formed by affixing the Person Number and Gender (PNG) marker to any stem (STEM + PNG). These PNN forms in 1 st , 2 nd and 3 rd persons are attested in many Classical Tamil verses with distinctive grammatical functions as argument or predicate. nāṭu > nāṭaṉ "the one from/ possesseur of nāṭu" > nāṭaṉai "you chief of the nāṭu" Whereas, in Modern Tamil, the PNN forms as occurred in 1 st and 2 nd person nouns have almost fallen into disuse and those in 3 rd person, though are in use, this, however, tends to be generalised and lost their Person distinction. On the contrary, in Tamil inscriptions the PNN seem to be frequently used. A detailed analysis of the data from the inscriptional Tamil reveals not only that PNN are used in wider grammatical contexts and preserve their multifunctionality (like arguments and predicate) but also the proper nouns are pronominalised, probably, unique feature in the Tamil pattern.

In the inscriptional Tamil we notice any noun, common noun, numerals and proper noun can be pronominalised. SII. 12. 55 nāl-v-ōm "we four" tontāviḷakk.erippōm.āṉōm […] innalvōm …… perpetual lamp burn.nonpast.1pl. oblige.past.1pl deic.four.1pl

"We four […] are obliged to lit a perpetual lamp"

The pronominalisation of common nouns are attested in Tamil and in many other languages. However, in the inscriptional Tamil we notice the pronominalisation of proper nouns. This seems to be an innovation in epigraphic Tamil and not noticed in other Tamil literary texts. I, Nārāyaṇaṉ Aṭaikalavaṉ, the accountant of this city, I wrote

The technique of pronominalizing nouns is a characteristic feature of omnipredicative languages. In omnipredicative languages different parts of speech behave similarly syntactically.

CONCLUSION

In the above pages, I tried to present a few salient features of the inscriptional Tamil based on my previous works. It would be impossible to present here all the characteristic elements of epigraphic Tamil that are pertinent for the historical linguistics. The most interesting aspect would be the presence of archaic characters in the Tamiḻ-Brāhmi inscriptions. Many of the points discussed as above are either not attested in the traditional grammars of Tamil or not observable in Modern Tamil. In few cases, what had been considered as 'ungrammatical' in epigraphic Tamil by scholars are simply based on the relics of the old structures as defined in the traditional grammars and suggest a failure to understand the distinctive features of inscriptional Tamil. To summarise, it may not be an exaggeration to presume that every aspect of the grammar of inscriptional Tamil is different from the variety of Modern Tamil and also from the other known 'varieties' of Tamil. The 'grammars' of inscriptional Tamil is motivated, among other things, mainly by the principles of information structure or information packaging. Thus, a careful study of the inscriptional Tamil, particularly on the grounds of its distinctive and salient features, would surely help to understand better on the typological changes that underwent during the transition of language change from Classical Tamil to Contemporary modern Tamil.

BIBLIOGRAPHY

  . Let us consider the following examples:

	SII.2.5.p56.11
	…..ivvūrai	ūṭaṛuttup pōy puṛavūrkkup pāyum	vāykkāl …..
	…..deic.village.acc	cross.go.adp	other villages.dat irrigate.rp	channel
	'… canel which crosses through the village and irrigates other village…'

  Raman Kāri kannan, the writer took notice came and reported [the order]' In the above example, a verbal phrase occupies the clause initial position and the agent noun phrase is at the clause final position. The finite verb is preceded by a set of adverbial participles, describing a series of sequential actions. The writer and his identity (the proper noun), the salient pieces of information, are at the clause final position. Among the two nominals, the name of the writer rāmaṉ kārikaṇṇaṉ, unpredictable to the audience, is at the right most part of the clause and occupies the highest position in the saliency hierarchy. This is the memorial of Santirananti Asirikar, [who] fasted for 57 days [and gave up his life]' The above example constitutes itself an inscription. While we read an inscription, the context and the location in which the inscription is situated become crucial to understand the meaning. In this example, the most important or salient information 'nicītikai' (memorial) is placed at the focal position, which is normally position of predicate.

	listen.adpl	come.adpl	say.past.3.ms	writer	pn
	'S.I.I.17.262 (0600 CE) [VSN]
	aimpateḻ	aṉacaṇan nōṟṟa	cantirananti ācirikar nicītikai
	57	fasting	endure.rp	pn		memorial
	'Type of inscription	Verb final	Verb non-final	Total
		Pulanguricci	06		09	15
		Pallankoyil	15		05	20
		Hero stone		46		34	80
		Total		67		48	115
		Percentage		58.26%		41.73%
	āvaṇam, Pulanguricci inscriptions (450 CE) [VS]
	kēṭṭu	vantu	kūṟiṉāṉ	ōlai eḻutuvāṉ	ṛamaṉ kārikaṇṇāṉ

  Andronov, M. 1991. Word Order: Causality and Relations, (eds) B. Lakshmi Bai & B. Ramakrishna Reddy,Studies in Dravidian and General Linguistics: A Festschrift for Bh. Krishnamurthi, 91-97. Hyderabad: Osmania University.

Andronov. M. 2001. Dravidian Hstorical Linguistics, LINCOM EUROPA

It is a great pleasure to be able to contribute to this volume that celebrates and honours the service of a dear friend Professor L. Ramamoorthy

See for instance the following passage of M. Raghavaingar in Tamil, translated by Y. Subbarayalu "Generally inscriptions cannot be rated high on the basis of the Style of their language. By their very nature of writing on stone, they abound in Orthographical and grammatical errors. Hence it would be rare to find Tamil Scholars taking an interest in studying the inscriptions. […]" and the comment by Y. Subbarayalu "This passage reflects the exact attitude of the majority of Tamil scholars towards inscriptions which have been approached by them with some scorn."(Subbarayalu 2006: 49-50).

"The language used in most of the Pandiya inscriptions was rather close to the standard Tamil. It preserved classical form in a large measure. On the other hand, as a whole, language was not standardised in the Pallava Kingdom"(A. Velupillai, 1980:172).

The 'unstandardized' form of epigraphic language is not only said of the Tamil inscriptions, it is also noted in the case of inscriptional Prakrits: "The inscriptional Prakrits are diverse and largely unstandardized. Much more than is the case with the literary Prakrits of later times, the morphology and especially the orthography of the inscriptional dialects is unstandardized and inconsistent, to the extent that it is not unusual to find the same word spelled several different ways within the same inscription.(Solomon 1998:72).

The term Indo-Aryanisation is preferred to Sanskritisation as we come across borrowings from Prakrits, Pali and Sanskrit.

In an 'isolating' language, "each word consists of one morpheme. That is, each lexical root is a word and each grammatical element is shown as a distinct word (not as an affix)" Dixon 2010/1:226).(cf. Pilot-Raichoor 2012)

In modern typology, other classificatory parameters are used. One of them is a scalar evaluation of the complexity of the words: from "analytic': smallish number of components -root(s) plus grammatical elementsper word" to "synthetic: largish number of components per word" (Dixon 2010/1:226). ).(cf. Pilot-Raichoor 2012)

8 This type of word order is seen even in later Sangam texts. See for instance in Cilappatikāram : eḷḷunar pōlum ivar eṉ pūṅkōtaiyai / mock-3pl like they my flower garland.acc/ 'these people would mock at my flower garland (heroine)'Cilap.1.10.231

However,, the objects that are weighed, measured, counted, received take the accusative case marker. If we analyse this pattern based on the above rule of (tol.col.72), this may be considered 'ungrammatical'. But the grammatical function of the accusative case is replaced by the relativization process which renders the donated object definite.