The prisoner transportation problem

Jan Christiaens, Hatice Çalik, Tony Wauters, Reshma Chirayil Chandrasekharan and Greet Vanden Berghe

European Journal of Operational Research, 2020, vol. 284, issue 3, 1058-1073

Abstract: Prisoners often require transportation to and from services such as hospital appointments, court proceedings and family visits during their imprisonment. Organising daily prisoners transportation consumes a huge amount of resources. A large fleet of highly protected vehicles, their drivers and security guards must be assigned to all prisoner transports such that all safety and time-related constraints are satisfied while inter-prisoner (inter-passenger) conflicts are avoided. It is beyond human planners’ capabilities to minimize costs while attempting to feasibly schedule all prisoner transportation requests. Whereas the prisoner transportation problem (PTP) bears resemblance with vehicle routing, common software systems for vehicle routing fail to address the intricacies associated with the PTP. A dedicated decision support system is required to both support human planners as well as reduce operational costs. The considerable computational challenge due to problem-specific components (inter-passenger conflicts and simultaneous servicing) also makes the PTP interesting from an academic point of view. We formally introduce the problem by providing mixed integer programming models. We implement exact iterative procedures to solve these formulations and evaluate their performance on small instances. In order to solve instances of a realistic size, we present a heuristic. Academic PTP instances generated and employed for experimentation are made publicly available with a view towards encouraging further follow-up research. The heuristic presented in this paper provides all the necessary components to solve the PTP adequately and sets initial benchmarks for the new public instance set.

Keywords: Vehicle routing; Prisoner transportation problem; Simultaneous servicing; Inter-passenger conflicts; Multi-compartment (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720300485
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:284:y:2020:i:3:p:1058-1073

DOI: 10.1016/j.ejor.2020.01.027

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().