A comparison of different lower bounding procedures for the routing of automated guided vehicles in an urban context. (2015) - Fatnassi, Ezzeddine; Chaouachi, Jouhaina
We propose different lower bounding procedures to solve the problem of routing a set of automated guided vehicles in an urban context. This problem consists of designing a set of low-cost roads starting and ending at a depot while satisfying a set of transportation demands in an urban area. The problem is treated under a set of different constraints, such as battery constraints and time window constraints. Our lower bounding approach consists of a decomposition method in which we first solve a relaxed problem. We then deal with the set of infeasible routes obtained from the relaxed problem. The different procedures developed in this paper allow us to find a set of good-quality lower bounds.