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

## 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.

### Keywords

- bus scheduling
- bus utilization
- linear programming
- optimization techniques
- model validation

## 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

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.

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

The common VRP comprises a set of at most

Subject to

Where:

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

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].

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.

Route No. | Origin(local Name) | Destination (local Name) | No. of busses | Kms |
---|---|---|---|---|

Megenagna | Kara | 2.00 | 7.70 | |

Kore Mekanisa | Addis Ketema | 4.00 | 11.10 | |

Ayertena | Minilik Square | 8.00 | 10.80 | |

Haliti | Addis Ketema | 5.00 | 19.40 | |

Bole Bulbula | Megenagna | 2.00 | 15.20 | |

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% |

870 | 100 |

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

Definition of terms:

j = Shifts,

The objective is to minimize the total number of trips made by bus type-I and bust type-II. This objective is represented by

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

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,

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.

Subject to

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,

### 7.1 Minimum number of buses

For clarity and understanding, moreover, some of the parameters were defined. Some of the parameters are,

Thus using Eq. 15 and the data reported in Table 2 above, the value of

Route No. | Demand | Demani (D_{ij}) per Shift | Trip factor (T_{ij}) per Shift | |||||||
---|---|---|---|---|---|---|---|---|---|---|

Pi | D_{1} (m_{1} = 7) | D_{2} (m_{2} = 12) | D_{3} (m_{3} = 8) | D_{4} (m_{4} = 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 |

### 7.2 Trip factor analysis

The other parameter that needs to be defined and explained is the trip factor,

The trip factor is the maximum number of trips a bus can make on route

By multiplying the trip factor by the available number of busses, that is

### 7.3 Trip proportion

The other parameter that needs explanation is the trip proportion,

The last parameter the requires explanation is

### 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 (

### 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 (

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:

Subject to

## 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 |

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 (

## 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

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

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 |

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.

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.

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

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

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.

Table d(i, j) demand distribution on route

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

_{ij}

Table T(

Parameters M(

_{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/

_{i}

1 0.014

2 0.012

3 0.040

. .

. .

. .

92 0.012

93 0.009/;

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.

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;

## References

- 1.
Cordeau J-F, Gendreau M, Laporte G, Potvin J-Y, Semet F. A guide to vehicle routing heuristics. Journal of the Operational Research Society. 2002; 53 :512-522 - 2.
Reimann M. Analyzing a vehicle routing problem with stochastic demand using ant colony optimization. In: EURO Working Group on Transportation. 2005 - 3.
Bunte S, Kliewer N. An overview on vehicle scheduling models. In: Decision Support & Operations Research Lab. Warburger, Germany: University of Paderborn; 2009 - 4.
Seong P, Jae. Bus Network Scheduling with Genetic Algorithms and Simulation [Master of Science Thesis]. College Park: University of Maryland, Department of Civil and Environment Engineering, University of Maryland; 2005 - 5.
Caric T, Gold H. Vehicle Routing Problem. Croatia: I-Tech, I-Tech Education and Publishing KG; 2008 - 6.
Christopher J, Goodson. Solutions Methodologies for VRP with Stochastic Demand [Dissertation] Iowa; 2010 - 7.
Clara N, Rosemary B, Jeff L, Robert S. A Set Partitioning-Based Model for the Stochastic Vehicle Routing Problem. Technical Report. Bethlehem, PA: Texas State University and Lehigh University, 601 University Drive San Marcos, TX 78666 or 200 W. Packer Ave; 2006 - 8.
Reimann M, Doerner K, Hartl RF. D-ants: Savings based ants divide and conquer the vehicle routing problem. Journal of Computers & Operations Research. 2003; 31 (4):563-591. ISSN: 0305-0548 - 9.
Antonios T, Ioannis M. Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns. European Journal of Operational Research. 2009; 197 :557-571 - 10.
Bianchi L. Notes on Dynamic Vehicle Routing, the State-of-the-Arts. Techniacal Report Idsia-05-01. Switzerland: Istituto Dalle Molle di Studi sull’Intelligenza Artificiale; 2000 - 11.
Anbuudayasankar SP, Ganesh K. Mixed-integer linear programming for vehicle routing problem with simultaneous delivery and pick-up with maximum route-length. The International Journal of Applied Management and Technology. 2008; 6 (1):31-52 - 12.
Dantzig GB, Ramser JH. The truck dispatching problem. Journal of management science. Management Science. 1959; 6 (1):80-91 - 13.
Laporte G, Louveaux FV, Hamme v L. An integer l-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research. 2002; 50 :415-423 - 14.
Tillman FA. The multiple terminal delivery problem with probabilistic demands. Transportation Science. 1969; 3 :192-204 - 15.
Baldacci R, Vigo D, Toth P. Exact Solution of the Capacitated Vehicle Routing Problem. USA: John Wiley & Sons, Inc.; 2010 - 16.
Toth P, Daniele V. The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications. Philadelphia, PA: Society for Industrial and Applied Mathematics, Society for Industrial and Applied Mathematics; 2002. pp. 19104-12688 - 17.
Winston W. Operations Research: Applications and algorithms (with CD-ROM and Infotrac). 4th ed. Thomson Brooks/Cole; 2003 - 18.
Calvete HI, Gale C, Oliveros MJ, Sanchez-valverde B. Vehicle routing problems with soft time windows: An optimization based approach. Journal of Monograf del Seminario Matemco Garce Galdeano. 2004; 31 :295-304 - 19.
Drex M. Rich Vehicle Routing in Theory and Practice. Technical Report Lm. Mainz, Germany: Johannes Gutenberg University; 2011 - 20.
Moses C, Samir K, Balaji R. Algorithms for capacitated routing. Journal of SIAM Journal on computing. 2001; 31 (3):665-682 - 21.
Xiangyong L, Peng T, Leung S. Vehicle routing problems with-time windows and stochastic travel and service times: Models and algorithm. International Journal of Production Economics. 2010; 125 :137-145 - 22.
Chenghua S, Xiaofeng Z. Research on model fitting capacity of vehicle routing problem. International Journal of Advancements in Computing Technology(IJACT). 2011; 3 (11):185-193 - 23.
Roberto B, Maria B, Daniele V. Routing a Heterogeneous Fleet of Vehicles. Technical Report deis. or. ingce 2007/1, DEIS, University Bologna, via Venezia 52, 47023 Cesena, Italy; 2007 - 24.
Laporte G. Fifty years of vehicle routing. Transportation Science. 2009; 43 (4):408-416 - 25.
Avishai C. Optimal multi-vehicle type transit timetabling and vehicle scheduling. Procedia—Social and Behavioral Sciences. 2011; 20 (0):19-30 - 26.
Baldacci R, Battarra M, Vigo D. Routing a heterogeneous fleet of vehicles. In: Golden B, Raghavan S, Wasil E, editors. The Vehicle Routing Problem: Latest Advances and New Challenges, Volume 43 of Operations Research/Computer Science Interfaces. US: Springer; 2008. pp. 3-27 - 27.
Mariam F, Ahmed M, Anouck G. Vehicle routing problem instances: Application to multi-uav mission planning. In: Conference, American Institute of Aeronautics and Astronautics (AIAA) Guidance, Navigation. Toronto, Ontario Canada; 2010 - 28.
Linong C-Y, Wan I, Khairuddin O, Zirour M. Vehicle routing problem: Models and solutions. Journal of Quality Measurement and Anlysis. 2008; 4 (1):205-218 - 29.
Cordeau J-F, Laporte G, Mercier A. A unifid tabu search heuristic for vehicle routing problem with time windows. Journal of Operations Research Society. 2001; 53 :928-936 - 30.
Wouter J. Approximate Models and Solution Approaches for the Vehicle Routing Problem with Multiple Use of Vehicles and Time Windows [Master thesis] Middle East Technical University; 2008 - 31.
Stewart WJ, Golden BL. Stochastic vehicle routing: A comprehensive approach. European Journal of Operational Research. 1983; 14 :371-385 - 32.
Berhan E et al. Performance Analysis on Public Bus Transport of the City of Addis Ababa. International Journal of Computer Information Systems and Industrial Management Applications. 2013; 5 :722-728. ISSN: 2150–7988 - 33.
TCRP. Transit Capacity and Quality of Service: Part 4 Bus Transit Capacity Manual. 2nd ed. Vol. 8. Orlando, FL: Kisttelson and Associates, Inc; 2012