PhD.Dissertation DefenseSaeedeh Ahmadi Basir
The Periodic Vehicle Routing Problem with Visual Attractiveness and Driver Consistency Considerations
Saeedeh Ahmadi Basir
Industrial Engineering, PhD Dissertation, 2014
Thesis Jury
Asst. Prof. Gizem Özbaygın (Thesis Advisor),
Asst. Prof. Esra Koca,
Asst. Prof. Duygu Taş Küten
Assoc. Prof. Çağrı Koç
Asst. Prof. Sina Rastani
Date & Time: July 24th, 2014 – 11 AM
Place: FENS L058
Keywords : Vehicle Routing, Visual Attractiveness, Driver Consistency, Parallel Tempering, Adaptive Large Neighborhood Search
Abstract
This thesis explores advanced methodologies and innovative approaches to the Periodic Vehicle Routing Problem (PVRP) and its variants. Initially, we propose a new vehicle flow formulation for the PVRP and strengthen it with valid inequalities. We also investigate two prominent formulations for the PVRP available in the literature: a commodity flow formulation, referred to as the load-based formulation, and a cut-based formulation which is adapted from a formulation originally developed for a variant of the PVRP. We also extend these formulations to model the PVRP with time windows (PVRPTW) and employ valid inequalities to tighten the resulting formulations. A comprehensive computational study is then carried out to compare the performances of alternative PVRP and PVRPTW formulations on various sets of benchmark instances with different characteristics. The results attest to the robustness and the consistency of the proposed formulation and its strengthened versions in producing good quality solutions, especially for large instances although the load-based formulations tend to perform well in small instances. Subsequently, we address the PVRP using a Logic-Based Benders Decomposition approach (LBBD) and a Column Generation-based heuristic. Our findings reveal that the Column Generation algorithm achieves near-optimal solutions, deviating by an average of only 0.21% from the best-known solutions in the literature. Further, we incorporate visual attractiveness and driver consistency constraints into the PVRPTW, developing a Mixed-Integer Linear Programming (MILP) formulation for this extended problem (PVRPTWVADC). To solve the PVRPTWVADC, we propose an Adaptive Large Neighborhood Search (ALNS) algorithm and a Parallel Tempering-based ALNS (PTALNS). Comprehensive computational studies highlight the robustness and superior performance of the PTALNS algorithm.