A New Solution Method for Solving Transit Assignment Problems

A New Solution Method for Solving Transit

Assignment Problems

Le Luong Vuong1

, Tran Duc Quynh2

, and Nguyen Quang Thuan3(&)

1 Industrial University of Ho Chi Minh City, Ho Chi Minh City, Vietnam 2 Vietnam National University of Agriculture, Hanoi, Vietnam 3 International School (VNU-IS), Vietnam National University-Hanoi (VNU),

Hanoi, Vietnam

[email protected]

Abstract. Congested transit assignment problems are crucial sub problems in

planning public transportation systems. These problems are usually formulated

in the form of non-convex optimization programs. In this work, we investigate

the model given by De Cea et al. [3] that has been widely used by both prac￾titioners and researchers. For solving this model, to the best of our knowledge,

one must use a diagonalization technique in order to yield a symmetric

assignment problem before applying a solution method. Consequently, the

quality of the obtained solution would be possibly affected. The motivation of

our work is to find a new efficient solution method to tackle directly the original

assignment problem without diagonalization techniques. Basing on DC pro￾graming, we introduce a new solution method. The proposed algorithm is tested

on the data given in [3]. Comparing with the existing method, the experimental

results show that our approach is promising.

Keywords: Transit assignment problems
DC algorithm

Non-convex optimization
Public transportation

1 Introduction

Public transportation is a key factor of urban transportation that occupies an important

place in economic and social development of a country. Some problems can be listed

such as transit route network design, bus scheduling, bus rapid transit systems, etc.

These problems have attracted attention from both practitioners and researchers. In

general, these problems are formulated into optimization problems and then are solved

by certain solution methods. The mathematical formulations are usually in the form of a

bi-level optimization problem in which the lower level is a transit assignment problem

[4–6]. Finding efficient algorithms for the lower problem plays an important role in the

schema of solving the original problems. In case that congestion is not taken into

account, assignment problems are possibly modeled as linear programs for which

efficient solution algorithms have been implemented [2, 8]. However, linear models are

limited since congestion is often encountered in cities. Some attempts have been made

in the past to build transit assignment models that consider congestion [1, 3].

© Springer Nature Switzerland AG 2019

H. Fujita et al. (Eds.): ICERA 2018, LNNS 63, pp. 70–76, 2019.

https://doi.org/10.1007/978-3-030-04792-4_11