Linear Programming Optimization Techniques for Addis Ababa Public Bus Transport

Abstract

Anbessa City Bus Service Enterprise (ACBSE) is the only public enterprise that provides transport services in the city of Addis Ababa. The enterprise uses a fixed bus schedule system to serve passengers in more than 125 routes. However, the current bus assignment and scheduling system are becoming a challenge in the company’s operational performances. The objective of this paper is to develop an optimum bus assignment method using linear programming (LP). After a thorough analysis of the existing bus scheduling system, the LP model is developed and used to determine the optimal number of busses for each route in four shifts. The output of the LP-model is then validated with the performances of the existing systems. The findings of the study showed that the new model reveals better performances on the operating costs, bus utilization, and trips and distance covered compared with the existing scheduling system. The bus utilization is improved by the new system and cut costs on the one hand and improves the service quality to passengers on the other hand. The authors recommended the enterprise to adopt the new bus assignment system so that busses can be assigned based on the demand distribution of passengers for each route at a given shift.

1. Introduction

The bus schedule is one of the operations planning process in bus transport that deals with the proper assignment of busses to routes to serve the expected passenger demand. The planning process in public transportation consists of different recurrent and complex tasks. It starts at a strategic level by collecting or forecasting the number of passengers at each transfer point, which is most of the time fully unknown and adds to the complexity of the planning process [1, 2, 3].

The decision-making process of the bus assignment is, however, a trade-off between service quality and operating costs for the bus operating companies [4]. It is because using too many busses incurs more operating costs while resulting in good service quality, whereas too few busses have the opposite effect. Based on the information collected from Anbessa City Bus Service Enterprise (ACBSE) currently, the enterprise serves more than 125 routes (as of 2019) that connect different parts of the city using 759 operational busses. The number of passengers shows high variability during each period which requires fluctuating the number of assigned busses in each route. But the enterprise uses mainly a fixed number of busses scheduled per route in its operation throughout the day. This resulted in some busses moving empty while others are being overcrowded, which subsequently results in poor performance and service quality. Moreover, the transportation service in ACBSE has many challenges such as low bus utilization, unsatisfied passengers’ demand, and higher operating costs.

To address the challenges of bus assignment and scheduling problems in ACBSE, this paper first focuses to develop a demand-oriented Linear Programming (LP). Linear Programming is a well-accepted technique within the field of Operations Research, a specialty area within the broader field of Industrial Engineering. Then the LP-model is used to solve and optimally satisfy the existing passengers’ demand in four operating periods in a day using 93 selected routes. For simplicity purpose, in this paper, the four operating periods are named as shifts.

2. Bus scheduling techniques

The concept of planning a minimum cost set of transporting routes to serve a group of customers is a fundamental constraint in the field of transport and logistics [5, 6, 7]. It is because, in the total cost of the product, transportation accounts for about 20% of the total costs of a product [8]. Therefore, the need for developing a better route plan that can reduce the cost of transportation is the concern of various industries in the field.

To address the above issues, the basic and well-studied routing model is the Traveling Salesman Problem (TSP), in which a salesman is to visit a set of cities and return to the city he started in [2, 9, 10]. The objective of the TSP is to minimize the total distance traveled by the salesman. Vehicle Routing Problem (VRP) is a generalization of the TSP in that the VRP consists of determining m vehicle, where a route is a tour that begins at the depot, visits a subset of the customers in a given order, and returns to the depot [9, 10, 11].

The activity of planning and designing a delivery or a pickup service to customers in the logistics and supply chain is known as a Vehicle Routing Problem [6]. The first time it was proposed by [12] under the title “Truck dispatching problem” to design the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal. Often the context is that of delivering goods located at a central depot to customers who have placed orders for such goods, but the area of application of VRP is also so versatile and is used in many areas in real-world life.

“The VRP is defined by a depot, as a set of geographically scattered customers with known demands, and a set of vehicles with fixed capacity” [7, 13]. All depts must be visited just once and the total demand of a route must not exceed the total vehicle capacity. The VRP aims to minimize the overall distribution costs. In most real-life distribution contexts many side constraints complicate the VRP model. These side constraints can be time, that is the total route time and windows time within which the service must begin.

In the literature, VRP was also known as the “vehicle scheduling” (VSP) [6], or “Vehicle dispatching” or simply as the “delivery problem” [14]. It appears very frequently in real-world situations not directly related to the physical delivery of goods.

The VRP problem is a combination of the two well-known optimization problems: the Bin Packing Problem (BPP) and the Traveling Salesman Problem (TSP) [15, 16, 17]. The BPP is a problem given a finite set of numbers (the item sizes) and a constant $K$, specifying the capacity of the bin, what is the minimum number of bins needed? [16].

Logically, all the items have to be inside exactly in one bin and the total capacity of items in each bin has to be within the capacity limits of the bin. This is known as the best packing version of BPP. The TSP [3] is about a traveling salesman who needs to visit several cities. The salesman has to visit each city exactly once, start and end location, commonly called depot in VRP. The issue is to search the shortest tour within all the cities [17]. Connecting this to the VRP, customers can be allotted to vehicles by solving BPP and the order in which they are visited can be found by solving TSP. A VRP with a single vehicle and infinite capacity is a TSP.

VRP is a common name given to a problem in which a set of routes for a fleet of vehicles based at one or several locations called a depot, must be determined for several dispersed cities or customers [18]. The motive is to service a set of customers with a minimum-cost [16, 19]. Vehicle routes originate and terminate at a depot. It is one of the most challenging combinatorial optimization problems in distribution, and logistics [7]. Customers may be in a dispersed location and a fleet of vehicles need to serve them from a depot and return to the depot [16]. The decision here is to determine the assignment of the vehicle (s) and route (s) that a vehicle will serve them best. The commonly used illustration of the input and output of VRP is given in Figures 1 and 2.

Figure 1.

VRP inputs.

Figure 2.

VRP outputs.

Figure 3.

Average daily bus utilization; current vs improved system.

Since both BPP and TSP are the so-called NP-hard problems and since VRP is a combination of the two, it is also NP-hard [12, 16, 20, 21]. Since the last decades, VRP has got much interest from many scholars. Even in recent years, with the rapid advancements of globalization and supply chain systems, VRP is becoming one of the important research topics in the fields [4, 22, 23].

Moreover, the complexity and its application importance immense literature have devoted to the study and analysis of Bus Scheduling Problem (BSP) and many optimization models have been proposed [23]. The different models developed have tried to accomplish near-optimal solutions with an acceptable amount of computational effort and time [6]. There are many extensions for the Vehicle Schedule Problem (VSP) or VRP with several requirements in the literature over the last 50 years [16, 24]. Among many others, some of the examples are the existence of one depot [18] or more than one depots [4, 16], a heterogeneous fleet with multiple vehicle types [18] the permission of variable departure times of trips, VRP with deterministic demand which is commonly called classical VRP [13, 18].

3. Modeling and vehicle routing problem

Vehicle Routing Problem has been used in different applications and practices but with many constraints. The major constraints according to [16] are the network [25], demand and customers, depot locations, the type of vehicle used, and sometimes drivers. it is not possible to satisfy all the constraints in one model. In this case, some of the constraints can be reduced without loss of generality. When some customers left unserved due to this reason, in VRP, it called route failure [7]. In some cases, by introducing different penalties or priorities, the situations can be handled [6, 16].

The routing operations are performed to serve customers to start and end at one or more locations, located at the road [5]. Each location or depot is identified by the number and types of vehicles associated with it and by the number of goods it can deal with [23]. Transportation of goods is carried out by using a fleet of vehicles with fixed composition and size according to the necessities of the customers [25, 26].

The vehicle used in VRP is also one constraint in the model assumptions. According to [16], the vehicles may be characterized by the capacity of the vehicle, expressed as the maximum weight, or volume, or the number of pallets, the vehicle can carry. In most application areas, the least practice constraint is the drivers [16].

VRP is one of the most studied combinatorial optimization problems and is concerned with the optimal design of routes to be used by a fleet of vehicles to serve a set of customers [26]. VRP is not only focusing on the delivery and collection of goods but involves also in different application areas arising from the transportation and logistics system [16].

Different VRP models have been developed for different applications to study the Routing Problem [1, 22]. The most recent is the one that has been devoted to more complex variants of the VRP occasionally called “rich” VRPs. These are closer to the VRP models [23] and are used to design an optimum allocation system that can improve the level of their services [27]. Toth Paolo and Vigo Daniele [16] have reported that the use of computerized methods in the VRP problems has significantly saved the computational effort ranging from 5 to 20%.

VRP can be designed as a directed or undirected graph subject to the problem environment [21, 28]. In the case of classical VRP where customers or customer’s demands are known in advance and the driving time between the customer and the service time at each customer are also known, it can be defined and formulated in this section as a general VRP model [28].

It is designated in graph theory. To define the general model of VRP, let $G=\left(v,A\right)$ be an asymmetric graph where $V=\left\{0,1,\dots ,n\right)$ is a set of vertices representing cities or depot situated at the vertex 0, and $A$ is the set of arcs. In every arc $\left(i,j\right);i=j$ is related to a nonnegative distance matrix $C=(C_{\mathit{ij}}$). In some cases, $C_{\mathit{ij}}$ can be understood as a travel cost or as a travel time [21, 29, 30], it is often appropriate to substitute $A$ by $E$. Where $E$ is a set of undirected edges in the graph to represent asymmetric or undirected graph.

The common VRP comprises a set of at most $K$ delivery or collection routes plan such that each route starts and ends at the depot, each customer is visited exactly once by exactly one vehicle, the total demand of each route does not exceed the vehicle capacity and the total routing cost is minimized. With all these assumptions, according to Stewart and Golden [31], a compact representation of VRP can be presented as follow:

$$Minimize=\sum _{k=1}^n{c}_{\mathit{ij}}{x}_{\mathit{ij}}^k$$E1

Subject to

$$\sum _{i,j}^n{q}_i{x}_{\mathit{ij}}^k\le Q,k=1,2,..n$$E2

Where:

$c_{\mathit{ij}}$ = The cost/distance of traveling, from $i$ to $j.$

$x_{\mathit{ij}}^k$ = 1 if vehicle k travels from $i$ to $j$; 0 otherwise

$m$ = The number of vehicles available

$S_m$ = The set of all feasible solutions in the m-traveling salesman problem (m-TSP)

$q_i$ = The amount demanded at location $i$

$Q$ = The vehicle capacity.

In many realistic cases, the cost or the distance matrix satisfies the triangular inequality such that Eq. (3):

$$c_{\mathit{ik}}+c_{\mathit{kj}}\ge c_{\mathit{ij}};{\forall }_{i,j,k}\in V.$$E3

In the VRP models, a differentiation has to be made between symmetric Eq. (4) and asymmetric Eq. (5). Solution approaches can vary significantly between these two cases [30].

$$A=\left\{\left(i,j\right)|i\in V,j\in V,i=j\right\}$$E4

$$A=\left\{\left(i,j\right)|i\in V,j\in V,i<j\right\}$$E5

In the real world, however, the general VRP model is enhanced by various constraints or side-constraints, [5]. The constraints can be such as vehicle capacity or time interval in which each customer has to be served [16], revealing the Capacitated Vehicle Routing Problem (CVRP) [20] and the Vehicle Routing Problem with Time Windows (VRPTW) [18, 21].

VRP models, whether they are used for public transport or transit, as well as distribution and logistics, they share certain mutual features. That is, they focus on the optimization of cost (working cost), distance covered, waiting time, etc.

4. Methodology

The current operations schedule of ACBSE has faced many challenges in its schedule busses assignment for each route. The enterprise uses a scheduling system that operates from 6:30 to 20:30. As shown in Table 1 below, The enterprise has a fixed scheduling system, which means, the number of busses allowed on each route remains constant irrespective of the commuters’ demand. In reality, however, the number of busses in each route should have been varied and can be determined based on the commuters’ demand distribution. These approaches have made some busses moving empty while others being congested and resulting in capacity loss to the enterprise and bad service to passengers.

Figure 4.

Average bus utilization for peak and off-peak shifts; current vs improved system.

Route No.	Origin(local Name)	Destination (local Name)	No. of busses	Kms
1	Megenagna	Kara	2.00	7.70
2	Kore Mekanisa	Addis Ketema	4.00	11.10
3	Ayertena	Minilik Square	8.00	10.80
4	Haliti	Addis Ketema	5.00	19.40
93	Bole Bulbula	Megenagna	2.00	15.20
	Total		36.00	132.80

Table 1.

The fixed number of busses assigned on selected routes (as of 2011).

The enterprise occasionally involves additional busses on few routes during peak hours to overcome the challenges. Due to the absence of records for such decisions, therefore, in this study, the fixed number of busses assigned on each route is only considered as a basis for benchmarking.

5. Data collection

The data were collected only on the 93 routes that have been used by the enterprise for more than a decade. The data includes route performances, number of passengers served per route, the total trips made, revenue generated, running cost, and distance traveled. Moreover, data were also collected concerning the number of busses, bus capacity, average bus travel time, the length of each route, and working hours. The data were analyzed and organized per shift per route basis for validation purposes. The operating shifts, the time interval for each shift, and the passengers demand proportion per shift are reported in Table 2.

Shift	Time interval	Duration (minute)	Demand proportion (%)
Morning peak hours	6:15–9:30	195	40%
First off-peak hours	9:30–15:30	360	20%
Evening peak hours	15:30–19:30	240	35%
Second off-peak hours	19:30–21:00	90	5%
Total		870	100

Table 2.

Demand proportion and duration of each shift.

As per the report of the company, the enterprise has 534 busses and transported about 640, 000 passengers per day in 125 routes. In addition to these, the enterprise covers about 138 km and makes 61.50 trips per day [32]. In this study, it is also possible to classify the enterprise schedules in four shifts, i.e. peak hour and off-peak-hour schedules. These are two peaks and two off-peak periods during the services time (from 6:30 to 21:00). The morning peaks are from 6:30–9:30 and 15:30–19:30, while the off-peaks are also in the morning and afternoon shift. The details are reported in Table 2.

The demand proportion has also distributed within the four shifts. In the morning peak hour, the enterprises serve about 40% of the daily passengers. In the second peak-passengers’ demand occurs in the evening shift shares about 35% of total passengers. The other periods are the first and the second off-peak shift which occurs after the morning peak and the evening peak shift in which 20% and 5% for the demand proportion is allocated respectively.

6. Model development

The researchers have investigated the existing operating systems of the ACBSE, and a linear programming (LP) model was developed. The model helps to achieve a solution for the scheduling problems of the enterprise. The LP model developed in this study is a new approach in the literature of VRP that considers the trips made by two different types of busses to address the demand distribution of passengers in 93 routes in four working shifts.

6.1 Running the model

The LP model was fitted with data. To achieve its object, the model was coded and run using the General Algebraic Modeling System (GAMS) optimization software. The GAMS code was running within 0.15 seconds on 3.10 GHz, Window7 Home Premium, 4GB RAM, and core (i5) Dell Personal computer (Optiplex 790-Model). The resulting solution of the LP-model was first the number of trips per route per shift for each type of bus. After obtaining the solution, then, the number of trips was translated into the number of busses per route per shift for each type of bus.

6.2 Model validation

The LP model was investigated and validated to identify potential areas of improvement in the scheduling and assignment problem of ACBSE. It is also used to determine the number of busses to be assigned in a given route at a given shift that can address the demand distribution of passengers each shift for the 93 routes. The results of the LP-model were validated by comparing the current schedule and performances of the enterprise. The validation was made using four performance measuring parameters namely bus utilization, the total number of trips made, the total distance traveled, and the different operating costs.

7. Develop the LP model

In order to develop the LP mode, let $\mathrm{i}$ be the number of trips per route per shift $\mathrm{j}$ made by bus type-I is represented by “$x_{\mathit{ij}}$” and by that of bus type-II is marked by “$y_{\mathit{ij}}$”. The model is developed as a general model, at this section, then later is fitted to the ACBSE problem with data collected from the enterprise.

Definition of terms:

$\mathrm{i}$ = Route number, where $\mathrm{i}=1,2,3,\dots .,\mathrm{n}$

j = Shifts, $\mathrm{j}=1,2,\dots ,\mathrm{m}$

$D_{\mathit{ij}}$ = Passenger demand of route i at shift j

$C_x$ and $C_y$ = Capacity of bus type-I and bust type-II, respectively

$M_j$ = Minimum Number of trips required at a given shift j

$F_x$ and $F_Y$ = Total available busses type-I and bus type-II, respectively

$T_{\mathit{ij}}$= Trip factor, maximum trips a bus can be made on route $i$ per shift $j$

$P_i$ = Trip proportion for route $i$

The objective is to minimize the total number of trips made by bus type-I and bust type-II. This objective is represented by $Minimize:{\sum }_{j=1}^m{\sum }_{i=1}^n\left[x_{\mathit{ij}}+y_{\mathit{ij}}\right]$ but needs to fulfill other various constraints.

The first constraint is to set the overall bus capacity of the Enterprise. This is the capacity of the two types of busses assigned in route $i$ during shift $j$. This capacity should be greater than or equals to the total demand required by passengers that require ta rip in route $i$ at shift $j$. It is Mathematically expressed as $C_x{x}_{\mathit{ij}}+C_y{y}_{\mathit{ij}}\ge D_{\mathit{ij}}$. The second and third constraints are used to check the total number of busses for each type of bus. To this effect, the total trip required by bus type-I and bus type-II should be less than or equal to the total trips available by bus type-I and bus type-II respectively. These are Mathematically expressed as: ${\sum }_{j=1}^{\mathrm{m}}{\sum }_{i=1}^n{x}_{\mathit{ij}}\le F_x{\sum }_{j=1}^{\mathrm{m}}{\sum }_{i=1}^n{T}_{\mathit{ij}}$; and ${\sum }_{j=1}^{\mathrm{m}}{\sum }_{i=1}^n{y}_{\mathit{ij}}\le F_Y{\sum }_{j=1}^{\mathrm{m}}{\sum }_{i=1}^n{T}_{\mathit{ij}}$.

The fourth constraint will determine the total minimum number of trips required in every 30 minutes for each of the 93 routes. This constraint is given b, ${\sum }_{j=1}^{\mathrm{m}}{\sum }_{i=1}^n\left[x_{\mathit{ij}}+y_{\mathit{ij}}\right]\ge 93{\sum }_{j=1}^4{M}_j$ . The trip made by bus type-I and bus type-II for each route i at each shift j should also be less than the total proportion of the trip available. This constrain is mathematically stated as: $x_{\mathit{ij}}\le F_x{P}_i{T}_{\mathit{ij}}$; and $y_{\mathit{ij}}\le F_y{P}_i{T}_{\mathit{ij}}$. The last constraint that shows sum of proportion. It must be summed and become one. This is written as ${\sum }_{i=1}^m{P}_i=1.$

After compiling all the above constraints, the overall LP-model that determines the optimum number of trips i required per route per shift j is formulated as follows.

$$Minimize:\sum _{j=1}^m\sum _{i=1}^n\left[x_{\mathit{ij}}+y_{\mathit{ij}}\right]$$E6

Subject to

$$C_x{x}_{\mathit{ij}}+C_y{y}_{\mathit{ij}}\ge D_{\mathit{ij}}$$E7

$$\sum _{j=1}^{\mathrm{m}}\sum _{i=1}^n{x}_{\mathit{ij}}\le F_x\sum _{j=1}^{\mathrm{m}}\sum _{i=1}^n{T}_{\mathit{ij}}$$E8

$$\sum _{j=1}^{\mathrm{m}}\sum _{i=1}^n{y}_{\mathit{ij}}\le F_y\sum _{j=1}^{\mathrm{m}}\sum _{i=1}^n{T}_{\mathit{ij}}$$E9

$$\sum _{j=1}^{\mathrm{m}}\sum _{i=1}^n\left[x_{\mathit{ij}}+y_{\mathit{ij}}\right]\ge \mathrm{m}\sum _{j=1}^{\mathrm{m}}{M}_j$$E10

$$x_{\mathit{ij}}\le F_x{P}_i{T}_{\mathit{ij}}$$E11

$$y_{\mathit{ij}}\le F_y{P}_i{T}_{\mathit{ij}}$$E12

$$\sum _{i=1}^m{P}_i=1$$E13

$$x_{\mathit{ij}},y_{\mathit{ij}}\ge 0$$E14

The objective function 6 will minimize the total number of busses required to serve the total demand. Constraint 7 represents the combined capacity of busses assigned to each route i at a given shift j. Eq. 8 and 9 represent the total number of busses that need to be assigned for each route. The total required number of busses must be equal or less than the available number of busses the enterprise has; Eq. 10 shows that the total number of busses to be allotted on each route per shift has to fulfill the minimum number of busses required per route per shift. Eq. 11 and 12 are the number of busses to be assigned to a given route. Moreover, Eq. 13 warrants that the total sum of a probability is always one; last Eq. 14 is nonnegativity constraints.

This model guarantees at least one round trip for each route every 30 minutes to maintain a quality service level. It also contributes to the scientific body of knowledge by introducing different bus types in a single LP-model as a new constraint.

In the model, the travel time of bus on a given route was considered as the total sum of passenger boarding and alighting time (dwell time), acceleration and deceleration at bus stops, traffic light, and transfer time between each stop. However, little attention was also given to consider the functionality of the model and its output. In particular, the model was run once for all of the four shifts. The number of busses will be checked to make sure, $M_j$ is met for all time slots. The results obtained may be fractional but rounded up later into upper integer values. All these may affect real mathematical optimality.

7.1 Minimum number of buses

For clarity and understanding, moreover, some of the parameters were defined. Some of the parameters are, $M_j$, $T_{\mathit{ij}}$, and $P_i$. They are explained and illustrated in detail below. The value of $M_j$ is the minimum number of trips required at shift j to meet the maximum allowable waiting time. In this model, a single trip time for a given shift is 30 minutes in the length of the period which is 4 hours. For a given shift, then a minimum of 8 trips are required to limit the maximum waiting time of passengers to 30 minutes. This means, there should be at least one bus every 30 minutes or half an hour for each shift to provide quality service. The actual minimum number of busses required for this model is one bus because within a trip time of 30 minutes one bus can make eight trips during a 4 hour time interval. Therefore, $M_j$ is given by:

$$M_j=\frac{\mathit{\text{Total Duration for}}\mathrm{s}\mathit{\text{hift}}j\left(\mathit{\text{minutes}}\right)}{30\mathit{\text{minutes}}}$$E15

Thus using Eq. 15 and the data reported in Table 2 above, the value of $M_j$ for the four shifts are computed and presented in Table 3.

Route No.	Demand		Demani (Dij) per Shift				Trip factor (Tij) per Shift
		Pi	D1 (m1 = 7)	D2 (m2 = 12)	D3 (m3 = 8)	D4 (m4 = 3)	1	2	3	4
1	4126	0.014	1650	825	1444	206	7	12	8	3
2	3497	0.012	1399	699	1224	175	4	7	5	2
3	11,030	0.038	4412	2206	3860	551	4	7	5	2
4	3029	0.010	1212	606	1060	151	3	5	3	1
93	778	0.003	311	156	272	39	2	4	3	1

Table 3.

Input parameters for the LP model for some routes.

7.2 Trip factor analysis

The other parameter that needs to be defined and explained is the trip factor, $T_{\mathit{ij}}$. It is computed using Eq. 16. This value is the minimum number of trips a bus can make on route $i$ at a given shift $j$. Since the model computes the total trips that are needed per route per shift, the trip factor is used to calculate the available number of trips per route per shift.

The trip factor is the maximum number of trips a bus can make on route $i$ per shift $j$; this factor is used to get the available number of busses in terms of trips. This is because the model computes the total number of trips that are required per route per shift. The actual number of busses is, then, calculated from the trip factor by setting how many trips a single bus can make at a given period.

$$T_{\mathit{ij}}=\frac{\mathit{\text{Total Duration for shift j}}}{\mathit{\text{Single trip travel time for route i}}}$$E16

By multiplying the trip factor by the available number of busses, that is $F_x$ and $F_y$, it can help to find the maximum possible trips made by the total available busses.

7.3 Trip proportion

The other parameter that needs explanation is the trip proportion, $P_i$. It is required for route $i$ during shift $j$. $P_i$ is the trip proportion of a given route $i$ from the overall routes also given by Eq. 17? $P_i$ is used to determine trips to route $i$ from the total available. The number of trips for each route is also computed based on the proportion of the total trips of all the routes. It is given by the following equation.

$$P_i=\frac{\mathit{\text{Daily Demand of Route i}}}{\mathit{\text{Total Daily Demand of all Routes}}}$$E17

The last parameter the requires explanation is $D_{\mathit{ij}}$. It is the average daily passengers of route $i$ during shift $j$ that requires transport services. It is collected from the secondary data sources of the enterprise. It is allocated per shifty by multiplying the average number of daily passengers of route $i$ by the demand proportion of shift $j$ and is reported in Table 2.

7.4 Solve the model

The next step is to run the model to obtain feasible solutions. The LP model is solved based on the data of the average daily passengers that have been transported for the last 19 months in four shifts. The daily passengers’ that demand for transport for the last 19 months was collected and then the average daily passenger’ demand of each month was computed per route per shift based on the trip proportion ($P_i$) of route $i$, and reported in Table 3.

7.5 Input parameter to the model

In the process of running and solving the model, first, the input data has to be fitted. In this regard, to fit the LP-model with the input parameters that are involved in the model, first it the parameters needs to be determined. These parameters are either computed or collected from the enterprise. The sample input parametric values are shown in Table 3.

These inputs parameters are standard carrying capacity of busses, the operational number of busses, the passenger that demand transport services per route per shift ($D_{\mathit{ij}}$), the trip factors ($T_{\mathit{ij}}$), the minimum number of trips per shift ($M_j$) and the trip proportion per route ($P_i$). The sample input parametric values of a few routes are shown in Table 3.

There are four types of busses used by the enterprise (namely DAF, Mercedes, Single, and rigged Articulated busses) but they can be categorized in two based on their seat capacity. These are one bus with seat capacities of 30 passengers (DAF, Mercedes, Single, and rigged Articulated) and busses with seat capacity 50 passengers (the Articulated one).

While fitting to the LP-model busses with a seating capacity of 30 are classified as bus type-I (but can transport 60 passengers) and busses with a seating capacity of 50 are classified as bus type-II (but can transport 90 passengers). The maximum number of capacity, 60 passengers and 90 passengers are based on the standard capacity of public bus transportation [33]. The total capacity of each bus type is equal to the seating capacity plus the standing capacity. The enterprise has a total number of type-I and type-II is 600 and 90, respectively. Thus, the objective function of the research is used to compute the optimum trips and mixes of the two types of busses per route per shift.

The total operational busses in bus type-I are 600 and that of bus type-II is 90 busses. The numbers of operational busses are not only 690, but the rest of the operational busses are kept for backups during failure and other services such as contract and employee service. Also, the 93 routes which are under analysis serve more than 90% of the demand during a day and thus the operational bus assignment is based on this proportion. After substituting the values of input parameters and constants into the LP model, the model can be re-written as:

$$Minimize:\sum _{j=1}^4\sum _{i=1}^{93}\left[x_{\mathit{ij}}+y_{\mathit{ij}}\right]$$E18

Subject to

$$60x_{\mathit{ij}}+90y_{\mathit{ij}}\ge D_{\mathit{ij}}$$E19

$$\sum _{j=1}^4\sum _{i=1}^{93}{x}_{\mathit{ij}}\le 600\ast \sum _{j=1}^4\sum _{i=1}^{93}{T}_{\mathit{ij}}$$E20

$$\sum _{j=1}^4\sum _{i=1}^{93}{y}_{\mathit{ij}}\le 90\ast \sum _{j=1}^4\sum _{i=1}^{93}{T}_{\mathit{ij}}$$E21

$$\sum _{j=1}^4\sum _{i=1}^{93}\left[x_{\mathit{ij}}+y_{\mathit{ij}}\right]\ge 93\ast \sum _{j=1}^4{M}_j$$E22

$$x_{\mathit{ij}}\le 600\ast P_i{T}_{\mathit{ij}}$$E23

$$y_{\mathit{ij}}\le 90\ast P_i{T}_{\mathit{ij}}$$E24

$$\sum _{i=1}^{93}{P}_i=1$$E25

$$x_{\mathit{ij}},y_{\mathit{ij}}\ge 0$$E26

8. Model output

The output of the model indicates the total number of trips by the two types of busses needed to serve the average demand of each route on a given shift. The sample outputs of the LP model are shown in Table 4.

Route No.	Shift 1		Shift 2		Shift 3		Shift 4
	Bus type-I	Bus type-II	Bus type-I	Bus type-II	Bus type-I	Bus type-II	Bus type-I	Bus type-II
L	19	9	0	10	14	11	0	3
2	19	5	5	8	15	6	0	2
3	61	14	14	24	48	17	0	7
4	18	3	6	5	15	3	2	1
5	14	3	4	6	12	3	0	2
6	51	12	0	21	41	14	0	6
·	·	·	·	·	·	·	·	·
·	·	·	·	·	·	·	·	·
·	·	·	·	·	·	·	·	·
91	4	1	2	2	4	1	1	1
92	21	5	0	9	17	6	0	3
93	11	4	0	5	9	4	0	2
Total	1541	402	174	618	1231	490	18	156

Table 4.

Number of trips required per route per shift.

The GAMS build system has different solvers such as BARON, BDMLP, and BENCH. Replace this text with your section Heading CNOPT, CPLEX, LGO, etc. that are capable of solving different varieties of problems. After trying each solver, for reporting purposes, CPLEX solver is chosen to solve the LP model developed above. The LP model is coded and programmed using the GAMS. This build system and the piece of the GAMS code are reported in the Appendix.

The outputs of the model are reported by taking the upper integer value. As shown in Table 4, for example for route 3, 61 trips by bus type-I and 14 trips by bus type-II were required for shift one. There are also routes where no trips are required by bus type-I in the off-peak shifts. Since the LP model produces the number of trips required, the output has to be converted into the number of busses required for each route in a given shift. This has to be done by dividing the number of trips from the model output by the trip factor ($T_{\mathit{ij}}$). The sample of the number of busses per route per shift presented in Table 4 and computed for all 93 routes in the same way.

9. Assigning buses to routes

Based on the results of the output of the LP-model, there are 4627 total trips required to serve the average daily passenger demand. The actual number of busses required for a given route i during a given shift $j$ depends on the trip factor. That is the number of trips that can be made by each bus type during a given shift. Thus, the output needs to be transformed into the number of busses needed for each route per shift based on the feasible trips that a bus can make during a given shift $j$ on each route $i$. From the output of the LP model shown in Table 3, the number of trips can be transformed into number busses using the following equation.

$$\mathit{\text{Number of Bus}}=\frac{\mathit{\text{Number of Trips}}}{T_{\mathit{ij}}}$$E27

For some routes, the output of the LP is small for some route, so adjusting the actual number of busses is required for such routes to have at least two busses on a given route per shift to allocate them on both ends of the route; that is one on the going trip and the other on the returning trip. This is because the demand during a given shift $j$ on each route $i$ lies in both directions of the route. Sample of the number of busses per route per shift reported in Table 5 and computed for all 93 routes in the same way.

	Shift 1		Shift 2		Shift 3		Shift 4
Route No.	Bus type-I	Bus type-II	Bus type-I	Bus type-II	Bus type-I	Bus type-II	Bus type-I	Bus type-II
1	3	1	1	1	2	1	1	1
2	5	1	1	1	3	1	1	1
3	16	3	2	3	10	4	0	3
4	6	1	2	1	4	1	2	0
5	4	1	1	1	3	1	1	1
6	12	3	0	3	8	3
·	·	·	·	·	·	·	·	·
·	·	·	·	·	·	·	·	·
·	·	·	·	·	·	·	·	·
91	3	0	2	0	3	0	3	0
92	5	1	1	1	3	1	1	1
93	2	1	1	1	1	1	2	0
Total	396	94	114	88	269	94.8	121	79

Table 5.

Number of busses per route per shift.

The results showed that the actual number of busses required during peak periods is higher than that of off-peak periods. Thus, some of the busses that operate during the morning peak period have to wait on bus stops until they are required for the evening peak.

Similarly, the actual number of busses required for each shift varies and the number of busses required during peak periods is higher than that of off-peak periods. Thus, some of the busses that operate during the morning peak period have to wait on bus stops until they are required for the evening peak.

10. Model validations

The outputs of the LP-model were evaluated using different performance measuring parameters. For the validation purpose, various assessments were made between the existing performances and the LP improved systems. The comparisons made, in this research, were based on bus utilization, distance and trips covered and the different operating costs of the enterprise [32]. Each of them is discussed in the following sections.

10.1 Bus utilization

After converting and assigning busses to each route and each shift, then the improvements achieved by the LP model were compared with the existing bus utilization of ACBSE [32]. The bus utilization was calculated as the ratio of the number of passengers served by the bus to the number of passengers carrying capacity. The average daily bus utilization of the existing and the improved systems are presented in Figure 3. The results of the study show that the improved system has better bus utilization than the existing one. The existing system has a maximum bus utilization of about 125% on daily basis, which is very congested and crowded, while the improved system by this study has shown that a maximum bus utilization of 97% [32]. This shows how passenger congestion and service quality were improved by the new system. The average bus utilization for the improved systems is about 66.33% which is better than the existing systems that are 64.26%. Though the average utilization of both of the systems seems close to each other, in the improved most of the utilization lies between 60% and 80% whereas in the existing system had unbalanced bus utilization which is sometimes failed below 20% and other times above 120%.

As presented in Figure 4, an in-depth analysis of bus utilization based on shift was carried out. The improved system exhibited significant improvement as compared to the existing one and reported by shift. The improved bus utilization by shift is 89.8% during the morning peak, 51.19% during the first off-peak, 82.24% during the evening peak, and 42.1% during the second off-peak periods. The improvement as compared to the existing systems is 19.75% during first off-peak and 12.15% during the second off-peak. The bus utilization of the improved system also reduced the passengers’ congestions in peak hours, i.e. bus utilization is decreased from 116.1% to 89.8%. Thus, the improved system has a relatively stable and consistent bus utilization with improved service quality. The new model also indirectly improves the service quality for passengers by reducing over crowdedness while during peak periods and reduces the operating cost during off-peak periods to the enterprise.

10.2 Distance and trip coverage

In this section, the distance covered by the existing and the new system are compared. To compare this, the total kilometer covered by busses for route i per day is computed. It is the sum of the Kilometer covered during all the four shifts. Figure 5 shows that the total distance coverage of the current and improved systems. The distance covered on each shift was computed by multiplying the number of busses allocated to a given route at that shift by the number of trips that can be made by a single bus and by the route length. The total distance covered per day for the improved system is 70,964 kilometers, while for the existing system, it is about 78,963.7 kilometers per day. This shows a reduction of 10.13% in the daily distance coverage to serve the same number of passengers.

Figure 5.

Distance coverage; current vs improved system.

In this case, the total daily trips made for the improved system is also computed for each shift by multiplying the number of busses assigned and the number of trips a single bus can make during that shift. The total trips covered for the existing systems were 5504 trips per day while 5584 for improved systems. This also shows an improvement of 80 trips per day compared with the existing system. The increased number of trips was achieved with a 10.13% reduction on the daily Kilometer. This also improves service availability in addition to saving on the operating costs.

10.3 Operating costs

Using the different operating costs of the enterprise, the other performance measuring parameters were also assessed in this research. The improvements made by the new model were also considerable. The total daily operating cost of the enterprise for each route is the sum of operating costs for all the shifts. From the comparison made, the results of the study show that the average daily operating costs of the enterprise for the existing systems are about 1,101,283.68 ETB (ETB = Ethiopian Birr and 1USD = 34.33ETB as of Jun 4, 2020) while for the improved systems is 949,991.49 ETB. The saving of the new system in this read is about 13.74% per day compared to the current system. Figure 6 shows the improvements made by the new systems are achieved nearly in all the operating costs of the enterprise compared to the existing one.

Figure 6.

Current vs improved operating cost.

As compared to all the operating costs, larger saving is observed on gas oil. This reduction has also a strong relationship with the total Kilometer covered by each bus. This is due to the fact that the total kilometer covered is improvement resulted in a reduction in the cost of gas oil consumed.

11. Conclusion

The motivation of this research was to develop a model that can optimize the operational performances of ACBSE. Based on the major findings, it can be concluded that the existing scheduling systems of ACBSE have shown low performances on the bus utilization, operating cost, and daily trips and distance covered. These improvements have been achieved because the existing system has fixed numbers of busses assigned to routes without considering the variability of passenger demands. This had cost more the enterprise. However, the operational performance improvements of the LP-model have shown better performances over the existing one nearly in all of the above performance measuring parameters. Besides, it can be concluded that the existing bus scheduling and operations system has a lower average utilization of busses compared with the new system by 2.1%. The bus utilization per route per shift also shows significant improvement over the existing system. With regard to the cost-saving, the new model has resulted in a saving of 13.74% (151,292.19 ETB) in the operating costs of the enterprise. Moreover, the new model also resulted in a 10.13% saving on the total km covered with 80 additional available trips per day for the enterprise. In addition to these and the saving in all the parameters, the improved system has also reduced the waiting time, improve service quality, and reduce passenger congestion by scheduling busses based on the international standard bus capacity. The new system has also a significant reduction in the total kilometer covered while improving the total trips made daily. All these improvements of the new system of the LP-Model were exhibited without altering the existing routes used by the enterprise. But rerouting the existing route’s design may also bring radical improvement to the performances of the enterprise.

Appendix: the GAMS sample code

***************

Defining Route i and Shift j

Sets i Routes /1 ∗ 93/ This sets routes from route 1 to route 93.

j Time periods /1 ∗ 4/; Sets shifts from shift 1 to shift 4.

Sample Demand distribution per route per shift

Table d(i, j) demand distribution on route $i$ on time shift $j$

  1   2   3   4

1 2249 1124 1968 281

2 2249 1124 1968 281

3 2249 1124 1968 281

.  .   .   .   .

.  .   .   .   .

.  .   .   .   .

92 1848 924 1617 231

93 1362 681 1192 170

Sample Trip Factors (T_ij)

Table T($\mathit{ij}$) trip factor on route $i$ for time period $j$

Minimum Trip Required (M$j$)

Parameters M($j$) minimum trips required at time period $j$

Trip Proportion (P_i)

 1 2 3 4

1 7 12 8 3

2 4 7 5 2

3 4 7 5 2

. . . . .

. . . . .

. . . . .

92 8 5 2

93 5 9 6 2

/1 7

2 12

3 8

4 3/

P(_i) demand proportion of route$\mathit{i}$from all routes /

1 0.014

2 0.012

3 0.040

. .

. .

. .

92 0.012

93 0.009/;

Decision Variables

 X(i$j$) Number of Bus type-I for route i during shift j

 Y (i$j$) Number of Bus type-II for route i during shift j;

 Variable Z; For the objective function

Model Equation

 obj.. Z=e=sum((i,j), X(i,j))+ sum((i,j), Y(i,j));

 const1.. sum((i,j), X(i,j))*60 + sum((i,j), Y(i,j))*90 =g= sum((i,j),d(i,j));

 const2.. sum((i,j), X(i,j))=l= sum((i,j), T(i,j))*600;

 const3.. sum((i,j), Y(i,j))=l= sum((i,j), T(i,j))*90;

 const4.. sum((i,j), X(i,j))+ sum((i,j), Y(i,j)) =g= sum(j, M(j));

 const5.. sum((i,j), X(i,j))+ sum((i,j), Y(i,j))=l=sum((i,j),T(i,j))*690;

Since bus type-II has greater capacity, priority is given so that demand is to be served by the available capacity of Y for that route to reduce number of buses required and if it is beyond the available number of Y for that route then the rest is to be served by the available number of X. Thus, based on this assumption the following equation sets the lower bound to values of X and Y, if not since it is minimization it starts from zero and can’t display the appropriate mix of X and Y.

Y.lo(i, j)$[(d(i, j)/90) ≤ (T(i, j) * P(i) * 90)] = d(i, j)/90; lower bound for Y

Y.lo(i, j)$[(d(i, j)/90) ≥ (P(i) * T(i, j) * 90)] = P(i) ∗*T(i, j) * 90;

X.lo(i, j)$[(d(i, j)/90) ≥ (P(i) * T(i, j) * 90)] = (d(i, j)/60) − (P(i) * T(i, j) * 90);

*lower bound for X*

X.lo(i, j)$[((d(i, j)/60)−(P(i)*T(i, j)*90)) ≥ (P(i)*T(i, j)*600)] = (P(i)*T(i, j)* 600);

Thus from this, the assignment of bus type X depends on the assignment of Y and X is

assigned for a given route if the expected demand during that time period is beyond

the capacity and availability of bus type Y

Model eq / All / ;

Solve eq using lp minimizing Z;

display X.l;

display Y.l;

*****************