The robust vehicle routing problem with time windows Agostinho Agra, Marielle Christiansen, Rosa Figueiredo, Lars Magnus, Michael Poss, Cristina Requejo To cite this version: Agostinho Agra, Marielle Christiansen, Rosa Figueiredo, Lars Magnus, Michael Poss, et al.. The robust vehicle routing problem with time windows. Computers and Operations Research, 2013, 40 (3), pp.856 - 866. ￿10.1016/j.cor.2012.10.002￿. ￿hal-00916976￿ HAL Id: hal-00916976 https://hal.science/hal-00916976 Submitted on 11 Dec 2013 HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non, lished or not. The documents may come from émanant des établissements d’enseignement et de teaching and research institutions in France or recherche français ou étrangers, des laboratoires abroad, or from public or private research centers. publics ou privés. The robust vehicle routing problem with time windows Agostinho Agra ∗ Marielle Christiansen † Rosa Figueiredo ‡ Lars Magnus Hvattum § Michael Poss ¶ Cristina Requejo (cid:107) September 25, 2012 Abstract This paper addresses the robust vehicle routing problem with time windows. We are motivated by a problem that arises in maritime transportation where delays are frequentandshouldbetakenintoaccount. Ourmodelonlyallowsroutesthatarefea- sible for all values of the travel times in a predetermined uncertainty polytope, which yieldsarobustoptimizationproblem. Weproposetwonewformulationsfortherobust problem, each based on a different robust approach. The first formulation extends the well-knownresourceinequalitiesformulationbyemployingadjustablerobustoptimiza- tion. We propose two techniques, which, using the structure of the problem, allow to reduce significantly the number of extreme points of the uncertainty polytope. The secondformulationgeneralizesapathinequalitiesformulationtotheuncertaincontext. Theuncertaintyappearsimplicitlyinthisformulation,sothatwedevelopanewcutting planetechniqueforrobustcombinatorialoptimizationproblemswithcomplicatedcon- straints. In particular, efficient separation procedures are discussed. We compare the two formulations on a test bed composed of maritime transportation instances. These results show that the solution times are similar for both formulations while being sig- nificantlyfasterthanthesolutionstimesofalayeredformulationrecentlyproposedfor the problem. Keywords: robust optimization; uncertainty polytope; vehicle routing problem; time windows; dynamic programming. 1 Introduction This paper demonstrates how to efficiently solve the vehicle routing problem with time windows (VRPTW) when travel times are uncertain. The aim is to find robust solutions, whereroutesarefeasibleforalltraveltimesdefinedbyapredetermineduncertaintypolytope. Althoughtheformulationsdevelopedinthispaperaregeneralenoughtodescribemanytypes of applications, the motivation for the work comes from maritime transportation, where routing problems are known to include many types of uncertainty [11] and where travel times and service times can vary due to unforeseen events such as bad weather, mechanical breakdowns and port congestion. Much research has been performed on vehicle routing problems, not the least due to its importance for applications in transportation, distribution and logistics [14]. Two well ∗CIDMA,DepartmentofMathematics,UniversityofAveiro,3810-193Aveiro,Portugal,[email protected] †DepartmentofIndustrialEconomicsandTechnologyManagement,NorwegianUniversityofScienceand Technology,NO-7491,Trondheim,Norway,[email protected] ‡CIDMA, Department of Mathematics, University of Aveiro, 3810-193 Aveiro, Portugal, rosa.fi[email protected] §DepartmentofIndustrialEconomicsandTechnologyManagement,NorwegianUniversityofScienceand Technology,NO-7491,Trondheim,Norway,[email protected] ¶CMUC, Department of Mathematics, University of Coimbra, 3001-454 Coimbra; UMR CNRS 6599 Heudiasyc,Universit´edeTechnologiedeCompi`egne,CentredeRecherchesdeRoyallieu,60200Compi`egne, France,Portugal,[email protected]. (cid:107)CIDMA,DepartmentofMathematics,UniversityofAveiro,3810-193Aveiro,Portugal,[email protected] 1 knownclassesofvehicleroutingproblemsarethecapacitatedvehicleroutingproblem(CVRP) and the VRPTW. The VRPTW and CVRP share many common features, and path-flow formulationswhereintegervariablesrepresentpathsinthenetworkareverysimilarforboth problems [21]. However, arc-flow formulations, where integer variables represent single arcs in the network, have notable differences: While it is straightforward to express the capacity constraint in the space of arc variables, time windows require either additional variables or an exponential number of inequalities [15]. We study integer programming formulations for a variant of the VRPTW. More specif- ically, we study the problem where travel times belong to an uncertainty polytope. Hence, ourapproachfallsintotheframeworkofrobustprogramming, whereasolutionissaidtobe feasible only if it is feasible for all realizations of the data in a predetermined uncertainty set T. Robust programming stems from the original work of Soyster [22] and has witnessed a continuous attention in the last decade. We refer the interested reader to the survey from Bertsimas et al. [6]. Prior to our recent note [1], Sungur et al. [25] were the first to mention a robust vehicle routing problem with time windows and uncertain travel times (T-VRPTW). However, their modeling assumption led to all travel times taking their maximum values, yielding an over-conservativemodel. Infact,Sunguretal.[25]mainlyfocusedontherobustCVRP and study conditions under which robust versions of the CVRP can be solved through methods similartotheonesusedforthedeterministicversionoftheCVRP,seealso[18]forasurvey ontherobustCVRP. TheliteratureonstochasticversionsoftheVRPTW isscantwhenit comestostochastictraveltimes,theonlyexamplecomingfromChardyandKlopfenstein[9] who propose pre-processing techniques based on stochastic inequalities. In contrast to this, the stochastic versions of the CVRP have witnessed continued attention for many years, see [10] and the references therein. Our recent note [1] presents the first general approach to the robust vehicle routing problem with time windows and uncertain travel times. Travel times belong to a demand uncertainty polytope, which makes the problem harder to solve than its deterministic coun- terpart. Thebenefitoftheadditionincomplexityisthatthemodelfrom[1]ismoreflexible than the one from [25] and leads to less conservative robust solutions. The work presented in [1] focuses on applying the classical dualization technique for robust programming which yieldsaverylargeformulationthatarehardlysolvedforinstanceswithmorethan20nodes. The limited results obtained in [1] motivate us to tackle the T-VRPTW with the more so- phisticated robust approaches used in this paper. Our first approach uses adjustable robust optimization, while the second one substitutes robust constraints with canonical cuts. The first of our formulations extends the classical resource inequalities formulation to the robust context. This yields a two-stage robust program, based on the framework of adjustable robust optimization from Ben-Tal et al. [4]. Robust integer programs with arbi- trary decision rules are extremely hard to solve exactly so that most authors have devised approximation schemes that are computationally tractable, such as the affine decision rules introduced in [4]. However, some authors have raised the possibility of obtaining exact so- lutions to robust programs with arbitrary decision rules, see [8, 20]. When it is possible to computeallextremepointsoftheuncertaintysetandthenumberofthesepointsislimited, Poss and Raack [20] suggest to consider all of them and to solve the resulting formulation. Very often, the numbers of extreme points are too large to be handled explicitly so that Bienstock and O¨zbay [8] propose decomposition algorithms that require solving non-convex subproblems. For our two-stage robust program, we follow the approach of Bienstock and O¨zbay [8] andgeneratedynamicallytheextremepointsoftheuncertaintypolytope. First,wepropose two techniques that allow a significant reduction of the number of extreme points needed to formulate the problem. The first technique shows that the number of extreme points whichwemustconsiderisnotlargerthanthenumberofextremepointsoftheprojectionof the uncertainty polytope into the subspace corresponding to the coefficients defining any of its constraints. The second technique introduces the notion of dominance among extreme 2 points. Finally, we apply a column-and-row generation algorithm to generate only a subset ofthenon-dominatedextremepoints. Incontrasttotheapproachof[8]thatsolvesNP-hard subproblems, our subproblem can be solved in polynomial time by a dynamic programming algorithm. This is an important feature of our method that makes it scalable with the problem size. ThesecondofourformulationsextendsthepathinequalitiesformulationfromKallehauge et al. [15]. The uncertain parameters do not appear explicitly in the constraints of this formulation, so that we decompose the problem into a master problem and a subproblem. Themasterproblemcontainsthedeterministicconstraintsoftheoriginalproblemplusaset ofcanonicalcutsensuringthattherobustconstraintsarealsosatisfied,whilethesubproblem generatesadditionalcanonicalcutswhenthemasterproblem’ssolutionviolatessomeofthe robustconstraints. WeapplythisapproachtoVRPTW andT-VRPTW andournumerical results show that the resulting optimization problems for VRPTW and T-VRPTW are of the same difficulty for our instances. This is an important result since the introduction of uncertainty in an integer program usually makes the problem much harder to solve. For instance, the classical dualization approach increases significantly the number of variables and constraints of the original problem. To summarize our contributions, we present in this paper two formulations for the T-VRPTW that can handle instances of the maritime transportation problem for real- istic dimensions. Both formulations studied in this paper are tackled by decomposition algorithmswhichmakesthemscalableandlimitsthecomputationaldifficultythatnormally arises from the introduction of robustness. Our main contributions are (i) the study of techniques to reduce the number of extreme points of the uncertainty polytope that must beconsideredinthemodel,and(ii)theimplementationofacutting-planealgorithmforthe paths inequalities formulation that solves the robust instances as easily as the deterministic ones. This paper is structured as follows. The next section introduces two different formula- tions of the VRPTW. Section 3 presents some key aspects of robust programming that are needed to provide finite linear programming formulations for linear problems under poly- hedral uncertainty. In particular, Section 3.1 presents our new technique based on implicit representation of robust constraints. The tools from Section 3 are used in Section 4 to pro- videtwoformulationsfortheT-VRPTW. Section4.1alsopresentsadetailedstudyonhow to reduce the number of scenarios that must be considered. Section 5 presents a numerical assessment of our formulations on a maritime transportation problem that is described in Section 5.1, and we conclude the paper in Section 6. 2 The vehicle routing problem with time windows We first present a definition of the VRPTW. Considering the application to maritime transportationthatwewillpresentinSection5,thefollowingdefinitionismoregeneralthan the standard VRPTW. By allowing travel costs and travel times to be different for each vehicle, the definition includes other related problems such as the VRPTW with multiple depots. Also due to our maritime transportation application, we omit capacity constraints in the formulation. However, including capacity is easy in all of the formulations given in this paper. We are given a directed graph G = (N,A), a set of vehicles K, a cost function c : A×K → R , and a time function t : A×K → R for traveling along the arcs of G. + + Thegraphcontainsspecialdepotnodeso(origin)andd(destination)connectedtoallother nodesofG, andwedenotebyN∗ thesetofnodesthatarenotdepots, N∗ :=N\{o,d}. We are given time windows [a ,b ] with a ,b ∈R , for each i∈N∗. Because different vehicles i i i i + may have access to different routes, we also introduce the subset Ak of A for each k ∈K. The VRPTW consists of defining routes for the vehicles in K such that the union of all routes passes exactly once by each i ∈ N∗. When |K| = 1, the problem contains a unique vehicle and reduces to the asymmetric traveling salesman problem with time windows [2]. Inthissection,werecalltwowell-knownformulationsfortheVRPTW,basedonresource 3 inequalities and path inequalities, respectively, and introduce a new layered formulation for the problem. These formulations suppose that all parameters are known with certainty. 2.1 Resource inequalities We first recall a classical formulation for the VRPTW based on resource inequalities. The formulation uses a set of binary flow variables xk which indicates whether vehicle k ij travels from node i∈N to node j ∈N, and a set of continuous variables yk indicating the i arrival time of vehicle k at node i ∈ N. In fact, since only one vehicle can serve node i, we may drop the index k and let y be the arrival time at node i of the vehicle that serves i i. Time windows [a ,b ] are imposed at each node i ∈ N∗, and we assume that a vehicle i i arriving earlier than a can wait until a at no cost. The resource inequalities model for i i VRPTW follows. (cid:88) (cid:88) min ckxk (1) ij ij k∈K(i,j)∈Ak (cid:88) (cid:88) s.t. xk =1, i∈N∗, (2) ij k∈Kj∈N:(i,j)∈Ak  −1 i=o (cid:88) (cid:88)  (RI) xk − xk = 1 i=d , i∈N, k ∈K, (3) ji ij j∈N:(j,i)∈Ak j∈N:(i,j)∈Ak  0 otherwise xk(y +tk −y )≤0, (i,j)∈Ak, k ∈K, ij i ij j (4) a ≤y ≤b , i∈N∗, (5) i i i xk ∈{0,1}, (i,j)∈Ak, k ∈K. ij Theobjectivefunction(1)minimizesthecostofoperatingthesetofvehicles. Constraints(2) ensure that all i∈N∗ are served exactly once, and constraints (3) are the flow conservation constraints for each vehicle. Constraints (4) link routes and schedules, that is, y must be j greater than or equal to y +tk whenever vehicle k travels from i to j, while constraints (5) i ij ensure that the time windows are respected. Constraint (4) can be linearized and replaced with constraints y −y +(b +tk −a )xk ≤b −a , (i,j)∈Ak, k ∈K. (6) i j i ij j ij i j It is shown in the next proposition that model (RI) can be improved by strengthening constraints (6). Proof of Proposition 1 is straightforward and thus, we omit it. Proposition 1. Constraints (cid:88) y −y + max{b +tk −a ,0}xk ≤b −a , (i,j)∈A. (7) i j i ij j ij i j k∈K:(i,j)∈Ak are valid for (RI). Moreover, any (x,y)∈{0,1}|A||K|×R|N∗| that satisfies constraints (7) also satisfies constraints (6). Proposition 1 reinforces formulation (RI) and reduces its number of constraints. In addition, the result is fundamental to derive, later in the paper, a robust formulation whose dimension is not influenced (on the robust part) by the number of vehicles. An important characteristic of (RI) is the presence of variables y that depend explicitly on the travel time values tk. Given routes described by variables x, variables y enable us to ij knowhowmuchtimethevehicleshavetowaitbeforebeingabletoserveeachnodealongtheir route. This level of information is useful in some applications that consider costs related to waiting times such as described by Desaulniers and Villeneuve [13]. However, in the 4 application considered in this paper, only travel costs are relevant. Hence, the formulations presented in the next two sections only contain variables related to the vehicle routes. This shall have a crucial impact when applying robust models and methods to the VRPTW, as will be discussed in Sections 3 and 4. 2.2 Path inequalities A recent formulation based only on arc variables x has been proposed by Kallehauge et al. [15] for the VRPTW. The formulation does not explicitly consider the satisfaction of the time windows. Instead, it forbids routes in G for which it is not possible to construct a feasible schedule. Let Pk be the set of infeasible paths from o to d in G, that is, the set of paths in G for which it is not possible to define arrival times y that satisfy constraints (4) i and (5). For p∈Pk, we denote by |p| the number of arcs contained in p. The main idea of this formulation is simply to forbid such paths. (cid:88) (cid:88) min ckxk ij ij k∈K(i,j)∈A (PI) s.t. (2),(3) cycle-breaking inequalities, (8) (cid:88) xk ≤|p|−1, p∈Pk, k ∈K, (9) ij (i,j)∈p xk ∈{0,1}, (i,j)∈Ak, k ∈K. ij Formulation (PI) contains one set of variables which, as before, indicates which arcs are usedbyeachvehicle. Constraints(8)canbeanysetofconstraints(possiblywithadditional variables) that forbid cycles. In our computational results we use the MTZ inequalities [17] which,essentially,usesanauxiliarysetofvariablessimilartoyin(RI)toimposeanorderon thenodesvisitedbythevehicles. Then, constraints(9)forbidinfeasiblepaths. Formulation (PI) contains a very large number of inequalities (9), possibly exponential in the size of the problem, so that branch-and-cut algorithms must be devised to solve (PI) exactly. 3 Robust linear programming In this work, we consider uncertain travel times that belong to a polytope T. This makes the problem a robust program, a class of optimization problems that has witnessed an increased attention in the recent years. Conducting an exhaustive literature review of robust programming is beyond the scope of this paper and we redirect the interested reader to [6], among others. Theclassicalapproachforrobustprogrammingreliesonstaticmodelswherethevariables of the problem are not allowed to vary to account for the different values taken by the uncertain parameters. This is different from adjustable robust optimization that will be introduced later in this section. Consider the following linear program in {0,1}-variables min cTx (P) s.t. Bx≤b, (10) Tx≤d, (11) x∈{0,1}n, with c ∈ Rn,b ∈ Rr,d ∈ Rs,T ∈ Rsn, and B ∈ Rrn. Suppose that the problem is subject to uncertainty in the sense that matrix T belongs to a polytope T ⊂ Rsn. The robust 5 counterpart of (P) is min cTx (T-P) s.t. Bx≤b, Tx≤d T ∈T, (12) x∈{0,1}n, where the s linear constraints in (11) must now be satisfied for each value of T ∈T. Hence, the finite set of constraints (11) has been replaced by the infinite set of constraints (12). The classical approach in linear robust programming under polyhedral uncertainty to handle the infinite set of constraints (12) [5], relies on dualizing constraints (12). This results in the addition of a polynomial set of constraints and variables which depend on the definition of the uncertainty polytope T. To be applied to the T-VRPTW, this approach requires to use an extended formulation, which contains a set of constraints Tx ≤ d that describe the time windows in a static manner, that is, using only variables related to the routes (and not to the actual schedule). Such a formulation has been proposed in [1]. The formulation from [1] yields very poor numerical results even in the deterministic case. For this reason, we introduce alternative formulations in this paper, respectively based on the implicit representation of (12) and on adjustable robust optimization. 3.1 Implicit reformulation The method described in this section is based on the implicit representation of (12) via canonical cuts. Implicit reformulation has already been used in this paper to obtain formulation (PI) where the satisfaction of time windows is not included explicitly. Instead, (9) play this role by forbidding individual paths that do not satisfy the time windows. The idea of replacing complicating constraints by canonical cuts has been used in other contexts as well [12, 23]. To our knowledge, this paper is the first work that applies this implicit reformulation to a robust program. In the following, we recall first the general idea for the deterministic problem (P). Then, we extend it to the robust problem (T-P). LetX ⊂{0,1}n bethesetofallbinaryvectorsthatviolateatleastoneoftheconstraints (11). For x∗ ∈ {0,1}n, we denote by x∗(1) ⊆ {0,...,n} (resp. x∗(0) ⊆ {0,...,n}) the set of indices where x∗ is equal to 1 (resp. 0). Hence, a vector x∗ ∈ X can be cut-off by the following canonical cut (cid:88) (cid:88) (1−x )+ x ≥1, i i i∈x∗(1) i∈x∗(0) firstmentionedbyBalasandJeroslow[3]. Thus,constraints(11)forxbinaryareequivalent to the following set of canonical cuts (cid:88) (cid:88) (1−x )+ x ≥1, x∗ ∈X. (13) i i i∈x∗(1) i∈x∗(0) We see that constraints (9) are an example of (13). Similarly, let X(T) be the set of binary vectors that violate at least one of the constraints in (12). This set of constraints for x binary are equivalent to (cid:88) (cid:88) (1−x )+ x ≥1, x∗ ∈X(T). (14) i i i∈x∗(1) i∈x∗(0) Therefore, (T-P) can equivalently be written as min cTx (T-Png) s.t. (10),(14) x∈{0,1}n, 6 which is a finite linear program in {0,1}−variables. Let us make a couple of remarks about (T-Png). First, canonical cuts employed in (14) areextremelyweakbecauseeachoftheseconstraintscutsoffauniquebinaryvector. Hence, one should try to reinforce these constraints with problem-dependent valid inequalities. For instance, eachpathinequalityin(9)cuts-offauniquepathotod. Theycanbeimprovedas follows. Instead of considering a whole path from o to d, we can forbid its smallest subpath that is not feasible for the time windows. By doing so, we cut off all paths from o to d that contain the forbidden subpath. Even further, these inequalities can be lifted to obtain the tournament inequalities [2]. Second,(T-Png)islikelytocontainaverylargenumberofconstraintsin(14). Therefore, a solution method that intends to solve (T-Png) efficiently should employ a cutting plane algorithm that alternates between feasibility checks – does the current x∗ belong to X(T) – and the addition of canonical cuts to a master problem [12, 2, 15]. An important issue in theseiterativetechniquesisrelatedtohowtoperformthefeasibilitycheck. Abinaryvector x∗ belongstoX(T)ifandonlyifthereexistsaT ∈T suchthatTx>d,whichisequivalent to ∃i∈{1,...,s} s.t. maxT x>d . (15) i i Ti∈Ti Hence, checking whether x∗ belongs to X(T) amounts to solve s linear programs. Solving s linearprogramscanbetimeconsumingingeneral. Hence,itisusefultodevisemoreefficient algorithmsthatmakeuseoftheparticularstructureoftheproblemundertheconsideration and the uncertainty polytope T. We show later in this paper that this check can be improved when using the budget uncertainty from Bertsimas and Sim [7] and even further for T-VRPTW by taking into account that vector x describes a set of paths from o to d. 3.2 Adjustable robust optimization Model (T-P) suffers from a certain rigidity in the sense that a vector x must satisfy constraints (12) for all T ∈T to be feasible for (T-P). In particular, the problem variables arenotallowedtoadjustthemselvestothevaluestakenbytheuncertainparameters. Thisis an important modeling restriction that may not suit many problem formulations, including the formulation (RI) from last section. Namely, adapting (RI) in the way suggested by model (T-P) would yield an optimization problem where the arrival times would be fixed once for all travel times in the uncertainty set. Such an optimization problem is likely to be infeasible whenever T is not a singleton, see Example 1 from [1]. Ben-Taletal.[4]haveintroducedamoreflexibleclassofrobustprograms,whereasubset of variables is allowed to adapt itself as the uncertain parameters vary in the uncertainty set T. Applied to (P), their model essentially allows a subset of variables, which we denote by x2, to become functions defined on T. To keep notations simple, we suppose that these functions take only real values, x2 : T → Rn2. Hence, x = (x1,x2),c = (c1,c2),B = (B1,B2),T =(T1,T2), and x2 is allowed to vary as T1 takes different values in T. For the sake of simplicity, we also suppose that c2 =B2 =0. The problem becomes: min (c1)Tx1 (TR-P) s.t. B1x1 ≤b, T1x1+T2x2(T1)≤d, T1 ∈T, (16) x1 ∈{0,1}n1, x2(T1)∈Rn2, T1 ∈T. Problem (TR-P) is often called an adjustable robust program, which features two levels of decisions: first-stage variables x1 must be fixed before the uncertainty is revealed, while adjustablevariablesx2 canreacttoaccountfortheuncertainty. Noticethat(TR-P)canbe extended to the case of uncertain cost c1 by replacing the objective function with minz and 7 adding the restrictions z ≥ (c1)Tx1 to the set of uncertain constraints. Similarly, one can suppose that B2 (cid:54)=0 or that c2 (cid:54)=0. In the latter, one must add term max (c2)Tx2(T1) T∈T1 to the objective function. However, the situation where c2 or T2 is uncertain is more complicated and we do not address it in the following. Model(TR-P)hasaninfinitenumberofvariablesx2(T1)andconstraints(16). However, given that all constraints present in the problem are linear, it is easy to show that we can restrict ourselves to the extreme points of T, ext(T), which exist in finite number since T is a polytope. This simple result is recalled below. Lemma1. LetT ⊂Rsn1 beapolytopeandext(T)bethesetofitsextremepoints. Consider vectors x1 ∈{0,1}n1 and d∈Rs. There exists x2 :T →Rn2 such that T1x1+T2x2(T1)≤ d,∀T1 ∈ T if and only if there exists x2 : ext(T) → Rn2 such that T1x1 +T2x2(T1) ≤ d,∀T1 ∈ext(T). Lemma 1 allows us to solve (TR-P) through (ext(T)R-P). Though finite, (ext(T)R-P) tends to be very large because the number of extreme points of the uncertainty polytope tends to grow rapidly with the problem size. For this reason, we present in Section 4.1.1 techniques to reduce the number of extreme points. 4 The robust V RPTW From this section on, we suppose that travel times tk are not known with precision and ij belong to an uncertainty set. This is because in our application in maritime transportation, it often happens that delays occur during some of sailings due to unstable weather. We must however ensure that the routes proposed for the ships are feasible in most situations. Hence, we model the travel times with the help of an uncertainty polytope T ⊂ R|A||K|, making the optimization problem a robust program. In the following subsections, we apply the methods described in Section 3 to the formulations for VRPTW from Section 2. For eachformulation,wefirstpresenttherobustequivalentforageneraluncertaintypolytopeT. Then, we particularize the formulations to take into account the structure of the polytope T used in our numerical experiments. Γ Roughlyspeaking,Γimposesanupperboundonthenumberofdelaysthateachshipcan suffer. Asaconsequence,theuncertaintypolytopeT containsalltraveltimeswhereatmost Γ Γ trips suffer from delays for each ship. More precisely, we suppose that each component tk of t lies between its mean value tk and its peak value tk +tˆk and that, for each k ∈K, ij ij ij ij at most Γ of them can reach their peak values simultaneously. Formally, this is defined by T =× Tk where each Tk is such that each tk lies in [tk,tk +δktˆk] with 0≤δk ≤1, Γ k∈K Γ Γ ij ij ij ij ij ij (cid:80) δk ≤ Γ for some Γ ∈ Z with Γ < |A|. This is the budget uncertainty polytope studied ij ij by Bertsimas and Sim [7]. To keep notations simple, we suppose throughout that Γ is the same for each vehicle. It is however straightforward to extend our formulations and methods to the uncertainty polytopewheredifferentvaluesofΓareassociatedtodifferentvehicles,denotedT . Hence, Γ∗ ifthedecisionmakerfeelsthatsomeshipsaremorelikelytobesubjecttodelaysthanothers, she can increase the values of Γ for those ships. Beforepresentingtherobustformulations,weintroduceasetofconstraintsthathasbeen proposed by Chardy and Klopfenstein [9] to check that time windows are satisfied without the need of additional variables. Consider a binary vector x ∈ {0,1}|A||K| that describes a path p from i to i , that is, p=i ,...,i and xk =1 for each (i,j)∈p, such that xk =0 0 n 0 n ij ij otherwise. Constraints (4) and (5) for k along p are equivalent to (cid:88) a + tk ≤b , 0≤l <l ≤n. (17) il1 ilil+1 il2 1 2 l=l1,...,l2−1 Constraints (17) will be used in the next two subsections to check that a path satisfies the time windows. 8 4.1 Resource inequalities Model (RI) can be naturally extended to handle uncertain polytope T: x becomes the set of first-stage variables, while y becomes y(t), a function of t∈T. Thanks to Lemma 1, we only need to consider travel time vectors t that belong to ext(T). Hence, the robust problem contains equations (5) and (7) written for every scenario t∈ext(T), that is a ≤y (t)≤b , i∈N,t∈ext(T), (18) i i i and (cid:88) y (t)−y (t)+ max{(b +tk −a ),0}xk ≤b −a , (i,j)∈A,t∈ext(T). (19) i j i ij j ij i j k∈K:(i,j)∈Ak The robust version of (RI) becomes (cid:88) (cid:88) min c xk ij ij k∈K(i,j)∈Ak (ext(T)-RI) s.t. (2),(3),(18),(19) xk ∈{0,1}, (i,j)∈Ak, k ∈K. ij A crucial feature of formulation (T-RI) is that its numbers of “robust” constraints and variables do not depend on |K|. Namely, the number of variables y and the number of con- straints (18) increase with |N| and |ext(T)|, while the number of constraints (19) increases with |A| and |ext(T)|. This remarkable property is due to Proposition 1, which allows to group constraints (4) associated to different vehicles. To simplify notations, we assume in the rest of this section that Ak =A for each k ∈K. However, the results presented next are easy to generalize to the case where Ak can be different from Ah for any pair of distinct vehicles k and h. In what follows, we denote the elements of ext(T) either by extreme points or by scenarios. Considering every scenario in ext(T)iscertainlyprohibitivewhensolvingreasonablesizeinstances. Inthenextsubsection, we focus on approaches to reduce the number of scenarios to be considered by proposing formulations that are equivalent to (ext(T)-RI). Given a finite set S ⊂ R|A||K|, we define (S-RI) as (ext(T)-RI) by replacing ext(T) with S in constraints (18) and (19). Hence, we want to characterize finite sets S with the lowest possible cardinality that satisfies the following property: a first stage solution x is feasible for (S-RI) if and only if it is feasible for (ext(T)-RI). We mention that S may not be a subset of ext(T). 4.1.1 Reducing the number of scenarios The simplest approach tries to withdraw individual scenarios from ext(T) by comparing them to other scenarios that are more representative in the sense explained next. Namely, we say that an extreme point t∈ext(T) is dominated by another extreme point τ ∈ext(T) if any solution for first stage variables x feasible for scenario τ is also feasible for t. Hence, onlythoseextremepointsthatarenotdominatedneedtobeconsidered. Inparticular,there exists an easy sufficiency condition to check whether t is dominated by τ. Proposition 2. Let t,τ be two vectors in ext(T). If τk ≥tk for each k ∈K and (i,j)∈A, ij ij then t is dominated by τ. Proof. Theresultfollowsdirectlybyconsideringtherewritingofthetimewindowsperformed in (17). In what follows we make an abuse of language and say that a vector t is dominated by τ when they satisfy the conditions of Proposition 2. The concept of dominance has already been used with success in the context of robust network design [19, 20]. 9