Théo Le Colleter
email: lecolleter.theo@gmail.com

Dorian Dumez
email: dorian.dumez@hec.ca

Fabien Lehuédé

Olivier Péton
email: olivier.peton@imt-atlantique.fr

Small and Large Neighborhood Search for the Park-and-Loop Routing Problem with Parking Selection

Keywords: vehicle routing, park-and-loop, large neighborhood search, last-mile delivery

This paper presents a variant of the vehicle routing problem regarding the delivery of products to customers in cities with a combination of walking and driving. The objective is first to offer a better modeling of delivery problems in congested cities and also to evaluate potential savings in traveled distances and parking times. We introduce the Park-and-Loop Routing Problem with Parking Selection (PLRP-PS) in which a parking space or loading zone has to be found for the driver and his vehicle before he walks to deliver to one or several customers. In this paper, we will focus on cases where parking locations should be selected among a large set of parking areas. To solve this problem, we developed a variant of the large neighborhood search metaheuristic called Small and Large Neighborhood Search (SLNS). We will focus on designing and comparing simple and efficient techniques to select parking spots for vehicles before goods are delivered by walking trips. The efficiency of the approach is demonstrated in the park-andloop routing problem, with eleven new best solutions found on an existing benchmark. Some realistic instances were generated based on open data from the city of Nantes, France. In these instances, we find that combining walking and driving to deliver to the center of a city can save 19% of working time on average compared to the classical vehicle routing approach.

Introduction

Reducing congestion and CO 2 emissions is a major challenge for the delivery of goods in urban areas. In this paper, we are interested in combining driving and walking for last-mile delivery, with a focus on where a vehicle can park before its driver can deliver to his or her customers.

The foremost inspiration of this work is that most vehicle routing problems implicitly assume that vehicles park in front of customer locations. This assumption is not always realistic in dense cities, since parking spaces do not always exist at a customer location. Indeed, parking a delivery vehicle exactly in front of each customer is often impossible, but it may not even be profitable considering the driving distance or workload. It can be more efficient to cross the street by foot than to turn around or make a detour to park on the customer's side of the street. If two successive customers are located near each other, re-starting the vehicle and parking it a few meters further is also not realistic when the driver can walk between the two addresses. As many cities tend to reallocate road space to pedestrians, bicycles, and public transportation [START_REF] Martinez-Sykora | Optimised solutions to the last-mile delivery problem in London using a combination of walking and driving[END_REF] it seems more and more valuable to optimize delivery routes by considering parking locations and walking trips. Supporting this statement, recent studies show that the time to find parking spots is not negligible in large cities [START_REF] Reed | Does Parking Matter? The Impact of Search Time for Parking on Last-Mile Delivery Optimization[END_REF]. Thus, the unproductive driving time spent looking for a parking space leads to significant overhead costs [START_REF] Bates | Are people the key to enabling collaborative smart logistics[END_REF]. Consequently, drivers often illegally double-park, also at high costs [START_REF] Dalla Chiara | A Policy-Sensitive Model of Parking Choice for Commercial Vehicles in Urban Areas[END_REF]. In both cases, assuming parking at customers has a cost, it also generates congestion, air pollution and noise pollution.

To address this challenge we investigate vehicle routing with driving, walking, and parking selection for last mile delivery. In this study, the potential parking locations are the available commercial loading zones defined by local authorities. In a dense urban area, we show that it is beneficial to serve multiple customers from one parking spot.

To better integrate these considerations in VRP models and algorithms, we introduce the Park-and-Loop Routing Problem with Parking Selection (PLRP-PS). This problem considers a set of customers who are delivered to from a depot by drivers with a homogeneous fleet of vehicles. We presume a large set of parking locations is known and that drivers have to park at one of these locations before delivering to some customers through walking-trips.

In this paper, we first review the related literature in Section 2. Then, a formal definition and a Mixed Integer Linear Programming (MILP) formulation for the PLRP-PS are proposed in Section 3. To solve this problem, we designed a variant of Large Neighborhood Search (LNS) called Small and Large Neighborhood Search (SLNS) (Section 4). We detail the used operators, types of insertions, and we focus more specifically on efficient parking selection strategies.

The computational experiments are presented in Section 5. We first evaluate the proposed algorithmic components in order to identify the best LNS configuration to solve the PLRP-PS. Then, the performance of the designed SLNS is evaluated on a particular case of the VRP-TR [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF]. Finally, managerial insights on the impact of parking selection are presented.

Literature review

Section 2.1 discusses VRP variants that integrate the combination of driving and walking. Section 2.2 presents some other categories of problems related to the PLRP-PS. As the main focus of this paper is the selection of parking in a commercial loading zone from a large set of possible locations, the literature review gives particular attention to this aspect.

Vehicle routing problems with park-and-loop

The combination of walking and driving in routing optimization was first introduced in a Location Arc Routing Problem by [START_REF] Levy | The arc oriented location routing problem[END_REF], within the context of mail delivery. Later on, park-and-loop was described in [START_REF] Bodin | Scheduling of local delivery carrier routes for the United States Postal Service[END_REF] as a practice of parking the vehicle before serving a set of nearby customers on foot before returning to the vehicle and continuing the route. This practice is also mentioned in Irnich (2008) as an extension of the windy rural postman problem. To our knowledge, the first solution method for a VRP with park-and-loop was proposed by [START_REF] Gussmagg-Pfliegl | Maildelivery problems with park-and-loop tours : a heuristic approach[END_REF] also presented as a mail delivery problem. This method follows a cluster-first route-second heuristic combined with the solving of a set partitioning problem.

Park-and-loop is considered in the Vehicle Routing Problem with Time Windows and Multiple Service Workers (VRPTWMS, [START_REF] Senarclens | Evaluating two new heuristics for constructing customer clusters in a VRPTW with multiple service workers[END_REF]). The VRPTWMS is an extension of the VRPTW where multiple service workers can be in the same vehicle and vehicles can park only at pre-identified parking locations. After a vehicle is parked, workers perform back-and-forth walking trips to customers from the vehicle, serving only one customer per walking trip. The vehicle may leave the parking spot when all workers have served their customers. A fast cluster-first route-second heuristic was developed. First, a parallel insertion heuristic is used to group customers and assign them to a parking location. Second, the I1 insertion heuristic of [START_REF] Solomon | Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[END_REF] is used to determine the routes. Randomly generated instances with up to 200 customers and 150 parking locations are considered. [START_REF] Martinez-Sykora | Optimised solutions to the last-mile delivery problem in London using a combination of walking and driving[END_REF] solve an asymmetric TSP with park-and-loop where the objective is a weighted sum of the total driving time and the total walking time. A branch-and-cut algorithm is used to solve instances from a London case study with up to 30 customers. In this problem, the vehicle is parked at a customer's location but the driver can walk to serve several customers from one parking spot. [START_REF] Reed | Does Parking Matter? The Impact of Search Time for Parking on Last-Mile Delivery Optimization[END_REF] describe the Capacitated Delivery Problem with Parking (CDPP). The CDPP is a VRP in which delivery persons can drive and walk. They park near the customers and can serve a few others by walking but finding a parking spot on a commercial loading zone takes a given amount of time. A Mixed Integer Programming (MIP) model is developed, with dedicated valid inequalities, to solve instances based in the State of Illinois. Extensive experiments study the impact of parking time. They conclude that taking it into account is of major importance in cities and that combining driving and walking is very promising. [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF] introduce the Vehicle Routing Problem with Transportable Resources (VRP-TR). The VRP-TR considers a setting with drivers and additional workers that can carpool, walk between customers, and possibly change vehicles. The objective in this problem is to minimize the sum of all vehicles' travel distance, taking account a maximum overall walking distance for each worker as well as a day duration constraint. A Variable Neighborhood Search (VNS) metaheuristic is developed to solve instances inspired by a European energy provider with up to 50 customers with a time budget of 10 hours. These VRP-TR instances are solved both in the case where car-pooling is allowed and also with one driver per vehicle and no car-pooling. The VRP-TR also takes the set of customers as the set of parking locations. [START_REF] Cabrera | The Doubly Open Park-and-loop Routing Problem[END_REF] introduce the Doubly Open Park-and-Loop Routing Problem (DO-PLRP) which is closely related to the VRP-TR especially when carpooling is not allowed. The DOPLRP consists of designing routes for technicians to visit a set of customers for an energy provider. Routes are subcontracted and their costs are evaluated based on the distance traveled between the first and the last customer of each route. There are three types of routes: pure vehicle routes where the technician serves customers by driving only, pure walking routes where the technician serves customers by walking only, and vehicle routes with park-and-loop. Vehicles can park at customer locations. The authors propose a matheuristic which is composed of a split procedure on a giant-tour that provides routes and a set partitioning formulation that uses these routes to improve solutions. The algorithm is shown to outperform the VNS of [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF] on the VRP-TR instances in the case where carpooling is not considered. In addition, the proposed method is used to solve real-world DOPLRP instances with up to 3800 customers.

A first observation from the recent literature is that, independent of parking selection, the terminology is not unified over the different papers that integrate the VRP and park-and-loop.

In the following, we denote by the Park-and-Loop Routing Problem (PLRP) that the simplest integration of park-and-loop in the VRP, whereby vehicles can park at customers and drivers can perform walking trips to deliver more than one customer from a parking location. This corresponds to the VRP-TR without car-pooling of [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF] or the DOPLRP with closed vehicle routes from [START_REF] Cabrera | The Doubly Open Park-and-loop Routing Problem[END_REF].

Related classes of problems

The Truck and Trailer Routing Problem (TTRP) was first studied by [START_REF] Semet | A two-phase algorithm for the partial accessibility constrained vehicle routing problem[END_REF] under the name Partial Accessibility Vehicle Routing Problem. This problem typically occurs in milk collection problems where some producers cannot be accessed by a truck with its trailer. Thus, the truck can leave its trailer at some customer's location and perform some visits before recoupling with its trailer. Hence, in this problem, solutions have a park-and-loop structure. The connection between the TTRP and park-and-loop routing problems is extensively discussed in the recent paper of [START_REF] Cabrera | The Doubly Open Park-and-loop Routing Problem[END_REF]. In particular, the TTRP with time windows has been recently addressed by [START_REF] Parragh | Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows[END_REF] with a branch-and-price algorithm and an LNS. The authors solve instances with up to 100 customers in which the decoupling points are the customers that are accessible with trailers.

The routing problems with drones also consider sub-tours for visiting customers. The Traveling Salesman Problem with Drone (Agatz et al., 2018, TSP-D) extends the standard TSP by allowing the driver to send an unmanned aerial vehicle (UAV) to deliver a package while he/she is serving other customers. The truck and the drone can couple/decouple only at customers' locations. The authors propose a mathematical model and a route-first, cluster-second method to solve instances with up to 100 customers. More recently, [START_REF] Li | Ground-vehicle and unmanned-aerialvehicle routing problems from two-echelon scheme perspective: a review[END_REF] defined the Two-Echelon Vehicle Routing Problem with Time Windows and Mobile Satellites (2E-VRP-TM). This problem considers a homogeneous fleet of vans paired with UAVs for parcel delivery.

It extends the standard VRP by allowing UAVs to deliver customers while the van is parked at another customer location. An Adaptive Large Neighborhood Search (ALNS) heuristic is proposed to solve instances with up to 100 customers.

In addition, the combination of walking and driving can be found in home health care logistics. For example, [START_REF] Dumez | Hybridizing Large Neighborhood Search and Exact Methods for Generalized Vehicle Routing Problems with Time Windows[END_REF] consider that nurses could be driven to customers by a driver and serve some other customers on foot before being picked up. The resulting problem is similar to a dial-a-ride problem. Instances based on data from the Austrian red cross with up to 125 customers were solved with a Tabu Search heuristic.

The connection is also strong with the Two-Echelon VRP [START_REF] Gabriel Crainic | Models for Evaluating and Planning City Logistics Systems[END_REF], in which large vehicles transfer goods to smaller vehicles at so-called satellites, the later ones being allowed to deliver to the customer in a restricted delivery area. We refer the interested reader to [START_REF] Cuda | A survey on twoechelon routing problems[END_REF] and [START_REF] Sluijk | Twoechelon vehicle routing problems: A literature review[END_REF]. Nonetheless, as in other routing problems with intermediate facilities [START_REF] Gianfranco Guastaroba | Intermediate Facilities in Freight Transportation Planning: A Survey[END_REF], the purpose of those is to concentrate the flows. Thus, only a few are considered especially because of their high initial cost in practice.

Discussion

We observe that, although problems with park-and-loop structures have already been investigated in the literature, none of these really consider the selection of parking spaces into a large set of available ones. The largest instances assume that each customer can be a parking space but we think that two considerations are worth investigating in a city logistics context: firstly, parking as close as possible to a customer may not be the best strategy depending on its accessibility and the direction from which the vehicle is coming. Secondly, a large set of areas are available for delivery vehicles in some cities and there is a need for efficient selection rules to be used in vehicle routing heuristics.

The Park-and-Loop Routing Problem with Parking Selection

This section introduces the Park-and-Loop Routing Problem with Parking Selection (PLRP-PS). Section 3.1 depicts the problem settings and Section 3.2 provides a mathematical model. For the sake of simplicity, we do not consider the time necessary to pick up packages at the vehicle nor the service duration at customers, but their integration in our model and method is straightforward.

Problem description

Let us consider a set N of customers with non-unitary demand q i , ∀i ∈ N . Let K = {1, ..., k max } denote the homogeneous vehicle fleet, where k max is the maximum vehicle fleet size. We consider that each vehicle is assigned to a driver who will perform deliveries by walking from a parking location to the customers. Accordingly, we indifferently refer to a vehicle k ∈ K or to a driver k ∈ K in this paper. All vehicles are based at a depot denoted o. The set P models the set of delivery areas. Each parking location j ∈ P is associated with a parking time pt j .

The PLRP-PS is defined on a directed graph G = (V, A). The set of vertices is V = N ∪ P ∪ {o}. The set of arcs is A = A d ∪ A w , where A d is the set of driving arcs, with

A d = {(o, p) | ∀p ∈ P }∪{(i, j) | ∀i, j ∈ P, i = j}∪{(p, o) | ∀p ∈ P }, and A w is the set of walking arcs, with A w = {(p, i) | ∀p ∈ P, i ∈ N } ∪ {(i, j) | ∀i, j ∈ N, i = j} ∪ {(i, p) | ∀p ∈ P, i ∈ N }.
In addition, we define the set A c = {(i, j) | ∀i, j ∈ N, i = j} of walking arcs between customers, with A c ⊆ A w . The driving time matrix is t d , with t d ij ∀(i, j) ∈ A d the driving time for all driving arcs. A driving time t d ij integrates the parking time at destination pt j . The walking time matrix is t w , with t w ij ∀(i, j) ∈ A w the walking time for all walking arcs.

The walking distance matrix is d w , with d w ij ∀(i, j) ∈ A w the walking distance for all walking arcs.

A vehicle route starts from the depot, visits a sequence of parking locations in P , and returns to the depot. The sum of customer orders served by a vehicle route must not exceed the vehicle capacity Q d and a vehicle route duration must not exceed the value h max . A walking-trip starts from a parking location in P , visits a sequence of customers, and returns to the same parking location. The duration of a walking-trip is the sum of the duration of all walking arcs used in this walking-trip. The customer orders served by a walking-trip should not be larger than the walking capacity denoted Q w . The overall walking distance of each driver (i.e. the sum of the distance d w ij of the walking arcs used by a driver over all of its working trips) should not exceed the value w max . At a parking location, a walking-trip can start after the vehicle is parked. Then, the drivers may perform several walking-trips from their parked vehicle.

The PLRP-PS consists of designing vehicle routes and walking-trips, with respect to their delivery and walking capacities, the maximum route duration of each vehicle, and the maximum walking distance of each driver such that each customer is served by exactly one driver. The objective function lexicographically minimizes the number of vehicles (z 1 ) and the sum of driving times, walking times, and parking times denoted z 2 .

Figure 1 illustrates a PLRP-PS solution with

N = {c 1 , c 2 , c 3 , c 4 , c 5 }, P = {p 1 , p 2 , p 3 } and K = {k 1 , k 2 }.

Mathematical model

This section introduces an MILP formulation for the PLRP-PS. It introduces two classes of binary variables and two classes of real variables. First of all, x k ij is a binary variable that takes value 1 if arc (i, j) ∈ A d is used by vehicle k ∈ K, and is equal to 0 otherwise. Then, y kp ij is equal to 1 if arc (i, j) ∈ A w is used by driver k ∈ K by walking while his/her vehicle is 195 parked at p ∈ P , and 0 otherwise. The non-negative real variable r k p models the order in which a vehicle k ∈ K (or its driver) visits parking locations p ∈ P . Finally, non-negative real variable u k i represents the remaining capacity of the driver k ∈ K after visiting customer c ∈ N during the considered walking-trip. According to this notation, the PLRP-PS can be modeled with the following MILP formulation:

200 lex -min(z 1 , z 2 ) (1a) s.t. z 1 = k∈K i∈P x k 0i (1b) z 2 = k∈K p∈P (i,j)∈Aw t w ij y kp ij + k∈K (i,j)∈A d t d ij x k ij ( 1c
)
k∈K p∈P (i,j)∈Aw

y kp ij = 1 ∀j ∈ N (1d) (i,j)∈Aw y kp ij = (j,i)∈Aw y kp ji ∀k ∈ K, p ∈ P, j ∈ N ∪ P (1e) (i,p)∈A d x k ip = (p,i)∈A d x k pi ∀k ∈ K, p ∈ P (1f) (0,i)∈A d x k 0i = (i,n+1)∈A d x k i,n+1 = 1 ∀k ∈ K (1g) (i,p)∈A d x k ip ≥ y kp pj ∀k ∈ K, p ∈ P, j ∈ N (1h) y kp ij = 0 ∀k ∈ K, i, p ∈ P, i = p, j ∈ N (1i) y kp ji = 0 ∀k ∈ K, i, p ∈ P, i = p, j ∈ N ∪ P (1j) p∈P (i,j)∈Aw d w ij × y kp ij ≤ w max ∀k ∈ K (1k) p∈P (i,j)∈Aw t w ij y kp ij + (i,j)∈A d t d ij x k ij ≤ h max ∀k ∈ K (1l) u k i ≤ Q w -q i × y kp pi ∀k ∈ K, p ∈ P, i ∈ N (1m) u k j ≤ u k i -q j + (1 -y kp ij )Q w ∀k ∈ K, p ∈ P, (i, j) ∈ A w (1n) p∈P (i,j)∈Aw q j × y kp ij ≤ Q d ∀k ∈ K, j ∈ N (1o) r k j -r k i ≥ 1 -|P |(1 -x k ij ) ∀k ∈ K, i, j ∈ P, i = j (1p) x k ij ∈ {0, 1} ∀k ∈ K, (i, j) ∈ A d (1q) y kp ij ∈ {0, 1} ∀k ∈ K, p ∈ P, (i, j) ∈ A w (1r) 0 ≤ u k i ∀k ∈ K, i ∈ N (1s) 0 ≤ r k p ∀k ∈ K, p ∈ P (1t)
In this model, the objective function (1a) lexicographically considers two objectives. The first objective (1b) minimizes the vehicle fleet size, while the second objective (1c) minimizes the sum of walking time and driving time (that also includes parking time).

The first set of constraints (1d) fulfills customers' order satisfaction. Every customer must be served by a driver k ∈ K using a walking arc (i, j) ∈ A w while the vehicle is parked at parking node p ∈ P . Constraints (1e) enforce flow conservation on walking arcs. A driver walking to a node j ∈ N ∪ P (either a parking or customer node) should also leave this node by walking. Constraints (1f) enforce the vehicles flow conservation. Constraints (1g) state that each vehicle in K must leave the depot and return to the depot. If a solution uses less than |K| vehicles, then each unused vehicle k ∈ K takes the arc (0, n + 1) with cost 0. Constraints (1h) state that the driver of vehicle k ∈ K can deliver j ∈ N from parking node p ∈ P if there is a driving arc x k ip that enters parking p. Constraints (1i) state that a driver cannot deliver a customer j ∈ N directly from a parking node i ∈ P if i = p where p ∈ P is the parking node assigned to the walking arc y kp ij . Constraints (1j) state that a driver cannot walk to a parking i ∈ P if the car is parked at another parking p ∈ P : i = p.

The overall walking distance constraints (1k) are: for each vehicle k ∈ K the sum of walking arcs distances used by this vehicle should not exceed w max . Constraints (1l) limit the duration of a route, and its walking trips, to h max , i.e. the day duration.

The walking capacity constraints are (1m) and (1n), the capacity remaining after delivering to the first client of a walking-trip i ∈ N is given by (1m). Also, (1n) gives the capacity remaining after delivering the following clients in this walking-trip. The driving capacity constraints are (1o): for each vehicle k ∈ K the sum of the demands served by this vehicle should not exceed the vehicle capacity Q d . Finally, constraints (1p) rank the visits to parking. This adoption of the Miller-Tucker-Zemlin constraints [START_REF] Dantzig | Solution of a large-scale traveling-salesman problem[END_REF] is used to eliminate subtours.

Small and Large Neighborhood Search

The Large Neighborhood Search (LNS) metaheuristic consists of iteratively destroying and repairing the current solution in order to improve it, until a time or iteration limit is reached. The destroy part appeals to so-called destroy operators and the repairing part to repair operators. The idea of LNS was first introduced by Shaw (1998) in constraint programming and reintroduced by [START_REF] Schrimpf | Record breaking optimization results using the ruin and recreate principle[END_REF] under the name "ruin and recreate." Its popularization as a metaheuristic is due to Ropke and Pisinger (2006a) who proposed an adaptive LNS in which several operators are selected depending on their previous performance. The method was shown to be efficient for solving large classes of VRP [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF]Ropke and Pisinger, 2006b). Recently, [START_REF] Christiaens | Slack induction by string removals for vehicle routing problems[END_REF] considerably improved the efficiency of the approach by introducing, among other features, a smaller destruction size and fast repair operators. Dumez et al. (2021a) combines small and large destruction sizes for the LNS. This approach is improved in Dumez et al. (2021b) to solve variants of the generalized VRP. The LNS variant of Dumez et al. (2021a) and Dumez et al. (2021b) was further detailed in Dumez (2021). In this paper, we present a more formal definition of this algorithm under the name Small and Large Neighborhood Search (SLNS).

The SLNS general algorithm is presented in Section 4.1. The destroy and repair operators designed to solve the PLRP-PS are described in Section 4.2, while the different types of insertions implemented in these operators are detailed in Section 4.3. Finally, the proposed parking selection strategies are presented in Section 4.4.

Algorithm

Let us first introduce the concept of partial solution and request bank, which is the LNS way to visit infeasible solutions. The LNS algorithm iteratively destroys and repairs solutions. Hence, the algorithm manipulates partial solutions. Given a solution S, the set B(S), called the request bank, denotes the set of customers that are not served in S. When B(S) is non-empty, S is a called partial solution. Partial solutions are used in operators, with the number of requests in the request bank penalized in the cost function as proposed by [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF]. Accordingly, considering z 2 = f (S), a modified objective function z 2 = f (S) is optimized in LNS, with:

f (S) = f (S) 1 + β |B(S)| N . (2)
In SLNS, the small and large destruction sizes are randomly chosen in intervals [δ small , ∆ small ] and [δ large , ∆ large ], respectively. In addition, we presume two sets of destroy operators: denoted Σ - small and Σ - large , and two sets of repair operators denoted Σ + small and Σ + large . A Small Neighborhood Search (SNS) iteration draws a destruction size in [δ small , ∆ small ], a destroy operator in Σ - small and a repair operator in Σ + small . A Large neighborhood Search (LNS) iteration draws a destruction size in [δ large , ∆ large ], a destroy operator in Σ - large and a repair operator in Σ + large . Dumez et al. (2021b) propose to control these destruction sizes based on a parameter ω called the LNS frequency: if no new best solution is found within ω SNS iterations, then the next iteration will be an LNS iteration. SLNS is described in Algorithm 1.

Algorithm 1 Small and Large Neighborhood Search Input: δ small , ∆ small , δ large , ∆ large , Σ - small , Σ - large , Σ + small ,Σ + large , ω, β, S Output: Best solution found S * 1: iter = 0 2: while the time budget is not reached do 3:

if iter < ω then 4: iter ← iter + 1 {small neighborhood search iteration} 5: S ← S 6:
randomly select a small destruction size Φ ∈ [δ small , ∆ small ] 7:

randomly select operators σ -∈ Σ - small and σ + ∈ Σ + small 8: The iteration counter iter, initialized to zero in line 1, tracks the number of SNS iterations without improving the best known solution S * . The counter iter is re-initialized to 0 on each LNS iteration (line 13) and each time S * is improved (line 22). The main loop between lines 2 and 24 performs SNS iterations and LNS iterations as long as the time limit is not reached. On an SNS iteration (iter < ω, Line 3 -11), a new solution S is created from the current solution S, a small destruction size φ is drawn in the interval [δ small , ∆ small ], a small destroy operator σ -is selected in Σ - small and a small recreate operator σ + is selected in Σ + small . The new solution S is obtained (Line 8) by applying these two operators. S is accepted as the current solution for the next iteration based on a record-to-record acceptance criterion [START_REF] Dueck | New optimization heuristics: The great deluge algorithm and the record-to-record travel[END_REF] applied on the modified cost function f (line 9). In addition, a new solution is also accepted if it improves the current solution. This condition is used in particular on the SNS iterations that follow a LNS one.

S ← σ + (σ -(S , Φ)) 9: if f (S ) < (1 + )f (S * ) or f (S ) < f (S)
If S * is not improved for ω iterations, an LNS iteration is performed (line 13-19). In this case, the new solution S is created from the best known solution S * . The destruction size φ, destroy operator σ -and repair operator are drawn from [δ large , ∆ large ], Σ - large and Σ + large , respectively. The produced solution is then systematically accepted as the current solution for the next SLNS iteration. Over all iterations of the main loop, the best found solution S * is saved (lines 20-22) and returned at the end of the algorithm.

As in Ropke and Pisinger (2006a) SLNS is used in two consecutive phases. The initial solution is found with an unlimited number of vehicles. The first phase reduces the number of vehicles (z 1 ): every time a feasible solution is found (i.e. the request bank is empty), the maximum number of vehicles k max is decremented, the route with the minimum number of customers is removed from the solution and its customers are added to the request bank. When the minimum number of vehicles i∈N q i Q d or the first phase time budget is reached, the second phase (minimization of z 2 ) starts.

Destroy and repair operators

This section introduces the SLNS operators that were implemented to solve the PLRP-PS. We will first briefly describe the destroy operators of the set Σ - small used in SNS iterations:

Random removal (Ropke and Pisinger, 2006a) randomly selects φ customers and removes them from the current solution.

Worst removal (Ropke and Pisinger, 2006a) removes φ customers one after the other, each time selecting the customer whose removal decreases the cost function the most.

Related removal [START_REF] Vera C Hemmelmayr | An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics[END_REF] selects a seed-customer randomly together with its φ -1 nearest customers. These are removed from the solution.

(Split) String removal [START_REF] Christiaens | Slack induction by string removals for vehicle routing problems[END_REF] removes sequences of customers in the walking trips of the current solution, either conserving, or not, a sub-string in the middle.

The destroy operators Σ - large used in LNS iterations bring diversification to the algorithm.

Every small destroy operator described previously is also used as a large destroy operator, i.e. Σ - small ⊂ Σ - large .

In addition to the original versions, we adapt these four operators to the PLRP-PS. To take this problem structure into account, some destroy operators can be either applied to customers or to parking locations (similarly to Hemmelmayr et al. ( 2012)). Hence, for each operator we create an equivalent destroy operator that removes parking locations instead of customers.

When a visited parking location is removed from a solution, all the customers that are served by the walking trips starting from this parking spot are placed in the request bank. For example, the random parking removal operator randomly selects some visited parking locations, all of their visited customers are placed in the request bank and the visit to that particular parking spot is removed from the route, until φ customers have been removed. Symmetrically, when a walking trip becomes empty (after removing its last customer), the corresponding parking location is removed from the vehicle route.

Historical removal [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF] is adapted here to focus on removing parking locations exclusively. It is based on the best objective value obtained by a previous solution that was using a particular parking location. For each parking location, the best objective function value (z 2 ) is stored over SLNS iterations. This operator iteratively removes the parking location with the worst objective value in the history until at least φ customers have been placed in the request bank.

Route removal [START_REF] Vera C Hemmelmayr | An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics[END_REF] removes a random route from the solution.

In our SLNS implementation, the same set of repair operators Σ + is used for large and small destruction sizes. Let S be a partial solution and B(S) the set of customers in the request bank. A repair operator σ + ∈ Σ + evaluates the insertion of customers in B(S). These are selected according to list heuristics, as proposed in Christiaens and Vanden Berghe (2020):

Random selects customers in a random order.

Closest selects customers whose nearest parking location is the closest to the depot first.

Farthest selects customers whose nearest parking location is the farthest to the depot first.

Largest selects customers with the largest demand first.

First in first out (FIFO) selects customers according to their order of insertion in B(S).

When a customer is selected for insertion, it has to be inserted in a walking-trip, starting and returning from a parking location on a route. The insertion position process with parking selection is detailed in Section 4.3). It may happen that no feasible insertion position is found for a customer. In this case, it remains in the request bank and the next customer is selected. This results in a partial solution.

Note that in all repair operators, a parking spot already used by a vehicle is never inserted into another route or in another position on its current route.

Customer insertion

When a customer has been selected to be inserted in a solution, three types of insertions are considered:

• Insertion in a new route: the first customer is inserted into a solution by creating a new route (Figure 2a). Hence, in this insertion a customer is served from a new route and a new parking location.

• Insertion through a new parking location: a customer can be inserted into a new walking-trip, starting from a new parking location (Figure 2b) on an existing route. This operation adds a parking location to the list of used parking spots.

• Insertion through a served parking location: both of the above types of insertions involve stopping at a new parking location, while serving a customer from a served parking location takes advantage of the vehicle being already parked to serve several customers. In this case, all possible insertions on existing walking-trips (Figure 2c), or on new walkingtrips from each served parking spot (Figure 2d) are evaluated.

For each customer insertion, for all insertion types and unless a parking selection strategy applies (as presented in Section 4.4), all insertion positions (all parking and customer positions in walking trips) are evaluated and the best one is inserted. Note that in this process a diversification is obtained by integrating the blink principle of Christiaens and Vanden Berghe (2020): insertions are evaluated with a probability 1 -γ, i.e. they have a probability γ to be ignored.

The performed insertion is the cheapest one among all evaluated insertions. Let us presume that a customer has been selected and our goal is to evaluate its insertion in a new route or through a new parking location. We propose different parking selection strategies. A parking selection strategy is composed of a parking selection criterion and parking selection method.

We consider two criteria to select parking locations from each customer: The first criterion is the walking time between the parking location and the customer (radius-r criterion). The second criterion is the ranking of the parking spot in the list of parking spots ordered by nondecreasing distance to the considered customer (k-nearest criterion). In addition, two methods involve these criteria to reduce the set of evaluated parking spots: The first one filters the parking set from which each customer can be served a priori, keeping the locations below a given threshold on the chosen criterion. In the second method, for each customer a sorted list of parking locations is designed based on the selected criterion. The locations are then evaluated according to this order, with a given probability to stop after each location evaluation. These two methods are detailed below.

Filtering parking locations

Let us presume that, for each customer i ∈ N , a subset of parking locations is selected from P and is referred to as P i ⊂ P . According to the filtering method, when the customer i has to be inserted in a new route or with a new parking location, the location j is considered if and only if j ∈ P i .

Given a parameter r > 0, the radius-r criterion defines P i as the subset of parking spots within r minutes walking time from i, i.e. P i = {j ∈ P |t w ij r}. The k-nearest criterion, with k ≤ 1 defines P i as the subset containing the k nearest parking locations, walking from i.

Note that in a solution, a customer i may still be served from a parking location not included in P i if it has been inserted in an existing trip or through a served parking location.

Sorting parking locations

The second method is denoted sorting. It consists of building, for each customer, a sorted list of parking locations. With both criteria, for each customer i ∈ N , the parkings j ∈ P are sorted in non-decreasing order of t w ij . When inserting a customer i in a new route or through a new parking location, the parking locations are considered according to their order in the customer's sorted list of parking spots.

For the radius-r criterion, for a given parameter r, the list of parking locations is explored while µ ≤ exp (-t w ij /r) where µ ∼ U ([0; 1]) and t w ij is the walking time between the customer i and the parking spot j. As for the simulated annealing criterion [START_REF] Kirkpatrick | Optimization by Simulated Annealing[END_REF], this criterion is designed such that the expected walking time between i and the last parking location explored is around r minutes when the exploration stops.

For the k-nearest criterion, for a given parameter k, the list of parking locations is explored while µ ≤ 1 -1 k , with µ ∼ U ([0; 1]). Let Y be a random variable modeling the number of evaluated parking locations. By definition of a geometric distribution, we can say that Y ∼ Geo( 1 k ), and that its expected value is E(Y ) = k. In other words, the expected position of the parking location in the list when the exploration stops is k.

Computational Results

This section presents the experiments performed with SLNS to solve the PLRP-PS. The algorithm is coded in Julia 1.5.0. The experiments were performed on a PC running Linux, Ubuntu 20.04.2 LTS, equipped with an Intel Xeon Gold 6230 @ 2.10GHz. A single thread is used by our code.

Section 5.1 introduces the instances that were generated for these experiments based on realistic data. Section 5.2 compares the different parking selection strategies. SLNS is evaluated on the PLRP, and our results are compared to those of [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF] and [START_REF] Cabrera | The Doubly Open Park-and-loop Routing Problem[END_REF] in Section 5.3. Finally, numerical studies are performed in Section 5.4 to evaluate the impact of various delivery area configurations.

Instances and parameters

We created realistic instances based on open data from Nantes Metropole1 , as well as on the official French open data platform2 .

The set of parking locations is taken from the "Loading zones in downtown Nantes" dataset3

(Figure 3a). The customer locations were obtained with filters: "active," "accommodation," and "catering locations" in "Loire-Atlantique" on the dataset "SIRENE database of companies in Nantes Metropole"4 (Figure 3b). Our full dataset encompasses 352 loading zones (Figure 4a) and 1196 customer locations within walking range of a loading zone (Figure 4b). The depot, represented by the black circle on the left of Figure 4b, is located outside of the city center.

Real-world distances and travel time matrices were obtained with openrouteservice backend5 . The driving speeds are heuristically computed by this software based on the legislation and road characteristics. A walking speed of 4.8km/h is assumed. All visualizations were created using Open Street Map6 . This data set is used to generate five sets of instances, including between 50 and 400 customers. For each instance size, ten instances were generated, taking customer locations at For the sake of readability, driving paths between the depot and parking locations or loading zones are replaced by dashed lines. Driving and walking paths are obtained with the openrouteservice backend 5 .

Table 2 summarizes the default parameter values taken for SLNS and for the PLRP-PS that were used in our experiments. The parameters of the parking selection strategies will be thoroughly investigated in Section 5.2. The time budget used in SLNS for each instance size n = {50, 100, 200, 300, 400} is {1, 3, 10, 20, 40} minutes, respectively.

PLRP-PS:

k max ∞ (to be minimized) Q d 50 Q w 10 pt 5 minutes w max 8 kilometers h max 420 minutes (i.e 7h) SLNS: initial solution Largest repair operator [δ small , ∆ small ] [0.05|N |, 0.10|N |] [δ large , ∆ large ] [0.10|N |, 0.20|N |] ω |N | 1.5 β 20 γ 10%

Selection of parking locations

This section provides insights into the main focus of this paper: the selection of parking locations in SLNS. In this section, we present different results of SLNS on the PLRP-PS, focusing on the parking selection parameters introduced in Section 4.4, comparing the filtering and sorting methods as well as the k-nearest and radius-r criteria. To find the best parking selection method, the different strategies were tested with different parameter values. In addition, as a base case, we consider the no-filter (x5) configuration in which the maximum runtime is multiplied by five and no selection method is applied (all parking locations p ∈ P are evaluated in all types of insertion). Then, the results of these configurations are compared to the best-known solutions (BKS) with different measures: number of BKS found (i.e gap is zero), average gap, and maximum gap. The gap is computed such as ∆ = z-BKS BKS ×100, where z is the sum of driving time, walking time, and parking time.

Table 3 synthesizes the results of these experiments (the detailed results are provided in Appendix in Table A.7).

For each configuration, all instances are solved five times and the best solution out of these five runs is kept. Each line corresponds to a configuration. The configurations are first grouped by strategy: k-nearest or radius-r. Secondly, they are grouped by approach: filtering or sorting.

Then, Column 3 specifies the value of r (in minutes) or k (in number of parking locations). Finally, Columns 4, 5, and 6 give the number of best known solutions found, the maximum gap, and the average gap, respectively.

From these experiments we find that the k-nearest parking selection strategy outperforms the radius-r strategy. An interpretation is that the duration radius r integrates too many parking locations for customers in dense areas, and not enough when customers are isolated. On the contrary, the k-nearest criterion considers a limited and controlled number of parking locations for customers regardless of the density of parking locations. To understand the poor performance of the filtering strategy with r=5 or r=10, let us have a deeper look into the solution of instance nantes-50-1. For the r = 5 radius criterion with the filtering parking selection method, the best solution has a total working time of 394.1, with a driving time of 80.4, a walking time of 258.7 and a parking time of 55. On the other hand, for the k = 10 nearest criterion with the filtering method, the best solution has an overall working time of 326.5 with a driving time of 78.8, a walking time of 157.7, and a parking time of 90. With too few possibilities to start new walking trips from new parking locations, the insertion algorithm mainly inserts in existing trips, resulting in a solution with long walking trips.

As far as the k-nearest parking selection criterion is concerned, the filtering method with k = 10 and the sorting method with k = 5 both perform well. Let us denote them filtering-k10 and sorting-k5, respectively. The sorting-k5 strategy has better average and maximum gaps, but filtering-k10 seems to provide more best-known solutions.

Figure 4 presents a more detailed comparison of these two strategies. The results are aggregated per instance size. In this table the column #Best indicates the number of instances for which each strategy allows one to find the best solution out of the solutions given by the two strategies. An additional column #veh indicates the average number of vehicles in each category of instance. The first thing to notice here is that, when compared only to filtering-k10, the sorting-k5 strategy is often better than filtering-k10. This comforts the slight superiority of sorting-k5 over filtering-k10 in our experiments. Nevertheless, the two strategies remain very close. In particular, they find the same average number of vehicles per category.

According to these results, the following experiments are performed using the sorting-k5 strategy.

Computational experiments on benchmark PLRP instances

The performance of the proposed SLNS is evaluated in the PLRP, in which the set of parking locations is restricted to the set of customers. PLRP instances can be obtained from the VRP-TR instances of [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF] instances are available online7 and they have been solved under these assumptions by the VNS of [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF] and the matheuristic of [START_REF] Cabrera | The Doubly Open Park-and-loop Routing Problem[END_REF]. [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF] minimize the sum of driving distances. To adapt our method, the time needed to park is fixed to zero and the walking cost is obtained by multiplying all walking distances by a small value ε. The constraints used by [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF] to solve their instances are as follows: a maximum overall walking distance for each worker of 5 km (here named w max = 5) and a time horizon of 7h (here h max = 420). These instances also contain a service duration at each customer. This service duration is not considered as a part of the objective function but it is used to evaluate the day duration constraint.

For this set of experiments, the time limit of SLNS is set to 15, 30, 60, and 120 seconds for the 20, 30, 40, and 50 customers instances, respectively. These values are chosen very close to the average run-times of [START_REF] Cabrera | The Doubly Open Park-and-loop Routing Problem[END_REF], who used a limited number of iterations. The average run-times of [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF] are significantly greater (6779 seconds for 50 customer instances). Ten runs are performed for each instance.

Table 5 synthesizes the comparison between the proposed SLNS algorithm, the VNS of [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF], and those of the matheuristic of [START_REF] Cabrera | The Doubly Open Park-and-loop Routing Problem[END_REF] (denoted MH).

The detailed results for each instance can be found in Table A.6. Similarly to the previous tables, each line represents averaged results for each instance size. For each method, the columns indicate the number of BKS (including our solutions), the maximum gap to the best known solution (in %), and the average gap to the best-known solutions (in %). From these experiments we find that, with equivalent computing times, SLNS finds a little more BKS than MH though it is not always on the same instances. New BKS are found for eleven instances. Overall, SLNS misses only seven BKS over the set of forty instances. In addition, SLNS has the smallest average gap (0.14%) on average, while MH has a slightly better average for maximum gaps. It can be noted that with slightly longer run-times (600 seconds on all instances), the SLNS average of average gaps falls to 0.05, while the average of maximum gaps falls to 0.44.

In conclusion, SLNS offers competitive results on the PLRP. With equivalent run-times, the results slightly outperform the elaborate matheuristic of [START_REF] Cabrera | The Doubly Open Park-and-loop Routing Problem[END_REF]. It also has the advantage of being simple to design and easy to integrate in classical VRP heuristics.

Managerial insights

The objective of this section is to evaluate the impact of integrating parking selection and walking trips in vehicle routing. Therefore, we present computational experiments in which the PLRP-PS is solved with different parameter values and compared with the CVRP and PLRP. These experiments are led on the Nantes instances presented in Section 5.1. We evaluate the impact on driving time, walking time, and parking time as well as the number of times vehicles park as the number of possible parking location increases.

As described in the previous section, our SLNS for the PLRP-PS can solve the PLRP by limiting the set of parking locations to the set of customers (P = N ). It can also be used to solve a CVRP by taking P = N and setting the maximum walking distance per driver, w max to zero.

Impact of different compositions of the parking locations set

In the following experiments, we compare the solutions obtained with SLNS when solving the Nantes instances as CVRP, PLRP, or as PLRP-PS. In the latter case, we consider two sets of parking locations: either the set of loading zones (denoted LZ), or the set made of parking at each customer location, plus the loading zones (denoted C+LZ). The parking time pt is set to five minutes in all cases. Figure 6 presents a breakdown of the objective function value between driving time, parking time, and walking time, on average for each PLRP-PS instance size, divided by the number of customers, for the different problem settings. The first observation is that all PLRP variants achieve a reduction in cost with respect to the CVRP. In more detail, the PLRP solutions reduce driving time by 16% and parking times by 72% compared to the CVRP. Moreover, the PLRP solution costs are on average 35% cheaper. This indicates that, even when parking at customers in city centers takes reasonable time, walking to serve several customers from one parking location should be considered as a way to reduce cost. Comparing the PLRP-PS(LZ) to the CVRP, the driving time is reduced by 19%, the parking time is reduced by 80% and the objective value is reduced by 30%. The difference of reduction of the objective value between the PLRP and PLRP-PS(LZ) is due to the walking time. In the latter case, the average walking time is 50% greater than for the PLRP. Still looking at the overall cost, it is interesting to note that the relative cost saving is greater for the PLRP variants when the number of customers is high. This indicates that park-and-loop efficiency increases with the density of customers, which was expected.

Secondly, the results for the PLRP are very similar to the ones with PLRP-PS(C+LZ) where all customers and delivery areas are considered parking locations. These results indicate that it is more efficient to park at customers when it is possible. Looking at the detail of driving, parking, and walking times, parking at customers mainly reduces the walking time while driving and parking times are higher.

To further analyze the PLRP and PLRP-PS solutions, Figure 7 represents the average number of parking instances per customer (i.e. the number of used parking locations divided by the number of customers) for each instance size and each PLRP variant.

Parking at customers is represented in orange, while parking at loading zones is in green. Let us recall that some parking at customers have been added to the PLRP-PS(LZ) parking locations for customers that are too far from a loading zone. The figure confirms that parking at customers is mostly used in PLRP-PS(C+LZ) solutions. When parking farther from customers (i.e. in PLRP-PS(LZ) solutions), fewer parking locations are used.

It is also worth noting that the average number of parking instances per customer decreases when the number of customers increases. This confirms that the greater the density of customers, the more efficient the park-and-loop practice.

Impact of parking time

When comparing the different variants of the PLRP-PS, there is no doubt that parking time is of uttermost importance. To evaluate its impact, we compare the solutions of the PLRP-PS with different values of pt ∈ {0, 3, 5, 15} (in minutes). The parking set is the set of loading zones (PLRP-PS(LZ)). Figure 8 shows the impact of parking time variations. For each value of pt and each instance size, the bar chart shows the average driving time, walking time, and parking time per customer. A first observation is that for all instance sizes, the average driving time per customer remains relatively stable when pt increases. The average parking time per customers in solutions also increases with pt but this increase remains consequently smaller than the increase of pt itself. On the contrary, the walking time significantly increases, especially on small instances. On average, when parking time increases from pt = 0 to pt = 5, the average driving time per customer is reduced by 10% and the walking time is increased by 44%. Looking at the impact on the overall working time, increasing the parking time from pt = 0 to pt = 5 generates a limited increase of working time by less than three minutes per customer for the least favorable instances (N = 50). As far as the 400-customers instances are concerned, this increase is even reduced to one minute and seventeen seconds on average. This confirms that considerable savings can be generated by the park-and-loop practice when parking requires significant time.

Looking at the number of parking instances per customer on Figure 9, we observe that when pt increases, the proportion of parking locations used decreases. For instance, when pt = 5 minutes, the average number of parking locations used in solutions is reduced by 59% compared to solutions where pt = 0. It is worth observing that even when the parking time is null, a parking spot is generally used to serve several customers. This can be explained by the fact that not every customer is necessarily in the immediate vicinity of a loading zone.

Conclusion

In this paper, we introduced the Park-and-Loop Routing Problem with Parking Selection (PLRP-PS), which is an extension of previous vehicle routing problems where customers are served through a combination of walking and driving, presented under the denomination Parkand-Loop Routing Problem (PLRP). The PLRP-PS captures practical aspects of urban delivery by integrating the selection of a parking location into vehicle routing. To solve this problem, we proposed a Small and Large Neighborhood Search (SLNS) metaheuristic combining recent progress in the large neighborhood search meta-heuristic. We led extensive computational experiments that focus on the integration of parking selection strategies in vehicle routing heuristics. We compared four parking selection strategies which are integrated in the repair operators of SLNS. These strategies are evaluated in real-world instances built upon public data from the city of Nantes.

We find that selection strategies based on the selection of a number of nearest parking locations for each customer are more efficient than those based on the selection of parking spots within a fixed radius around each customer. Despite its simplicity, we show that SLNS competes with state of the art metaheuristic on existing benchmarks from the literature. Besides, we provide insights on the practical relevance of the PLRP-PS on our instances. Compared to a classical CVRP model, we find that combining driving and walking reduces the driving time needed by 19% on average to deliver to all customers while also decreasing the overall working time by 30%. Most of this saving is achieved by reducing the overall parking time by 80%.

To complete this analysis, we find that the parking time has a major impact on solutions. Indeed, integrating a five-minute parking time reduces the average number of parking locations used in solutions by 59% compared to a situation where the parking time is null.

We conclude that integrating parking selection in heuristics can be efficiently done with simple approaches. In this context, the park-and-loop practice is of significant interest to reduce working and driving time in dense delivery areas. Interesting perspectives would be to investigate the impact of park-on-loop on C0 2 emissions as well as on the integration of temporal aspects such as time windows at customers. (13, 999.38 -300-10 (19, 1596.87) (19, 1579.23) (19, 1417.85) (19, 1378.28) (19, 1395.42) (19, 1384.38)

  Vehicle routes are represented by solid lines and walking trips are represented by dashed lines.

Figure 1 :

 1 Figure 1: Routes and walking-trips representation in the PLRP-PS

Figure 2 :

 2 Figure 2: Types of insertions in PLRP-PS solutions

Figure 3 :

 3 Figure 3: Datasets representation

  Loading zones + reduced customers locations

Figure 4 :

 4 Figure 4: Reduction of the datasets

Figure 5 :

 5 Figure 5: Visualization of the best found solution for instance "nantes-50-1" with 50 customers.

Figure 6 :

 6 Figure 6: Decomposition into driving, parking, and walking time

Figure 7 :

 7 Figure 7: Average number of parking instances per customer and per parking type in the PLRP and PLRP-PS solutions

Figure 8 :

 8 Figure 8: Average time per customer decomposed by driving time, parking time, and walking time

Figure 9 :

 9 Figure 9: Evolution of the average number of parking instances per customer with respect to parking time

Table 1 :

 1 Table 1 presents an overview of the operators that are implemented in the SLNS algorithm. Sets in columns Customer/Parking/Route indicate when they may be used depending on what they operate on. The references in the column source indicate the articles that proposed the considered criteria. Overview of destroy and repair operators

	Type	Name	Customer	Parking Route Source
	Destroy Random Worst Related String Historical Route	Σ -small , Σ -large Σ -small , Σ -large Σ -small , Σ -large Σ -small , Σ -large	Σ -large Σ -large Σ -large Σ -large Σ -large	Σ -large	Ropke and Pisinger (2006a) Ropke and Pisinger (2006a) Hemmelmayr et al. (2012) Christiaens and Vanden Berghe (2020) Pisinger and Ropke (2007) Hemmelmayr et al. (2012)
	Repair	Random Closest Farthest Largest FIFO	Σ + small , Σ + large Σ + small , Σ + large Σ + small , Σ + large Σ + small , Σ + large Σ + small , Σ + large			Christiaens and Vanden Berghe (2020) Christiaens and Vanden Berghe (2020) Christiaens and Vanden Berghe (2020) Christiaens and Vanden Berghe (2020) this paper

Table 2 :

 2 Default SLNS and PLRP-PS parameter values

Table 3 :

 3 Comparison of the parking selection strategies

  , without car-pooling and time windows. These

			filtering-k10			sorting-k5
	n	#Best Max∆ Avg∆ #veh #Best Max∆ Avg∆ #veh
	50	4	0.71	0.17	3.7	6	1.21	0.2	3.7
	100	5	1.07	0.31	6.7	5	1.74	0.35	6.7
	200	3	2.9	0.72	12.3	7	2.02	0.4	12.3
	300	4	1.9	0.84	18.4	6	1.64	0.5	18.4
	400	6	2.2	0.48	24.5	4	2.37	0.61	24.5
	Avg.	22	2.9	0.5	-	28	2.37	0.41	-

Table 4 :

 4 Detailed comparison per instance size of the filtering-k10 and sorting-k5 strategy.

Table 5 :

 5 Comparison on the Coindreau et al. (2019) PLRP instances to the VNS of Coindreau et al. (2019) and the matheuristic (MH) of Cabrera et al. (2022).

https://data.nantesmetropole.fr

https://www.data.gouv.fr

https://www.data.gouv.fr/fr/datasets/aires-de-livraison-du-centre-ville-de-la-ville-de-nantes/

https://data.nantesmetropole.fr/explore/dataset/244400404_base-sirene-entreprises-nantes-metropole/

www.openrouteservice.org and www.github.com/GIScience/openrouteservice

www.openstreetmap.org

https://github.com/ncabrera10/VRPTR_instances

Acknowledgment

We kindly thank Nicolás Cabrera and Jorge E. Mendoza for their insights on the PRLP instances, as well as Gwénaël Rault for his advice about the real-world data.

This research was supported by the Agence Nationale de la Recherche (ANR) under grant ANR-17-CE22-0015. This support is gratefully acknowledged.

Appendix A. Computational experiments results details

Inst

VNS MH SLNS [START_REF] Coindreau | Vehicle routing with transportable resources: Using carpooling and walking for on-site services[END_REF] [START_REF] Cabrera | The Doubly Open Park-and-loop Routing Problem[END_REF] -200-1 (13, 1166.72) (13, 1096.33) (13, 1015.5) (13, 994.3)


Hasnaa Ait Malek
email: hasnaa.aitmalek@mpsa.com

Alain Etienne
email: alain.etienne@ensam.eu

Ali Siadat
email: ali.siadat@ensam.eu

Thierry Allavena
email: thierry.allavena@mpsa.com

A Literature review on the Level of Automation and new approach proposal

Keywords: Automation, Requirements, Indicator, Level of Automation, Time

This paper sheds light on various definitions of the term automation. On the basis of a bibliographical study it hands out a state of the art in terms of the level of automation. The aim of the said paper is to study, analyze and discuss several definitions of the LoA proposed in the literature. On the grounds of this analysis, a set of requirements that ought to be respected by an accurate indicator were given out in order to propound a new definition of the LoA aimed at application in the manufacturing domain and its interest in order to optimize workstations. At the end of this bibliographical study, a table summarizing the list of different definitions, and the requirements that each of them meet is drawn. A proposal for a new definition of LoA as a time ratio is also presented. Furthermore, the application on an academic case study on an assembly line with 13 operations helped us demonstrate its interest.

Introduction

The word "automation" appeared in April 1947 in the department of Ford's vicepresident, Del Harder, who wanted to use technology to change production rates and increase the productivity of automotive assembly lines [START_REF] Lorre | L'automatisation industrielle, quel avenir pour les usines du futur? Transhumanisme et Intelligence Artificielle[END_REF]. In 1997, Parasuraman and Riley [START_REF] Parasuraman | Humans and Automation: Use, Misuse, Disuse, Abuse[END_REF] defined automation as the performance by a machine (usually a computer) of a function previously performed by a human. Thus, according to Claverie [START_REF] Claverie | COGNITIQUE -Science et pratique des relations à la machine à penser[END_REF], the automation of processes has changed working conditions and the role of human in industry. The latter has become, instead of an actor, a designer, maintenance agent or supervisor. In 2016, Vagia, Transeth and Fjerdingen [START_REF] Vagia | A literature review on the levels of automation during the years. What are the different taxonomies that have been proposed?[END_REF] presented another definition of automation. For them, this term refers to a system that will perform the tasks for which it is programmed without having the choice or possibility to act differently. Its actions are predefined from the beginning and it has no possibility to change them in the future.

Today, the technological challenge for manufacturers is to have a versatile production line, flexible to the product and volume [START_REF] Wiendahl | Changeable Manufacturing -Classification[END_REF]. Therefore, choosing a good level of automation will avoid unnecessary investments in inadequate technological solutions. Establishing a good level of automation from the design phase of the line will avoid the enormous costs of changing the production line in case we realize the unsuitability after its implementation. So the objective of our work is to group together the operations that can be automated in order to make the investments profitable and optimize the workstations. Which leads to this scientific question: "How to qualify the level of automation of a work station? "

The purpose of this paper is to present and analyze the different approaches proposed in recent years on the level of automation in order to finally propose a new quantitative approach.

2

The Level of Automation

Currently, there is no consensus on the definition of the level of Automation. In fact, the decision about automation should be driven based on several parameters and decision criteria. Therefore, this section introduces this concept by addressing the different approaches found in the literature. The objective is to come up with a new scale proposal for evaluating this indicator.

There are many definitions of the LoA concept. The method of evaluation is not the same, some studies propose a quantitative evaluation while others are moving towards a qualitative approach.

2.1

LoA defined as a degree of evolution of the expert system in decision-making

One of the oldest definitions that can be found in the literature is proposed by Sheridan and Verplank [START_REF] Sheridan | Human and Computer Control of Undersea Teleoperators[END_REF] and repeated in various works [START_REF] Parasuraman | A model for types and levels of human interaction with automation[END_REF] [START_REF] Gavan Lintern | Development of a Supervisory Control Rating Scale[END_REF]. The authors [START_REF] Sheridan | Human and Computer Control of Undersea Teleoperators[END_REF] identified six functions that a human operator or computer could perform during an operation: Requests, Gets, Selects, Approves, Starts and Tells. The authors explain how the human operator and the computer are supposed to cooperate under different LoAs for each of these commands. In this sense, the authors define automation as a total or partial replacement of a function previously performed by the human operator. This implies that automation is not total or non-existent, but that it can vary according to different levels. The Table 1 presents the 10 levels of LoA, defined by Sheridan and Verplank [START_REF] Sheridan | Human and Computer Control of Undersea Teleoperators[END_REF].

For example, at low level 2 (Table 1), several options are offered to humans, but the system has no say in the decision. At level 4, the computer suggests an alternative decision, but the human being retains the power to execute this alternative or choose another one. At a higher level 6, the system gives human only a limited amount of time to exercise his right of veto before making a decision.

LoA Description

Level 1 Fully manual control, the computer offers no assistance Level 2

The computer offers a complete set of alternatives. Several options are offered to human who decides Level 3

The computer reduces the number of alternatives, and it is always the human who decides Level 4

The computer suggests only one option, human can decide whether or not to follow it Level 5

The computer executes the option if the human approves it. The approval of human is necessary Level 6

The computer leaves a limited time to the human to decide before executing the action Level 7

The computer executes the action automatically and informs the human Level 8

The computer informs the human if he requests the information Level 9

The computer informs if it considers it necessary Level 10 Full control of the computer. It decides everything and acts independently In this definition, the authors proposed a very broad and detailed explanation on computer and human operator cooperation under different LoA degrees from fully manual to fully automated. However, this definition is more oriented towards the control of systems than the operational part.

LoA defined as a degree of automation of physical and cognitive operations

In 2008, Frohm, Lindström and Winroth [START_REF] Frohm | Levels of Automation in Manufacturing[END_REF] defined the level of automation as the allocation of physical and cognitive operations between humans and technology. Indeed, for them, LoA is presented in two degrees: one for physical operations, and the other for cognitive operations. The Table 2 presents the seven LoA levels proposed by the authors. The degree of description is fairly accurate and complete. However, the scale can lead to confusion. We don't understand the value of establishing two levels; a static hand tool (LoA = 2) and a totally manual (LoA = 1). Using a manual tool (such as a screwdriver or hammer) doesn't change the decision about automation. The level for us should always be manual. Another problem concerns levels 3 (Flexible hand tool) and 4 (Automated hand tool). In fact, a flexible hand tool can be automated, such as an automatic screwdriver for which the drills calibers can be changed to deal with different screw sizes or types. The last point concerns level 7 (fully automatic). It can be flexible, such as robotic or reconfigurable stations. We believe that this scale describes the levels excluding new advanced robotic solutions that cannot be exclusively classified in a single category of the proposed scale. In addition, level 5 of static machine can in some cases be confused with level 7 of fully automatic. In fact, a dedicated static machine can operate autonomously and can be fully automatic.

2.3

LoA defined as a degree of intelligence and autonomy

In 1989, Riley defined a general model of human-machine interaction. His model presents factors that define 7 levels of intelligence (Table 3) and 12 levels of autonomy (Table 4) [START_REF] Adams | Mixed-Initiative Interaction and Robotic Systems[END_REF]. Each combination of an intelligence level and an autonomy level is called an automation state and each state corresponds to predefined and unique form [START_REF] Riley | A General Model of Mixed-Initiative Human-Machine Systems[END_REF].

Intelligence Level Description

Level 1 Manual operations Level 2

Processing of available information Level 3

The system cannot perform any action by itself, unless it advises the operator Level 4

Recommendations: The machine has no power to act and is limited to communication with the operator Level 5

Recommendations with interaction: The machine does not have the power to act and is limited to communication with the operator Level 6

Adaptive recommendations: The machine has no power to act and is limited to communication with the operator Level 7

The machine is a servant and has the possibility to perform actions

Autonomy Level Description

Level 1 Manual operations Level 2

Processing of available information Level 3

The system cannot perform any action by itself, unless it advises the operator Level 4

Recommendations: The machine has no power to act and is limited to communication with the operator Level 5

Recommendations with interaction: The machine does not have the power to act and is limited to communication with the operator Level 6

Adaptive recommendations: The machine has no power to act and is limited to communication with the operator Level 7

The machine is a servant and has the possibility to perform actions Level 8

The machine is an assistant and can perform actions but requires operator approval

Level 9

The machine is associated and can perform actions autonomously without explicit authorization from the operator, but the operator can always replace it Level 10

The machine is a partner and has the same rights as the operator Level 11 The machine is a supervisor and can replace the operator who has no authority Level 12 Fully autonomous operation

In the first six levels of autonomy (Table 4), the machine has no authority to act; it is limited to communication with the operator. The last six levels give the machine the possibility to act. The distinctions between these levels of autonomy are based on the sophistication of the machine's information processing functions and the authority to manipulate the operator's screens. For example, an Associated machine is autonomous and able to perform actions without the explicit authorization of the operator, but the operator can always cancel it. A Partner machine has the same derogation power as the operator, and a Supervisor machine can replace the operator, but the operator cannot ignore it [START_REF] Riley | A General Model of Mixed-Initiative Human-Machine Systems[END_REF].

LoA defined as a cost ratio

The level of automation 𝐿 𝑎𝑢𝑡𝑜 can be calculated based on the operating costs of equipment 𝐶 𝑒𝑞ℎ (€/h) and Labor costs 𝐶 𝐿𝑎𝑏 (€/h) [START_REF] Windmark | A Cost Model for Determining an Optimal Automation Level in Discrete Batch Manufacturing[END_REF], as shown in equation ( 1)

𝐿 𝑎𝑢𝑡𝑜 = 𝐶 𝑒𝑞ℎ 𝐶 𝑒𝑞ℎ + 𝐶 𝐿𝑎𝑏 (1)
When the ratio 𝐿 𝑎𝑢𝑡𝑜 is zero, it is assumed that production is entirely manual; the operating cost of the equipment is negligible compared to the cost of Labor. When this ratio is equal to 1, it is the Labor cost that is negligible compared to the operating cost of the equipment, so production is fully automated.

This approach has the advantage of describing the LoA in a quantitative way. However, it does not provide a true picture of the rate of automation in a workshop. The definition of cost is not sufficiently representative. For example, if we consider a workshop of 8 workstations, with 2 automated workstations at a high cost. The ratio 𝐿 𝑎𝑢𝑡𝑜 will be close to 1, without a high automation rate. This limit more significant in countries where investment and operating costs are significantly higher than Labor costs. Thus, this approach does not reflect the actual level of automation of a production line.

An analysis of the various works in the literature shows that most of the proposed approaches address the entire process and lack precision in describing the Level of automation of each workstation or operation.

Requirements and Suggested LoA definition

The purpose of the bibliographic study that was carried-out is to analyze the different definitions of levels of automation presented in the literature. An appropriate definition and scale must first be established to be able to describe all possible automation scenarios before making a decision.

Requirements

Our scale must be applicable for existing production systems (R1) and applicable for future production systems (R2). A good indicator should be quantitative (R3), measurable data that can be easily monitored to maximize or minimize our LoA as needed. The scale must concern the operating mode (R4), i.e. the physical operations that the machine or human can perform. A good definition of LoA must be objective (R5) and can allow decision making according to a methodology rather than intuition. The indicator must allow partial automation (R6), and therefore have levels between fully manual and fully automatic. And finally, the scale must give a clear vision to decision-makers on the operator and machines load (R7), which allows to study the line balancing and take into account the profitability aspect. The Table 5 summarizes the different approaches identified with the requirements they meet. It can be noted that none of the proposed definitions in the literature respect all the requirements. Nevertheless, all definitions are applicable. Most of them are qualitative and allow partial automation. There is only one definition that is quantitative, but unfortunately, it takes cost as a criterion, which really does not give a clear vision of the level of automation. However, none of the definitions found in the literature take into account the operator and machines load aspect.

Suggested LoA definition

We appreciate defining a good level of automation as the best allocation of resources and their associated levels of automation. The indicator chosen to quantify the LoA is Time, which makes it possible to study the load of operators and the load of automated tools, in order to get a clear vision of line balancing.

To improve decision support methods for assembly line automation, it is necessary to develop a new definition of the LoA. Therefore, the definition proposed will be at the workstation level and not at the level of the entire process. This allows us to analyze all operations and suggest several automation scenarios to choose the optimal one. The level of automation must be quantitative and must vary from fully manual to fully automated with intermediate levels to represent human-machine collaboration. The indicator chosen to quantify the LoA is Time. Hence, the proposed LoA is defined as a time relationship between the time of automated operations 𝑇 𝑎𝑢𝑡𝑜 (min) and the cycle time 𝑇 𝑐 (min) as shown in equation [START_REF] Parasuraman | Humans and Automation: Use, Misuse, Disuse, Abuse[END_REF].

𝐿𝑜𝐴 = 𝑇 𝑎𝑢𝑡𝑜 𝑇 𝑐 (2)
If the LoA ≈ 0%, the workstation is completely manual; the only resource is human. If the LoA ≈ 100%, the workstation is fully automated; the only resource is the machine. Between the two levels, the station is semi-automated; the two resources present are human and machine.

4

Case study

For reasons of confidentiality, we have presented in this paper an academic case study. The Fig. 1 shows a production line with several workstations. The analysis is done on the first workstation with a cycle time equal to 1.86 min. The tasks done by the operator are presented in Table 6 which also shows the time (in min) for each of the operations. According to this configuration, 𝐿𝑜𝐴 = 0%; the station is totally manual. If we decide to automate the picking and dropping of parts, Op1, Op2, Op7, Op8 and Op9 will be suppressed. Op3, Op4, Op5 and Op6 will be fully automated so 𝑇 𝑎𝑢𝑡𝑜 = 0.5 𝑚𝑖𝑛. In this case, 𝐿𝑜𝐴 = 27%. The indicator shows that 27% of the operations on the first workstation are automated. Therefore, we know the availibility of the operator which allows us, not only, to optimize and improve the workstation, but also to balance the line to make it more efficient.

Manipulator

The reasons for automating can be seen from different viewpoints either to reduce labor costs, to increase the quality level or to solve ergonomic problems. Our approach is limited since it takes into account only the physical operations therefore a second approach should be considered so as to integrate other aspects related to work conditions such as mental workload, ergonomics etc.

Conclusion

In this paper, we have presented a review of different definitions of the Level of automation. We also discussed and analyzed each one of them in order to allow the reader to understand the difference between these definitions. We went through three main points: the LoA definition in the literature, the difference between each of these definitions and the chosen criteria for an appropriate definition. Finally, we have listed a set of requirements that a good definition of LoA must respect, and based on these requirements, we proposed a quantitative definition of the LoA that was applied on an academic case study.

Fig. 1 .

 1 Fig. 1. Fictive production line and presentation of the operations and the different operator's positions

Table 1 .

 1 Definition of LoA proposed by Sheridan and Verplank [

6]

Table 2 .

 2 Definition of LoA proposed by Frohm, Lindström et Winroth [9]

	LoA	Physical operations	Cognitive operations
	Level 1	Totally Manual	Totally manual
	Level 2	Static hand tool : Manual work	Decision giving : The user gets information
		with support of static tool	on what to do, or proposal on how the task
			can be achieved
	Level 3	Flexible hand tool : Manual	Teaching : The user gets instruction on how
		work with support of flexible tool	the task can be achieved
	Level 4	Automated hand tool : Manual	Questioning : The technology question the
		work with support of automated	execution, if the execution deviate from
		tool	what the technology consider being
			suitable
	Level 5	Static machine/workstation :	Supervision : The technology calls for the
		Automatic work by machine that	users' attention
		is designed for a specific task
	Level 6	Flexible machine/workstation :	Intervene : The technology takes over and
		Automatic work by machine that	corrects the action
		can be reconfigured for different
		tasks
	Level 7	Totally Automated	Totally automated

Table 3 .

 3 Riley's proposed intelligence levels[START_REF] Vagia | A literature review on the levels of automation during the years. What are the different taxonomies that have been proposed?[END_REF]

Table 4 .

 4 Riley's proposed autonomy levels[START_REF] Vagia | A literature review on the levels of automation during the years. What are the different taxonomies that have been proposed?[END_REF]

Table 5 .

 5 Table summarizing the different approaches identified in the literature with and the requirements they meet

	Authors	R1	R2	Requirements R3 R4 R5	R6	R7
	Sheridan and Verplank	X					X
	Frohm, Lindström and Winroth	X			X		X
	Riley	X			X		X
	Windmark, Gabrielson, Anders-son and StOEhl	X	X	X	X	X	X

Table 6 .

 6 Description of the operations done by the operator, his position and the duration of each one of them

	Operation	Description	Position	Time (min)
	Op 1	Move to the manipulator's zone	B	0.1
	Op 2	Take the manipulator	A	0.02

Acknowledgments

This work took place in the framework of the OpenLab Materials and Processes combining Arts et Métiers network, GeorgiaTech Lorraine and Groupe PSA.