Alan Rodolfo Osorio Mora - University of Bologna

will give a presentation on 

Algorithms for latency routing and location routing problems

Abstract:

The latency location routing problem (LLRP) is a relatively new variant of the well-known location routing problem. Given a set of customers to be served and a set of potential uncapacitated depots, the problem consists of determining the subset of at most p depots to open, the customers and the vehicles to be assigned to each open depot and the routes to be constructed to fulfill the demand of the customers by taking into account the capacity of the vehicles. The objective is to minimize the sum of the arrival times at the customers, i.e., the latency. The multi-depot cumulative capacitated vehicle routing problem (MDCCVRP) is a particular case of LLRP in which all the available depots can be opened. The multi-depot k-traveling repairman problem (MDk-TRP) is a particular case of MDCCVRP in which there are no capacity constraints for the vehicles. A novel iterated-local-search-based metaheuristic algorithm called M-ILS is proposed for the solution of the LLRP, the MDCCVRP, and the MDk-TRP. Extensive computational experiments indicate that M-ILS outperforms the currently published algorithms in terms of solution quality, requiring competitive computing times. The LLRP assumes that all the parameters involved are deterministic. In real-life situations it may be not true, and uncertainty must be taken into account. In this talk, we also consider an LLRP with stochastic travel times (LLRP-STT). Since latency routing problems have been mainly motivated by applications in disaster operations management (e.g. humanitarian logistics problems) a risk-averse decision maker is assumed. A two-stage stochastic programming model and a variable neighborhood search (VNS) heuristic are proposed for solving the LLRP-STT. Furthermore, for solving instances with continuous probability distributions, i.e., an infinite number of scenarios, a sampling method and a simheuristic algorithm are developed. The effectiveness of the proposed methods is studied through extensive computational experiments. Moreover, several insights are presented.