MSc Thesis Defense: Aksel Akmercan, SAMPLE AVERAGE APPROXIMATION AND LARGE NEIGHBORHOOD SEARCH METHODS FOR THE STOCHASTIC VEHICLE ROUTING PROBLEM WITH FLEXIBLE DELIVERIES, Date & Time: 03 July, 2026 – 10:30 AM, Place: FENS G035

SAMPLE AVERAGE APPROXIMATION AND LARGE NEIGHBORHOOD SEARCH METHODS FOR THE STOCHASTIC VEHICLE ROUTING PROBLEM WITH FLEXIBLE DELIVERIES

Aksel Akmercan
Industrial Engineering, MSc Thesis, 2026

Thesis Jury

     Asst. Prof. Duygu Taş Küten (Thesis Advisor)

  Asst. Prof. Esra Koca

  Prof. Çağrı Koç

Date & Time: July 3rd, 2026 –  10:30 AM

Place: FENS G035

Keywords : Vehicle Routing Problem, Flexible Deliveries, Stochastic Travel Times,

Sample Average Approximation, Large Neighborhood Search

Abstract

The increasing complexity of last-mile logistics has motivated the development of routing models that consider customer flexibility and travel time uncertainty. In this thesis, we study the Vehicle Routing Problem with Flexible Deliveries and Stochastic Travel Times (VRPFD-STT), where customers can be served at alternative delivery locations and travel times follow Gamma distributions. The thesis consists of two studies. First, a Sample Average Approximation (SAA) framework is developed to solve the stochastic optimization problem through a finite set of travel time scenarios. For 16 out of 20 benchmark instances, the lower and upper bounds obtained from the SAA framework coincide, resulting in a zero gap and demonstrating the effectiveness of this method on small-sized instances. However, computational requirements increase significantly as instance size grows, limiting the applicability of the exact stochastic optimization approach to larger problems. To address this limitation, the second part of the thesis proposes a scenario-based Large Neighborhood Search (LNS) heuristic. The proposed method evaluates routing decisions under multiple travel time scenarios and incorporates four destroy and four repair operators. In particular, a min-max insertion mechanism is developed to improve robustness against adverse travel time realizations. Computational experiments on 40 benchmark instances show that the proposed heuristic is capable of producing high-quality solutions in reasonable computation time. On average, the minimum-cost solutions generated by the heuristic are 5.99% higher than the upper-bound solutions obtained by a column-generation-based exact method. The results indicate that the proposed SAA and scenario-based LNS approaches provide effective solution methodologies for the VRPFD-STT.