Abstract
This article presents a multi-start heuristic approach to a design problem motivated by a real-world application in the Italian transport system. Specifically, it focuses on the problem of designing optimal lots in the public transport organization. In defining lots (in terms of number, size, and boundaries) both cost and service level have to be considered. Under certain assumptions, we model the problem as a graph partitioning problem and consider the same performance measure indicated by the relevant decree-law enacted by the Italian Ministry of Transport. The multi-start algorithm proposed for individuating high-quality solutions for the problem uses adaptive large neighbourhood search. The results of a computational study based on real data from a region in Southern Italy are reported.