A heuristic approach to real time dynamic provincial bus routing and scheduling with multiple terminals, and time windows

Date of Publication

2006

Document Type

Bachelor's Thesis

Degree Name

Bachelor of Science in Industrial Engineering

Subject Categories

Engineering

College

Gokongwei College of Engineering

Department/Unit

Industrial and Systems Engineering

Thesis Adviser

Dennis Cruz

Defense Panel Chair

Dennis Hui Beng

Defense Panel Member

Bryan, Gobaco

Abstract/Summary

Vehicle Routing Problem (VRP) has been a relentless interest in the field of Operations Research. Routing of vehicles has always been an important aspect of any transportation system because of the advantages that it brings about most especially in terms of cost minimization. The evaluation of VRP is seen in many researches conducted that opt to capture real-world setting in their systems. This brings about the emergence of using dynamic environment and real-time data.

In most cases, VRP focuses more on collection system rather than in public transportation systems, like that of a provincial bus transportation system. This study will consider a provincial bus system in a dynamic environment that is triggered by real-time demand. In a provincial bus transportation system, the complexity of demand, heterogeneous fleet of vehicles, and multiple terminals that is capable of loading and unloading are the things that defines the system from a typical collection system. This study aims to maximize profit by finding the best possible route of a bus upon the arrival of the real-time demand.

A suggested heuristic is developed in order to get the near optimal solution to the problem introduced. A heuristic is used since it is a more practical tool to use than mathematical modeling with NP-hard problems like that of a VRP. Also, a dynamic environment would suggest a heuristic to capture what is really happening within the system.

It was found out that the heuristic developed generated solutions that are included in the top 10 routes using the complete enumeration method. Also, the complexity analysis concluded a polynomial function, which implies that the heuristic will be hard to perform on large-scale models.

Through the sensitivity analysis, it was seen that number of reroutes increases faster as the gap between the assigned and unassigned demand increases. It was also found out that the major driver of rerouting would be the price. On the other hand, based on the findings in the sensitivity analysis, traveling cost, cost of cancellation, and number of trips seem to have no vast effect in the rerouting to be performed.

Abstract Format

html

Language

English

Format

Print

Accession Number

TU13831

Shelf Location

Archives, The Learning Commons, 12F, Henry Sy Sr. Hall

Physical Description

[2], vii, 212 leaves : ill. ; 28 cm.

Keywords

Heuristic programming; Heuristic; Operations research; Transportation engineering

This document is currently not available here.

Share

COinS