Philippe Grangier
email: philippe.grangier@mines-nantes.fr

Michel Gendreau
email: michel.gendreau@cirrelt.ca

Fabien Lehuédé
email: fabien.lehuede@ls2n.fr

Louis-Martin Rousseau
email: louis-martin.rousseau@polymtl.ca

A LNS and branch-and-check approach for a VRP with cross-docking and ressource synchronization

Resource synchronization constraints are a major rising features of many city logistics and transportation problems. Such type of constraints typically arise from limited parking spaces at logistics warehouses or hubs

Introduction

In logistics, cross-docking is a distribution strategy in which goods are brought from suppliers to an intermediate transshipment point, the so-called cross-dock, where they may be transferred (without storing) to another vehicle for delivery. Compared to traditional distribution systems, cross-docking can help reducing delivery costs and delivery lead time, that is why it is used by many companies from different sectors: LTL, retail or automotive for example [? ]. In the vehicle routing literature, the associated routing problem is called the Vehicle Routing Problem with Cross-Docking (VRPCD). It is a variant of the Pickup and Delivery Problem with Transfers with one compulsory transfer point: vehicles start by collecting items, then return to the cross-dock where they unload/reload some items and eventually visit delivery locations. A few authors have proposed methods to solve this problem or variants of it, but to our knowledge, in most models there is no limit on the processing capacities of the cross-dock: as soon as a truck arrives, it immediately undergoes consolidation operations. However in practice, this may not be the case because of limited equipment or workforce, and trucks may have to wait before being unloaded. In fact, a wide range of the cross-docking literature is dedicated to the scheduling of operations at the cross-dock taking into account the cross-dock capacity. It has recently been pointed out [? ? ], that there is a need to consider the synchronization of local and network-wide cross-docking operations, in particular to take into account resource capacity at the cross-dock. To that end, in this paper, we introduce a new variant of the VRPCD in which the number of vehicles that can simultaneously be processed at the cross-dock is limited. We call it the Vehicle Routing Problem with Cross-Docking and Resource Constraints (VRPCD-RC). The dock resource constraint, is a resource synchronization constraint as defined by Drexl [? ] as vehicles compete to access a scarce resource: the processing capacity of the cross-dock. Very often resource synchronization constraints imply a difficult scheduling problem which is embedded within the vehicle routing problem. VRPCD-RC is no exception and the main contribution of this paper is on the integration of the scheduling problem associated with the dock resource constraints within a recently proposed large neighborhood search based method [? ] for the VRPCD.

The remainder of this paper is organized as follows. A literature review is presented in Section 2, while the problem is defined in Section 3. In Section 4, we recall the method of [? ], and Section 5 is devoted to the its adaptation to VRPCD-RC. Eventually, computational results are presented in Section 6.

Literature review

In this section we review the literature on two related vehicle routing problems: the vehicle routing problem with cross-docking and vehicle routing problems with resource synchronization.

The vehicle routing problem with cross-docking

A lot of cross-docking related problems exist such as: location, assignment of trucks to doors, inner flow optimization or routing. In particular, the vehicle routing problem with cross-docking consists in designing routes to pick up and deliver a set of transportation requests at minimal cost using a single cross-dock. It was introduced by Lee et al. [? ] in a variant which imposes trucks to arrive at the exact same time at the cross-dock. Wen et al. [? ] relaxed this last constraint only imposing precedence constraints based on the consolidation decisions and added time windows. This is the most studied variant, and it is the one we will refer to as the vehicle routing with cross-docking (VRPCD). Several heuristics have been proposed to solve it: based on tabu-search [? ? ? ? ], iterated local search [? ] and large neighborhood search

Resource synchronization

The expression resource synchronization appears in [? ] as a way to model the following constraint: 'The total consumption of a specified resource by all vehicles must be less than or equal to a specified limit.' Of course, this resource has to be scarce to be constraining, as vehicles compete to access it. Such resource constraints arise in many different vehicle routing problems usually when a special infrastructure or equipment is required: a docking station or parking space in airport cargo system [? ], a berth in maritime transportation [? ], a forest loader in forestry [? ], a pump in ready mix-concrete delivery [? ], an asphalt paver in public works [? ]. Limited storage [? ] or processing capacities [? ] can also account for resource synchronization constraints. Hempsch and Irnich [? ] also mention a situation where only a fixed number of vehicles (smaller than the total number) can perform long routes. Many approach have been applied to deal with these resource constraints in vehicle routing problems. In [? ], Ebben et al. sequentially insert requests and check resource constraints in a predefined order. In [? ], El Hachemi et al. use a dedicated constraint programming model, later combined with a greedy scheduling heuristic in [? ], to ensure that resource constraints are satisfied during their entire solving process. In ready-mix concrete routing problems as well as in public works routing problem, orders are larger than truck capacity, as such they have to be split into several delivery operations that should not overlap. Resource synchronization constraints arise at pickup sites or at delivery sites or at both. Asbach et al.

The vehicle routing problem with cross-docking: model and resource synchronization constraint

This section presents the vehicle routing problem with cross-docking, and in particular the cross-dock model, as defined by Wen et al. [? ]. It also introduces the two considered cross-dock resource models .

The vehicle routing problem with cross-docking

In the VRPCD, we consider a cross-dock c, a set of requests R, and a homogeneous fleet of vehicles V , each of capacity Q and based at o. Each request r ∈ R has to be picked up at its pickup location p r within its pickup time window [e pr , l pr ], and has to be delivered at its delivery location d r within its delivery time window [e dr , l dr ]. In case of early arrival, a vehicle is allowed to wait, but late arrivals are forbidden. We denote by P the set of pickup locations and by D the set of delivery locations. Each vehicle starts at o, then goes to several pickup locations, arrives at the cross-dock where it unloads/reloads some requests. A vehicle then visits delivery locations and eventually returns at o. Note that a vehicle has to visit the cross-dock even if it does not unload nor reload any requests there. The sequencing of operations at the cross-dock is described in 3.2. The VRPCD is defined on a directed graph G = (V, A), with G = {o}∪P ∪{c}∪D and

A = {(o, p)|p ∈ P } ∪ P × P ∪ {(p, c)|p ∈ P } ∪ D × D ∪ {(d, e)|d, e ∈ D} ∪ {(d, o)|d ∈ D} ∪ {(o, c), (c, o)}.
With each arc (i, j) ∈ A is associated a travel time t i,j and a travel cost c i,j . Solving the VRPCD involves finding |V | routes, and a schedule for each route, such that the capacity and time-related constraints are satisfied, at minimal routing cost. An arc-based mathematical formulation can be found in [? ].

Precedence constraints at the cross-dock

Following [? ], if a vehicle k has to unload a set of items R - k and reload a set R + k at the cross-dock, the time spent at the cross-dock can be divided into four periods:

• Preparation for unloading. The duration δ u of this period is fixed.

• Unloading of requests. The duration of this period depends on the quantity of items to unload. For vehicle k the duration is ( i∈R - k q i )/s u , where s u is the unloading speed in quantity per time unit. All unloaded items become available for reloading at the end of this period.

• Preparation for reloading. The duration δ r of this period is fixed.

• Reloading of requests. The duration of this period depends on the quantity of items to reload. For vehicle k the duration is ( i∈R + k q i )/s r , where s r is the reloading speed in quantity per time unit. All the items for loading must have been unloaded before the beginning of the reloading operation (preemption is not allowed).

Items that are not transferred at the cross-dock remain in the vehicle. Thus, if a vehicle does not unload or reload it need not spend any time at the cross-dock and can leave immediately.

Resource constraints models at the cross-dock

According to Van Belle et al. [? ], the most common service mode of a cross-dock is called exclusive. In an exclusive mode, a dock door is either exclusively dedicated to unloading (inbound operations) or reloading (outbound operations). Such affectation is a decision taken at a strategical or tactical level which cannot be modified in the VRPCD, which is an operational problem. In practice most cross-docks are I-shaped [? ], with inbound doors on one side and outbound doors on the other. The flow of items is thus uni-directional, which can be easier to manage. This is a common situation but it is not mandatory. Cross-docks usually have many doors (typically ranging from 40 to 150 according to [? ]). However, as mentioned in [? ] or [? ], processing capacities may actually be lower than the number of doors. This comes from a limited workforce or special equipment to move the items within the cross-dock. Because of the previous two considerations regarding operations at the cross-dock, we will consider two exclusive cross-dock models that integrate resource constraints:

• a case in which the total number of doors (both inbound and outbound) that can be processed simultaneously is limited to a number S. This is a simple way to model resource constraints due to limited workforce. We refer to this case as shared.

• a case in which the number of inbound doors (resp. outbound doors) that can be processed simultaneously is limited to a number I (resp O). This is a simple way to model a resource constraints due to special equipment. We refer to this case as separated.

Provided that at least two dock doors can be processed simultaneously, the scheduling problems at the cross-dock is NP-Hard as the scheduling problem P 2||C max is included in them. In the rest, we will simply use dock to refer to the capacity in the number of docks processed simultaneously. We call the VRPCD with these dock resource constraints, vehicle routing problem with resource constraints (VRPCD-RC). Figure 1 illustrates the sequencing of consolidation operations for a vehicle that unloads and reloads items at the cross-dock in the VRPCD-RC. When the vehicle arrives at the cross-dock, it can immediately be prepared for unloading, but it has to wait before being actually unloaded (W U ) because of a lack of available resources (note that such waiting time does not exist in the VRPCD). Once the unloading operation is done, the vehicle can proceed and move to an outbound door. Again preparation operation can be performed immediately, but it may wait before being actually reloaded (W R ). This waiting time can have two origins: first, not all items are available when it is ready (such situation can also arise in the VRPCD), second, there maybe a lack of available resources (which cannot occur in the VRPCD).

Prep. U. Unloading Prep. R. Reloading

W U W R t

Matheuristic of Grangier et al. [? ] for the VRPCD

In a previous paper [? ], we proposed a matheuristic to solve the VRPCD, called LNS+SPM (Large Neighborhood Search + Set Partitioning and Matching). To our knowledge, this method is currently one of the best heuristic for the VRPCD. A sketch of LNS+SPM method is given in Algorithm 1. In details, the main component is LNS(l. 4-15), which is enhanced by the occasional solution of an SPM(l.18 and l.23). When the LNS finds a new solution, the pickup part and delivery part, called legs, of each route are added to a memory component (l. 16), called a pool of legs. The SPM aims to create the best possible solution from the legs in the pool. As shown in [? ], this component significantly improves the quality of the solution compared to LNS alone. Hereafter, we recall the methods that are used in the LNS component and the SPM component.

Large neighborhood search

Large Neighborhood Search [? ] iteratively destroys (removes several requests from) and repair (reinserts requests into) the current solution using heuristics. In what follows, the destruction and repair methods used in [? ] are summarized.

Destruction operators

When partially destroying a solution, a destruction method M -and a number Φ of requests to remove are selected. Unless stated otherwise, this method is reused until Φ is reached. The transfer removal was introduced for the VRPCD, and the other removal techniques below are inspired by [? ].

Random removal:. a request is removed at random. Worst removal:. a request with a high removal gain is removed. The removal gain is defined as the difference between the cost of the solution with and without the request. Then, the requests are sorted in non increasing order of their removal gains and put in a list N . The request to remove is selected in a randomized fashion as in [? ]: given a parameter p, a random number y between 0 and 1 is drawn. The request in position y p × |N | is then removed.

Historical node-pair removal:. each arc (u, v) ∈ G is associated with the cost of the cheapest solution it appears in (initially this cost is set to infinity). For each request, the sum of the cost of its associated arcs in the current solution is computed. A randomized selection, similar to worst removal, is performed.

Related removals:. these methods aim to remove related requests. Let the relatedness of requests i and j be R(i, j). Two distinct relatedness measures are used: distance and time. The distance measure between two requests is the sum of the distance between their pickup points and the distance distance between their delivery points. The time measure is the sum of the absolute difference between their start of service at their pickup points and the absolute gap between their start of service at their delivery point. In both cases a small R(i, j) indicates a high relatedness. A randomized selection, similar to worst removal (albeit with a non decreasing ordering), is performed.

Transfer removal:. for each pair of routes (v i , v j ), with v i = v j the number of requests transferred from v i to v j is computed. Then a roulette wheel selection is applied on the pairs of routes (the score of a pair being the number of requests transferred), and the requests that are transferred between the routes in the selected pair are removed. If there are less transferred requests than the target number Φ to remove, the rest of the removals is performed with random removal.

Repair operators

In LNS, the unplanned requests are stored in a requests bank. In the following, the operators to reinsert them in a solution are described. Best-insertion, 2-regret, 3-regret and 4-regrets are used as repair methods in LNS+SPM.

Best insertion:. from the requests r in the requests bank, the one with the cheapest insertion cost considering all possible insertion (with and without transfer) is performed.

Regret Insertion:. for each request r in the requests bank and for each pair of vehicles (pickup vehicle, delivery vehicle), the cost of cheapest feasible insertion (if any) is computed. Note that the pickup and delivery vehicles may be the same (in the case of insertion without transfer). Then, with these insertion options, the k-regret value of r is defined as

c k r = k i=1 (f i -f 1 )
, where f 1 is the cost of the cheapest insertion, f 2 is the cost of the second-cheapest insertion and so on, and k is a parameter. The cheapest insertion of the request with the highest regret value is performed.

Feasibility tests and reduction of neighborhood

In [? ], we used an adaptation of forward time slacks [? ] due to Masson et al. [? ] to check time feasibility of insertions in constant time (capacity check in constant time is straightforward). To reduce the runtime, we do not consider all insertions with transfer. For a request r we only consider transfer from the five closest vehicles to its pickup point, to the five closest vehicles from its delivery point. For large scale instances, this halves the runtime.

Set Partitioning and Matching

Given a set of legs L, set partitioning and matching (SPM) aims to select a subset L of L such that (1) each request is picked up and delivered by exactly one leg in L and (2) legs in L can be matched to form routes that respect time constraints. Each leg l ∈ L has an associated routing cost c l , the objective in the SPM is to minimize the sum of the costs of the selected legs. Notice that only non-dominated legs in L have to be considered in the SPM. A pickup (resp. delivery) leg l i is said to be dominated by a leg l j iff: l i and l j serve the same set of requests, c j < c i and a j ≤ a i (resp. b j ≥ b i ) where a represents the arrival time at the cross-dock and b represents the departure time from the cross-dock. The SPM is solved using a technique called branch-and-check, presented in Section 4.2.1. Its subproblem is a dedicated matching and scheduling subproblem, detailed in Section 4.2.2. The SPM is solved every thousand iterations with a time limit of ninety seconds. If the SPM is solved to optimality within the time limit, the legs in memory are kept, otherwise the pool is cleared.

Branch-and-check

We present branch-and-check [? ] using the following optimization problem:

M 1 : min c x (1) Ax ≤ b (2) H(x, y) (3) x ∈ {0, 1} n (4) y ∈ R m (5)
Assume that H(x, y) represents a set of constraints that have a limited impact on the LP relaxation and/or are difficult to efficiently model in a MIP, but that can be handled relatively easily by a CP solver. (1), ( 2) and (4) form a relaxation (M2) of (M1) that can be solved using branch-and-bound. The general principle of branch-and-check is the following. To solve (M1), a branch-and-bound is carried on (M2). Whenever an integral solution of (M2) is found, a CP solver is called to check constraints (3). If they are satisfied, the best solution found so far for (M1) is updated accordingly. Otherwise, this solution is rejected. In both cases the branch and bound process continues.

Application of branch-and-check to the VRPCD

For the SPM in the VRPCD, a classical set partitioning problem (SPP) is used as relaxation. For each request r ∈ R and each leg l ∈ L, let λ r,l be a binary constant that indicates whether this request is served by this leg, and for each leg, let x l be a boolean variable that indicate whether this leg is selected. The SPP on legs is then :

min l∈L c l x l (6) l∈Lp λ r,l x l = 1 ∀r ∈ R (7) l∈L d λ r,l x l = 1 ∀r ∈ R (8) x l ∈ {0, 1} ∀l ∈ L (9)
The objective (6) is to minimize the cost of the selected legs while constraints (7) (resp. ( 8)) ensure that each pickup point (resp. delivery point) is covered by exactly one leg.

A solution to the SPP on legs, which involves a set of pickup legs denoted Lp and a set of delivery legs denoted Ld , is a solution to the VRPCD iff there exists a matching of pickup legs and delivery legs to form routes that respects time constraints. For each pickup leg l ∈ Lp , let T l be the set of delivery legs that deliver at least one request picked up by l. If a pickup leg l and a delivery leg l are matched together to create a route, there are an associated unloading task o - ll , with a set of requests R - ll being unloaded, and a reloading task o + ll , with a set of requests R + ll being reloaded. These tasks have to be performed iff l and l are in the same route. The matching and scheduling problem is modeled as a constraint satisfaction problem, represented using notation from OPL (Optimization Programming Language [? ]). In particular the model is based on the notion of interval variables and uses alternative constraints. As used here (from [? ]): 'An interval variable represents an interval of time during which a task happen, and whose position in time is an unknown of the scheduling problem. An interval is characterized by a start value, an end value and a size. (...) An interval variable can be optional, that is, one can decide not to consider [it] The matching and scheduling problem is then:

Alternative(t l , {o - ll ; ∀l ∈ Ld }) ∀l ∈ Lp (10) Alternative(t l , {o + ll ; ∀l ∈ Lp }) ∀l ∈ Ld (11) o - ll .IsOptional ← T rue ∀l ∈ Lp , ∀l ∈ Ld (12) o + ll .IsOptional ← T rue ∀l ∈ Lp , ∀l ∈ Ld (13) o - ll .IsP resent ⇐⇒ o + ll .IsP resent ∀l ∈ Lp , ∀l ∈ Ld (14) t l .Start ≥ t l .End ∀l ∈ Lp , l ∈ T l (15) o + ll .Start ≥ o - ll .End + δ r ∀l ∈ Lp , ∀l ∈ Ld s.t. R + ll = ∅ (16) o + ll .Start ≥ o - ll .End ∀l ∈ Lp , ∀l ∈ Ld s.t. R + ll = ∅ (17) o - ll .Start ≥ a l + δ u ∀l ∈ Lp , ∀l ∈ Ld s.t. R - ll = ∅ (18) o - ll .Start ≥ a l ∀l ∈ Lp , ∀l ∈ Ld s.t. R - ll = ∅ (19) o + ll .End ≤ b l ∀l ∈ Lp , ∀l ∈ Ld ( 20
)
For each pickup leg l, t l is an interval variable that represents the associated unloading task that takes place at the cross dock. Alternative constraints (10) and (12) ensure that for each pickup leg l exactly one unloading task o ll is scheduled and that it is equal to t l . The same holds for delivery legs and reloading operations through variables t l and constraints (11) and (13). Constraints (14) ensure that the unloading operation associated with the matching of pickup leg l and the delivery leg l in the same vehicle is present iff the corresponding reloading operation is present as well. Constraints (15) ensure that all the reloading operations that depend on a pickup leg l start no earlier than the end of the unloading task associated with l. Constraints ( 16) and (17) ensure that when two legs are packed together, the delay between the two tasks respects the model presented in Section 3.2. Constraints (18) and ( 19) ensure that for each pickup leg, its corresponding unloading operation cannot start before the earliest feasible arrival time at the cross-dock. Constraints (20) ensure that for each delivery leg, its corresponding reloading operation is done by its latest feasible departure time.

Proposed matheuristic for the VRPCD-RC

In this section, we present the matheuristic that has been derived from [? ] for the VRPCD-RC: Large Neighborhood Search+Set Partitioning and Scheduling (LNS+SPS). In Section 5.1 we focus on the feasibility test of insertions in the repair methods. Then we summarized the methods used in the LNS in Section 5.2. Because of the dock resource constraints, in place of SPM, we propose a Set Partitioning and Scheduling problem (SPS). We present it in Section 5.3. The overall method is summarized in Section 5.4.

Integration of dock resource constraints in LNS

In the repair methods of LNS, we need to ensure that the considered insertions are feasible both with respect to capacity and time-related constraints (time windows and dock resource). Capacity constraints can easily be checked in constant time, thus in what follows we focus on how to handle dock resource constraints. To that end, we start by presenting the scheduling model associated with dock resource constraints, then the methods we propose to solve it and eventually the general structure of feasibility tests we use for maximal efficiency.

Scheduling problems associated with dock resource constraints

For each route k ∈ K, let a k be its earliest feasible arrival time at the cross-dock and b k its latest feasible departure time from the cross-dock. For an insertion that would insert request r in route k 1 for pickup and route k 2 for delivery, we can compute the new earliest feasible arrival time at the cross-dock of k 1 : a 1 , and the new latest feasible departure time of k 2 : b 2 (provided that no time windows violation occurs in the pickup leg of k 1 and in the delivery leg of k 2 , in which case we could immediately reject the insertion). Thus, dock resource constraints can be seen as a satisfaction scheduling problem at the cross-dock. For each route k ∈ K, let T k be the set of routes that deliver at least one request picked up by k; let t - k and t + k be its associated unloading and reloading operations respectively; and let R - k and R + k be the sets of requests R - k being unloaded and reloaded respectively. Let isActive be an indicator function such that isActive(o, h) is equal to 1 iff task o is being performed at instant h. Let H be the time horizon of the problem. In the separated case the associated scheduling problem is:

t + k .Start ≥ t - k .End ∀k ∈ K, k ∈ T k (21) t + k .Start ≥ t - k .End + δ r ∀k ∈ K; s.t. R + k = ∅ (22) t + k .Start ≥ t - k .End ∀k ∈ K; s.t. R + k = ∅ (23) t - k .Start ≥ a k + δ u ∀k ∈ K; s.t. R - k = ∅ (24) t - k .Start ≥ a k ∀k ∈ K; s.t. R - k = ∅ (25) t + k .End ≤ b k ∀k ∈ K (26) k∈K isActive(t - k , h) ≤ I ∀h ∈ [0, H] (27) k∈K isActive(t + k , h) ≤ O ∀h ∈ [0, H] (28)
In the shared case the associated scheduling problem is:

(21 -26) k∈K isActive(t - k , h) + isActive(t + k , h) ≤ S h ∈ [0, H] (29)
Constraints ( 21) ensure that all the reloading operations that depend on a route k start no earlier than the end of the unloading task associated with k. Constraints ( 22) and ( 23) ensure the delay between the unloading and reloading task of a route k respects the model presented in Section 3.2. Constraints (24) and (25) ensure that for each route, its corresponding unloading operation cannot start before the earliest feasible arrival time at the cross-dock. Constraints (26) ensure that for each route, its corresponding reloading operation is done by its latest feasible departure time. Constraints (27 and 28) models the separated case while constraint (29) models the shared case.

Proposed methods for the dock resource constraints

To solve the satisfaction scheduling problems of Section 5.1.1 we propose two methods: (1) using a third party CP solver or (2) using scheduling heuristics. When repeatedly calling a third party solver we cannot neglect its overhead (model building, memory allocation of the solver, ...) potentially leading to very high runtimes. Scheduling heuristics are potentially faster, we could thus perform more LNS iterations within the same time budget, but they are likely to report more false negatives (stating that an insertion is infeasible although it is actually feasible). This is a runtime versus quality trade-off situation.

The scheduling heuristics we use are list heuristics: among a list of available tasks (a task is said to be available for scheduling if all its predecessors have already been scheduled) we select one task according to a given criterion and we try to schedule it. If we can schedule it, we update the resource constraints accordingly, we update the list of available tasks to schedule, and we repeat the process. If at one point we cannot schedule a task, we declare this insertion infeasible according to this scheduling heuristic. The four different selection criteria we use are listed hereafter.

First Come First Served (FCFS):. we select the task with the earliest release date in the list of available tasks.

Earliest Due Date (EDD):. we select the task with the earliest due date in the list of available tasks.

Most Successors First (MSF):. we select the task with the largest number of successors tasks in the list of available tasks. By definition reloading tasks do not have successors, we break ties with the EDD rule.

Shortest Processing Time First (SPTF):. we select the task with the shortest processing time in the list of available tasks.

Checking the feasibility of an insertion in the VRPCD-RC

First, observe that, a necessary condition for an insertion to be feasible in the VRPCD-RC, is for it to be feasible in the VRPCD. As mentionned in Section 4.1.3, feasibility tests in the VRPCD can be performed in constant time. On the other hand feasibility test with respect to dock resource constraints in the VRPCD-RC cannot be done in constant time. Thus for maximal efficiency, we test the feasibility of an insertion as shown on Fig. 2: we start by checking if it is feasible for the VRPCD, if the insertion passes these tests, we test it with respect to dock resource constraints using either a CP solver or scheduling heuristics.

LNS operators

In the proposed LNS, we use the destruction operators of LNS+SPM (see Section 4.1.1). For repair operators, two facts should be taken into account: first, because of resource constraints, only a limited number of requests will be transferred (some requests that were transferred in the VRPCD may not be transferred in the VRPCD-RC). Thus, there is an incentive in creating routes without transfer. Second, as mentioned in Section 5.1.2, feasibility tests can no longer be performed in constant time, thus repair methods that check many insertions, such as k-regret with a high value of k, should be avoided. As such we use: best insertion, 2-regret, best insertion without transfer and 2-regret without transfer as repair methods. In the variants without transfer, only insertions without transfer are considered.

Integration of dock resource constraints in the periodical set partitioning based problem

For the VRPCD-RC, adding dock resource constraints makes the SPM (see Section 4.2) significantly more difficult. Indeed preliminary tests showed that, very often, the CP solver could not find any solution to the corresponding matching and scheduling problem within reasonable runtimes. On the other hand we noticed that the scheduling problems of Section 5.1.1 were solved by the CP solver within a relatively small time. Thus, because the set partitioning idea proved very efficient in [? ], and to cope with the added complexity of the dock resource constraints, in place of SPM we propose to solve a Set Partitioning and Scheduling problem (SPS). It provides the best possible solution from a set of routes (instead of legs in the SPM). It is solved using branch-and-check. To that end a set partitioning problem on routes (similar to the SPP on legs of Section 4.2.2) is solved in a branch-and-bound fashion. At each integral node, the associated scheduling problem corresponds to the one in Section 5.1.1. This approach is efficient to select the best routes but the matching of legs in these routes may be improved. At the end of the SPS, we solve an optimization version of the matching and scheduling problem of Section 4.2.2, where the objective is to minimize the volume transferred at the cross-dock. In the shared case, the CP problem is:

min (l,l )∈ Lp× Ld o - ll .IsP resent × r∈R - l,l q r (30) (10 -20) l∈Lp isActive(t l , h) ≤ I ∀h ∈ [0, H] (31) l ∈L d isActive(t l , h) ≤ O ∀h ∈ [0, H] (32)
(30) minimizes the volume transferred at the cross-dock, while constraints (31) and (32) account for the capacity constraints and are similar to ( 27) and (28) of Section 5.1.1. A similar problem for the separated case can be formulated with an adaptation of (29).

Structure of the proposed method

Algorithm 2 and Algorithm 3 present a sketch of the proposed method: LNS+SPS. Algorithm 2 is similar to Algorithm 1 except for two changes. First, since feasibility tests are computationally more intensive, we consider a stop-criterion based on time, and enclose all instructions within time conditions. Second, the pool of routes K (l. 2 in Algorithm 3) plays the exact same role as the pool of legs L in Algorithm 1. The pool of legs L is still present, it now acts as a memory that can help improving routes in K before solving the SPS, as presented in Algorithm 3. We first apply dominance rules to the legs in L (see Section 4.2). Then we try to improve each route in K by replacing its pickup leg and/or its delivery leg by a non dominated equivalent in L (l. 2-4 in Algorithm 3). We remove dominated routes from K (l. 5 in Algorithm 3). A route is dominated iff there exists a route with a smaller cost that covers the same requests and can arrive earlier at the cross-dock and/or can leave later from the cross-dock. We solve the SPS, and eventually we try to improve the matching of legs in the solution. The initial solution is obtained by applying a 2-regret without transfer.

Result

Computational experiments

The algorithm is coded in C++ and uses CPLEX and CP Optimizer from IBM ILOG Cplex Optimization Studio 12.6.1 as MIP solver and CP solver, respectively. The experiments were conducted under Linux using an Intel Xeon X7350 @ 2.93 GHz. Only one core is used both by our code and third party solvers. We consider instances proposed by Wen et al [? ], that range from 50 to 200 requests. They are based on real life data from a Danish logistics company. The termination criterion for all algorithms is based on time: 15 minutes for size 50 instances, 30 minutes for size 100 for instances, 60 minutes for size 150 instances and 120 minutes for size 200 instances. SPS time limit is 180 seconds. These time limits are between two and three times the runtimes reported for the VRPCD in [? ]. As in [? ], the number Φ of requests to remove in the repair phase of the LNS is drawn randomly in the interval [min(30, 10% of |R|), max(60, 20% of |R|)], acceptance criterion is descent.

Bound setting for the number of docks

To determine when limiting the number of docks start being a constraint in the VRPCD-RC, we postprocessed the solutions obtained in [? ] for the VRPCD. To that end, for all the ten solutions found for each instance for the VRPCD, we solve optimization versions of the satisfaction scheduling problems introduced in Section 5.1.1. We take as objective: to minimize S in the shared case, and in the separated case, we only consider symmetric configurations where I = O and we minimize I. In table 1, columns A correspond to the smallest value obtained after two hours of runtime for the CP solver, and columns B correspond to the worst value obtained after five minutes of post-process. For each instance, columns B corresponds to a threshold for the dock value, above which, the VRPCD-RC could be solved as a VRPCD (postprocessing the solution for a Table 1: Dock value obtained when postprocessing for each instance all of ten solutions of [? ]. Columns A refer to the to the best solution (min dock use) obtained after two hours, while columns B correspond to the worst value (max dock use) obtained after five minutes of post-processing.

Parameters tuning

In this section we evaluate and adjust several parameters. We start with the time limit for the CP solver in LNS feasibility tests, then we report the success rate of heuristics. After, we present the influence of the SPS frequency on the quality of solutions, and eventually we compare the performance of four possible configurations: with CP solver tests/with heuristic tests in LNS, with/without SPS. For tuning, we use instances 50b, 100b, 150b, 200b, and we consider the shared cross-dock configuration case.

CP solver time limit in feasibility tests

When checking the feasibility with respect to dock resource constraints, we need to set a time limit after which the CP solver will stop searching and declare the insertion infeasible. This avoids spending a large amount of time checking the feasibility of a single insertion. In Table 2, we compare four different time limits. In the final setting, the time limit of the CP Solver is set to 0.01 seconds

Heuristics performance

As mentioned in Section 5.1.2, using CP versus using heuristics for feasibility tests is a quality/runtime trade-off. For each instance in the training set, we performed two runs with LNS, with the stop-criterion CP Time Limit (s) 1 0.1 0.01 0.001 Runtime 1 0.33 0.12 0.10 Time limit hit (%) 0.5 12.9 20.1 27.3

Table 2: Comparison of four different time limits for the CP solver, when used as feasibility test in the shared case. Runtime is normalized with 1 representing the runtime for a CP solver time limit of 1s. Time limit hit represents the percentage of calls for which the CP solver could not find an answer within the time limit. Figures reported for one thousand LNS iterations, two runs were performed in each case.

set to one thousand iterations. We count how many time insertions were reported feasible by heuristics and how many times they were reported feasible by the CP solver with a time limit of 1 second (according to Table 2, with this time limit we can consider that the CP solver give an accurate answer most of the time). On average, 71.1% of feasible insertions are reported feasible by heuristics. Performing one thousand LNS iterations with feasibility tests performed by heuristics takes only 18.2% of the time taken with CP solver tests (with 0.01s as time limit).

SPS frequency

In [? ], the SPM was solved twenty times per run (every thousand iterations with a stop-criterion of twenty thousands iterations). In the VRPCD-RC, because feasibility tests are computationally intensive, the stop-criterion is based on time. The number of iterations performed within the time limit depends not only on the size of the instance but also on the dock value. As such, we propose a SPS-criterion based on time. In Table 3 and Table 4, we compare three different settings for the SPS frequency : 10, 20 and 40 calls within the time limit. Accordingly, the number of calls per run is set to 20 for heuristic test and 10 for CP solver test.

Performance comparison

On Fig. 3 we present the convergence curves of LNS and LNS+SPS over time for both CP solver and heuristics feasibility tests. From this graph, we can observe two things. First, as in the VRPCD, periodically solving a set partitioning based problem significantly improves performance compared to LNS alone: -6.96% for heuristic test and -7.92% for CP solver test on average. Second, the best performing method is LNS+SPS with heuristic feasibility tests, as it finds solutions that are 1.19% better on average than LNS+SPS with CP solver test. In the rest, we thus use LNS+SPS with heuristic feasibility test.

Results

Table 5 and Table 6 present the results in the shared case and in the separated case respectively. A dock value of 0 corresponds to the case where no transfer is allowed. These results highlight the increased complexity induced by integrating dock resource constraints, as there exists for each instance, at maximum dock value, a solution with 0% gap (see Section 6.1). Nevertheless LNS+SPS finds solutions that are 1.6% more expensive in the shared case and 1.5% more expensive in the separated case, which remains satisfactory. The algorithm shows relatively good performance in terms of stability: the difference between the average value and the best value of the five runs for each instance and each dock value is 0.6% on average and at most 1.4% in the shared case and 0.6% on average and at most 3.2% in the separated case. Regarding routing costs: integrating dock resource constraints implies an increase in cost. Comparing the two systems, the shared case costs are slightly smaller than separated costs (e.g, for instance 150b, 5.85% for 2 shared docks compared to 6.05 as shown on Fig. 4). This differences increases with the number of docks.

Conclusion

This paper presents an adaptation of the method proposed in [? ], which is based on large neighborhood search and periodic calls to a set partitioning based problem, to solve an extension of the VRPCD that includes resource synchronization constraints at the cross-dock. To deal with these constraints, scheduling heuristics and a CP model have been used as feasibility tests for insertions in LNS. In this case, experiments have showed that heuristics are the most efficient compromise. Compared to [? ], because of the increased complexity induced by resource synchronization constraints, the set partitioning based problem had to be adapted with a simpler subproblem. As in [? ], adding this component helps finding solutions significantly better than those obtained by LNS alone. The proposed method has been tested on instances from the literature, where it shows an increase in routing costs with the decrease in cross-dock capacity.

  [? ]. Other variants have been studied by Santos et al. [? ? ] which integrate a cost for transferring item at the cross-dock and have no temporal constraints. It was later extended in [? ] with optional cross-dock return. These three articles proposed methods based on branch-and-price. The work of Petersen and Ropke [? ] considers optional cross-dock return and multiple trips per day. They propose a parallel adaptive large neighborhood search to solve large real-life instances with up to 982 requests. In [? ], Nikolopoulou et al. considers optional cross-dock returns when comparing direct shipping versus cross-docking strategy. Dondo and Cerdà [? ] consider a case where the number of doors is fixed and smaller than the number of trucks. In particular each door is modeled individually: a time matrix models the time spent by a truck for moving from an inbound door a to an outbound door b. They solve two randomly generated instances with up to 70 requests with a mathematical model combined with a sweep heuristic. Recently, Maknoon and Laporte [? ] study the extension of the problem to multiple cross-docks, Nikolopoulou et al. study the many-to-many case and Ahmadizar et al. [? ] propose a hybrid genetic algorithm for the multiple cross-dock, multiple suppliers case. From a general perspective, the VRPCD can be viewed as a special case of the pickup and delivery problem with transfers with only one compulsory transfer point [? ]. Guastaroba et al. [? ] released a survey on intermediate facilities in freight transportation. For a general overview of cross-docking and cross-dock related problems we refer the reader to [? ? ? ]

  [? ], Schmid et al. [? ], Schmid et al. [? ] and Grimault et al. [? ] impose precedence constraints on the sequencing of operations to handle precedence constraints. Gronhaug et al. [? ] rely on a time-discretized formulation in which resource synchronization constraints are easily expressed. Hempsch and Irnich [? ] proposed a generic modeling for inter-routes constraints via the use of Resource Extension Functions (REF). In particular they focused on the use of REF as efficient feasibility tests in local search based algorithms when the solution is represented by a giant tour. From this literature review, it is clear that most of the resource synchronization constraints are in fact complex scheduling problem integrated into a vehicle routing problem. However the precise definition of the scheduling problem depends largely on the vehicle routing problem at stake.

Figure 1 :

 1 Figure 1: Time chart for vehicle unloading and reloading at the cross-dock in the VRPCD-RC

Result:s := s 6 7

 6 The best found solution s 1 Pool of legs L := ∅ 2 Generate an initial solution s 3 s := s 4 while stop-criterion not met do 5 Destroy quantity: select a number Φ of requests to remove from s Operator selection: select a destruction operator M -and a repair operator M + 8 Destruction : apply M -to remove Φ requests from s , and put them in the requests bank of s 9 Repair: apply M + to reinsert the requests in the requests bank in s 10 if acceptance criteria is met then 11 s := s 12 end 13 if cost of s is better than cost of s then 14 s := s 15 end 16 Add legs of s to L 17 if set partitioning and matching condition is met then 18 Perform set partitioning and matching with the legs in L 19 Update s and s if a new best solution has been found 20 Perform pool management 21 end 22 end 23 Perform set partitioning and matching with the legs in L 24 Update s if a new best solution has been found 25 return s Algorithm 1: LNS+SPM of Grangier et al.

  in the solution schedule.' In this model, we model alternative activities [? ] by using alternative constraints (from [? ]): 'An alternative constraint between an interval variable a and a set of interval variables b 1 , . . . , b n models an exclusive alternative between b 1 , . . . , b n . If interval a is present, then exactly one of intervals b 1 , . . . , b n is present and a starts and ends together with this specific interval. Interval a is absent if and only if all intervals in b 1 , . . . , b n are absent.'

Figure 2 :

 2 Figure 2: Logical flow-chart of feasibility tests for the VRPCD-RC

:s := s 7 8

 7 The best found solution s 1 Pool of legs L := ∅ 2 Pool of routes K := ∅ 3 Generate an initial solution s 4 s := s 5 while stop-criterion not met do 6 Destroy quantity: select a number Φ of requests to remove from s Operator selection: select a destruction operator M -and a repair operator M + 9 Destruction : apply M -to remove Φ requests from s , and put them in the requests bank of s 10 Repair: apply M + to reinsert the requests in the requests bank in s 11 if acceptance criteria is met then 12 s := s 13 end 14 if cost of s is better than cost of s then 15 s := s 16 end 17 Add legs of s to L 18 Add routes of s to R 19 if set partitioning and scheduling condition is met then 20 Perform SPS(L, K, s , s );

Figure 3 :

 3 Figure 3: Comparison of the evolution of the average solution quality over time (in percentage of time limit) for four different configurations: with CP solver/with heuristics tests, with/without SPS. The results aggregate 5 runs for each dock value in the shared case for instances in the training set. They have been normalized, first by instance then by method, with 100 representing the cost at the end of LNS with CP solver tests (LNS-CP)

( a )

 a Figure 4: Influence of the dock value for instance 150b. Five runs were performed for each dock value. The y-axis represents the average gap with respect to the average value reported in [? ]

Table 3 :

 3 Comparison of the impact of the number of SPS calls per run on the quality of the solution for heuristic feasibility tests. Five runs were performed for each dock value for each instance in the training set. 10 calls is taken as reference for the gap

	Number of calls	10	20	40
	Average gap (%) 0 +0.40 +0.68

Table 4 :

 4 Comparison of the impact of the number of SPS calls per run on the quality of the solution for CP solver tests. Five runs were performed for each dock value for each instance in the training set. 10 calls is taken as reference for the gap


Fabien Lehuédé

Olivier Péton

Fabien Tricoire

Multi-directional local search for the leximax-VRP

published or not. The documents may come

Multi-directional local search for the leximax-VRP Fabien Lehuédé IMT Atlantique, LS2N UMR CNRS 6004, Nantes, France Email: fabien.lehuede@imt-atlantique.fr Olivier Péton IMT Atlantique, LS2N UMR CNRS 6004, Nantes, France Fabien Tricoire Institute for Production and Logistics Management, Johannes Kepler University Linz, Austria

Most vehicle routing problems (VRPs) studied in the Operations Research literature deal with the design of a set of routes of minimal cost to serve a set of customers. In many practical cases, companies seek cost minimization as well as the optimization of criteria related to vehicles and drivers. In particular, preserving equity among drivers through a good balance of their workload is often sought. Historically, two main equity measures, have been proposed in the VRP literature. First, min-max approaches, such as proposed by Golden et al. [START_REF] Golden | An adaptive memory heuristic for a class of vehicle routing problems with minmax objective[END_REF], propose to minimize the length of the longest route. An unfortunate consequence of this approach is that all solutions with the same longest route length have the same equity measure. The second equity measure, recently designated by the term range [START_REF] Matl | Workload Equity in Vehicle Routing Problems: A Survey and Analysis[END_REF], considers the difference between the longest route and the shortest route [START_REF] Lee | A study of vehicle routing problems with load-balancing[END_REF].

An important drawback of this measure is its non-monotonicity. As recently exposed by

Halvorsen-Weare and Savelsbergh [START_REF] Halvorsen-Weare | The bi-objective mixed capacitated general routing problem with different route balance criteria[END_REF] or Matl et al [START_REF] Matl | Workload Equity in Vehicle Routing Problems: A Survey and Analysis[END_REF] among other drawbacks: the range of a solution can be improved by increasing, even in an inconsistent way, the length of its shortest route of a solution without decreasing the length of the others.

As recently summarized by Ogryczak et al. [START_REF] Ogryczak | Fair optimization and networks: A survey[END_REF] in a survey on fair optimization and networks, the lexicographic minimax approach has been used in domains such as network optimization, facility location and network optimization to produce equitable or fair solutions. The lexicographic minimax, based on the leximax operator, refines the min-max approach: informally speaking, when a minimal value has been found for the longest route, the lexicographic minimax considers the second longest route, the third longest route, and so on, until all ties have been broken.

In this presentation, we introduce the leximax-VRP as a refinement of the CVRP with two objective functions: the sum of routing costs and the lexicographic minimax over routes durations.

Solution method

We propose to integrate the lexicographic minimax approach in a multi-objective optimization framework called Multi-Directional Local Search (MDLS) [START_REF] Tricoire | Multi-directional local search[END_REF].

MDLS principle

MDLS offers a very simple local search framework but it still competes with state-of-theart methods when solving multi-objective optimization problems. In MDLS, a local search LS j is defined for each objective j. This local search is later performed in order to improve solutions with respect to objective j. A set of non-dominated solutions is kept in an archive and returned at the end of the algorithm. An iteration consists in (i) selecting a solution from the archive, (ii) performing local search on this solution for each objective/direction, thus producing a new feasible solution in each direction and (iii) updating the archive using newly produced solutions.

Local search components

In our algorithm, we consider that local search consists of one Large Neighborhood Search (LNS) iteration. Several ruin and recreate operators are defined for each objective. Hence, at each iteration, for each objective (i) a ruin and a recreate operator are randomly selected in the set of operators for that objective and (ii) a new solution is produced using the selected operators.

The cost operators are defined according to the classical LNS operators for the VRP [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF]. The set of ruin operators that we use are: random removal, worst removal, related removal and route removal. The recreate operators for the cost objective are the cheapest insertion heuristic and the k-regret heuristic for k = 2, 3, 4.

We introduce lexicographic minimax operators which extend the classical operators to the lexicographical minimax approach. The ruin operators include the random removal and the related removal as well as the following two operators:

• worst max removal: at each iteration this operator removes, from the longest route, the customer that decreases the most the length of this route.

• longest route removal: at each iteration, all customers from the longest route are removed.

Two sets of recreate operators have been designed to guide the search towards lexicographic minimax efficient solutions: q q q q q q q q q q q q q q q q q q q q q q q q q 0 25 50 factor(method) all leximax max q q q q q q q q q q q q q q q q q q q q q 20 40 60 • The leximax cheapest insertion and leximax k-regret extend the cheapest insertion and k-regret heuristics to the lexicographic minimax approach.

• The min-max cheapest insertion and min-max k-regret extend cheapest insertion and k-regret, but using only the duration of the longest route as a criterion to guide the search and the solution cost increase to break ties.

As the lexicographic minimax heuristics involve sorting route vectors to compare solutions, our objective is to assess whether the faster min-max heuristics can be more efficient to guide the search towards lexicographic minimax solutions.

Experiments

To illustrate the experimental study in this abstract, we present the comparison of three configurations, which all include cost operators and lexicographic minimax ruin operators.

Configuration leximax integrates the leximax cheapest insertion and leximax k-regret. Configuration max integrates min-max cheapest insertion and min-max k-regret. Configuration all includes all of these recreate operators for the lexicographic minimax objective.

Our MDLS is evaluated on the Christofides CVRP instances, which are traditionally used to benchmark the VRP with load balancing. 10 runs of 60 minutes are performed for each configuration and each instance and a reference set is constructed by taking the non-dominated union of the sets returned by each run for each configuration over all experiments. To evaluate configurations, we consider two indicators: the percentage of solutions from the reference front found in a given run, and the percentage of solutions found which are within 2% of a solution from the reference front. A solution x 1 is within 2% of another solution x 2 if, when the cost and all route lengths of x 2 are multiplied by 1.02, then x 1 dominates this transformed solution. This information is summarized in the two plots from Figure 1. On the left plot, for each instance and each configuration, we represent the percentage of solutions of the reference front that are found on each run.

The distribution of the performance evaluation of each run is displayed with a Box Plot.

For the majority of instances, the percentage of solutions of the reference front found for each run remains quite low. Comparing the three configurations, it is not possible to clearly state that one dominates the other. The right plot shows the percentage of solutions of the reference front that lie within a 2% distance of a solution returned by each run. This plot shows that the returned approximation returned by the all and leximax configurations remains within close distance of the reference front. Comparing the various configurations, guiding the search with insertion criteria based on the longest route is less effective than with the proposed leximax based heuristics.

Figure 1 :

 1 Figure 1: Boxplots charts for the number of solution of the reference front that have been found and within 2% distance for each run and each instance in one hour.