A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem

João F.M. Sarubbi; Caio M.R. Mesquita; Elizabeth F. Wanner; Vinicius F. Santos; Cristiano M. Silva

doi:10.1109/NOMS.2016.7502983

A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem

João F.M. Sarubbi, Caio M.R. Mesquita, Elizabeth F. Wanner, Vinicius F. Santos, Cristiano M. Silva

College of Engineering and Physical Sciences

Research output: Chapter in Book/Published conference output › Conference publication

Abstract

In this work we tackle the bus stop selection step for the School Bus Routing Problem (SBRP). Our goal is to minimize the number of bus stops in order to assign all students to a bus stop respecting a home-to-bus-stop walking distance constraint. Our strategy creates a large number of possible bus stops points in a road network and uses a pseudo-random constructive heuristic algorithm to assign students to a bus stops. Our approach is tested on a real georeferenced data of a Brazilian city and is compared with a different methodology. Results demonstrate that the proposed approach is able to find good solutions for this optimization problem. Besides, the higher the number of possible points to install bus stops, the smaller is the number of bus stops required to attend all students.

Original language	English
Title of host publication	Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016
Editors	Sema Oktug, Mehmet Ulema, Cicek Cavdar, et al
Publisher	IEEE
Pages	1175-1180
Number of pages	6
ISBN (Electronic)	978-1-5090-0223-8
DOIs	https://doi.org/10.1109/NOMS.2016.7502983
Publication status	Published - 30 Jun 2016
Event	2016 IEEE/IFIP Network Operations and Management Symposium - Istanbul, Turkey Duration: 25 Apr 2016 → 29 Apr 2016

Publication series

Name
ISSN (Print)	2374-9709

Symposium

Symposium	2016 IEEE/IFIP Network Operations and Management Symposium
Abbreviated title	NOMS 2016
Country/Territory	Turkey
City	Istanbul
Period	25/04/16 → 29/04/16

Bibliographical note

© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Keywords

bus stop selection
constructive greedy heuristic
school bus routing problem

Access to Document

10.1109/NOMS.2016.7502983

Clustering students minimizing the number of bus stops for solving the school bus routing problem
© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Accepted author manuscript, 645 KB

Cite this

Sarubbi, J. F. M., Mesquita, C. M. R., Wanner, E. F., Santos, V. F., & Silva, C. M. (2016). A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem. In S. Oktug, M. Ulema, C. Cavdar, & et al (Eds.), Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016 (pp. 1175-1180). IEEE. https://doi.org/10.1109/NOMS.2016.7502983

@inproceedings{1bc132494f1d4a319f22dd2074cab22b,

title = "A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem",

abstract = "In this work we tackle the bus stop selection step for the School Bus Routing Problem (SBRP). Our goal is to minimize the number of bus stops in order to assign all students to a bus stop respecting a home-to-bus-stop walking distance constraint. Our strategy creates a large number of possible bus stops points in a road network and uses a pseudo-random constructive heuristic algorithm to assign students to a bus stops. Our approach is tested on a real georeferenced data of a Brazilian city and is compared with a different methodology. Results demonstrate that the proposed approach is able to find good solutions for this optimization problem. Besides, the higher the number of possible points to install bus stops, the smaller is the number of bus stops required to attend all students.",

keywords = "bus stop selection, constructive greedy heuristic, school bus routing problem",

author = "Sarubbi, {Jo{\~a}o F.M.} and Mesquita, {Caio M.R.} and Wanner, {Elizabeth F.} and Santos, {Vinicius F.} and Silva, {Cristiano M.}",

note = "{\textcopyright} 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.; 2016 IEEE/IFIP Network Operations and Management Symposium, NOMS 2016 ; Conference date: 25-04-2016 Through 29-04-2016",

year = "2016",

month = jun,

day = "30",

doi = "10.1109/NOMS.2016.7502983",

language = "English",

publisher = "IEEE",

pages = "1175--1180",

editor = "Sema Oktug and Mehmet Ulema and Cicek Cavdar and {et al}",

booktitle = "Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016",

address = "United States",

}

Sarubbi, JFM, Mesquita, CMR, Wanner, EF, Santos, VF & Silva, CM 2016, A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem. in S Oktug, M Ulema, C Cavdar & et al (eds), Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016. IEEE, pp. 1175-1180, 2016 IEEE/IFIP Network Operations and Management Symposium, Istanbul, Turkey, 25/04/16. https://doi.org/10.1109/NOMS.2016.7502983

A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem. / Sarubbi, João F.M.; Mesquita, Caio M.R.; Wanner, Elizabeth F. et al.
Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016. ed. / Sema Oktug; Mehmet Ulema; Cicek Cavdar; et al. IEEE, 2016. p. 1175-1180.

Research output: Chapter in Book/Published conference output › Conference publication

TY - GEN

T1 - A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem

AU - Sarubbi, João F.M.

AU - Mesquita, Caio M.R.

AU - Wanner, Elizabeth F.

AU - Santos, Vinicius F.

AU - Silva, Cristiano M.

N1 - © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

PY - 2016/6/30

Y1 - 2016/6/30

N2 - In this work we tackle the bus stop selection step for the School Bus Routing Problem (SBRP). Our goal is to minimize the number of bus stops in order to assign all students to a bus stop respecting a home-to-bus-stop walking distance constraint. Our strategy creates a large number of possible bus stops points in a road network and uses a pseudo-random constructive heuristic algorithm to assign students to a bus stops. Our approach is tested on a real georeferenced data of a Brazilian city and is compared with a different methodology. Results demonstrate that the proposed approach is able to find good solutions for this optimization problem. Besides, the higher the number of possible points to install bus stops, the smaller is the number of bus stops required to attend all students.

AB - In this work we tackle the bus stop selection step for the School Bus Routing Problem (SBRP). Our goal is to minimize the number of bus stops in order to assign all students to a bus stop respecting a home-to-bus-stop walking distance constraint. Our strategy creates a large number of possible bus stops points in a road network and uses a pseudo-random constructive heuristic algorithm to assign students to a bus stops. Our approach is tested on a real georeferenced data of a Brazilian city and is compared with a different methodology. Results demonstrate that the proposed approach is able to find good solutions for this optimization problem. Besides, the higher the number of possible points to install bus stops, the smaller is the number of bus stops required to attend all students.

KW - bus stop selection

KW - constructive greedy heuristic

KW - school bus routing problem

UR - http://ieeexplore.ieee.org/document/7502983/authors?ctx=authors

UR - http://www.scopus.com/inward/record.url?scp=84979780273&partnerID=8YFLogxK

U2 - 10.1109/NOMS.2016.7502983

DO - 10.1109/NOMS.2016.7502983

M3 - Conference publication

AN - SCOPUS:84979780273

SP - 1175

EP - 1180

BT - Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016

A2 - Oktug, Sema

A2 - Ulema, Mehmet

A2 - Cavdar, Cicek

A2 - et al,

PB - IEEE

T2 - 2016 IEEE/IFIP Network Operations and Management Symposium

Y2 - 25 April 2016 through 29 April 2016

ER -

Sarubbi JFM, Mesquita CMR, Wanner EF, Santos VF, Silva CM. A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem. In Oktug S, Ulema M, Cavdar C, et al, editors, Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016. IEEE. 2016. p. 1175-1180 doi: 10.1109/NOMS.2016.7502983

A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem

Abstract

Publication series

Symposium

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

A GRASP-based heuristic for allocating the roadside infrastructure maximizing the number of distinct vehicles experiencing contact opportunities

Cite this