The periodic vehicle routing problem with visual attractiveness and driver consistency

This thesis explores advanced methodologies and innovative approaches to thePeriodic Vehicle Routing Problem (PVRP) and its variants. Initially, we propose anew vehicle flow formulation for the PVRP and strengthen it with valid inequalities.We also investigate two prominent formulations for the PVRP available in theliterature: a commodity flow formulation, referred to as the load-based formulation,and a cut-based formulation which is adapted from a formulation originally developedfor a variant of the PVRP. We also extend these formulations to model thePVRP with time windows (PVRPTW) and employ valid inequalities to tighten theresulting formulations. A comprehensive computational study is then carried out tocompare the performances of alternative PVRP and PVRPTW formulations on varioussets of benchmark instances with different characteristics. The results attest tothe robustness and the consistency of the proposed formulation and its strengthenedversions in producing good quality solutions, especially for large instances althoughthe load-based formulations tend to perform well in small instances. Subsequently,we address the PVRP using a Logic-Based Benders Decomposition approach anda Column Generation-based heuristic. Our findings reveal that the Column Generationalgorithm achieves near-optimal solutions, deviating by an average of only0.21% from the best-known solutions in the literature. Further, we incorporatevisual attractiveness and driver consistency constraints into the PVRPTW, developinga Mixed-Integer Linear Programming formulation for this extended problem (PVRPTWVADC). To solve the PVRPTWVADC, we propose an Adaptive LargeNeighborhood Search (ALNS) algorithm and a Parallel Tempering-based ALNS(PTALNS). Comprehensive computational studies highlight the robustness and superiorperformance of the PTALNS algorithm.