Alaa Daoud
email: alaa.daoud@emse.fr

Flavien Balbo
email: flavien.balbo@emse.fr

Paolo Gianessi
email: paolo.gianessi@emse.fr

Gauthier Picard
email: gauthier.picard@onera.fr

ORNInA: A Decentralized, Auction-based Multi-agent Coordination in ODT Systems

Keywords: On-demand transport, Coordination, Decentralized optimization, Combinatorial auctions

systems have attracted increasing attention in recent years. Traditional centralized dispatching can achieve optimal solutions, but NP-Hard complexity makes it unsuitable for online and dynamic problems. Centralized and decentralized heuristics can achieve fast, feasible solution at run-time with no guarantee on the quality. Starting from a feasible not optimal solution, we present in this paper a new solution model (ORNInA) consisting of two parallel coordination processes. The first one is a decentralized insertion-heuristic based algorithm to build vehicle schedules in order to solve a particular case of the dynamic Dial-A-Ride-Problem (DARP) as an ODT system, in which vehicles communicate via Vehicle-to-vehicle communication (V2V) and make decentralized decisions. The second coordination scheme is a continuous optimization process namely Pull-demand protocol, based on combinatorial auctions, in order to improve the quality of the global solution achieved by decentralized decision at run-time by exchanging resources between vehicles (k-opt). In its simplest implementation, k is set to 1 so that vehicles can exchange only one resource at a time. We evaluate and analyze the promising results of our contributed techniques on synthetic data for taxis operating in Saint-Étienne city, against a classical decentralized greedy approach and a centralized one that uses a classical mixed-integer linear program (MILP) solver.

Introduction

On-Demand Transport (ODT) systems have attracted increasing attention in recent years. The area of application was almost limited to road systems. The ODT system has never been considered for the replacement of public transport services but to extend it. According to [START_REF] Bellini | The demand responsive transport services: Italian approach, Transaction on the Built Environment[END_REF], the concept of ODT was formulated for the first time in the United States around 1990 as a solution to the growing disaffection of potential users, especially at night.

Within ODT, allocation problems rise as the most studied optimization problems in the literature [START_REF] Danassis | Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior[END_REF]. They generally can be addressed by linear programming since its relaxation of formulation admits optimal integral solutions. However, in reality, if a cen-tral dispatcher exists, performing such optimal decisions, it requires vehicles to have continuous access to their portal via the global communications infrastructure such as the Long-Term Evolution (LTE) communication (3G, 4G or 5G), whose data traffic is expensive for the required usage density and the persistent operation, and can cause a critical bottleneck on the portal side.

The computational complexity of ODT allocation problems, which extend the NP-Hard traveling salesman problem (TSP), makes it difficult for the central dispatcher to manage the dynamics of the problem during execution (online requests, variable fleet size, traffic problems, and other environment dynamics). Therefore one may expect that decentralization can cop off with these problems. The insertion heuristics proposed by [START_REF] Solomon | Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[END_REF] is a popular method for solving a variety of scheduling and routing problems. It can be used as a method to quickly find a feasible solution (with no guarantee on solution quality). For instance, in Vehicle Routing Problem (VRP), it creates the solution by repeatedly inserting unscheduled demands in a partially constructed route or as the first demand in a new route. Local search with the k-exchange neighborhoods (kopt) is one of the most commonly used heuristic methods for problems inherited from TSP. k-opt is a path improvement algorithm, where at each planning phase, k steps from the current plan are replaced by k steps to get a cheaper path [START_REF] Helsgaun | General k-opt submoves for the Lin-Kernighan TSP heuristic[END_REF].

In what follows, we will describe the main characteristics of ODT problem in (Section 1) in order to differentiate it from other modes. In this work, we propose the Autonomous Vehicle Fleet Allocation Problem (AVFAP), which extends the traditional Dial-A-Ride-Problem (DARP) with the usage of a fleet of autonomous vehicles, replacing the central dispatcher with the coordination between each other in a Peer-to-Peer (P2P) manner in order to make decentralized decisions. We more precisely propose a new decentralized heuristic for the AVFAP, named ORNInA, benefiting from the fast responsiveness of insertion heuristics and the good results gained by 1-opt optimization.

The paper is organized as follows. In Section 2, we overview the related transport problems in literature, and more precisely, we focus on efforts done to address related ODT problems. Section 3 expounds on the model we consider for the decentralized resource allocation problem for autonomous vehicle fleets with an illustrative scenario showing the main components of the ODT system. Then, the contribution for fast decision is presented in Section 4 and an optimization protocol is detailed in Section 5. Experimental parameters, evaluation, and results are detailed in Section 6. Finally, we conclude the paper in Section 7 with some perspectives.

Problem Definition

The concept of On-Demand Transport (ODT) was formulated for the first time around 1990 as a solution to the growing disaffection of potential users of public transport, especially at night [START_REF] Bellini | The demand responsive transport services: Italian approach, Transaction on the Built Environment[END_REF]. There exist similar terms in the literature describing several transportation systems that could be similar in some characteristics and differ in others; e.g., the term Demand-Responsive-Transport (DRT) refers to the same concept. Moreover, in recent years, the term Dial-A-Ride Problem (DARP) is becoming more common in real- life scenarios, such as the services provided by Uber, Lyft, and other on-demand transport platforms.

For [START_REF] Kfh-Group | Corporation, Guidebook for measuring, assessing, and improving performance of demand-response transportation[END_REF], "On-Demand Transport is a transit mode consisting of passenger vehicles, vans, or small buses that respond to the calls of passengers or their agents to the transit operator, who then sends a vehicle to collect passengers and transport them to their destinations." Additionally, Demand-Response (DR) operation in a transport system was characterized in [START_REF] Ronald | Simulating demandresponsive transportation: a review of agent-based approaches[END_REF] as follows:

• Vehicles do not operate on a fixed course or a fixed schedule, except, perhaps, temporarily to satisfy a special need, • A vehicle can be sent to take several passengers to different collection points before taking them to their respective destinations and can also be stopped on the way to these destinations to catch other passengers, • Passenger could be served by multi-vehicle trajectory, • Requests usually present intentions of a trip from source to destination within a certain time window.

Finally, the main features of ODT optimization are defined by [START_REF] Bellini | The demand responsive transport services: Italian approach, Transaction on the Built Environment[END_REF] to be: firstly, as door-to-door as possible transportation; secondly, minimize waiting times, walking paths, and vehicle changes.

In this context, we propose the Autonomous Vehicle Fleet Allocation Problem (AVFAP), illustrated in Figure 1, as follows: Definition 1. AVFAP is an extension of the traditional DARP with the usage of a fleet of autonomous vehicles, replacing the central dispatcher with the coordination between each other in Peer to Peer (P2P) manner in order to make decentralized decisions.

Since the early 21st century, short-and long-range vehicle communication technologies, including equipment, applications, and systems, have been developed and introduced in the transportation domain to enable the vehicle to everything (V2X) communication. The concept of V2X includes communication between vehicles (V2V), between vehicles and pedestrians (V2P), and between vehicles and infrastructure (V2I). Short-range vehicle communication protocols have been based on the WLAN IEEE 802.11 [START_REF] For | WLAN Standards[END_REF] standards known in the United States as Wireless Access in Vehicle Environments (WAVE) and in Europe as ITS-G5 [START_REF]Intelligent Transport Systems (ITS);Access layer specification for Intelligent Transport Systems operating in the 5 GHz frequency band[END_REF]. Also known as Dedicated Short-Range Communication (DSRC).

V2V communication via DSRC provides low latency, fast network connectivity with a range of communication up to 300 meters.

DSRC has been widely tested in Europe, the United States, and other regions with different road safety and traffic efficiency use-cases. More recently, the direct cellular (C-V2V) using the 3GPP PC5 interface has been introduced as an alternative to IEEE 802.11p for V2V Short Range [START_REF] Ce Delft | The impact of emerging technologies on the transport system[END_REF]. In this paper, neither the cases of multi-vehicle trajectories nor the passenger walking parts of the trip are considered, as we define a satisfied request as a request that is picked up from its specified pick-up location during its defined time window and dropped of exactly in its defined drop-off location [START_REF] Dey | Vehicle-to-vehicle (V2V) and vehicle-toinfrastructure (V2I) communication in a heterogeneous wireless network -Performance evaluation[END_REF]. Having limited communication ranges, each vehicle is only aware of a subset of demands and communicates with entities (vehicles or demand sources) if they are co-located in each others' range.

On-Demand Transport and Related Problems

The problem of resource allocation and task assignment across multiple entities is a central concern in both Computer Science and Economics. It has interdisciplinary characteristics that make it relevant for different application areas, including industrial production and planning, routing, traffic management, transport, and logistics. In our scenario, under a set of constraints, assigning demands to vehicles can be seen as an intersection between resource allocation and constraint optimization problems. The classical modeling approach for such problems is Linear Programming (LP), and more specifically, MILP (Mixed Integer LP).

The problem described by the illustrative scenario (in Section 1) extends the Dial-A-Ride Problem (DARP), which belongs to the family of Pick-up and Delivery problems and can itself be considered as a special variant of the Vehicle Routing Problem with Pick-up and Delivery (VRPPD) with time windows. The problem, which we briefly recall in the following, can be seen as both a scheduling and an allocation problem.

Deal A Ride Problems

In [START_REF] Savelsbergh | The General Pickup and Delivery Problem[END_REF], the Generalized Pick-up and Delivery Problem (GPDP) is defined as the general framework for all Pick-up and Delivery problems. In it, n requests must be served, each associated with a set of origins and destinations to be visited, respectively, to pick-up or deliver goods or people. A fleet of m heterogeneous vehicles, each with its own capacity, is used to serve requests. A request is unsplittable (must be served entirely by one same vehicle) and all origins must be visited before any destination, without transshipment in intermediate locations. Each vehicle has specific start and end locations and can serve more than one request, provided that all along its service route its load is nonnegative and within its capacity. The well-known Vehicle Routing Problem (VRP), which is known to be NPhard [START_REF] Cordeau | Chapter 6 Vehicle Routing[END_REF], is the particular case of the GPDP with the same capacity for all the vehicles and only one origin or destination per request, the depot, which also acts as the start/end point of all routes. Another particular case of GPDP, which also generalizes VRP, is what in [START_REF] Cordeau | Chapter 7 Transportation on Demand[END_REF] is named the Vehicle Routing Problem with Pickup and Delivery (VRPPD), in which each request has one origin and one destination and the vehicles are heterogeneous but all based at a depot. The authors also call it the n-commodities PDP to distinguish it from the single-commodity PDP, in which one type of product is collected or delivered to each node, and the twocommodity PDP that implies two products and every node can act as a pick-up point for one and delivery point for the other: the delivery of beverages, in which vehicles deliver full bottles and collect empty ones, is cited as a common real-life case.

In the same work, the VRPPD with time windows (VRPPDTW) is tackled, motivated by the fact that most practical VRPPD applications enforce restrictions on time slots in which a vehicle can visit a site. VRPPDTW is defined on a directed graph G = (N, A) with 2n + 2, i.e. as many nodes as twice the request plus the two nodes needed to be able to represent outgoing and incoming trips of the depot at which vehicles are based. Vehicles are heterogeneous and must complete their routes within a given time horizon, and service at a node must begin within a time window as- sociated with it. VRPPDTW is NP-hard as it generalizes the TSP with Time Windows and Precedence Constraints (TSP-TWPC), which is known to be NP-hard (see e.g. [START_REF] Mingozzi | Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints[END_REF]). The 3-index Mixed-Integer Linear Programming (MILP) formulation proposed in [START_REF] Cordeau | Chapter 7 Transportation on Demand[END_REF] allows to consider a variant in which vehicles have different start-and endpoint, and which is not easier than the basic VRPPDTW version.

As stated by the authors of [START_REF] Cordeau | Chapter 7 Transportation on Demand[END_REF], DARP is actually a version of the basic VRPPD in which the objective mostly revolves around Quality of Service (QoS), i.e. minimizing user inconvenience, which plays a central role [START_REF] Ronald | Simulating demandresponsive transportation: a review of agent-based approaches[END_REF] (though more specific DARPs allow for one passanger only and thus also restrict the capacity of vehicles to 1). In addition, vehicle capacity is normally limited in DARP, while it is often redundant in VRPPD applications (particularly those related to the collection and delivery of letters and small parcels [START_REF] Cordeau | The dial-a-ride problem: models and algorithms[END_REF]). The work [START_REF] Cordeau | Chapter 7 Transportation on Demand[END_REF] then reviews the different cases of DARP in the literature, like e.g. single-and multivehicle cases, or the different functions to model passenger inconvenience (possibly giving rise to quadratic or convex functions) and how its minimization is dealt with. Quality of Service can replace, or being evaluated along with, some cost related terms, as well as DARPspecific constraints, as e.g. maximum waiting time or maximum excess in user ride times.

In [START_REF] Parragh | Demand responsive transportation[END_REF], the notion of time window is integrated in the basic definition of DARP, as we will consider in the following of the present work. The authors of [START_REF] Parragh | Demand responsive transportation[END_REF] review some of the most common real-world aspect that are dealt with in literature, especially for what concerns the diversity of vehicles, which can differ not only in capacity but also for what concerns e.g. speed, travel cost, equipment, number of person that can be transported, transportation mode depending on the passengers, possibility of accompanying persons. As pointed out in [START_REF] Cordeau | The dial-a-ride problem: models and algorithms[END_REF], the main consideration in some of such a diversity of problems is to tackle the strategic problem of determining a size and composition of the fleet that will satisfy the entire demand, while in others the goal is to maximize the number of applications that can be offered with a fleet of fixed dimensions. A compromise is to serve part of the demand with a basic fleet of vehicles and to use additional vehicles (e.g. regular taxis) if necessary. The authors of [START_REF] Parragh | Demand responsive transportation[END_REF] also propose a wide review of exact methods for static DARP variants, as well as and heuristic approaches for static, dynamic and stochastic variants that are found in the literature.

Along with static Dial-a-ride services, in which all requests for transport are known in advance, there also exist dynamic services, in which requests are progressively revealed throughout the day, or existing requests ar cancelled, and vehicle routes are adjusted in real time accordingly, trying to do so without causing too much trouble for other passengers. In the literature, dynamic variants of DARP can be found, although in practice pure dynamic DARPs rarely exist because a subset of requests is often known in advance, according to [START_REF] Cordeau | The dial-a-ride problem: models and algorithms[END_REF], who reports some examples of dynamic DARP. [START_REF] Madsen | A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives[END_REF] developed an insertion algorithm, RE-BUS, based on the ADARTW procedure of [START_REF] Jaw | A heuristic algorithm for the multi-vehicle advance request diala-ride problem with time windows[END_REF] for a real-life problem involving services to elderly and disabled people in Copenhagen. Requests arrive dynamically along a time horizon and are inserted in existing routes considering the difficulty of insertion. The algorithm is reportedly capable of a good quality-time compromise solutions on a 300-customer, 24-vehicle instance. [START_REF] Colorni | Modeling and optimizing dynamic dial-a-ride problems[END_REF] uses three different objectives, namely the number of serviced requests, the perceived QoS level by users and the traveled distance. The insertion of new requests is based on a clustering phase and a routing phase. The routing algorithm applies branchand-bound to a set of requests that according to time windows are closer to occur. The authors report that they have performed experiments in two cities in northern Italy. Finally, in [START_REF] Coslovich | A two-phase insertion technique of unexpected customers for a dynamic diala-ride problem[END_REF], an off-line/on-line two-phase strategy is used for inserting of a new request into an existing route, the objective being minimum user dissatisfaction.

To conclude this review of Dial-A-Ride Problems, we cite some more recent works. [START_REF] Gschwind | Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem[END_REF] defines an Adaptive Large Neighborhood Search (ALNS) to find a set of minimum-cost routes on a DARP variant with time windows and additional constraints on and maximum user ride times. [START_REF] Muelas | A distributed VNS algorithm for optimizing dial-a-ride problems in large-scale scenarios[END_REF] proposes a distributed algorithm to solve large scale DARP instances: tests on a set of 24 different scenarios with up to 16,000 requests or 32,000 locations in the city of San Francisco prove it effective. [START_REF] Vallee | New online reinsertion approaches for a dynamic Dial-a-Ride Problem[END_REF] tackles a dynamic DARP found in a mobility service operated by a private company, in which service requests are either in advance or in real-time and get an immediate answer about being accepted or rejected. The main goal is to maximize the number of accepted requests. Three main online reinsertion heuristics (HDR, GH, IGH) based on different neighborhoods are proposed. [START_REF] Bongiovanni | The electric autonomous dial-a-ride problem[END_REF] presents the e-ADARP, a DARP variant which considers the use of electric autonomous vehicles, thus introducing battery management, charging stations, recharge times. The goal of the problem is to minimize a weighted objective function of vehicles total travel time and excess ride-time of the users. The authors propose a 3-index and a 2-index MILP formulations, along with a branch-and-cut algorithm with new valid inequalities. [START_REF] Brevet | A dial-a-ride problem using private vehicles and alternative nodes[END_REF] addresses the dial-a-ride problem (DARP) using private vehicles and alternative nodes (DARP-PV-AN), in which to achieve greater flexibility the on-demand transportation service can be done either by a public fleet or by clients that use their private vehicles. Several pickup/delivery nodes for the transportation requests are considered to address the resulting privacy concerns. A compact MILP model and an Evolutionary Local Search (ELS) algorithm are proposed.

Variations of Dial-a-Ride Problem

A common example in many countries is door-todoor transportation for the elderly or disabled persons (i.e. Paratransit [START_REF]Specialized Transit Eligibility Certification Programs[END_REF][START_REF] Cannon | Shaping National Disability Policy: Transportation Access and Social Security Reforms[END_REF]). [START_REF] Häll | The integrated dial-a-ride problem[END_REF] presents an integrated version of the DARP (IDARP), Some part of each journey can be carried out by a fixed route public transport service, without synchronizing time tables, which assumes the services are frequent. In many of the practical cases described by IDARP it is useful and reasonable to allow a request to end its journey on a transfer node near its drop-off node without taking another vehicle for the last leg (part) of the journey. Likewise, there may be cases where it is reasonable, from reducing costs and user-inconvenience points of view, to start the journey on a transfer node rather than on the original pick-up locations. This has lead the authors of [START_REF] Posada | The integrated diala-ride problem with timetabled fixed route service[END_REF] to propose the integrated dial-a-ride problem with timetables (IDARP-TT), in which, under some circumstances, requests may start or end the journey from/to transfer nodes sufficiently close to the pick-up or dropoff nodes without involving the vehicles in the first or last part of the journey. Each request has a given origin, destination, and demand for a set of resources, such as regular seats, wheelchair spaces, and baggage. A request can be served by a single vehicle or transferred between a demand-responsive vehicle and fixed routing system. A heterogeneous fleet of vehicles with different speeds, operating costs, and capacities is located in a depot and used to serve requests. The goal is to find vehicle routes that minimize the cost of service on demand and the cost of using the fixed routing system.

ODT Solution Methods and Approaches

Traditional approaches for ODT consider a centralized dispatcher architecture like in [START_REF] Egan | Market Mechanism Design for Profitable On-Demand Transport Services[END_REF][START_REF] Shen | Managing Autonomous Mobility on Demand Systems for Better Passenger Experience[END_REF] or a decentralized Multiagent System (MAS) to reduce problem complexity with a central coordinator like in [START_REF] Falou | On demand transport system's approach as a multi-agent planning problem[END_REF][START_REF] Grau | Agent based modeling for simulation of taxi services[END_REF]. There exist several approaches for decentralized decisions and self-coordination, like [START_REF] Glaschenko | Multi-Agent Real Time Scheduling System for Taxi Companies[END_REF] which introduce a multi-agent bid-based real-time scheduling solution in fully decentralized settings. Here each vehicle represented by an agent can negotiate via radio channels with flexible decision criteria. A pattern recognition algorithm is used to predict the most likely locations for the next demand using agent-based data mining to recommend movements to these locations.

Investigating the applicability of genetic programming (GP) for developing decentralized MAS that solve dynamic DARP, [START_REF] Van Lon | Evolutionary synthesis of multi-agent systems for dynamic dial-a-ride problems[END_REF] presents a method to automatically generate a MAS that can solve the DARP for a specific set of scenarios. GP is used to generate a heuristic that is effective in solving the DARP compared to centralized solutions. The best result achieved with this approach is by planning only one demand in advance by vehicle, which maximizes the agent's local interests (greedy) and produces a feasible solution very fast.

An agent-based model based on simulated events for the real taxi market was proposed by [START_REF] Grau | Agent Based Modelling for Simulating Taxi Services[END_REF], where supply and demand matching depends on event-based interactions. According to their conclusion, one of the main limitations is the assumption of uniform distribution of demand in the service area. To address the uncertainty caused by the dynamic nature of online demands, with ignoring the time required to execute a planning algorithm, [START_REF] Agatz | Dynamic ride-sharing: A simulation study in metro Atlanta[END_REF] proposed using a deterministic rolling horizon solution approach, in which plans are drawn up using all known information in a planning horizon, that is "rolled" forward to include more available information.

Based on vehicle coordination via message passing, and extending the generic model for Online Localized Resource Allocation (OLRA) [START_REF] Zargayouna | Generic model for resource allocation in transportation. Application to urban parking management[END_REF], using P2P communication, in our previous work [START_REF] Picard | Approches multiagents pour l'allocation de courses à une flotte de taxis autonomes[END_REF] we proposed the Online Localized with Communication Constraint Resource Allocation (OLC 2 RA) for concurrently solving the allocation problem over a fleet of autonomous taxis, in which a vehicle decide its next destination (scheduling only one demand in advance). On the contrary, ALMA decentralized heuristic proposed by [START_REF] Danassis | Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior[END_REF] is wholly decoupled and does not require direct communication between the participants. They demonstrate an upper bound of the speed of convergence which is polynomial to the desired quantity of resources and competing agents per resource; in the realistic case where the mentioned quantities are limited whatever the total number of agents/resources, the convergence time remains constant as the total size of the problem increases. However, in [START_REF] Danassis | Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior[END_REF] conflict detection still requires communication with other vehicles, resources, or a central entity to enable resources to share information about their status, such as the blackboard coordination mechanism.

So far and to the best of our knowledge, efforts done in ODT planning domain provide either optimized solutions ignoring the execution time, or provide very fast, just feasible solution to respond quickly to dynamic online demands. In this work, as the optimal solution for this dynamic problem is not achievable within reasonable computational time, our proposal combines the benefits of these approaches in one heuristic that provide a fast auction-based response (fast feasible solution), and this solution is gradually improved at run time with demand-exchange rescheduling.

AVFAP Model

The section expounds on the problem addressed in the remainder of the paper. The Autonomous Vehicle Fleet Allocation Problem (AVFAP) extends the traditional DARP by considering a fleet of autonomous vehicles that coordinate without a central dispatcher. The vehicles make decentralized decisions based on information exchanged via Peer-to-Peer (P2P) communication as illustrated in Figure 1.

The city map graph, shown in Figure 2, consists of nodes representing geographic locations and edges representing the road connections between these locations. A fleet of autonomous vehicles is distributed throughout the city. Each vehicle has a set of properties whose values are constant (capacity, cost, and average speed) or variable (location, schedule) because they are time-dependent. Passengers emit demands from different locations (which we will call sources later). Each one takes the form of a request that defines: the pick-up and delivery locations associated with the desired service time window. We define a solution as a schedule for each vehicle that meets the demands by satisfying their constraints, minimizing passenger waiting time, and minimizing vehicle travel costs.

The vehicles communicate by broadcast via an ad-hoc Vehicle-to-vehicle communication (V2V) network, where the communication range is limited. Each vehicle that receives new information broadcasts it again, and the vehicles are thus connected by transitivity within their communication range. In the rest of Fig. 2. A sample AVFAP city infrastructure this article, we use the term "connected set" to refer to a set of items (vehicles and sources) that can communicate with each other directly or by transitive message passing.

In this context, a vehicle is not aware of requests outside its connected set. The vehicle's belief evolves during the execution time, as the vehicle moves around, receives new requests from request sources, meets other vehicles, and exchanges messages with them. By using a low latency, fast connectivity communication mean like DSRC, we can ignore the time loss caused by the communication delay within connected sets

In the same direction of the work done in [START_REF] Picard | Approches multiagents pour l'allocation de courses à une flotte de taxis autonomes[END_REF], the AVFAP model is defined as:

AV FAP :=< M, V, D, T > M :=< G, w > V := {v 1 , v 2 , . . . , v n } D := {d 1 , d 2 , . . . , d m } T := {t 0 , t 1 , . . . , t end }
where M defines the urban infrastructure map (locations, roads, and distances); the offer is represented by a V fleet of n autonomous vehicles; D defines a dynamic set of passenger demands that occur at the time of execution, and T defines the time horizon within which vehicles must respond to passenger demands. We define time T as a discrete set of ticks.

Urban Infrastructure Map

The urban infrastructure map is defined by a weighted directed graph M, as shown in Figure 2. G is a directed connected graph where N is the set of nodes, E is the set of edges between nodes. The valuation function w associates each edge e with the value w e based on a measure of temporal distance (for example, average driving time in minutes), which will be used to calculate the operational costs of vehicle trips.

G :=< N, E > w := {w e1 , w e2 , . . . , w |E| }

Vehicle Properties

Each v ∈ V is defined by v :=< capa, cpd, range > and has a set of dynamic properties

v_location : V × T → N ∪ E f ree_seats : V × T → N +
Where capa defines the total number of passenger seats in the vehicle, cpd defines the vehicle's cost per unit of distance, and range defines the communication range within which the vehicle can communicate with other entities. At any given time t ∈ T a vehicle v ∈ V knows its current situation: v_location defines the location of v that could be located in a node or moving through an arc; and f ree_seats defines the number of free seats available in v at time t.

Demand Properties

A demand d ∈ D is defined as a request

d :=< required, tw, pick_up, drop_off >
where required is the number of seats required; tw defines a time interval [t min , t max ] in which the pickup event is considered acceptable; pick_up and drop_off are the origin and destination of the request, respectively. As for vehicles, at time t ∈ T , we will consider that a request d ∈ D can also be communicated using the V2V network. The request could be issued by the customer or the infrastructure (roadside unit).

Auction-based Insertion Heuristics in ORNinA

This section presents our new insertion heuristic, where vehicles coordinate through auctions. The main objective of vehicle agents is to provide feasible schedules that maximize their utility by minimizing the global operational cost of serving the maximum number of requests.

Given a vehicle v having a potential demand set D v , providing a schedule for v that satisfies all the requests d ∈ D v means solving a TSP to produce the best ordering of requests in the schedule. Considering the dynamic aspect of our model, we use an insertion heuristic like the one described in [START_REF] Solomon | Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[END_REF] to adapt local vehicle schedules continuously. The result of this algorithm is a set of requests; each of them is associated with the potential time at which a vehicle will be at the pickup location. The insertion heuristic is proven to be efficient in finding feasible schedules very fast [START_REF] Campbell | Efficient insertion heuristics for vehicle routing and scheduling problems[END_REF], but since it handles the scheduling of requests one by one, its performance is relative to the order of these demands.

In our model, the agents handle the request based on their priority order. An agent uses a priority function to assign priority values to the requests he knows. Given a vehicle v, the priority function returns for a demand d a value that is inversely proportional to the cost costDemand(d, v) of inserting the demand in the schedule of v:

1 costDemand(d,v) . Thus, the lower the cost, the higher the priority. The cost function returns the distance of d's pick-up location from v's location in its simplest form. Thus agents assign the highest priority to the request with the nearest pick-up location, wrt their current location.

Each agent determines his schedule to maximize the value of the quality of his solution. Since several vehicles may be interested in the same request, we need a coordination mechanism to resolve these conflicts. We will use an auction-based mechanism for this purpose, which is one of the effective and proven ways to solve such problems [START_REF] Cramton | An overview of combinatorial auctions[END_REF].

Auction Theory

Since ancient times, auctions have been used to answer the most fundamental questions in the Economy: who should get the goods and at what price? Therefore, auction theory is one of the most significant and widely studied topics in Economics. Some types of auctions are well known, such as the ascending-bid auction or the first-price auction used in many public markets. Auctions are distinguished not only by the terms and conditions of the auction but also by the environment in which they take place. These auctions can be studied in a wide range of characteristics of the auction environment, including the number of participants, the number of items traded, the parties' preferences, and the form of private information that participants have about their preferences.

A common aspect of auction forms is that they receive information, in the form of bids, from potential participants about their willingness to pay the price, and the result -i.e., who wins what and how much has to be paid-is determined exclusively based on the information received. This implies that auctions are universal in the sense that they can be used for many scenarios to determine winners [START_REF] Krishna | Introduction[END_REF], especially in resource allocation [START_REF] Chevaleyre | Issues in Multiagent Resource Allocation[END_REF][START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF].

Bid Criterion

In our model, we use a first-price auction form [START_REF] Krishna | Introduction[END_REF] to answer the question "which vehicle will consume the request and at what cost?". When a vehicle v becomes aware of a request d, it ranks it in its queue according to the priority it has assigned to it. At the time t, v selects the first request d s in the queue, generates a set of alternatives, each of which is a potential schedule resulting from the insertion of d s in a feasible step (that does not violate any of d s 's constraints) of the v's current schedule. Every alternative is associated with a cost, which is the marginal operational cost of adding this request to the schedule. The choice with the best cost is considered to broadcast an offer

Bid d v (t start , cost)
with t start the time of pick_up for d s .

In this paper, we consider the operational cost of trips as a linear relation to the routes' lengths, so that for a vehicle whose cpd = 1, the cost of a trip is simply the total length of its route (sum of the distances, as shown in Figure 2). We consider the value of cpd = 1 for every vehicle in the following examples. Therefore, the marginal cost of insertion is the difference in path length between the initial path and the new path.

Winner Determination

Given a set of bids B in a combinatorial auction on a set of resources R, the winner determination problem (WDP) is defined as finding an allocation of items to bidders that maximizes the auctioneer's revenue [START_REF] Lehmann | The Winner Determination Problem[END_REF].

The WDP is known as a NP-Hard problem because each subset of bids would have to be checked for feasibility and the revenue that this subset of bids provides.

In its simple form, when the auction is about a single, indivisible resource ∇ ∈ R, the question becomes, "to whom ∇ should be allocated?", which can be expressed as a linear relation:

winner : R → B ∪ φ
Seeking decentralization, we considered a binary version of this relation corresponding to our problem

win : V × D → {0, 1}
where the bidders are the vehicles and the resource items are the requests. We assume all agents to be truthful collaborating agents so that every vehicle v ∈ V that is aware of a request d is responsible for determining the value of win(v, d). The default value for win(v, d) is 0. After their announcement, the bids remain available for a specific time period t expire . Until t expire the vehicle listen to other vehicles' bids on d, if it receive a better offer, it assigns the value 0 to win(v, d) which means it determines itself as a looser and withdraw from the auction. On t expire if the bid cost of v is less than any other bid Bid d v received at t Bid d v + t expire to serve a request d, v considers itself the winner of the auction (i.e. assigns 1 to win(v, d)), and updates its schedule with the new bid path. This mechanism implies that on t expire of each auction d is allocated to at most one vehicle (in the connected set). V2 (t 10 , 13). V 1 is considered a winner and adds d 1 to its schedule, so that the overall operational cost of the fleet is now 11.

Limitations in Dynamic Settings

The problem at hand is considered as dynamic in both spatial and temporal dimensions. On the one hand in the temporal dimension, the requests are not known in advance but announced in a stochastic manner at run-time. On the other hand, the vehicle's knowledge is also limited to the information received and shared in its neighborhood through its connected set. This implies the dynamics in spatial dimension as the vehicle location affects the context of the problem. This dynamics may affect the quality of upcoming planning decisions dramatically and reduces benefits of the already taken long-term planning decisions [START_REF] Van Lon | Evolutionary synthesis of multi-agent systems for dynamic dial-a-ride problems[END_REF] similar to the situation shown in the following example.

Example 2. Figure 4 shows a situation where the use of the bid-based insertion heuristic is very reactive but does not guarantee good scheduling. At the moment t 2 when the new request d 2 :< 1, (t 15 , t 40 ), J, K > arrives, both vehicles are aware of it and place their possible bids. In the absence of any exchange capacity, V 1 still To be able to make effective bids for new requests or improve the solution, we also propose that the vehicles exchange their planned requests, as illustrated in Example 2.

Online Solution Improvement in ONRInA

In the following, we propose a local optimization protocol to improve the quality of the solution for cases like Figure 4.

This protocol is based mainly on the k-exchange neighborhoods (k-opt), a path improvement algorithm, where at each planning phase, k steps from the current plan are replaced by k steps to get a cheaper path [START_REF] Helsgaun | General k-opt submoves for the Lin-Kernighan TSP heuristic[END_REF]. In its simplest settings, k is set to 1, so the k-opt becomes 1-opt, which means a vehicle can exchange at most one demand at a time. In this work, we seek the implementation of the simple auction mechanism 1-opt to avoid dealing with the NP-complete winner determination of the k-opt combinatorial auctions.

Example 3. Let's consider another case shown in Figure 6, where V 1 has d 1 in its schedule, V 2 has is the winner and V 1 takes the charge of both demands with global cost +15, while the optimal solution in this case is that V 2 who takes both demands which make the global cost only +13, but using the auctions with abandon strategies lets V 2 in this case either bid for d alone when it is announced, or bid for d 1 alone in response of the abandon suggestion by V 1 . So in this case, the optimal solution is not achievable with the aforementioned abandon strategies.

Pull-demand Optimization Bids

Similar to the rolling horizon strategy of [START_REF] Agatz | Dynamic ride-sharing: A simulation study in metro Atlanta[END_REF], we propose an optimization protocol to improve our heuristics. In the rolling horizon strategy, all vehicle schedules are considered temporary and available to be scheduled by any vehicle, unless they are considered as committed requests by particular events; for example, v has started serving (moving towards) d, whose remaining time to serve it is below the horizon threshold.

The application of this strategy requires that all vehicle schedules are in shared memory, so that when a vehicle v i offers to serve a request d, it knows if it is scheduled by another vehicle v j , and therefore if it should send its offer cost to v j . Then v j will calculate

Protocol 1 Pull-demand Optimization Protocol

Step 1 A set of new demands enters the system based on announcement time order.

Step 2 Each new request is distributed to the connected set to which the sources belong. Each agent in this set can select his potential requests from requests that include new requests, scheduled and unscheduled requests that have not yet reached their scheduled departure time.

Step 3 The agents enter the auction to serve their potential demands in similar auction criteria (i.e. for each agent in the connected set, the potential requests are chosen and ordered in a list of candidates based on the same priority function, and the same cost function) of the initial phase.

Step 4 Each agent searches among its scheduled requests for the one to satisfy the next tick; this request is called dnext. If dnext exists, the agent broadcasts a "clear_demand" message to inform other agents that it handles dnext. Each receiver deletes it from their potential and known sets of requests. In addition, each agent deletes any other requests that reach their time window upper-bound because staying any longer available for rescheduling would violate their time constraints.

Step 5 The scheduled and unscheduled requests that still have time remain announced by their sources ( Step2). This allows better planning in the next tick if new requests are announced or some new agents join the connected set.

its estimation to the global gain (or loss) in operating cost by abandoning d compared to the cost proposed by v i . If there is a gain, it agrees to abandon d and then v i updates its schedule with d, otherwise the bid is rejected.

In our protocol, we do not use the concept of committed request, but a vehicle can only bid on requests that it can satisfy, so requests that are rescheduled or that do not have enough time to be rescheduled are automatically ignored by the agent. Another difference here is that we don't have a shared memory. Agents exchange information about the context of the environment and about requests through information messages. Moreover, in [START_REF] Agatz | Dynamic ride-sharing: A simulation study in metro Atlanta[END_REF], optimization is performed periodically at a predefined frequency, while the protocol we propose is executed in parallel with the auction-based insertion strategy to have a fast rescheduling for continuous requests. Based on shared information of the current context, the optimization protocol is executed between connected sets of vehicles when any change in this set context is detected (the set of vehicles in the connected set is changed or at least one of them is newly aware of some requests which are already scheduled by others). Protocol 1 details this strategy.

Discussion

Given the decentralized context, the insertion heuristic is very efficient in terms of response time. The temporal complexity of the basic insertion heuristic for the Vehicle Routing Problem (VRP) is of O(n 3 ) [START_REF] Campbell | Efficient insertion heuristics for vehicle routing and scheduling problems[END_REF]. This type of heuristic is often used to solve DARPs, where new incoming requests have to be continuously processed in real-time and integrated into the evolving schedules of vehicles. The usage of k-opt may add local improvements to the insertion heuristic solution based on the current context. However, the Pulldemand protocol can significantly improve the quality of the solution, as illustrated in the following example.

Example 4. Let's consider another case illustrated in Figure 6, where V 1 has d 1 in its schedule, V 2 has an empty schedule, and a new request d :< (t 10 , t 20 ), D, F > is announced. The bids of the vehicles are thus Bid d V1 (t 12 , +4), and Bid d V2 (t 10 , +13). It is obvious that Bid d1,d V1 is the winner, and V 1 will handle the two requests with an overall cost of 15. With the Pulldemand protocol, d 1 and d enters in the set of candidate requests for V 1 and V 2 , so that the vehicles can make combinatorial offers: Bid d1,d V1 ((t 10 , t 12 ), 0) and Bid d ,d1

V2 (-2). The cost of V 2 is 13 and the gain of V 1 is 15). V 1 has nothing to change in its schedule. V 2 wins and the solution is improved with an additional optimization round. Let's look at the applied protocol, step by step.

Step 1: d enters the system at t 2 and both vehicles are aware of this, V 1 wins the auction with an overall cost of 15 Step 2: d 1 and d are now in the set of requests known by both vehicles, V 2 calculates the costs to serve d 1 alone (13), d alone ( 9) and both requests together making 13. It then selects the two requests as its potential requests. V 1 has no potential request because it already has the two requests in its schedule.

Step 3: V 2 places a bid Pull_Bid d ,d1

V2 ((t 10 , t 12 ), 13). For V 1 the cost to serve both requests is 15 so it accepts Pull_Bid d ,d1 V2 because it causes a gain of 2.

Step 4: None of the requests reach their scheduled service time or the upper-bound of their time window.

Step 5: All known requests remain announced and available for the next potential improvement.

Experimental Evaluation

In this section, we experimentally evaluate the performance of our contributed ORNInA approach, using synthetic data and Open Street Map information.

Experimental Setup

The city map of Saint-Étienne was chosen for the simulation. The structure of the graph G =< N, E > including nodes, edges and a set of sources of the S ⊂ N request is extracted from OpenStreetMap (OSM1 ) and post-processed by Plateforme Territoire2 . In all the experiments, we set the number of sources |S | = 40, having a set E S ⊂ E of edges, such that |E S | = 71 connecting the sources, each edge has a number of points which varies according to its length and the information extracted from OSM. The distance between two consecutive points is 40 meters. We used a discretetime transport simulator available in the Plateforme Territoire to evaluate the proposed strategy and analyze it in terms of quality of service and gain. The Java-based ORNInA and IBM ILOG CPLEX Optimizer Version 12.9.0 have been executed on an octacore Intel® Core™ i7-8650U CPU @ 1.90GHz, with 32GB DDR4 RAM.

A fleet V of n vehicles is distributed randomly through S at the beginning of execution. Each vehicle v ∈ V moves from one point to another on the same edge during each simulation cycle. In our test, we consider that vehicles communicate via DSRC with a realistic communication range of 250m so that a vehicle can send/receive messages to/from other entities located in its range. Each vehicle v can adopt two distinct travel behaviors: either marauding for requests or going to a destination:

• going_to defines the state of a vehicle when it has a specific destination, i.e. a request to serve. The vehicle is either going_to pickup location if the request is not yet picked up, or going_to delivery location otherwise. • marauding defines the state of a vehicle when it does not have a request to serve, i.e., at the beginning of the simulation, each vehicle marauds until it decides to serve a request. Once a passenger is dropped off, the vehicle reverts to marauding. In this state, the vehicle randomly moves through its neighborhood to find requests to serve.

At each simulation cycle, 0, 1 or 2 requests are generated in a uniform random manner. For each request, the origin and destination points are randomly and uniformly generated from all sources. The time window for the requests is generated using two constant parameters l and u for the lower and upper limits as follows [tw min , tw max ] is initialized with two uniform random values where : tw min < tw max tw min t actual + l tw max tw min + u

The evaluation criteria for these simulations are mainly the number of requests satisfied as a measure of Quality of Service (QoS), the simulated profit of the solution as a measure of Quality of Business (QoB). The profit is calculated in terms of the difference between the simulated travel price and the cost. where total_distance(v) is the total traveled distances by v including marauding and going_to distances.

In real-life scenarios, the pricing criteria is more complex and depend on many other factors, here we provide an approximate pricing model based only on distance. In our tests, we consider the vehicles identical in terms of cpd(•) travel cost and p pricing factor. We set P = 1.5, p = 2 and cpd(v) = 1 for all v, so that the vehicle will gain 1.5 money-unit per satisfied request in addition to 2 money-unit per traveled distance-unit with passenger on-board, while it looses 1 money-unit per traveled distance-unit. A successfully traveled distance with passenger on-board leads to a net gain of 1 money unit.

Maximizing the income requires maximizing the number of satisfied requests and the riding distance, while to reduce the costs, the vehicles need to reduce the empty driving slots in their trip schedules. In this notion, we can define the allocation process's objective as maximizing the QoB function pro f it.

To assess the feasibility of the ORNInA heuristic, we compare it to two other approaches: GREEDY: a decentralized approach based on planning a single request in advance. This approach has been mentioned by [START_REF] Van Lon | Evolutionary synthesis of multi-agent systems for dynamic dial-a-ride problems[END_REF] as the best strategies for dynamic settings, following genetic algorithm selection. CPLEX: building vehicle schedules dynamically by a central dispatcher that uses CPLEX solver to solve the allocation problems as MILP which maximize the objective function pro f it. The central dispatcher calculates a solution in response to a query from a connected set.

The two decentralized approaches use the same request selection strategy (request priority function that is derived from the objective function) during each scenario. Being optimal, the CPLEX approach is reported as an upper-bound for the solution quality, regardless of its computational time and practical applicability.

Experimental Results

The results presented in the Figures 7 and8 concern a scenario in which vehicles select the cheapest request considering the costDemand(d, v) is the marginal cost mentioned in Section 4; the same applies to the greedy algorithm since the vehicle schedule can only contain one demand. We have executed several instances of problems that vary with the size of the fleet n. Each instance of these tests is executed 10 times with different probability seeds. First, we evaluate with a fixed fleet size n = 20 to track the quality of the solution over time, then with a variable fleet size n ∈ [3..35] over 300 cycles for each scenario. The global quality of solutions obtained by the CPLEX solver depends on two factors: To achieve a global solution that is optimal (or very close to optimal) in this dynamic settings, the solver must be queried at each simulation cycle for each connected set to consider the new announced requests. This is not feasible in practice because of the computational complexity of the problem but still provides offline bounds on the solution. This strategy is coined CPLEX_R in the figures. In our experiments, we examined, in addition, another strategy in which the CPLEX solver is queried each time a connected set member changes in order to obtain an optimal solution for the sub-problem defined by the context of the connected set. This solution is still valid as an optimal decision until the context is changed. This strategy is coined CPLEX_CS in the figures. The results obtained by the first strategy (CPLEX_R) represent an upper-bound for the objective function (QoB) as the CPLEX solver is queried to calculate the optimal solution in the highest possible frequency (i.e., every time a new request is announced). Usually, the vehicles move and change their connected sets frequently, which means even the second strategy (CPLEX_CS), can keep the schedules mostly up-to-date. However, on the one hand in some scenarios with few vehicles in a wild map, vehicles may be far away from each other, so they do not belong to any connected set, and their knowledge about requests is limited. On the other hand, with more vehicles, the connectivity between vehicles increases, leading to some point where all vehicles are stably connected, e.g., all vehicles belong to a unique connected set that does not change. In such a case, the CPLEX solver is never queried with the CPLEX_CS for a while until a vehicle leaves the connected set. These two cases explain why in the medium fleet sizes, the results from CPLEX_CS are close to the upper-bound obtained by CPLEX_R, as the connected sets change more frequently and so the rescheduling. Note that it is impossible to achieve a 100% QoS rate in these scenarios since there will always be requests that will be generated until the last cycle, assuming that the scenario execution continues to serve them, while the execution stops at the last cycle, leaving them unserved.

With a low number of vehicles, the connected sets are small and, as a consequence, the amount of shared information is reduced so that there are no quality discrepancies between the compared approaches. With larger fleet sizes, more information is shared in the connected sets. Additionally, vehicles switch from one connected set to another more frequently. Although QoS values of our algorithm are close to those obtained by the greedy approach, they remain slightly ahead of them, and to achieve the same values of QoS with no coordination, more vehicles in the fleet are required, as shown in Figure 9.

Starting from small fleet of 3 vehicles, the ORNInA heuristic allows obtaining solutions with the same QoS We find that the increase in these values for the ORNInA heuristic is more significant than that of the greedy approach. This can be explained by the fact that demand planning improves the system profit in the foreseeable future, as it reduces the process of roaming without a specific destination until a new demand is chosen, which is the behavior of the vehicles in the greedy algorithm.

The value of QoS continues to grow as the fleet size increases until it reaches a n QoS threshold where the addition of new vehicles becomes unnecessary, as all requests received in the system now or in the future (except those received in the last moments of execution) can be served with the current fleet size. The same is true for QoB, but the difference here is that the vehicles added will result in additional operational expenses, resulting in a loss of profit value after reaching

QoB

. This gives a broader range of options for combining the enhancements of the provided solution (QoS and QoB). Figure 11 particularly demonstrates how GREEDY has an abysmal performance when looking at both QoS and QoB (and their ratio), while the other allocation mechanisms remain in the same group, completing both qualities, but at different levels.

In the three compared approaches, every simulation cycle, agents in a connected set of size n that are aware of m requests exchange info messages. In addition, agents in ORNInA approach exchange bid and pull messages, while in the centralized CPLEX approach, agents send queries and receive schedules in answer from the solver. Table 1 shows statistics about the exchanged messages by the three approaches in these experiments. In GREEDY, agents exchange the minimal number and size of messages that contain the essential information about known requests and the contexts of connected sets. Each agent may receive up to one message from each other member of its connected set.

The size of a query message to the CPLEX solver depends on the sub-problem instance size. In our experiments, the largest sub-problem instance was 10 vehicles and 22 requests; this instance's query message reached the size of 2.5 kB. In ORNInA, the bid and pull messages and their answers are of small size, but the message count is higher.

The above results show that in all cases, and in the condition of updating schedules frequently, scheduling several requests in advance (like ORNInA and CPLEX) gives better results than scheduling a single request with a GREEDY approach.

In practice, the dynamic aspect of the problems requires frequent and real-time computation of sched-

Conclusion

In this paper, we proposed ORNInA, a decentralized coordination mechanism for the exchange of requests, based on an insertion heuristic and auctions, to allocate requests to vehicles in the context of dynamic on-demand transport with V2V communication. We model this allocation problem with connectivity constraints as the AVFAP, which extends traditional DARP.

We show through examples that the request exchange protocol can be a promising improvement in the quality of the solutions. To assess the feasibility of the proposed protocol, we evaluated our technique's results on synthetic data for taxis operating in the city of Saint-Étienne and showed that it outperforms a classical greedy approach. Moreover, compared to classical centralized MILP-based solvers (computing the optimal allocation either at each simulation step or at each connected set update), ORNInA provides very good quality results on both QoB and QoS while following fully decentralized decision making.

In future work, we plan to have more evaluation on the efficiency, performance, robustness, and optimality of this heuristic with respect to different approaches, like distributed constraint optimization, by simulating different parameters on information distribution, decision criteria, and different levels of problem dynamics. Finally, to assess the scalability of such decentralized approaches, we plan to simulate larger cities and fleets, based on real on-demand transport dataset, like the NYC-TLC open dataset 3 or an adaptation of the Li and Lim benchmark4 to AVFAP.

Fig. 1 .

 1 Fig. 1. A sample AVFAP problem instance, with demand sources (triangles) and taxis (circles) with their respective communication ranges (in blue).

4 Fig. 3 .

 43 Fig. 3. V 1 wins the auction to serve d 1 from C to H

Fig. 4 . 1 Example 1 .

 411 Fig. 4. With no demand exchange, V 2 wins d 2 and V 1 keeps d 1 Example 1. The simple scenario in Figure 3 shows two vehicles V 1 and V 2 located in A and B, with empty schedules at the beginning. At time t 1 , the first request is announced d 1 :< 1, (t 10 , t 20 ), C, H >. Both vehicles now know d 1 . V 1 can serve it by following the path A → C → E → F → H, so V 1 places the offer Bid d1 V1 (t 10 , 11). V 2 can serve it via the path B → D → C → E → F → H, so issues the offer Bid d1V2 (t 10 , 13). V 1 is considered a winner and adds d 1 to its schedule, so that the overall operational cost of the fleet is now 11.

Fig. 5 .

 5 Fig. 5. Global improvement when V 1 abandons d 1 to serve d 2 has d 1 in its schedule (with an initial cost of 11), so the best offer it can place is to serve both requests with a marginal cost of 14. While V 2 places the winning bid Bid d2 V2 (t 15 , 11), it adds d 2 to its schedule, and the overall cost becomes 22. Note that in this case, serving d 2 with V 1 and letting V 2 take care of d 1 (as shown in Figure 5) results in an overall gain of global operational cost which becomes 21, but this solution is never realized because d 1 is already scheduled on V 1 .

Fig. 6 .

 6 Fig. 6. While it can serve both demands, V 2 can only bid for one demand at a time empty schedule, and a new demand is announced d :< (t 10 , t 20 ), D, F >. V 1 offers two alternative bids Bid d1,d V1 ((t 10 , t 12 ), +4), and Bid d V1 (t 10 , +15)(taking into account abandoning d 1 ) , while V 2 can only offer Bid d V2 (t 10 , +13). Obviously Bid d1,d V1

  pro f it = total_income -total_cost where total_income = d∈Ds P + p * distance(d) D s ⊆ D is the set of all satisfied requests, P is a fixed price (service fee) per request, p is a pricing factor per unit of distance travelled, distance(d) is the total travel distance for a request d and total_cost = v∈V cpd(v) * total_distance(v)

Fig. 7 .Fig. 8 .

 78 Fig. 7. Quality of service for a fleet of 20 vehicles

Fig. 9 .

 9 Fig. 9. Quality of Service with increasing fleet size

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Quality of Business with increasing fleet size

  the CPLEX central dispatcher approach because of the NP-Hard complexity of the problem. However, ORNInA provides a good combination of quality and feasibility of the solution with its reduced computation time and no global information sharing.

Table 1

 1 Exchanged messages per simulation cycle QoB growth threshold. In general, n QoB is less than n QoS , and we can see a trade-off between improving QoS or QoB. According to the Figure 10, we see that the greedy fleet has n GREEDY QoB = 12 with a QoS of only about 60% compared to n ORNInA QoB = 16 with a QoS of about 70%, while the highest value of QoB in these experiments is about 80% with n CPLEX

	Approach	Count	Avg size (Bytes) Max size (Bytes)
	GREEDY	O(n)		88	140
	CPLEX		O(2n)		163	2500
	ORNInA		O(n * m)	112	140
	its n QoB	= 18 . Note that
	n GREEDY QoB	< n ORNInA QoB	and even if it decreases afterwards,
	the value of n ORNInA QoB	remains higher than n GREEDY

https://www.openstreetmap.org/

https://territoire.emse.fr/

https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page

https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/

Acknowledgements

We would like to warmly thank Fabien Badeig from Institut Henri Fayol for his technical support in realizing the experiments of this work, within the Plateforme Territoire.