A BI-LEVEL ALGORITHM PROPOSAL FOR THE INITIAL PLANNING OF FEEDER BUS ROUTES

Abstract

A sustainable urban transportation system uses different classes of transportation modes whose services should be well integrated. The Feeder Bus Route Network Problem (FBRNDP) is an important part of this integration. FBRNDP primarily deals with the provision of access to an existing mainline movement through feeder transit system usually to expand it’s the service coverage. The multiple traveling salesman problem (MTSP) has similar properties with FBRNDP, thus, making the formulation of MTSP to be adoptable for feeder bus routes. In this study, a bi-level heuristic algorithm is developed to solve this problem by clustering demand nodes around nearest destination and using genetic algorithm (GA) based on fixed start MTSP to optimize the shortest distance the salesmen will have to travel to cover the service area. The algorithm compares well to the results of a case study found in literature and shows a promising way of designing feeder bus routes strictly based on the shortest distance and variation of the number of routes required. The proposed method can be useful in the initial planning of an integrated transit system and it may serve as a seed solution in a multi-objective optimization.

Keywords

• Feeder Bus Routes Planning
• Multiple Traveling Salesman Problem
• Genetic Algorithm

BESLEYİCİ OTOBÜS ROTALARININ ÖN PLANLAMASI İÇİN İKİ DÜZEYLİ BİR ALGORİTMA ÖNERİSİ

Abstract

Sürdürülebilir bir kentsel ulaşım sisteminin, hizmetleri iyi entegre edilmesi gereken farklı ulaşım türlerini kullanması gerekmektedir. Besleyici Otobüs Rotası Ağ Tasarım Problemi (BORATP) bu entegrasyonun önemli bir parçasıdır. BORATP öncelikle hizmet kapsamını genişletmek için besleyici transit sistemi aracılığıyla mevcut bir ana hat hareketine erişim sağlanması ile ilgilenir. Çoklu seyahat eden satıcı problemi (ÇSESP), BORATP'ye benzer özellikler içermektedir ve bu nedenle ÇSESP formülasyonu besleyici otobüs rotalarının optimizasyonu için kullanılmaya uygundur. Bu çalışmada, BORATP’nin çözümü için talep noktalarını en yakın hedef etrafında kümeleyen ve satıcıların hizmeti kapsaması için seyahat etmesi gereken en kısa mesafeyi sabit başlangıçlı ÇSESP’ye dayalı bir genetik algoritma (GA) kullanarak optimize eden iki seviyeli deneysel bir algoritma geliştirilmiştir. Algoritma, literatürde bulunan bir vaka çalışmasının sonuçlarıyla karşılaştırılarak ve iyi bir uyum sağladığı görülmüş ve gerekli olan rota sayısının en kısa mesafesine ve varyasyonuna dayanarak besleyici otobüs güzergahları tasarlamak için cazip bir yöntem olduğu ortaya konmuştur. Önerilen yöntem, entegre bir toplu ulaşım sisteminin ilksel planlamasında yararlı olabilecek ve çok amaçlı bir optimizasyonda bir başlangıç çözümü olarak kullanılabilecektir.

Keywords

• Besleyici Otobüs Rota Planlaması
• Çoklu Seyahat Satıcısı Sorunu
• Genetik Algoritma

References

1. Arostegui Jr, M. A., Kadipasaoglu, S. N., & Khumawala, B. M. (2006). An empirical comparison of Tabu search, simulated annealing, and genetic algorithms for facilities location problems. International Journal of Production Economics, 103(2), 742-754.
2. Arya, V., Goyal, A., & Jaiswal, V. (2014). An optimal solution to multiple traveling salesperson problem using a modified genetic algorithm. International Journal of Application or Innovation in Engineering & Management (IJAIEM), 3(1).
3. Başkan, Ö., Ozan, C., Ceylan, H., (2019). Optimization of reserve capacity in urban road networks based on traffic signal timings, Journal of Engineering Sciences and Design, 7(4), 787-795
4. Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3), 209-219
5. Carter, A. E., & Ragsdale, C. T. (2006). A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European journal of operational research, 175(1), 246-257.
6. Chien, S., Yang, Z., & Hou, E. (2001). Genetic algorithm approach for transit route planning and design. Journal of transportation engineering, 127(3), 200-207.
7. Eldrandy, K. A., Ahmed, A. H. N., & AbdAllah, A. F. (2008, December). Routing Problems: A Survey. In The 43rd Annual Conference on Statistics, Computer Sciences and Operations Research (pp. 51-70)
8. Erkan, İ. (2014). Evaluation of level of service for Isparta Süleyman Demirel Airport terminal building, Journal of Engineering Sciences and Design, 2(2), 113-118.

9. Goldberg, D., 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, Boston: MA: Addison-Wesley Professional.
10. Joseph Kirk (2020). Fixed Start Open Multiple Traveling Salesmen Problem Genetic Algorithm.
11. (https://www.mathworks.com/matlabcentral/fileexchange/21302-fixed-start-open-multiple-traveling salesmen-problem-genetic-algorithm), MATLAB Central File Exchange. Retrieved December, 2019.
12. Karakatič, S., & Podgorelec, V. (2015). A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27, 519-532.
13. Kepaptsoglou, K., & Karlaftis, M. (2009). Transit route network design problem. Journal of transportation engineering, 135(8), 491-505.
14. Király, A., & Abonyi, J. (2011). Optimization of multiple traveling salesmen problem by a novel representation based genetic algorithm. In Intelligent computational optimization in engineering (pp. 241-269). Springer, Berlin, Heidelberg.
15. Kuah G, K, and Perl J.1989. The feeder-bus network-design problem. Journal of the Operational Research Society; vol.40, no.8, pp. 751–767
16. Kuan S, N, Ong H, L, and Ng K. M. 2006. Solving the feeder bus network design problem by genetic algorithms and ant colony optimization. Advances in Engineering Software, vol.37, no.6, pp. 351–359.
17. Kuan, S. N., Ong, H. L., & Ng, K. M. (2004). Applying metaheuristics to feeder bus network design problem. Asia-Pacific Journal of Operational Research, 21(04) 543-560.
18. Park, Y. B. (2001). A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines. International Journal of Production Economics, 73(2), 175-188.
19. Shrivastav, P., & Dhingra, S. L. (2001). Development of feeder routes for suburban railway stations using heuristic approach. Journal of transportation engineering, 127(4), 334-341.
20. Singh, A. (2016). A review on algorithms used to solve multiple traveling salesman problem. International Research Journal of Engineering and Technology (IRJET), 3(4), 598-603.
21. Tang L, Liu J, Rong A, Yang Z. (2000). A multiple traveling salesman problem models for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European Journal of Operational Research 124:267–82.
22. Yaslı, F., Güvensan, M.A., (2019). Discriminative features for energy-constrained devices on transportation mode detection, Journal of Engineering Sciences and Design, 7(1), 90-102.
23. Yu, Z., Jinhai, L., Guochang, G., Rubo, Z., & Haiyan, Y. (2002, June). An implementation of evolutionary computation for path planning of cooperative mobile robots. In Proceedings of the 4th World Congress on Intelligent Control and Automation (Cat. No. 02EX527) (Vol. 3, pp. 1798-1802). IEEE.
24. Zhang T, Gruver W A, and Smith M H. (1999). Team scheduling by a genetic search. Proceedings of The Second International Conference On Intelligent Processing and Manufacturing of Materials.2, 839-44.