Optimization of Public Sector Bus Routing Using the Chinese Postman Problem
Overview
This paper applies the Chinese Postman Problem (CPP) to optimize public sector bus routing, a real-world arc routing problem. The author proposes a solution that minimizes total mileage by dividing the network into sections respecting capacity constraints and ensuring Euler circuits exist through graph theory principles.
What this coursework covers
- Introduction to Chinese Postman Problem and its application to public bus routing optimization
- Problem formulation as arc routing problems with operational constraints including speed limits and capacity constraints
- Network division methodology using graph theory to create sections with even nodes and continuous boundaries
Preview
Chinese Postman Problem
Student’s Name
Institution Affiliation
The Chinese Postman Problem is aimed at finding the shortest route that touches all the links on a graph once or severally. Public sector bus routing is a real-world optimization problem that is an example of the CPP. Routing of buses in the public sector is a major challenge in many cities across the globe. The main objective of the private sector is to minimize costs and maximize profits. Although investors in this sector spend billions of dollars each year in such operations, a huge amount of money goes into waste as a result of poor planning. The industry faces several challenges in their quest for greater profits and more effective operating procedures. Public sector bus routing represents one of the most relevant applications that allows individuals to apply the logic proposed in the Chinese Postman Problem in studying the structure of a problem and proposing a workable solution that can help save a substantial amount of money.
Public bus routing problems can be formulated as ARPs (arc routing problems). Such problems may occur naturally such as in cases where customers located along the motorway must be picked or dropped. The ideal scenario in this case is to find the shortest road without plying the same path twice (Laporte, G. 2015). However, if some routes must be used more than once, then one has to find the shortest one that covers every motorway at least once and with the least total mileage.