key: cord-0009969-60kuwg9h authors: Shen, Yindong; Xia, Jiahong title: Integrated bus transit scheduling for the Beijing bus group based on a unified mode of operation date: 2009-02-23 journal: Int Trans Oper Res DOI: 10.1111/j.1475-3995.2009.00673.x sha: e12d7aa58d54b0ff35deeec1ebba036e91c81468 doc_id: 9969 cord_uid: 60kuwg9h This paper presents an applied study of scheduling buses and drivers for the Beijing Bus Group (BJBUS), the largest bus company in China. This is pioneering research in China for bus transit scheduling using computers based on a unified mode of operation. It is anticipated that the research fruits and experiences obtained would be of benefit to other bus operators in China. The bus transit scheduling problem in BJBUS is first presented in the paper. The particular characteristics are pointed out, which are different from those in developed countries, while many are common in China. After a brief review and analysis of the appropriateness of some currently successful approaches, the paper focuses on reporting the solution ideas and methods for BJBUS, especially those developed to solve the specific problems of BJBUS, such as scheduling buses with built‐in meal periods, multi‐type bus scheduling, restricting drivers to one or two particular buses, etc. Finally, the implementation and computational results are reported before the concluding remarks. The bus transit scheduling problem is of great practical importance as efficient schedules can make huge monetary savings and/or increase the capacity of bus transit services. Building efficient schedules is one of the best ways for the transportation industry to maximize profit. This problem has attracted much research interest in developed countries since the 1960s. Many approaches have been developed, most of which have been reported in a series of international conferences on Computer-aided Public Transport Scheduling (e.g., Hickman et al., 2008) . However, research on bus transit scheduling using computers in China has just started in recent years. Much of it attempts to build a mathematical or heuristic model to tackle the bus vehicle scheduling problem on a line-by-line basis (Li et al., 1992 (Li et al., , 1995 Liu and Shen, 2007; Chen et al., 2004; Xia, 2003, 2004b) . Unfortunately, it still requires much effort to meet the practical requirements of bus operators. So far, the bus operators commonly schedule their buses and drivers manually on a line-by-line basis. The operation mode and scheduling methods have not significantly improved since the establishment of P. R. China in 1949; however, the number of vehicles has increased more than 1000 times since then, from fewer than 200 to about 240,000 buses. In contrast to western countries, the mode of bus operation and the scheduling methods in China are very inefficient, and are difficult to adapt to the rapid increase in vehicle numbers and the changed requirements of bus services. The backward mode of operation and the scheduling methods have caused many problems to the bus operators and the government. The major problems are summed up as follows: (1) Utilization of resources is restricted and inefficient Buses and drivers are restricted to a specific bus line. Each line has to be assigned enough buses and drivers to meet the demands of its own peak times. This will cause some buses and drivers to be left unused before and after the peak times. Hence, the utilization of these resources which are not allowed be switched between lines, is restricted. (2) The management and operational cost is high Each line has to set up an individual management group and its own depot in most cases. The ratio of staff to buses may reach 5 to 1 in many bus companies; the distributed depots occupy much precious land in cities. (3) Schedules are compiled manually and cannot be timely adjusted according to changes Normally compiling a set of bus and driver schedules for a line will take about 20 person-days. It is also very time-consuming to adjust schedules according to changes in service demands and operating conditions; therefore, many schedulers abandon such adjustments because they can only achieve them with difficulty. Furthermore, schedules compiled manually are usually too simple to fit the real service demands and operating environment, and hence they can seldom be executed. For this reason, some bus companies do not compile schedules at all. (4) There are no practical schedules guiding dispatchers and drivers Each terminus has to have a dispatcher, who plays part of the roles of schedulers by deciding the departure time of each service trip according to experience. The efficiency of dispatching depends greatly on the experience, responsibility and personal authority to drivers of an individual dispatcher. (5) Bus services are often in disorder The bus service is independent between individual lines; hence the different lines passing along the same road cannot be organized and scheduled together. It often causes disorder at busstops as several buses arrive simultaneously. This phenomenon is quite common in many cities, and is called train-like bus service. supported by the state. The demonstration project of BJBUS attempts to set up a pattern of scheduling buses and drivers using computers based on a unified operation mode for the 1300 bus companies in China. It was anticipated that most of the bus operators in China would apply the advanced scheduling techniques to schedule their buses and drivers based on a unified mode of operation before the start of the 2008 Olympic Games. It was also anticipated that it would save about 5-10% of buses and drivers by applying the procedures obtained in the project. This would have a great significance in China, where there would be 400,000 buses and one million drivers in services in 2008. However, there were fears that the new operation mode would cause unpredictable problems during the critical year of the Olympic games. It is therefore at present only used within one sub-district of the Beijing Bus Group. Wider implementation of the system will take place after 2008. The authors of this paper have been involved in this project and are in charge of the core research work of building an integrated bus transit scheduling system for BJBUS. The work is reported in this paper. The organization of the paper is as follows: the bus and driver scheduling problem of BJBUS is first presented; the framework of the demonstration project is then depicted. Next, the scheduling and rostering approaches developed for BJBUS are addressed. Finally, the implementation and computational results are reported before the concluding remarks are given. BJBUS is the largest bus company in China. Over 85% of bus services in the city of Beijing are provided by BJBUS, which possesses about 22,000 buses working on 776 lines, each scheduled separately, with about 97,000 drivers. Bus services in Beijing have to meet extraordinary levels of demand and traffic congestion. The nature of the scheduling problem is different from most of those described in the publications of developed countries (e.g., Hickman et al., 2008; Desaulnier, 2007; Ernst et al., 2004) , but typical in China. In the most successful bus and driver scheduling systems, many of which are developed based on the operations in developed countries, buses and drivers are scheduled independently, and can switch between lines during a single work period. However, the scheduling mode and requirements of BJBUS are considerably different: buses and drivers are scheduled manually and simultaneously on a line-by-line basis; each line is assigned a fixed number of buses and drivers to meet the demands in its own peak times; there is a set of rules governing the legality of duty generation (a duty is the work to be performed by a driver during one day from signing on until signing off at the depot); besides the most common rules such as maximum daily driving time limits, say 8 h (listed in Smith and Wren, 1988) , there are some rules stipulated according to Chinese conventions, e.g., a meal break must occur within the customary time range for lunch or dinner, say, from 11:30 to 13:00 or from 18:00 to 20:00; the scheduling strategy is to develop bus schedules with built-in periods at lunch or dinner time when the buses are parked at the terminus so that meal breaks can be taken; each bus can be assigned to at most two duties; each duty is limited to work on at most two buses (a single bus is preferable). In recent years BJBUS has been interested in reducing costs by applying more efficient scheduling techniques and management modes, possibly switching buses and drivers between lines or introducing empty balancing journeys against the peak flow under some restrictions. Considering all these rules and requirements (which are commonly imposed by many of the bus operators in China), the existing manual and computer-aided scheduling systems encounter difficulties. It is a major problem to solve the scheduling requirements of BJBUS. Scheduling buses and drivers based on a unified mode of operation using computers is a brand-new idea in China although it has been quite common in developed countries. To convert from a line-by-line scheduling mode to the unified scheduling mode while satisfying many of the current rules and requirements, none of the existing systems are directly applicable, needing a great effort of research. Meantime, reorganization of customary management modes and methods is also needed in order to make the new scheduling system work properly, which is a non-trivial task. In China new management systems, new management methods and new techniques to be applied to the bus companies are usually first tried in BJBUS. If successful, the other companies would follow it and treat BJBUS's experience as a benchmark. Therefore, selecting BJBUS to do the Demonstration Project on Unified Bus Transit Scheduling and Dispatching has great practical significance. It will affect profoundly the other bus companies. After the completion of the project, BJBUS will be the first in China to schedule its buses and drivers using computers based on a unified operation mode. The demonstration project has had 18 million RMB Yuan invested in research and 80 million RMB Yuan in the reconstruction of the depots, termini and a unified scheduling and dispatching centre, etc. It was originally expected that a computer-aided Bus Transit Management and Scheduling (BTMS) system (illustrated in Fig. 1 ) would be built in three years from 2002. Figure 1 illustrates the framework and data flow of the computer-aided BTMS system, which consists of a supporting platform and a set of application systems. The supporting platform includes database management systems, computer networks, communication systems and a geographic information system (GIS). The set of application systems includes a management information system (MIS), a scheduling system, a dispatching system, a passenger demands collecting system ( PDCS), a vehicle locating system (VLS), and a custom information service system (CISS). The MIS is the foundation of the applications systems, managing all kinds of data related to bus transit management and operation. The VLS system is in charge of locating and recording the running of buses aided by a global positioning system (GPS). The PDCS is to collect the numbers of passengers on each line in order to find the pattern of demands. The dispatching system is to help human dispatchers to direct drivers' operations when some unexpected events happen so that the precompiled schedule cannot be executed. The CISS may include many kinds of systems to provide service information, such as a web-based information system, a built-in bus message monitor, a station message monitor, etc. The scheduling system is the core of the entire BTMS system, without which the function of the other systems cannot be fully realized. The scheduling system has to include the following functions: Y. Shen and J. Xia / Intl. Trans. in Op. Res. 16 (2009) (a) To assist the bus management to decide the composition of operating districts by compiling simulated schedules for the lines within the proposed district. (b) To compile effective bus and driver schedules, which would serve as guidelines for drivers and dispatchers. With the aid of these elaborate schedules and a monitoring and dispatching system, drivers could complete their duties without the direction of human dispatchers. Hence, the number of dispatchers could be reduced. (c) To allow the schedules to be recompiled quickly to meet changes in demands and running conditions (the schedules to be executed must be generated at least one day in advance because this scheduling system does not attempt to handle urgent events on a real-time basis). As already mentioned, the bus transit scheduling system is the core of the demonstration project. The purpose of the system is to solve the bus transit scheduling problem of BJBUS. The concept the bus transit scheduling problem shall be used to denote the problem based on a unified operation mode throughout this paper. The problem on a line-by-line basis is a special case, in which each operating district consists of only one line. This special case will be distinguished in this paper only when necessary. The bus transit scheduling problem is concerned with the allocation of a set of resources to timetabled activities in the public transport field. It aims to help bus operators maximize the utilization of bus and driver resources by building efficient schedules. The problem is a wellknown hard combinatorial optimization problem. It tends to be handled by dealing with three separate problems: vehicle scheduling, driver scheduling and driver rostering, because the three problems, especially the vehicle scheduling problem and the driver scheduling problem, are individually hard. If these problems were combined the ensuing problem would surpass current computer scheduling approaches run on standard machines used by transport companies. The usual practice in developed countries is to compile first the vehicle schedule, then the driver schedule and finally the duty rosters in rotation. Although this decomposition would theoretically compromise the optimization of the entire problem, there have been many successful applications. Because the research on solving the BJBUS problem is novel in China, we attempt to use for reference the experiences and approaches successful in developed countries. Having done some initial research, we found unfortunately that the existing approaches could not meet all the practical requirements of BJBUS, for instance, bus schedules should have built-in periods at lunch or dinner time when the buses are parked at the terminus so that meal breaks can be taken. Therefore, we have had to develop a set of applicable approaches, and to combine them to build an integrated bus transit scheduling system as requested by BJBUS. We have used the adjective ''integrated'' in front of the proposed bus transit scheduling system for the following reasons. Firstly, the scheduling system integrates three modules: vehicle scheduling, driver scheduling and driver rostering into a package; secondly, some constraints imposed on driver duties have to be considered as vehicle schedules are being compiled; thirdly, the generation of the vehicle and driver schedules and the duty rosters are closely related while the earlier results will profoundly affect the later solutions. These three modules, respectively, will be discussed below, while the characteristics of the BJBUS problem and the solution methods will be addressed. In public bus transport, bus vehicle scheduling (bus scheduling for short) is to allocate buses to the trips to be operated (the service being fixed in advance) in such a way that the total number of buses required to operate all the trips and the total cost are minimized. Each trip is a timetabled activity that starts and ends at specified times and locations. Bus scheduling involves making feasible and economical links among these activities. The feasibility of a solution depends mainly on whether there is enough time for the bus to connect between two successive trips. This problem has several variations depending on the number of depots, the number of bus types, the length of trips and some practical requirements, such as each bus must start and end its work day at the same depot. Among the solution methods, VAMPIRES (Wren, 1972; Smith and Wren, 1981) is a member of one of the most successful families. Later, the VAMPIRES system, developed using the Y. Shen and J. Xia / Intl. Trans. in Op. Res. 16 (2009) (Kwan and Rahin, 1999) , embracing the object-oriented paradigm and using a more user-friendly interface. The bus scheduling algorithm belongs to the class of heuristics generally known as ''2-opt''. It first forms a crude initial schedule using a target number of buses. The target is either estimated by an automatic process or specified by the user. It is possible that some of the links in the initial schedule are time infeasible, i.e. the bus arrives later than it is due to depart. The schedule is then iteratively refined. In each iteration, selected pairs of links are broken up and re-linked in the opposite way if the overall infeasibility and/or cost of the schedule are reduced. At the end, either the lowest cost feasible solution found is returned, or, if the target number of buses is too low, the critical bus trips that might be retimed to make the target number of buses feasible are indicated. VAMPIRES has been used in many hundreds of real bus scheduling problems, and has never failed to find the best known solution. BOOST, its successor, has been used in some feasibility studies involving bus companies in the United Kingdom and Brazil. Wren and Kwan (1999) report an application for one United Kingdom bus company, whose main depot in the city centre has been relocated to a new site. They satisfactorily used BOOST to re-schedule their entire new operation. In the case of BJBUS, we attempted to apply the same idea as BOOST. Unfortunately the following problems, specific for BJBUS but common in China, could not be solved: (1) Many types of bus may be operated on one line. For instances, Lines 373 and 308 run from YaMenKou, which is located outside the third circle route, to the centre of Beijing. These two lines used to have one type of bus called Gemel Bus, which are now not allowed to go to within the third circle route and have to turn around in GongZhuFen, just outside the third route. Hence, another type of bus, the capacity of which is smaller, has to be introduced into this line. Another more common instance is that buses with and without an air-conditioner are requested to run in turn. (2) Each driver must have his/her meal during the customary lunch or dinner time and it is preferable that a driver will drive the same bus after the meal. Hence, the bus schedule has to form built-in periods at lunch or dinner time when the buses stop in designated locations. (Chinese believe that having meals at regular times is very important and healthy for the stomach. Moreover, road conditions are various and complex, and hence it is better that a driver should drive the same bus all the time in consideration of safe driving.) Although the latter requirement is related to driver scheduling, it has to be considered at the same time as the bus schedule is compiled. Otherwise, it might be impossible to obtain a solution that meets the requirements enforced on driver duties later in driver scheduling. Our solution method to the BJBUS problem consists of the following main steps: (1) form a set of trips; (2) build an initial schedule; (3) refine the schedule. In the first step, a set of trips will be automatically generated based on the passenger demands of each line considering the variants in different periods of a day and bus types will be allocated. Then human schedulers may adjust the departure times and designate or modify the bus type of each trip via a user-friendly interface. The system can also assign the trips to different bus types in turn within any given running period. This step has set up the foundation of solving the bus schedule problem with multi-types. The second step is to generate a crude initial schedule using a set of target numbers, each corresponding to a bus type. The target numbers are estimated by an automatic process but can be individually increased or decreased by the user. The basic idea of this approach is derived from BOOST although BOOST only handles the bus scheduling problem with single bus-type that is usually less complex than the multi-type problem. The last step is to refine the initial schedule applying 2-opt heuristics aided by 3-opt heuristics. A 2-opt heuristic (Lin, 1965 ) is a kind of Mild Descent neighbourhood search method, in which an improved solution is obtained by exchanging two distinct components in the current solution. By exchanging three distinct components, the approach becomes a 3-opt heuristic, which is more time-consuming than the 2-opt approach and hence to be used as a last resort in this bus scheduling approach. Being analogous to BOOST, the initial schedule could be refined iteratively by breaking and re-linking pairs of links. It seems that the problem could be directly solved by this method. However, further contemplation of the method has revealed the following difficulties. Costing method Using Neighbourhood Search, a large number of solutions have to be evaluated during the scheduling process. The definition of costing methods is essential. In BOOST, a link (lining any two trips) has an associated cost, which is expressed as a function of idle time (i.e. waiting time of a bus after finishing a trip at a place and before making another trip from the place), dead run (i.e. non-passenger-carrying trips) or depot return (i.e. a time gap long enough to justify temporarily returning the bus to the depot before its next departure). The cost of operating the actual trips in most practical situations may be regarded as constant, and therefore for the optimization process the total cost of a bus schedule can be regarded as the sum of the costs of all the individual links. This costing method is called a link-based costing method, in which each link in a bus (a chain of links) has an independent cost and the sum of the individual costs constitutes the cost of the chain. A revised chain can be easily costed by re-costing only the revised or newly added links involving only simple addition and subtraction. For instance, in BOOST the cost difference between a current schedule and the new schedule after a 2-opt exchange between two links is just the same as the cost difference between the two pairs of links before and after the exchange. However, this link-based costing method is insufficient to form a schedule with built-in mealbreaks as requested by BJBUS. According to this requirement enforced on driver duties, each bus whose duration is longer than the stipulated maximum continuous driving time, should have at least a built-in period at lunch or dinner time. Therefore, when any link in a bus is changed, the validation of built-in periods has to be evaluated again. In this case, it is hard to assess precisely how much a link is contributing to optimality, and hence the cost of a bus. We therefore develop a chain-based costing method. It simply treats all the links in the same bus as having the same cost as the entire bus. When any link in a bus is changed, the bus is transformed, and the cost must be re-calculated according to its constituent links, the consistency of bus types and the validation of built-in periods. This costing method is generally more complicated and time-consuming than the link-based costing method. Penalty costing In BOOST, a link is infeasible only when there is not enough time to connect two consecutive trips. The quantitative penalty of a link is simply defined as the time lacking for connection, and thus the total penalty of a bus is defined as the sum of the penalties of all the individual links. The penalty of a feasible link is defined as zero. However, considering the built-in meal-breaks requested by BJBUS, one cannot determine whether an individual link is feasible without inspecting the whole bus. Hence, we similarly apply the chain-based costing method to treat all the links in the same bus as having the same penalty as the entire bus. If a bus is legal according to the feasibility of its constituent links, the consistency of bus types and the validation of built-in periods, the penalty of the bus is defined as zero; otherwise, a quantitative penalty is assigned to the bus. Each type of infeasibility is assigned a corresponding penalty function. The total penalty of a bus is defined as the sum of all the individual penalty functions. Penalty costing a bus is non-trivial. To conclude, the BOOST system is a basis for the development of the 2-opt heuristic approach for BJBUS, but extensive adaptations have been applied. The greatest adaptations include: being able to deal with multi-type bus scheduling problems and to compile bus schedules with built-in meal-breaks. The bus driver scheduling problem is the process of partitioning predetermined bus work into a set of driver duties, i.e. a driver schedule. The number of possible combinations for partitioning the bus work is usually astronomical. There is a set of restrictions on efficient provision of driver schedules. For example, the daily working time for a driver has to be limited to a certain number of hours. These restrictions are normally called labour agreement rules, which vary a great deal between different operators. The most common rules for bus drivers are listed in Smith and Wren (1988) . The rules governing the legality of a driver duty affect profoundly the complexity of duty compilation. The criteria are usually that the schedule must be legal according to the rules and should have the minimum number of duties and lowest total hours of work. In China, minimizing the number of duties generally has priority over minimizing the total hours of work. Using computers to solve the driver scheduling problem started in the 1960s, generate-andselect approaches based on an Integer Linear Programming (ILP) model (Smith and Wren, 1988; Fores et al., 1999 Fores et al., , 2001 Rousseau and Desrochers, 1995) are at present the most successful. They involve generating a set of legal potential duties from which a minimal and most efficient subset is selected. Despite advances in the ILP solvers, such as column generation techniques, some artificial restrictions must still be imposed on the duties in order to reduce the size of the set. For example, in practice, when a vehicle stops at a location, there is often a gap between the arrival time and the departure time, which is called a time window. A time window at a particular relief point constitutes a window of relief opportunities (WRO), during which drivers can be relieved. The generate-and-select-based approach cannot handle WROs (Shen and Kwan, 2001a; Shen, 2001) . The usual simplification is to consider one, sometimes two, discrete times within each WRO. Besides this simplification, filtering rules are often applied so that the set of potential duties generated would not be prohibitively large. For example, a minimum length may be imposed on a continuous spell of driving work. This parameter normally would be set to the highest value that would not prevent ''good'' duties from being generated. However, in practice there is no such thing as ''too short a piece of work'' for the driver, and the combinatorial nature of the problem is such that some small pieces of work may be vital in forming an efficient schedule as a whole. The resultant model solved therefore diverts from the true real-life setting and optimality is compromised. Tuning the parameterized filtering rules is also frustrating to schedulers and timeconsuming. The successful applications of the ILP-based approach are mainly in developed countries. It is not practically applicable to BJBUS. The major reasons can be summarized as follows: (1) BJBUS imposes fewer hard rules on duty generation, such as: maximum driving time and working time (corresponding to wage-cost) for a duty. Hence, it needs to apply many soft rules to prevent a system from generating too many potential duties. The adjustment of these soft rules is extremely difficult for Chinese schedulers who do not appreciate the practical limitations of the ILP approach. Moreover, applying so many artificial rules will considerably compromise the optimal solution. (2) WROs provide BJBUS with more chances to compile a ''good'' schedule, but cannot be practically handled by the ILP-based approach. (3) The problems in BJBUS even with some extent of decomposition may still be too large according to the capability of the ILP solver. A series of techniques to reduce the number of variables (potential duties) and constraints (ROs) has to be operated, and hence, the optimal solution will be further compromised. (4) Owing to the quick development and the unstable running conditions in China, bus schedules are usually changed more frequently. As a result, driver schedules need to be recompiled accordingly, and hence, a driver scheduling approach with fast computation and ease of use is expected. The ILP-based approach is not satisfactory because the duty generation process is very time-consuming and the system usually cannot produce a schedule in one go. To solve the driver scheduling problem, we enhance a Tabu Search (Glover and Laguna, 1997 )based constructive approach called HACS, which was originally developed in Leeds University by Shen and Kwan (2001b) . The HACS approach diverts from the generate-and-select model. It constructs an initial schedule and then refines it iteratively. Filtering rules and explicit reduction in problem size are unnecessary under this approach, and WROs can be solved practically. Moreover, HACS can produce solutions quickly and is easy to use; more features of HACS can be found in Shen and Kwan (2001a) and Shen (2003) . The basic idea underlying the HACS approach is appropriate to BJBUS but still needs adaptation because the HACS approach originated in a developed country and still has room for improvements. As indicated by Shen (2001) , HACS could benefit from further development in the method of constructing an initial schedule because the original one is very crude. As already mentioned, the complexity of driver scheduling is profoundly affected by a set of labour agreement rules, which are operator-specific. In BJBUS, the following rules are enforced on duties: (1) A driver signs on and signs off at the same depot; (2) Three types of duties are allowed, which are split duties (longer than standard duties, e.g. up to 12 h or more, plus a long break in the middle), straight duties (with a meal break in the middle), and single-spell duties (containing a short straight run, say 2-5 h, without meal Y. Shen and J. Xia / Intl. Trans. in Op. Res. 16 (2009) . For a split duty, the longest gap between two consecutive spells is not shorter than a given minimum length of time. (3) Meal break (i.e. the time allowance between two spells of work for the driver to travel to the canteen, have a meal and then take over the next bus) is not shorter than a specified minimum length of time, and the meal is taken within a given lunch or dinner time range; (4) A driver is usually restricted to a single bus, at most two buses, and must have knowledge of the type of the buses; (5) A bus is operated by one or two drivers, at most three only when necessary; (6) There is a limit on driving time, i.e. the total bus running time on a duty; (7) There is a maximum working time for a duty. The calculation of the working time of a duty (e.g. whether non-driving time is partially or fully counted as working time) depends on the operator and the type of the duty. Taking account of the above rules, a new method for constructing an initial schedule is designed, which consists of the following steps. (1) Form feasible duties with one bus A straight duty with a built-in meal break or a split duty is firstly formed from the beginning of the bus, the duration of which is as long as possible while maintaining feasibility (satisfying all the governing rules). Then, another duty is similarly formed from the end of the bus if there is work remaining and the duty can be feasible. The remaining work of the bus (if it exists) is left as a spell, called an uncovered spell. If all the work in the bus is exactly covered by the duties generated (without overlap), the duties are selected; otherwise, the two duties are kept in a temporary store and the remaining work of each of the duties is formed as an overlap spell. The above process will be repeated for each of the buses in the bus schedule. (2) Form feasible duties with two buses Try to pair the uncovered spells into feasible duties; then pair an uncovered spell and an overlap spell, and finally, pair the overlap spells to form feasible duties. Once an overlap spell is successfully paired, the corresponding duty stored will be removed and the other duty on the same bus will be selected and removed from the temporary store. Pair the uncovered spells, if they exist, to form duties, which may be infeasible (i.e. be time infeasible or have violated some labour agreement rules). Then, form the last single-spell duty, if the number of uncovered spells is odd. (4) Remove the overlapping work Remove the overlapping work from the duties kept in the temporary store while keeping the revised duties feasible. The above method aims to use the minimum number of duties (the preferential objective of BJBUS) and best to meet the specific requirements (see the third to fifth rules) of BJBUS. The initial schedule generated may contain infeasible duties, which are to be removed by a refining process. In the refining process, a series of strategies is devised and included in the following functions: swapping-link, replacing-ARO and adding-duty within a Tabu Search framework. Interested readers may refer to Shen and Kwan (2001b) and Shen (2003) , although some enhancements have been made in this research, such as the fact that the duty evaluation must consider the particular rules of BJBUS, and hence the costing and penalty formulas have to be revised accordingly. The nature of the Tabu Search-based approach remains the same. Driver rostering is the final stage of the bus transit scheduling. After scheduling the buses and drivers, driver rostering is the process of combining daily driver duties into sets of work for actual drivers on a daily, weekly or monthly basis. In the existing bus driver rostering approaches, rostering is normally on a weekly basis. In North America, rostering has often been left to the drivers, where each driver picks his or her duties and days off in order of seniority. This practice often leads to leftover duties that cannot be legally combined and require costly part-time or overtime work. It can also lead to an excessive number of duties with non-consecutive days off. In Europe, rostering is much more complex where the goal is to minimize the difference between individual driver's workweeks. The rostering method of BJBUS is quite different from those in North America and in Europe. The goals of rostering in BJBUS are as follows: (1) Respect a required day off. The usual practice is that a driver has a day-off after having worked three consecutive days and meanwhile completed required running miles. (2) Respect minimum off time between consecutive working days. Drivers need a minimum amount of time off between the end of one day's duty and the beginning of the next day. (3) Respect the designated line, depot and bus type of a bus and driver. A driver usually drives a fixed bus, even when his/her duty is shifted as scheduled. (4) Respect the driving groups established in advance. A driving group contains all the drivers and conductors associated with certain buses. The schedulers of BJBUS do not compile a weekly or monthly duty roster in advance. The roster for the next day is compiled daily by dispatchers based on the days and the total miles that a driver has worked consecutively since the previous day-off. Hence, drivers have to confirm their duties one day before, which is very inconvenient for drivers. The calculation of drivers' working time and off-days is a severe burden to dispatchers. Our rostering approach aims to compile duty rosters automatically respecting the proposal goals. It provides two optional modules. One is to realize the manual rostering method by computers. It creates first an initial working roster, which can be manually revised by replacing the buses or drivers as wanted via a user-friendly interface. The starting date for executing this roster has to be designated. Then, the difference between the starting date and a given date is calculated based on the parameterized rostering period (e.g. on a daily, weekly or monthly basis). Next, it can automatically generate the roster of the given date based on the difference obtained in the previous step. If the given date is not later than the initial executing date (i.e. the difference is non-positive), the roster remains the same as the initial one. This module can meet the specific requirements of BJBUS but is operator-specific. The other module attempts to be more general on a weekly basis following the pattern used in Europe. We believe that the latter module would benefit the Chinese bus operators, and expect that it would be applied after some unnecessary chronic rules were removed in the future. Y. Shen and J. Xia / Intl. Trans. in Op. Res. 16 (2009) The solution methods for the bus transit scheduling problem of BJBUS have been presented in this section. The development of the methods has taken advantage of the ideas embedded in the currently successful approaches of developed countries. However the successful application to BJBUS is greatly dependent on the solution to the characteristic problems of BJBUS. Developing an integrated bus transit scheduling system practically applicable to BJBUS has been the overriding objective. Obviously, the integration of bus scheduling, driver scheduling and rostering increases dramatically the complexity of the solution method. It would be impossible to build a comprehensive approach to solve the three problems as one. Therefore, the integrated system developed for BJBUS has compiled the bus schedule, driver schedule and duty rosters respectively in three modules while some closely related constraints are cross referenced as follows: the bus scheduling module schedules buses respecting the meal-break rules enforced on driver duties; the driver scheduling module schedules drivers taking advantage of the built-in periods in the bus schedule; the rostering module compiles duty rosters respecting the fixed line, depot, bus type of a bus and its driver. The cross references between modules are caused by some of the specific requirements of BJBUS. The idea of using the cross references has constituted the key to solving the BJBUS problem. Meanwhile, the work to meet the other practical requirements, such as multi-type buses in one line, and a driver being limited to certain buses, is also non-trivial. The ShiJingShan district of the sixth sub-company of BJBUS has been selected as the location for the implementation of the demonstration project. The 11 lines within the district are organized into a management and scheduling entity. This means that the buses and drivers of these 11 lines can be scheduled and managed together, breaking through the traditional management and scheduling mode on a line-by-line basis. The three scheduling and rostering approaches developed for BJBUS have been implemented and combined into an Integrated Bus Transit Scheduling (IBTS) system using C11 with Microsoft's COM1technique. The IBTS system is the core of the demonstration project, which has been tested on the selected 11 lines. The other application systems in the demonstration project are generally approaching the end of their development, for example, the simplified MIS has been completed, the VLS based on GPS plus GIS is being tested, the web pages of BJBUS have been able to provide bus service information. The Passenger Demand Collecting System is unfortunately encountering great difficulty due to the unacceptably low precision, and hence the human inspectors and statisticians are still employed. The dispatching system is still under construction. However, it does not obstruct the application of the IBTS system. To evaluate the performance of the IBTS system, the manual schedules of the 11 lines were gathered as a set of test problems, each of which dealt with the situation on different days (e.g., on national holidays, in the period when the SARS virus spread in China) or had a different combination of the lines (e.g. 3, 4 or 7 lines). The latest test problem of these 11 lines contained 112 vehicles (each line was assigned between 4 and 20 buses) and 182 drivers distributed among four depots. The IBTS system was run on the test problem on a Pentium III 1 GHz personal computer. The computational results show: (1) The IBTS system produced a better solution using 107 buses and 164 duties. The average relative percentage deviation (RPD) over the manual schedules is 4.5% in terms of total number of buses and 9.9% in terms of total number of duties. (The rates of saving in the other test problems are greater or similar in terms of the number of buses.) (2) The computational time was very short. The elapsed time for generating the bus schedule was about 2 min, while within 1 minute the driver schedule was formed. A duty roster was built within several seconds. (3) The schedules generated have met all the requirements, especially the particular ones of BJBUS, and were displayed in various formats in order for the schedulers to understand and implement them. This is very important to achieve acceptance of the new scheduling and management mode by operators and schedulers, and vital for the system to reach the level of real application under a unified operation mode. (4) Each schedule is associated with a set of statistical data, some of which is related to the wage cost of drivers. Hence, it can be helpful to justify more equitably the work of drivers than the current method, in which much data is produced based on an average of the work of the drivers on the same bus. (5) Using the IBTS system, a scheduler can produce quickly the whole set of schedules within the scheduling area. However, the current situation of BJBUS is that each scheduler can only work for one, or sometimes two lines, because the manual compilation of schedules is extremely difficult and time-consuming. The paper has presented the research on solving the practical bus transit-scheduling problem of BJBUS, during which an integrated bus transit system has been developed. It is a case study relevant to developing countries. In contrast to the applications in developed countries or to the theoretical research on algorithms, this research has its important features: it focuses on the enhancement of the management mode and scheduling means; it assists BJBUS with the change from the line-by-line mode to the unified operation mode; it implements in BJBUS the scheduling of buses and drivers using computers instead of manually. Because of the long history of the current mode, it is difficult to fulfil all the goals of the new mode in one step. Therefore, the scheduling approaches developed for BJBUS have to meet some transitional requirements, such as a driver being restricted to a certain bus, a meal being taken in the customary lunch or dinner time. On all counts, the bus operators in developing countries such as China prefer to obtain benefits from the revolution in the way of scheduling rather than refine the algorithms for ''optimal'' solutions as done in developed countries. In the process of this research, we have adopted various ideas, methods and techniques applied successfully in developed countries. However, China, as a developing country, is in a different development stage. It becomes inevitable, in adapting existing techniques to the particular problems, that the bus operators will encounter particular difficulties. The innovative work presented in this paper, such as integrated scheduling of buses and drivers with cross references to each other, has enriched the research on bus transit scheduling, but the most significant achievements are as follows: BJBUS is able to apply the advanced scheduling technique and the unified operation mode with the aid of the integrated bus transit scheduling system; furthermore, its management and economic interests benefit enormously. Although this research has been conducted for BJBUS, the research fruits and practical experiences would be of great benefit to the other operators in China and some other developing countries. Bus service frequency optimal model Managing large fixed costs in vehicle routing and crew scheduling problems solved by column generation Staff scheduling and rostering: A review of applications, methods and models An improved ILP system for driver scheduling Experiences with a flexible driver scheduler Tabu Search Computer-aided Systems in Public Transport Object oriented bus vehicle scheduling -the BOOST system Real-time scheduling on a transit bus route Journal compilation r 2009 International Federation of Operational Research Societies Real-time dispatching of public transit operations with and without bus location information Computer solutions of the travelling salesman problem Regional bus operation bi-level programming model integrating timetabling and vehicle scheduling Results obtained with CREW-Opt, a column generation method for transit crew scheduling Tabu Search for Bus and Train Driver Scheduling With Time Windows Two Neighbourhood Search Approaches: 2-opt Heuristics and Tabu Search for Bus and Train Driver Scheduling A constructive approach to bus and train driver scheduling Tabu search for driver scheduling Scheduling bus transit resources using computers Initial research on applying the multi-routes model for bus operations in China Selection of information systems for bus companies VAMPIRES AND TASC: Two successfully applied bus scheduling programs A bus crew scheduling system using set covering formulation Bus scheduling: An interactive computer method Installing an urban transport scheduling system We would like to thank Mr Jianguo Li, the vice-director of the Beijing Communication Committee, for his promoting this project and choosing us to conduct this research. We are also grateful to Mr Lijie Zhou and his colleagues in the information centre of BJBUS for their hard work in the organization of the entire project. We would also like to thank Mr Qingshan Yang, the vice secretary-general of the China Urban Public Transport Association, for his recommendation of us to BJBUS. Finally, our thanks go to the colleagues in the sixth subcompany of BJBUS for providing us with various data and information.We also thank Emeritus Professor Anthony Wren of the University of Leeds, in whose research group one of the authors previously worked, and who has advised on the final implementation of this paper. This work was supported by National Natural Science Foundation of China (70671045); by the National Key Technologies R&D Program for the 10th Five-year Plan Project (2002BA404A18B); by the Key Project of Chinese Ministry of Education (205103) and SRF for ROCS.