Planning Routes and Shifts Driving for a Small Business of Road Passenger Transport

Brazilian Journal of Operations & Production Management 13 (2016), pp 400-407 PLANNING ROUTES AND SHIFTS DRIVING FOR A SMALL BUSINESS OF ROAD PASSENGER TRANSPORT Pablo Aparicio Ruiza; Jesús Muñuzuri Sanza; Alejandro Escudero Santanaa; Rafael Grosso de la Vegaa a Sevilla University (US) - Sevilla, Spain The presented work is done for a company that currently operates twenty lines of passenger transport in the metropolitan area of Seville. The planning of these was originally carried out manually, building routes and shifts in an Excel spreadsheet. In order to automate the process as much as possible. It was designed and implemented by a scheduling algorithm that would be much simple than other algorithms in the literature and that, in addition, would make it possible to allow mixing vehicles and drivers between the lines. The objective was, firstly, to employ the minimum number of drivers; then, it was to try to use the least possible number of vehicles; finally, the study tried to reduce as much as possible the amount of split shifts. In addition, restrictions on the design of routes and shifts were added. At all times the service frequencies remained above the set limit. To allow the possibility of unexpected demand peaks, was established in the capacity of each route some slack. Keywords: planning routes; shifts driving; bus; passenger transport; algorithm ABSTRACT ABEPRO DOI: 10.14488/BJOPM.2016.v13.n3.a16 Brazilian Journal of Operations & Production Management Volume 13, Número 3, 2016, pp. 400-407 DOI: 10.14488/BJOPM.2016.v13.n3.a16 401 1. INTRODUCTION Planning passengers’ bus services is a complex optimization problem, because the conditions and restrictions that often occurring in them are usually specific to each case. This necessitates the use of simplified or partial approaches to reach good enough designs. Thus, the global problem of planning a bus service is broken down into basic modules, in a total of five, according to the original description of (Ceder et Wilson, 1986), shown in Table 1. Many scientific papers focus on each of the steps shown in Table 1, sometimes considering several stages at once. Ceder et Wilson propose a two-step algorithmic procedure to establish the network design and service frequencies, whereas (Guihaire et Hao, 2008) carried out an extensive collection of articles focusing on the planning of schedules in the network. Finally, regarding planning on driving schedules, (Ernst, 2004) collected studies about heuristic approaches (e.g., Martello et Toth, 1986), column generation methods (Desrochers et Soumis, 1989) metaheuristics (Wren et Wren, 1995), or even multi-objective approaches (Lourenço et al., 2001). This paper focuses on the last three stages of the planning process associated with the establishment of schedules of buses and shifts driving. These problems, which are based on prior knowledge of the network and the minimum frequency step and the demand divided time slots and all data cost and time constraints can be addressed in multiple ways. The most advanced approach is to solve the three problems together (Ball et al., 1983; Rodrigues et al., 2006; Mesquita et Paias, 2008). However, this approach has the disadvantage that it requires solving a linear optimization problem at some point in the execution of the algorithm. An approach is taken in this case because it is a small company with few lines, is a heuristic approach that seeks a reasonably good solution in a time interval reduced to provide guidance to the company in planning schedules and shifts driving. Thus, we decouple both problems, using the result of the first as input for solving the second. The goal of the algorithm is: first, it expects to employ as few conductors as possible; then, will seek to use the least possible number of vehicles; eventually pursue reduce as much as possible the amount of split shifts that are required. Table 1 Bus services planning process. Inputs required Planning activity Outputs Demand data Network Design Route changes Supply data New routes Route performance indices Operating strategies Budget or subsidy available Establishment frequency Service frequencies Buses available Service policies Demand for time slots Timetable development Trip departure time Trip arrival time Start and end time of service Travel time Deadhead times Bus schedules Bus schedules Break or rest periods Time restrictions Structure of operating costs Driver work rules Drivers scheduling Driver shifts schedules Staff costs or structure cost Source: Ceder et Wilson (1986). 2. PROBLEM DEFINITION From the files of the company, it was known the following information for each of the lines: the round trip time (rt), the number of daily services (ns), the start and end of the journey, the first hour (hf) and last hour (hl) of departure, the demand for each slot in each line (D). If a line has several variants (i), the number of daily services (nsi) and the round trip time (rti). As is reflected in Table 1, the complete planning, scheduling and shifts driving also required information on the costs involved and the time constraints applicable to each line. This information is detailed below: • Structure cost. The cost applicable to the service depends on the type of activity, basically, drivers can perform three types of functions: - Time of presence (TP): It is the time spend next to the vehicle without driving. There is an obligatory time of presence of 10 minutes at the beginning of each day to prepare the vehicle, and a similar end for the liquidation of the cash box. - Time driver-no-receiver (TDNR): The driver is driving the vehicle without carrying passengers. Such times are for the routes from the garage to the header line and vice versa, or fictitious routes which are placed on service planning. - Time driver-receiver (TDR): The driver is driving the vehicle carrying passengers. It corresponds to the regular bus services. The time costs associated with these three types of functions have the next relation: cost per hour (TDR) > cost per hour (TDNR) > cost per hour (TP) • Temporal restrictions. There is a restriction on driving times and rest periods of drivers. This restriction is described by the following four principles: Brazilian Journal of Operations & Production Management Volume 13, Número 3, 2016, pp. 400-407 DOI: 10.14488/BJOPM.2016.v13.n3.a16 402 - Driving shift: There are two types of shifts: full and split shifts (morning, evening). - Length shift: normal shifts are 8 hours, and maximum an extra additional hour a day. - Start and end of shifts: morning shifts often end before 15h, and often start later than 12h. - Rest periods: Maximum period of continuous driving is 6h. If the shift is longer, it is obligatory to introduce a break period of at least 15 minutes (OBP, Obligatory Break Period), if it is higher, is recorded at the present time. However, in split shifts that break is at least 1 hour, but time will not be considered presence if the break is longer. In Figure 2, different shift configuration structures are presented. Figure 2. Temporal Restriction. In blue colour, it is shown the driving time or the Time Driver-Receiver, in orange the Obligatory Break Period, this period is always 15 minutes in the middle of the shifts. Finally, in yellow is shown the Time of Presence (TP), it is the time spent next to the vehicle without driving, and when it is more than an hour, the system builds a split shift. In this figure is not shown the obligatory time presence (OTP) of 10 minutes at the beginning of each day to prepare the vehicle, and a similar end for the liquidation of the cash box. 3. THE PROPOSED SOLUTION The proposed solution is presented in Figure 3. The solution consists of an initial analysis and a heuristic calculation. First is defined inputs (number of buses, hours, etc.). Then we work in an initial analysis, and are obtained the initial outputs, the necessary data for this heuristic, that define the bus schedule planning and the drivers’ shifts planning. Finally, it is obtained the vehicle, shifts and schedules. 3.1. Initialanalysis The initial calculation, which is initially determined, the number of buses to be used in each line and a first approximation to the schedules of them, the lines of the company are classified into different groups, and this consists of several steps: • The calculation of the number of buses needed for each line, estimated from: (4.1) Also, is calculated: the travel time in one direction (ttd = rt / 2), hours of service (hs = hl – hf + ttd) or the number of buses needed (nb = ns · rt / hs). • Grouping and closing of the lines. If the decimal part of the nb is greater than 0.85 (modifiable parameter) will be considered closed lines. For the remaining lines, to identify those lines that are coincident, that is, they share the same terminal point in Seville. Then: - All possible groups of matched lines are tested, in order to maximize the number of closed groups. Figure 3. The planning algorithm. Brazilian Journal of Operations & Production Management Volume 13, Número 3, 2016, pp. 400-407 DOI: 10.14488/BJOPM.2016.v13.n3.a16 403 - Afterwards, groups of lines that are mismatched and not closed are tested, to building all possible closed groups. Accordingly, four cases are defined: - Type A: Individual lines closed with one vehicle - Type B: Lines individual closed with two or more vehicles - Type C: Groups with two or more vehicles - Type D: Lines with various routes with different times. These lines are treated as belonging to type C. Thus, the total number of buses is obtained, rounded to the next whole number needed for each line and closed group buses. 3.2 Heuristic After preliminary analysis, the heuristic calculation performs the final planning, the heuristic is divided into two modules: the bus schedules and the driver shifts planning. 3.2.1 Bus schedules The planning module of bus schedules, is based on a historical demand of each line and travel times according to the time of day. Route designs are done by determining the number of vehicles required and departure times. To understand the heuristic, an operation of a bus, with four services (two departures and two arrivals, between two terminals) is shown in Figure 4. For each service, it has shown time in each terminal, departure time in one terminal and arrival time in the other, in the line, the slope defines speed and distance between both terminals. Figure 4. Description of the operation of a bus line with two services. The operation of the heuristic for determining bus schedules depend on the type of line, according to the definition in the preliminary analysis. The procedure for each type of possible lines are described: • Type A: lines that only need a single vehicle for all services, the process is as follows: - The only vehicle defines their services beginning at the start time of service (hf). As in Figure 2, outward journeys are defined at (hf + rt, hf + 2 rt, hf + 3 rt,...) and return journeys at (hf + ts, hf + rt + ts, hf + 2 rt + ts,…) to meet the demand or minimum service associated with each slot time. When all services in the time slot have been performed, the bus is waiting for the next service. The process continues in this way until the end of the day (hl). • Type B: lines with two or more vehicles for all services, the process is as follows: - Times are determined for the first vehicle in the same way as in the type A (Bus 1 in Figure 5). - For the second vehicle, the backward process is performed. Defined the routes backwards from the time of the last arrival (hl - rt, hl - 2 rt, hl - 3 rt,…) and from the opposite terminal (hl - ts, hl - rt - ts, hl - 2 rt - ts,…), until the start of the day. (Bus 2 in Figure 5). Figure 5. Type B. - If it is necessary a third vehicle, there is reintroduced forward, like the first. (Bus 3 in Figure 5). The departure time of the first service will be the midpoint between the first and the second vehicle departure time (hm). From there, we proceed identifying services until the end of the day. - The process continues in this way until the number of vehicles needed is completed. • Type C: The situation is more complex when are line groups with two or more vehicles, in which is known amount of vehicles, and are shared the services assigned to them all. In such lines, the heuristic operates in a greedy way, following a similar procedure to the previous cases. This preliminary estimation about time schedules is built on the classification of lines made above. Thus: - Allocate to each group enough buses as indicated by the integer part of bn. - Allocate these bus schedules following the same pattern than in type A and B. - For other buses: if it is only a single, is considered shared between all lines of the group. If they are m Brazilian Journal of Operations & Production Management Volume 13, Número 3, 2016, pp. 400-407 DOI: 10.14488/BJOPM.2016.v13.n3.a16 404 buses to be distributed in n lines of the group (with m<n), take the m lines with decimal part upper to bn, and combine with remaining nm lines trying than the sum of lines in all combinations is as small as possible. - If the bus has to serve p lines, in each line is proceeded with the calculation D/bn, for the morning and afternoon. These bus travel is sequentially allocated to bus lines based on that calculation. 3.2.2. The driver shifts planning Driving shifts are constructed taking into account the break times, lunch times if there are split shifts, time constraints driving and the associated costs. It allows multi-shift worker allocation along the lines, that allowing a single worker is allocated to different lines on the same day, depending on the needs of the service and trying to optimize break times. For a line or group of lines with bn necessary vehicles and dn drivers needed. Two possible cases may occur: First, if n = 1, all the time will be assigned to a single conductor. Second, if n>1, further fulfilling that n = 2 · bn, we will focus on this case. Finally, if n> 1 and n> 2 · bn. In the second case, each vehicle was initially allocated two drivers, one at the opening and one at the end of the day. The number of services tn that are assigned at the beginning (end) of the journey. That number can only be such that tn · rt is between 35% and 65% of the number of daily driving hours. This will give x total possible values of v. After (before) to make that number of trips, the driver can enjoy a short break (less than 1 hour) or long break (not less than 1 hour), and after (before) this break, the driver may rejoin to either bn vehicles of the line, performing all trips that still have to do the bus. To show the complexity of the problem, for example, a line or group of lines with 4 buses and 8 drivers who could make 2 or 3 trips (two possibilities) before break, the number of possibilities before the break will be: VR (2,8) = 28 = 256, and the breaks can be short and long we will have 65,536 possibilities (256 · 256). After the break, we should combine each driver with each of the possibilities of each bus. Thus, the four drivers who started the day could end their turn in each of the four buses, resulting V (4,4) = 24 variants. Likewise, each conductor used to close the bus line, can start your day in each of the four buses, taking another 24 possibilities, and giving a total of 37,748,736 variants (65,536 · 24 · 24). This number would be increased by a factor that depends on the number of possible variations caused by the long or short break in each case. In the evaluation of each alternative, should be penalized with plb hours long break over an hour, with px hours extra, and with psb hours of short break over 15 minutes, where: plb < px < psb. The goal is to minimize the total cost. The procedure for allocating drivers to the services is carried out by greedy heuristic. For each group, the journey of one of the nc drivers needed is allocated to one of the initial services in a line. At the end of that service, is assigned the new service that is closer to start of the whole group (which will usually be in the same line, however, this is not necessarily the case). This is the process until you have covered 50% of their workday. If there is a sufficient gap between services for a short break, is assigned and the driver continues to allocate services to the end of their journey. If there is no space, the allocation of the bus drivers stop. The following drivers are also assigned to services, but this time from back to front, assigning the last line services, until the moment of break. We proceed in the same way with all nc drivers until some of them are completed, and others have covered only up to their break, backwards or forwards. Then are allocated the breaks to drivers, initially all short, to try to maximize the number of consecutive shifts and assigning services continues until completely covered. If the service earlier than can be assigned to a driver has an excessively large slack after the short break, this is replaced by a long break and the allocation is continued. 4. CASE STUDY The problem consists in the planning of a company that operates twenty lines in the metropolitan area of Seville. The lines have radial character, operating from a terminal in the city of Seville and another located in the metropolitan area. Three different terminals in Seville, with approximately equal numbers in each line. The lines need two planning processes per year (winter and summer). At the beginning of our work, this process was done manually for each of the lines separately, using a spreadsheet. Automating the process, attached to the possibility of combining lines between vehicles and drivers that have the same terminal. Thus, this work presents great opportunities for increased efficiency. To consider opening up a description of scenarios, when this project was applied in a real company, this should be done in a way to allow anonymity, for this reason it is applied only in a small a fictitious example that is shown in this section. A case study describes typical administrative issues or problems confronting a manager in an organization. It is usually presented from the standpoint of the decision maker involved. Brazilian Journal of Operations & Production Management Volume 13, Número 3, 2016, pp. 400-407 DOI: 10.14488/BJOPM.2016.v13.n3.a16 405 Figure 1. Metropolitan area of Seville Table 2. Minimum services and demand for a bus line. Range Start time End time Demand Terminal 1 (T1) Demand Terminal 2 (T2) Min. Service T1 Average Time T1→T2 Average Time T2→T1 Min. Service T2 1 06:00 08:00 25 0 0 00:30 00:30 1 2 08:00 10:00 0 1 1 00:30 00:30 1 3 10:00 12:00 45 34 0 00:30 00:30 0 4 12:00 14:00 65 35 0 00:30 00:30 0 5 14:00 16:00 45 76 0 00:30 00:30 0 6 16:00 18:00 0 1 1 00:30 00:30 0 718:00 20:00 0 0 1 00:30 00:30 0 Table 3. Bus schedules (with only one bus). Start End From Fictitious Range transshipment terminal 1 06:00 06:30 T1 no 1 T1 2 06:30 07:00 T2 no 1 T1 3 08:00 08:30 T1 no 2 T1 4 08:30 09:00 T2 no 2 T1 5 10:00 10:30 T1 no 3 T1 6 10:30 11:00 T2 no 3 T1 712:00 12:30 T1 no 4 T1 8 12:30 13:00 T2 no 4 T1 9 13:00 13:30 T1 no 4 T1 10 14:00 14:30 T2 no 5 T1 11 14:30 15:00 T1 no 5 T1 12 15:00 15:30 T2 no 5 T1 13 16:00 16:30 T1 no 6 T1 14 16:30 17:00 T2 no 6 T1 15 18:00 18:30 T1 no 7T1 16 18:30 19:00 T2 yes 7T1 Brazilian Journal of Operations & Production Management Volume 13, Número 3, 2016, pp. 400-407 DOI: 10.14488/BJOPM.2016.v13.n3.a16 406 In this case the service is planned for an example of bus line. The definition is performed in a theoretically defined situation with conditions that depend on the characteristics of the day of the year (weekday, weekend, holiday, vacation, etc.). The table 2 show the number of minimum service guaranteed and the demand, when the first output is at 6.00 and the last arrival is at 19.00. With this demand and minimum services, following the methodology described above, the departure times of buses that are needed are constructed, see Table 3. The shift in a company depends on the conditions: • In the example 1, if the administrative time is 15 minutes, the break period should be between the third and the fifth hour, the longitude of this break is 15 minutes, and the limit in the shift period is nine hours and the maximum time to build in a split shift is 45 minutes, the system builds this two shift that appears in Table 4, where one is a broken shift with 8.75 hours, six as a driver, 2.5 hours as a presence, and 0.25 hours as an administrative time. And the system builds a short shift (because is a small example) with 3.25 hours: 1.5 as a driver, 0.5 hours of preceptor driver, 1 hour of presence time and 15 minutes of administrative time. • In the example 2, if the administrative time is 24 minutes, the break period should be between the second and the fourth hour, the longitude of this break is 27 minutes, and the limit in the shift period is eight hours and the maximum time to build in a split shift is 78 minutes, the system builds this two shift that appear in Table 4, where one is a complete shift with 7.4 hours, 4 hours of driving, 2.55 hours of presence time, and 0.4 hours of administrative time. And the system builds a second complete shift with 6.4 hours: 3.5 as a driver, 0.5 hours of Table 4. The driver shifts planning. Example 1 Example 2 Shift Start End Type From Shift Start End Type From 0 05:45:00 06:00:00 OTP - 0 05:36:00 06:00:00 OTP - 0 06:00:00 06:30:00 TDR T1 0 06:00:00 06:30:00 TDR T1 0 06:30:00 07:00:00 TDR T2 0 06:30:00 07:00:00 TDR T2 007:00:00 08:00:01 TP T1 0 07:00:00 08:00:01 TP - 0 08:00:01 08:30:01 TDR T1 0 08:00:01 08:30:01 TDR T1 0 08:30:01 09:00:01 TDR T2 0 08:30:01 09:00:01 TDR T2 0 09:00:01 10:00:01 SPLIT - 0 09:00:01 09:27:01 OBP - 0 10:00:01 10:30:01 TDR T1 0 09:27:01 10:00:01 TP - 0 10:30:01 11:00:01 TDR T2 0 10:00:01 10:30:01 TDR T1 0 11:00:01 12:00:01 TP - 0 10:30:01 11:00:01 TDR T2 0 12:00:01 12:30:01 TDR T1 0 11:00:01 12:00:01 TP - 0 12:30:01 13:00:01 TDR T2 0 12:00:01 12:30:01 TDR T1 0 13:00:01 13:30:01 TDR T1 0 12:30:01 13:00:01 TDR T2 0 13:30:01 14:00:01 TP - 1 13:00:01 13:30:01 TDR T1 0 14:00:01 14:30:01 TDR T2 1 13:30:01 14:00:01 TP - 0 14:30:01 15:00:01 TDR T1 1 14:00:01 14:30:01 TDR T2 0 15:00:01 15:30:01 TDR T2 1 14:30:01 15:00:01 TDR T1 1 16:00:01 16:30:01 TDR T1 1 15:00:01 15:30:01 TDR T2 1 16:30:01 17:00:01 TDR T2 1 15:30:01 15:57:01 OBP - 117:00:01 18:00:01 TP - 1 15:57:01 16:00:01 TP - 1 18:00:01 18:30:01 TDR T1 1 16:00:01 16:30:01 TDR T1 1 18:30:01 19:00:01 TDNR T2 1 16:30:01 17:00:01 TDR T2 1 19:00:01 19:15:01 OTP - 1 17:00:01 18:00:01 TP - 1 18:00:01 18:30:01 TDR T1 1 18:30:01 19:00:01 TDNR T2 1 19:00:01 19:24:01 OTP - Brazilian Journal of Operations & Production Management Volume 13, Número 3, 2016, pp. 400-407 DOI: 10.14488/BJOPM.2016.v13.n3.a16 407 preceptor driver, 1.55 hours of presence time and 0.4 hours of administrative time. In previous results is shown as the tool you can reach different types of shift workers: complete shift, split shift or partial shift, depending on the characteristics of the problem. This is a small example, but in the real example the system operates twenty lines of passenger transport in the metropolitan area of Seville. The line has a radial character with 3 terminals with equal number of lines in the city. In general, it uses 2 planning process per year, one in the winter and one in the summer, this planning have different type of days, weekend, weekdays, holidays and other special days. The planning of these was originally carried out manually, building routes and shifts in an Excel spreadsheet, the mixing vehicles and drivers between different lines is allowed. The next section explains the result and conclusions. 5. RESULTS AND CONCLUSIONS In this paper, we have presented a simple algorithm to schedule work shifts from driving in a metropolitan company with a small size of passenger transport and bus services. While it does not guarantee the optimal solution, it does allow the company to achieve a good solution in a small space of time, avoiding having to resort to commercial optimization software packages or modelled complexes. The application of this methodology to the Seville Company under study allowed to achieve a reduction of 12.5% in the number of buses required to meet all the daily services, 8% in the number of drivers and 7.5% in the total cost of operation. It is therefore a tool effectively, susceptible as well as being applicable in any company with similar characteristics, in which the manual planning and lack of validation of procedures tend to hide great opportunities for improving efficiency and reducing costs. REFERENCES Ball, M., Bodin, L. and Dial, R. (1983), “A matching based heuristic for scheduling mass transit crews and vehicles”. Transportation Science, Vol. 17, No. 1, pp. 4-31. Ceder, A. and Wilson, N. (1986), “Bus network design”. Transportation Research B, Vol. 20B, No. 4, pp. 331-344. Desrochers, M. and Soumis, F. (1989), “A Column Generation Approach to the Urban Transit Crew Scheduling Problem”. Transportation Science, Vol. 23, No. 1, pp. 1-13. Guihaire, V., Hao, J. (2008), “Transit network design and scheduling: a global review”. Transportation Research A, Vol. 42, pp. 1251-1273. Lourenço, H., Paixao, J. and Portugal, R. (2001), “Multiobjective metaheuristics for the bus–driver scheduling problem”. Transportation Science, Vol. 35, No. 3, pp. 331– 341. Martello, S. and Toth P. (1986), “A heuristic approach to the bus driver scheduling problem”. European Journal of Operational Research, Vol. 24, pp. 106-117. Mesquita, M. and Paias, A. (2008), “Set partitioning/ covering-based approaches for the integrated vehicle and crew scheduling problem”. Computers and Operations Research, Vol. 35, pp. 1562 – 1575. Rodrigues, M., de Souza, C. and Moura, A. (2006), “Vehicle and crew scheduling for urban bus lines”. European Journal of Operational Research, Vol. 170, pp. 844–862. Wren, A. and Wren, D. (1995), “A genetic algorithm for public transport driver scheduling”. Computers and Operations Research, Vol. 22, No. 1, pp. 101-110.