A local search algorithm for finding optimal transit routes configuration with elastic demand

• Author: Amirali Zarrinmehr,Seyedehsan Seyedabrishami,Mahmoud Saffarzadeh
• DOI: http://doi.org/10.1111/itor.12359
• Published date: 01 September 2018
• Date: 01 September 2018

Intl. Trans. in Op. Res. 25 (2018) 1491–1514

DOI: 10.1111/itor.12359

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A local search algorithm for finding optimal transit routes

configuration with elastic demand

Amirali Zarrinmehr, Mahmoud Saffarzadeh and Seyedehsan Seyedabrishami

Department of Civil and Environmental Engineering, Tarbiat Modares University,Tehran, Iran

E-mail: amirali.zarrinmehr@modares.ac.ir,azarinmehr@gmail.com [Zarrinmehr];

saffar_m@modares.ac.ir[Saffarzadeh]; seyedabrishami@modares.ac.ir [Seyedabrishami]

Received 17 January 2016; received in revised form 5 September 2016; accepted 16 September 2016

Abstract

This paper proposes a newlocal search algorithm for finding the optimal configuration of subroutes from a set

of candidate transit routes in a transportation network. It is intended to maximize the transit ridership while

holding the budget constraint. In each iteration of the algorithm, route segments that are likely to absorb

more transit passengers are added to the configuration and less-contributing segments are removed, instead.

A path-based model with elastic demand is applied for traffic assignment problem. The algorithm takes

advantage of the equilibrium paths information to speed up the calculations for emerging configurations. A

numerical experiment on Sioux-Fallsnetwork indicates that the proposed algorithm can achieve high-quality

solutions at different levels of budget.Also, the run-time and performance of the algorithm are reported over

a large problem instance of the Chicago sketch network with 55 artificial candidate routes.

Keywords:transit route; optimal configuration; elastic demand; local search algorithm; traffic assignment

1. Introduction

The experience of urban development in recent decades proved that increasing the share of private

transportation in daily commuting brings about serious problems such as traffic congestion and air

pollution. As a result, urban public transportation or transit has been widely recognized as a viable

option in moving towardsustainable development (Sinha, 2003; Kepaptsoglou and Karlaftis, 2009).

Numerous studies have been directed in the field of operations research to investigate the problem

of determining the optimal set of routes and schedules for bus/rail systems. This problem, known

as the transit network design problem, has been approached from various aspects in the literature

(Guihaire and Hao, 2008).

From a general perspective, a hierarchy of decision-making problems is involved in the overall

transit planning process, from long-term strategic planning decisions to short-term operational

decisions (Farahani et al., 2013). The problem of transit routes design (TRD), which is the focus of

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1492 A. Zarrinmehr et al. / Intl. Trans. in Op. Res. 25 (2018) 1491–1514

this paper,falls into the category of strategic planning problems. It is consideredthe most important

decision-making problem in the process of transit planning since all of the subsequent decisions are

conditioned to it (Ceder and Wilson, 1986; Mauttone and Urquhart, 2009).

The TRD problem is confronted with many modeling/solution complexities. As noted by Baaj

and Mahmassani (1991): (a) it is complicated to incorporate the definition and nodal composition

of the routes in the problem formulation, (b) nonconvexities and nonlinearities arise at the stage

of formulating the problem, (c) as the network size enlarges, there is a combinatorial explosion in

the number of route decision variables, (d) multiple conflicting objectives may need to be traded off

against each other, and finally (e) it is difficult to formally characterize a good configuration.Due to

the mathematical complexities such as nonconvexities, nonlinearities, and combinatorial explosion,

application of exact solution approaches in large TRD problems cannot be expected. As a result,

the main body of the research has focused on heuristic/metaheuristic solution approaches to tackle

the problem (Sch¨

obel, 2012; Farahani et al., 2013).

To overcome the intractable size of transit routes in TRD, most studies typically break the

problem into two phases, namely, the route generation and the route configuration (Kepaptsoglou

and Karlaftis, 2009; Sch¨

obel, 2012). The route generation phase involves generating a pool of

candidate routes according to some standards, expert judgements, etc. Generated routes are then

used as the inputs to the route configuration phase where the optimal subset of routes is selected

(Kepaptsoglou and Karlaftis, 2009). The final configuration of transit routes must work the best

from the users’ perspective while also accounting for the operational constraints, for example,

budget, route lengths, etc. Defining the “best” configuration, however, depends on the objective

function considered in the problem. Since moving toward a sustainable transportation is a primary

concern in urban planning, maximization of the transit ridership might be stated as an ultimate

objective function for the TRD problem. Though, to our knowledge, this objective function has

been rarely used explicitly in related literature of TRD. Researchers have always addressed the

transit ridership through alternative objective functions. Farahani et al. (2013) have listed many of

these objective functions such as maximizing the routes coverage, minimizing the number of empty

seats, minimizing users’ average travel time, or minimizing the operational costs. Maximizing the

routes coverage, for example, has been applied as an objective function in many related studies

(Farahani et al., 2013).

Routescoverage, as defined by manyresearchers, refers to the percentage of the travel demand that

can be “potentially” served by the network of transit routes (Zhao and Zeng, 2006; Kepaptsoglou

and Karlaftis, 2009). Although widely applied, the routes coverage cannot provide much insight

about the competition between public and private modes in real-world instances. Figure 1 shows an

illustrative example for how the results of coverage may differ from the outcome of the competition

between the two modes.

In Fig. 1, a simple network is available as an example with two public and private transportation

modes. It is assumed that the travel demands from1 to 3 and from 2 to 3 are 800 and 200 passengers

per hour, respectively. Also, for simplicity, link travel times are considered to be fixed and are

depicted (in minutes) next to the links in the figure. We refer all remaining details of the problem,

for brevity, to Section 2 where the assumptions will be listed.

As Fig. 1 shows, the transit coverage is 80.0% in Scenario 1, as the transit route goes directly

from 1 to 3. However, in the same scenario, the share of the transit demand in competition with

the private mode is only 16.5%, which is notably less than 80.0%. Besides, to improve the route

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation of OperationalResearch Societies