Optimization and public transport tendering: a case study in Southern Italy

Document Type

Journal Article

Publication Date


Subject Area

place - europe, place - urban, mode - bus, organisation - contracting, planning - service level


Bus service, Transport cost, Graph partitioning, Districting, Mathematical programming, Adaptive large neighbourhood search


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.


Permission to publish the abstract has been given by SpringerLink, copyright remains with them.