Application of a Hill-Climbing Algorithm to Public Transportation Routes Design in Grid Networks

Transit Routes Design (TRD) problem deals with optimizing the configuration of transit routes to satisfy a given objective, such as maximizing network coverage, while holding the budget constraint. In its discrete form, TRD is recognized as a computationally interactive problem. A review of the literature reveals that, despite extensive research on this problem, the number of studies on specific urban network configurations has remained limited. Among these studies, many have applied simplifying assumptions such as continuous design variables which may not be applicable to real-world settings. The present study focuses on a discrete version of the TRD problem for an urban “grid” network and aims to maximize the service coverage through the network. To this end, a local search Hill-Climbing (HC) heuristic algorithm is proposed and evaluated. The proposed HC algorithm performs several replications in which it starts with a combination of randomly selected routes and iteratively improves them by moving to the “best neighbour” until it reaches a local optimum solution. Our results for a ۶×۱۰ grid network for three budget levels (i.e. low, medium, and high budget levels) indicate that, in much shorter run-times than the exact algorithm, the proposed HC algorithm can produce high-quality solutions with ۰.۱۲%, ۴.۱۶%, and ۲.۲۲% difference from global optimums.

Keywords:

Transit Routes Design , Grid Network , Coverage , Hill Climbing