Correo Electrónico
DNINFOA - SIA
Bibliotecas
Convocatorias
Identidad U.N.
Publicado
Cooperation strategies featuring optimization in the school transportation system in Bogota
Estrategias de cooperación en el sistema de transporte de estudiantes en Bogotá usando optimización
DOI:
https://doi.org/10.15446/dyna.v84n202.65391Palabras clave:
school bus routing, routing and scheduling, heuristics, traffic congestion, mathematical models (en)ruteo de buses escolares, ruteo y secuenciación, heurísticas, congestión vehicular, modelos matemáticos (es)
Descargas
Recibido: 31 de mayo de 2017; Revisión recibida: 18 de julio de 2017; Aceptado: 2 de agosto de 2017
Abstract
The transport of students presents important challenges in the case of the city of Bogota, where an important cluster of schools is located in one zone, but there is only one road connecting these schools to residential zones. Thus, traffic congestion is high, generating long travel times for students, high operational costs, and mobility problems. This paper studies the impacts of a cooperative strategy between logistics operators using a mixed integer programming mathematical model, to find the optimal design of school routes on a network with the topology that describes the aforementioned road system. Two strategies are compared: a mixed loads strategy, where students from different schools share buses; and a single load strategy, where students from different schools cannot share buses. The objective is to minimize the total operational costs while satisfying the schools’ time windows. Comparative results of the two models using exact and heuristic approaches are presented.
Keywords:
school bus routing, routing and scheduling, heuristics, traffic congestion, mathematical models..Resumen
El transporte de estudiantes tiene desafíos importantes en el caso de la ciudad de Bogotá, donde un grupo de escuelas se encuentra en una zona, pero sólo hay una carretera que las conecta con zonas residenciales. Por lo tanto, la congestión del tráfico es alta, generando largos tiempos de viaje, altos costos de operación y problemas de movilidad. Se estudia el impacto de una estrategia cooperativa entre operadores logísticos a través de modelos de programación de entera mixta, para encontrar el diseño óptimo de rutas escolares en una red con la topología que describe el mencionado sistema vial. Se comparan dos estrategias: Cargas mixtas y carga única, donde los estudiantes de diferentes escuelas comparten o no los autobuses disponibles. El objetivo es minimizar los costos totales de operación respetando las ventanas de tiempo de las escuelas. Se presentan los resultados comparativos de los modelos usando enfoques exactos y heurísticos.
Palabras clave:
ruteo de buses escolares, ruteo y secuenciación, heurísticas, congestión vehicular, modelos matemáticos..1. Introduction
Cities have the challenge of defining a sustainable urban mobility model to improve the population’s quality of life [1]. High traffic congestion levels tend to increase despite infrastructure investments as a result of the rise in the number of vehicles [2]. This congestion generates low productivity, and pollution.
School buses are part of transportation systems and contribute to traffic congestion, since these buses transport students during rush hours. Thus, an interest to study the school bus routing problem (SBRP) arises. The problem is first studied by [3] who propose to design a schedule for a fleet of school vehicles to pick up students at different geographic points and deliver them to their designated schools, while respecting the maximum capacity of students in a bus, the maximum time travel, and the time window that students have to arrive to class. Different variants have been studied, such as considering a heterogeneous fleet of buses; multiple school systems in rural or urban zones; different planning horizons (morning, afternoon, or both); or special-education students (e.g., students with disabilities). Different objectives are sought, such as: the reduction of the number of buses; travel times; and the minimization of the distance that students have to walk to bus pick-up points (see [4]).
In the case of Bogota, Colombia, and the highway called Autopista Norte, a high level of traffic is found on the Autopista Norte during rush hours, since this is the only road that links the northern school zone to residential zones (see Fig. 1). The problem is the increased travel times that students spend on the bus. Further, according to the INRIX Global Traffic Scorecard, Bogota was the fifth-worst city in the world in terms of traffic severity in 2016.
This problem has been analyzed by the district government. In 2017, the District Department of Mobility [5] restricted a lane to be used exclusively by school buses in rush hours. Results show that average travel times on the highway have been reduced from 43 to 23 minutes. Despite these measures, traffic congestion in the city remains a problem.
Figure 1: Map of the north of Bogota - School zone.
Case studies on this issue have been presented. For instance, in Beijing, congestion and pollution consequences of driving-to-school trips were analyzed by [6]. For Dublin, a study of sustainable school commuting was done by [7] and in US the cost of school transportation was analyzed [8].
This paper studies the impact of collaborative strategies for student transportation in the north of the city of Bogota, through the use of optimization models. The transportation system is analyzed considering independent routes. This strategy is known as “Single load” [9]; it consists of designing routes to pick up students who attend a single school. The shared routes strategy; known as “Mixed load”, is also analyzed, where students from different schools share buses [10].
The mixed load strategy offers better coordination in highway sequencing, since a collaborative planning of routes for different schools is feasible. The single load strategy presents some issues: entry to the highway can only be coordinated for buses going to the same school, but buses from different schools will get on to the highway in an uncoordinated way. The collaborative strategy has potential benefits such as shorter routes (less travel time); less operating costs (less buses); greener operation (less fuel consumption); and reduced traffic congestion.
The main contribution of the paper is the analysis of the benefits and implications of both strategies, and the conclusions as to the most efficient route design for the school transportation system in the city. A routing and scheduling model is presented to perform this analysis. This paper is organized as follows: section 2 presents a literature review; section 3 presents the proposed mathematical formulation; section 4 presents a proposed heuristic approach; section 5 shows computational results; and section 6 presents the conclusions and future research.
2. State of the art
This section presents a review of the literature related to the school bus routing problem. Notions referring to vehicle scheduling are presented to contextualize the school bus routing problem. The objective of SBRP is to plan an efficient schedule for a fleet of school buses to pick up students at different geographic points and deliver them to the designated school [4]. The SBRP is a particular application of the vehicle routing problem (VRP). In the latter problem, several clients are visited by a set of vehicles, which leave a depot, visit the clients, and return to the depot after completing the route [11]. One variant of the classical VRP, that is similar to the SBRP, as presented in this research, is the multi-depot open vehicle routing problem (MDOVRP), which is studied by [12]. The MDOVRP considers the vehicles to start their journeys from multiple depots to deliver products to clients. When vehicles complete the journey, it is not necessary to return to the depot where the route started [13]. Compared to SBRP, depots correspond to the points where buses start their routes; clients that have to be visited correspond to students who have to be included on different routes; and the designated school in which buses complete the route correspond to the last client in the route. In some European and North American countries, students are collected at fixed points (often clusters of houses or neighborhoods). Nonetheless, in Bogota, students must be picked up right outside their houses.
The SBRP is known to be NP-Hard [14]. A mathematical model to optimize school bus service of two schools is proposed in [15]; the model is solved by an exact method. Recently, models in the literature have aimed to minimize the transportation costs associated with travel time. A rural school district SBRP using heuristics is proposed in [16]. Similarly, [17] propose an ant colony optimization algorithm. Mathematical models to determine the routes of each bus, and the stations where students have to walk to be picked up is developed in [18]. A particle swarm optimization to solve the SBRP is proposed in [19].
At the national level, the SBRP has already been applied to a private school in the city of Bogota by [20]. They modeled the system as a capacitated vehicle routing problem (CVRP) and solved it in two phases: the first stage assigns students to buses, and the second determine the vehicle routes via an ant colony optimization. The total distance covered by buses is reduced by 8,3% in the morning. However, this research does not take traffic congestion into account.
Further, the mixed load strategy for the SBRP has been studied by [21], who developed an algorithm to improve the results obtained in [10]. The implementation of the mixed load to a single load strategy is compared in [22]. In contrast to previous research, we will include the bus scheduling decisions at the node that represents the path along the highway that connects schools to students’ houses.
Additionally, [23] studied the vehicle routing and scheduling in a cross-docking system. In this research, school buses are scheduled at the node that represents the highway, an analogy of the cross-docking system for a single bus dock is implemented here, where the vehicle entry is scheduled while it is unloaded and delivered from the station [24].
The conclusion of this review is that there is no-
to the best of our knowledge-paper that simultaneously combines the routing and scheduling decisions of buses in a school routing system of single and mixed load strategies where vehicles have to tackle heavy traffic congestion on highways to transport students to their designated schools. Moreover, the impact of each of the two strategies for school route transportation will be analyzed for the studied case.
3. Mathematical formulations
In this section, the mathematical formulations based on mixed integer programming (MIP) for the single load and mixed load strategies are presented. We assume that students have no special requirements other than being picked up at their homes. The fleet of buses is homogeneous and the transfer of students between buses is not allowed. Thus, the bus that picks up each student is the same bus that delivers the student to his/her school.
3.1. Mathematical formulation for school bus routing and scheduling problem - single load strategy
Let the problem be mathematically defined on a directed graph G={𝑣,𝑒}. The set 𝑣: 𝜃 𝑘 ∪ 𝑗 ∪ 𝑎 ∪ 𝑚 , where 𝜃 𝑘 <𝑗<𝑎<𝑚. That is, the set of nodes 𝑣 is composed by a set 𝜃 𝑘 of bases where buses are located at the beginning of the journey, the set 𝑗 represents the students to pick up. The total number of students in the system is denoted by the constant 𝐶. The vertex 𝑎 represents the Autopista Norte highway, and the vertex 𝑚 represents the destination school. We assume that set 𝑘 denotes the set of available buses, each with a maximum capacity of 𝑄 students, and a fixed cost of used of 𝐶𝑓. Let set 𝑣1 be a copy of set 𝑣; set 𝑗1 be a copy of set 𝑗; and set 𝑘1 a copy of set 𝑘.
Set 𝑗 is associated with a parameter 𝑑 𝑗 to indicate the number of students to collect at each node and the service time 𝑠 𝑗 at node 𝑗. The school is associated with parameters 𝑤 1 , 𝑤 2 , indicating the earliest and latest times, respectively, that the students are expected to arrive at school.
The set of edges 𝑒 in the graph represent the roads in the city of Bogota. Using a geographical information system, the parameter 𝑡𝑖 (𝑣,𝑣1) representing the travel time from node 𝑣 to node 𝑣1 in set 𝑉 is computed. The variable cost of the bus operation, denoted as 𝐶𝑣 (𝑣,𝑣1) ∀ 𝑣,𝑣1 , is calculated with the expression: (𝐷 (𝑣,𝑣1) ∗𝐶𝑢𝑑), where 𝐷 (𝑣,𝑣1) refers to the distance between the nodes 𝑣 and 𝑣1, a parameter that is calculated with the following expression (𝑡𝑖 (𝑣,𝑣1) ∗𝑉), where 𝑉 is a constant that represents average bus speed. Additionally, the parameter 𝐶𝑢𝑑 is a constant that refers to the cost per unit of distance. Further, let 𝑅 denote the desired minimum time difference between two consecutive bus arrivals to the highway. The bigger the parameter 𝑅, the less likely it is that buses will create a bunching effect.
The decision variables in this model are the following: Let 𝑋 𝑣,𝑣1,𝑘 be equal to 1 if the bus 𝑘 uses edge 𝑣,𝑣1 , otherwise it is equal to 0. Let 𝑌 𝑘,𝑘1 be 1 if bus 𝑘 precedes bus 𝑘1 in the sequence to pass along the highway, otherwise let it be 0. Let 𝐿 𝑣,𝑘 be the cumulative number of students in bus 𝑘 after visiting node 𝑣∈𝑉. Let 𝑇1 𝑣,𝑘 be the arrival time of bus 𝑘 at node 𝑣, only defined at nodes in the set 𝑘 and 𝑗 (points where the routes start and the children houses.) Let 𝑇2 𝑎,𝑘 be the arrival time of bus 𝑘 at node 𝑎. Let 𝑇3 𝑎,𝑘 be the leaving time of bus 𝑘 at node 𝑎. Finally, let 𝑇4 𝑚,𝑘 be the arrival time of bus 𝑘 to node 𝑚. The objective function (1) of the model is to minimize the total cost of the operation of the fleet of buses, which is in function of the route variable cost ( 𝐶 𝑣 ) and the fixed cost (𝐶𝑓) of the operation of each bus, explained above.
The first group of constraints indicate which routes do not exist. Eq. (2) guarantees that no starting point will be visited after starting the route. Expression (3) forbids that buses pick up students after having visited node 𝑎 (highway). Eq. (4) forbids that buses leave a node and return to it consecutively. Eq. (5) forces buses to avoid starting a route from another bus’s base. Expression (6) guarantees that the routes finish when the bus arrives to school. Finally, eq. (7) avoids the scenario in which 𝑘 precedes itself.
The second group of constraints refers to the school bus transportation system. Expression (8) forces all students to be picked up only once. Expressions (9) and (10) are related to the flow conservation at nodes that represent students and the highway. They guarantee that if a bus picks up a student, it continues the route leaving the node visited. Eq. (11) guarantees that each route starts from its own starting point. Eq. (12) guarantees that when a bus picks up students, it leaves from its own base. Expression (13) guarantees that the node that represents the highway is included in all the routes used. Eq. (14)-(15) control the number of students that are being picked up at node visited (in this case, one student), and that the bus capacity is respected. Expressions (16) and (17) compute the total number of students a bus picks up. Eq. (18) guarantees that a bus adds children when that bus picks them up. Finally, eq. (19) guarantees that buses are empty when they start each route.
The third group of constraints controls the time variables and guarantees the right sequencing of buses at the highway. Expressions (20) to (27) limit the time from the moment bus k starts a route, picks up students, and travels along highway a, until it finishes in school m. Expression (28) guarantees sequencing when bus k precedes bus k1, by respecting a minimum amount of time R, in which bus k1 cannot enter the highway. Eq. (29) guarantees the consistency between arrival time of bus k to the highway and the leaving time of bus k1 to the highway when bus k does not precede bus k1. Further, eq. (30)-(31) guarantees that children arrive on time to schools (within the time window). Expressions (32)-(34) guarantee that if a bus k does not start a route, its time T1, T2, and T3 are not calculated.
Finally, the fourth group of constraints (35)-(36) guarantees the nature of the binary and positive variables, respectively. The previous groups of constraints lead to the single load base model. Moreover, there is a last group of expressions known as valid inequalities, which increase the efficiency of the model. Details will be given in section 5. Expression (37) avoids the generation of sub-trips between two nodes visited consecutively. Eq. (38)-(39) guarantee that routes are generated in ascending order.
3.2. Mathematical formulation for school bus routing and scheduling problem - mixed load strategy
The formulation for the mixed load strategy is similar to that of the single load strategy. Additional sets, parameters, variables and expressions will be presented in this numeral. In each case, the elements that remain constant for both models will be explicitly shown. For this strategy, the sets j, k, 𝜃 ?? , a, v1, j1, and k1 remain the same as in the single load strategy. Let set m be the destination schools. We include the node f representing a fictitious node where all routes finish. The parameters Q, dj, sj, w1, w2, C, ti(v,v1), Cv(v,v1) ,C and R remain the same in this model. Now, the parameter denoted as 𝜙 𝑗𝑚 is a binary parameter indicating if the student j goes to school m. The set 𝑣: 𝜃 𝑘 ∪ 𝑗 ∪ 𝑎 ∪ 𝑚 ∪ 𝑓 , where 𝜃 𝑘 <𝑗<𝑎<𝑚<𝑓. 𝑚1 is a copy of 𝑚.
In addition to decision variables 𝑋 𝑣,𝑣1,𝑘 , 𝑌 𝑘,𝑘1 , 𝐿 𝑣,𝑘 , 𝑇1 𝑣,𝑘 , 𝑇2 𝑎,𝑘 , 𝑇3 𝑎,𝑘 , 𝑇4 𝑚,𝑘 that remain the same in this model, the following decision variables are included: let 𝑊 𝑣,𝑘 be equal to 1 if node 𝑣 is visited by bus 𝑘, otherwise let if be equal to 0. Also, let 𝑇5 𝑚,𝑘 be the arrival time of bus 𝑘 at school 𝑚. The function objective of mixed load model is the same as expression (1) of the single load model. The following constraints are considered:
The first group of constraints contains the expressions (2)-(5) and (7) of the single load model. The added expressions (40) guarantees that going directly from the node a to the fictitious node is not allowed (used in the mixed load as final point of routes), and (41) guarantees that bus k does not visit more nodes after finishing the route on the fictitious node f.
In the second group, constraints remain the same as expressions (8)-(19) of the single load. Additionally, the following constraints, for the mixed load model, are defined:
Expression (42) guarantees that bus k visits school m only once if it delivers students of that school, while eq. (43) guarantees that school m is visited at least once for bus k. Expression (44) guarantees that bus k only cumulates children when they are effectively picked up by this bus. Eq. (45) guarantees that when a student is picked up in route k, this is delivered to the school destination. Expressions (46) and (47) guarantee that if a student is picked up by a bus k, it only has one predecessor node. Finally, eq. (48) guarantees that bus k finishes the route at fictitious node f after delivering students to schools.
In the third group of constraints, expressions (20) to (29) and (32) to (34) stay as in single load model. Moreover, the following expressions, for the mixed load model, are defined:
Eq. (49)-(52) calculate and control the time in which bus k arrives at node m1, immediately after visiting node m. Expressions (53)-(56) guarantee that students are delivered to schools at the established time. Constraints (57)-(58) guarantee the nature of binary and positive variables. Expressions (37)-(39), mentioned in the single load model, are used in this model as well.
4. Proposed solution methodology
A heuristic method is proposed to find near-optimal solutions to the problem and to keep better control of the computational times. The algorithm starts with a constructive approach known as “cluster first-route second”. This procedure consists of clustering students to assign them to each bus. Then, the sequence of students is computed. This approach has been applied by [25], who solved a pick-up and delivery routing problem, and [26], who develop a tabu search meta-heuristic to solve a problem that included the load balance of vehicles. Fig. 2 shows the flowchart of the heuristic for the single load and the mixed load strategies.
The first step of the algorithm is to calculate the target number of buses. This corresponds to the integer obtained after rounding up the result of the relation j/Q. Then, the algorithm searches for homogeneous generation of clusters in relation to the number of children. To do so, clusters are built by dividing the y-axis of the geographical plane, in such a way that the number of students in each cluster is balanced. A nearest-neighbor routing heuristic is applied to determine the sequence in which students are picked up and the schools that are visited (for the case of the mixed load strategy). This approach is also used by [26]. The proposed approach is similar to the one presented by [27], their metaheuristic approach solves the generalized elementary shortest path problem, which consists on finding a shortest path from a known location to a known destination by visiting clusters of nodes where a profit is collected.
Figure 2: Flowchart of developed heuristic.
Finally, the “longest processing time” rule from machine-scheduling heuristic is used to determine the order and the time intervals in which routes will be performed. The objective of this is to sequence the buses at the node that represents the highway to avoid heavy congestion. The proposed algorithm uses a backward scheduling approach, starting with the longest route to the shortest one. This tries to guarantee that the longest route arrives within the time window limit at the schools. Thus, the second-longest route is scheduled to enter the highway with a delay of R time units after the previous route is scheduled. The procedure is repeated for the other routes until the shortest route is scheduled. In the case in which an infeasibility is generated because the length of the route is longer than the defined timeline (from 0 to w 2 ), the algorithm starts the process again, increasing in 1 the number of clusters and until the maximum number of clusters is equal to the number of students.
5. Numerical Example
A numerical example is presented to present some insights of the problem. For this example, three instances of the single load model are solved independently, each one with six students. Then these are combined to solve a mixed load system with 18 students and three schools (Instance 6-18). In Fig. 3, the obtained geographical distribution for the different set of nodes is shown.
Figure 3: Geographical distribution of nodes for instance 6 with 18 students.
Figure 4 shows the solutions obtained when these instances were solved under the single load strategy. In this case, the optimal solution for the instances of School1, School2, and School3 were found in 0.19, 0.27, and 0.21 seconds respectively (0.67 seconds in total). After running the solution to solve this instance with the mixed load strategy, the optimal solution was obtained in 17 minutes. It is shown in Fig. 5.
Figure 4: Single load solution for instance 6 with 18 students.
Figure 5: Mixed load solution for instance 6 with 18 students.
Tables 1-3 show the arrival times for single load routes, illustrated in Fig. 4. Tables 4 and 5 present the corresponding times to mixed load routes, represented in Fig. 5.
Source: prepared by authorsTable 1: Single load strategy - Arrival times for route 1
Source: prepared by authorsTable 2: Single load strategy - Arrival times for route 2
Source: prepared by authorsTable 3: Single load strategy - Arrival times for route 3
Source: prepared by authorsTable 4: Mixed load strategy - Arrival times for route 1
Source: prepared by authorsTable 5: Mixed load strategy - Arrival times for route 2
The mixed load strategy, on the contrary, guarantees collaborative planning. In this manner, the entry of buses to the highway is carried out in an orderly and coordinated way for all schools, as shown in Tables 4 and 5. For this case, the arrival time is at 07:05 and 07:20, respectively. In other words, buses arrive 15 minutes apart (R=15), minimizing the bunching effect. Fig. 6 shows a Gantt graph of the arrival times at the highway for the different routes of the two strategies.
Figure 6: Gantt chart for the scheduling of buses on the highway.
6. Computational results
Random instances are built to do experiments. To generate the data, the following assumptions are considered: the geographical location per node is random on a Cartesian plane of 50 kilometers on the horizontal axis (coordinate x), and 20 kilometers on the vertical axis (coordinate y). This plane has an area of 1000km2, which represents approximately 75% of the area of Bogota. The timeline starts from 05:00a.m. to 08:30a.m. in minutes (0 to 210 minutes).
The time window for the school is from 07:30a.m. - 08:30a.m. The average time taken in traffic congestion to travel along the highway is 30 minutes, and the average speed is 36 km/hour. There are as many available buses as students, that is, k=j, and each bus has a capacity of 10 students. At each stop, the bus picks up only one student. The time one bus spends to pick up one student is 1 minute. That is, buses must be scheduled at least 15 minutes apart when they are about to enter to node that represents the highway (R = 15 minutes). The fixed cost is 50 currency units. The variable cost relates to the covered distance; it is assumed to be five (5) currency units/km.
Experiments are carried out using solver GAMS v. 23.5.1 on a personal computer with an Intel® Core™ i3-2310M 2.10GHz processor 8 Gb RAM. 51 instances are generated, which vary from four (4) to 20 students (three (3) different instances for the same problem size). The optimal solution is found in 21 instances, an integer solution is found in 23 instances, and no solution is found in seven (7) instances with a time limit of four (4) hours. All the above demonstrate the complexity of the problem to be solved, since optimal solutions are found only for instances with 10 students. According to this, valid inequalities are proposed to make the mathematical model more efficient, and in this manner, optimal solutions for more instances are computed.
For the case of the model with valid inequalities (WVI Model), the optimal solutions for 27 instances are found, an integer solution are found in 16 cases, and no solution is found in eight (8) cases. Additionally, a comparative analysis is carried out in terms of time for the 21 instances, in which an optimal solution is found, either with the base model as with WVI Model. Thus, the average time for the base model is 309.1 seconds while the average time for the WVI model is 7.87 seconds. In conclusion, for the sample of 21 instances, the WVI Model needs 2.5% of the base model time to find the optimal solution.
Table 6 shows the consolidated results according to the size of the instances (N) for both cases. Column “CPU[s]” corresponds to the average solver run time in seconds. Column “Cost” refers to the average objective function value. Finally, column “O.S.F.” presents the number of optimal solutions found per instance size group.
Source: prepared by authorsTable 6: Comparative results by solver of single load model with and without valid inequalities.
The WVI single load model structure is used to develop the mixed load model. Ten (10) instances are taken into account combining single load instances to obtain a system with multiple schools of mixed load, and in that way, carry out a comparative analysis between the two strategies, maintaining equality in the conditions of the two systems.
Table 7 shows the results for the mixed load strategy instances and the comparison with the added results obtained with single load strategy, based on the size of the instance (8-21). The column “N.R.” refers to the number of buses needed in the solutions. The column “CPU[s]” corresponds to execution time in seconds. The column “Cost” refers to the objective function value. A bold font is used to highlight when an optimal solution is found. The relationship in terms of cost (R.C) of mixed load strategy over single load strategy is also presented. (OOM means “Out of memory”).
Source: prepared by authorsTable 7: Comparative results by solver between mixed load and single load strategies
For the generated mixed load instances, the optimal solution for seven (7) out of 10 instances is found, an integer solution is found for two (2) instances, and the computer ran out of memory once. It is important to highlight that, for these nine (9) instances, the average number of routes used and the objective function value with mixed load strategy correspond to 74%, and 77% of the single load strategy, respectively.
Additionally, in terms of computational time, the mixed load strategy is not competitive in terms of time when compared to the results of the single load. In this case, it is necessary to develop a heuristic method focused on improving this measure, since in instances with sizes adapted to reality, the tool should facilitate decision making in reasonable times.
The proposed heuristic algorithm is implemented in Python. In the following, a comparative analysis of the heuristic method and the commercial solver is presented.
Table 8 shows the consolidated results based on the size of the instances (N) for both methods and the single load strategy. The column “Cost” refers to the objective function value. The column “CPU[s]” corresponds to the average time of the run in seconds. The column “N.O.S” refers to the number of optimal solutions found in instances with a determined size. The column “GAP” refers to the absolute percentage deviation of the cost obtained with the heuristic method, according to the cost of the best known solution for each of the instances.
Source: prepared by authorsTable 8: Comparative results between the commercial solver and the heuristic for the single load strategy
As observed in Table 8, with the commercial solver, 27 optimal solutions are found, while with the heuristic method 12 (56% less). Nevertheless, the average percentage (%) gap for the solutions with the heuristic method in relation to solver is 7.3%. This suggests competitiveness of the heuristic method. In the case of the solver, it is not possible to find a solution for eight (8) of the 51 instances, while the heuristic method attained a solution for each of the instances. To conclude, it is important to highlight the efficiency of computational time using the heuristic method; it required 0.12% of the average time used by the solver. In other words, there is a reduction of 99.88%.
To prove the capability of the heuristic method, three (3) random instances with 100 students are generated, in which the parameters are modified as follows: R=15, Q=30, Sj=0, Sa=10, and V=50. By running the algorithm, solutions with four (4) routes for each instance, with an average cost of 1,698.0 currency units in an average time of 0.001 seconds, are obtained.
Table 9 shows the obtained results for the instances developed with mixed load strategy, both with the heuristic method as with the solver. The column “Cost” refers to the value of the objective function. The column “CPU[s]” corresponds to the run time in seconds. A bold font highlights if an optimal solution is found. The table also shows the column “GAP”, which refers to the absolute percentage deviation of the obtained cost with the heuristic method according to the cost of the best known solution for each of the instances. (OOM stands for “Out of memory”). Seven (7) optimal solutions are found with the solver, while with the heuristic method only one. Nevertheless, the average GAP of the solutions with the heuristic method according to the solver is 7.8%. The case of the solver showed no solution for one (1) of the instances, while the heuristic method found one solution for each of the instances. The efficiency in terms of computational time of the heuristic method is important, since it spent in average only 0.02% of the time than the solver to find a solution.
Source: prepared by authorsTable 9: Comparative results between the commercial solver and the heuristic for mixed load strategy
An instance is generated by taking the three (3) largest instances generated with the single load strategy. It means, an instance with 60 students in which the parameters are modified as follows: R=8, Q=15, Sv=0, and Sa=12. This is done to prove the efficiency of the heuristic method proposed. By running the algorithm, a solution with five (5) routes, with a total cost of 2,165.0 currency units in a time of 0.002 seconds is found.
7. Conclusions and future research
Different strategies are studied to optimize the use of buses in the school transportation system, in the case of Bogota. Mixed integer formulations are presented for the single load and mixed load strategies. The proposed modelling approach decides the sequence in which students are collected and the times at which the buses take the main road to the school zone in order to reduce traffic congestion. We propose a set of valid inequalities to improve the performance of the mathematical models. Further, a comparative analysis of the performance measures and benefits between both strategies is presented.
Results show that the mixed load strategy produces a better use of the resources. In the presented experiments, the number of buses is reduced in 25% in comparison to the single load strategy. Thus, fewer buses are needed in rush hours, less vehicle congestion is produced, and student travel times are reduced. Moreover, given the complexity of the problem, a heuristic method is developed to have better control of the CPU times. Competitive solutions are computed by the proposed method, with averages gaps between 7.3% - 7.8% in the optimal solutions. Future research includes considering special-education students; stochastic travel times; a heterogeneous fleet of buses; a multi-objective version of the models to minimize environmental impacts; other performance measures; and more sophisticated exact and heuristic methodologies.
References
Referencias
Mollinedo, C. L., Movilidad Urbana Sostenible: Un reto para las ciudades del siglo XXI, Economía, Sociedad y Territorio, 6(22), pp. 1-35, 2006.
Jaramillo-Molina, C., Ríos-Rivera, P.A. and Ortiz-Lasprilla, A.R., Incremento del parque automotor y su influencia en la congestión de las principales ciudades colombianas, Universidad del Valle, Cali, Colombia, 2009.
Newton, R. and Thomas, W., Design of school bus routes by computer. Socio-Economic Planning Sciences, 3(1), pp. 75-85, 1969. DOI: 10.1016/0038-0121(69)90051-2
Park, J. and Kim, B.I., The school bus routing problem: A review. European Journal of Operational Research, 202(2), pp. 311-319, 2010. DOI: 10.1016/j.ejor.2009.05.017
Redacción Bogota, Este lunes arranca en firme carril exclusivo para rutas escolares en el norte de Bogota, EL ESPECTADOR, [en línea]. [Consultado: 16 de enero de 2017]. Disponible en: http://www.elespectador.com/noticias/bogota/lunes-arranca-firme-carril-exclusivo-rutas-escolares-el-articulo-674911.
Lu, M., Sun, C. and Zheng, S., Congestion and pollution consequences of driving-to-school trips: A case study in beijing, Transportation Research, 50, pp. 280-291, 2016. DOI: 10.1016/j.trd.2016.10.023
Kelly, J.A. and Fu, M., Sustainable school commuting – Understanding choices and identifying opportunities: A case study in Dublin, Ireland, Journal of Transport Geography, 34, pp. 221-230, 2014. DOI: 10.1016/j.jtrangeo.2013.12.010
McDonald, N.C., Steiner, R.L., Palmer, W.M., Bullock, A.N., Sisiopiku, V.P. and Lytle, B.F., Costs of school transportation: Quantifying the fiscal impacts of encouraging walking and bicycling for school travel. Transportation, 43(1), pp. 159-175, 2016. DOI: 10.1007/s11116-014-9569-7
Bodin, L.B.L., Routing and scheduling of school buses by computer. Transportation Science, 13(2), pp. 113-129, 1979. DOI: 10.1287/trsc.13.2.113
Braca, J., Bramel, J., Posner,B. and Simchi-Levi., D., A computerized approach to the New York city school bus routing problem, IIE Transactions, 29, pp. 693-702, 1997. DOI: 10.1287/trsc.13.2.113
Montoya-Torres, J.R., López-Franco, J., Nieto-Isaza, S., Felizzola-Jiménez H .and Herazo-Padilla, N., A literature review on the vehicle routing problem with multiple depots, Computers & Industrial Engineering, 79, pp. 115-129, 2015. DOI: 10.1016/j.cie.2014.10.029
Liu, R., Jiang, Z. and Geng, N., A hybrid genetic algorithm for the multi-depot open vehicle routing problem, OR Spektrum, 36(2), pp. 401-421, 2014. DOI: 10.1007/s00291-013-0346-3
Lalla-Ruiz, E., Expósito-Izquierdo, C., Taheripour S. and Voß, S., An improved formulation for the multi-depot open vehicle routing problem, OR Spektrum, 38(1), pp. 1-13, 2015. DOI: 10.1007/s00291-015-0408-9
Schittekat, P., Kinable, J., Sörensen, K., Sevaux M. and Spieksma, F., A metaheuristic for the school bus routing problem with bus stop selection, European Journ al of Operational Research, (2), pp. 518-528, 2013. DOI: 10.1016/j.ejor.2013.02.025
Manumbu, D.M., Mujuni, E. and Kuznetsov, D., Mathematical formulation model for a school bus routing problem with small instance data, Mathematical Theory and Modeling, 4(8), pp. 121-132, 2014.
Thangiah, S.R., Fergany, A., Wilson, B., Pitluga, A. and Mennell, W., School bus routing in rural school districts, Lecture Notes in Economics and Mathematical Systems, 600, pp. 209-232, 2008. DOI: 10.1007/978-3-540-73312-6_11
Euchi, J. and Mraihi, R., The urban bus routing problem in the Tunisian Case by the hybrid artificial ant colony algorithm, Swarm and Evolutionary Computation, 2, pp. 15-24, 2011. DOI: 10.1016/j.swevo.2011.10.002
Riera-Ledesma, J. and Salazar-González, J.J., Solving school bus routing using the multiple vehicle traveling purchaser problem: A branch-and-cut approach, Computers & Operations Research, 39(2), pp. 391-404, 2012. DOI: 10.1016/j.cor.2011.04.015
Zhang, J.J. and Li, Y.G., School bus problem and its algorithm, IERI Procedia, 2, pp. 8-11, 2012. DOI: 10.1016/j.ieri.2012.06.043
Arias-Rojas, J.S., Jiménez, J.F. and Montoya-Torres, J.R., Solving of school bus routing problem by ant colony optimization, Revista EIA, Escuela de Ingeniería de Antioquia, Medellín (Colombia), 17, pp. 193-208, 2012.
Park, J., Tae, H. and Kim, B.I., A Post-improvement procedure for the mixed load school bus routing problem. European Journal of Operational Research, 217(1), pp. 204-213, 2012. DOI: 10.1016/j.ejor.2011.08.022
Ellegood, W.A., Campbell, J.F. and North, J., Continuous approximation models for mixed load school bus routing, Transportation Research, Part B(77), pp. 182-198, 2015. DOI: 10.1016/j.trb.2015.03.018
Yin, P.Y., Lyu S.R. and Chuang, Y.L., Cooperative coevolutionary approach for integrated vehicle routing and scheduling using cross-dock buffering. Engineering Applications of Artificial Intelligence, 52, pp. 40-53, 2016. DOI: 10.1016/j.engappai.2016.02.006
Vahdani, B. and Zandieh, M., Scheduling trucks in Cross-Docking systems: Robust meta-heuristics. Computers & Industrial Engineering, 58(1), pp. 12-24, 2010. DOI: 10.1016/j.cie.2009.06.006
Min, H., The multiple vehicle routing problem with simultaneous delivery and pick-up points, Transportation Research Part A: General, pp. 377-386, 1989. DOI: 10.1016/0191-2607(89)90085-X
Sarmiento-Lepesqueur, A. y Quintero-Araujo, C.L., Estudio del problema de ruteo de vehículos con balance de carga: Aplicación de la meta-heurística Búsqueda Tabú, Tesis Maestría Gerencia de Operaciones, Universidad de la Sabana, Bogotá, Colombia, 2014.
Guerrero, W.J., Velasco, N., Prodhon, C. and Amaya, C.A., On the generalized elementary shortest path problem: A heuristic approach. Electronic Notes in Discrete Mathematics, 41, pp. 503-510, 2013. DOI: 10.1016/j.endm.2013.05.131
Cómo citar
IEEE
ACM
ACS
APA
ABNT
Chicago
Harvard
MLA
Turabian
Vancouver
Descargar cita
CrossRef Cited-by
1. Jacek Widuch. (2020). Smart Delivery Systems. , p.1. https://doi.org/10.1016/B978-0-12-815715-2.00006-3.
Dimensions
PlumX
Visitas a la página del resumen del artículo
Descargas
Licencia
Derechos de autor 2017 DYNA
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
El autor o autores de un artículo aceptado para publicación en cualquiera de las revistas editadas por la facultad de Minas cederán la totalidad de los derechos patrimoniales a la Universidad Nacional de Colombia de manera gratuita, dentro de los cuáles se incluyen: el derecho a editar, publicar, reproducir y distribuir tanto en medios impresos como digitales, además de incluir en artículo en índices internacionales y/o bases de datos, de igual manera, se faculta a la editorial para utilizar las imágenes, tablas y/o cualquier material gráfico presentado en el artículo para el diseño de carátulas o posters de la misma revista.
