Report

An Efficient Large Neighborhood Search based Matheuristic for Rich Vehicle Routing Problems S im ona M ancini DIST, Politecnico di Torino, Torino, Italy Outlines • • • • • • • VRP and its variants Real life VRPs Problem description Mixed Integer Programming formulation Large Neighborhood based matheuristic Computational results Conclusions and future perspectives 2 The Vehicle Routing Problem Further constraints: • Limited number of vehicles • Capacity • Route length • Route duration 3 VRP variants • • • • • • • • • • • VRP with Time Windows VRP with Pick-up and Delivery VRP with backhauls VRP with heterogeneus fleet Multi Depot VRP Multi-Period VRP Periodic VRP VRP with Stochastic Demands Dynamic VRP …. Multi Echelon VRP (Two-Echelon, Intermediate Facilities, Location routing, Truck and Trailer..) • … 4 A complex real-life VRP VRP Heterogeneous Fleet Multi-Depot MDMPVRPHF 5 Multi-Period Heterogeneus VRP Real-life problems Studied in literature • Capacity • Usage cost • Kilometric cost • vehicle characteristics and compatibility with customers Refrigerated Freezer Armoured • Autonomy smaller for electric vehicles • Fuel consumption rate 6 Larger for big trucks Multi-depot VRP Routes start from and end at the same depot Can be split into an assignment problem plus several VRPs which can be solved separately 7 Real life Multi-Depot Routes may end at a different depot form the starting one if it is convenient More complex to model Cannot be split into assignment+routing 8 Multi-period VRP • Works with a planning horizon of T days • Each customer has frequency of visit requirements (k out of T days) • Visits to customers must occor on allowed k-days combinations • Decision made for one period impact outcomes in other periods Assign visits schedule to each customer Solve a vehicle routing problem for each day 9 Real life multi-period I Distribution • Grocery and soft drink distribution • Fuel oil and industrial gas delivery • Pharmacies supply • Automobile parts distribution Waste Collection Maintenance services Surveillance patrols 10 Real life multi-period II • What does matter is not only the period in which a customer is served, but also the moment within that period, in which the delivery is performed • In a multi-depot multi-period problem the fleet available at each depot may change across the periods, if vehicles do not come back to their starting depot Visits Scheduling and Routing cannot be treated separately anymore, since the input data for a VRP related to a given period, depends on the routing plan of the previous ones 11 MDMPVRPHF I • No multiple visits • Customers may be served in one of the periods in which they are available, taking into account Days off Good available only after a given period • Multi depot where routes may start from and end at different depots • Depending on products availabilty, not all the customer may be served by all the depots (may be bypassed adding fictitious huge distance between customers and not available depots) 12 MDMPVRPHF II • Heterogeneous fleet Vehicles initially located at a depot Variable capacity, usage cost, cost/km Characteristics (refrigerated, freezer..) and compatibility with customers Product request (perishable food, ice cream..) Customer location limitation (large trucks cannot enter city center..) 13 Problem definition I • The problem consist of serving a set of customers, I, at the minimum cost. • Each customer i requires a quantity of goods qi, which can be delivered from one of more depots d belonging to the set of depots D, depending on the availability of the requested products at the depots. • Delivery may be carried out by vehicles which are compatible with customers request, during a time-slot (day) in which the customer is available. • Further temporal constraint may be given by strictly deadlines imposing that customer i must receive his order before day s goods availability (in some cases goods may be available only after day s). 14 Problem definition II • A set of vehicles V is located at the depots. • For each vehicle v is known the capacity Cv, the cost per min of usage μv, and the depot d where the vehicle is located. • A set of possible routes K is given, where for each route k is known the vehicle v to which it is associated the day s in which it is scheduled. 15 Problem definition III • A customer may be assigned to a route only if it is performed • A vehicle v is supposed to be located at depot d on day s (for s > 1) if d is the arrival depot of the routes performed by v on day s - 1 • If v has not been used in day s - 1 he is supposed to be located at the arrival depot of its last performed route, or if it has not been used yet, at the depot where it was located at the beginning of the time-horizon. 16 Input Data I 17 Input data II 18 Input Data III 19 Variables 20 Objective function Cost minimization 21 Assignment constraints I A customer can be visited by a route only if it has been assigned to it Each customer must be assigned to one and only one route 22 Assignment constraints II Customer-depot compatibility Each route, if performed must start and end at a depot Customers may be assigned to a route only if is performed 23 Constraints I Subtours elimination Capacity not exceeded Route duration 24 Constraints II • Constraints allowing to determine the starting depot for each routes, depending on the vehicle and the routes performed by it on the previous days. 25 Route Compatibility Constraints 26 Variables domain 27 Classical Local Search heuristics • Small neighborhood search often remain trapped into local minima • Only very limited regions of the solution space are reached • Multi-start methods allow to explore different regions but we have no guarantees that we did not discard promising areas • Too sensitive to the diversification process 28 Large Neighborhood Search I • Large neighborhoods allow to explore wider regions of the solution space • Exponential number of solutions • Analyze the neighborhood is strongly time consuming • Only a subset of the solutions is actually analyzed 29 Large Neighborhood Search II • Neighborhoods are implicitly defined • Destroy and repair operators are applied Destroy operators Route removal Depot closure Remove k% of the customers form the solution Remove k% longest arcs Random selection vs quality criteria based 30 Large Neighborhood Search III • Repair operators: Optimal Shortest path Network-flow based improvement algorithms Explicitly enumeration (time-consuming) Heuristic Best insertion Auction insertion Truncated Branch and Bound Further considerations • Too Small destroy operators yields to small neighborhoods • Too Large destroy operators may yield a loss of good information and the reconstructed solution may be worse than the previous one • Simply repair operators may yield to poor quality solutions • Complex repair operators may be very time consuming 32 A LNS based Matheuristic I • General idea Exahustively exploit the whole neighborhood in a short computational time High quality solution Add at each iteration a set of constraints which force the largest part of the variables to assume the same values they assumed in the current solution Let the model solve the ultra-constrained problem and to determine the optimal value for the other variables This correspond to solve to the optimality an exponential neighborhood The ultra-constrained problem may be solved to the optimality in short computational times At each iteration a different subset of the variables is kept fixed 33 A LNS based Matheuristic II • Working on the customer-to-route assignment variables Yik • A initial feasible solution is computed • At each iteration p customers are randomly selected • All the others N-p customers are assigned to the same route to which they were assigned in the initial solution • The p selected ones assignment is let free 34 A LNS based Matheuristic III • This can be exploited adding the following set of constraints to the model • The ultra-constrained model is run and solved to the optimality 35 A LNS based Matheuristic IV • The new obtained solution is the best one in the exponential neighborhood • This solution is kept as initial solution for the following iteration • The algorithm terminates after a maximum number of iterations (MAXITER) is reached a maximum number of iterations without improvements (MAXNOIMPROVE) is reached 36 Further considerations I • The parameter p can be aritbrarly chosen keeping in mind that small values of p allow a limited perturbation with the risk to remain trapped into local minima, while very big values generate such a large neighborhood search which cannot be easily exhaustively explored in a short computational 37 Further considerations II • This procedure need an initial feasible solution form which to start which is computed letting the model run for TIMELIMIT seconds enough time to find a feasible solution • The initial solution quality is not a crucial issue, because, due to the strong diversication inserted in the algorithm, the matheuristic is capable to explore regions potentially far, in the solutions space, from the starting point and to converge to a very good solution even starting from a poor quality one. This is a strong good point! 38 Computational tests I • • • • • Number of customers: 30 Number of depots: 3 Number of vehicles: 6 Number of days: 5 Number of routes: number of vehicles * number of days = 30 • Maximum route duration: 11 hours • Average speed 80 Km/h 39 Instances Description I • 9 instances with different combination of customers-vehicles compatibility and customers availability levels • Food delivery is generally characterized by a low compatibility and a high availability • Electronic commerce (like amazon..) is characterized by complete compatibility and low availability 40 Instances Description II • Three customers-vehicles compatibility levels: High compatibility: around 90% of customer-vehicle assignments are feasible Medium compatibility: around 80% of customer-vehicle assignments are feasible Low compatibility: around 60% of customer-vehicle assignments are feasible • Three customers availability levels: High availability: around 95% of customer-day assignments are feasible Medium availability: around 70% of customer-day assignments are feasible Low availability: around 30% of customer-day assignments are feasible 41 Model results Time-limit 3600 sec – corei7 at 1.8 Ghz and 8 Gb of RAM 42 Comparison LNS vs MODEL Average results are very similar to best results Robustness of the solution 43 Comparison LNS vs INITIAL SOL Averaged computational times for the MH are around 200 seconds 44 Conclusions I • The MH is robust • It is able to strongly improve the initial solution (25%) • It is able to sensibly improve (5-6%) the MODEL results strongly reducing computational times • The MODEL performs better on highly constrained problems, therefore the improvement with MH is smaller because we compare its results with an high quality solution 45 Future Developments I • Extremely portable method • Application to other rich VRPs Multi-Depot Two-Echelon VRP • Can be easily embedded in a more complex metaheuristic framework VNS ALNS 46 Future Developments II • The same approach can be used for other kind of neighborhoods Arcs variables fixing Route destruction Depote closure • And for other kind of problems Scheduling Packing Other problems working with binary variables 47 Thank you for the kind attention 48