Back to search

McMaster University

A Meta-Heuristic Algorithm for Vehicle Routing Problem with Interdiction

Abstract

dc:description.abstract

This thesis addresses the Vehicle Routing Problem with Interdiction (VRPI), an extension of the classic Vehicle Routing Problem (VRP) that incorporates the risk of route interdiction due to events such as natural disasters, armed conflicts, and infrastructural failures, among others. These interdictions introduce uncertainty and complexity into logistics planning, requiring innovative approaches to the routing process. This research employs both exact methods, using the CPLEX solver, and heuristic methods, particularly using the Greedy Randomized Adaptive Search Procedure (GRASP), to solve VRPI with different instance sizes. This research’s key contributions include successfully implementing the GRASP algorithm on large-scale benchmark instances, representing a significant advancement over prior implementations that focused on smaller, randomly generated instances. A flexible framework was also developed to adapt the GRASP methodology for different VRP variants, including the Capacitated Vehicle Routing Problem (CVRP) and Split Delivery Vehicle Routing Problem (SDVRP), with and without interdiction. A feasibility analysis for small instances was developed using CPLEX, highlighting the sensitivity of VRPI solutions to interdiction probabilities, particularly in scenarios with tight capacity constraints. The findings of this analysis are extended to large instances. Additionally, a 3-fold logic was incorporated in the GRASP implementation—focused on minimizing cost, minimizing interdiction, and minimizing demand—proved crit- ical in facing the VRPI challenges, and provided high-quality solutions with reduced computational effort. Including the minimum demand logic in GRASP was instrumen- tal during the implementation and numerical experimentation for large benchmark in- stances. The implications of this thesis are significant for operational research (OR), particularly in high-risk environments where route interdictions can occur. Future research directions include generating more diverse benchmark instances for VRPI, exploring the impact of variability in interdiction probabilities on solution quality and computational time, and applying exact methods like dynamic programming to solve large VRP instances.

Degree

thesis:*
Department dc:contributor.department
Computational Engineering and Science
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hinrichsen Picand, Carlos
Advisor dc:contributor.advisor
  • Huang, Kai

Subjects

dc:subject × 9

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Hinrichsen Picand, Carlos. A Meta-Heuristic Algorithm for Vehicle Routing Problem with Interdiction. 2024. http://hdl.handle.net/11375/30390