AVariable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

MICHAEL POLACEK, RICHARD F. HARTL AND KARL DOERNER Department of Production and Operations Management, Institute of Management Science, University of Vienna, A-1210 Vienna, Austria email: michael.polacek@univie.ac.at email: richard.hartl@univie.ac.at email: karl.doerner@univie.ac.at
MARC REIMANN Institute for Operations Research, ETH Zurich, CH-8092 Zurich, Switzerland email: marc.reimann@ifor.math.ethz.ch
Submitted in August 2003 and accepted by Stefan Voss in October 2004 after 2 revisions
Abstract
The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS)tosolveMultiDepotVehicleRoutingProblemswithTimeWindows.Thepaperhastwomaincontributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results showthattheapproachiscompetitivewithanexistingTabuSearchalgorithmwithrespecttobothsolutionquality and computation times.
KeyWords: Metaheuristic, Variable Neighborhood Search, VNS, Multi Depot Vehicle Routing Problem with Time Windows, MDVRPTW

1. Introduction
   Vehicle Routing Problems (VRP) are classical combinatorial optimization problems with considerable economic significance as pointed out by the following statement. “Thelargenumberofreal-worldapplications,bothinNorthAmericaandinEurope,have widelyshownthattheuseofcomputerizedproceduresforthedistributionprocessplanning producessubstantialsavings(generallyfrom5to20%)intheglobaltransportationcosts.It is easy to see that the impact of these savings on the global economic system is significant. Indeed, the transportation process involves all stages of the production and distribution systems and represents a relevant component (generally from 10 to 20%) of the final cost of the goods.”1 A brief description of the basic VRP can be given as follows: customers with known demands are serviced by a homogeneous fleet of vehicles with limited capacity. Routes are assumed to start and end at exactly one depot, each customer is fully served by exactly
   614 POLACEK ET AL.
   one vehicle and the primary objective is to minimize the total distance travelled by all vehicles. However,tosatisfyreal-lifedemandsadditionalconstraintsarecomplicatingthedevelopmentofappropriatemethods.Forvariousapplications,likebankdeliveries,postaldeliveries or school bus routing, a time interval is also associated with each customer to define the timeofservice.Moreover,largecompanies,astheycanbefoundinthepetroleumindustry, havemorethanjustonedepotfromwhichservicestationsaresupplied.Onaccountofthis, multiple depots are a reasonable extension to the classical VRP. The basic VRP and basically all of its variants belong to the class of NP-hard problems (c.f., Garey and Johnson (1979)) such that exact algorithms, as described in Kohl et al. (1999) and Laporte and Nobert (1987), become highly time consuming as soon as problem instancesareincreasinginsize.Thus,forlargescaleprobleminstancesastypicallyfoundin industrial applications finding an ‘optimal’ solution is not practicable. Therefore different types of heuristics, ranging from route construction over route improvement heuristics to sophisticated metaheuristics emerged which quickly produce solutions of reasonable quality. The aim of this paper is to propose an algorithm based on the philosophy of the Variable NeighborhoodSearch(VNS),ametaheuristic,describedinHansenandMladenovi´ c(1999) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two maincontributions.First,fromatechnicalpointofview,itpresentsthefirstapplicationofa VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with the Tabu Search (TS) algorithm published in Cordeau, Laporte, and Mercier (2001), with respect to both solution quality and computation times. Theremainderofthepaperisorganizedasfollows.Inthenextsectionaproblemdescription is given and related work is discussed. Section 3 reviews the main ideas underlying VNSandprovidesthedetailsoftheimplementationandthedesignchoicesforthedescribed problem. Computational results are presented and discussed in Section 4. In Section 5 we present results for an improved version of the algorithm that takes into account route duration considerations before Section 6 concludes the paper with a r´esum´eofthe applied approach and comments on possible directions for further research.
2. Problem description and related work
   The problem tackled in this paper is the Multi Depot Vehicle Routing Problem with Time Windows (MDVRPTW). It is a generalization of the well known Vehicle Routing Problem with Time Windows (VRPTW) where instead of one depot, several depots with different locations and associated fleets have to be considered. Thus, the problem is defined on a complete graph G=(V, A), where V ={v1,…,vm,vm+1,…,vm+n}is the vertex set and A={ (vi,vj):vi,vj ∈ V,i= j} is the arc set. Vertices v1 to vm correspond to the m depots, while the vertices vm+1 to vm+n represent the n customers. Each vertex vi ∈ V has several nonnegative weights associated to it, namely, a demand di,aservice time si, as well as an earliest ei and latest li possible start time for the service, which define a time window [ei,li]. For the depots these time windows correspond to the opening hours.
   VNS FOR THE MDVRPTW 615
   Further, the depot vertices v1 to vm feature no demands and service times, i.e. di =si =0, ∀i ∈{ v1,…,vm}. Associated to each arc (vi,vj)isanonnegative travel time or costc ij. Finally, a fleet of K vehicles is located at the m depots. Each vehicle k has associated a nonnegative capacity Dk and a nonnegative maximum route duration Tk. Note, that the distribution of vehicles over the depots is fixed a-priori and is given as input data. Based on this graph, the MDVRPTW consists of building K vehicle routes such that eachvehiclestartsandendsatitshomedepot,eachcustomerisservedbyoneandonlyone vehicle,thetotalloadanddurationofvehiclek doesnotexceed Dk and Tk respectively,the serviceateachcustomeri beginswithintheassociatedtimewindow[ei,li]andeachvehicle route starts and ends within the time window of its depot. The objective is to minimize the total distance travelled by all vehicles. As stated above, the MDVRPTW is a generalization of the VRPTW and is thus NPhard. Hence, exact approaches are bound to be efficient for very small problem instances only and the use of heuristics should be justified. For the VRPTW this research direction has been followed intensively as can be seen from an abundant number of papers describing different approaches for the VRPTW, ranging from simple heuristic methods to very sophisticated metaheuristics of all kinds. Reviews of these works have been put together by Braysy and Gendreau (to appear). Also, the MDVRP, i.e. the version of the problem without time windows has been studied by several authors (c.f. e.g., Chao, Golden, and Wasil (1993), Cordeau, Gendreau, and Laporte (1997), and Renaud, Boctor, and Laporte (1996)). To our best knowledge there is only one paper that addresses (among other problems) the MDVRPTW, namely the work of Cordeau et al. from 2001 (see Cordeau, Laporte, and Mercier (2001)) describing the application of an adapted TS algorithm, which had previously been applied to the MDVRP and the Periodic VRP. The main characteristics of this approach are the use of a very simple neighborhood, a move of one customer from one route to another, and the fact that infeasible solutions are allowed during the search. To ensure that the algorithm is able to move from infeasible to feasible parts of the search spaceanadaptivepenaltyfunctionisusedthatreactstothesearchhistory.Numericalresults are presented for the Periodic VRPTW, the MDVRPTW and the VRPTW. While for the formertwoproblemsnobenchmarksexisted,theresultsfortheVRPTWprovedthequality oftheapproachasillustratedbyacomparisonwithstateoftheartapproachesontheclassic Solomon instances.
3. VNS for the MDVRPTW
   VNS is a recent metaheuristic for solving combinatorial and global optimization problems proposedbyMladenovi´ candHansenin1997(c.f.e.g.,HansenandMladenovi´ c(1999,2001) andMladenovi´ candHansen(1997)).Thebasicideaisasystematicchangeofneighborhood withinalocalsearch.Here,severalneighborhoodstructuresareusedinsteadofasingleone, asitisgenerallythecaseinmanylocalsearchimplementations.Furthermore,thesystematic change of neighborhood is applied during both a descent phase and an exploration phase, allowing to get out of local optima.
   616 POLACEK ET AL.
   Figure 1. Steps of the basic VNS (c.f. Hansen and Mladenovi´ c (2001)).
   Differingfromotherlocalsearchbasedmetaheuristics,VNSdoesnotfollowatrajectory but rather “explores increasingly distant neighborhoods of the current incumbent solution, and jumps from this solution to a new one if and only if an improvement has been made. In thiswayoftenfavorablecharacteristicsoftheincumbentsolution,e.g.,thatmanyvariables arealreadyattheiroptimalvalue,willbekeptandusedtoobtainpromisingneighboringsolutions.Moreover,alocalsearchroutineisappliedrepeatedlytogetfromtheseneighboring solutions to local optima.”2 The steps of the basic VNS are shown in figure 1. Here, Nκ(κ=1,…,κmax)isafinite set of pre-selected neighborhood structures. The stopping condition may be, e.g., maximumCPUtimeallowed,maximumnumberofiterationsormaximumnumberofiterations between two improvements. ThebasicVNSconsistsofbothastochasticcomponent,i.e.,therandomizedselectionof a neighbor in the shaking phase, and a deterministic component, that is the application of a local search in each iteration. Finally, the solution obtained is compared to the incumbent oneandwillbeacceptedasnewstartingpointifanimprovementwasmade,otherwiseitwill berejected.Thus,theprocedureisadescent,firstimprovementmethodwithrandomization. However, as pointed out in Hansen and Mladenovi´ c (2001), it could be transformed into a descent-ascent method without much additional effort. Thereby x is also set to x with some probability, even if the solution is worse than the incumbent. Below,theimplementationofeachpartoftheVNStosolvetheMDVRPTWisdescribed. Thedescriptioncomprehendsthebuildingofaninitialsolution,theshakingphaseincluding theneighborhoodstructuredefinitionwiththenecessaryexchangeoperators,thelocalsearch method, and the acceptance decision in the Move or not phase.
   3.1. Initial solution
   To construct an initial solution for the MDVRPTW, each customer i is first assigned to the nearest depot. Afterwards, all customers within a depot are ordered by the center of their timewindow 1 2(ei +li).Ifthisisdone,routesareconstructedforeachdepotusingthesame simple procedure described in figure 2.