Efficient GRASP solution approach for the Prisoner Transportation Problem

Every day, resources are allocated to the transportation of prisoners to and from services such as hospitals and court proceedings. The optimal allocation of the resources – such as protected vehicles, drivers, and guards – is a complex task that requires significant efforts of human planners. For this reason, a recent paper described the Prisoner Transportation Problem (PTP), that aims to optimize the transportation of convicts between origin–destination pairs within pre-defined time windows. In addition to the similarities with the Vehicle Routing Problem with Time Windows, the PTP presents many additional challenges induced by the use of multi-comparted vehicles and incompatibility constraints, related to the safety of both prisoners and personnel. To efficiently solve the PTP, this paper proposes a GRASP approach, that was tested on a dataset of real-size instances, and the results show significant improvements with respect to the only competing approach proposed in the literature, both in terms of solution quality and computational times required to find them.