Author(s): Ferreira, Luciano ; Maciel, Marcos Vinicius Milan ; Valério de Carvalho, José Manuel ; Silva, Elsa ; Alvelos, Filipe Pereira e
Date: 2025
Persistent ID: https://hdl.handle.net/1822/95468
Origin: RepositóriUM - Universidade do Minho
Subject(s): Transportation; Vehicle routing; Prisoner transportation problem; Inter-passenger conflicts; Heuristic
The Prisoner Transportation Problem is an NP-hard combinatorial problem and a complex variant of the Dial-aRide Problem. Given a set of requests for pick-up and delivery and a homogeneous fleet, it consists of assigning requests to vehicles to serve all requests, respecting the problem constraints such as route duration, capacity, ride time, time windows, multi-compartment assignment of conflicting prisoners and simultaneous services in order to optimize a given objective function. In this paper, we present a new solution framework to address this problem that leads to an efficient heuristic. A comparison with computational results from previous papers shows that the heuristic is very competitive for some classes of benchmark instances from the literature and clearly superior in the remaining cases. Finally, suggestions for future studies are presented.
