Keywords

1 Introduction

In this paper, a real case of SPP which belongs to Gaziantep city (Turkey) is considered. The starting point is considered as the main gate of Gaziantep University. The finishing point is determined as the bus terminal of Gaziantep. The main reason considered this route is that it is one of the most frequently used lines in the city. There are almost 50 thousands students in Gaziantep University and most of them are using bus terminal while they are living near the university campus. Although there are currently 11 different bus routes between Gaziantep University and Gaziantep bus terminal, most of the students dissatisfy with the long and circulating routes. To overcome aforementioned dissatisfaction, a new route which is shorter and has fewer stops is investigated in this paper. Therefore, the problem is considered as a SPP.

The SPP is a typical combinatorial problem that contains key elements of network flow problems; it has been extensively studied, and a large number of algorithms exist to solve it [1]. The SPP is to search a path with a minimal overall length from a starting node to an end node. The arc lengths can alternatively be thought of as travel times or expenditures for traveling the respective arcs [2].

In literature, there are mainly four types of SPPs. They are single pair, single source, single destination and all pairs SPPs [3]. The SPP variants with their explanations are given in Table 1.

Table 1. SPP variants
Full size table

Our problem belongs to single pair SPP type. Despite the fact that shortest path methods have been used in numerous areas, most of them focuses complexity of the problems [7]. Application of single pair shortest path algorithms to the transportation problems is not a new issue [8]. For instance, Wu and Hartley [9] used shortest paths algorithms for calculating a sufficient number of ranked shortest routes for the public transportation network of Nottingham City. Then, Huang et al. [10] created an algorithm that calculates the shortest cost path between a moving object and its destination by constantly adapting to changing traffic conditions while using prior search results.

For multimodal transportation networks, Idri et al. [11] devised a new time-dependent shortest path algorithm. The proposed method was a single-source single-destination goal-oriented algorithm. As a case study of Pokhara city, Thapa and Shrestha [12] focused on finding the shortest path possible in terms of minimum time and cost to reach a specific place for a person. Finally, Tu et al. [13] investigated the constrained reliable shortest path (CRSP) problem for electric vehicles in the urban transportation network. For recent applications of SPP on public transportation, the reader is referred to Susilowati and Fitriani [14]; Win et al. [15] and Liu and Liu [16].

The remainder of the paper is organized as follows after the introduction section: Sect. 2 presents the applied binary integer programming formulation. In Sect. 3, the case is introduced and the results of computational experiments are given. Main conclusions are offered in Sect. 4.

2 The Mathematical Model

As mentioned in the previous section, single pair SPP is considered in this study. For the solution approach, a binary integer programming formulation [17] is used. Given a directed graph \(G=\left(V,A\right)\) and arc costs (distance) \({d}_{ij}\) for each (\(i,j)\in A\), he SPP entails determining the shortest path between two nodes, s and t. The following is a standard binary integer programming formulation for determining the shortest path from node s to node t [17]:

$$ minimize\sum\nolimits_{i,j \in A} {d_{ij} x_{ij} } $$
(1)

Subject To

$$ \sum\nolimits_{i,j \in A} {x_{ij} } - \sum\nolimits_{i,j \in A} {x_{ij} } = \left\{ {\begin{array}{*{20}c} {\begin{array}{*{20}c} 1 & {if\, i = s} \\ \end{array} } \\ {\begin{array}{*{20}c} { - 1} & {if\, i = t} \\ \end{array} } \\ {\begin{array}{*{20}c} 0 & { else} \\ \end{array} } \\ \end{array} } \right.\;\;\;\;\;\;\;\;\;\;\;\;\forall i \in V $$
(2)
$$ \sum\nolimits_{i,j \in A} {x_{ij} } \le 1\;\;\;\;\;\;\;\;\forall i \in V $$
(3)
$$ x_{ij} \in \left\{ {0, 1} \right\}\;\;\;\;\;\;\;\;\;\;\forall i,j \in A $$
(4)

where \({x}_{ij}\) is binary link variables that get value 1 if the arc \((i,j)\) belongs to the path. Objective function (1) finds the shortest path between two nodes s and t. Equation (2) are flow conservation constraints, while Eq. (3) assures that each node's outgoing degree is limited to one. Finally, Eq. (4) is the binary restriction constraint.

3 The Case Study

In this paper, we tried to find the shortest public transportation from Gaziantep University to Gaziantep bus terminal based on the road distance. For this, we used the Gaziantepkart application, which was put into practice by Gaziantep Municipality and can be downloaded for free from providers such as Google Play. We have identified the names of all municipal buses on the route from Gaziantepkart application to Gaziantep University and Gaziantep bus terminal and at which station they stop. Many buses followed the same route. The stops were very close to each other or they used more than one same stop at the same time. Therefore, after determining all the stops and the distance between them, we eliminated some of the stations very close to each other and included only one of the stops in which they stopped again in a loop.

Our aim here was to create the shortest route by using the same stops rather than the routes already used and to shorten the journey time. We thought that if we reduced the number of stops and determined the appropriate intervals between stops, we would gain both distance and time. By analyzing the current 11 bus routes, 46 different and common stops are determined. The locations of stops are shown in Fig. 1.

Fig. 1.
figure 1

Considered 46 stop locations.

Full size image

We marked the stops obtained from Gaziantepkart application on the map between the Gaziantep University and Gaziantep bus terminal in the most appropriate way for real measurements using Google Earth. Then, using the distance measurement application in Google Earth, we determined the approximate distance between stops. The network consists of 46 stops are shown in Fig. 2. While the first node shows starting point (Gaziantep University), the last point indicates the ending point (Gaziantep bus terminal).

Fig. 2.
figure 2

Network of bus stops.

Full size image

The model was solved by the GAMS 23.1 optimization package program (less than 5 CPU seconds) and the shortest distance between the two points (10.4 km) was found to be optimal. As a result, a new bus route including 18 destination stops with shorter distances than the existing 11 bus routes has been proposed. The new route is shown as pink in Fig. 3. It must be noted the proposed new route (10.4 km) is 17% less than the current route.

Fig. 3.
figure 3

Proposed route in the network.

Full size image

4 Conclusion

Single pair SPP for the public transportation case is studied in this paper. Considering the current bus routes between starting and ending points, a network with 46 stops is created. A binary integer programming formulation is applied to find the shortest route between Gaziantep University (starting point) and Gaziantep bus terminal (ending point). As a result, obtained optimal route consists of 18 bus stops and provides 10.4 km distance which is less distance (17% less) than the existing routes. For the future, a geographic information system-based solution approach should be developed. In addition, traveling time instead of traveling distance should be used as a performance indicator.