Philippe Lacomme
email: placomme@isima.fr

Gwénaël Rault

Marc Sevaux
email: marc.sevaux@univ-ubs.fr

Integrated Decision Support System for Rich Vehicle Routing Problems

Keywords: Supply Chain, Transportation System, REST API, Rich VRP

Recent economic and environmental constraints push supply chain management systems to adopt closed-loop supply chain operating modes that have to address very complex problems including the end-user quality of services, environmental considerations, and daily transportation time variations. Relevant and challenging research areas require a proper coordination between the data provider software (Transport Management Software) and the operational research tool in charge of trip definition.

This paper proposes a decision support system applied to the Vehicle Routing Problem able to tackle very large instances with real-life constraints. Our contribution is to propose an architecture that handle both static resolution prior to the completion of routes and update them in a dynamical context during their completions. This is implemented through a REST based API using numerous state-of-the-art operational research methods. Moreover, this system in used in practice by the Mapotempo company.

Introduction

Recent economic and environmental constraints increase the pressure on the supply chain management systems to integrate multi-attribute decisions both for the last mile and closed-loop of the supply chain [START_REF] Cardenas | City logistics, urban goods distribution and last mile delivery and collection[END_REF][START_REF] Macharis | City distribution and urban freight transport : multiple perspectives[END_REF]. Due to the wide development of e-commerce, and 5 the quick growth of online retailers [START_REF] Chen | Performance Impacts of Web-Enabled Retail Services: An Empirical Study[END_REF] the demand has been fragmented. Previously the supply activities were performed in shopping centers or within few shops, with only few contacts with the final user. Nowadays, every house, office or shop is a potential point of interaction between the supply chain and the customer. The last mile is about delivering goods provided by the whole supply chain to specific customers, where the closed-loop, is more about taking back products from customers to recover additional value from the product itself or some of its components. The objectives of the supply chain model can include profit maximization, environmental impact customer quality of service. This is placed in a dynamic urban environment with transportation conditions which variate from day to day and along the day. The road network may change, and traffic jams may appear. This requires most of the time robust solutions or dynamic systems to update iteratively a solution. Decision making of the supplier and manufacturer in a supply chain management to tackle these real-world situations require efficient Operations Research (OR) tools dedicated to the Vehicle Routing Problem (VRP) [START_REF] Toth | Vehicle routing : problems, methods, and applications[END_REF] to obtain an efficient solution regarding model objective. These tools can be based on numerous exact methods, heuristics, or meta-heuristics depending by the size of the instances, which exhibit the complexity of the problem, and the end-user constraint on computational time.

The future of transportation depends on several relevant and challenging research areas that are impacted by 1) environmental constraints, 2) digitization of the services, and of 3) new modes of transport more connected due to the service digitization. The research community needs to collaborate with practitioners to efficiently manage the global transportation that requires a proper coordination between the data provider software (Transport Management Software) and the Operational Research tool in charge of trip definition addressing the whole constraints. This paper presents an original contribution by making easily reachable OR resolution methods for the VRP and its variants for software engineers through a high level API which handles an entire problem and selects by itself the best suited methods to solve it. Moreover, some low level APIs are available giving access to the set of data necessary to solve such problems and allow the user to interact with the data and the solution and to display these on a map. This work is motivated by the specific needs in the last mile of the supply chain. It requires fine data to be relevant in such dynamic context. The traffic and the position of vehicles evolve all along the day. Missions to perform may change during the realization of tours. This is particularly the case in the dynamic or multi period variants of the VRP.

The OR methods embedded within the system are selected both for their flexibility and fastness. Evolving in a dynamic context requires to be able to start from an existing state and give limits in the neighborhood which can be reached through the resolution. It may not be feasible to entirely change the route of a driver while he is already performing his tour. The dynamic context of city logistic requires robust solutions in order to keep an high level customer satisfaction.

The proposed decision support systems introduce low-level systems such as Geocoder and Router services which give basic bricks used by others systems, respectively to convert addresses into coordinates and provide data about the path between points. Some high-level systems as Optimizer and Fleet services give access to more advanced features. A Web App is as well available to display an overview of the capabilities provided by the combination of whole services.

The architecture is scalable, each service can be replicated and eventually implements mechanism to delegate operations to other machines.

The system is expected to propose good and robust solutions in a very short amount of time fitted to the dynamic environment of the city logistic. This paper is organized following the next structure. Section 2 will provide an overview of the evolutions in the OR research field to solve the VRP and its variants. Section 3 introduce the concept of Application Programming Interface (API). The following Section 4 propose an application of the API to the problematic of the Decision Support System applied to the last mile. Section 5 provides a particular focus on the implementation of Optimizer-API using the Representational State Transfer (REST) standard. Section 7 will provide a comparison of the Optimizer-API against the alternative available on the market in term of capability. Then a benchmark on various instances of the literature will be presented. Some particular points of the paper will be discussed in Section 8. Finally, Section 9 presents concluding remarks and provide some future perspective to this work.

Related work

More than 60 years have elapsed since [START_REF] Dantzig | The truck dispatching problem[END_REF] have introduced the VRP and open a new research field for the operation researchers.

The community have been largely inspired by the need of the supply chain, this can be shown through the number of variants addressed. This emulation has create a large basis of instance sets on which the community can rely on to compare the efficiency of the resolution methods. Among others we can mention the work of [START_REF] Solomon | Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[END_REF] and [START_REF] Gehring | A Parallel Hybrid Evolutionary Metaheuristic for the Vehicle Routing Problem with Time Windows[END_REF] on the VRP with Time Windows (VRPTW). [START_REF] Cordeau | A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems[END_REF] has introduced various instances on the Multi-Depot VRP (MDVRP) and the Periodic VRP (PVRP).

And lately add the Time Windows attributes to theses variants MDVRPTW and PVRPTW (Cordeau & Laporte, 2001). The combination of attributes expresses the need of the community to get closer of the reality. [START_REF] Duhamel | Efficient frameworks for greedy split and new depth first search split procedures for routing problems[END_REF] in this trend have introduce instances for the Heterogeneous Fleet VRP (HFVRP) where distance matrices were calculated using the road network instead of traditional measures such as euclidean and Manhattan distance. On another side, as the methods became more refined and their performances have improved, the size of the problems which could be handled increases. This has lead the community to update the classical instances to increase their size such as Vidal et al. (2013a) on the MDVRPTW, PVRPTW and Site Dependent VRP (SDVRP).

In the same time, as the contribution to new variants have been shared. A need of classification of the different attributes has been expressed [START_REF] Vidal | Heuristics for multi-attribute vehicle routing problems: A survey and synthesis[END_REF][START_REF] Caceres-Cruz | Rich vehicle routing problem: Survey[END_REF] with the idea of exploring which combinations were already explored, which were the current trends and which were the unknown land. Some recent contributions have rushed down this path. That is the case of [START_REF] Penna | A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet[END_REF]. They have added various attributes to he HFVRP and provide an hybrid heuristic able to solve efficiently rich variants of the HFVRP. More recently [START_REF] Sadykov | A Bucket Graph-Based Labeling Algorithm with Application to Vehicle Routing[END_REF] have proposed an exact method based on bucket graph labeling algorithm able to solve a large set of variants of the VRP.

As a regard to the need to challenge even more the resolution methods with instances of bigger size [START_REF] Arnold | Efficiently Solving Very Large Scale Routing Problems[END_REF] provide both instances of large scale for the Capacitated VRP (CVRP), up to 12000 nodes to serve and an efficient heuristic to solve these. Even if the field is highly active both on the research and the industrial fields, the contribution in the creation of commercial plateforms are rarely shared with the community. The only previous contribution we have found comes from [START_REF] Welch | Dynamic vehicle routing problems appear in a number of 945 industries[END_REF]

Web API definition

The first developments of distributed environments for optimization took place in the 1990s, and were based on a client-server architecture that allowed end-users to submit problems and receive solutions using protocols including FTP (File Transfer Protocol), SMTP (Simple Mail Transfer Protocol), and even on the lowest protocols TCP-IP (Transmission Control Protocol (TCP) and Internet Protocol (IP)). This first generation of servers rapidly evolved to take advantage of the power of expression offered by the new protocols developed for the World Wide Web (WWW).

Web-based technologies have transformed the design, development, implementation and deployment of decision support systems. As stressed by [START_REF] Cohen | Decision support with Web-enabled software[END_REF] with the definition of web-based decision support systems in Supply Chain Management. The interconnection of modules in the business process models [START_REF] Wang | Guidelines for Business Rule Modeling Decisions[END_REF] of the Supply Chain Management is based on application programming interfaces (API) that define a set of procedure and methods that can be executed by a module through an internet connection. It can be written into any programming language that manages internet access using TCP-IP. Those interfaces are called remotely through internet protocols and allow them to build applications with distant services on servers. Such APIs are designed to provide specific data or services in order to delegate parts of much larger applications. They give access to black-boxes on which developers can rely on to provide an expected behavior. Managing data and performing complex tasks are often involved to specialized entities as it requires otherwise to have developers with appropriate skills or to have access to large volume of data to feed such systems.

APIs are one way to implement the Service-Oriented Architecture (SOA) paradigm and are designed to tackle the problem of integration of heterogeneous sources and to make heterogeneous systems inter-operable. A key to design such API is how requests are processed on the server side (processing model) and how clients invoke and use this service (interaction model).

An API service processing model may be business object (or method) centric or it may be document centric.

the business object-centric approach is driven by a series of method calls. These successive method calls apply the business logic of the service to a set of business objects hold by the API and containing the information required for processing the requests. a document-centric API keeps the business logic separates from the document content. The service receives a document that only contains data and no explicit binding to the business logic that has to be applied. There is no mapping of the request to the business logic; that is, specific methods are not invoked by the client. The processing workflow is deducted from the document content. Despite the effort of numerous studies in recommending adequate API structure, several relevant shortcomings can be disputed including but not limited to the following remarks: most of the service recommendation approaches focus on recommending services in isolation to obtain an availability rank that matches the customer requirement [START_REF] Almarimi | Web service API recommendation for automated mashup creation using multi-objective evolutionary search[END_REF].

the confidentiality becomes more challenging especially with the increasing number of available services interconnected. And even more, regarding the GDPR. a reasonable access across the service users depending on the usage in the services ecosystem and on the commercial usage contract that provide equity between customers. avoid unfair API usage pattern which is a sequence of method calls which are not compliant with the end-user user permissions define synchronous and asynchronous abstraction layer with a service composition that has to be proved to be correct and complete. Specific techniques for planning execution and allowing the combination of asynchronous services according to behavioral requirements have been provided [START_REF] Zhao | Building asynchronous geospatial processing workflows with web services[END_REF].

The current trend for Web Services is to rely on various services available through the network. It relies on the Service-Oriented Computing (SOC) paradigm and supports the development of rapid, low-cost, inter-operable, evolvable, and massively distributed systems. The promise of SOC is to easily assemble loosely coupled micro-services to build dynamic business processes [START_REF] Papazoglou | Service-Oriented Computing: State of the Art and Research Challenges[END_REF][START_REF] Karakoc | Composing semantic Web services under constraints[END_REF]. It comes with another important fundamental concept, which is quality of service (QoS). It is used to drive the selection of candidate service through the evaluation of various attributes [START_REF] Parejo | QoS-aware web services composition using GRASP with Path Relinking[END_REF][START_REF] Ramírez | Evolutionary composition of QoS-aware web services: A many-objective per-spective[END_REF] : cost, availability, response time, reliability, security, latency, documentation.

Definition of the Mapotempo Transportation System

Decision support systems (DSS) are information systems that provide assistance to humans involved in complex decision-making processes. Unlike online retail services, the supply chain management requires, especially in its last mile part, to consider various sources of change in the plan. As the situation on the field may evolve quickly it has to consider many feedback loops at every step of the decision process. Even if a first plan could be defined from scratch, it should anticipate the traffic state to return a sufficiently robust solution.

The vehicle fleet may be heterogeneous in term of physical vehicle, which influence the road network that can be traveled through. It influences also the travel speed, that could also variate from one driver to another due to their experience or their behavior on the road. The time spend at customer's site may variate from one route to another has it depends on the type of vehicle. A truck has more difficulties to find parking places, it is also longer to open the trailer or take out the parcels. The time spend at customer's site also depend on the driver and the politic of quality of service set up by the company. These parameters are usually known in advance.

Some parameters are fixed in advance, it is often the case in the press portage, the routes are defined in advance and send to subcontractors as it.

But to improve the margin of such routes external newspaper clippings are introduced to the existing route if they do not improve the total cost of the route and generate no detours.

Furthermore, once a plan has been established it may be hard to change it entirely. At this step, searching an optimal solution is irrelevant, the need is to find a solution of good quality with a small "distance" to the existing one.

That is particularly true when the shiploads are prepared in advance to ease the load of the trucks when the drivers arrive to the loading docks. It may also be difficult to dismiss a driver because his route has been dispatched through multiple other routes. Whenever the route has begun, some missions may be assigned to other drivers, if it doesn't depend on the shipload, due to event on the route.

Such DSS must provide an adapted solution from the current state of one or multiple routes with various levels of preservation of the previous solution.

The modules that operate in this context must consider these constraints, states, priority and preferences. The tools at the disposal of the operator should give him correct feedback on the progress of the plan. The route manager may have to adjust the solution or deploy it to its vehicle fleet directly on the field. Moreover, the web services are divided in two main layers. The front end assembles all the methods available to computer science engineers who come into direct contact with the various functional bricks. The back end is a structured collection of modules which are dedicated to specific goals to create additional values from the routing data.

The MTS is compartmentalized. Every main functional block is self-contained. Thus, every service may evolve independently from the rest of the global project.

The client, here the Web rely on the services behind and contact them whenever it requires a specific action on the data. Each service implements a set of methods exposed through its API as a set of resources. These have been summa-

Geocoder

Mailing addresses are usually provided as a text split in multiple fields such as a street, a zip code, and a city. But such addresses could be of poor quality or containing exotic data. The geocoder service has to interpret this information, to find the best source of data which could convert it into coordinates, to evaluate the quality of this data and eventually interrogate another source of data.

Mailing address standards change from one country to another and even sometimes from one region to another, mainly because of the syntax construction of the official language of the given locality. Some countries or newly constructed boroughs may not have proper addresses.

Another feature is to translate coordinates into mailing address and is commonly called reverse geocoding. Both of these operations are performed synchronously.

Router

The last mile part of the supply chain belongs to a dense environment with many regulation rules on the road network. Various means of transportation operate in this context with rules varying from one business field to another and eventually from one driver to another. In this context determining the shortest path between delivery points requires to put in correlation the road network, the vehicle features, the driver behavior, and the geographic points to pass through to complete the expected activities.

The router does not take as input mailing addresses but expects proper coordinates. The geocoding result is entirely dependent on the quality of the data. This quality of the obtained coordinates can only be qualified with a specific expertise. As Geocoder only returns the most probable coordinates corresponding to the information, it could be dangerous and poorly relevant to directly return route data. This choice of separating these two phases also has the advantage to increase the isolation the service.

The Router web service has three main features. First, it must determine the shortest path for a given vehicle to navigate through an ordered set of point.

Then, the matrix operation has to return the route time and distance between each pair of points. Finally, the isoline feature give the area which could be reached within a given amount of time or within a limited distance. These operations are synchronously performed. The matrix operation may take an important amount of time for a large set of points, but most of the requests are performed for a very small set of points and could be answered in a very short time.

It has to be noted, that it uses by default Open Source and Open Data layers to provide such data. The road network data are coupled with a land use data set in order to adapt the speed profiles accordingly to the population density.

The method is currently only available for occidental countries and could be extended as these data are progressively aggregated worldwide (Terroso-Saenz & Muñoz, 2020).

Optimizer

Like the router service, the optimizer expects already geocoded data. Nevertheless, it performs requests to the router. Indeed, the Vehicle Routing Problem sent usually does not contain its own matrix between all the points of the problem. Unlike the geocoding which could be easily validated by a human operator.

Travel time and distance matrices in their entirety are difficult to evaluate. Even if an individual itinerary could be humanly evaluated. The volume of data, as they are dependent on a large set of parameters, is left to the discretion of the project, if not provided by the client itself.

Within this ecosystem, the web service dedicated to the resolution of Vehicle

Routing Problems has received a particular attention, as it receives and gathers all the data collected from the others services and must provide an adapted route plan regarding all the constraints described by the client.

Figure 2 gives the conceptual model behind the Optimizer web service. This web service does not have as a goal to store data and let users to add, edit, or delete single customers within a given problem to solve. The client is supposed to send a fully formed problem in a single row, containing all the data of the problem (except the matrix data) with the solve operation. This opera-

tion would not answer a solution synchronously, first because the computation of matrices may be time-consuming and secondly because the resolution itself requires heavy computations. Then, the solve operation will return an id. This id could be sent to the solution resource to check the current status of the resolution, and when terminated the final result. Eventually, the client may decide that a resolution is no more required, he could with this it interrupt the resolution. Currently no mechanism of notification has been put in place. Some questions have to be answered first, as we have no assumption on the use case of this API. The VRP could be sent from one device (the route manager desktop)

and the solution could be expected both on the same device or on another one (a driver app).

The Optimizer Back End includes every operation performed behind the hood to answer client requests. It is structured into multiple modules. When a Application, a given problem will only be solved once.

Concerning the deployment of servers on the fly or the affectations of ded-icated servers, any problem must be evaluated in order to determine what resources have to be devoted to its resolution. Indeed, this question is complex [START_REF] Rasley | Efficient queue management for cluster scheduling[END_REF] and has to take into account a large panel of business considerations, some parameters are displayed within Figure 3. The main objective is to find a balance between resource allocation, profitability, and the delay to answer. This subject has become more critical with the development of Infrastructure as a Service (IaaS) providers on the market [START_REF] Heilig | Modeling and solving cloud service purchasing in multi-cloud environments[END_REF]. The driver, on its side, receive the set of missions to perform its tour. Fleet may also receive, as the tour progresses, data from the field, both to inform the route manager on eventual issues and the final customers to update the ETA. All these web services could be called independently and may be adapted to a large set of contexts.

Web Application

The Web Application is available both as a demonstrator of the technical stack and as fully functional Route Management Software (RMS) distributed commercially (see Figure 4). It is a user-friendly application that has been built

with the Model-View-Controller (MVC) software design pattern to provide a very low latency but let the user manipulating its data to build its route. The Web application uses a server-side scripting language, which means that the code is executed and interpreted by the server. The client, on its side, only displays generated views with behaviors which trigger controllers on the serverside. The views and the controllers are both exposed on the front end. This has for advantage to allow developers to integrate directly parts the web application, or to re-implement some views to fulfill particular needs. This service is designed to fit within a large set of last-mile activities. This generalization implies some choices in the representation of the data, their han-dling and the operations to apply. Any data representation or behavior implies making the technical choice to balance between reactivity and accuracy. This may also require performing various calls to other services.

The final customers are represented both as complex objects with various properties, especially their address. It is projected on the map with its coordinates. Address and coordinates are then supposed to be highly related. But whenever the point which represents this customer is moved on the map, its coordinates are edited. Does the application have to propose a new address?

Or keep the current one, even if the point has moved to a completely different location? And inversely, if the address is edited, does the point have to be geocoded again? The current choice is to geocode the address on the creation of the customer, the following edits suggest the user to edit the according data with a non-blocking button. On a plan, which displays all the routes of a single day, every path of the route is displayed and gives information on the travel time and the associated distance. On any change, automatic (customers insertions) or manual (shift of a customer within a route) shall we recompute the entire path? In the current application, every path is calculated independently, switching two customers only requires to calculate the new detour. But this choice is outdated if we consider traffic data as the whole route is impacted.

Edits of the route are in this case less responsive as the route size increase.

Such drawbacks illustrate the need of third-party editors to have access to the unitary operation which lets them build their own interface dedicated to the activity of their own customers.

Any plan calculated is dependent on the current state of the road network, the current data relative to the customers, and the vehicle fleet in use. This means that a plan is by essence ephemeral. A solution provided by the Optimizer Web Service is also subject to this temporality. Whenever a user imports again a plan performed months ago within the application, the current road network will be applied to it. Eventually, if the plan becomes infeasible regarding the current constraints, alerts will be raised and a decision from the route manager is expected to arbitrate with its own field experience if the routes are feasible or not and adjust them consequently. Eventually, his decision could be to request a new resolution.

Furthermore, the supply chain is exposed to inertia. A provisional plan once built may not be changed entirely. Indeed, as some appointments with customers are booked accordingly to the plan along the day, it may be hard to unplan them. The goods are as well prepared and put in the right warehouse bay or vehicle. Such plans are more often subject to the insertion of new flow than to fundamental changes. The level of change is dependent on the organizational choices of each company and should be transcribed as constraints in the Vehicle Routing Problem to solve.

Optimizer API

In the sequel, we will focus on the choices performed within the Optimizer service. Indeed, this project is from our point of view a good case study showing the interactions between operational research algorithms, decision-making process and computer science engineering applied to the supply chain.

Choosing a standard to define an API has to be done wisely depending on the context of its usage [START_REF] Jin | Designing Web APIs -Building APIs that developers love[END_REF][START_REF] Jacobson | A web service framework for astronomical remote observation in Antarctica by using satellite link[END_REF]. The Event-Driven architectures [START_REF] Dunkel | Event-driven architecture for decision support in traffic management systems[END_REF] expect to have a stable communication all along with the exchange of data and a relatively continuous feed of lightweight data to transmit [START_REF] Jacobson | A web service framework for astronomical remote observation in Antarctica by using satellite link[END_REF]. In the context of a Web-Service dedicated to vehicle routing, it might be expected that the API is used on the field with the variable network quality. Moreover, as the processing of a problem may require a long amount of time the necessity of a continuous communication is not mandatory. These reasons have excluded protocols such as Webhooks, WebSockets or HTTPStreaming.

This bears the choice on Request-Response APIs, which expects the clients to send a request and get the expected result directly or provide a key to retrieve the result subsequently, in the case of an asynchronous operation. The communication between the client and the server has to be as lightweight as possible as we have to deal with the network issues and as the data could be related to really big problems. As SOAP relies on XML which is highly verbose, it can be excluded from the current consideration [START_REF] Tihomirovs | Comparison of SOAP and REST Based Web Services Using Software Evaluation Metrics[END_REF].

Representational State Transfer (REST) is an established standard [START_REF] Massé | An Analysis of Public REST Web Service APIs[END_REF]. Furthermore, we can mention that, as it is close to other web technologies, it is relatively easy for developers to learn how to handle such web service. Note that REST is a software architecture style based on web standards. It means that any of the principles which will be defined below are a convention and may not be applied by every web service [START_REF] Massé | An Analysis of Public REST Web Service APIs[END_REF]. The term Restful is applied to services, which comply with every REST principle.

REST exposes resources as part of URLs. A resource is an entity that is exposed from outside of the system and allows to access a part of the Model, or on which an action can be triggered. REST is based on the use of the standard HTTP methods Create, Read, Update and Delete (CRUD) in order to perform transactions on the resources (see Table 2). Any resource implements one or more of the CRUD verbs. Non-CRUD actions that may be applied are not Client-Server: Responsibilities must be separated between the multiple organizational domains. The server receives the requests and store them into a queue. Workers check out this queue to obtain problem to process.

Statelessness:

The requests are self-sufficient and do not require the server to store the state of the session. The client sends a request and receive an id as answer, using this id, any client can verify the optimization status and retrieve its result.

Cacheability: Responses are cacheable. From a single optimization, a result could be retrieved without performing the whole resolution.

Layered system: A server can delegate a request to another server to generate a result. The API is organized into an interface delegating resolution to workers which could be placed on another physical machine.

This ease the scalability of the system.

Code on demand (optional):

Servers should be able to transfer executable code. The current project doesn't implement this kind of functionality.

Uniform interface: The internal data representation is conceptually separated from the answer returned to the client. It also gives enough information to delete the resource from the server, here using an id. The answer is self-interpretive and holds itself the type of data returned, such that the client knows dynamically which type to handle.

Having a business-centric or a document-centric service is not restricted to the choice of the standard but is more related to the architecture of the project itself. Within a REST context, both alternatives are practicable, the operations may be unitary, following the business-centric definition, such as the user will have to call the right methods to handle the data and perform the expected actions. It is also possible to POST a single document with all the data and the API will deduce the internal operations to perform. It is also possible to combine both approaches, having some operations which are business-centric and will directly manipulate the data processing. Some other operations that are independent of user interventions.

This property is particularly interesting in our context, indeed we will receive big and complex routing problems to solve, the goal of the API is to provide a black box-like service which will return organized routes. The user would not have to know which operations have to be performed in order to solve the problem sent. Nevertheless, the user may have to manipulate a higher level of the process. As the solving a task may be time-consuming, it will be performed asynchronously, so the user may want to manipulate the object containing the problem to solve with unitary operations. He will have to interrogate on occasion whether or not the resolution is complete. He may also want the resolution to be stopped. He may also want to obtain the list of its resolutions currently in process. These three last operations are business-centric as they do not expect the API to perform hidden and complex tasks but only perform simple and direct tasks directly relative to the operation called.

Security

The first level of security which has to be discussed is how the data transmitted to the API are kept confidential. At this purpose, HTTP implements the Transport Layer Security (TLS) through the HTTPS protocol (Figure 5).

It encrypts the data between the sending app and the web server. First of all, the server has to be known by a certification authority. For this purpose, the server generates a private and a public key and performs a Certification Signing Request (CSR) to a Certification Authority which will act as proof of identity for the server.

Once the server is registered, HTTPS requests can be performed. At the beginning of a new transaction, the client asks the server to transmit a chain which authenticate a certificate authority server. The client verifies if the certificate authority server belongs to its trusted list. If so, the client asks to this

Authentication

Basic authentication

One of the easiest ways to implement an authentication consists of asking the user a username and a password. It requires no extra libraries or implementation. This solution is simple and widely diffused, but it has also some weaknesses. When an application is compromised, the credentials are exposed which means that private user data may leak through the vulnerability. It becomes even more critical as we know that the same passwords are often used across multiple services. Any access to these credentials maybe gives access to several sources of data even if the applications are provided by an unrelated service provider. As a consequence, this authentication method is discouraged particularly in the context of business management.

OAuth

Instead of performing the authentication directly within the API, this part may be delegated to another service which is more widely used. In this manner, the user has a centralized access to multiple services with the same credentials, which are only present in a single location. Users authorize applications to access the details of their own account if they successfully login within this centralized location. This way, a user can edit its password without revoking the access of API to its data. And inversely, revoke access of APIs without changing its credentials. This method is particularly interesting as the login is delegated to a trusted party, similar to HTTPS, which decouple the access to personal data of the access to business data. However, it has to be considered wisely, a business is rarely managed by a single user, the access to this set of tokens has been shared by a group of users with multiple right levels. This solution is currently not implemented in the project as it currently used by centralized applications, which only requires a single token, here called api key. But it could with only a few efforts by adding some unitary operations in the input of the API, such as registration or login endpoints.

API Keys

API keys are another way to be authenticate into such service. Theses keys are randomly generated long sequences of characters, making it hard to guess even through a brute-force attack. It has the advantage to be unique, so it is used only by the service generating the key. Another advantage is that the API does not require to delegate the authentication to another service. It is a really good and fast solution to start up a project, until reaching a sufficient user base to consider more advanced authentication methods. The philosophy is similar to OAuth, as the authentication is based on a single key or token. Nevertheless, API keys are less flexible they do not involve a trusted third party.

API keys are the current choice implemented within the project. Indeed, most of the customers interact directly with the Web App and by the same occasion delegates the interactions with the web services. The registration of a new api key is only possible through a contact with the technical team. Nevertheless, this hasn't been blocking as the way to discover the project is to begin with the web application, which has a self-registration system.

Authorization

Once the client is identified, we have to define which feature it can access.

First, we have to define if multiple levels of access are required. This design is dictated by the purpose of the API. That is particularly true if the right access management to data or to resources is required. In the case, that the API only provides a result from self-sufficient data transmitted by the client without interaction from other clients, multiple levels of access are only useful when particular operations access would be restricted. But we may have to restrict for each user the resources allocated simultaneously to a single user.

In the case of interactions between user data, we have to handle privacy and moderation rights. This implies to define individual rights or group management. Individual rights are rarely a good idea as it is harder to handle once the number of users increases. Group management is easier to scale and allows us to define multiple levels of groups. Such a hierarchy allows defining more refined right management.

In the current state of the project, as we have a single API key by company, the data privacy across users of an API key is delegated to the client application.

Nevertheless, a single API key only have access to the optimization results sent with this particular key.

Rate-Limit

API clients may tend to send requests simultaneously with various calls without considering fairness or concurrent requests from other clients. As it is not the client's role to know the charge of the server it has to be managed on the API side. This is done by a rate-limiting mechanism. Such constraints will make the API protected against denial-of-service (DoS) attacks. It will also prevent the application from abusive usage and spam-sending. A ratelimit could be defined at the server-side regardless of the application and the users. This defines a maximum number of connections to the physical machine simultaneously and will tend to banish misbehaving users. Rate-limiting may also be defined more granularity with a limit defined by source and not only at the scale of the server. This will allow limiting only users with a heavy load.

We may also have to consider users which have generally few requests but may send a lot of data in a short amount of time. Shall the API be insensitive to this or may it tolerate such burst calls until a given limit? Does this limitation have to be equal amongst all the clients or defined differently for multiple groups of users who shared resources?

Token-bucket

The token bucket algorithm implementation is based on a maximum number of available tokens, each arriving request consumes a token and new tokens arrive regularly. If there is no token left, the request is rejected.

Fixed-window counter

Within a given time window a maximum number of requests is given. At the end of the period, the counter is reset allowing another bunch set of requests.

Sliding-window counter

Instead of considering a static definition of a minute or an hour, we might consider a floating one. Because you do not want to forget about a potential burst at the end of the last period of time, we may try to smooth the requests.

Optimizer Back-End

Once the security layer has been successfully overcome, the optimization layer has two main methods which can be reached from the front-end directly or indirectly.

First, requesting a resolution (Figure 6) requires having a problem, which could be sent entirely from the front-end directly or could be agglomerated through the data layer. So, with a problem, the user still must be authenticated, not from the security but from the contractual agreement point of view. Indeed, users may have to face various policies to process the incoming request. The policies could limit the size of the request, the time to process it, or indicate the eventually dedicated resources allowed to this user. Once the policy rule has been retrieved, the problem is analyzed, and its consistency validated in order to ensure that the data transmitted are relevant both individually and within the context of the global resolution. The policy is then applied depending on the data which have been validated. Note that, some data may have been filtered as they are not relevant but may not prevent problems to be consistent in itself, such data are put aside. If some inconsistent data are part of the core of the problem, the problem cannot be solved, and an error is raised. When a problem passes the validation phase, it is given to the job manager with the policy previously retrieved. The job manager will return in exchange for a job id, which will allow retrieving the solution on a later call.

Secondly, whenever a job has been handled by the job manager and its resolution has been delegated to workers for an asynchronous processing. The client will regularly interrogate the API to know the current status of the resolution (Figure 7). For this purpose, it will request the Get operations on the job resource directly or obtain the result through the Web App which will apply the solution once it is available. In any case, if the solution is not already present in the cache, the operation will interrogate the Solution Manager which will return if the id is known, its current status and if possible the partial solution or the final solution whenever it is available.

The exchange of data and status between the resolution layers is displayed in Figure 8. The workers interrogate regularly the job store to know if a job is available for resolution. Note that a worker may not reach certain jobs due to resource policies. If a job is available, the worker takes its own and gets the data associated. Once the job acquired, it will process the tasks described in Figure 9. At every step of the resolution, the worker may store its current 635 status and eventually the intermediate results. At the end of the resolution, the worker stores the final solution and informs that the job is completed. The worker retrieves at this moment its initial state and starts to fetch again the job store.

The job manager on its side stores problems in the job store when those 640 arrive in exchange of a job id. The job manager also interrogates the store whenever a Get operation is requested to send the content currently stored.

The resolution is divided into various sequential steps which are interdependent preventing then to divide it into multiple tasks which could have been cess. Whenever all the sub-problems have been solved, the results are merged and stored, and the status is changed to "completed".

Performance Indicators

Market study

Tables 3 and4 compare the solution Optimizer-API of Mapotempo against similar solutions on the market as well as the Vehicle Routing Web-based Solver provided by INRIA with the solver developed by [START_REF] Sadykov | A Bucket Graph-Based Labeling Algorithm with Application to Vehicle Routing[END_REF]. Table 3 presents a comparison of the APIs capabilities regardless to the variants it can address. Routific and Tarot Analytics didn't communicate on the solver they Every project presented here use the REST standard to expose their API.

The resolution requests are performed asynchronously except for Verso, which has the particularity to build its solver with a focus to provide good solutions in very short amount of time. Among the list of the APIs presented, the commercial solutions didn't provide proof of optimality. This segment is reserved to the academic API of INRIA.

As mentioned in section 4.4 integrating the geocoding step directly within the resolution segment could be dangerous. Nevertheless, Grapphopper and Routific provide directly this feature with their Vehicle Routing API.

Every commercial solution provide a projection of the problem to solve on the road network to provide to provide route duration. This feature is not present in the INRIA API. Indeed the academic instances use a specified distance metric, which is often an Euclidean or Manhattan distance. Sometimes, the distance matrix is provided with the instance. This is comprehensible as the road network and the legislation applied on may change. In a commercial context, it may be hard to ask the final user to provide an entire matrix.

Note that, the time matrix is often sufficient to solve a VRP. But it many cases, both time and distance matrices are needed. The working time of drivers is regulated by the law, then reducing this value is not an objective in itself but becomes a constraint. The real goal is to reduce the total distance and eventually the greenhouse gas emissions. In these cases, the time and distance matrices at the same time are mandatory. This features is provided by Graphhopper and Mapotempo. In addition if this feature Graphhopper and Mapotempo provide distinct matrices for heterogeneous fleet because trucks, cars or cycles are subject to distinct road laws.

The column Initial presents the capability of taking into account an initial solution or state as a starting point for the resolution. The column Relation indicate the capability to link nodes together, it could be by putting nodes in the same route, in a given order or a given sequence. "P&D" indicates the possibility to define a link between two nodes, one pickup and one delivery.

This refers to the Pickup and Delivery VRP (PDVRP) variant.

Table 4 displays the coverage of the various projects selected on some variants of the VRP. The variants not introduced until now are the Capacitated VRP (CVRP), VRP with Lunch Break (VRPLB), Orienteering Problem (OP),

Periodic VRP (PVRP), VRP with Semi-Soft Time Windows (VRPSSTW). The column skills doesn't correspond to a proper variant, as it could be represented as a capacity dimension with a maximum value of zero on certain vehicles and a infinite capacity on others. This attribute displays the ability of given vehicles to visit a set of nodes.

Numerical results

Table 5 summarizes the results obtained using Optimizer API and a generic model implemented with OR-Tools v7.5 on various instance sets from the literature. Theses variants of the VRP only consider the case where the vehicles starts and finish their routes from and to their depot. The distances are calculated using an euclidean distance. The maximum resolution time of Optimizer-API has been fixed to 10 minutes, except for MDVRPTW, with a time limit set to 1 hour. Note that, Optimizer-API embeds a mechanism to interrupt resolutions which didn't find any improvement within a time equivalent to a multiple of the time spend to find the current best solution.

The results presented here only represent a small subset of the capabilites provided by Optimizer API. Nevertheless, these results are the best way to exhibit the performances of the system. Indeed, these problems have been largely studied. The detailed results are put in appendix 7.

The generic model gives good solution for small instances.Furthermore, the gap increase for bigger instances, but as the time to obtain these solution is strictly limited, the gap remains contained.

The configuration used to solve the instances is set such that above 400 nodes, the problem has to be split in two parts until each sub problem reach a size below this limit. Indeed, this can lead to make the optimal solution unreachable. Nevertheless, it allows in a time constrained situation to obtain a solution of good quality within a strictly limited amount of time.

Discussions 740

The implementation of Web Services dedicated to decision support systems is a great step to democratize operation research algorithms. As such problems are resource and time consuming to solve, delegate such operations are both beneficial for the end-user as its machine will remain entirely free and responsive for others tasks. And for the service provider as the quality of the result will 745 not rely on the user's device computation performances. Moreover, the service provider is able to associate the most fitted resources to reduce the computation time and the cost required for a single optimization.

Such a solution could be used directly by end users through the Web App.

Nevertheless, such a tool is oriented and will only expose a subset of the entire solving capability of the optimization layer. Indeed, providing a generic user interface perfectly fitted to any segment of the supply-chain is particularly difficult as any ergonomic choice is biased and designed for a few use cases. Providing a direct access to the optimization layer makes the optimization independent from the user interface which could be delegated to external entities such as software publishers specialized on a particular field of the last-mile.

Decoupling user interface from a particular module of such application by providing independent software brick makes the particular elements more flexible to integrate new features. By the way, the flexibility is precious in the context of the last-mile as the environment and the constraints evolve quickly.

Such architecture divided into multiple services allows to change data providers and technical bricks providers without changing the whole stack. The Geocoder is relatively stable in time, as the address conventions are widely diffused, but the data sources uses multiple formats. The Router as the transportation networks evolve quickly, that is particularly the case with the progressive release of the public transport network data and the growth of smart cities.

Conclusion and Future Work

This article proposes an API able to support as input a large variety of VRP variants with many attributes. The current implementation interprets the input and distinguishes wherever the problem sent is valid or not. Once validated, the problem is prepared and eventually split, this has for consequence to lost the reachability of the optimal solution. But, as the split happens when the problems are large and the resolution time is relatively small, this optimal solution is anyway hard to reach. Optimizer API is designed to orient the problem or sub-problems to call the most efficient solver depending on the case met, currently OR-Tools and VROOM are used. Other solvers have been integrated, but some didn't met the expected quality of result or simply the current license doesn't allow to use them in a commercial context.

Even if our OR-Tools model is sufficiently flexible to tolerate a large variety of attributes, it shows its limits regarding the State-of-the-Art methods with a tight gap. The future work can be divided in multiple categories.

Currently, some heuristic logic, such the split mechanism, are implemented within the Back-End, their performance is currently under investigation and should be improved in a close future. The split logic is part of it, and is currently extracted to build a new micro-service. This makes the clustering logic developped for the Vehicle Routing context available directly for Mapotempo Web or from any other project without formulating an complete VRP problem.

On the solver side, the OR-Tools model must be edited to improve the performance of the calls to the solver. Some operators allowing to define relations between vehicles are absent and for example makes it hard to solve directly the PVRP efficiently.

The decision support system in its entirety gives both access to bricks of various levels from the basics (Routing, Geocoding) to more sophisticated ones (Optimizer, Fleet, Mapotempo Web) towards the preparation, visualization, resolution and realization of the VRP. Particularly, the system has been designed

to tackle daily organization of the last mile delivery, pickup or service. The APIs are used at multiple steps of the decision chain. Among others, it is used as an investigation tool to explore deep changes of the current process for the last mile delivery for various actors of the 3 PL (Third Party-Logistic). It is also used to integrate external flows without increasing the exploitation cost, particularly for the Newspaper delivery. Some companies use the APIs for appointment booking. Some others use the decision system to build their strategic visit planning over several months with regular visits to their customers.

From an OR point of view, the decision support system certainly covers a large set of variants for the static resolution of the VRP. But that's not the only The resolution of each user request is currently performed with a single thread. Nevertheless, some resolution methods allow parallel processing. For example, the large problems can be split into multiple subparts which can be processed in parallel.

The OR community has lately developed a big interest to the Machine Learning (ML) tools. Performance improvements may come from the learning of efficient solution patterns. Moreover, the user usually edits manually the solution provided by the system, or the driver chose to switch some parts of the route.

Such decisions could be also learned over regular patterns to make the resolution fitting the user preferences make the resolution met user preferences.

At the architecture level, various problems are not yet addressed. For example, the load balancing is currently not taken into account. The system is limited to basic DNS balancing rules which redirect the users to a server depending on their geographic position. Nevertheless, this geographic assignment may cause some problems in term of replication of the data through the multiple nodes of the decision support system. A wise system of balancing is therefore one of the key for large adoption of this technological stack.

Detailed results

950

In all the tables, the times are in seconds. n is the number of nodes to serve, m is the number of vehicles and d is the number of depots. Note that in the case of multi depot instances, there are m vehicles per depot and in the case of heterogeneous fleet, m represents the number of vehicle configurations in term of cost and capacity. the results in bold have comes with a proof of optimality.

955

The VRPTW variant, as shown in Table 13, has been tested both with the generic model and the dedicated method provided by VROOM through Optimizer-API. On every instance the dedicated method has a smaller gap within a smaller amount of time, the generic model has some counterparts, which makes it slower to converge. Nevertheless, the resolution time is strictly 960 limited and this constraint is essential to make the solution usable in practice.

This point has to be put in perspective to compare the results provided by [START_REF] Sadykov | A Bucket Graph-Based Labeling Algorithm with Application to Vehicle Routing[END_REF] where the time limit is set to 60 hours.

Generic model

  10

Figure 1 :

 1 Figure 1: Mapotempo Transportation System Architecture

Figure 2 :

 2 Figure 2: Optimizer Web Service

Figure 3 :

 3 Figure 3: Worker assignment wheel

Figure 4 :

 4 Figure 4: Example of the user friendly interface proposed by the Web Application

Figure 5 :

 5 Figure 5: TLS authentication

Figure 6 :

 6 Figure 6: Job manager input

Figure 8 :

 8 Figure 8: Resolution communication

Figure 9 :

 9 Figure 9: Worker process

  problem which can be met in the context of the last mile. The resolution of the VRP in a dynamic environment such as the Time Dependent VRP (TDVRP) or the Dial A Ride Problem (DARP). Other problems related, such as the Location Routing Problem (LRP) are not currently covered. Nevertheless, the basic bricks able to provide data to solve these problems are available through the APIs. The Vehicle Routing and Truck Driver Scheduling Problem (VRTDSP) to comply with the regulation laws about the working hours of truck drivers is as well under investigation. But since the main target field is the last mile of the supply chain, the driver work days are subject to few simplification in the model.

Table 1 :

 1 Front End resources

	rized within Table 1. APIs may communicate between themselves. In particular
	both Optimizer and Fleet serviced rely on the paths calculated by Router.

Table 2 :

 2 CRUD operations and Rest verbs

	CRUD	HTTP verb	Description
	Create	POST	A new resource is added to the database
	Read	GET	Give a read-only access to resources
	Update PUT/PATCH	Edit or replace existing resources
	Delete	DELETE	Remove existing resources
	easily represented using such structure. Still, it can usually be sent as an update
	of the resource state by giving a parameter via the PUT verb. Another way
	of manipulating those actions is to create a sub-resource which will represent
	specific actions. A sub-resource shows the relationship with the above resource.
	As mentioned above, REST is a standard design to create Web APIs. The
	rules behind the architecture focused on performance, scalability, simplicity,
	modifiability, visibility, portability and reliability. The architecture is ruled by

Table 5 :

 5 Gap to the State-of-the-Art

Table 6 :

 6 Relative performances of computers

			Luo & Chen(2014) Penna et al.(2019) Sadykov et al.(2020)	Our proposal
	CPU	Opteron 2755 2.2GHz Pentium 4 2.8 GHz	i7 2.93 GHz	E5-2680 v3 2.50 GHz i7-7700HQ 2.80GHz
	OS			Ubuntu 14.04		Linux Mint 20
	Language	C++	C++	C++	C++	C++
	Rating	445	502	1394	1810	2069
	Speed factor	4,65	4,12	1,48	1,14	1

Table 7 :

 7 MDVRPTW

	Vidal et al.(2013)	BKS

Table 8 :

 8 MDVRPTW

	Sadykov et al.(2020) Luo & Chen(2014)

Table 9 :

 9 MDVRP

	Sadykov et al.(2020) Penna et al.(2019)

Table 10 :

 10 HFVRP -with customers up to 125 customers

	Sadykov et al.(2020) Penna et al.(2019)

Table 11 :

 11 HFVRP -with customers above 125 and up to 170

	Sadykov et al.(2020) Penna et al.(2019)

Table 12 :

 12 HFVRP -with customers above 170

	49

Table 13 :

 13 VRPTW