Allocation method for transit lines considering the user equilibrium for operators

https://doi.org/10.1016/j.trc.2018.09.019Get rights and content

Highlights

  • Address the allocation of transit lines problem in operation-sharing.

  • User Equilibrium for operator based on mathematical programming and game theory.

  • Propose an algorithm employing both column generation and branch-and-bound.

Abstract

The purpose of this study is to address the allocation of transit lines problem in operation-sharing. An allocation method for urban transit lines is proposed to guide public authorities to pursue an optimal plan considering the User Equilibrium for operators (UE-O). The method utilizes the concepts from mathematical programming and game theory to present the UE-O and proposes a set partitioning formulation considering the benefits of both passengers and operators. A branch-and-price algorithm employing both column generation and branch-and-bound is used to tackle the problem. The proposed method is validated through a case study using data from the Development District of Dalian. Results show that the proposed line allocation method considering the UE-O can reduce the potential competitions among operators. This method and findings can provide a guidance to the problems in operation-sharing regarding allocation of transit lines.

Introduction

In recent years, reform in the transit sector takes place in many countries, including changing the operation of transit from monopoly to sharing. Government monopoly of transit lines is no longer a favorable strategy due to poor service level and low efficiency caused by monopoly. Compared with monopoly, operation-sharing of transit lines could introduce competition to maintain the service level and efficiency. Demsetz (1968) mentioned that competition of the market is a way to enhance efficiency. Opening the market to competition has been necessary to create competitiveness in the transit sector. If transit lines are operated by multiple operators, competitive pressure will be induced among operators. Thus, operators will improve service levels and reduce operating costs to increase their competitiveness. Many countries allocating transit lines by introducing competition have so far been successful (Preston, 2005, Wu et al., 2012, Zhao and Huang, 2016).

However, there are some problems caused by introducing transit competition in operation-sharing. Each operator’s individual goal is to maximize his own benefit. Hence, operators may adjust operational strategies of their lines to gain more benefits after the authority allocating lines (Zhou et al., 2005). In general, the main operational strategy is to adjust the departure frequency of each transit line. When an operator is allocated a line to run, competition exists with other operators running on lines “attractive” to the same passengers. On the competitive line, operators tend to increase the departure frequency to compete for passengers, such as deploy more vehicles on these competitive lines. And an equilibrium state is obtained when no operator can increase his profit by changing his departure frequency. That is the UE-O presented in the paper. The competition among operators can cause some problems. On one hand, the increase of vehicles can result in heavier traffic in the competitive lines and serious waste of vehicle resources. On the other hand, vehicles of less profitable lines are transferred to the competitive lines due to the fixed number of vehicles available for each operator, which results in poor service level of transit on the less profitable lines. Therefore, though operators may have high profits under competitive market (Filippini et al., 2015, Zha et al., 2016), the service levels of less profitable lines are very low and passenger satisfaction is poor. It is obviously not the global optimal solution desired by public authorities.

Competition among operators results in that the actual departure frequency of each line is not the global optimal solution desired by public authorities. Therefore, when public authorities allocate transit lines considering the UE-O, an allocation mechanism avoiding competition as much as possible should be designed to guarantee the service level. In the proposed model, three types of players are considered: the public authority, operators, and passengers. As shown in Fig. 1, the interactions among the three players are depicted as a hierarchical system. In the hierarchical system, the public authority aims to optimize the allocation of transit lines so as to minimize the total transit time of passengers. Operators are assumed to compete with each other by changing line frequency, while passengers have corresponding responses and adaptations on the changing line frequency considering operators’ services. In turn, passenger responses ultimately determine the decision of the public authority and operators. In the proposed model, the optimal frequencies of lines maximizing each operator’s profit on each line allocation scheme is obtained considering the UE-O. The competition on the competitive lines is portrayed as a non-cooperative game by changing the departure frequency of each competitive transit line separately so as to maximize the profit of each operator.

In this paper, the problem is formulated as a set partitioning formulation. Then, a branch-and-price algorithm employing both column generation and branch-and-bound is used to find an optimal solution. Finally, the optimal line allocate plan of Development District of Dalian is obtained by using the proposed model and algorithm.

The paper is organized as follows: Section 2 discusses the main findings of the literature on the operation of transit lines, operation plans optimization, and transit competition models applying game theory. Section 3 provides a formal description of the problem. In Section 4, we specify the model. Section 5 presents the solution approach. An instance is studied in Section 6 and we draw some conclusions in Section 7.

Section snippets

Literature reviews

In this section, we review research in the operation of transit lines, operation plans optimization, and transit competition models applying game theory.

In the literature of transit lines operation, a lot of works are devoted to studying operation policies, e.g., some scholars assessed the benefits and drawbacks of transit deregulation policy in private or public transit systems (Mackie et al., 1995, White, 1995, Preston and Almutairi, 2013, Li et al., 2015, Tang et al., 2012, Zhang et al., 2016

Problem description

There exists a non-cooperative game among operators in sharing-operation of transit lines as shown in Fig. 2. The transit line 1 and line 2 are allocated to operator A, while line 3, line 4 and line 5 are allocated to operator B. Competition exists between operator A and operator B because line 1 and line 3 attract passengers from similar locations. On the competitive lines 1 and 3, operator A tends to deploy more vehicles on line 1 to compete for more passengers, and operator B adopts the same

Notation and assumptions

The model proposed in this paper is intended to be computed at the stage of service planning. It is assumed that each line is only operated by one operator and the number of vehicles available for each operator is fixed. In reality, different vehicle types may be adopted by different public agencies. However, how to efficiently distribute different vehicle types to different transit routes becomes another new problem. To simplify the problem, in this paper, the type of vehicles is assumed to be

Solution method

In the integer model [P1], the number of feasible allocations is so large that it is impractical to solve the model by using mathematical programming software directly. Column generation algorithm is a method to solve such problems having plenty of variables (Barnhart et al., 1998, Gamache et al., 1999, Desrochers et al., 1992). And when solving large-scale integer programming problem, it was proved that column generation was a successful method as a complement of integer programming approach,

Case study

An instance based on the Development District of Dalian are conducted in this section to validate the line allocation model proposed in this paper. The instance is solved by CPLEX 12.5 and in each iteration the subproblem is calculated in Visual studio 2010.

Conclusions

This study focuses on the allocation of transit lines problem in operation-sharing by considering the competition mechanism among operators. While huge literature focuses on the operation of transit lines, few studies incorporated the allocation of transit lines in operation-sharing. Different from the government monopoly, allocating transit lines in operation-sharing reasonably is important for avoiding vicious competition between operators and improving the transit service. This paper

Acknowledgments

This research was supported by the National Natural Science Foundation of China 71571026 and 51578112, Liaoning Excellent Talents in University LR2015008 and the Fundamental Research Funds for the Central Universities (YWF-16-BJ-J-40 and DUT16YQ104)

References (63)

  • F. Liao et al.

    Incorporating space–time constraints and activity-travel time profiles in a multi-state supernetwork approach to individual activity-travel scheduling

    Transport. Res. Part B: Methodol.

    (2013)
  • W. Liu et al.

    Expirable parking reservations for managing morning commute with parking space constraints

    Transport. Res. Part C: Emerging Technol.

    (2014)
  • H. Martínez et al.

    Frequency optimization in public transportation systems: Formulation and metaheuristic approach

    Eur. J. Oper. Res.

    (2014)
  • J. Preston et al.

    Evaluating the long term impacts of transport policy: an initial assessment of bus deregulation

    Res. Transport. Econ.

    (2013)
  • E. Rönnberg et al.

    All-integer column generation for set partitioning: basic principles and extensions

    Eur. J. Oper. Res.

    (2014)
  • H. Spiess et al.

    Optimal strategies: A new assignment model for transit networks

    Transp. Res. Part B

    (1989)
  • G. Wall et al.

    Improving bus service quality and information in winchester

    Transp. Policy

    (2007)
  • L. Wang et al.

    An effective hybrid eda-based algorithm for solving multidimensional knapsack problem

    Expert Syst. Appl.

    (2012)
  • J.Y.T. Wang et al.

    A game-theoretic analysis of competition in a deregulated bus market

    Transport. Res. Part E: Logist. Transport. Rev.

    (2005)
  • H.C.W.L. Williams et al.

    Transit services under market arrangements I: a model of competition between independent operators

    Transport. Res. Part B: Methodol.

    (1993)
  • D. Wu et al.

    Design of more equitable congestion pricing and tradable credit schemes for multimodal transportation networks

    Transport. Res. Part B: Methodol.

    (2012)
  • B. Yao et al.

    Transit network design based on travel time reliability

    Transport. Res. Part C: Emerging Technol.

    (2014)
  • H. Yang et al.

    The impact of speed limits on traffic equilibrium and system performance in networks

    Transport. Res. Part B: Methodol.

    (2012)
  • M. Yildirimoglu et al.

    Equilibrium analysis and route guidance in large-scale networks with MFD dynamics

    Transp. Res. Part C

    (2015)
  • B. Yu et al.

    Transit route network design-maximizing direct and transfer demand density

    Transp. Res. Part C

    (2012)
  • B. Yu et al.

    A bi-level programming for bus lane network design

    Transp. Res. Part C

    (2015)
  • W. Zeng et al.

    Specification and calibration of a microscopic model for pedestrian dynamic simulation at signalized intersections: a hybrid approach

    Transport. Res. Part C Emerging Technol.

    (2017)
  • L. Zha et al.

    Economic analysis of ride-sourcing markets

    Transport. Res. Part C: Emerging Technol.

    (2016)
  • J. Zhang et al.

    Modeling route choice inertia in network equilibrium with heterogeneous prevailing choice sets

    Transport. Res. Part C: Emerging Technol.

    (2015)
  • Z. Zhang et al.

    Probe data-driven travel time forecasting for urban expressways by matching similar spatiotemporal traffic patterns

    Transport. Res. Part C Emerging Technol.

    (2017)
  • C.L. Zhao et al.

    Experiment of boundedly rational route choice behavior and the model under satisficing rule

    Transport. Res. Part C: Emerging Technol.

    (2016)
  • Cited by (27)

    • Efficient and stable data-sharing in a public transit oligopoly as a coopetitive game

      2022, Transportation Research Part B: Methodological
      Citation Excerpt :

      Equilibria were derived for collusion and competition in price and quantity. Yao et al. (2019) focused on the problem of an upper-level transit authority assigning transit lines to lower-level operators making line frequency strategies. Rasulkhani and Chow (2019), Pantelidis et al. (2020b), and Ma et al. (2021) proposed different models under a stable matching framework to reveal the joint behavior of operator decisions (pricing and routes to serve) and user path choices.

    • Traffic congestion mechanism in mega-airport surface

      2021, Physica A: Statistical Mechanics and its Applications
      Citation Excerpt :

      Research on airport surface traffic flow is relatively elementary and profound yet, and there is a lack of theoretical research on airport surface traffic congestion. Therefore, according to previous research, this paper draws on the lessons of the traffic flow modeling process from scholars in ground transportation [40–45]. An airport traffic flow model based on CTM was established, aiming to analyze characteristics of airport surface traffic flow.

    • Real-time customized bus routes design with optimal passenger and vehicle matching based on column generation algorithm

      2021, Physica A: Statistical Mechanics and its Applications
      Citation Excerpt :

      Besides, compared with the demand-responsive taxi and conventional taxi, the customized bus has more advantages in price. Therefore, the customized bus service has a promising prospect to offer efficient and convenient service for passenger, especially under extremely tight road during peak hours [5–7]. In this paper, we propose a concept of real-time customized bus service which is a bus service by reserving online and then feedback in an acceptable time.

    • A data-driven hybrid control framework to improve transit performance

      2019, Transportation Research Part C: Emerging Technologies
      Citation Excerpt :

      Public transport services are difficult to regularize in daily operations because operational vehicles are impacted by diverse disruptions (Newell and Potts, 1964; Chen et al., 2013, Liao and van Wee, 2017; Varga et al., 2018). The disruptions mainly include two aspects: the variability in travel time and the variations of passenger demand (Yao et al., 2019). These disruptions tend to induce ‘bus bunching’ or large intervals in service, resulting in an increase in passenger travel time.

    • Travel time prediction based on route links’ similarity

      2023, Neural Computing and Applications
    View all citing articles on Scopus

    This article belongs to the Virtual Special Issue on “Mobility Strats & Effect”.

    View full text