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

• Main Authors: Pacis, Mary Rose T., Reyes, Victor Paolo C., Ting, Kris Elliot N.
• Format: text
• Language: English
• Published: Animo Repository 2006
• Subjects: Heuristic programming; Heuristic; Operations research; Transportation engineering; Engineering
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/7931
• Institution: De La Salle University

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.