Exact approaches for the time-dependent elementary shortest path problem with resource constraints

GONZALO LERA ROMERO; JUAN JOSÉ MIRANDA BRONT

Córdoba

Congreso; 46 Jornadas Argentinas de Investigación Operativa; 2017

Sociedad Argentina de Informática e Investigación Operativa

Congestion in large cities and populated areas is one of the major challenges in urban logistics, becoming one of the major issues in city planning and last-mile logistics due to its economic, social and environmental impact. Most of the research devoted to the Vehicle Routing Problem (VRP) considers that travel times between any two locations are fixed along the time horizon. In the last few years, there has been a trend to enrich these models by incorporating more complex travel time functions to capture the effect of congestion, known as Time-Dependent VRPs (TDVRP, see, e.g., Gendreau et al. (2003), for an updated survey).Incorporating the congestion explicitly at a tactical level is a key aspect of modern Decision Support Systems (DSS) in order to obtain distribution plans that are representative of the real-life operations (Huang et al. [3]). However, most of the studies related to the TDVRPs are still limited to consider standard operational constraints and state-of-the-art algorithms require further developments, as shown in Dabia et al. (2013) and Montero et al. (2017), in order to derive into automated tools that can be implemented in practice.Exact approaches for multi-vehicle variants of the classical VRP generally resort to Integeer Linear Programming (ILP) and decomposition techniques, resulting in Branch and Price (BP) and Branch-cut and price (BCP) algorithms. These approaches produce the best results in general, and one of their key ingredients rely on the pricing problem within the column generation algorithm to solve the LP relaxation at each node of the enumeration tree. When tackling a TDVRP, the pricing problem can be formulated as a Time-Dependent Elementary Shortest Path Problem with Resouruce Constraints (TDESPPRC). Dabia et al. (2013) follows this approach and propose a BP algorithm for the capacitated TDVRP with time windows (TDVRP-TW) and Sun et al. [6] further consider the TDESPPRC with precedence constraints. In both papers, the corresponding problem is tackled by Dynamic Programming (DP) algorithms the pricing step appears as a very difficult and challenging problem that requires further developments.The aim of this research goes in that direction. We consider the TDESPPRC under different operational constraints and explore the effectiveness of different exact approaches for the problem. In particular, we study the TDESPPRC with limited vehicle capacity and focus on two variants: with and without time windows. For this purpose, we provide an efficient implementation of the tailored DP algorithm proposed in Dabia et al. (2013) as well as an enhanced ILP formulation based on the one proposed in Sun et al. (2017). Furthermore, we build upon the works by Taccari (2016) and Jepsen and Pisinger (2011) on the ESPPRC with time-independent travel times and include a cutting plane algorithm to improve the quality of the lower bounds provided by the LP relaxation. Computational experiments are conducted over benchmark instances for the TDVRP-TW as well as on new instances for the TDVRP, which to the best of our knowledge has not been studied so far in the literature. The proposed algorithms are evaluated by considering the solution of the initial LP relaxation of the corresponding TDVRP variant, focusing on their performance in terms of both computing time and solution quality