Development of a Genetic Algorithm for the School Bus Routing Problem

Published on May 31, 2015in International Journal of Software Engineering and its Applications
路 DOI :10.14257/IJSEIA.2015.9.5.11
Moo-Hong Kang2
Estimated H-index: 2
,
Sung-kwan Kim3
Estimated H-index: 3
+ 2 AuthorsMin-Je Cho3
Estimated H-index: 3
Sources
Abstract
The School Bus Routing Problem (SBRP) covers the issue of establishing plans to efficiently transport students distributed across a designated area to the relevant schools using defined resources. As with the similar Vehicle Routing Problem (VRP), the SBRP may have diverse constraints such as heterogeneous vehicles, the allotted time window and multiple depots. Many solutions for effectively solving the problem are currently being studied. By their nature, these routing problems are NP-Hard (non-deterministic polynomial-time hard) problems in which the search domains increase exponentially as they become larger, thus making it difficult to obtain solutions using an exact approach except for relatively simple and localized problems. Therefore the heuristic approach is being studied in many regions. In this study, an algorithm was developed using genetic algorithms, which stem from meta-heuristic algorithms, and the algorithm was tested against diverse problems to identify its performance and practicality.
馃摉 Papers frequently viewed together
20155.06Networks
20153.24PLOS ONE
5 Authors (Xiaopan Chen, ..., Xinyue Ye)
References23
Newest
#1Sun-Jeong Kim (Hallym University)H-Index: 2
#2Young-Woong Ko (Hallym University)H-Index: 4
Last. Jin Kim (Hallym University)H-Index: 5
view all 4 authors...
We applied genetic algorithm to nurse scheduling problem. For time complexity problem of genetic algorithm, we suggested efficient operators using a cost bit matrix of which each cell indicates any violation of constraints. A cell with 1 indicates that the corresponding assignment violates constraints and needs no further consideration. The experimental results showed that the suggested method generated a nurse scheduling faster in time and better in quality compared to the traditional genetic a...
Source
#1John Awuah AddorH-Index: 1
#2Samuel Amponsah (KNUST: Kwame Nkrumah University of Science and Technology)H-Index: 8
Last. Charles Sebil (KNUST: Kwame Nkrumah University of Science and Technology)H-Index: 4
view all 4 authors...
This research article presents a School Bus Routing Problem of Wood Bridge School Complex,Sekondi-Takoradi, Ghana. The problem was formulated as an Integer Programming Model and an Ant Colony Based Meta-heuristic for the Travelling Salesman Problem was used to solve the problem. Data on distances were collected and coded usingMatlab. Our proposed model revealed a tremendous improvement in the total route length by approximately 32%.
Source
#1Taehyeong KimH-Index: 3
#2Bum-Jin ParkH-Index: 1
School bus routing problem has been a significant concern of most people related to school and school bus system as one of vehicle routing problems. Making an appropriate problem formulation depends on how to reflect the realities of the problem. And, as the problem scope becomes wider, the problem can鈥檛 be solved only with the exact methods. So, there is need to develop an efficient heuristic method to solve more complicated problem. In this study, the model for school bus routing problem is pr...
#1Patrick SchittekatH-Index: 5
#2Joris KinableH-Index: 12
Last. Sintef IctH-Index: 1
view all 7 authors...
Existing literature on routing of school buses has focused mainly on building intricate models that attempt to capture as many real-life constraints and objectives as possible. Our work is more concerned with the bus route generation and the bus stop selection. The school bus routing problem (SBRP) is defined as a variant of the vehicle routing problem in which three simultaneous decisions have to be made : (1) determine the set of stops to visit, (2) determine for each student which stop (s)he ...
#1Moo Hong Kang (UALR: University of Arkansas at Little Rock)H-Index: 1
#2Hyung Rim Choi (Dong-a University)H-Index: 11
Last. Byung Joo ParkH-Index: 39
view all 4 authors...
Recently, the port logistics market is rapidly expanding, along with the active maritime trade. To adjust to this trend and gain a competitive advantage, competition among shipping companies at home and abroad has intensified, and many efforts are being made for the improvement of customer services and cost saving. In particular, car carriers transporting more than 80% of total car import/export volume must quickly make efforts to reduce transportation costs. Much research has been conducted to ...
Source
#1Junhyuk Park (POSTECH: Pohang University of Science and Technology)H-Index: 6
#2Byung-In Kim (POSTECH: Pohang University of Science and Technology)H-Index: 21
This paper aims to provide a comprehensive review of the school bus routing problem (SBRP). SBRP seeks to plan an efficient schedule for a fleet of school buses where each bus picks up students from various bus stops and delivers them to their designated schools while satisfying various constraints such as the maximum capacity of a bus, the maximum riding time of a student in a bus, and the time window of a school. This class of problem consists of different sub-problems involving data preparati...
Source
#1Sam R. Thangiah (SRU: Slippery Rock University of Pennsylvania)H-Index: 10
#2Adel Fergany (SRU: Slippery Rock University of Pennsylvania)H-Index: 2
Last. William Mennell (UMD: University of Maryland, College Park)H-Index: 1
view all 5 authors...
The Commonwealth of Pennsylvania has the nation鈥檚 largest rural population and the Commonwealth plays an important role in providing transportation for students to travel to their respective schools. State and local governments reimburse school districts for student transportation costs in Pennsylvania. Effective policies for governing the transportation of students can result in large cost savings for the respective governments and reduced travel time for the students. This paper presents heuri...
Source
#1Tolga Bekta艧 (UdeM: Universit茅 de Montr茅al)H-Index: 35
#2Seda Elmastas (Bilkent University)H-Index: 1
In this paper, an exact solution approach is described for solving a real-life school bus routing problem (SBRP) for transporting the students of an elementary school throughout central Ankara, Turkey. The problem is modelled as a capacitated and distance constrained open vehicle routing problem and an associated integer linear program is presented. The integer program borrows some well-known inequalities from the vehicle routing problem, which are also shown to be valid for the SBRP under consi...
Source
#1David Ripplinger (NDSU: North Dakota State University)H-Index: 7
The school bus routing problem traditionally has been defined in an urban context. However, because of the unique attributes of the problem in rural areas, traditional heuristic methods for solving the problem may produce impractical results. In many cases, these characteristics also provide the opportunity to investigate what size and mix of vehicles, whether large or small buses, conforming vans, or other modes, are most efficient. In addition, these vehicles may be further differentiated by t...
Source
#1Barrie M. Baker (Coventry University)H-Index: 9
#2M. A. Ayechew (Coventry University)H-Index: 1
This study considers the application of a genetic algorithm (GA) to the basic vehicle routing problem (VRP), in which customers of known demand are supplied from a single depot. Vehicles are subject to a weight limit and, in some cases, to a limit on the distance travelled. Only one vehicle is allowed to supply each customer.The best known results for benchmark VRPs have been obtained using tabu search or simulated annealing. GAs have seen widespread application to various combinatorial optimisa...
Source
Cited By16
Newest
#2Ricardo Saraiva de Camargo (UFMG: Universidade Federal de Minas Gerais)H-Index: 13
Last. Nilson Tadeu Ramos Nunes (UFMG: Universidade Federal de Minas Gerais)H-Index: 6
view all 5 authors...
Abstract This paper addresses the school bus routing problem with bell adjustments. This problem extends the traditional school bus routing problem by having the school working times as decision variables instead of input data. Adjusting schools working times (bell adjustment) increases managerial flexibility to lower transportation costs. On the other hand, this comes at the price of having to deal with more complex solution design and greater computational complexity, as underlaid by the scarc...
Source
#1Eda Koksal (NUS: National University of Singapore)
#2Abhishek R. Hegde (NUS: National University of Singapore)
Last. Bharadwaj Veeravalli (NUS: National University of Singapore)H-Index: 33
view all 4 authors...
Abstract Bi-objective school bus scheduling optimization problem that is a subset of vehicle fleet scheduling problem is focused in this paper. In the literature, school bus routing and scheduling problem is proven to be an NP-Hard problem. The processed data supplied by our framework is utilized to search a near-optimum schedule with the aid of reinforcement learning by evolutionary algorithms. They are named as reinforcement learning-enabled genetic algorithm (RL-enabled GA), reinforcement lea...
Source
#1Eda Koksal Ahmed (NUS: National University of Singapore)H-Index: 1
#2Zengxiang Li (Agency for Science, Technology and Research)H-Index: 12
Last. Shen Ren (Agency for Science, Technology and Research)H-Index: 6
view all 4 authors...
In this paper, we focus on a bi-objective school bus scheduling optimization problem, which is a subset of vehicle fleet scheduling problems to transport students distributed across a designated ar...
Source
#1Zhongxiang Wang (UMD: University of Maryland, College Park)H-Index: 5
#2Ali Haghani (UMD: University of Maryland, College Park)H-Index: 26
Abstract Given a trip plan (a sequence of bus stops), the integrated school bell time and bus scheduling problem simultaneously optimizes the school bell time and bus routes (the assignment of buses to serve trips at a specific time) while maintaining the minimum level-of-service requirements. The objective is to minimize the total number of buses and the total vehicle time. The previous efforts focused on the deterministic problem. However, uncertainty is unavoidable in a real-world problem. Th...
Source
#1William A. Ellegood (SHSU: Sam Houston State University)H-Index: 4
#2Stanislaus Solomon (SIUE: Southern Illinois University Edwardsville)H-Index: 2
Last. James F. Campbell (UMSL: University of Missouri鈥揝t. Louis)H-Index: 30
view all 4 authors...
Abstract The school bus routing problem (SBRP) is a challenging operations research problem that has been studied by researchers for almost 50 years. SBRP publications address one or more operational sub-problems, including: bus stop selection, bus route generation, bus route scheduling, school bell time adjustment, and strategic transportation policy issues. This paper reviews 64 new SBRP research publications and analyzes them by sub-problem type, problem characteristics and solution approach....
Source
#1Alberto Ochoa-Zezzatti (Universidad Aut贸noma de Ciudad Ju谩rez)H-Index: 6
#2Ulises Carbajal (Universidad Aut贸noma de Ciudad Ju谩rez)
Last. Sa煤l Gonz谩lez (Universidad Aut贸noma de Ciudad Ju谩rez)H-Index: 5
view all 6 authors...
Since transport is an inalienable right for students in many countries of the world, the problem of school bus routing problem (SBRP) arises, where some students spend a lot of time on these routes. Several restrictions are presented, such as the time of arrival at class and the number of students who can travel on a bus. These restrictions are considered to make the best optimization of routes, with the minimum number of buses needed to move all students, whether from a school or a school distr...
Source
#1Sinem B眉y眉ksaat莽谋 Kiri艧 (Istanbul University)H-Index: 1
#2Tuncay 脰zcan (Istanbul University)H-Index: 5
Source
#1Jacek Widuch (Silesian University of Technology)H-Index: 3
Abstract In this chapter, we present a survey on the current models and formulations of real-life vehicle routing problems. They include Vehicle Routing Problem (VRP) and its variants, Unmanned Vehicle Routing Problem (UVRP), Bicriterion and Multicriteria Bus Routing Problem (BBRP and MBRP), School Bus Routing Problem (SBRP), alongside routing problems of electric vehicles. We discuss the impact of using vehicles on the environment and using ecofriendly vehicles. We also present the methods prop...
Source
#1Ali Shafahi (UMD: University of Maryland, College Park)H-Index: 14
#2Zhongxiang Wang (UMD: University of Maryland, College Park)H-Index: 5
Last. Ali Haghani (UMD: University of Maryland, College Park)H-Index: 26
view all 3 authors...
School bus planning problem (SBPP) has drawn much research attention due to the huge costs of school transportation. In the literature, the SBPP is usually decomposed into the routing and scheduling subproblems due to its complexity. Because of the nature of the decomposition, even if all the subproblems are solved to optimality, the final solution may not be as good as the solution from the integrated model. In this paper, we present a new approach that incorporates the scheduling information (...
Source
#1Douglas Moura Miranda (UFMG: Universidade Federal de Minas Gerais)H-Index: 3
#2Ricardo Saraiva de Camargo (UFMG: Universidade Federal de Minas Gerais)H-Index: 13
Last. Nilson Tadeu Ramos Nunes (UFMG: Universidade Federal de Minas Gerais)H-Index: 6
view all 5 authors...
Abstract In this work we introduce the multi-loading school bus routing problem which extends the rural school bus routing problem with mixed loads by incorporating an innovative feature here referred to as multi-load. Whereas the mixed load variant allows students from different schools to ride the same bus at the same time, the multi-load model expands this definition by admitting students to be picked up and delivered simultaneously, regardless of their shift, commuting direction (going to or...
Source
This website uses cookies.
We use cookies to improve your online experience. By continuing to use our website we assume you agree to the placement of these cookies.
To learn more, you can find in our Privacy Policy.