Solving the service-oriented single-route school bus routing problem: Exact and heuristic solutions

Farnaz Farzadnia; Jens Lysgaard

doi:10.1016/j.ejtl.2021.100054

Solving the service-oriented single-route school bus routing problem: Exact and heuristic solutions

Department of Economics and Business Economics

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

Abstract

This paper addresses a school bus routing problem, which is classified as a location–allocation–routing problem. The problem consists of selecting pickup locations, allocating students to them, and generating a route that traverses between them. The proposed model is for a single school and a single-route. The objective is to find the subset of pickup stops aiming to minimize the total distance walked by all students from their homes to the respective pickup stops, subject to an upper bound on the route distance of connecting selected stops. We present an exact and heuristic algorithms which are developed based on a layered graph. Computational results are conducted on a series of generated benchmark instances and test data from Norway that demonstrate a good performance of the proposed approach.

Original language	English
Article number	100054
Journal	EURO Journal on Transportation and Logistics
Volume	10
ISSN	2192-4376
DOIs	https://doi.org/10.1016/j.ejtl.2021.100054
Publication status	Published - 2021

Keywords

Generalized traveling salesman problem
Layered network
Location routing
Public transportation
School bus routing

Access to Document

10.1016/j.ejtl.2021.100054Licence: CC BY-NC-ND

Cite this

@article{6134168af1e142c19313d5b512574332,

title = "Solving the service-oriented single-route school bus routing problem: Exact and heuristic solutions",

abstract = "This paper addresses a school bus routing problem, which is classified as a location–allocation–routing problem. The problem consists of selecting pickup locations, allocating students to them, and generating a route that traverses between them. The proposed model is for a single school and a single-route. The objective is to find the subset of pickup stops aiming to minimize the total distance walked by all students from their homes to the respective pickup stops, subject to an upper bound on the route distance of connecting selected stops. We present an exact and heuristic algorithms which are developed based on a layered graph. Computational results are conducted on a series of generated benchmark instances and test data from Norway that demonstrate a good performance of the proposed approach.",

keywords = "Generalized traveling salesman problem, Layered network, Location routing, Public transportation, School bus routing",

author = "Farnaz Farzadnia and Jens Lysgaard",

year = "2021",

doi = "10.1016/j.ejtl.2021.100054",

language = "English",

volume = "10",

journal = "EURO Journal on Transportation and Logistics",

issn = "2192-4376",

publisher = "Springer",

}

TY - JOUR

T1 - Solving the service-oriented single-route school bus routing problem

T2 - Exact and heuristic solutions

AU - Farzadnia, Farnaz

AU - Lysgaard, Jens

PY - 2021

Y1 - 2021

N2 - This paper addresses a school bus routing problem, which is classified as a location–allocation–routing problem. The problem consists of selecting pickup locations, allocating students to them, and generating a route that traverses between them. The proposed model is for a single school and a single-route. The objective is to find the subset of pickup stops aiming to minimize the total distance walked by all students from their homes to the respective pickup stops, subject to an upper bound on the route distance of connecting selected stops. We present an exact and heuristic algorithms which are developed based on a layered graph. Computational results are conducted on a series of generated benchmark instances and test data from Norway that demonstrate a good performance of the proposed approach.

AB - This paper addresses a school bus routing problem, which is classified as a location–allocation–routing problem. The problem consists of selecting pickup locations, allocating students to them, and generating a route that traverses between them. The proposed model is for a single school and a single-route. The objective is to find the subset of pickup stops aiming to minimize the total distance walked by all students from their homes to the respective pickup stops, subject to an upper bound on the route distance of connecting selected stops. We present an exact and heuristic algorithms which are developed based on a layered graph. Computational results are conducted on a series of generated benchmark instances and test data from Norway that demonstrate a good performance of the proposed approach.

KW - Generalized traveling salesman problem

KW - Layered network

KW - Location routing

KW - Public transportation

KW - School bus routing

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

U2 - 10.1016/j.ejtl.2021.100054

DO - 10.1016/j.ejtl.2021.100054

M3 - Journal article

SN - 2192-4376

VL - 10

JO - EURO Journal on Transportation and Logistics

JF - EURO Journal on Transportation and Logistics

M1 - 100054

ER -

Solving the service-oriented single-route school bus routing problem: Exact and heuristic solutions

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this